| 1 | //===- SimplifyAffineWithBounds.cpp ---------------------------------------===// |
| 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 | // This file implements simplification patterns for affine.delinearize_index / |
| 10 | // affine.linearize_index pairs using value bounds analysis. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "mlir/Dialect/Affine/Transforms/Passes.h" |
| 15 | |
| 16 | #include "mlir/Dialect/Affine/IR/AffineOps.h" |
| 17 | #include "mlir/Dialect/Affine/Transforms/Transforms.h" |
| 18 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 19 | #include "mlir/Dialect/Utils/StaticValueUtils.h" |
| 20 | #include "mlir/IR/PatternMatch.h" |
| 21 | #include "mlir/Interfaces/ValueBoundsOpInterface.h" |
| 22 | #include "mlir/Transforms/GreedyPatternRewriteDriver.h" |
| 23 | |
| 24 | #define DEBUG_TYPE "affine-simplify-with-bounds" |
| 25 | |
| 26 | using namespace mlir; |
| 27 | using namespace mlir::affine; |
| 28 | |
| 29 | /// Accumulate a single basis element into the running product expression. |
| 30 | /// Static values become affine constants, and dynamic values become symbols. |
| 31 | static void buildProductExpr(OpFoldResult basis, AffineExpr &productExpr, |
| 32 | SmallVectorImpl<Value> &operands, |
| 33 | MLIRContext *ctx) { |
| 34 | if (auto val = getConstantIntValue(ofr: basis)) { |
| 35 | productExpr = productExpr * getAffineConstantExpr(constant: *val, context: ctx); |
| 36 | } else { |
| 37 | operands.push_back(Elt: cast<Value>(Val&: basis)); |
| 38 | productExpr = productExpr * getAffineSymbolExpr(position: operands.size() - 1, context: ctx); |
| 39 | } |
| 40 | } |
| 41 | |
| 42 | /// Try to find k consecutive elements from `lhs` (starting from tail offset) |
| 43 | /// whose product equals the single next element from `rhs`. |
| 44 | /// The product is accumulated incrementally to avoid redundant computation. |
| 45 | /// Returns the number of matched elements k, or std::nullopt if no match. |
| 46 | static std::optional<size_t> tryMatchProduct(ArrayRef<OpFoldResult> lhs, |
| 47 | size_t lhsTailConsumed, |
| 48 | ArrayRef<OpFoldResult> rhs, |
| 49 | size_t rhsTailConsumed, |
| 50 | MLIRContext *ctx) { |
| 51 | // Build a Variable for the single rhs element. |
| 52 | AffineExpr rhsExpr = getAffineConstantExpr(constant: 1, context: ctx); |
| 53 | SmallVector<Value> rhsOperands; |
| 54 | buildProductExpr(basis: rhs[rhs.size() - rhsTailConsumed - 1], productExpr&: rhsExpr, operands&: rhsOperands, |
| 55 | ctx); |
| 56 | ValueBoundsConstraintSet::Variable rhsVar( |
| 57 | AffineMap::get(dimCount: 0, symbolCount: rhsOperands.size(), results: rhsExpr, context: ctx), rhsOperands); |
| 58 | |
| 59 | // Incrementally accumulate lhs product and check for equality. |
| 60 | AffineExpr lhsExpr = getAffineConstantExpr(constant: 1, context: ctx); |
| 61 | SmallVector<Value> lhsOperands; |
| 62 | for (size_t k = 1; k + lhsTailConsumed <= lhs.size(); ++k) { |
| 63 | buildProductExpr(basis: lhs[lhs.size() - lhsTailConsumed - k], productExpr&: lhsExpr, |
| 64 | operands&: lhsOperands, ctx); |
| 65 | AffineMap lhsMap = AffineMap::get(dimCount: 0, symbolCount: lhsOperands.size(), results: lhsExpr, context: ctx); |
| 66 | ValueBoundsConstraintSet::Variable lhsVar(lhsMap, lhsOperands); |
| 67 | FailureOr<bool> result = ValueBoundsConstraintSet::areEqual(var1: lhsVar, var2: rhsVar); |
| 68 | if (succeeded(Result: result) && *result) |
| 69 | return k; |
| 70 | } |
| 71 | return std::nullopt; |
| 72 | } |
| 73 | |
| 74 | namespace { |
| 75 | |
| 76 | /// Simplify delinearize(linearize) pairs from the tail by matching groups of |
| 77 | /// dimensions whose basis products are equal via ValueBounds analysis. |
| 78 | /// |
| 79 | /// For each step from the tail, tries: |
| 80 | /// 1. Many-to-one: k linearize dims -> 1 delinearize dim |
| 81 | /// 2. One-to-many: 1 linearize dim -> k delinearize dims |
| 82 | /// |
| 83 | /// Matched trailing dimensions are peeled off. Unmatched prefix dimensions |
| 84 | /// are left as residual linearize/delinearize operations. |
| 85 | /// |
| 86 | /// Example (many-to-one, D*E == Z): |
| 87 | /// %lin = affine.linearize_index disjoint [%a, %b, %c, %d, %e] |
| 88 | /// by (A, B, C, D, E) |
| 89 | /// %result:3 = affine.delinearize_index %lin into (X, Y, Z) |
| 90 | /// -> |
| 91 | /// %prefix_lin = affine.linearize_index disjoint [%a, %b, %c] by (A, B, C) |
| 92 | /// %prefix:2 = affine.delinearize_index %prefix_lin into (X, Y) |
| 93 | /// %tail = affine.linearize_index disjoint [%d, %e] by (D, E) |
| 94 | /// %result = [%prefix#0, %prefix#1, %tail] |
| 95 | struct SimplifyDelinearizeOfLinearizeDisjoint final |
| 96 | : OpRewritePattern<AffineDelinearizeIndexOp> { |
| 97 | using Base::Base; |
| 98 | |
| 99 | LogicalResult matchAndRewrite(AffineDelinearizeIndexOp delinearizeOp, |
| 100 | PatternRewriter &rewriter) const override { |
| 101 | auto linearizeOp = |
| 102 | delinearizeOp.getLinearIndex().getDefiningOp<AffineLinearizeIndexOp>(); |
| 103 | if (!linearizeOp) |
| 104 | return rewriter.notifyMatchFailure(arg&: delinearizeOp, |
| 105 | msg: "index doesn't come from linearize" ); |
| 106 | |
| 107 | if (!linearizeOp.getDisjoint()) |
| 108 | return rewriter.notifyMatchFailure(arg&: linearizeOp, msg: "not disjoint" ); |
| 109 | |
| 110 | SmallVector<OpFoldResult> linBasis = linearizeOp.getMixedBasis(); |
| 111 | SmallVector<OpFoldResult> delinBasis = delinearizeOp.getMixedBasis(); |
| 112 | ValueRange linInputs = linearizeOp.getMultiIndex(); |
| 113 | MLIRContext *ctx = rewriter.getContext(); |
| 114 | |
| 115 | // Track how many elements consumed from each tail. |
| 116 | size_t linTailConsumed = 0; |
| 117 | size_t delinTailConsumed = 0; |
| 118 | |
| 119 | // For each matched group (innermost first), record the number of |
| 120 | // linearize and delinearize dimensions it spans. Many-to-one groups |
| 121 | // have linCount > 1, one-to-many groups have delinCount > 1. |
| 122 | SmallVector<std::pair<size_t, size_t>> matchedGroups; |
| 123 | |
| 124 | while (linTailConsumed < linBasis.size() && |
| 125 | delinTailConsumed < delinBasis.size()) { |
| 126 | // Try many-to-one: k lin dims -> 1 delin dim. |
| 127 | if (std::optional<size_t> k = tryMatchProduct( |
| 128 | lhs: linBasis, lhsTailConsumed: linTailConsumed, rhs: delinBasis, rhsTailConsumed: delinTailConsumed, ctx)) { |
| 129 | matchedGroups.emplace_back(Args&: *k, Args: 1); |
| 130 | linTailConsumed += *k; |
| 131 | delinTailConsumed += 1; |
| 132 | continue; |
| 133 | } |
| 134 | // Try one-to-many: 1 lin dim -> k delin dims. |
| 135 | if (std::optional<size_t> k = tryMatchProduct( |
| 136 | lhs: delinBasis, lhsTailConsumed: delinTailConsumed, rhs: linBasis, rhsTailConsumed: linTailConsumed, ctx)) { |
| 137 | matchedGroups.emplace_back(Args: 1, Args&: *k); |
| 138 | delinTailConsumed += *k; |
| 139 | linTailConsumed += 1; |
| 140 | continue; |
| 141 | } |
| 142 | break; |
| 143 | } |
| 144 | |
| 145 | if (matchedGroups.empty()) |
| 146 | return rewriter.notifyMatchFailure(arg&: delinearizeOp, |
| 147 | msg: "no trailing dimensions matched" ); |
| 148 | |
| 149 | SmallVector<Value> results; |
| 150 | |
| 151 | // Build residual prefix ops for unmatched dimensions. |
| 152 | if (delinTailConsumed < delinBasis.size()) { |
| 153 | // Partial match: create residual linearize + delinearize for the |
| 154 | // unmatched prefix. |
| 155 | Value residualLinearize = AffineLinearizeIndexOp::create( |
| 156 | builder&: rewriter, location: linearizeOp.getLoc(), multi_index: linInputs.drop_back(n: linTailConsumed), |
| 157 | basis: ArrayRef(linBasis).drop_back(N: linTailConsumed), |
| 158 | disjoint: linearizeOp.getDisjoint()); |
| 159 | auto residualDelinearize = AffineDelinearizeIndexOp::create( |
| 160 | builder&: rewriter, location: delinearizeOp.getLoc(), linear_index: residualLinearize, |
| 161 | basis: ArrayRef(delinBasis).drop_back(N: delinTailConsumed), |
| 162 | hasOuterBound: delinearizeOp.hasOuterBound()); |
| 163 | results.append(in_start: residualDelinearize.getResults().begin(), |
| 164 | in_end: residualDelinearize.getResults().end()); |
| 165 | } else if (!delinearizeOp.hasOuterBound()) { |
| 166 | // All basis elements consumed, but the original delinearize has no outer |
| 167 | // bound which requires special handling. |
| 168 | ValueRange remainingInputs = linInputs.drop_back(n: linTailConsumed); |
| 169 | if (remainingInputs.empty()) { |
| 170 | // The outermost delinearize result is guaranteed to be zero. |
| 171 | results.push_back(Elt: arith::ConstantIndexOp::create( |
| 172 | builder&: rewriter, location: delinearizeOp.getLoc(), value: 0)); |
| 173 | } else if (remainingInputs.size() == 1) { |
| 174 | // Pass through the single remaining input. |
| 175 | results.push_back(Elt: remainingInputs.front()); |
| 176 | } else { |
| 177 | // Re-linearize the remaining inputs to produce the outermost result. |
| 178 | Value newLin = AffineLinearizeIndexOp::create( |
| 179 | builder&: rewriter, location: linearizeOp.getLoc(), multi_index: remainingInputs, |
| 180 | basis: ArrayRef(linBasis).drop_back(N: linTailConsumed), |
| 181 | disjoint: linearizeOp.getDisjoint()); |
| 182 | results.push_back(Elt: newLin); |
| 183 | } |
| 184 | } |
| 185 | |
| 186 | // Build results for each matched group. |
| 187 | size_t linInputOffset = linInputs.size() - linTailConsumed; |
| 188 | size_t linBasisOffset = linBasis.size() - linTailConsumed; |
| 189 | size_t delinBasisOffset = delinBasis.size() - delinTailConsumed; |
| 190 | for (auto [linCount, delinCount] : llvm::reverse(C&: matchedGroups)) { |
| 191 | if (linCount == 1 && delinCount == 1) { |
| 192 | // Exact 1:1 match: pass through directly. |
| 193 | results.push_back(Elt: linInputs[linInputOffset]); |
| 194 | } else if (linCount > 1) { |
| 195 | // Many-to-one: re-linearize the group's lin inputs. |
| 196 | Value newLin = AffineLinearizeIndexOp::create( |
| 197 | builder&: rewriter, location: linearizeOp.getLoc(), |
| 198 | multi_index: linInputs.slice(n: linInputOffset, m: linCount), |
| 199 | basis: ArrayRef(linBasis).slice(N: linBasisOffset, M: linCount), |
| 200 | /*disjoint=*/true); |
| 201 | results.push_back(Elt: newLin); |
| 202 | } else { |
| 203 | // One-to-many: delinearize the single lin input. |
| 204 | auto newDelin = AffineDelinearizeIndexOp::create( |
| 205 | builder&: rewriter, location: delinearizeOp.getLoc(), linear_index: linInputs[linInputOffset], |
| 206 | basis: ArrayRef(delinBasis).slice(N: delinBasisOffset, M: delinCount), |
| 207 | /*hasOuterBound=*/true); |
| 208 | results.append(in_start: newDelin.getResults().begin(), |
| 209 | in_end: newDelin.getResults().end()); |
| 210 | } |
| 211 | linInputOffset += linCount; |
| 212 | linBasisOffset += linCount; |
| 213 | delinBasisOffset += delinCount; |
| 214 | } |
| 215 | |
| 216 | rewriter.replaceOp(op: delinearizeOp, newValues: results); |
| 217 | return success(); |
| 218 | } |
| 219 | }; |
| 220 | |
| 221 | /// Simplifies the affine map results by eliminating redundant expressions. |
| 222 | /// |
| 223 | /// This function performs a pairwise comparison of all expressions in the map |
| 224 | /// using the analysis from `ValueBoundsConstraintSet`. If an expression `a` is |
| 225 | /// statically proven to be strictly bounded or covered by another expression |
| 226 | /// `b` (based on the given comparison operator `cmp`), `a` is considered |
| 227 | /// redundant and is safely pruned from the results. |
| 228 | static SmallVector<AffineExpr> |
| 229 | simplifyRedundantMapResults(AffineMap map, ValueRange operands, |
| 230 | ValueBoundsConstraintSet::ComparisonOperator cmp) { |
| 231 | llvm::BitVector preservedExprs(map.getNumResults(), true); |
| 232 | for (size_t i = 0, e = map.getNumResults(); i < e; ++i) { |
| 233 | AffineMap mapA = map.getSubMap(resultPos: i); |
| 234 | ValueBoundsConstraintSet::Variable varA(mapA, operands); |
| 235 | |
| 236 | for (size_t j = 0; j < e; ++j) { |
| 237 | if (i == j || !preservedExprs[j]) |
| 238 | continue; |
| 239 | |
| 240 | AffineMap mapB = map.getSubMap(resultPos: j); |
| 241 | ValueBoundsConstraintSet::Variable varB(mapB, operands); |
| 242 | |
| 243 | if (ValueBoundsConstraintSet::compare(lhs: varB, cmp, rhs: varA)) { |
| 244 | preservedExprs[i] = false; |
| 245 | break; |
| 246 | } |
| 247 | } |
| 248 | } |
| 249 | |
| 250 | SmallVector<AffineExpr> mapResults; |
| 251 | for (size_t i = 0, e = map.getNumResults(); i < e; ++i) |
| 252 | if (preservedExprs[i]) |
| 253 | mapResults.push_back(Elt: map.getResult(idx: i)); |
| 254 | return mapResults; |
| 255 | } |
| 256 | |
| 257 | /// A pattern that simplifies multi-result lower and upper bounds of |
| 258 | /// `affine.for` loops by pruning redundant expressions leveraging |
| 259 | /// `ValueBoundsConstraintSet`. |
| 260 | struct SimplifyAffineLoopBoundMap final : OpRewritePattern<AffineForOp> { |
| 261 | using Base::Base; |
| 262 | LogicalResult matchAndRewrite(AffineForOp forOp, |
| 263 | PatternRewriter &rewriter) const override { |
| 264 | AffineMap lowerBoundMap = forOp.getLowerBoundMap(); |
| 265 | auto lowerBoundOperands = forOp.getLowerBoundOperands(); |
| 266 | AffineMap upperBoundMap = forOp.getUpperBoundMap(); |
| 267 | auto upperBoundOperands = forOp.getUpperBoundOperands(); |
| 268 | if (lowerBoundMap.getNumResults() < 2 && |
| 269 | forOp.getUpperBoundMap().getNumResults() < 2) |
| 270 | return failure(); |
| 271 | |
| 272 | SmallVector<AffineExpr> lowerMapExprs = simplifyRedundantMapResults( |
| 273 | map: lowerBoundMap, operands: lowerBoundOperands, cmp: ValueBoundsConstraintSet::GT); |
| 274 | SmallVector<AffineExpr> upperMapExprs = simplifyRedundantMapResults( |
| 275 | map: upperBoundMap, operands: upperBoundOperands, cmp: ValueBoundsConstraintSet::LT); |
| 276 | |
| 277 | bool lowerBoundUpdate = |
| 278 | lowerMapExprs.size() < lowerBoundMap.getNumResults(); |
| 279 | bool upperBoundUpdate = |
| 280 | upperMapExprs.size() < upperBoundMap.getNumResults(); |
| 281 | if (!(lowerBoundUpdate || upperBoundUpdate)) |
| 282 | return failure(); |
| 283 | |
| 284 | MLIRContext *context = forOp->getContext(); |
| 285 | if (lowerBoundUpdate) { |
| 286 | rewriter.modifyOpInPlace(root: forOp, callable: [&]() { |
| 287 | forOp.setLowerBound(operands: forOp.getLowerBoundOperands(), |
| 288 | map: AffineMap::get(dimCount: lowerBoundMap.getNumDims(), |
| 289 | symbolCount: lowerBoundMap.getNumSymbols(), |
| 290 | results: lowerMapExprs, context)); |
| 291 | }); |
| 292 | } |
| 293 | if (upperBoundUpdate) { |
| 294 | rewriter.modifyOpInPlace(root: forOp, callable: [&]() { |
| 295 | forOp.setUpperBound(operands: forOp.getUpperBoundOperands(), |
| 296 | map: AffineMap::get(dimCount: upperBoundMap.getNumDims(), |
| 297 | symbolCount: upperBoundMap.getNumSymbols(), |
| 298 | results: upperMapExprs, context)); |
| 299 | }); |
| 300 | } |
| 301 | return success(); |
| 302 | } |
| 303 | }; |
| 304 | } // namespace |
| 305 | |
| 306 | void affine::populateSimplifyAffineWithBoundsPatterns( |
| 307 | RewritePatternSet &patterns) { |
| 308 | patterns |
| 309 | .add<SimplifyDelinearizeOfLinearizeDisjoint, SimplifyAffineLoopBoundMap>( |
| 310 | arg: patterns.getContext()); |
| 311 | } |
| 312 | |
| 313 | //===----------------------------------------------------------------------===// |
| 314 | // Pass definition |
| 315 | //===----------------------------------------------------------------------===// |
| 316 | |
| 317 | namespace mlir { |
| 318 | namespace affine { |
| 319 | #define GEN_PASS_DEF_SIMPLIFYAFFINEWITHBOUNDS |
| 320 | #include "mlir/Dialect/Affine/Transforms/Passes.h.inc" |
| 321 | } // namespace affine |
| 322 | } // namespace mlir |
| 323 | |
| 324 | namespace { |
| 325 | struct SimplifyAffineWithBoundsPass |
| 326 | : affine::impl::SimplifyAffineWithBoundsBase<SimplifyAffineWithBoundsPass> { |
| 327 | void runOnOperation() override { |
| 328 | RewritePatternSet patterns(&getContext()); |
| 329 | // Add canonicalization patterns first so cheap exact-match cases are |
| 330 | // handled without invoking value bounds analysis. |
| 331 | AffineDelinearizeIndexOp::getCanonicalizationPatterns(results&: patterns, |
| 332 | context: &getContext()); |
| 333 | AffineLinearizeIndexOp::getCanonicalizationPatterns(results&: patterns, |
| 334 | context: &getContext()); |
| 335 | populateSimplifyAffineWithBoundsPatterns(patterns); |
| 336 | if (failed(Result: applyPatternsGreedily(op: getOperation(), patterns: std::move(patterns)))) |
| 337 | return signalPassFailure(); |
| 338 | } |
| 339 | }; |
| 340 | } // namespace |
| 341 | |