15 #include "llvm/ADT/APSInt.h"
16 #include "llvm/Support/Debug.h"
18 #define DEBUG_TYPE "value-bounds-op-interface"
25 #include "mlir/Interfaces/ValueBoundsOpInterface.cpp.inc"
29 if (
auto bbArg = dyn_cast<BlockArgument>(value))
37 : mixedOffsets(offsets), mixedSizes(sizes), mixedStrides(strides) {
38 assert(offsets.size() == sizes.size() &&
39 "expected same number of offsets, sizes, strides");
40 assert(offsets.size() == strides.size() &&
41 "expected same number of offsets, sizes, strides");
46 : mixedOffsets(offsets), mixedSizes(sizes) {
47 assert(offsets.size() == sizes.size() &&
48 "expected same number of offsets and sizes");
53 mixedStrides.append(offsets.size(),
Builder(ctx).getIndexAttr(1));
58 op.getMixedStrides()) {}
63 if (
auto val = llvm::dyn_cast_if_present<Value>(ofr)) {
66 return intVal.getSExtValue();
70 Attribute attr = llvm::dyn_cast_if_present<Attribute>(ofr);
71 if (
auto intAttr = dyn_cast_or_null<IntegerAttr>(attr))
72 return intAttr.getValue().getSExtValue();
86 std::optional<int64_t> dim) {
89 assert(!dim &&
"expected no dim for index-typed values");
94 Value value = cast<Value>(ofr);
97 assert(isa<ShapedType>(value.
getType()) &&
"expected shaped type");
104 mapOperands.emplace_back(value, dim);
109 assert(map.
getNumResults() == 1 &&
"expected single result");
114 for (int64_t i = 0, e = map.
getNumDims(); i < e; ++i)
119 dimReplacements, symReplacements, 0,
125 assert(var.map.getNumResults() == 1 &&
"expected single result");
126 assert(var.map.getNumDims() == 0 &&
"expected only symbols");
128 for (
auto valueDim : var.mapOperands) {
129 auto it = llvm::find(this->mapOperands, valueDim);
130 if (it != this->mapOperands.end()) {
133 std::distance(this->mapOperands.begin(), it)));
136 symReplacements.push_back(
138 this->mapOperands.push_back(valueDim);
142 var.map.getResult(0).replaceSymbols(symReplacements);
144 this->map = tmpMap.
replace(replacements, 0,
145 this->mapOperands.size());
164 assert(!dim.has_value() &&
"invalid dim value");
165 }
else if (
auto shapedType = dyn_cast<ShapedType>(value.
getType())) {
166 assert(*dim >= 0 &&
"invalid dim value");
167 if (shapedType.hasRank())
168 assert(*dim < shapedType.getRank() &&
"invalid dim value");
170 llvm_unreachable(
"unsupported type");
186 LLVM_DEBUG(llvm::dbgs() <<
"Failed to add bound: " << expr <<
"\n");
191 std::optional<int64_t> dim) {
200 std::optional<int64_t> constSize = std::nullopt;
201 auto shapedType = dyn_cast<ShapedType>(value.
getType());
203 if (shapedType.hasRank() && !shapedType.isDynamicDim(*dim))
204 constSize = shapedType.getDimSize(*dim);
206 constSize = *constInt;
225 (void)
insert(value, dim,
true,
false);
227 bound(value)[*dim] == *constSize;
229 bound(value) == *constSize;
240 if (
Value value = llvm::dyn_cast_if_present<Value>(ofr))
241 return getExpr(value, std::nullopt);
243 assert(constInt.has_value() &&
"expected Integer constant");
252 std::optional<int64_t> dim,
253 bool isSymbol,
bool addToWorklist) {
262 LLVM_DEBUG(llvm::dbgs() <<
"Inserting constraint set column " << pos
274 LLVM_DEBUG(llvm::dbgs() <<
"Push to worklist: " << value
275 <<
" (dim: " << dim.value_or(
kIndexValue) <<
")\n");
285 LLVM_DEBUG(llvm::dbgs() <<
"Inserting anonymous constraint set column " << pos
297 assert(map.
getNumResults() == 1 &&
"expected affine map with one result");
298 int64_t pos =
insert(isSymbol);
303 auto mapper = [&](std::pair<Value, std::optional<int64_t>> v) {
304 return getExpr(v.first, v.second);
318 return insert(var.map, var.mapOperands, isSymbol);
322 std::optional<int64_t> dim)
const {
325 assert((isa<OpResult>(value) ||
326 cast<BlockArgument>(value).getOwner()->isEntryBlock()) &&
327 "unstructured control flow is not supported");
329 LLVM_DEBUG(llvm::dbgs() <<
"Getting pos for: " << value
347 std::optional<int64_t> dim)
const {
354 LLVM_DEBUG(llvm::dbgs() <<
"Processing value bounds worklist...\n");
359 "did not expect std::nullopt on worklist");
361 Value value = valueDim.first;
362 int64_t dim = valueDim.second;
366 auto shapedType = cast<ShapedType>(value.
getType());
367 if (shapedType.hasRank() && !shapedType.isDynamicDim(dim)) {
368 bound(value)[dim] ==
getExpr(shapedType.getDimSize(dim));
374 auto maybeDim = dim ==
kIndexValue ? std::nullopt : std::make_optional(dim);
376 LLVM_DEBUG(llvm::dbgs() <<
"Stop condition met for: " << value
377 <<
" (dim: " << maybeDim <<
")\n");
385 LLVM_DEBUG(llvm::dbgs()
386 <<
"Query value bounds for: " << value
390 valueBoundsOp.populateBoundsForIndexValue(value, *
this);
392 valueBoundsOp.populateBoundsForShapedValueDim(value, dim, *
this);
396 LLVM_DEBUG(llvm::dbgs() <<
"--> ValueBoundsOpInterface not implemented\n");
401 auto dstOp = value.
getDefiningOp<DestinationStyleOpInterface>();
404 Value tiedOperand = dstOp.getTiedOpOperand(cast<OpResult>(value))->
get();
416 assert(erased &&
"inconsistent reverse mapping");
441 std::optional<int64_t> except) {
458 int64_t ubAdjustment = closedUB ? 0 : 1;
465 int64_t pos =
cstr.insert(var,
false);
466 assert(pos == 0 &&
"expected first column");
467 cstr.processWorklist();
473 p.second ==
kIndexValue ? std::nullopt : std::make_optional(p.second);
476 cstr.projectOutAnonymous(pos);
486 if ((type != BoundType::LB) &&
487 (ub.empty() || !ub[0] || ub[0].getNumResults() == 0))
490 if ((type != BoundType::UB) &&
491 (lb.empty() || !lb[0] || lb[0].getNumResults() == 0))
495 if (type != BoundType::LB)
496 assert(ub.size() == 1 && ub[0].getNumResults() == 1 &&
497 "multiple bounds not supported");
498 if (type != BoundType::UB)
499 assert(lb.size() == 1 && lb[0].getNumResults() == 1 &&
500 "multiple bounds not supported");
503 if (type == BoundType::EQ && ub[0] != lb[0])
507 if (type == BoundType::EQ || type == BoundType::LB) {
512 ub[0].getResult(0) + ubAdjustment);
517 "inconsistent mapping state");
519 int64_t numDims = 0, numSymbols = 0;
529 if (
bound.isFunctionOfDim(i))
552 assert(
cstr.positionToValueDim[i].has_value() &&
553 "cannot build affine map in terms of anonymous column");
555 Value value = valueDim.first;
556 int64_t dim = valueDim.second;
561 mapOperands.push_back(std::make_pair(value, std::nullopt));
565 assert(cast<ShapedType>(value.
getType()).isDynamicDim(dim) &&
566 "expected dynamic dim");
567 mapOperands.push_back(std::make_pair(value, dim));
570 resultMap =
bound.replaceDimsAndSymbols(replacementDims, replacementSymbols,
571 numDims, numSymbols);
579 resultMap, mapOperands, type, var,
581 return llvm::is_contained(dependencies, std::make_pair(v, d));
592 auto isIndependent = [&](
Value v) {
598 if (visited.contains(next))
600 visited.insert(next);
601 if (llvm::is_contained(independencies, next))
614 resultMap, mapOperands, type, var,
616 return isIndependent(v);
627 auto defaultStopCondition = [&](
Value v, std::optional<int64_t> dim,
634 pos =
cstr.populateConstraints(var.map, var.mapOperands);
635 assert(pos == 0 &&
"expected `map` is the first column");
638 int64_t ubAdjustment = closedUB ? 0 : 1;
640 return type == BoundType::UB ? *
bound + ubAdjustment : *
bound;
645 std::optional<int64_t> dim) {
660 int64_t pos =
insert(map, operands,
false);
669 std::optional<int64_t> dim1,
670 std::optional<int64_t> dim2) {
680 Variable(map, {{value1, dim1}, {value2, dim2}}));
698 <<
"cannot compare value/dims: constraint system is already empty");
704 return comparePos(lhsPos, ComparisonOperator::LE, rhsPos) &&
705 comparePos(lhsPos, ComparisonOperator::GE, rhsPos);
709 if (cmp ==
LT || cmp ==
LE) {
712 }
else if (cmp ==
GT || cmp ==
GE) {
716 llvm_unreachable(
"unsupported comparison operator");
718 if (cmp ==
LE || cmp ==
GE)
741 int64_t lhsPos = -1, rhsPos = -1;
745 if (
size_t(lhsPos) >=
cstr.positionToValueDim.size() ||
746 size_t(rhsPos) >=
cstr.positionToValueDim.size())
749 return cstr.comparePos(lhsPos, cmp, rhsPos);
752 lhsPos =
cstr.populateConstraints(lhs.map, lhs.mapOperands);
753 rhsPos =
cstr.populateConstraints(rhs.map, rhs.mapOperands);
754 return cstr.comparePos(lhsPos, cmp, rhsPos);
772 "expected slices of same rank");
774 "expected slices of same rank");
776 "expected slices of same rank");
779 bool foundUnknownBound =
false;
799 foundUnknownBound |=
failed(constBound);
800 if (
succeeded(constBound) && *constBound <= 0)
816 foundUnknownBound |=
failed(constBound);
817 if (
succeeded(constBound) && *constBound <= 0)
824 if (foundUnknownBound)
837 "expected slices of same rank");
839 "expected slices of same rank");
841 "expected slices of same rank");
847 for (
auto [offset1, offset2] :
855 for (
auto [size1, size2] :
863 for (
auto [stride1, stride2] :
875 llvm::errs() <<
"==========\nColumns:\n";
876 llvm::errs() <<
"(column\tdim\tvalue)\n";
878 llvm::errs() <<
" " << index <<
"\t";
881 llvm::errs() <<
"n/a\t";
883 llvm::errs() << valueDim->second <<
"\t";
886 if (
OpResult result = dyn_cast<OpResult>(valueDim->first)) {
887 llvm::errs() <<
"(result " << result.getResultNumber() <<
")";
889 llvm::errs() <<
"(bbarg "
890 << cast<BlockArgument>(valueDim->first).getArgNumber()
893 llvm::errs() <<
"\n";
895 llvm::errs() <<
"n/a\tn/a\n";
898 llvm::errs() <<
"\nConstraint set:\n";
900 llvm::errs() <<
"==========\n";
905 assert(!this->dim.has_value() &&
"dim was already set");
static Operation * getOwnerOfValue(Value value)
static void assertValidValueDim(Value value, std::optional< int64_t > dim)
Base type for affine expression.
AffineExpr replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements) const
This method substitutes any uses of dimensions and symbols (e.g.
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
MLIRContext * getContext() const
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
unsigned getNumSymbols() const
unsigned getNumDims() const
unsigned getNumResults() const
AffineMap replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements, unsigned numResultDims, unsigned numResultSyms) const
This method substitutes any uses of dimensions and symbols (e.g.
AffineExpr getResult(unsigned idx) const
AffineMap replace(AffineExpr expr, AffineExpr replacement, unsigned numResultDims, unsigned numResultSyms) const
Sparse replace method.
Attributes are known-constant values of operations.
This class is a general helper class for creating context-global objects like types,...
AffineExpr getAffineSymbolExpr(unsigned position)
AffineExpr getAffineConstantExpr(int64_t constant)
AffineExpr getAffineDimExpr(unsigned position)
This class provides support for representing a failure result, or a valid value of type T.
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool closedUB=false)
Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an...
A hyperrectangular slice, represented as a list of offsets, sizes and strides.
HyperrectangularSlice(ArrayRef< OpFoldResult > offsets, ArrayRef< OpFoldResult > sizes, ArrayRef< OpFoldResult > strides)
ArrayRef< OpFoldResult > getMixedOffsets() const
ArrayRef< OpFoldResult > getMixedSizes() const
ArrayRef< OpFoldResult > getMixedStrides() const
MLIRContext is the top-level object for a collection of MLIR operations.
This class represents a single result from folding an operation.
MLIRContext * getContext() const
This is a value defined by a result of an operation.
Operation is the basic unit of execution within MLIR.
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
OperationName getName()
The name of an operation is the key identifier for it.
operand_range getOperands()
Returns an iterator on the underlying Value's.
Helper class that builds a bound for a shaped value dimension or index-typed value.
void operator>(AffineExpr expr)
BoundBuilder & operator[](int64_t dim)
Specify a dimension, assuming that the underlying value is a shaped value.
void operator<=(AffineExpr expr)
void operator==(AffineExpr expr)
void operator<(AffineExpr expr)
void operator>=(AffineExpr expr)
A variable that can be added to the constraint set as a "column".
MLIRContext * getContext() const
Variable(OpFoldResult ofr)
Construct a variable for an index-typed attribute or SSA value.
A helper class to be used with ValueBoundsOpInterface.
static bool compare(const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
Return "true" if "lhs cmp rhs" was proven to hold.
static FailureOr< bool > areEqual(const Variable &var1, const Variable &var2)
Compute whether the given variables are equal.
DenseMap< ValueDim, int64_t > valueDimToPosition
Reverse mapping of values/shape dimensions to columns.
void processWorklist()
Iteratively process all elements on the worklist until an index-typed value or shaped value meets sto...
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.
SmallVector< std::optional< ValueDim > > positionToValueDim
Mapping of columns to values/shape dimensions.
static LogicalResult computeIndependentBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, ValueRange independencies, bool closedUB=false)
Compute a bound in that is independent of all values in independencies.
void projectOut(int64_t pos)
Project out the given column in the constraint set.
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.
void addBound(presburger::BoundType type, int64_t pos, AffineExpr expr)
Bound the given column in the underlying constraint set by the given expression.
StopConditionFn stopCondition
The current stop condition function.
ComparisonOperator
Comparison operator for ValueBoundsConstraintSet::compare.
BoundBuilder bound(Value value)
Add a bound for the given index-typed value or shaped value.
static LogicalResult computeBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, StopConditionFn stopCondition, bool closedUB=false)
Compute a bound for the given variable.
int64_t getPos(Value value, std::optional< int64_t > dim=std::nullopt) const
Return the column position of the given value/dimension.
int64_t insert(Value value, std::optional< int64_t > dim, bool isSymbol=true, bool addToWorklist=true)
Insert a value/dimension into the constraint set.
bool comparePos(int64_t lhsPos, ComparisonOperator cmp, int64_t rhsPos)
Return "true" if, based on the current state of the constraint system, "lhs cmp rhs" was proven to ho...
static FailureOr< int64_t > computeConstantBound(presburger::BoundType type, const Variable &var, StopConditionFn stopCondition=nullptr, bool closedUB=false)
Compute a constant bound for the given variable.
void dump() const
Debugging only: Dump the constraint set and the column-to-value/dim mapping to llvm::errs.
std::queue< int64_t > worklist
Worklist of values/shape dimensions that have not been processed yet.
FlatLinearConstraints cstr
Constraint system of equalities and inequalities.
bool isMapped(Value value, std::optional< int64_t > dim=std::nullopt) const
Return "true" if the given value/dim is mapped (i.e., has a corresponding column in the constraint sy...
AffineExpr getPosExpr(int64_t pos)
Return an affine expression that represents column pos in the constraint set.
void projectOutAnonymous(std::optional< int64_t > except=std::nullopt)
static FailureOr< bool > areEquivalentSlices(MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
Return "true" if the given slices are guaranteed to be equivalent.
ValueBoundsConstraintSet(MLIRContext *ctx, StopConditionFn stopCondition)
std::pair< Value, int64_t > ValueDim
An index-typed value or the dimension of a shaped-type value.
void populateConstraints(Value value, std::optional< int64_t > dim)
Traverse the IR starting from the given value/dim and populate constraints as long as the stop condit...
static FailureOr< bool > areOverlappingSlices(MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
Return "true" if the given slices are guaranteed to be overlapping.
std::function< bool(Value, std::optional< int64_t >, ValueBoundsConstraintSet &cstr)> StopConditionFn
The stop condition when traversing the backward slice of a shaped value/ index-type value.
Builder builder
Builder for constructing affine expressions.
bool populateAndCompare(const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
Populate constraints for lhs/rhs (until the stop condition is met).
static constexpr int64_t kIndexValue
Dimension identifier to indicate a value is index-typed.
static LogicalResult computeDependentBound(AffineMap &resultMap, ValueDimList &mapOperands, presburger::BoundType type, const Variable &var, ValueDimList dependencies, bool closedUB=false)
Compute a bound in terms of the values/dimensions in dependencies.
This class provides an abstraction over the different types of ranges over Values.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
MLIRContext * getContext() const
Utility to get the associated MLIRContext that this value is defined in.
Type getType() const
Return the type of this value.
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
void addInequality(ArrayRef< MPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
unsigned getNumSymbolVars() const
std::optional< int64_t > getConstantBound64(BoundType type, unsigned pos) const
The same, but casts to int64_t.
unsigned appendVar(VarKind kind, unsigned num=1)
Append num variables of the specified kind after the last variable of that kind.
unsigned getNumDimAndSymbolVars() const
bool isEmpty() const
Checks for emptiness by performing variable elimination on all variables, running the GCD test on eac...
unsigned getNumCols() const
Returns the number of columns in the constraint system.
void removeInequality(unsigned pos)
void projectOut(unsigned pos, unsigned num)
Projects out (aka eliminates) num variables starting at position pos.
unsigned getNumInequalities() const
unsigned getNumDimVars() const
Include the generated interface declarations.
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
SmallVector< OpFoldResult > getMixedSizes(OpBuilder &builder, Location loc, Value value)
Return the dimensions of the given memref value.
BoundType
The type of bound: equal, lower bound or upper bound.
bool operator>(const Fraction &x, const Fraction &y)
bool operator<(const Fraction &x, const Fraction &y)
bool operator>=(const Fraction &x, const Fraction &y)
bool operator<=(const Fraction &x, const Fraction &y)
Include the generated interface declarations.
bool matchPattern(Value value, const Pattern &pattern)
Entry point for matching a pattern over a Value.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
detail::constant_int_value_binder m_ConstantInt(IntegerAttr::ValueType *bind_value)
Matches a constant holding a scalar/vector/tensor integer (splat) and writes the integer value to bin...
std::optional< int64_t > getConstantIntValue(OpFoldResult ofr)
If ofr is a constant integer or an IntegerAttr, return the integer.
bool operator==(StringAttr lhs, std::nullptr_t)
Define comparisons for StringAttr against nullptr and itself to avoid the StringRef overloads from be...
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value.
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
SmallVector< std::pair< Value, std::optional< int64_t > >> ValueDimList
auto get(MLIRContext *context, Ts &&...params)
Helper method that injects context only if needed, this helps unify some of the attribute constructio...
AffineMap foldAttributesIntoMap(Builder &b, AffineMap map, ArrayRef< OpFoldResult > operands, SmallVector< Value > &remainingValues)
Fold all attributes among the given operands into the affine map.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
This class represents an efficient way to signal success or failure.