MLIR  18.0.0git
Classes | Public Types | Public Member Functions | Static Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | Static Protected Attributes | List of all members
mlir::ValueBoundsConstraintSet Class Reference

A helper class to be used with ValueBoundsOpInterface. More...

#include "mlir/Interfaces/ValueBoundsOpInterface.h"

Classes

class  BoundBuilder
 Helper class that builds a bound for a shaped value dimension or index-typed value. More...
 

Public Types

using StopConditionFn = function_ref< bool(Value, std::optional< int64_t >)>
 The stop condition when traversing the backward slice of a shaped value/ index-type value. More...
 

Public Member Functions

BoundBuilder bound (Value value)
 Add a bound for the given index-typed value or shaped value. More...
 
AffineExpr getExpr (Value value, std::optional< int64_t > dim=std::nullopt)
 Return an expression that represents the given index-typed value or shaped value dimension. More...
 
AffineExpr getExpr (OpFoldResult ofr)
 Return an expression that represents a constant or index-typed SSA value. More...
 
AffineExpr getExpr (int64_t constant)
 Return an expression that represents a constant. More...
 

Static Public Member Functions

static LogicalResult computeBound (AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, Value value, std::optional< int64_t > dim, StopConditionFn stopCondition, bool closedUB=false)
 Compute a bound for the given index-typed value or shape dimension size. More...
 
static LogicalResult computeDependentBound (AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, Value value, std::optional< int64_t > dim, ValueDimList dependencies, bool closedUB=false)
 Compute a bound in terms of the values/dimensions in dependencies. More...
 
static LogicalResult computeIndependentBound (AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, Value value, std::optional< int64_t > dim, ValueRange independencies, bool closedUB=false)
 Compute a bound in that is independent of all values in independencies. More...
 
static FailureOr< int64_t > computeConstantBound (presburger::BoundType type, Value value, std::optional< int64_t > dim=std::nullopt, StopConditionFn stopCondition=nullptr, bool closedUB=false)
 Compute a constant bound for the given affine map, where dims and symbols are bound to the given operands. More...
 
static FailureOr< int64_t > computeConstantBound (presburger::BoundType type, AffineMap map, ValueDimList mapOperands, StopConditionFn stopCondition=nullptr, bool closedUB=false)
 
static FailureOr< int64_t > computeConstantBound (presburger::BoundType type, AffineMap map, ArrayRef< Value > mapOperands, StopConditionFn stopCondition=nullptr, bool closedUB=false)
 
static FailureOr< int64_t > computeConstantDelta (Value value1, Value value2, std::optional< int64_t > dim1=std::nullopt, std::optional< int64_t > dim2=std::nullopt)
 Compute a constant delta between the given two values. More...
 
static FailureOr< bool > areEqual (Value value1, Value value2, std::optional< int64_t > dim1=std::nullopt, std::optional< int64_t > dim2=std::nullopt)
 Compute whether the given values/dimensions are equal. More...
 
static FailureOr< bool > areEqual (OpFoldResult ofr1, OpFoldResult ofr2)
 Compute whether the given values/attributes are equal. More...
 
static FailureOr< bool > areOverlappingSlices (MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
 Return "true" if the given slices are guaranteed to be overlapping. More...
 
static FailureOr< bool > areEquivalentSlices (MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
 Return "true" if the given slices are guaranteed to be equivalent. More...
 

Protected Types

using ValueDim = std::pair< Value, int64_t >
 An index-typed value or the dimension of a shaped-type value. More...
 

Protected Member Functions

 ValueBoundsConstraintSet (MLIRContext *ctx)
 
void processWorklist (StopConditionFn stopCondition)
 Iteratively process all elements on the worklist until an index-typed value or shaped value meets stopCondition. More...
 
void addBound (presburger::BoundType type, int64_t pos, AffineExpr expr)
 Bound the given column in the underlying constraint set by the given expression. More...
 
int64_t getPos (Value value, std::optional< int64_t > dim=std::nullopt) const
 Return the column position of the given value/dimension. More...
 
int64_t insert (Value value, std::optional< int64_t > dim, bool isSymbol=true)
 Insert a value/dimension into the constraint set. More...
 
int64_t insert (bool isSymbol=true)
 Insert an anonymous column into the constraint set. More...
 
void projectOut (int64_t pos)
 Project out the given column in the constraint set. More...
 
void projectOut (function_ref< bool(ValueDim)> condition)
 Project out all columns for which the condition holds. More...
 

Protected Attributes

SmallVector< std::optional< ValueDim > > positionToValueDim
 Mapping of columns to values/shape dimensions. More...
 
DenseMap< ValueDim, int64_t > valueDimToPosition
 Reverse mapping of values/shape dimensions to columns. More...
 
std::queue< int64_t > worklist
 Worklist of values/shape dimensions that have not been processed yet. More...
 
FlatLinearConstraints cstr
 Constraint system of equalities and inequalities. More...
 
Builder builder
 Builder for constructing affine expressions. More...
 

Static Protected Attributes

static constexpr int64_t kIndexValue = -1
 Dimension identifier to indicate a value is index-typed. More...
 

Detailed Description

A helper class to be used with ValueBoundsOpInterface.

This class stores a constraint system and mapping of constrained variables to index-typed values or dimension sizes of shaped values.

Interface implementations of ValueBoundsOpInterface use addBounds to insert constraints about their results and/or region block arguments into the constraint set in the form of an AffineExpr. When a bound should be expressed in terms of another value/dimension, getExpr can be used to retrieve an AffineExpr that represents the specified value/dimension.

When a value/dimension is retrieved for the first time through getExpr, it is added to an internal worklist. See computeBound for more details.

Note: Any modification of existing IR invalides the data stored in this class. Adding new operations is allowed.

Definition at line 66 of file ValueBoundsOpInterface.h.

Member Typedef Documentation

◆ StopConditionFn

using mlir::ValueBoundsConstraintSet::StopConditionFn = function_ref<bool(Value, std::optional<int64_t> )>

The stop condition when traversing the backward slice of a shaped value/ index-type value.

The traversal continues until the stop condition evaluates to "true" for a value.

The first parameter of the function is the shaped value/index-typed value. The second parameter is the dimension in case of a shaped value.

Definition at line 116 of file ValueBoundsOpInterface.h.

◆ ValueDim

using mlir::ValueBoundsConstraintSet::ValueDim = std::pair<Value, int64_t>
protected

An index-typed value or the dimension of a shaped-type value.

Definition at line 264 of file ValueBoundsOpInterface.h.

Constructor & Destructor Documentation

◆ ValueBoundsConstraintSet()

ValueBoundsConstraintSet::ValueBoundsConstraintSet ( MLIRContext ctx)
protected

Definition at line 70 of file ValueBoundsOpInterface.cpp.

Member Function Documentation

◆ addBound()

void ValueBoundsConstraintSet::addBound ( presburger::BoundType  type,
int64_t  pos,
AffineExpr  expr 
)
protected

◆ areEqual() [1/2]

FailureOr< bool > ValueBoundsConstraintSet::areEqual ( OpFoldResult  ofr1,
OpFoldResult  ofr2 
)
static

Compute whether the given values/attributes are equal.

Return "failure" if equality could not be determined.

ofr1/ofr2 must be of index type.

Definition at line 553 of file ValueBoundsOpInterface.cpp.

References computeConstantBound(), mlir::presburger::EQ, mlir::failed(), mlir::failure(), mlir::foldAttributesIntoMap(), mlir::AffineMap::get(), mlir::Builder::getAffineSymbolExpr(), and mlir::OpFoldResult::getContext().

◆ areEqual() [2/2]

FailureOr< bool > ValueBoundsConstraintSet::areEqual ( Value  value1,
Value  value2,
std::optional< int64_t >  dim1 = std::nullopt,
std::optional< int64_t >  dim2 = std::nullopt 
)
static

Compute whether the given values/dimensions are equal.

Return "failure" if equality could not be determined.

dim1/dim2 must be nullopt if and only if value1/value2 are index-typed.

Definition at line 542 of file ValueBoundsOpInterface.cpp.

References computeConstantDelta(), mlir::failed(), and mlir::failure().

Referenced by areEquivalentSlices(), and mlir::vector::isDisjointTransferIndices().

◆ areEquivalentSlices()

FailureOr< bool > ValueBoundsConstraintSet::areEquivalentSlices ( MLIRContext ctx,
HyperrectangularSlice  slice1,
HyperrectangularSlice  slice2 
)
static

Return "true" if the given slices are guaranteed to be equivalent.

Return "false" if the given slices are guaranteed to be non-equivalent. Return "failure" if unknown.

Slices are equivalent if their offsets, sizes and strices are equal.

Definition at line 643 of file ValueBoundsOpInterface.cpp.

References areEqual(), mlir::failed(), mlir::failure(), mlir::HyperrectangularSlice::getMixedOffsets(), mlir::HyperrectangularSlice::getMixedSizes(), and mlir::HyperrectangularSlice::getMixedStrides().

◆ areOverlappingSlices()

FailureOr< bool > ValueBoundsConstraintSet::areOverlappingSlices ( MLIRContext ctx,
HyperrectangularSlice  slice1,
HyperrectangularSlice  slice2 
)
static

Return "true" if the given slices are guaranteed to be overlapping.

Return "false" if the given slices are guaranteed to be non-overlapping. Return "failure" if unknown.

Slices are overlapping if for all dimensions:

  • offset1 + size1 * stride1 <= offset2
  • and offset2 + size2 * stride2 <= offset1

Slice are non-overlapping if the above constraint is not satisfied for at least one dimension.

Definition at line 578 of file ValueBoundsOpInterface.cpp.

References computeConstantBound(), mlir::presburger::EQ, mlir::failed(), mlir::failure(), mlir::foldAttributesIntoMap(), mlir::AffineMap::get(), mlir::Builder::getAffineSymbolExpr(), mlir::HyperrectangularSlice::getMixedOffsets(), mlir::HyperrectangularSlice::getMixedSizes(), mlir::HyperrectangularSlice::getMixedStrides(), and mlir::succeeded().

◆ bound()

BoundBuilder mlir::ValueBoundsConstraintSet::bound ( Value  value)
inline

Add a bound for the given index-typed value or shaped value.

This function returns a builder that adds the bound.

Definition at line 241 of file ValueBoundsOpInterface.h.

Referenced by computeBound(), computeConstantBound(), and processWorklist().

◆ computeBound()

LogicalResult ValueBoundsConstraintSet::computeBound ( AffineMap resultMap,
ValueDimList mapOperands,
presburger::BoundType  type,
Value  value,
std::optional< int64_t >  dim,
StopConditionFn  stopCondition,
bool  closedUB = false 
)
static

Compute a bound for the given index-typed value or shape dimension size.

The computed bound is stored in resultMap. The operands of the bound are stored in mapOperands. An operand is either an index-type SSA value or a shaped value and a dimension.

dim must be nullopt if and only if value is index-typed. The bound is computed in terms of values/dimensions for which stopCondition evaluates to "true". To that end, the backward slice (reverse use-def chain) of the given value is visited in a worklist-driven manner and the constraint set is populated according to ValueBoundsOpInterface for each visited value.

By default, lower/equal bounds are closed and upper bounds are open. If closedUB is set to "true", upper bounds are also closed.

Definition at line 273 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), bound(), cstr, mlir::failure(), mlir::AffineMap::get(), mlir::Builder::getAffineConstantExpr(), mlir::Builder::getAffineDimExpr(), mlir::Builder::getAffineSymbolExpr(), mlir::Value::getContext(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::FlatLinearConstraints::getSliceBounds(), mlir::Value::getType(), mlir::Type::isIndex(), kIndexValue, mlir::presburger::IntegerRelation::projectOut(), and mlir::success().

Referenced by computeDependentBound(), and reifyValueBound().

◆ computeConstantBound() [1/3]

FailureOr< int64_t > ValueBoundsConstraintSet::computeConstantBound ( presburger::BoundType  type,
AffineMap  map,
ArrayRef< Value mapOperands,
StopConditionFn  stopCondition = nullptr,
bool  closedUB = false 
)
static

Definition at line 514 of file ValueBoundsOpInterface.cpp.

References computeConstantBound().

◆ computeConstantBound() [2/3]

FailureOr< int64_t > ValueBoundsConstraintSet::computeConstantBound ( presburger::BoundType  type,
AffineMap  map,
ValueDimList  mapOperands,
StopConditionFn  stopCondition = nullptr,
bool  closedUB = false 
)
static

◆ computeConstantBound() [3/3]

FailureOr< int64_t > ValueBoundsConstraintSet::computeConstantBound ( presburger::BoundType  type,
Value  value,
std::optional< int64_t >  dim = std::nullopt,
StopConditionFn  stopCondition = nullptr,
bool  closedUB = false 
)
static

Compute a constant bound for the given affine map, where dims and symbols are bound to the given operands.

The affine map must have exactly one result.

This function traverses the backward slice of the given operands in a worklist-driven manner until stopCondition evaluates to "true". The constraint set is populated according to ValueBoundsOpInterface for each visited value. (No constraints are added for values for which the stop condition evaluates to "true".)

The stop condition is optional: If none is specified, the backward slice is traversed in a breadth-first manner until a constant bound could be computed.

By default, lower/equal bounds are closed and upper bounds are open. If closedUB is set to "true", upper bounds are also closed.

Definition at line 460 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), mlir::AffineMap::get(), mlir::Builder::getAffineDimExpr(), and mlir::Value::getContext().

Referenced by areEqual(), areOverlappingSlices(), computeConstantBound(), computeConstantDelta(), computePaddedShape(), and mlir::affine::fullyComposeAndComputeConstantDelta().

◆ computeConstantDelta()

FailureOr< int64_t > ValueBoundsConstraintSet::computeConstantDelta ( Value  value1,
Value  value2,
std::optional< int64_t >  dim1 = std::nullopt,
std::optional< int64_t >  dim2 = std::nullopt 
)
static

Compute a constant delta between the given two values.

Return "failure" if a constant delta could not be determined.

dim1/dim2 must be nullopt if and only if value1/value2 are index-typed.

Definition at line 526 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), computeConstantBound(), mlir::presburger::EQ, mlir::AffineMap::get(), mlir::Builder::getAffineDimExpr(), and mlir::Value::getContext().

Referenced by areEqual(), and mlir::vector::isDisjointTransferIndices().

◆ computeDependentBound()

LogicalResult ValueBoundsConstraintSet::computeDependentBound ( AffineMap resultMap,
ValueDimList mapOperands,
presburger::BoundType  type,
Value  value,
std::optional< int64_t >  dim,
ValueDimList  dependencies,
bool  closedUB = false 
)
static

Compute a bound in terms of the values/dimensions in dependencies.

The computed bound consists of only constant terms and dependent values (or dimension sizes thereof).

Definition at line 414 of file ValueBoundsOpInterface.cpp.

References computeBound().

◆ computeIndependentBound()

LogicalResult ValueBoundsConstraintSet::computeIndependentBound ( AffineMap resultMap,
ValueDimList mapOperands,
presburger::BoundType  type,
Value  value,
std::optional< int64_t >  dim,
ValueRange  independencies,
bool  closedUB = false 
)
static

Compute a bound in that is independent of all values in independencies.

Independencies are the opposite of dependencies. The computed bound does not contain any SSA values that are part of independencies. E.g., this function can be used to make ops hoistable from loops. To that end, ops must be made independent of loop induction variables (in the case of "for" loops). Loop induction variables are the independencies; they may not appear in the computed bound.

Definition at line 426 of file ValueBoundsOpInterface.cpp.

References worklist.

Referenced by makeIndependent().

◆ getExpr() [1/3]

AffineExpr ValueBoundsConstraintSet::getExpr ( int64_t  constant)

Return an expression that represents a constant.

Definition at line 137 of file ValueBoundsOpInterface.cpp.

References builder, and mlir::Builder::getAffineConstantExpr().

◆ getExpr() [2/3]

AffineExpr ValueBoundsConstraintSet::getExpr ( OpFoldResult  ofr)

Return an expression that represents a constant or index-typed SSA value.

In case of a value, if this value was not used so far, it is added to the worklist.

Definition at line 129 of file ValueBoundsOpInterface.cpp.

References builder, mlir::Builder::getAffineConstantExpr(), mlir::getConstantIntValue(), and getExpr().

◆ getExpr() [3/3]

AffineExpr ValueBoundsConstraintSet::getExpr ( Value  value,
std::optional< int64_t >  dim = std::nullopt 
)

Return an expression that represents the given index-typed value or shaped value dimension.

If this value/dimension was not used so far, it is added to the worklist.

dim must be nullopt if and only if the given value is of index type.

Definition at line 102 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), builder, cstr, mlir::Builder::getAffineConstantExpr(), mlir::Builder::getAffineDimExpr(), mlir::Builder::getAffineSymbolExpr(), mlir::getConstantIntValue(), mlir::presburger::IntegerRelation::getNumDimVars(), getPos(), mlir::Value::getType(), insert(), kIndexValue, and valueDimToPosition.

Referenced by getExpr(), and processWorklist().

◆ getPos()

int64_t ValueBoundsConstraintSet::getPos ( Value  value,
std::optional< int64_t >  dim = std::nullopt 
) const
protected

Return the column position of the given value/dimension.

Asserts that the value/dimension exists in the constraint set.

Definition at line 173 of file ValueBoundsOpInterface.cpp.

References assertValidValueDim(), kIndexValue, and valueDimToPosition.

Referenced by getExpr().

◆ insert() [1/2]

int64_t ValueBoundsConstraintSet::insert ( bool  isSymbol = true)
protected

Insert an anonymous column into the constraint set.

The column is not bound to any value/dimension. If isSymbol is set to "false", a dimension is added.

Note: There are certain affine restrictions wrt. dimensions. E.g., they cannot be multiplied. Furthermore, bounds can only be queried for dimensions but not for symbols.

Definition at line 162 of file ValueBoundsOpInterface.cpp.

References mlir::presburger::IntegerRelation::appendVar(), cstr, positionToValueDim, and valueDimToPosition.

◆ insert() [2/2]

int64_t ValueBoundsConstraintSet::insert ( Value  value,
std::optional< int64_t >  dim,
bool  isSymbol = true 
)
protected

Insert a value/dimension into the constraint set.

If isSymbol is set to "false", a dimension is added. The value/dimension is added to the worklist.

Note: There are certain affine restrictions wrt. dimensions. E.g., they cannot be multiplied. Furthermore, bounds can only be queried for dimensions but not for symbols.

Definition at line 141 of file ValueBoundsOpInterface.cpp.

References mlir::presburger::IntegerRelation::appendVar(), assertValidValueDim(), cstr, kIndexValue, positionToValueDim, valueDimToPosition, and worklist.

Referenced by getExpr().

◆ processWorklist()

void ValueBoundsConstraintSet::processWorklist ( StopConditionFn  stopCondition)
protected

Iteratively process all elements on the worklist until an index-typed value or shaped value meets stopCondition.

Such values are not processed any further.

Definition at line 194 of file ValueBoundsOpInterface.cpp.

References bound(), mlir::get(), mlir::Value::getDefiningOp(), getExpr(), getOwnerOfValue(), mlir::Value::getType(), kIndexValue, positionToValueDim, and worklist.

◆ projectOut() [1/2]

void ValueBoundsConstraintSet::projectOut ( function_ref< bool(ValueDim)>  condition)
protected

Project out all columns for which the condition holds.

Definition at line 258 of file ValueBoundsOpInterface.cpp.

References positionToValueDim, and projectOut().

◆ projectOut() [2/2]

void ValueBoundsConstraintSet::projectOut ( int64_t  pos)
protected

Project out the given column in the constraint set.

Definition at line 242 of file ValueBoundsOpInterface.cpp.

References cstr, positionToValueDim, mlir::presburger::IntegerRelation::projectOut(), and valueDimToPosition.

Referenced by projectOut().

Member Data Documentation

◆ builder

Builder mlir::ValueBoundsConstraintSet::builder
protected

Builder for constructing affine expressions.

Definition at line 317 of file ValueBoundsOpInterface.h.

Referenced by getExpr().

◆ cstr

FlatLinearConstraints mlir::ValueBoundsConstraintSet::cstr
protected

◆ kIndexValue

constexpr int64_t mlir::ValueBoundsConstraintSet::kIndexValue = -1
staticconstexprprotected

Dimension identifier to indicate a value is index-typed.

This is used for internal data structures/API only.

Definition at line 261 of file ValueBoundsOpInterface.h.

Referenced by computeBound(), getExpr(), getPos(), insert(), and processWorklist().

◆ positionToValueDim

SmallVector<std::optional<ValueDim> > mlir::ValueBoundsConstraintSet::positionToValueDim
protected

Mapping of columns to values/shape dimensions.

Definition at line 306 of file ValueBoundsOpInterface.h.

Referenced by insert(), processWorklist(), and projectOut().

◆ valueDimToPosition

DenseMap<ValueDim, int64_t> mlir::ValueBoundsConstraintSet::valueDimToPosition
protected

Reverse mapping of values/shape dimensions to columns.

Definition at line 308 of file ValueBoundsOpInterface.h.

Referenced by getExpr(), getPos(), insert(), and projectOut().

◆ worklist

std::queue<int64_t> mlir::ValueBoundsConstraintSet::worklist
protected

Worklist of values/shape dimensions that have not been processed yet.

Definition at line 311 of file ValueBoundsOpInterface.h.

Referenced by computeIndependentBound(), insert(), and processWorklist().


The documentation for this class was generated from the following files: