1//===- AffineExpr.cpp - MLIR Affine Expr Classes --------------------------===//
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 <cmath>
10#include <cstdint>
11#include <utility>
12
13#include "AffineExprDetail.h"
14#include "mlir/IR/AffineExpr.h"
15#include "mlir/IR/AffineExprVisitor.h"
16#include "mlir/IR/AffineMap.h"
17#include "mlir/IR/IntegerSet.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVectorExtras.h"
20#include "llvm/Support/MathExtras.h"
21#include <numeric>
22#include <optional>
23
24using namespace mlir;
25using namespace mlir::detail;
26
27using llvm::divideCeilSigned;
28using llvm::divideFloorSigned;
29using llvm::divideSignedWouldOverflow;
30using llvm::mod;
31
32MLIRContext *AffineExpr::getContext() const { return expr->context; }
33
34AffineExprKind AffineExpr::getKind() const { return expr->kind; }
35
36/// Walk all of the AffineExprs in `e` in postorder. This is a private factory
37/// method to help handle lambda walk functions. Users should use the regular
38/// (non-static) `walk` method.
39template <typename WalkRetTy>
40WalkRetTy mlir::AffineExpr::walk(AffineExpr e,
41 function_ref<WalkRetTy(AffineExpr)> callback) {
42 struct AffineExprWalker
43 : public AffineExprVisitor<AffineExprWalker, WalkRetTy> {
44 function_ref<WalkRetTy(AffineExpr)> callback;
45
46 AffineExprWalker(function_ref<WalkRetTy(AffineExpr)> callback)
47 : callback(callback) {}
48
49 WalkRetTy visitAffineBinaryOpExpr(AffineBinaryOpExpr expr) {
50 return callback(expr);
51 }
52 WalkRetTy visitConstantExpr(AffineConstantExpr expr) {
53 return callback(expr);
54 }
55 WalkRetTy visitDimExpr(AffineDimExpr expr) { return callback(expr); }
56 WalkRetTy visitSymbolExpr(AffineSymbolExpr expr) { return callback(expr); }
57 };
58
59 return AffineExprWalker(callback).walkPostOrder(e);
60}
61// Explicitly instantiate for the two supported return types.
62template void mlir::AffineExpr::walk(AffineExpr e,
63 function_ref<void(AffineExpr)> callback);
64template WalkResult
65mlir::AffineExpr::walk(AffineExpr e,
66 function_ref<WalkResult(AffineExpr)> callback);
67
68// Dispatch affine expression construction based on kind.
69AffineExpr mlir::getAffineBinaryOpExpr(AffineExprKind kind, AffineExpr lhs,
70 AffineExpr rhs) {
71 if (kind == AffineExprKind::Add)
72 return lhs + rhs;
73 if (kind == AffineExprKind::Mul)
74 return lhs * rhs;
75 if (kind == AffineExprKind::FloorDiv)
76 return lhs.floorDiv(other: rhs);
77 if (kind == AffineExprKind::CeilDiv)
78 return lhs.ceilDiv(other: rhs);
79 if (kind == AffineExprKind::Mod)
80 return lhs % rhs;
81
82 llvm_unreachable("unknown binary operation on affine expressions");
83}
84
85/// This method substitutes any uses of dimensions and symbols (e.g.
86/// dim#0 with dimReplacements[0]) and returns the modified expression tree.
87AffineExpr
88AffineExpr::replaceDimsAndSymbols(ArrayRef<AffineExpr> dimReplacements,
89 ArrayRef<AffineExpr> symReplacements) const {
90 switch (getKind()) {
91 case AffineExprKind::Constant:
92 return *this;
93 case AffineExprKind::DimId: {
94 unsigned dimId = llvm::cast<AffineDimExpr>(Val: *this).getPosition();
95 if (dimId >= dimReplacements.size())
96 return *this;
97 return dimReplacements[dimId];
98 }
99 case AffineExprKind::SymbolId: {
100 unsigned symId = llvm::cast<AffineSymbolExpr>(Val: *this).getPosition();
101 if (symId >= symReplacements.size())
102 return *this;
103 return symReplacements[symId];
104 }
105 case AffineExprKind::Add:
106 case AffineExprKind::Mul:
107 case AffineExprKind::FloorDiv:
108 case AffineExprKind::CeilDiv:
109 case AffineExprKind::Mod:
110 auto binOp = llvm::cast<AffineBinaryOpExpr>(Val: *this);
111 auto lhs = binOp.getLHS(), rhs = binOp.getRHS();
112 auto newLHS = lhs.replaceDimsAndSymbols(dimReplacements, symReplacements);
113 auto newRHS = rhs.replaceDimsAndSymbols(dimReplacements, symReplacements);
114 if (newLHS == lhs && newRHS == rhs)
115 return *this;
116 return getAffineBinaryOpExpr(kind: getKind(), lhs: newLHS, rhs: newRHS);
117 }
118 llvm_unreachable("Unknown AffineExpr");
119}
120
121AffineExpr AffineExpr::replaceDims(ArrayRef<AffineExpr> dimReplacements) const {
122 return replaceDimsAndSymbols(dimReplacements, symReplacements: {});
123}
124
125AffineExpr
126AffineExpr::replaceSymbols(ArrayRef<AffineExpr> symReplacements) const {
127 return replaceDimsAndSymbols(dimReplacements: {}, symReplacements);
128}
129
130/// Replace dims[offset ... numDims)
131/// by dims[offset + shift ... shift + numDims).
132AffineExpr AffineExpr::shiftDims(unsigned numDims, unsigned shift,
133 unsigned offset) const {
134 SmallVector<AffineExpr, 4> dims;
135 for (unsigned idx = 0; idx < offset; ++idx)
136 dims.push_back(Elt: getAffineDimExpr(position: idx, context: getContext()));
137 for (unsigned idx = offset; idx < numDims; ++idx)
138 dims.push_back(Elt: getAffineDimExpr(position: idx + shift, context: getContext()));
139 return replaceDimsAndSymbols(dimReplacements: dims, symReplacements: {});
140}
141
142/// Replace symbols[offset ... numSymbols)
143/// by symbols[offset + shift ... shift + numSymbols).
144AffineExpr AffineExpr::shiftSymbols(unsigned numSymbols, unsigned shift,
145 unsigned offset) const {
146 SmallVector<AffineExpr, 4> symbols;
147 for (unsigned idx = 0; idx < offset; ++idx)
148 symbols.push_back(Elt: getAffineSymbolExpr(position: idx, context: getContext()));
149 for (unsigned idx = offset; idx < numSymbols; ++idx)
150 symbols.push_back(Elt: getAffineSymbolExpr(position: idx + shift, context: getContext()));
151 return replaceDimsAndSymbols(dimReplacements: {}, symReplacements: symbols);
152}
153
154/// Sparse replace method. Return the modified expression tree.
155AffineExpr
156AffineExpr::replace(const DenseMap<AffineExpr, AffineExpr> &map) const {
157 auto it = map.find(Val: *this);
158 if (it != map.end())
159 return it->second;
160 switch (getKind()) {
161 default:
162 return *this;
163 case AffineExprKind::Add:
164 case AffineExprKind::Mul:
165 case AffineExprKind::FloorDiv:
166 case AffineExprKind::CeilDiv:
167 case AffineExprKind::Mod:
168 auto binOp = llvm::cast<AffineBinaryOpExpr>(Val: *this);
169 auto lhs = binOp.getLHS(), rhs = binOp.getRHS();
170 auto newLHS = lhs.replace(map);
171 auto newRHS = rhs.replace(map);
172 if (newLHS == lhs && newRHS == rhs)
173 return *this;
174 return getAffineBinaryOpExpr(kind: getKind(), lhs: newLHS, rhs: newRHS);
175 }
176 llvm_unreachable("Unknown AffineExpr");
177}
178
179/// Sparse replace method. Return the modified expression tree.
180AffineExpr AffineExpr::replace(AffineExpr expr, AffineExpr replacement) const {
181 DenseMap<AffineExpr, AffineExpr> map;
182 map.insert(KV: std::make_pair(x&: expr, y&: replacement));
183 return replace(map);
184}
185/// Returns true if this expression is made out of only symbols and
186/// constants (no dimensional identifiers).
187bool AffineExpr::isSymbolicOrConstant() const {
188 switch (getKind()) {
189 case AffineExprKind::Constant:
190 return true;
191 case AffineExprKind::DimId:
192 return false;
193 case AffineExprKind::SymbolId:
194 return true;
195
196 case AffineExprKind::Add:
197 case AffineExprKind::Mul:
198 case AffineExprKind::FloorDiv:
199 case AffineExprKind::CeilDiv:
200 case AffineExprKind::Mod: {
201 auto expr = llvm::cast<AffineBinaryOpExpr>(Val: *this);
202 return expr.getLHS().isSymbolicOrConstant() &&
203 expr.getRHS().isSymbolicOrConstant();
204 }
205 }
206 llvm_unreachable("Unknown AffineExpr");
207}
208
209/// Returns true if this is a pure affine expression, i.e., multiplication,
210/// floordiv, ceildiv, and mod is only allowed w.r.t constants.
211bool AffineExpr::isPureAffine() const {
212 switch (getKind()) {
213 case AffineExprKind::SymbolId:
214 case AffineExprKind::DimId:
215 case AffineExprKind::Constant:
216 return true;
217 case AffineExprKind::Add: {
218 auto op = llvm::cast<AffineBinaryOpExpr>(Val: *this);
219 return op.getLHS().isPureAffine() && op.getRHS().isPureAffine();
220 }
221
222 case AffineExprKind::Mul: {
223 // TODO: Canonicalize the constants in binary operators to the RHS when
224 // possible, allowing this to merge into the next case.
225 auto op = llvm::cast<AffineBinaryOpExpr>(Val: *this);
226 return op.getLHS().isPureAffine() && op.getRHS().isPureAffine() &&
227 (llvm::isa<AffineConstantExpr>(Val: op.getLHS()) ||
228 llvm::isa<AffineConstantExpr>(Val: op.getRHS()));
229 }
230 case AffineExprKind::FloorDiv:
231 case AffineExprKind::CeilDiv:
232 case AffineExprKind::Mod: {
233 auto op = llvm::cast<AffineBinaryOpExpr>(Val: *this);
234 return op.getLHS().isPureAffine() &&
235 llvm::isa<AffineConstantExpr>(Val: op.getRHS());
236 }
237 }
238 llvm_unreachable("Unknown AffineExpr");
239}
240
241// Returns the greatest known integral divisor of this affine expression.
242int64_t AffineExpr::getLargestKnownDivisor() const {
243 AffineBinaryOpExpr binExpr(nullptr);
244 switch (getKind()) {
245 case AffineExprKind::DimId:
246 [[fallthrough]];
247 case AffineExprKind::SymbolId:
248 return 1;
249 case AffineExprKind::CeilDiv:
250 [[fallthrough]];
251 case AffineExprKind::FloorDiv: {
252 // If the RHS is a constant and divides the known divisor on the LHS, the
253 // quotient is a known divisor of the expression.
254 binExpr = llvm::cast<AffineBinaryOpExpr>(Val: *this);
255 auto rhs = llvm::dyn_cast<AffineConstantExpr>(Val: binExpr.getRHS());
256 // Leave alone undefined expressions.
257 if (rhs && rhs.getValue() != 0) {
258 int64_t lhsDiv = binExpr.getLHS().getLargestKnownDivisor();
259 if (lhsDiv % rhs.getValue() == 0)
260 return std::abs(i: lhsDiv / rhs.getValue());
261 }
262 return 1;
263 }
264 case AffineExprKind::Constant:
265 return std::abs(i: llvm::cast<AffineConstantExpr>(Val: *this).getValue());
266 case AffineExprKind::Mul: {
267 binExpr = llvm::cast<AffineBinaryOpExpr>(Val: *this);
268 return binExpr.getLHS().getLargestKnownDivisor() *
269 binExpr.getRHS().getLargestKnownDivisor();
270 }
271 case AffineExprKind::Add:
272 [[fallthrough]];
273 case AffineExprKind::Mod: {
274 binExpr = llvm::cast<AffineBinaryOpExpr>(Val: *this);
275 return std::gcd(m: (uint64_t)binExpr.getLHS().getLargestKnownDivisor(),
276 n: (uint64_t)binExpr.getRHS().getLargestKnownDivisor());
277 }
278 }
279 llvm_unreachable("Unknown AffineExpr");
280}
281
282bool AffineExpr::isMultipleOf(int64_t factor) const {
283 AffineBinaryOpExpr binExpr(nullptr);
284 uint64_t l, u;
285 switch (getKind()) {
286 case AffineExprKind::SymbolId:
287 [[fallthrough]];
288 case AffineExprKind::DimId:
289 return factor * factor == 1;
290 case AffineExprKind::Constant:
291 return llvm::cast<AffineConstantExpr>(Val: *this).getValue() % factor == 0;
292 case AffineExprKind::Mul: {
293 binExpr = llvm::cast<AffineBinaryOpExpr>(Val: *this);
294 // It's probably not worth optimizing this further (to not traverse the
295 // whole sub-tree under - it that would require a version of isMultipleOf
296 // that on a 'false' return also returns the largest known divisor).
297 return (l = binExpr.getLHS().getLargestKnownDivisor()) % factor == 0 ||
298 (u = binExpr.getRHS().getLargestKnownDivisor()) % factor == 0 ||
299 (l * u) % factor == 0;
300 }
301 case AffineExprKind::Add:
302 case AffineExprKind::FloorDiv:
303 case AffineExprKind::CeilDiv:
304 case AffineExprKind::Mod: {
305 binExpr = llvm::cast<AffineBinaryOpExpr>(Val: *this);
306 return std::gcd(m: (uint64_t)binExpr.getLHS().getLargestKnownDivisor(),
307 n: (uint64_t)binExpr.getRHS().getLargestKnownDivisor()) %
308 factor ==
309 0;
310 }
311 }
312 llvm_unreachable("Unknown AffineExpr");
313}
314
315bool AffineExpr::isFunctionOfDim(unsigned position) const {
316 if (getKind() == AffineExprKind::DimId) {
317 return *this == mlir::getAffineDimExpr(position, context: getContext());
318 }
319 if (auto expr = llvm::dyn_cast<AffineBinaryOpExpr>(Val: *this)) {
320 return expr.getLHS().isFunctionOfDim(position) ||
321 expr.getRHS().isFunctionOfDim(position);
322 }
323 return false;
324}
325
326bool AffineExpr::isFunctionOfSymbol(unsigned position) const {
327 if (getKind() == AffineExprKind::SymbolId) {
328 return *this == mlir::getAffineSymbolExpr(position, context: getContext());
329 }
330 if (auto expr = llvm::dyn_cast<AffineBinaryOpExpr>(Val: *this)) {
331 return expr.getLHS().isFunctionOfSymbol(position) ||
332 expr.getRHS().isFunctionOfSymbol(position);
333 }
334 return false;
335}
336
337AffineBinaryOpExpr::AffineBinaryOpExpr(AffineExpr::ImplType *ptr)
338 : AffineExpr(ptr) {}
339AffineExpr AffineBinaryOpExpr::getLHS() const {
340 return static_cast<ImplType *>(expr)->lhs;
341}
342AffineExpr AffineBinaryOpExpr::getRHS() const {
343 return static_cast<ImplType *>(expr)->rhs;
344}
345
346AffineDimExpr::AffineDimExpr(AffineExpr::ImplType *ptr) : AffineExpr(ptr) {}
347unsigned AffineDimExpr::getPosition() const {
348 return static_cast<ImplType *>(expr)->position;
349}
350
351/// Returns true if the expression is divisible by the given symbol with
352/// position `symbolPos`. The argument `opKind` specifies here what kind of
353/// division or mod operation called this division. It helps in implementing the
354/// commutative property of the floordiv and ceildiv operations. If the argument
355///`exprKind` is floordiv and `expr` is also a binary expression of a floordiv
356/// operation, then the commutative property can be used otherwise, the floordiv
357/// operation is not divisible. The same argument holds for ceildiv operation.
358static bool canSimplifyDivisionBySymbol(AffineExpr expr, unsigned symbolPos,
359 AffineExprKind opKind,
360 bool fromMul = false) {
361 // The argument `opKind` can either be Modulo, Floordiv or Ceildiv only.
362 assert((opKind == AffineExprKind::Mod || opKind == AffineExprKind::FloorDiv ||
363 opKind == AffineExprKind::CeilDiv) &&
364 "unexpected opKind");
365 switch (expr.getKind()) {
366 case AffineExprKind::Constant:
367 return cast<AffineConstantExpr>(Val&: expr).getValue() == 0;
368 case AffineExprKind::DimId:
369 return false;
370 case AffineExprKind::SymbolId:
371 return (cast<AffineSymbolExpr>(Val&: expr).getPosition() == symbolPos);
372 // Checks divisibility by the given symbol for both operands.
373 case AffineExprKind::Add: {
374 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
375 return canSimplifyDivisionBySymbol(expr: binaryExpr.getLHS(), symbolPos,
376 opKind) &&
377 canSimplifyDivisionBySymbol(expr: binaryExpr.getRHS(), symbolPos, opKind);
378 }
379 // Checks divisibility by the given symbol for both operands. Consider the
380 // expression `(((s1*s0) floordiv w) mod ((s1 * s2) floordiv p)) floordiv s1`,
381 // this is a division by s1 and both the operands of modulo are divisible by
382 // s1 but it is not divisible by s1 always. The third argument is
383 // `AffineExprKind::Mod` for this reason.
384 case AffineExprKind::Mod: {
385 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
386 return canSimplifyDivisionBySymbol(expr: binaryExpr.getLHS(), symbolPos,
387 opKind: AffineExprKind::Mod) &&
388 canSimplifyDivisionBySymbol(expr: binaryExpr.getRHS(), symbolPos,
389 opKind: AffineExprKind::Mod);
390 }
391 // Checks if any of the operand divisible by the given symbol.
392 case AffineExprKind::Mul: {
393 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
394 return canSimplifyDivisionBySymbol(expr: binaryExpr.getLHS(), symbolPos, opKind,
395 fromMul: true) ||
396 canSimplifyDivisionBySymbol(expr: binaryExpr.getRHS(), symbolPos, opKind,
397 fromMul: true);
398 }
399 // Floordiv and ceildiv are divisible by the given symbol when the first
400 // operand is divisible, and the affine expression kind of the argument expr
401 // is same as the argument `opKind`. This can be inferred from commutative
402 // property of floordiv and ceildiv operations and are as follow:
403 // (exp1 floordiv exp2) floordiv exp3 = (exp1 floordiv exp3) floordiv exp2
404 // (exp1 ceildiv exp2) ceildiv exp3 = (exp1 ceildiv exp3) ceildiv expr2
405 // It will fail 1.if operations are not same. For example:
406 // (exps1 ceildiv exp2) floordiv exp3 can not be simplified. 2.if there is a
407 // multiplication operation in the expression. For example:
408 // (exps1 ceildiv exp2) mul exp3 ceildiv exp4 can not be simplified.
409 case AffineExprKind::FloorDiv:
410 case AffineExprKind::CeilDiv: {
411 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
412 if (opKind != expr.getKind())
413 return false;
414 if (fromMul)
415 return false;
416 return canSimplifyDivisionBySymbol(expr: binaryExpr.getLHS(), symbolPos,
417 opKind: expr.getKind());
418 }
419 }
420 llvm_unreachable("Unknown AffineExpr");
421}
422
423/// Divides the given expression by the given symbol at position `symbolPos`. It
424/// considers the divisibility condition is checked before calling itself. A
425/// null expression is returned whenever the divisibility condition fails.
426static AffineExpr symbolicDivide(AffineExpr expr, unsigned symbolPos,
427 AffineExprKind opKind) {
428 // THe argument `opKind` can either be Modulo, Floordiv or Ceildiv only.
429 assert((opKind == AffineExprKind::Mod || opKind == AffineExprKind::FloorDiv ||
430 opKind == AffineExprKind::CeilDiv) &&
431 "unexpected opKind");
432 switch (expr.getKind()) {
433 case AffineExprKind::Constant:
434 if (cast<AffineConstantExpr>(Val&: expr).getValue() != 0)
435 return nullptr;
436 return getAffineConstantExpr(constant: 0, context: expr.getContext());
437 case AffineExprKind::DimId:
438 return nullptr;
439 case AffineExprKind::SymbolId:
440 return getAffineConstantExpr(constant: 1, context: expr.getContext());
441 // Dividing both operands by the given symbol.
442 case AffineExprKind::Add: {
443 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
444 return getAffineBinaryOpExpr(
445 kind: expr.getKind(), lhs: symbolicDivide(expr: binaryExpr.getLHS(), symbolPos, opKind),
446 rhs: symbolicDivide(expr: binaryExpr.getRHS(), symbolPos, opKind));
447 }
448 // Dividing both operands by the given symbol.
449 case AffineExprKind::Mod: {
450 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
451 return getAffineBinaryOpExpr(
452 kind: expr.getKind(),
453 lhs: symbolicDivide(expr: binaryExpr.getLHS(), symbolPos, opKind: expr.getKind()),
454 rhs: symbolicDivide(expr: binaryExpr.getRHS(), symbolPos, opKind: expr.getKind()));
455 }
456 // Dividing any of the operand by the given symbol.
457 case AffineExprKind::Mul: {
458 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
459 if (!canSimplifyDivisionBySymbol(expr: binaryExpr.getLHS(), symbolPos, opKind))
460 return binaryExpr.getLHS() *
461 symbolicDivide(expr: binaryExpr.getRHS(), symbolPos, opKind);
462 return symbolicDivide(expr: binaryExpr.getLHS(), symbolPos, opKind) *
463 binaryExpr.getRHS();
464 }
465 // Dividing first operand only by the given symbol.
466 case AffineExprKind::FloorDiv:
467 case AffineExprKind::CeilDiv: {
468 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
469 return getAffineBinaryOpExpr(
470 kind: expr.getKind(),
471 lhs: symbolicDivide(expr: binaryExpr.getLHS(), symbolPos, opKind: expr.getKind()),
472 rhs: binaryExpr.getRHS());
473 }
474 }
475 llvm_unreachable("Unknown AffineExpr");
476}
477
478/// Populate `result` with all summand operands of given (potentially nested)
479/// addition. If the given expression is not an addition, just populate the
480/// expression itself.
481/// Example: Add(Add(7, 8), Mul(9, 10)) will return [7, 8, Mul(9, 10)].
482static void getSummandExprs(AffineExpr expr, SmallVector<AffineExpr> &result) {
483 auto addExpr = dyn_cast<AffineBinaryOpExpr>(Val&: expr);
484 if (!addExpr || addExpr.getKind() != AffineExprKind::Add) {
485 result.push_back(Elt: expr);
486 return;
487 }
488 getSummandExprs(expr: addExpr.getLHS(), result);
489 getSummandExprs(expr: addExpr.getRHS(), result);
490}
491
492/// Return "true" if `candidate` is a negated expression, i.e., Mul(-1, expr).
493/// If so, also return the non-negated expression via `expr`.
494static bool isNegatedAffineExpr(AffineExpr candidate, AffineExpr &expr) {
495 auto mulExpr = dyn_cast<AffineBinaryOpExpr>(Val&: candidate);
496 if (!mulExpr || mulExpr.getKind() != AffineExprKind::Mul)
497 return false;
498 if (auto lhs = dyn_cast<AffineConstantExpr>(Val: mulExpr.getLHS())) {
499 if (lhs.getValue() == -1) {
500 expr = mulExpr.getRHS();
501 return true;
502 }
503 }
504 if (auto rhs = dyn_cast<AffineConstantExpr>(Val: mulExpr.getRHS())) {
505 if (rhs.getValue() == -1) {
506 expr = mulExpr.getLHS();
507 return true;
508 }
509 }
510 return false;
511}
512
513/// Return "true" if `lhs` % `rhs` is guaranteed to evaluate to zero based on
514/// the fact that `lhs` contains another modulo expression that ensures that
515/// `lhs` is divisible by `rhs`. This is a common pattern in the resulting IR
516/// after loop peeling.
517///
518/// Example: lhs = ub - ub % step
519/// rhs = step
520/// => (ub - ub % step) % step is guaranteed to evaluate to 0.
521static bool isModOfModSubtraction(AffineExpr lhs, AffineExpr rhs,
522 unsigned numDims, unsigned numSymbols) {
523 // TODO: Try to unify this function with `getBoundForAffineExpr`.
524 // Collect all summands in lhs.
525 SmallVector<AffineExpr> summands;
526 getSummandExprs(expr: lhs, result&: summands);
527 // Look for Mul(-1, Mod(x, rhs)) among the summands. If x matches the
528 // remaining summands, then lhs % rhs is guaranteed to evaluate to 0.
529 for (int64_t i = 0, e = summands.size(); i < e; ++i) {
530 AffineExpr current = summands[i];
531 AffineExpr beforeNegation;
532 if (!isNegatedAffineExpr(candidate: current, expr&: beforeNegation))
533 continue;
534 AffineBinaryOpExpr innerMod = dyn_cast<AffineBinaryOpExpr>(Val&: beforeNegation);
535 if (!innerMod || innerMod.getKind() != AffineExprKind::Mod)
536 continue;
537 if (innerMod.getRHS() != rhs)
538 continue;
539 // Sum all remaining summands and subtract x. If that expression can be
540 // simplified to zero, then the remaining summands and x are equal.
541 AffineExpr diff = getAffineConstantExpr(constant: 0, context: lhs.getContext());
542 for (int64_t j = 0; j < e; ++j)
543 if (i != j)
544 diff = diff + summands[j];
545 diff = diff - innerMod.getLHS();
546 diff = simplifyAffineExpr(expr: diff, numDims, numSymbols);
547 auto constExpr = dyn_cast<AffineConstantExpr>(Val&: diff);
548 if (constExpr && constExpr.getValue() == 0)
549 return true;
550 }
551 return false;
552}
553
554/// Simplify a semi-affine expression by handling modulo, floordiv, or ceildiv
555/// operations when the second operand simplifies to a symbol and the first
556/// operand is divisible by that symbol. It can be applied to any semi-affine
557/// expression. Returned expression can either be a semi-affine or pure affine
558/// expression.
559static AffineExpr simplifySemiAffine(AffineExpr expr, unsigned numDims,
560 unsigned numSymbols) {
561 switch (expr.getKind()) {
562 case AffineExprKind::Constant:
563 case AffineExprKind::DimId:
564 case AffineExprKind::SymbolId:
565 return expr;
566 case AffineExprKind::Add:
567 case AffineExprKind::Mul: {
568 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
569 return getAffineBinaryOpExpr(
570 kind: expr.getKind(),
571 lhs: simplifySemiAffine(expr: binaryExpr.getLHS(), numDims, numSymbols),
572 rhs: simplifySemiAffine(expr: binaryExpr.getRHS(), numDims, numSymbols));
573 }
574 // Check if the simplification of the second operand is a symbol, and the
575 // first operand is divisible by it. If the operation is a modulo, a constant
576 // zero expression is returned. In the case of floordiv and ceildiv, the
577 // symbol from the simplification of the second operand divides the first
578 // operand. Otherwise, simplification is not possible.
579 case AffineExprKind::FloorDiv:
580 case AffineExprKind::CeilDiv:
581 case AffineExprKind::Mod: {
582 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
583 AffineExpr sLHS =
584 simplifySemiAffine(expr: binaryExpr.getLHS(), numDims, numSymbols);
585 AffineExpr sRHS =
586 simplifySemiAffine(expr: binaryExpr.getRHS(), numDims, numSymbols);
587 if (isModOfModSubtraction(lhs: sLHS, rhs: sRHS, numDims, numSymbols))
588 return getAffineConstantExpr(constant: 0, context: expr.getContext());
589 AffineSymbolExpr symbolExpr = dyn_cast<AffineSymbolExpr>(
590 Val: simplifySemiAffine(expr: binaryExpr.getRHS(), numDims, numSymbols));
591 if (!symbolExpr)
592 return getAffineBinaryOpExpr(kind: expr.getKind(), lhs: sLHS, rhs: sRHS);
593 unsigned symbolPos = symbolExpr.getPosition();
594 if (!canSimplifyDivisionBySymbol(expr: binaryExpr.getLHS(), symbolPos,
595 opKind: expr.getKind()))
596 return getAffineBinaryOpExpr(kind: expr.getKind(), lhs: sLHS, rhs: sRHS);
597 if (expr.getKind() == AffineExprKind::Mod)
598 return getAffineConstantExpr(constant: 0, context: expr.getContext());
599 AffineExpr simplifiedQuotient =
600 symbolicDivide(expr: sLHS, symbolPos, opKind: expr.getKind());
601 return simplifiedQuotient
602 ? simplifiedQuotient
603 : getAffineBinaryOpExpr(kind: expr.getKind(), lhs: sLHS, rhs: sRHS);
604 }
605 }
606 llvm_unreachable("Unknown AffineExpr");
607}
608
609static AffineExpr getAffineDimOrSymbol(AffineExprKind kind, unsigned position,
610 MLIRContext *context) {
611 auto assignCtx = [context](AffineDimExprStorage *storage) {
612 storage->context = context;
613 };
614
615 StorageUniquer &uniquer = context->getAffineUniquer();
616 return uniquer.get<AffineDimExprStorage>(
617 initFn: assignCtx, args: static_cast<unsigned>(kind), args&: position);
618}
619
620AffineExpr mlir::getAffineDimExpr(unsigned position, MLIRContext *context) {
621 return getAffineDimOrSymbol(kind: AffineExprKind::DimId, position, context);
622}
623
624AffineSymbolExpr::AffineSymbolExpr(AffineExpr::ImplType *ptr)
625 : AffineExpr(ptr) {}
626unsigned AffineSymbolExpr::getPosition() const {
627 return static_cast<ImplType *>(expr)->position;
628}
629
630AffineExpr mlir::getAffineSymbolExpr(unsigned position, MLIRContext *context) {
631 return getAffineDimOrSymbol(kind: AffineExprKind::SymbolId, position, context);
632}
633
634AffineConstantExpr::AffineConstantExpr(AffineExpr::ImplType *ptr)
635 : AffineExpr(ptr) {}
636int64_t AffineConstantExpr::getValue() const {
637 return static_cast<ImplType *>(expr)->constant;
638}
639
640bool AffineExpr::operator==(int64_t v) const {
641 return *this == getAffineConstantExpr(constant: v, context: getContext());
642}
643
644AffineExpr mlir::getAffineConstantExpr(int64_t constant, MLIRContext *context) {
645 auto assignCtx = [context](AffineConstantExprStorage *storage) {
646 storage->context = context;
647 };
648
649 StorageUniquer &uniquer = context->getAffineUniquer();
650 return uniquer.get<AffineConstantExprStorage>(initFn: assignCtx, args&: constant);
651}
652
653SmallVector<AffineExpr>
654mlir::getAffineConstantExprs(ArrayRef<int64_t> constants,
655 MLIRContext *context) {
656 return llvm::map_to_vector(C&: constants, F: [&](int64_t constant) {
657 return getAffineConstantExpr(constant, context);
658 });
659}
660
661/// Simplify add expression. Return nullptr if it can't be simplified.
662static AffineExpr simplifyAdd(AffineExpr lhs, AffineExpr rhs) {
663 auto lhsConst = dyn_cast<AffineConstantExpr>(Val&: lhs);
664 auto rhsConst = dyn_cast<AffineConstantExpr>(Val&: rhs);
665 // Fold if both LHS, RHS are a constant and the sum does not overflow.
666 if (lhsConst && rhsConst) {
667 int64_t sum;
668 if (llvm::AddOverflow(X: lhsConst.getValue(), Y: rhsConst.getValue(), Result&: sum)) {
669 return nullptr;
670 }
671 return getAffineConstantExpr(constant: sum, context: lhs.getContext());
672 }
673
674 // Canonicalize so that only the RHS is a constant. (4 + d0 becomes d0 + 4).
675 // If only one of them is a symbolic expressions, make it the RHS.
676 if (isa<AffineConstantExpr>(Val: lhs) ||
677 (lhs.isSymbolicOrConstant() && !rhs.isSymbolicOrConstant())) {
678 return rhs + lhs;
679 }
680
681 // At this point, if there was a constant, it would be on the right.
682
683 // Addition with a zero is a noop, return the other input.
684 if (rhsConst) {
685 if (rhsConst.getValue() == 0)
686 return lhs;
687 }
688 // Fold successive additions like (d0 + 2) + 3 into d0 + 5.
689 auto lBin = dyn_cast<AffineBinaryOpExpr>(Val&: lhs);
690 if (lBin && rhsConst && lBin.getKind() == AffineExprKind::Add) {
691 if (auto lrhs = dyn_cast<AffineConstantExpr>(Val: lBin.getRHS()))
692 return lBin.getLHS() + (lrhs.getValue() + rhsConst.getValue());
693 }
694
695 // Detect "c1 * expr + c_2 * expr" as "(c1 + c2) * expr".
696 // c1 is rRhsConst, c2 is rLhsConst; firstExpr, secondExpr are their
697 // respective multiplicands.
698 std::optional<int64_t> rLhsConst, rRhsConst;
699 AffineExpr firstExpr, secondExpr;
700 AffineConstantExpr rLhsConstExpr;
701 auto lBinOpExpr = dyn_cast<AffineBinaryOpExpr>(Val&: lhs);
702 if (lBinOpExpr && lBinOpExpr.getKind() == AffineExprKind::Mul &&
703 (rLhsConstExpr = dyn_cast<AffineConstantExpr>(Val: lBinOpExpr.getRHS()))) {
704 rLhsConst = rLhsConstExpr.getValue();
705 firstExpr = lBinOpExpr.getLHS();
706 } else {
707 rLhsConst = 1;
708 firstExpr = lhs;
709 }
710
711 auto rBinOpExpr = dyn_cast<AffineBinaryOpExpr>(Val&: rhs);
712 AffineConstantExpr rRhsConstExpr;
713 if (rBinOpExpr && rBinOpExpr.getKind() == AffineExprKind::Mul &&
714 (rRhsConstExpr = dyn_cast<AffineConstantExpr>(Val: rBinOpExpr.getRHS()))) {
715 rRhsConst = rRhsConstExpr.getValue();
716 secondExpr = rBinOpExpr.getLHS();
717 } else {
718 rRhsConst = 1;
719 secondExpr = rhs;
720 }
721
722 if (rLhsConst && rRhsConst && firstExpr == secondExpr)
723 return getAffineBinaryOpExpr(
724 kind: AffineExprKind::Mul, lhs: firstExpr,
725 rhs: getAffineConstantExpr(constant: *rLhsConst + *rRhsConst, context: lhs.getContext()));
726
727 // When doing successive additions, bring constant to the right: turn (d0 + 2)
728 // + d1 into (d0 + d1) + 2.
729 if (lBin && lBin.getKind() == AffineExprKind::Add) {
730 if (auto lrhs = dyn_cast<AffineConstantExpr>(Val: lBin.getRHS())) {
731 return lBin.getLHS() + rhs + lrhs;
732 }
733 }
734
735 // Detect and transform "expr - q * (expr floordiv q)" to "expr mod q", where
736 // q may be a constant or symbolic expression. This leads to a much more
737 // efficient form when 'c' is a power of two, and in general a more compact
738 // and readable form.
739
740 // Process '(expr floordiv c) * (-c)'.
741 if (!rBinOpExpr || rBinOpExpr.getKind() != AffineExprKind::Mul)
742 return nullptr;
743
744 auto lrhs = rBinOpExpr.getLHS();
745 auto rrhs = rBinOpExpr.getRHS();
746
747 AffineExpr llrhs, rlrhs;
748
749 // Check if lrhsBinOpExpr is of the form (expr floordiv q) * q,
750 // where q is a symbolic expression.
751 auto lrhsBinOpExpr = dyn_cast<AffineBinaryOpExpr>(Val&: lrhs);
752 // Check rrhsConstOpExpr = -1 as part of ((expr floordiv q) * q)) * (-1).
753 auto rrhsConstOpExpr = dyn_cast<AffineConstantExpr>(Val&: rrhs);
754 if (rrhsConstOpExpr && rrhsConstOpExpr.getValue() == -1 && lrhsBinOpExpr &&
755 lrhsBinOpExpr.getKind() == AffineExprKind::Mul) {
756 // Check llrhs = expr floordiv q.
757 llrhs = lrhsBinOpExpr.getLHS();
758 // Check rlrhs = q.
759 rlrhs = lrhsBinOpExpr.getRHS();
760 auto llrhsBinOpExpr = dyn_cast<AffineBinaryOpExpr>(Val&: llrhs);
761 if (!llrhsBinOpExpr || llrhsBinOpExpr.getKind() != AffineExprKind::FloorDiv)
762 return nullptr;
763 if (llrhsBinOpExpr.getRHS() == rlrhs && lhs == llrhsBinOpExpr.getLHS())
764 return lhs % rlrhs;
765 }
766
767 // Process lrhs, which is 'expr floordiv c'.
768 // expr + (expr // c * -c) = expr % c
769 AffineBinaryOpExpr lrBinOpExpr = dyn_cast<AffineBinaryOpExpr>(Val&: lrhs);
770 if (!lrBinOpExpr || rhs.getKind() != AffineExprKind::Mul ||
771 lrBinOpExpr.getKind() != AffineExprKind::FloorDiv)
772 return nullptr;
773
774 llrhs = lrBinOpExpr.getLHS();
775 rlrhs = lrBinOpExpr.getRHS();
776 auto rlrhsConstOpExpr = dyn_cast<AffineConstantExpr>(Val&: rlrhs);
777 // We don't support modulo with a negative RHS.
778 bool isPositiveRhs = rlrhsConstOpExpr && rlrhsConstOpExpr.getValue() > 0;
779
780 if (isPositiveRhs && lhs == llrhs && rlrhs == -rrhs) {
781 return lhs % rlrhs;
782 }
783
784 // Try simplify lhs's last operand with rhs. e.g:
785 // (s0 * 64 + s1) + (s1 // c * -c) --->
786 // s0 * 64 + (s1 + s1 // c * -c) -->
787 // s0 * 64 + s1 % c
788 if (lBinOpExpr && lBinOpExpr.getKind() == AffineExprKind::Add) {
789 if (auto simplified = simplifyAdd(lhs: lBinOpExpr.getRHS(), rhs))
790 return lBinOpExpr.getLHS() + simplified;
791 }
792 return nullptr;
793}
794
795/// Get the canonical order of two commutative exprs arguments.
796static std::pair<AffineExpr, AffineExpr>
797orderCommutativeArgs(AffineExpr expr1, AffineExpr expr2) {
798 auto sym1 = dyn_cast<AffineSymbolExpr>(Val&: expr1);
799 auto sym2 = dyn_cast<AffineSymbolExpr>(Val&: expr2);
800 // Try to order by symbol/dim position first.
801 if (sym1 && sym2)
802 return sym1.getPosition() < sym2.getPosition() ? std::pair{expr1, expr2}
803 : std::pair{expr2, expr1};
804
805 auto dim1 = dyn_cast<AffineDimExpr>(Val&: expr1);
806 auto dim2 = dyn_cast<AffineDimExpr>(Val&: expr2);
807 if (dim1 && dim2)
808 return dim1.getPosition() < dim2.getPosition() ? std::pair{expr1, expr2}
809 : std::pair{expr2, expr1};
810
811 // Put dims before symbols.
812 if (dim1 && sym2)
813 return {dim1, sym2};
814
815 if (sym1 && dim2)
816 return {dim2, sym1};
817
818 // Otherwise, keep original order.
819 return {expr1, expr2};
820}
821
822AffineExpr AffineExpr::operator+(int64_t v) const {
823 return *this + getAffineConstantExpr(constant: v, context: getContext());
824}
825AffineExpr AffineExpr::operator+(AffineExpr other) const {
826 if (auto simplified = simplifyAdd(lhs: *this, rhs: other))
827 return simplified;
828
829 auto [lhs, rhs] = orderCommutativeArgs(expr1: *this, expr2: other);
830
831 StorageUniquer &uniquer = getContext()->getAffineUniquer();
832 return uniquer.get<AffineBinaryOpExprStorage>(
833 /*initFn=*/{}, args: static_cast<unsigned>(AffineExprKind::Add), args&: lhs, args&: rhs);
834}
835
836/// Simplify a multiply expression. Return nullptr if it can't be simplified.
837static AffineExpr simplifyMul(AffineExpr lhs, AffineExpr rhs) {
838 auto lhsConst = dyn_cast<AffineConstantExpr>(Val&: lhs);
839 auto rhsConst = dyn_cast<AffineConstantExpr>(Val&: rhs);
840
841 if (lhsConst && rhsConst) {
842 int64_t product;
843 if (llvm::MulOverflow(X: lhsConst.getValue(), Y: rhsConst.getValue(), Result&: product)) {
844 return nullptr;
845 }
846 return getAffineConstantExpr(constant: product, context: lhs.getContext());
847 }
848
849 if (!lhs.isSymbolicOrConstant() && !rhs.isSymbolicOrConstant())
850 return nullptr;
851
852 // Canonicalize the mul expression so that the constant/symbolic term is the
853 // RHS. If both the lhs and rhs are symbolic, swap them if the lhs is a
854 // constant. (Note that a constant is trivially symbolic).
855 if (!rhs.isSymbolicOrConstant() || isa<AffineConstantExpr>(Val: lhs)) {
856 // At least one of them has to be symbolic.
857 return rhs * lhs;
858 }
859
860 // At this point, if there was a constant, it would be on the right.
861
862 // Multiplication with a one is a noop, return the other input.
863 if (rhsConst) {
864 if (rhsConst.getValue() == 1)
865 return lhs;
866 // Multiplication with zero.
867 if (rhsConst.getValue() == 0)
868 return rhsConst;
869 }
870
871 // Fold successive multiplications: eg: (d0 * 2) * 3 into d0 * 6.
872 auto lBin = dyn_cast<AffineBinaryOpExpr>(Val&: lhs);
873 if (lBin && rhsConst && lBin.getKind() == AffineExprKind::Mul) {
874 if (auto lrhs = dyn_cast<AffineConstantExpr>(Val: lBin.getRHS()))
875 return lBin.getLHS() * (lrhs.getValue() * rhsConst.getValue());
876 }
877
878 // When doing successive multiplication, bring constant to the right: turn (d0
879 // * 2) * d1 into (d0 * d1) * 2.
880 if (lBin && lBin.getKind() == AffineExprKind::Mul) {
881 if (auto lrhs = dyn_cast<AffineConstantExpr>(Val: lBin.getRHS())) {
882 return (lBin.getLHS() * rhs) * lrhs;
883 }
884 }
885
886 return nullptr;
887}
888
889AffineExpr AffineExpr::operator*(int64_t v) const {
890 return *this * getAffineConstantExpr(constant: v, context: getContext());
891}
892AffineExpr AffineExpr::operator*(AffineExpr other) const {
893 if (auto simplified = simplifyMul(lhs: *this, rhs: other))
894 return simplified;
895
896 auto [lhs, rhs] = orderCommutativeArgs(expr1: *this, expr2: other);
897
898 StorageUniquer &uniquer = getContext()->getAffineUniquer();
899 return uniquer.get<AffineBinaryOpExprStorage>(
900 /*initFn=*/{}, args: static_cast<unsigned>(AffineExprKind::Mul), args&: lhs, args&: rhs);
901}
902
903// Unary minus, delegate to operator*.
904AffineExpr AffineExpr::operator-() const {
905 return *this * getAffineConstantExpr(constant: -1, context: getContext());
906}
907
908// Delegate to operator+.
909AffineExpr AffineExpr::operator-(int64_t v) const {
910 // Use unsigned negation to avoid signed integer overflow for INT64_MIN.
911 return *this + static_cast<int64_t>(-static_cast<uint64_t>(v));
912}
913AffineExpr AffineExpr::operator-(AffineExpr other) const {
914 if (auto constOther = dyn_cast<AffineConstantExpr>(Val&: other))
915 return *this - constOther.getValue();
916 return *this + (-other);
917}
918
919static AffineExpr simplifyFloorDiv(AffineExpr lhs, AffineExpr rhs) {
920 auto rhsConst = dyn_cast<AffineConstantExpr>(Val&: rhs);
921
922 // For the defined cases, simplify x floordiv x is 1.
923 if (lhs == rhs && (!rhsConst || rhsConst.getValue() >= 1))
924 return getAffineConstantExpr(constant: 1, context: lhs.getContext());
925
926 // All other simplifications further below are for the RHS constant case.
927 if (!rhsConst || rhsConst.getValue() == 0)
928 return nullptr;
929
930 if (auto lhsConst = dyn_cast<AffineConstantExpr>(Val&: lhs)) {
931 if (divideSignedWouldOverflow(Numerator: lhsConst.getValue(), Denominator: rhsConst.getValue()))
932 return nullptr;
933 return getAffineConstantExpr(
934 constant: divideFloorSigned(Numerator: lhsConst.getValue(), Denominator: rhsConst.getValue()),
935 context: lhs.getContext());
936 }
937
938 // Fold floordiv of a multiply with a constant that is a multiple of the
939 // divisor. Eg: (i * 128) floordiv 64 = i * 2.
940 if (rhsConst == 1)
941 return lhs;
942
943 // Simplify `(expr * lrhs) floordiv rhsConst` when `lrhs` is known to be a
944 // multiple of `rhsConst`.
945 auto lBin = dyn_cast<AffineBinaryOpExpr>(Val&: lhs);
946 if (lBin && lBin.getKind() == AffineExprKind::Mul) {
947 if (auto lrhs = dyn_cast<AffineConstantExpr>(Val: lBin.getRHS())) {
948 // `rhsConst` is known to be a nonzero constant.
949 if (lrhs.getValue() % rhsConst.getValue() == 0)
950 return lBin.getLHS() * (lrhs.getValue() / rhsConst.getValue());
951 }
952 }
953
954 // Simplify (expr1 + expr2) floordiv divConst when either expr1 or expr2 is
955 // known to be a multiple of divConst.
956 if (lBin && lBin.getKind() == AffineExprKind::Add) {
957 int64_t llhsDiv = lBin.getLHS().getLargestKnownDivisor();
958 int64_t lrhsDiv = lBin.getRHS().getLargestKnownDivisor();
959 // rhsConst is known to be a nonzero constant.
960 if (llhsDiv % rhsConst.getValue() == 0 ||
961 lrhsDiv % rhsConst.getValue() == 0)
962 return lBin.getLHS().floorDiv(v: rhsConst.getValue()) +
963 lBin.getRHS().floorDiv(v: rhsConst.getValue());
964 }
965
966 return nullptr;
967}
968
969AffineExpr AffineExpr::floorDiv(uint64_t v) const {
970 return floorDiv(other: getAffineConstantExpr(constant: v, context: getContext()));
971}
972AffineExpr AffineExpr::floorDiv(AffineExpr other) const {
973 if (auto simplified = simplifyFloorDiv(lhs: *this, rhs: other))
974 return simplified;
975
976 StorageUniquer &uniquer = getContext()->getAffineUniquer();
977 return uniquer.get<AffineBinaryOpExprStorage>(
978 /*initFn=*/{}, args: static_cast<unsigned>(AffineExprKind::FloorDiv), args: *this,
979 args&: other);
980}
981
982static AffineExpr simplifyCeilDiv(AffineExpr lhs, AffineExpr rhs) {
983 auto rhsConst = dyn_cast<AffineConstantExpr>(Val&: rhs);
984
985 // For the defined cases, simplify x ceildiv x is 1.
986 if (lhs == rhs && (!rhsConst || rhsConst.getValue() >= 1))
987 return getAffineConstantExpr(constant: 1, context: lhs.getContext());
988
989 // All other simplifications further below are for the RHS constant case.
990 if (!rhsConst || rhsConst.getValue() == 0)
991 return nullptr;
992
993 if (auto lhsConst = dyn_cast<AffineConstantExpr>(Val&: lhs)) {
994 if (divideSignedWouldOverflow(Numerator: lhsConst.getValue(), Denominator: rhsConst.getValue()))
995 return nullptr;
996 return getAffineConstantExpr(
997 constant: divideCeilSigned(Numerator: lhsConst.getValue(), Denominator: rhsConst.getValue()),
998 context: lhs.getContext());
999 }
1000
1001 // Fold ceildiv of a multiply with a constant that is a multiple of the
1002 // divisor. Eg: (i * 128) ceildiv 64 = i * 2.
1003 if (rhsConst.getValue() == 1)
1004 return lhs;
1005
1006 // Simplify `(expr * lrhs) ceildiv rhsConst` when `lrhs` is known to be a
1007 // multiple of `rhsConst`.
1008 auto lBin = dyn_cast<AffineBinaryOpExpr>(Val&: lhs);
1009 if (lBin && lBin.getKind() == AffineExprKind::Mul) {
1010 if (auto lrhs = dyn_cast<AffineConstantExpr>(Val: lBin.getRHS())) {
1011 // `rhsConst` is known to be a nonzero constant.
1012 if (lrhs.getValue() % rhsConst.getValue() == 0)
1013 return lBin.getLHS() * (lrhs.getValue() / rhsConst.getValue());
1014 }
1015 }
1016
1017 return nullptr;
1018}
1019
1020AffineExpr AffineExpr::ceilDiv(uint64_t v) const {
1021 return ceilDiv(other: getAffineConstantExpr(constant: v, context: getContext()));
1022}
1023AffineExpr AffineExpr::ceilDiv(AffineExpr other) const {
1024 if (auto simplified = simplifyCeilDiv(lhs: *this, rhs: other))
1025 return simplified;
1026
1027 StorageUniquer &uniquer = getContext()->getAffineUniquer();
1028 return uniquer.get<AffineBinaryOpExprStorage>(
1029 /*initFn=*/{}, args: static_cast<unsigned>(AffineExprKind::CeilDiv), args: *this,
1030 args&: other);
1031}
1032
1033static AffineExpr simplifyMod(AffineExpr lhs, AffineExpr rhs) {
1034 auto rhsConst = dyn_cast<AffineConstantExpr>(Val&: rhs);
1035
1036 // For the defined cases, simplify x % x to 0.
1037 if (lhs == rhs && (!rhsConst || rhsConst.getValue() >= 1))
1038 return getAffineConstantExpr(constant: 0, context: lhs.getContext());
1039
1040 // mod w.r.t zero or negative numbers is undefined and preserved as is.
1041 // All other simplifications further below are for the RHS constant case.
1042 if (!rhsConst || rhsConst.getValue() < 1)
1043 return nullptr;
1044
1045 if (auto lhsConst = dyn_cast<AffineConstantExpr>(Val&: lhs)) {
1046 // mod never overflows.
1047 return getAffineConstantExpr(constant: mod(Numerator: lhsConst.getValue(), Denominator: rhsConst.getValue()),
1048 context: lhs.getContext());
1049 }
1050
1051 // Fold modulo of an expression that is known to be a multiple of a constant
1052 // to zero if that constant is a multiple of the modulo factor. Eg: (i * 128)
1053 // mod 64 is folded to 0, and less trivially, (i*(j*4*(k*32))) mod 128 = 0.
1054 if (lhs.getLargestKnownDivisor() % rhsConst.getValue() == 0)
1055 return getAffineConstantExpr(constant: 0, context: lhs.getContext());
1056
1057 // Simplify (expr1 + expr2) mod divConst when either expr1 or expr2 is
1058 // known to be a multiple of divConst.
1059 auto lBin = dyn_cast<AffineBinaryOpExpr>(Val&: lhs);
1060 if (lBin && lBin.getKind() == AffineExprKind::Add) {
1061 int64_t llhsDiv = lBin.getLHS().getLargestKnownDivisor();
1062 int64_t lrhsDiv = lBin.getRHS().getLargestKnownDivisor();
1063 // rhsConst is known to be a positive constant.
1064 if (llhsDiv % rhsConst.getValue() == 0)
1065 return lBin.getRHS() % rhsConst.getValue();
1066 if (lrhsDiv % rhsConst.getValue() == 0)
1067 return lBin.getLHS() % rhsConst.getValue();
1068 }
1069
1070 // Simplify (e % a) % b to e % b when b evenly divides a
1071 if (lBin && lBin.getKind() == AffineExprKind::Mod) {
1072 auto intermediate = dyn_cast<AffineConstantExpr>(Val: lBin.getRHS());
1073 if (intermediate && intermediate.getValue() >= 1 &&
1074 mod(Numerator: intermediate.getValue(), Denominator: rhsConst.getValue()) == 0) {
1075 return lBin.getLHS() % rhsConst.getValue();
1076 }
1077 }
1078
1079 return nullptr;
1080}
1081
1082AffineExpr AffineExpr::operator%(uint64_t v) const {
1083 return *this % getAffineConstantExpr(constant: v, context: getContext());
1084}
1085AffineExpr AffineExpr::operator%(AffineExpr other) const {
1086 if (auto simplified = simplifyMod(lhs: *this, rhs: other))
1087 return simplified;
1088
1089 StorageUniquer &uniquer = getContext()->getAffineUniquer();
1090 return uniquer.get<AffineBinaryOpExprStorage>(
1091 /*initFn=*/{}, args: static_cast<unsigned>(AffineExprKind::Mod), args: *this, args&: other);
1092}
1093
1094AffineExpr AffineExpr::compose(AffineMap map) const {
1095 SmallVector<AffineExpr, 8> dimReplacements(map.getResults());
1096 return replaceDimsAndSymbols(dimReplacements, symReplacements: {});
1097}
1098raw_ostream &mlir::operator<<(raw_ostream &os, AffineExpr expr) {
1099 expr.print(os);
1100 return os;
1101}
1102
1103/// Constructs an affine expression from a flat ArrayRef. If there are local
1104/// identifiers (neither dimensional nor symbolic) that appear in the sum of
1105/// products expression, `localExprs` is expected to have the AffineExpr
1106/// for it, and is substituted into. The ArrayRef `flatExprs` is expected to be
1107/// in the format [dims, symbols, locals, constant term].
1108AffineExpr mlir::getAffineExprFromFlatForm(ArrayRef<int64_t> flatExprs,
1109 unsigned numDims,
1110 unsigned numSymbols,
1111 ArrayRef<AffineExpr> localExprs,
1112 MLIRContext *context) {
1113 // Assert expected numLocals = flatExprs.size() - numDims - numSymbols - 1.
1114 assert(flatExprs.size() - numDims - numSymbols - 1 == localExprs.size() &&
1115 "unexpected number of local expressions");
1116
1117 auto expr = getAffineConstantExpr(constant: 0, context);
1118 // Dimensions and symbols.
1119 for (unsigned j = 0; j < numDims + numSymbols; j++) {
1120 if (flatExprs[j] == 0)
1121 continue;
1122 auto id = j < numDims ? getAffineDimExpr(position: j, context)
1123 : getAffineSymbolExpr(position: j - numDims, context);
1124 expr = expr + id * flatExprs[j];
1125 }
1126
1127 // Local identifiers.
1128 for (unsigned j = numDims + numSymbols, e = flatExprs.size() - 1; j < e;
1129 j++) {
1130 if (flatExprs[j] == 0)
1131 continue;
1132 auto term = localExprs[j - numDims - numSymbols] * flatExprs[j];
1133 expr = expr + term;
1134 }
1135
1136 // Constant term.
1137 int64_t constTerm = flatExprs[flatExprs.size() - 1];
1138 if (constTerm != 0)
1139 expr = expr + constTerm;
1140 return expr;
1141}
1142
1143/// Constructs a semi-affine expression from a flat ArrayRef. If there are
1144/// local identifiers (neither dimensional nor symbolic) that appear in the sum
1145/// of products expression, `localExprs` is expected to have the AffineExprs for
1146/// it, and is substituted into. The ArrayRef `flatExprs` is expected to be in
1147/// the format [dims, symbols, locals, constant term]. The semi-affine
1148/// expression is constructed in the sorted order of dimension and symbol
1149/// position numbers. Note: local expressions/ids are used for mod, div as well
1150/// as symbolic RHS terms for terms that are not pure affine.
1151static AffineExpr getSemiAffineExprFromFlatForm(ArrayRef<int64_t> flatExprs,
1152 unsigned numDims,
1153 unsigned numSymbols,
1154 ArrayRef<AffineExpr> localExprs,
1155 MLIRContext *context) {
1156 assert(!flatExprs.empty() && "flatExprs cannot be empty");
1157
1158 // Assert expected numLocals = flatExprs.size() - numDims - numSymbols - 1.
1159 assert(flatExprs.size() - numDims - numSymbols - 1 == localExprs.size() &&
1160 "unexpected number of local expressions");
1161
1162 AffineExpr expr = getAffineConstantExpr(constant: 0, context);
1163
1164 // We design indices as a pair which help us present the semi-affine map as
1165 // sum of product where terms are sorted based on dimension or symbol
1166 // position: <keyA, keyB> for expressions of the form dimension * symbol,
1167 // where keyA is the position number of the dimension and keyB is the
1168 // position number of the symbol. For dimensional expressions we set the index
1169 // as (position number of the dimension, -1), as we want dimensional
1170 // expressions to appear before symbolic and product of dimensional and
1171 // symbolic expressions having the dimension with the same position number.
1172 // For symbolic expression set the index as (position number of the symbol,
1173 // maximum of last dimension and symbol position) number. For example, we want
1174 // the expression we are constructing to look something like: d0 + d0 * s0 +
1175 // s0 + d1*s1 + s1.
1176
1177 // Stores the affine expression corresponding to a given index.
1178 DenseMap<std::pair<unsigned, signed>, AffineExpr> indexToExprMap;
1179 // Stores the constant coefficient value corresponding to a given
1180 // dimension, symbol or a non-pure affine expression stored in `localExprs`.
1181 DenseMap<std::pair<unsigned, signed>, int64_t> coefficients;
1182 // Stores the indices as defined above, and later sorted to produce
1183 // the semi-affine expression in the desired form.
1184 SmallVector<std::pair<unsigned, signed>, 8> indices;
1185
1186 // Example: expression = d0 + d0 * s0 + 2 * s0.
1187 // indices = [{0,-1}, {0, 0}, {0, 1}]
1188 // coefficients = [{{0, -1}, 1}, {{0, 0}, 1}, {{0, 1}, 2}]
1189 // indexToExprMap = [{{0, -1}, d0}, {{0, 0}, d0 * s0}, {{0, 1}, s0}]
1190
1191 // Adds entries to `indexToExprMap`, `coefficients` and `indices`.
1192 auto addEntry = [&](std::pair<unsigned, signed> index, int64_t coefficient,
1193 AffineExpr expr) {
1194 assert(!llvm::is_contained(indices, index) &&
1195 "Key is already present in indices vector and overwriting will "
1196 "happen in `indexToExprMap` and `coefficients`!");
1197
1198 indices.push_back(Elt: index);
1199 coefficients.insert(KV: {index, coefficient});
1200 indexToExprMap.insert(KV: {index, expr});
1201 };
1202
1203 // Design indices for dimensional or symbolic terms, and store the indices,
1204 // constant coefficient corresponding to the indices in `coefficients` map,
1205 // and affine expression corresponding to indices in `indexToExprMap` map.
1206
1207 // Ensure we do not have duplicate keys in `indexToExpr` map.
1208 unsigned offsetSym = 0;
1209 signed offsetDim = -1;
1210 for (unsigned j = numDims; j < numDims + numSymbols; ++j) {
1211 if (flatExprs[j] == 0)
1212 continue;
1213 // For symbolic expression set the index as <position number
1214 // of the symbol, max(dimCount, symCount)> number,
1215 // as we want symbolic expressions with the same positional number to
1216 // appear after dimensional expressions having the same positional number.
1217 std::pair<unsigned, signed> indexEntry(
1218 j - numDims, std::max(a: numDims, b: numSymbols) + offsetSym++);
1219 addEntry(indexEntry, flatExprs[j],
1220 getAffineSymbolExpr(position: j - numDims, context));
1221 }
1222
1223 // Denotes semi-affine product, modulo or division terms, which has been added
1224 // to the `indexToExpr` map.
1225 SmallVector<bool, 4> addedToMap(flatExprs.size() - numDims - numSymbols - 1,
1226 false);
1227 unsigned lhsPos, rhsPos;
1228 // Construct indices for product terms involving dimension, symbol or constant
1229 // as lhs/rhs, and store the indices, constant coefficient corresponding to
1230 // the indices in `coefficients` map, and affine expression corresponding to
1231 // in indices in `indexToExprMap` map.
1232 for (const auto &it : llvm::enumerate(First&: localExprs)) {
1233 if (flatExprs[numDims + numSymbols + it.index()] == 0)
1234 continue;
1235 AffineExpr expr = it.value();
1236 auto binaryExpr = dyn_cast<AffineBinaryOpExpr>(Val&: expr);
1237 if (!binaryExpr)
1238 continue;
1239
1240 AffineExpr lhs = binaryExpr.getLHS();
1241 AffineExpr rhs = binaryExpr.getRHS();
1242 if (!((isa<AffineDimExpr>(Val: lhs) || isa<AffineSymbolExpr>(Val: lhs)) &&
1243 (isa<AffineDimExpr>(Val: rhs) || isa<AffineSymbolExpr>(Val: rhs) ||
1244 isa<AffineConstantExpr>(Val: rhs)))) {
1245 continue;
1246 }
1247 if (isa<AffineConstantExpr>(Val: rhs)) {
1248 // For product/modulo/division expressions, when rhs of modulo/division
1249 // expression is constant, we put 0 in place of keyB, because we want
1250 // them to appear earlier in the semi-affine expression we are
1251 // constructing. When rhs is constant, we place 0 in place of keyB.
1252 if (isa<AffineDimExpr>(Val: lhs)) {
1253 lhsPos = cast<AffineDimExpr>(Val&: lhs).getPosition();
1254 std::pair<unsigned, signed> indexEntry(lhsPos, offsetDim--);
1255 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()],
1256 expr);
1257 } else {
1258 lhsPos = cast<AffineSymbolExpr>(Val&: lhs).getPosition();
1259 std::pair<unsigned, signed> indexEntry(
1260 lhsPos, std::max(a: numDims, b: numSymbols) + offsetSym++);
1261 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()],
1262 expr);
1263 }
1264 } else if (isa<AffineDimExpr>(Val: lhs)) {
1265 // For product/modulo/division expressions having lhs as dimension and rhs
1266 // as symbol, we order the terms in the semi-affine expression based on
1267 // the pair: <keyA, keyB> for expressions of the form dimension * symbol,
1268 // where keyA is the position number of the dimension and keyB is the
1269 // position number of the symbol.
1270 lhsPos = cast<AffineDimExpr>(Val&: lhs).getPosition();
1271 rhsPos = cast<AffineSymbolExpr>(Val&: rhs).getPosition();
1272 std::pair<unsigned, signed> indexEntry(lhsPos, rhsPos);
1273 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()], expr);
1274 } else {
1275 // For product/modulo/division expressions having both lhs and rhs as
1276 // symbol, we design indices as a pair: <keyA, keyB> for expressions
1277 // of the form dimension * symbol, where keyA is the position number of
1278 // the dimension and keyB is the position number of the symbol.
1279 lhsPos = cast<AffineSymbolExpr>(Val&: lhs).getPosition();
1280 rhsPos = cast<AffineSymbolExpr>(Val&: rhs).getPosition();
1281 std::pair<unsigned, signed> indexEntry(
1282 lhsPos, std::max(a: numDims, b: numSymbols) + offsetSym++);
1283 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()], expr);
1284 }
1285 addedToMap[it.index()] = true;
1286 }
1287
1288 for (unsigned j = 0; j < numDims; ++j) {
1289 if (flatExprs[j] == 0)
1290 continue;
1291 // For dimensional expressions we set the index as <position number of the
1292 // dimension, 0>, as we want dimensional expressions to appear before
1293 // symbolic ones and products of dimensional and symbolic expressions
1294 // having the dimension with the same position number.
1295 std::pair<unsigned, signed> indexEntry(j, offsetDim--);
1296 addEntry(indexEntry, flatExprs[j], getAffineDimExpr(position: j, context));
1297 }
1298
1299 // Constructing the simplified semi-affine sum of product/division/mod
1300 // expression from the flattened form in the desired sorted order of indices
1301 // of the various individual product/division/mod expressions.
1302 llvm::sort(C&: indices);
1303 for (const std::pair<unsigned, unsigned> index : indices) {
1304 assert(indexToExprMap.lookup(index) &&
1305 "cannot find key in `indexToExprMap` map");
1306 expr = expr + indexToExprMap.lookup(Val: index) * coefficients.lookup(Val: index);
1307 }
1308
1309 // Local identifiers.
1310 for (unsigned j = numDims + numSymbols, e = flatExprs.size() - 1; j < e;
1311 j++) {
1312 // If the coefficient of the local expression is 0, continue as we need not
1313 // add it in out final expression.
1314 if (flatExprs[j] == 0 || addedToMap[j - numDims - numSymbols])
1315 continue;
1316 auto term = localExprs[j - numDims - numSymbols] * flatExprs[j];
1317 expr = expr + term;
1318 }
1319
1320 // Constant term.
1321 int64_t constTerm = flatExprs.back();
1322 if (constTerm != 0)
1323 expr = expr + constTerm;
1324 return expr;
1325}
1326
1327SimpleAffineExprFlattener::SimpleAffineExprFlattener(unsigned numDims,
1328 unsigned numSymbols)
1329 : numDims(numDims), numSymbols(numSymbols), numLocals(0) {
1330 operandExprStack.reserve(n: 8);
1331}
1332
1333// In pure affine t = expr * c, we multiply each coefficient of lhs with c.
1334//
1335// In case of semi affine multiplication expressions, t = expr * symbolic_expr,
1336// introduce a local variable p (= expr * symbolic_expr), and the affine
1337// expression expr * symbolic_expr is added to `localExprs`.
1338LogicalResult SimpleAffineExprFlattener::visitMulExpr(AffineBinaryOpExpr expr) {
1339 assert(operandExprStack.size() >= 2);
1340 SmallVector<int64_t, 8> rhs = operandExprStack.back();
1341 operandExprStack.pop_back();
1342 SmallVector<int64_t, 8> &lhs = operandExprStack.back();
1343
1344 // Flatten semi-affine multiplication expressions by introducing a local
1345 // variable in place of the product; the affine expression
1346 // corresponding to the quantifier is added to `localExprs`.
1347 if (!isa<AffineConstantExpr>(Val: expr.getRHS())) {
1348 SmallVector<int64_t, 8> mulLhs(lhs);
1349 MLIRContext *context = expr.getContext();
1350 AffineExpr a = getAffineExprFromFlatForm(flatExprs: lhs, numDims, numSymbols,
1351 localExprs, context);
1352 AffineExpr b = getAffineExprFromFlatForm(flatExprs: rhs, numDims, numSymbols,
1353 localExprs, context);
1354 return addLocalVariableSemiAffine(lhs: mulLhs, rhs, localExpr: a * b, result&: lhs, resultSize: lhs.size());
1355 }
1356
1357 // Get the RHS constant.
1358 int64_t rhsConst = rhs[getConstantIndex()];
1359 for (int64_t &lhsElt : lhs) {
1360 auto [prod, overflow] = llvm::MulOverflow(X: lhsElt, Y: rhsConst);
1361 if (overflow)
1362 return failure();
1363 lhsElt = prod;
1364 }
1365
1366 return success();
1367}
1368
1369LogicalResult SimpleAffineExprFlattener::visitAddExpr(AffineBinaryOpExpr expr) {
1370 assert(operandExprStack.size() >= 2);
1371 const auto &rhs = operandExprStack.back();
1372 auto &lhs = operandExprStack[operandExprStack.size() - 2];
1373 assert(lhs.size() == rhs.size());
1374 // Update the LHS in place.
1375 for (unsigned i = 0, e = rhs.size(); i < e; i++) {
1376 auto [sum, overflow] = llvm::AddOverflow(X: lhs[i], Y: rhs[i]);
1377 if (overflow)
1378 return failure();
1379 lhs[i] = sum;
1380 }
1381 // Pop off the RHS.
1382 operandExprStack.pop_back();
1383 return success();
1384}
1385
1386//
1387// t = expr mod c <=> t = expr - c*q and c*q <= expr <= c*q + c - 1
1388//
1389// A mod expression "expr mod c" is thus flattened by introducing a new local
1390// variable q (= expr floordiv c), such that expr mod c is replaced with
1391// 'expr - c * q' and c * q <= expr <= c * q + c - 1 are added to localVarCst.
1392//
1393// In case of semi-affine modulo expressions, t = expr mod symbolic_expr,
1394// introduce a local variable m (= expr mod symbolic_expr), and the affine
1395// expression expr mod symbolic_expr is added to `localExprs`.
1396LogicalResult SimpleAffineExprFlattener::visitModExpr(AffineBinaryOpExpr expr) {
1397 assert(operandExprStack.size() >= 2);
1398
1399 SmallVector<int64_t, 8> rhs = operandExprStack.back();
1400 operandExprStack.pop_back();
1401 SmallVector<int64_t, 8> &lhs = operandExprStack.back();
1402 MLIRContext *context = expr.getContext();
1403
1404 // Flatten semi affine modulo expressions by introducing a local
1405 // variable in place of the modulo value, and the affine expression
1406 // corresponding to the quantifier is added to `localExprs`.
1407 if (!isa<AffineConstantExpr>(Val: expr.getRHS())) {
1408 SmallVector<int64_t, 8> modLhs(lhs);
1409 AffineExpr dividendExpr = getAffineExprFromFlatForm(
1410 flatExprs: lhs, numDims, numSymbols, localExprs, context);
1411 AffineExpr divisorExpr = getAffineExprFromFlatForm(flatExprs: rhs, numDims, numSymbols,
1412 localExprs, context);
1413 AffineExpr modExpr = dividendExpr % divisorExpr;
1414 return addLocalVariableSemiAffine(lhs: modLhs, rhs, localExpr: modExpr, result&: lhs, resultSize: lhs.size());
1415 }
1416
1417 int64_t rhsConst = rhs[getConstantIndex()];
1418 if (rhsConst <= 0)
1419 return failure();
1420
1421 // Check if the LHS expression is a multiple of modulo factor.
1422 unsigned i, e;
1423 for (i = 0, e = lhs.size(); i < e; i++)
1424 if (lhs[i] % rhsConst != 0)
1425 break;
1426 // If yes, modulo expression here simplifies to zero.
1427 if (i == lhs.size()) {
1428 llvm::fill(Range&: lhs, Value: 0);
1429 return success();
1430 }
1431
1432 // Add a local variable for the quotient, i.e., expr % c is replaced by
1433 // (expr - q * c) where q = expr floordiv c. Do this while canceling out
1434 // the GCD of expr and c.
1435 SmallVector<int64_t, 8> floorDividend(lhs);
1436 uint64_t gcd = rhsConst;
1437 for (int64_t lhsElt : lhs)
1438 gcd = std::gcd(m: gcd, n: (uint64_t)std::abs(i: lhsElt));
1439 // Simplify the numerator and the denominator.
1440 if (gcd != 1) {
1441 for (int64_t &floorDividendElt : floorDividend)
1442 floorDividendElt = floorDividendElt / static_cast<int64_t>(gcd);
1443 }
1444 int64_t floorDivisor = rhsConst / static_cast<int64_t>(gcd);
1445
1446 // Construct the AffineExpr form of the floordiv to store in localExprs.
1447
1448 AffineExpr dividendExpr = getAffineExprFromFlatForm(
1449 flatExprs: floorDividend, numDims, numSymbols, localExprs, context);
1450 AffineExpr divisorExpr = getAffineConstantExpr(constant: floorDivisor, context);
1451 AffineExpr floorDivExpr = dividendExpr.floorDiv(other: divisorExpr);
1452 int loc;
1453 if ((loc = findLocalId(localExpr: floorDivExpr)) == -1) {
1454 addLocalFloorDivId(dividend: floorDividend, divisor: floorDivisor, localExpr: floorDivExpr);
1455 // Set result at top of stack to "lhs - rhsConst * q".
1456 lhs[getLocalVarStartIndex() + numLocals - 1] = -rhsConst;
1457 } else {
1458 // Reuse the existing local id.
1459 lhs[getLocalVarStartIndex() + loc] -= rhsConst;
1460 }
1461 return success();
1462}
1463
1464LogicalResult
1465SimpleAffineExprFlattener::visitCeilDivExpr(AffineBinaryOpExpr expr) {
1466 return visitDivExpr(expr, /*isCeil=*/true);
1467}
1468LogicalResult
1469SimpleAffineExprFlattener::visitFloorDivExpr(AffineBinaryOpExpr expr) {
1470 return visitDivExpr(expr, /*isCeil=*/false);
1471}
1472
1473LogicalResult SimpleAffineExprFlattener::visitDimExpr(AffineDimExpr expr) {
1474 operandExprStack.emplace_back(args: SmallVector<int64_t, 32>(getNumCols(), 0));
1475 auto &eq = operandExprStack.back();
1476 assert(expr.getPosition() < numDims && "Inconsistent number of dims");
1477 eq[getDimStartIndex() + expr.getPosition()] = 1;
1478 return success();
1479}
1480
1481LogicalResult
1482SimpleAffineExprFlattener::visitSymbolExpr(AffineSymbolExpr expr) {
1483 operandExprStack.emplace_back(args: SmallVector<int64_t, 32>(getNumCols(), 0));
1484 auto &eq = operandExprStack.back();
1485 assert(expr.getPosition() < numSymbols && "inconsistent number of symbols");
1486 eq[getSymbolStartIndex() + expr.getPosition()] = 1;
1487 return success();
1488}
1489
1490LogicalResult
1491SimpleAffineExprFlattener::visitConstantExpr(AffineConstantExpr expr) {
1492 operandExprStack.emplace_back(args: SmallVector<int64_t, 32>(getNumCols(), 0));
1493 auto &eq = operandExprStack.back();
1494 eq[getConstantIndex()] = expr.getValue();
1495 return success();
1496}
1497
1498LogicalResult SimpleAffineExprFlattener::addLocalVariableSemiAffine(
1499 ArrayRef<int64_t> lhs, ArrayRef<int64_t> rhs, AffineExpr localExpr,
1500 SmallVectorImpl<int64_t> &result, unsigned long resultSize) {
1501 assert(result.size() == resultSize &&
1502 "`result` vector passed is not of correct size");
1503 int loc;
1504 if ((loc = findLocalId(localExpr)) == -1) {
1505 if (failed(Result: addLocalIdSemiAffine(lhs, rhs, localExpr)))
1506 return failure();
1507 }
1508 llvm::fill(Range&: result, Value: 0);
1509 if (loc == -1)
1510 result[getLocalVarStartIndex() + numLocals - 1] = 1;
1511 else
1512 result[getLocalVarStartIndex() + loc] = 1;
1513 return success();
1514}
1515
1516// t = expr floordiv c <=> t = q, c * q <= expr <= c * q + c - 1
1517// A floordiv is thus flattened by introducing a new local variable q, and
1518// replacing that expression with 'q' while adding the constraints
1519// c * q <= expr <= c * q + c - 1 to localVarCst (done by
1520// IntegerRelation::addLocalFloorDiv).
1521//
1522// A ceildiv is similarly flattened:
1523// t = expr ceildiv c <=> t = (expr + c - 1) floordiv c
1524//
1525// In case of semi affine division expressions, t = expr floordiv symbolic_expr
1526// or t = expr ceildiv symbolic_expr, introduce a local variable q (= expr
1527// floordiv/ceildiv symbolic_expr), and the affine floordiv/ceildiv is added to
1528// `localExprs`.
1529LogicalResult SimpleAffineExprFlattener::visitDivExpr(AffineBinaryOpExpr expr,
1530 bool isCeil) {
1531 assert(operandExprStack.size() >= 2);
1532
1533 MLIRContext *context = expr.getContext();
1534 SmallVector<int64_t, 8> rhs = operandExprStack.back();
1535 operandExprStack.pop_back();
1536 SmallVector<int64_t, 8> &lhs = operandExprStack.back();
1537
1538 // Flatten semi affine division expressions by introducing a local
1539 // variable in place of the quotient, and the affine expression corresponding
1540 // to the quantifier is added to `localExprs`.
1541 if (!isa<AffineConstantExpr>(Val: expr.getRHS())) {
1542 SmallVector<int64_t, 8> divLhs(lhs);
1543 AffineExpr a = getAffineExprFromFlatForm(flatExprs: lhs, numDims, numSymbols,
1544 localExprs, context);
1545 AffineExpr b = getAffineExprFromFlatForm(flatExprs: rhs, numDims, numSymbols,
1546 localExprs, context);
1547 AffineExpr divExpr = isCeil ? a.ceilDiv(other: b) : a.floorDiv(other: b);
1548 return addLocalVariableSemiAffine(lhs: divLhs, rhs, localExpr: divExpr, result&: lhs, resultSize: lhs.size());
1549 }
1550
1551 // This is a pure affine expr; the RHS is a positive constant.
1552 int64_t rhsConst = rhs[getConstantIndex()];
1553 if (rhsConst <= 0)
1554 return failure();
1555
1556 // Simplify the floordiv, ceildiv if possible by canceling out the greatest
1557 // common divisors of the numerator and denominator.
1558 uint64_t gcd = std::abs(i: rhsConst);
1559 for (int64_t lhsElt : lhs)
1560 gcd = std::gcd(m: gcd, n: (uint64_t)std::abs(i: lhsElt));
1561 // Simplify the numerator and the denominator.
1562 if (gcd != 1) {
1563 for (int64_t &lhsElt : lhs)
1564 lhsElt = lhsElt / static_cast<int64_t>(gcd);
1565 }
1566 int64_t divisor = rhsConst / static_cast<int64_t>(gcd);
1567 // If the divisor becomes 1, the updated LHS is the result. (The
1568 // divisor can't be negative since rhsConst is positive).
1569 if (divisor == 1)
1570 return success();
1571
1572 // If the divisor cannot be simplified to one, we will have to retain
1573 // the ceil/floor expr (simplified up until here). Add an existential
1574 // quantifier to express its result, i.e., expr1 div expr2 is replaced
1575 // by a new identifier, q.
1576 AffineExpr a =
1577 getAffineExprFromFlatForm(flatExprs: lhs, numDims, numSymbols, localExprs, context);
1578 AffineExpr b = getAffineConstantExpr(constant: divisor, context);
1579
1580 int loc;
1581 AffineExpr divExpr = isCeil ? a.ceilDiv(other: b) : a.floorDiv(other: b);
1582 if ((loc = findLocalId(localExpr: divExpr)) == -1) {
1583 if (!isCeil) {
1584 SmallVector<int64_t, 8> dividend(lhs);
1585 addLocalFloorDivId(dividend, divisor, localExpr: divExpr);
1586 } else {
1587 // lhs ceildiv c <=> (lhs + c - 1) floordiv c
1588 SmallVector<int64_t, 8> dividend(lhs);
1589 dividend.back() += divisor - 1;
1590 addLocalFloorDivId(dividend, divisor, localExpr: divExpr);
1591 }
1592 }
1593 // Set the expression on stack to the local var introduced to capture the
1594 // result of the division (floor or ceil).
1595 llvm::fill(Range&: lhs, Value: 0);
1596 if (loc == -1)
1597 lhs[getLocalVarStartIndex() + numLocals - 1] = 1;
1598 else
1599 lhs[getLocalVarStartIndex() + loc] = 1;
1600 return success();
1601}
1602
1603// Add a local identifier (needed to flatten a mod, floordiv, ceildiv expr).
1604// The local identifier added is always a floordiv of a pure add/mul affine
1605// function of other identifiers, coefficients of which are specified in
1606// dividend and with respect to a positive constant divisor. localExpr is the
1607// simplified tree expression (AffineExpr) corresponding to the quantifier.
1608void SimpleAffineExprFlattener::addLocalFloorDivId(ArrayRef<int64_t> dividend,
1609 int64_t divisor,
1610 AffineExpr localExpr) {
1611 assert(divisor > 0 && "positive constant divisor expected");
1612 for (SmallVector<int64_t, 8> &subExpr : operandExprStack)
1613 subExpr.insert(I: subExpr.begin() + getLocalVarStartIndex() + numLocals, Elt: 0);
1614 localExprs.push_back(Elt: localExpr);
1615 numLocals++;
1616 // dividend and divisor are not used here; an override of this method uses it.
1617}
1618
1619LogicalResult SimpleAffineExprFlattener::addLocalIdSemiAffine(
1620 ArrayRef<int64_t> lhs, ArrayRef<int64_t> rhs, AffineExpr localExpr) {
1621 for (SmallVector<int64_t, 8> &subExpr : operandExprStack)
1622 subExpr.insert(I: subExpr.begin() + getLocalVarStartIndex() + numLocals, Elt: 0);
1623 localExprs.push_back(Elt: localExpr);
1624 ++numLocals;
1625 // lhs and rhs are not used here; an override of this method uses them.
1626 return success();
1627}
1628
1629int SimpleAffineExprFlattener::findLocalId(AffineExpr localExpr) {
1630 SmallVectorImpl<AffineExpr>::iterator it;
1631 if ((it = llvm::find(Range&: localExprs, Val: localExpr)) == localExprs.end())
1632 return -1;
1633 return it - localExprs.begin();
1634}
1635
1636/// Simplify the affine expression by flattening it and reconstructing it.
1637AffineExpr mlir::simplifyAffineExpr(AffineExpr expr, unsigned numDims,
1638 unsigned numSymbols) {
1639 // Simplify semi-affine expressions separately.
1640 if (!expr.isPureAffine())
1641 expr = simplifySemiAffine(expr, numDims, numSymbols);
1642
1643 SimpleAffineExprFlattener flattener(numDims, numSymbols);
1644 // has poison expression
1645 if (failed(Result: flattener.walkPostOrder(expr)))
1646 return expr;
1647 ArrayRef<int64_t> flattenedExpr = flattener.operandExprStack.back();
1648 if (!expr.isPureAffine() &&
1649 expr == getAffineExprFromFlatForm(flatExprs: flattenedExpr, numDims, numSymbols,
1650 localExprs: flattener.localExprs,
1651 context: expr.getContext()))
1652 return expr;
1653 AffineExpr simplifiedExpr =
1654 expr.isPureAffine()
1655 ? getAffineExprFromFlatForm(flatExprs: flattenedExpr, numDims, numSymbols,
1656 localExprs: flattener.localExprs, context: expr.getContext())
1657 : getSemiAffineExprFromFlatForm(flatExprs: flattenedExpr, numDims, numSymbols,
1658 localExprs: flattener.localExprs,
1659 context: expr.getContext());
1660
1661 flattener.operandExprStack.pop_back();
1662 assert(flattener.operandExprStack.empty());
1663 return simplifiedExpr;
1664}
1665
1666std::optional<int64_t> mlir::getBoundForAffineExpr(
1667 AffineExpr expr, unsigned numDims, unsigned numSymbols,
1668 ArrayRef<std::optional<int64_t>> constLowerBounds,
1669 ArrayRef<std::optional<int64_t>> constUpperBounds, bool isUpper) {
1670 // Handle divs and mods.
1671 if (auto binOpExpr = dyn_cast<AffineBinaryOpExpr>(Val&: expr)) {
1672 // If the LHS of a floor or ceil is bounded and the RHS is a constant, we
1673 // can compute an upper bound.
1674 if (binOpExpr.getKind() == AffineExprKind::FloorDiv) {
1675 auto rhsConst = dyn_cast<AffineConstantExpr>(Val: binOpExpr.getRHS());
1676 if (!rhsConst || rhsConst.getValue() < 1)
1677 return std::nullopt;
1678 auto bound =
1679 getBoundForAffineExpr(expr: binOpExpr.getLHS(), numDims, numSymbols,
1680 constLowerBounds, constUpperBounds, isUpper);
1681 if (!bound)
1682 return std::nullopt;
1683 return divideFloorSigned(Numerator: *bound, Denominator: rhsConst.getValue());
1684 }
1685 if (binOpExpr.getKind() == AffineExprKind::CeilDiv) {
1686 auto rhsConst = dyn_cast<AffineConstantExpr>(Val: binOpExpr.getRHS());
1687 if (rhsConst && rhsConst.getValue() >= 1) {
1688 auto bound =
1689 getBoundForAffineExpr(expr: binOpExpr.getLHS(), numDims, numSymbols,
1690 constLowerBounds, constUpperBounds, isUpper);
1691 if (!bound)
1692 return std::nullopt;
1693 return divideCeilSigned(Numerator: *bound, Denominator: rhsConst.getValue());
1694 }
1695 return std::nullopt;
1696 }
1697 if (binOpExpr.getKind() == AffineExprKind::Mod) {
1698 // lhs mod c is always <= c - 1 and non-negative. In addition, if `lhs` is
1699 // bounded such that lb <= lhs <= ub and lb floordiv c == ub floordiv c
1700 // (same "interval"), then lb mod c <= lhs mod c <= ub mod c.
1701 auto rhsConst = dyn_cast<AffineConstantExpr>(Val: binOpExpr.getRHS());
1702 if (rhsConst && rhsConst.getValue() >= 1) {
1703 int64_t rhsConstVal = rhsConst.getValue();
1704 auto lb = getBoundForAffineExpr(expr: binOpExpr.getLHS(), numDims, numSymbols,
1705 constLowerBounds, constUpperBounds,
1706 /*isUpper=*/false);
1707 auto ub =
1708 getBoundForAffineExpr(expr: binOpExpr.getLHS(), numDims, numSymbols,
1709 constLowerBounds, constUpperBounds, isUpper);
1710 if (ub && lb &&
1711 divideFloorSigned(Numerator: *lb, Denominator: rhsConstVal) ==
1712 divideFloorSigned(Numerator: *ub, Denominator: rhsConstVal))
1713 return isUpper ? mod(Numerator: *ub, Denominator: rhsConstVal) : mod(Numerator: *lb, Denominator: rhsConstVal);
1714 return isUpper ? rhsConstVal - 1 : 0;
1715 }
1716 }
1717 }
1718 // Flatten the expression.
1719 SimpleAffineExprFlattener flattener(numDims, numSymbols);
1720 auto simpleResult = flattener.walkPostOrder(expr);
1721 // has poison expression
1722 if (failed(Result: simpleResult))
1723 return std::nullopt;
1724 ArrayRef<int64_t> flattenedExpr = flattener.operandExprStack.back();
1725 // TODO: Handle local variables. We can get hold of flattener.localExprs and
1726 // get bound on the local expr recursively.
1727 if (flattener.numLocals > 0)
1728 return std::nullopt;
1729 int64_t bound = 0;
1730 // Substitute the constant lower or upper bound for the dimensional or
1731 // symbolic input depending on `isUpper` to determine the bound.
1732 for (unsigned i = 0, e = numDims + numSymbols; i < e; ++i) {
1733 if (flattenedExpr[i] > 0) {
1734 auto &constBound = isUpper ? constUpperBounds[i] : constLowerBounds[i];
1735 if (!constBound)
1736 return std::nullopt;
1737 bound += *constBound * flattenedExpr[i];
1738 } else if (flattenedExpr[i] < 0) {
1739 auto &constBound = isUpper ? constLowerBounds[i] : constUpperBounds[i];
1740 if (!constBound)
1741 return std::nullopt;
1742 bound += *constBound * flattenedExpr[i];
1743 }
1744 }
1745 // Constant term.
1746 bound += flattenedExpr.back();
1747 return bound;
1748}
1749