MLIR  19.0.0git
ReifyValueBounds.cpp
Go to the documentation of this file.
1 //===- ReifyValueBounds.cpp --- Reify value bounds with arith ops -------*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
10 
15 
16 using namespace mlir;
17 using namespace mlir::arith;
18 
19 /// Build Arith IR for the given affine map and its operands.
21  ValueRange operands) {
22  assert(map.getNumResults() == 1 && "multiple results not supported yet");
23  std::function<Value(AffineExpr)> buildExpr = [&](AffineExpr e) -> Value {
24  switch (e.getKind()) {
26  return b.create<ConstantIndexOp>(loc,
27  cast<AffineConstantExpr>(e).getValue());
29  return operands[cast<AffineDimExpr>(e).getPosition()];
31  return operands[cast<AffineSymbolExpr>(e).getPosition() +
32  map.getNumDims()];
33  case AffineExprKind::Add: {
34  auto binaryExpr = cast<AffineBinaryOpExpr>(e);
35  return b.create<AddIOp>(loc, buildExpr(binaryExpr.getLHS()),
36  buildExpr(binaryExpr.getRHS()));
37  }
38  case AffineExprKind::Mul: {
39  auto binaryExpr = cast<AffineBinaryOpExpr>(e);
40  return b.create<MulIOp>(loc, buildExpr(binaryExpr.getLHS()),
41  buildExpr(binaryExpr.getRHS()));
42  }
44  auto binaryExpr = cast<AffineBinaryOpExpr>(e);
45  return b.create<DivSIOp>(loc, buildExpr(binaryExpr.getLHS()),
46  buildExpr(binaryExpr.getRHS()));
47  }
49  auto binaryExpr = cast<AffineBinaryOpExpr>(e);
50  return b.create<CeilDivSIOp>(loc, buildExpr(binaryExpr.getLHS()),
51  buildExpr(binaryExpr.getRHS()));
52  }
53  case AffineExprKind::Mod: {
54  auto binaryExpr = cast<AffineBinaryOpExpr>(e);
55  return b.create<RemSIOp>(loc, buildExpr(binaryExpr.getLHS()),
56  buildExpr(binaryExpr.getRHS()));
57  }
58  }
59  llvm_unreachable("unsupported AffineExpr kind");
60  };
61  return buildExpr(map.getResult(0));
62 }
63 
67  ValueBoundsConstraintSet::StopConditionFn stopCondition, bool closedUB) {
68  // Compute bound.
69  AffineMap boundMap;
70  ValueDimList mapOperands;
72  boundMap, mapOperands, type, var, stopCondition, closedUB)))
73  return failure();
74 
75  // Materialize tensor.dim/memref.dim ops.
76  SmallVector<Value> operands;
77  for (auto valueDim : mapOperands) {
78  Value value = valueDim.first;
79  std::optional<int64_t> dim = valueDim.second;
80 
81  if (!dim.has_value()) {
82  // This is an index-typed value.
83  assert(value.getType().isIndex() && "expected index type");
84  operands.push_back(value);
85  continue;
86  }
87 
88  assert(cast<ShapedType>(value.getType()).isDynamicDim(*dim) &&
89  "expected dynamic dim");
90  if (isa<RankedTensorType>(value.getType())) {
91  // A tensor dimension is used: generate a tensor.dim.
92  operands.push_back(b.create<tensor::DimOp>(loc, value, *dim));
93  } else if (isa<MemRefType>(value.getType())) {
94  // A memref dimension is used: generate a memref.dim.
95  operands.push_back(b.create<memref::DimOp>(loc, value, *dim));
96  } else {
97  llvm_unreachable("cannot generate DimOp for unsupported shaped type");
98  }
99  }
100 
101  // Check for special cases where no arith ops are needed.
102  if (boundMap.isSingleConstant()) {
103  // Bound is a constant: return an IntegerAttr.
104  return static_cast<OpFoldResult>(
105  b.getIndexAttr(boundMap.getSingleConstantResult()));
106  }
107  // No arith ops are needed if the bound is a single SSA value.
108  if (auto expr = dyn_cast<AffineDimExpr>(boundMap.getResult(0)))
109  return static_cast<OpFoldResult>(operands[expr.getPosition()]);
110  if (auto expr = dyn_cast<AffineSymbolExpr>(boundMap.getResult(0)))
111  return static_cast<OpFoldResult>(
112  operands[expr.getPosition() + boundMap.getNumDims()]);
113  // General case: build Arith ops.
114  return static_cast<OpFoldResult>(buildArithValue(b, loc, boundMap, operands));
115 }
116 
118  OpBuilder &b, Location loc, presburger::BoundType type, Value value,
119  int64_t dim, ValueBoundsConstraintSet::StopConditionFn stopCondition,
120  bool closedUB) {
121  auto reifyToOperands = [&](Value v, std::optional<int64_t> d,
122  ValueBoundsConstraintSet &cstr) {
123  // We are trying to reify a bound for `value` in terms of the owning op's
124  // operands. Construct a stop condition that evaluates to "true" for any SSA
125  // value expect for `value`. I.e., the bound will be computed in terms of
126  // any SSA values expect for `value`. The first such values are operands of
127  // the owner of `value`.
128  return v != value;
129  };
130  return reifyValueBound(b, loc, type, {value, dim},
131  stopCondition ? stopCondition : reifyToOperands,
132  closedUB);
133 }
134 
136  OpBuilder &b, Location loc, presburger::BoundType type, Value value,
137  ValueBoundsConstraintSet::StopConditionFn stopCondition, bool closedUB) {
138  auto reifyToOperands = [&](Value v, std::optional<int64_t> d,
139  ValueBoundsConstraintSet &cstr) {
140  return v != value;
141  };
142  return reifyValueBound(b, loc, type, value,
143  stopCondition ? stopCondition : reifyToOperands,
144  closedUB);
145 }
static Value buildArithValue(OpBuilder &b, Location loc, AffineMap map, ValueRange operands)
Build Arith IR for the given affine map and its operands.
Base type for affine expression.
Definition: AffineExpr.h:69
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:47
int64_t getSingleConstantResult() const
Returns the constant result of this map.
Definition: AffineMap.cpp:365
bool isSingleConstant() const
Returns true if this affine map is a single result constant function.
Definition: AffineMap.cpp:357
unsigned getNumDims() const
Definition: AffineMap.cpp:378
unsigned getNumResults() const
Definition: AffineMap.cpp:386
AffineExpr getResult(unsigned idx) const
Definition: AffineMap.cpp:395
IntegerAttr getIndexAttr(int64_t value)
Definition: Builders.cpp:124
This class provides support for representing a failure result, or a valid value of type T.
Definition: LogicalResult.h:78
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:63
This class helps build Operations.
Definition: Builders.h:209
Operation * create(const OperationState &state)
Creates an operation given the fields represented as an OperationState.
Definition: Builders.cpp:464
This class represents a single result from folding an operation.
Definition: OpDefinition.h:268
bool isIndex() const
Definition: Types.cpp:56
A variable that can be added to the constraint set as a "column".
A helper class to be used with ValueBoundsOpInterface.
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.
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.
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:381
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
Type getType() const
Return the type of this value.
Definition: Value.h:129
Specialization of arith.constant op that returns an integer of index type.
Definition: Arith.h:92
FailureOr< OpFoldResult > reifyValueBound(OpBuilder &b, Location loc, presburger::BoundType type, const ValueBoundsConstraintSet::Variable &var, ValueBoundsConstraintSet::StopConditionFn stopCondition, bool closedUB=false)
Reify a bound for the given variable in terms of SSA values for which stopCondition is met.
FailureOr< OpFoldResult > reifyIndexValueBound(OpBuilder &b, Location loc, presburger::BoundType type, Value value, ValueBoundsConstraintSet::StopConditionFn stopCondition=nullptr, bool closedUB=false)
Reify a bound for the given index-typed value in terms of SSA values for which stopCondition is met.
FailureOr< OpFoldResult > reifyShapedValueDimBound(OpBuilder &b, Location loc, presburger::BoundType type, Value value, int64_t dim, ValueBoundsConstraintSet::StopConditionFn stopCondition=nullptr, bool closedUB=false)
Reify a bound for the specified dimension of the given shaped value in terms of SSA values for which ...
BoundType
The type of bound: equal, lower bound or upper bound.
Include the generated interface declarations.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
@ CeilDiv
RHS of ceildiv is always a constant or a symbolic expression.
@ Mul
RHS of mul is always a constant or a symbolic expression.
@ Mod
RHS of mod is always a constant or a symbolic expression with a positive value.
@ DimId
Dimensional identifier.
@ FloorDiv
RHS of floordiv is always a constant or a symbolic expression.
@ Constant
Constant integer.
@ SymbolId
Symbolic identifier.
SmallVector< std::pair< Value, std::optional< int64_t > >> ValueDimList
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:72