1//===- ValueBoundsOpInterfaceImpl.cpp - Impl. of ValueBoundsOpInterface ---===//
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
9#include "mlir/Dialect/Affine/IR/ValueBoundsOpInterfaceImpl.h"
10
11#include "mlir/Dialect/Affine/IR/AffineOps.h"
12#include "mlir/Interfaces/ValueBoundsOpInterface.h"
13#include "llvm/ADT/SmallVectorExtras.h"
14
15using namespace mlir;
16using namespace mlir::affine;
17
18namespace mlir {
19namespace {
20
21struct AffineApplyOpInterface
22 : public ValueBoundsOpInterface::ExternalModel<AffineApplyOpInterface,
23 AffineApplyOp> {
24 void populateBoundsForIndexValue(Operation *op, Value value,
25 ValueBoundsConstraintSet &cstr) const {
26 auto applyOp = cast<AffineApplyOp>(Val: op);
27 assert(value == applyOp.getResult() && "invalid value");
28 assert(applyOp.getAffineMap().getNumResults() == 1 &&
29 "expected single result");
30
31 // Fully compose this affine.apply with other ops because the folding logic
32 // can see opportunities for simplifying the affine map that
33 // `FlatLinearConstraints` can currently not see.
34 AffineMap map = applyOp.getAffineMap();
35 SmallVector<Value> operands = llvm::to_vector(Range: applyOp.getOperands());
36 fullyComposeAffineMapAndOperands(map: &map, operands: &operands);
37
38 // Align affine map result with dims/symbols in the constraint set.
39 AffineExpr expr = map.getResult(idx: 0);
40 SmallVector<AffineExpr> dimReplacements, symReplacements;
41 for (int64_t i = 0, e = map.getNumDims(); i < e; ++i)
42 dimReplacements.push_back(Elt: cstr.getExpr(value: operands[i]));
43 for (int64_t i = map.getNumDims(),
44 e = map.getNumDims() + map.getNumSymbols();
45 i < e; ++i)
46 symReplacements.push_back(Elt: cstr.getExpr(value: operands[i]));
47 AffineExpr bound =
48 expr.replaceDimsAndSymbols(dimReplacements, symReplacements);
49 cstr.bound(value) == bound;
50 }
51};
52
53/// Express `expr`, a result of `map`, in terms of the constraint set by
54/// replacing the dims and symbols of `map` with the expressions for the
55/// corresponding `operands`.
56static AffineExpr alignBoundExpr(AffineExpr expr, AffineMap map,
57 ValueRange operands,
58 ValueBoundsConstraintSet &cstr) {
59 SmallVector<AffineExpr> dimReplacements =
60 llvm::map_to_vector(C: operands.take_front(n: map.getNumDims()),
61 F: [&](Value v) { return cstr.getExpr(value: v); });
62 SmallVector<AffineExpr> symReplacements =
63 llvm::map_to_vector(C: operands.drop_front(n: map.getNumDims()),
64 F: [&](Value v) { return cstr.getExpr(value: v); });
65 return expr.replaceDimsAndSymbols(dimReplacements, symReplacements);
66}
67
68struct AffineForOpInterface
69 : public ValueBoundsOpInterface::ExternalModel<AffineForOpInterface,
70 AffineForOp> {
71 void populateBoundsForIndexValue(Operation *op, Value value,
72 ValueBoundsConstraintSet &cstr) const {
73 auto forOp = cast<AffineForOp>(Val: op);
74
75 // Only the induction variable is handled. Bounds for iter_args are not
76 // inferred.
77 if (value != forOp.getInductionVar())
78 return;
79
80 AffineMap lbMap = forOp.getLowerBoundMap();
81 AffineMap ubMap = forOp.getUpperBoundMap();
82 ValueRange lbOperands = forOp.getLowerBoundOperands();
83 ValueRange ubOperands = forOp.getUpperBoundOperands();
84
85 // The lower bound is the maximum over the results of `lbMap` and the upper
86 // bound is the minimum over the results of `ubMap`, so the induction
87 // variable is bounded by every individual result.
88 for (AffineExpr expr : lbMap.getResults())
89 cstr.bound(value) >= alignBoundExpr(expr, map: lbMap, operands: lbOperands, cstr);
90 for (AffineExpr expr : ubMap.getResults())
91 cstr.bound(value) < alignBoundExpr(expr, map: ubMap, operands: ubOperands, cstr);
92
93 // With a single lower and a single upper bound the step can be taken into
94 // account as well: the induction variable is always a multiple of `step`
95 // away from the lower bound, so it never exceeds
96 // `lb + (tripCount - 1) * step`. That is tighter than `ub - 1` whenever the
97 // trip count is not a multiple of the step, e.g. `affine.for %i = 0 to 300
98 // step 128` only ever yields {0, 128, 256}. This does not replace the
99 // `iv < ub` bound above, since multiplying two constraint set dimensions is
100 // not supported.
101 int64_t step = forOp.getStepAsInt();
102 if (step == 1 || lbMap.getNumResults() != 1 || ubMap.getNumResults() != 1)
103 return;
104 AffineExpr lb = alignBoundExpr(expr: lbMap.getResult(idx: 0), map: lbMap, operands: lbOperands, cstr);
105 AffineExpr ub = alignBoundExpr(expr: ubMap.getResult(idx: 0), map: ubMap, operands: ubOperands, cstr);
106 AffineExpr tripCount = (ub - lb).ceilDiv(v: step);
107 cstr.bound(value) <= lb + (tripCount - 1) * step;
108 }
109};
110
111struct AffineMinOpInterface
112 : public ValueBoundsOpInterface::ExternalModel<AffineMinOpInterface,
113 AffineMinOp> {
114 void populateBoundsForIndexValue(Operation *op, Value value,
115 ValueBoundsConstraintSet &cstr) const {
116 auto minOp = cast<AffineMinOp>(Val: op);
117 assert(value == minOp.getResult() && "invalid value");
118
119 // Align affine map results with dims/symbols in the constraint set.
120 for (AffineExpr expr : minOp.getAffineMap().getResults()) {
121 SmallVector<AffineExpr> dimReplacements = llvm::map_to_vector(
122 C: minOp.getDimOperands(), F: [&](Value v) { return cstr.getExpr(value: v); });
123 SmallVector<AffineExpr> symReplacements = llvm::map_to_vector(
124 C: minOp.getSymbolOperands(), F: [&](Value v) { return cstr.getExpr(value: v); });
125 AffineExpr bound =
126 expr.replaceDimsAndSymbols(dimReplacements, symReplacements);
127 cstr.bound(value) <= bound;
128 }
129 };
130};
131
132struct AffineMaxOpInterface
133 : public ValueBoundsOpInterface::ExternalModel<AffineMaxOpInterface,
134 AffineMaxOp> {
135 void populateBoundsForIndexValue(Operation *op, Value value,
136 ValueBoundsConstraintSet &cstr) const {
137 auto maxOp = cast<AffineMaxOp>(Val: op);
138 assert(value == maxOp.getResult() && "invalid value");
139
140 // Align affine map results with dims/symbols in the constraint set.
141 for (AffineExpr expr : maxOp.getAffineMap().getResults()) {
142 SmallVector<AffineExpr> dimReplacements = llvm::map_to_vector(
143 C: maxOp.getDimOperands(), F: [&](Value v) { return cstr.getExpr(value: v); });
144 SmallVector<AffineExpr> symReplacements = llvm::map_to_vector(
145 C: maxOp.getSymbolOperands(), F: [&](Value v) { return cstr.getExpr(value: v); });
146 AffineExpr bound =
147 expr.replaceDimsAndSymbols(dimReplacements, symReplacements);
148 cstr.bound(value) >= bound;
149 }
150 };
151};
152
153struct AffineDelinearizeIndexOpInterface
154 : public ValueBoundsOpInterface::ExternalModel<
155 AffineDelinearizeIndexOpInterface, AffineDelinearizeIndexOp> {
156 void populateBoundsForIndexValue(Operation *rawOp, Value value,
157 ValueBoundsConstraintSet &cstr) const {
158 auto op = cast<AffineDelinearizeIndexOp>(Val: rawOp);
159 auto result = cast<OpResult>(Val&: value);
160 assert(result.getOwner() == rawOp &&
161 "bounded value isn't a result of this delinearize_index");
162 unsigned resIdx = result.getResultNumber();
163
164 AffineExpr linearIdx = cstr.getExpr(value: op.getLinearIndex());
165
166 SmallVector<OpFoldResult> basis = op.getPaddedBasis();
167 AffineExpr divisor = cstr.getExpr(constant: 1);
168 for (OpFoldResult basisElem : llvm::drop_begin(RangeOrContainer&: basis, N: resIdx + 1))
169 divisor = divisor * cstr.getExpr(ofr: basisElem);
170
171 if (resIdx == 0) {
172 cstr.bound(value) == linearIdx.floorDiv(other: divisor);
173 if (!basis.front().isNull())
174 cstr.bound(value) < cstr.getExpr(ofr: basis.front());
175 return;
176 }
177 AffineExpr thisBasis = cstr.getExpr(ofr: basis[resIdx]);
178 cstr.bound(value) == (linearIdx % (thisBasis * divisor)).floorDiv(other: divisor);
179 }
180};
181
182struct AffineLinearizeIndexOpInterface
183 : public ValueBoundsOpInterface::ExternalModel<
184 AffineLinearizeIndexOpInterface, AffineLinearizeIndexOp> {
185 void populateBoundsForIndexValue(Operation *rawOp, Value value,
186 ValueBoundsConstraintSet &cstr) const {
187 auto op = cast<AffineLinearizeIndexOp>(Val: rawOp);
188 assert(value == op.getResult() &&
189 "value isn't the result of this linearize");
190
191 AffineExpr bound = cstr.getExpr(constant: 0);
192 AffineExpr stride = cstr.getExpr(constant: 1);
193 SmallVector<OpFoldResult> basis = op.getPaddedBasis();
194 OperandRange multiIndex = op.getMultiIndex();
195 unsigned numArgs = multiIndex.size();
196 for (auto [revArgNum, length] : llvm::enumerate(First: llvm::reverse(C&: basis))) {
197 unsigned argNum = numArgs - (revArgNum + 1);
198 if (argNum == 0)
199 break;
200 OpFoldResult indexAsFoldRes = getAsOpFoldResult(val: multiIndex[argNum]);
201 bound = bound + cstr.getExpr(ofr: indexAsFoldRes) * stride;
202 stride = stride * cstr.getExpr(ofr: length);
203 }
204 bound = bound + cstr.getExpr(value: op.getMultiIndex().front()) * stride;
205 cstr.bound(value) == bound;
206 if (op.getDisjoint() && !basis.front().isNull()) {
207 cstr.bound(value) < stride *cstr.getExpr(ofr: basis.front());
208 }
209 }
210};
211} // namespace
212} // namespace mlir
213
214void mlir::affine::registerValueBoundsOpInterfaceExternalModels(
215 DialectRegistry &registry) {
216 registry.addExtension(extensionFn: +[](MLIRContext *ctx, AffineDialect *dialect) {
217 AffineApplyOp::attachInterface<AffineApplyOpInterface>(context&: *ctx);
218 AffineForOp::attachInterface<AffineForOpInterface>(context&: *ctx);
219 AffineMaxOp::attachInterface<AffineMaxOpInterface>(context&: *ctx);
220 AffineMinOp::attachInterface<AffineMinOpInterface>(context&: *ctx);
221 AffineDelinearizeIndexOp::attachInterface<
222 AffineDelinearizeIndexOpInterface>(context&: *ctx);
223 AffineLinearizeIndexOp::attachInterface<AffineLinearizeIndexOpInterface>(
224 context&: *ctx);
225 });
226}
227
228FailureOr<int64_t>
229mlir::affine::fullyComposeAndComputeConstantDelta(Value value1, Value value2) {
230 assert(value1.getType().isIndex() && "expected index type");
231 assert(value2.getType().isIndex() && "expected index type");
232
233 // Subtract the two values/dimensions from each other. If the result is 0,
234 // both are equal.
235 Builder b(value1.getContext());
236 AffineMap map = AffineMap::get(/*dimCount=*/2, /*symbolCount=*/0,
237 result: b.getAffineDimExpr(position: 0) - b.getAffineDimExpr(position: 1));
238 // Fully compose the affine map with other ops because the folding logic
239 // can see opportunities for simplifying the affine map that
240 // `FlatLinearConstraints` can currently not see.
241 SmallVector<Value> mapOperands;
242 mapOperands.push_back(Elt: value1);
243 mapOperands.push_back(Elt: value2);
244 affine::fullyComposeAffineMapAndOperands(map: &map, operands: &mapOperands);
245 return ValueBoundsConstraintSet::computeConstantBound(
246 type: presburger::BoundType::EQ,
247 var: ValueBoundsConstraintSet::Variable(map, mapOperands));
248}
249