| 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 | |
| 15 | using namespace mlir; |
| 16 | using namespace mlir::affine; |
| 17 | |
| 18 | namespace mlir { |
| 19 | namespace { |
| 20 | |
| 21 | struct 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`. |
| 56 | static 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 | |
| 68 | struct 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 | |
| 111 | struct 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 | |
| 132 | struct 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 | |
| 153 | struct 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 | |
| 182 | struct 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 | |
| 214 | void mlir::affine::registerValueBoundsOpInterfaceExternalModels( |
| 215 | DialectRegistry ®istry) { |
| 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 | |
| 228 | FailureOr<int64_t> |
| 229 | mlir::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 | |