MLIR
18.0.0git
|
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... | |
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.
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.
|
protected |
An index-typed value or the dimension of a shaped-type value.
Definition at line 264 of file ValueBoundsOpInterface.h.
|
protected |
Definition at line 70 of file ValueBoundsOpInterface.cpp.
|
protected |
Bound the given column in the underlying constraint set by the given expression.
Definition at line 87 of file ValueBoundsOpInterface.cpp.
References mlir::FlatLinearConstraints::addBound(), cstr, mlir::failed(), mlir::AffineMap::get(), mlir::presburger::IntegerRelation::getNumDimVars(), and mlir::presburger::IntegerRelation::getNumSymbolVars().
|
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().
|
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().
|
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().
|
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:
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().
|
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().
|
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().
|
static |
Definition at line 514 of file ValueBoundsOpInterface.cpp.
References computeConstantBound().
|
static |
Definition at line 474 of file ValueBoundsOpInterface.cpp.
References mlir::FlatLinearConstraints::addBound(), bound(), cstr, mlir::presburger::EQ, mlir::failure(), mlir::presburger::IntegerRelation::getConstantBound64(), mlir::AffineMap::getContext(), mlir::AffineMap::getNumDims(), mlir::AffineMap::getNumResults(), mlir::AffineMap::getResult(), and mlir::AffineExpr::replaceDimsAndSymbols().
|
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().
|
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().
|
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().
|
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().
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().
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().
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().
|
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().
|
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.
|
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().
|
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.
|
protected |
Project out all columns for which the condition holds.
Definition at line 258 of file ValueBoundsOpInterface.cpp.
References positionToValueDim, and projectOut().
|
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().
|
protected |
Builder for constructing affine expressions.
Definition at line 317 of file ValueBoundsOpInterface.h.
Referenced by getExpr().
|
protected |
Constraint system of equalities and inequalities.
Definition at line 314 of file ValueBoundsOpInterface.h.
Referenced by addBound(), computeBound(), computeConstantBound(), getExpr(), insert(), mlir::ValueBoundsConstraintSet::BoundBuilder::operator<(), mlir::ValueBoundsConstraintSet::BoundBuilder::operator<=(), mlir::ValueBoundsConstraintSet::BoundBuilder::operator==(), mlir::ValueBoundsConstraintSet::BoundBuilder::operator>(), mlir::ValueBoundsConstraintSet::BoundBuilder::operator>=(), and projectOut().
|
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().
|
protected |
Mapping of columns to values/shape dimensions.
Definition at line 306 of file ValueBoundsOpInterface.h.
Referenced by insert(), processWorklist(), and projectOut().
Reverse mapping of values/shape dimensions to columns.
Definition at line 308 of file ValueBoundsOpInterface.h.
Referenced by getExpr(), getPos(), insert(), and projectOut().
|
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().