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
26using namespace mlir;
27using 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.
31static 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.
46static 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
74namespace {
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]
95struct 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.
228static SmallVector<AffineExpr>
229simplifyRedundantMapResults(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`.
260struct 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
306void affine::populateSimplifyAffineWithBoundsPatterns(
307 RewritePatternSet &patterns) {
308 patterns
309 .add<SimplifyDelinearizeOfLinearizeDisjoint, SimplifyAffineLoopBoundMap>(
310 arg: patterns.getContext());
311}
312
313//===----------------------------------------------------------------------===//
314// Pass definition
315//===----------------------------------------------------------------------===//
316
317namespace mlir {
318namespace affine {
319#define GEN_PASS_DEF_SIMPLIFYAFFINEWITHBOUNDS
320#include "mlir/Dialect/Affine/Transforms/Passes.h.inc"
321} // namespace affine
322} // namespace mlir
323
324namespace {
325struct 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