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"
31 : mixedOffsets(offsets), mixedSizes(sizes), mixedStrides(strides) {
32 assert(offsets.size() == sizes.size() &&
33 "expected same number of offsets, sizes, strides");
34 assert(offsets.size() == strides.size() &&
35 "expected same number of offsets, sizes, strides");
40 : mixedOffsets(offsets), mixedSizes(sizes) {
41 assert(offsets.size() == sizes.size() &&
42 "expected same number of offsets and sizes");
47 mixedStrides.append(offsets.size(),
Builder(ctx).getIndexAttr(1));
52 op.getMixedStrides()) {}
57 if (
auto val = llvm::dyn_cast_if_present<Value>(ofr)) {
60 return intVal.getSExtValue();
64 Attribute attr = llvm::dyn_cast_if_present<Attribute>(ofr);
65 if (
auto intAttr = dyn_cast_or_null<IntegerAttr>(attr))
66 return intAttr.getValue().getSExtValue();
76 assert(!dim.has_value() &&
"invalid dim value");
77 }
else if (
auto shapedType = dyn_cast<ShapedType>(value.
getType())) {
78 assert(*dim >= 0 &&
"invalid dim value");
79 if (shapedType.hasRank())
80 assert(*dim < shapedType.getRank() &&
"invalid dim value");
82 llvm_unreachable(
"unsupported type");
98 LLVM_DEBUG(llvm::dbgs() <<
"Failed to add bound: " << expr <<
"\n");
103 std::optional<int64_t> dim) {
108 auto shapedType = dyn_cast<ShapedType>(value.
getType());
111 if (shapedType.hasRank() && !shapedType.isDynamicDim(*dim))
123 int64_t pos =
getPos(value, dim);
130 if (
Value value = llvm::dyn_cast_if_present<Value>(ofr))
131 return getExpr(value, std::nullopt);
133 assert(constInt.has_value() &&
"expected Integer constant");
142 std::optional<int64_t> dim,
174 std::optional<int64_t> dim)
const {
177 assert((isa<OpResult>(value) ||
178 cast<BlockArgument>(value).getOwner()->isEntryBlock()) &&
179 "unstructured control flow is not supported");
189 if (
auto bbArg = dyn_cast<BlockArgument>(value))
199 "did not expect std::nullopt on worklist");
201 Value value = valueDim.first;
202 int64_t dim = valueDim.second;
206 auto shapedType = cast<ShapedType>(value.
getType());
207 if (shapedType.hasRank() && !shapedType.isDynamicDim(dim)) {
208 bound(value)[dim] ==
getExpr(shapedType.getDimSize(dim));
214 auto maybeDim = dim ==
kIndexValue ? std::nullopt : std::make_optional(dim);
215 if (stopCondition(value, maybeDim))
224 valueBoundsOp.populateBoundsForIndexValue(value, *
this);
226 valueBoundsOp.populateBoundsForShapedValueDim(value, dim, *
this);
234 auto dstOp = value.
getDefiningOp<DestinationStyleOpInterface>();
237 Value tiedOperand = dstOp.getTiedOpOperand(cast<OpResult>(value))->
get();
249 assert(erased &&
"inconsistent reverse mapping");
279 assert(!stopCondition(value, dim) &&
280 "stop condition should not be satisfied for starting point");
283 int64_t ubAdjustment = closedUB ? 0 : 1;
287 if (stopCondition(value, dim)) {
290 mapOperands.push_back(std::make_pair(value, dim));
292 if (type == BoundType::UB)
303 int64_t pos =
cstr.insert(value, dim,
false);
304 cstr.processWorklist(stopCondition);
313 p.second ==
kIndexValue ? std::nullopt : std::make_optional(p.second);
314 return !stopCondition(p.first, maybeDim);
325 if ((type != BoundType::LB) &&
326 (ub.empty() || !ub[0] || ub[0].getNumResults() == 0))
329 if ((type != BoundType::UB) &&
330 (lb.empty() || !lb[0] || lb[0].getNumResults() == 0))
334 if (type != BoundType::LB)
335 assert(ub.size() == 1 && ub[0].getNumResults() == 1 &&
336 "multiple bounds not supported");
337 if (type != BoundType::UB)
338 assert(lb.size() == 1 && lb[0].getNumResults() == 1 &&
339 "multiple bounds not supported");
342 if (type == BoundType::EQ && ub[0] != lb[0])
346 if (type == BoundType::EQ || type == BoundType::LB) {
351 ub[0].getResult(0) + ubAdjustment);
356 "inconsistent mapping state");
358 int64_t numDims = 0, numSymbols = 0;
368 if (
bound.isFunctionOfDim(i))
391 assert(
cstr.positionToValueDim[i].has_value() &&
392 "cannot build affine map in terms of anonymous column");
394 Value value = valueDim.first;
395 int64_t dim = valueDim.second;
400 mapOperands.push_back(std::make_pair(value, std::nullopt));
404 assert(cast<ShapedType>(value.
getType()).isDynamicDim(dim) &&
405 "expected dynamic dim");
406 mapOperands.push_back(std::make_pair(value, dim));
409 resultMap =
bound.replaceDimsAndSymbols(replacementDims, replacementSymbols,
410 numDims, numSymbols);
419 resultMap, mapOperands, type, value, dim,
420 [&](
Value v, std::optional<int64_t> d) {
421 return llvm::is_contained(dependencies, std::make_pair(v, d));
433 auto isIndependent = [&](
Value v) {
439 if (visited.contains(next))
441 visited.insert(next);
442 if (llvm::is_contained(independencies, next))
455 resultMap, mapOperands, type, value, dim,
456 [&](
Value v, std::optional<int64_t> d) {
return isIndependent(v); },
477 assert(map.
getNumResults() == 1 &&
"expected affine map with one result");
479 int64_t pos =
cstr.insert(
false);
483 auto mapper = [&](std::pair<Value, std::optional<int64_t>> v) {
484 return cstr.getExpr(v.first, v.second);
497 cstr.processWorklist(stopCondition);
501 cstr.processWorklist(
502 [&](
Value v, std::optional<int64_t> dim) {
508 int64_t ubAdjustment = closedUB ? 0 : 1;
510 return type == BoundType::UB ? *
bound + ubAdjustment : *
bound;
518 for (
Value v : operands) {
519 assert(v.getType().isIndex() &&
"expected index type");
520 valueDims.emplace_back(v, std::nullopt);
527 std::optional<int64_t> dim1,
528 std::optional<int64_t> dim2) {
538 {{value1, dim1}, {value2, dim2}});
543 std::optional<int64_t> dim1,
544 std::optional<int64_t> dim2) {
560 ofrOperands.push_back(ofr1);
561 ofrOperands.push_back(ofr2);
566 for (
Value v : valueOperands) {
567 assert(v.getType().isIndex() &&
"expected index type");
568 valueDims.emplace_back(v, std::nullopt);
582 "expected slices of same rank");
584 "expected slices of same rank");
586 "expected slices of same rank");
589 bool foundUnknownBound =
false;
609 foundUnknownBound |=
failed(constBound);
610 if (
succeeded(constBound) && *constBound <= 0)
626 foundUnknownBound |=
failed(constBound);
627 if (
succeeded(constBound) && *constBound <= 0)
634 if (foundUnknownBound)
647 "expected slices of same rank");
649 "expected slices of same rank");
651 "expected slices of same rank");
657 for (
auto [offset1, offset2] :
665 for (
auto [size1, size2] :
673 for (
auto [stride1, stride2] :
686 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 getNumDims() const
unsigned getNumResults() const
AffineExpr getResult(unsigned idx) const
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
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...
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 helper class to be used with ValueBoundsOpInterface.
DenseMap< ValueDim, int64_t > valueDimToPosition
Reverse mapping of values/shape dimensions to columns.
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.
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 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.
int64_t insert(Value value, std::optional< int64_t > dim, bool isSymbol=true)
Insert a value/dimension into the constraint set.
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.
BoundBuilder bound(Value value)
Add a bound for the given index-typed value or shaped value.
int64_t getPos(Value value, std::optional< int64_t > dim=std::nullopt) const
Return the column position of the given value/dimension.
std::queue< int64_t > worklist
Worklist of values/shape dimensions that have not been processed yet.
ValueBoundsConstraintSet(MLIRContext *ctx)
FlatLinearConstraints cstr
Constraint system of equalities and inequalities.
void processWorklist(StopConditionFn stopCondition)
Iteratively process all elements on the worklist until an index-typed value or shaped value meets sto...
static FailureOr< bool > areEquivalentSlices(MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
Return "true" if the given slices are guaranteed to be equivalent.
std::pair< Value, int64_t > ValueDim
An index-typed value or the dimension of a shaped-type value.
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.
static FailureOr< bool > areOverlappingSlices(MLIRContext *ctx, HyperrectangularSlice slice1, HyperrectangularSlice slice2)
Return "true" if the given slices are guaranteed to be overlapping.
Builder builder
Builder for constructing affine expressions.
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.
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 oper...
static constexpr int64_t kIndexValue
Dimension identifier to indicate a value is index-typed.
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.
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
void projectOut(unsigned pos, unsigned num)
Projects out (aka eliminates) num variables starting at position pos.
unsigned getNumDimVars() const
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.
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.