1//===- FlatLinearValueConstraints.cpp - Linear Constraint -----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "mlir/Analysis//FlatLinearValueConstraints.h"
10
11#include "mlir/Analysis/Presburger/PWMAFunction.h"
12#include "mlir/Analysis/Presburger/PresburgerSpace.h"
13#include "mlir/Analysis/Presburger/Utils.h"
14#include "mlir/IR/AffineExprVisitor.h"
15#include "mlir/IR/Builders.h"
16#include "mlir/IR/IntegerSet.h"
17#include "mlir/Support/LLVM.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/InterleavedRange.h"
22#include "llvm/Support/raw_ostream.h"
23#include <optional>
24
25#define DEBUG_TYPE "flat-value-constraints"
26
27using namespace mlir;
28using namespace presburger;
29
30//===----------------------------------------------------------------------===//
31// AffineExprFlattener
32//===----------------------------------------------------------------------===//
33
34namespace {
35
36// See comments for SimpleAffineExprFlattener.
37// An AffineExprFlattenerWithLocalVars extends a SimpleAffineExprFlattener by
38// recording constraint information associated with mod's, floordiv's, and
39// ceildiv's in FlatLinearConstraints 'localVarCst'.
40struct AffineExprFlattener : public SimpleAffineExprFlattener {
41 using SimpleAffineExprFlattener::SimpleAffineExprFlattener;
42
43 // Constraints connecting newly introduced local variables (for mod's and
44 // div's) to existing (dimensional and symbolic) ones. These are always
45 // inequalities.
46 IntegerPolyhedron localVarCst;
47
48 AffineExprFlattener(unsigned nDims, unsigned nSymbols)
49 : SimpleAffineExprFlattener(nDims, nSymbols),
50 localVarCst(PresburgerSpace::getSetSpace(numDims: nDims, numSymbols: nSymbols)) {};
51
52private:
53 // Add a local variable (needed to flatten a mod, floordiv, ceildiv expr).
54 // The local variable added is always a floordiv of a pure add/mul affine
55 // function of other variables, coefficients of which are specified in
56 // `dividend' and with respect to the positive constant `divisor'. localExpr
57 // is the simplified tree expression (AffineExpr) corresponding to the
58 // quantifier.
59 void addLocalFloorDivId(ArrayRef<int64_t> dividend, int64_t divisor,
60 AffineExpr localExpr) override {
61 SimpleAffineExprFlattener::addLocalFloorDivId(dividend, divisor, localExpr);
62 // Update localVarCst.
63 (void)localVarCst.addLocalFloorDiv(dividend, divisor);
64 }
65
66 LogicalResult addLocalIdSemiAffine(ArrayRef<int64_t> lhs,
67 ArrayRef<int64_t> rhs,
68 AffineExpr localExpr) override {
69 // AffineExprFlattener does not support semi-affine expressions.
70 return failure();
71 }
72};
73
74// A SemiAffineExprFlattener is an AffineExprFlattenerWithLocalVars that adds
75// conservative bounds for semi-affine expressions (given assumptions hold). If
76// the assumptions required to add the semi-affine bounds are found not to hold
77// the final constraints set will be empty/inconsistent. If the assumptions are
78// never contradicted the final bounds still only will be correct if the
79// assumptions hold.
80struct SemiAffineExprFlattener : public AffineExprFlattener {
81 using AffineExprFlattener::AffineExprFlattener;
82
83 LogicalResult addLocalIdSemiAffine(ArrayRef<int64_t> lhs,
84 ArrayRef<int64_t> rhs,
85 AffineExpr localExpr) override {
86 auto result =
87 SimpleAffineExprFlattener::addLocalIdSemiAffine(lhs, rhs, localExpr);
88 assert(succeeded(result) &&
89 "unexpected failure in SimpleAffineExprFlattener");
90 (void)result;
91
92 if (localExpr.getKind() == AffineExprKind::Mod) {
93 // Given two numbers a and b, division is defined as:
94 //
95 // a = bq + r
96 // 0 <= r < |b| (where |x| is the absolute value of x)
97 //
98 // q = a floordiv b
99 // r = a mod b
100
101 // Add a new local variable (r) to represent the mod.
102 unsigned rPos = localVarCst.appendVar(kind: VarKind::Local);
103
104 // r >= 0 (Can ALWAYS be added)
105 localVarCst.addBound(type: BoundType::LB, pos: rPos, value: 0);
106
107 // r < b (Can be added if b > 0, which we assume here)
108 ArrayRef<int64_t> b = rhs;
109 SmallVector<int64_t> bSubR(b);
110 bSubR.insert(I: bSubR.begin() + rPos, Elt: -1);
111 // Note: bSubR = b - r
112 // So this adds the bound b - r >= 1 (equivalent to r < b)
113 localVarCst.addBound(type: BoundType::LB, expr: bSubR, value: 1);
114
115 // Note: The assumption of b > 0 is based on the affine expression docs,
116 // which state "RHS of mod is always a constant or a symbolic expression
117 // with a positive value." (see AffineExprKind in AffineExpr.h). If this
118 // assumption does not hold constraints (added above) are a contradiction.
119
120 return success();
121 }
122
123 // TODO: Support other semi-affine expressions.
124 return failure();
125 }
126};
127
128} // namespace
129
130// Flattens the expressions in map. Returns failure if 'expr' was unable to be
131// flattened. For example two specific cases:
132// 1. an unhandled semi-affine expressions is found.
133// 2. has poison expression (i.e., division by zero).
134static LogicalResult
135getFlattenedAffineExprs(ArrayRef<AffineExpr> exprs, unsigned numDims,
136 unsigned numSymbols,
137 std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
138 FlatLinearConstraints *localVarCst,
139 bool addConservativeSemiAffineBounds = false) {
140 if (exprs.empty()) {
141 if (localVarCst)
142 *localVarCst = FlatLinearConstraints(numDims, numSymbols);
143 return success();
144 }
145
146 auto flattenExprs = [&](AffineExprFlattener &flattener) -> LogicalResult {
147 // Use the same flattener to simplify each expression successively. This way
148 // local variables / expressions are shared.
149 for (auto expr : exprs) {
150 auto flattenResult = flattener.walkPostOrder(expr);
151 if (failed(Result: flattenResult))
152 return failure();
153 }
154
155 assert(flattener.operandExprStack.size() == exprs.size());
156 flattenedExprs->clear();
157 flattenedExprs->assign(first: flattener.operandExprStack.begin(),
158 last: flattener.operandExprStack.end());
159
160 if (localVarCst)
161 localVarCst->clearAndCopyFrom(other: flattener.localVarCst);
162
163 return success();
164 };
165
166 if (addConservativeSemiAffineBounds) {
167 SemiAffineExprFlattener flattener(numDims, numSymbols);
168 return flattenExprs(flattener);
169 }
170
171 AffineExprFlattener flattener(numDims, numSymbols);
172 return flattenExprs(flattener);
173}
174
175// Flattens 'expr' into 'flattenedExpr'. Returns failure if 'expr' was unable to
176// be flattened (an unhandled semi-affine was found).
177LogicalResult mlir::getFlattenedAffineExpr(
178 AffineExpr expr, unsigned numDims, unsigned numSymbols,
179 SmallVectorImpl<int64_t> *flattenedExpr, FlatLinearConstraints *localVarCst,
180 bool addConservativeSemiAffineBounds) {
181 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
182 LogicalResult ret =
183 ::getFlattenedAffineExprs(exprs: {expr}, numDims, numSymbols, flattenedExprs: &flattenedExprs,
184 localVarCst, addConservativeSemiAffineBounds);
185 *flattenedExpr = flattenedExprs[0];
186 return ret;
187}
188
189/// Flattens the expressions in map. Returns failure if 'expr' was unable to be
190/// flattened (i.e., an unhandled semi-affine was found).
191LogicalResult mlir::getFlattenedAffineExprs(
192 AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
193 FlatLinearConstraints *localVarCst, bool addConservativeSemiAffineBounds) {
194 if (map.getNumResults() == 0) {
195 if (localVarCst)
196 *localVarCst =
197 FlatLinearConstraints(map.getNumDims(), map.getNumSymbols());
198 return success();
199 }
200 return ::getFlattenedAffineExprs(
201 exprs: map.getResults(), numDims: map.getNumDims(), numSymbols: map.getNumSymbols(), flattenedExprs,
202 localVarCst, addConservativeSemiAffineBounds);
203}
204
205LogicalResult mlir::getFlattenedAffineExprs(
206 IntegerSet set, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
207 FlatLinearConstraints *localVarCst) {
208 if (set.getNumConstraints() == 0) {
209 if (localVarCst)
210 *localVarCst =
211 FlatLinearConstraints(set.getNumDims(), set.getNumSymbols());
212 return success();
213 }
214 return ::getFlattenedAffineExprs(exprs: set.getConstraints(), numDims: set.getNumDims(),
215 numSymbols: set.getNumSymbols(), flattenedExprs,
216 localVarCst);
217}
218
219//===----------------------------------------------------------------------===//
220// FlatLinearConstraints
221//===----------------------------------------------------------------------===//
222
223// Similar to `composeMap` except that no Values need be associated with the
224// constraint system nor are they looked at -- the dimensions and symbols of
225// `other` are expected to correspond 1:1 to `this` system.
226LogicalResult FlatLinearConstraints::composeMatchingMap(AffineMap other) {
227 assert(other.getNumDims() == getNumDimVars() && "dim mismatch");
228 assert(other.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");
229
230 std::vector<SmallVector<int64_t, 8>> flatExprs;
231 if (failed(Result: flattenAlignedMapAndMergeLocals(map: other, flattenedExprs: &flatExprs)))
232 return failure();
233 assert(flatExprs.size() == other.getNumResults());
234
235 // Add dimensions corresponding to the map's results.
236 insertDimVar(/*pos=*/0, /*num=*/other.getNumResults());
237
238 // We add one equality for each result connecting the result dim of the map to
239 // the other variables.
240 // E.g.: if the expression is 16*i0 + i1, and this is the r^th
241 // iteration/result of the value map, we are adding the equality:
242 // d_r - 16*i0 - i1 = 0. Similarly, when flattening (i0 + 1, i0 + 8*i2), we
243 // add two equalities: d_0 - i0 - 1 == 0, d1 - i0 - 8*i2 == 0.
244 for (unsigned r = 0, e = flatExprs.size(); r < e; r++) {
245 const auto &flatExpr = flatExprs[r];
246 assert(flatExpr.size() >= other.getNumInputs() + 1);
247
248 SmallVector<int64_t, 8> eqToAdd(getNumCols(), 0);
249 // Set the coefficient for this result to one.
250 eqToAdd[r] = 1;
251
252 // Dims and symbols.
253 for (unsigned i = 0, f = other.getNumInputs(); i < f; i++) {
254 // Negate `eq[r]` since the newly added dimension will be set to this one.
255 eqToAdd[e + i] = -flatExpr[i];
256 }
257 // Local columns of `eq` are at the beginning.
258 unsigned j = getNumDimVars() + getNumSymbolVars();
259 unsigned end = flatExpr.size() - 1;
260 for (unsigned i = other.getNumInputs(); i < end; i++, j++) {
261 eqToAdd[j] = -flatExpr[i];
262 }
263
264 // Constant term.
265 eqToAdd[getNumCols() - 1] = -flatExpr[flatExpr.size() - 1];
266
267 // Add the equality connecting the result of the map to this constraint set.
268 addEquality(eq: eqToAdd);
269 }
270
271 return success();
272}
273
274// Determine whether the variable at 'pos' (say var_r) can be expressed as
275// modulo of another known variable (say var_n) w.r.t a constant. For example,
276// if the following constraints hold true:
277// ```
278// 0 <= var_r <= divisor - 1
279// var_n - (divisor * q_expr) = var_r
280// ```
281// where `var_n` is a known variable (called dividend), and `q_expr` is an
282// `AffineExpr` (called the quotient expression), `var_r` can be written as:
283//
284// `var_r = var_n mod divisor`.
285//
286// Additionally, in a special case of the above constaints where `q_expr` is an
287// variable itself that is not yet known (say `var_q`), it can be written as a
288// floordiv in the following way:
289//
290// `var_q = var_n floordiv divisor`.
291//
292// First 'num' dimensional variables starting at 'offset' are
293// derived/to-be-derived in terms of the remaining variables. The remaining
294// variables are assigned trivial affine expressions in `memo`. For example,
295// memo is initilized as follows for a `cst` with 5 dims, when offset=2, num=2:
296// memo ==> d0 d1 . . d2 ...
297// cst ==> c0 c1 c2 c3 c4 ...
298//
299// Returns true if the above mod or floordiv are detected, updating 'memo' with
300// these new expressions. Returns false otherwise.
301static bool detectAsMod(const FlatLinearConstraints &cst, unsigned pos,
302 unsigned offset, unsigned num, int64_t lbConst,
303 int64_t ubConst, MLIRContext *context,
304 SmallVectorImpl<AffineExpr> &memo) {
305 assert(pos < cst.getNumVars() && "invalid position");
306
307 // Check if a divisor satisfying the condition `0 <= var_r <= divisor - 1` can
308 // be determined.
309 if (lbConst != 0 || ubConst < 1)
310 return false;
311 int64_t divisor = ubConst + 1;
312
313 // Check for the aforementioned conditions in each equality.
314 for (unsigned curEquality = 0, numEqualities = cst.getNumEqualities();
315 curEquality < numEqualities; curEquality++) {
316 int64_t coefficientAtPos = cst.atEq64(i: curEquality, j: pos);
317 // If current equality does not involve `var_r`, continue to the next
318 // equality.
319 if (coefficientAtPos == 0)
320 continue;
321
322 // Constant term should be 0 in this equality.
323 if (cst.atEq64(i: curEquality, j: cst.getNumCols() - 1) != 0)
324 continue;
325
326 // Traverse through the equality and construct the dividend expression
327 // `dividendExpr`, to contain all the variables which are known and are
328 // not divisible by `(coefficientAtPos * divisor)`. Hope here is that the
329 // `dividendExpr` gets simplified into a single variable `var_n` discussed
330 // above.
331 auto dividendExpr = getAffineConstantExpr(constant: 0, context);
332
333 // Track the terms that go into quotient expression, later used to detect
334 // additional floordiv.
335 unsigned quotientCount = 0;
336 int quotientPosition = -1;
337 int quotientSign = 1;
338
339 // Consider each term in the current equality.
340 unsigned curVar, e;
341 for (curVar = 0, e = cst.getNumDimAndSymbolVars(); curVar < e; ++curVar) {
342 // Ignore var_r.
343 if (curVar == pos)
344 continue;
345 int64_t coefficientOfCurVar = cst.atEq64(i: curEquality, j: curVar);
346 // Ignore vars that do not contribute to the current equality.
347 if (coefficientOfCurVar == 0)
348 continue;
349 // Check if the current var goes into the quotient expression.
350 if (coefficientOfCurVar % (divisor * coefficientAtPos) == 0) {
351 quotientCount++;
352 quotientPosition = curVar;
353 quotientSign = (coefficientOfCurVar * coefficientAtPos) > 0 ? 1 : -1;
354 continue;
355 }
356 // Variables that are part of dividendExpr should be known.
357 if (!memo[curVar])
358 break;
359 // Append the current variable to the dividend expression.
360 dividendExpr = dividendExpr + memo[curVar] * coefficientOfCurVar;
361 }
362
363 // Can't construct expression as it depends on a yet uncomputed var.
364 if (curVar < e)
365 continue;
366
367 // Express `var_r` in terms of the other vars collected so far.
368 if (coefficientAtPos > 0)
369 dividendExpr = (-dividendExpr).floorDiv(v: coefficientAtPos);
370 else
371 dividendExpr = dividendExpr.floorDiv(v: -coefficientAtPos);
372
373 // Simplify the expression.
374 dividendExpr = simplifyAffineExpr(expr: dividendExpr, numDims: cst.getNumDimVars(),
375 numSymbols: cst.getNumSymbolVars());
376 // Only if the final dividend expression is just a single var (which we call
377 // `var_n`), we can proceed.
378 // TODO: Handle AffineSymbolExpr as well. There is no reason to restrict it
379 // to dims themselves.
380 auto dimExpr = dyn_cast<AffineDimExpr>(Val&: dividendExpr);
381 if (!dimExpr)
382 continue;
383
384 // Express `var_r` as `var_n % divisor` and store the expression in `memo`.
385 if (quotientCount >= 1) {
386 // Find the column corresponding to `dimExpr`. `num` columns starting at
387 // `offset` correspond to previously unknown variables. The column
388 // corresponding to the trivially known `dimExpr` can be on either side
389 // of these.
390 unsigned dimExprPos = dimExpr.getPosition();
391 unsigned dimExprCol = dimExprPos < offset ? dimExprPos : dimExprPos + num;
392 auto ub = cst.getConstantBound64(type: BoundType::UB, pos: dimExprCol);
393 // If `var_n` has an upperbound that is less than the divisor, mod can be
394 // eliminated altogether.
395 if (ub && *ub < divisor)
396 memo[pos] = dimExpr;
397 else
398 memo[pos] = dimExpr % divisor;
399 // If a unique quotient `var_q` was seen, it can be expressed as
400 // `var_n floordiv divisor`.
401 if (quotientCount == 1 && !memo[quotientPosition])
402 memo[quotientPosition] = dimExpr.floorDiv(v: divisor) * quotientSign;
403
404 return true;
405 }
406 }
407 return false;
408}
409
410/// Check if the pos^th variable can be expressed as a floordiv of an affine
411/// function of other variables (where the divisor is a positive constant)
412/// given the initial set of expressions in `exprs`. If it can be, the
413/// corresponding position in `exprs` is set as the detected affine expr. For
414/// eg: 4q <= i + j <= 4q + 3 <=> q = (i + j) floordiv 4. An equality can
415/// also yield a floordiv: eg. 4q = i + j <=> q = (i + j) floordiv 4. 32q + 28
416/// <= i <= 32q + 31 => q = i floordiv 32.
417static bool detectAsFloorDiv(const FlatLinearConstraints &cst, unsigned pos,
418 MLIRContext *context,
419 SmallVectorImpl<AffineExpr> &exprs) {
420 assert(pos < cst.getNumVars() && "invalid position");
421
422 // Get upper-lower bound pair for this variable.
423 SmallVector<bool, 8> foundRepr(cst.getNumVars(), false);
424 for (unsigned i = 0, e = cst.getNumVars(); i < e; ++i)
425 if (exprs[i])
426 foundRepr[i] = true;
427
428 SmallVector<int64_t, 8> dividend(cst.getNumCols());
429 unsigned divisor;
430 auto ulPair = computeSingleVarRepr(cst, foundRepr, pos, dividend, divisor);
431
432 // No upper-lower bound pair found for this var.
433 if (ulPair.kind == ReprKind::None || ulPair.kind == ReprKind::Equality)
434 return false;
435
436 // Construct the dividend expression.
437 auto dividendExpr = getAffineConstantExpr(constant: dividend.back(), context);
438 for (unsigned c = 0, f = cst.getNumVars(); c < f; c++)
439 if (dividend[c] != 0)
440 dividendExpr = dividendExpr + dividend[c] * exprs[c];
441
442 // Successfully detected the floordiv.
443 exprs[pos] = dividendExpr.floorDiv(v: divisor);
444 return true;
445}
446
447void FlatLinearConstraints::dumpRow(ArrayRef<int64_t> row,
448 bool fixedColWidth) const {
449 unsigned ncols = getNumCols();
450 bool firstNonZero = true;
451 for (unsigned j = 0; j < ncols; j++) {
452 if (j == ncols - 1) {
453 // Constant.
454 if (row[j] == 0 && !firstNonZero) {
455 if (fixedColWidth)
456 llvm::errs().indent(NumSpaces: 7);
457 } else {
458 llvm::errs() << ((row[j] >= 0) ? "+ " : "") << row[j] << ' ';
459 }
460 } else {
461 std::string var = std::string("c_") + std::to_string(val: j);
462 if (row[j] == 1)
463 llvm::errs() << "+ " << var << ' ';
464 else if (row[j] == -1)
465 llvm::errs() << "- " << var << ' ';
466 else if (row[j] >= 2)
467 llvm::errs() << "+ " << row[j] << '*' << var << ' ';
468 else if (row[j] <= -2)
469 llvm::errs() << "- " << -row[j] << '*' << var << ' ';
470 else if (fixedColWidth)
471 // Zero coeff.
472 llvm::errs().indent(NumSpaces: 7);
473 if (row[j] != 0)
474 firstNonZero = false;
475 }
476 }
477}
478
479void FlatLinearConstraints::dumpPretty() const {
480 assert(hasConsistentState());
481 llvm::errs() << "Constraints (" << getNumDimVars() << " dims, "
482 << getNumSymbolVars() << " symbols, " << getNumLocalVars()
483 << " locals), (" << getNumConstraints() << " constraints)\n";
484 auto dumpConstraint = [&](unsigned rowPos, bool isEq) {
485 // Is it the first non-zero entry?
486 SmallVector<int64_t> row =
487 isEq ? getEquality64(idx: rowPos) : getInequality64(idx: rowPos);
488 dumpRow(row);
489 llvm::errs() << (isEq ? "=" : ">=") << " 0\n";
490 };
491
492 for (unsigned i = 0, e = getNumInequalities(); i < e; i++)
493 dumpConstraint(i, /*isEq=*/false);
494 for (unsigned i = 0, e = getNumEqualities(); i < e; i++)
495 dumpConstraint(i, /*isEq=*/true);
496 llvm::errs() << '\n';
497}
498
499std::pair<AffineMap, AffineMap> FlatLinearConstraints::getLowerAndUpperBound(
500 unsigned pos, unsigned offset, unsigned num, unsigned symStartPos,
501 ArrayRef<AffineExpr> localExprs, MLIRContext *context,
502 bool closedUB) const {
503 assert(pos + offset < getNumDimVars() && "invalid dim start pos");
504 assert(symStartPos >= (pos + offset) && "invalid sym start pos");
505 assert(getNumLocalVars() == localExprs.size() &&
506 "incorrect local exprs count");
507
508 SmallVector<unsigned, 4> lbIndices, ubIndices, eqIndices;
509 getLowerAndUpperBoundIndices(pos: pos + offset, lbIndices: &lbIndices, ubIndices: &ubIndices, eqIndices: &eqIndices,
510 offset, num);
511
512 /// Add to 'b' from 'a' in set [0, offset) U [offset + num, symbStartPos).
513 auto addCoeffs = [&](ArrayRef<int64_t> a, SmallVectorImpl<int64_t> &b) {
514 b.clear();
515 for (unsigned i = 0, e = a.size(); i < e; ++i) {
516 if (i < offset || i >= offset + num)
517 b.push_back(Elt: a[i]);
518 }
519 };
520
521 SmallVector<int64_t, 8> lb, ub;
522 SmallVector<AffineExpr, 4> lbExprs;
523 unsigned dimCount = symStartPos - num;
524 unsigned symCount = getNumDimAndSymbolVars() - symStartPos;
525 lbExprs.reserve(N: lbIndices.size() + eqIndices.size());
526 // Lower bound expressions.
527 for (auto idx : lbIndices) {
528 auto ineq = getInequality64(idx);
529 // Extract the lower bound (in terms of other coeff's + const), i.e., if
530 // i - j + 1 >= 0 is the constraint, 'pos' is for i the lower bound is j
531 // - 1.
532 addCoeffs(ineq, lb);
533 llvm::transform(Range&: lb, d_first: lb.begin(), F: std::negate<int64_t>());
534 auto expr =
535 getAffineExprFromFlatForm(flatExprs: lb, numDims: dimCount, numSymbols: symCount, localExprs, context);
536 // expr ceildiv divisor is (expr + divisor - 1) floordiv divisor
537 int64_t divisor = std::abs(i: ineq[pos + offset]);
538 expr = (expr + divisor - 1).floorDiv(v: divisor);
539 lbExprs.push_back(Elt: expr);
540 }
541
542 SmallVector<AffineExpr, 4> ubExprs;
543 ubExprs.reserve(N: ubIndices.size() + eqIndices.size());
544 // Upper bound expressions.
545 for (auto idx : ubIndices) {
546 auto ineq = getInequality64(idx);
547 // Extract the upper bound (in terms of other coeff's + const).
548 addCoeffs(ineq, ub);
549 auto expr =
550 getAffineExprFromFlatForm(flatExprs: ub, numDims: dimCount, numSymbols: symCount, localExprs, context);
551 expr = expr.floorDiv(v: std::abs(i: ineq[pos + offset]));
552 int64_t ubAdjustment = closedUB ? 0 : 1;
553 ubExprs.push_back(Elt: expr + ubAdjustment);
554 }
555
556 // Equalities. It's both a lower and a upper bound.
557 SmallVector<int64_t, 4> b;
558 for (auto idx : eqIndices) {
559 auto eq = getEquality64(idx);
560 addCoeffs(eq, b);
561 if (eq[pos + offset] > 0)
562 llvm::transform(Range&: b, d_first: b.begin(), F: std::negate<int64_t>());
563
564 // Extract the upper bound (in terms of other coeff's + const).
565 auto expr =
566 getAffineExprFromFlatForm(flatExprs: b, numDims: dimCount, numSymbols: symCount, localExprs, context);
567 expr = expr.floorDiv(v: std::abs(i: eq[pos + offset]));
568 // Upper bound is exclusive.
569 ubExprs.push_back(Elt: expr + 1);
570 // Lower bound.
571 expr =
572 getAffineExprFromFlatForm(flatExprs: b, numDims: dimCount, numSymbols: symCount, localExprs, context);
573 expr = expr.ceilDiv(v: std::abs(i: eq[pos + offset]));
574 lbExprs.push_back(Elt: expr);
575 }
576
577 auto lbMap = AffineMap::get(dimCount, symbolCount: symCount, results: lbExprs, context);
578 auto ubMap = AffineMap::get(dimCount, symbolCount: symCount, results: ubExprs, context);
579
580 return {lbMap, ubMap};
581}
582
583/// Express the pos^th identifier of `cst` as an affine expression in
584/// terms of other identifiers, if they are available in `exprs`, using the
585/// equality at position `idx` in `cs`t. Populates `exprs` with such an
586/// expression if possible, and return true. Returns false otherwise.
587static bool detectAsExpr(const FlatLinearConstraints &cst, unsigned pos,
588 unsigned idx, MLIRContext *context,
589 SmallVectorImpl<AffineExpr> &exprs) {
590 // Initialize with a `0` expression.
591 auto expr = getAffineConstantExpr(constant: 0, context);
592
593 // Traverse `idx`th equality and construct the possible affine expression in
594 // terms of known identifiers.
595 unsigned j, e;
596 for (j = 0, e = cst.getNumVars(); j < e; ++j) {
597 if (j == pos)
598 continue;
599 int64_t c = cst.atEq64(i: idx, j);
600 if (c == 0)
601 continue;
602 // If any of the involved IDs hasn't been found yet, we can't proceed.
603 if (!exprs[j])
604 break;
605 expr = expr + exprs[j] * c;
606 }
607 if (j < e)
608 // Can't construct expression as it depends on a yet uncomputed
609 // identifier.
610 return false;
611
612 // Add constant term to AffineExpr.
613 expr = expr + cst.atEq64(i: idx, j: cst.getNumVars());
614 int64_t vPos = cst.atEq64(i: idx, j: pos);
615 assert(vPos != 0 && "expected non-zero here");
616 if (vPos > 0)
617 expr = (-expr).floorDiv(v: vPos);
618 else
619 // vPos < 0.
620 expr = expr.floorDiv(v: -vPos);
621 // Successfully constructed expression.
622 exprs[pos] = expr;
623 return true;
624}
625
626/// Compute a representation of `num` identifiers starting at `offset` in `cst`
627/// as affine expressions involving other known identifiers. Each identifier's
628/// expression (in terms of known identifiers) is populated into `memo`.
629static void computeUnknownVars(const FlatLinearConstraints &cst,
630 MLIRContext *context, unsigned offset,
631 unsigned num,
632 SmallVectorImpl<AffineExpr> &memo) {
633 // Initialize dimensional and symbolic variables.
634 for (unsigned i = 0, e = cst.getNumDimVars(); i < e; i++) {
635 if (i < offset)
636 memo[i] = getAffineDimExpr(position: i, context);
637 else if (i >= offset + num)
638 memo[i] = getAffineDimExpr(position: i - num, context);
639 }
640 for (unsigned i = cst.getNumDimVars(), e = cst.getNumDimAndSymbolVars();
641 i < e; i++)
642 memo[i] = getAffineSymbolExpr(position: i - cst.getNumDimVars(), context);
643
644 bool changed;
645 do {
646 changed = false;
647 // Identify yet unknown variables as constants or mod's / floordiv's of
648 // other variables if possible.
649 for (unsigned pos = 0, f = cst.getNumVars(); pos < f; pos++) {
650 if (memo[pos])
651 continue;
652
653 auto lbConst = cst.getConstantBound64(type: BoundType::LB, pos);
654 auto ubConst = cst.getConstantBound64(type: BoundType::UB, pos);
655 if (lbConst.has_value() && ubConst.has_value()) {
656 // Detect equality to a constant.
657 if (*lbConst == *ubConst) {
658 memo[pos] = getAffineConstantExpr(constant: *lbConst, context);
659 changed = true;
660 continue;
661 }
662
663 // Detect a variable as modulo of another variable w.r.t a
664 // constant.
665 if (detectAsMod(cst, pos, offset, num, lbConst: *lbConst, ubConst: *ubConst, context,
666 memo)) {
667 changed = true;
668 continue;
669 }
670 }
671
672 // Detect a variable as a floordiv of an affine function of other
673 // variables (divisor is a positive constant).
674 if (detectAsFloorDiv(cst, pos, context, exprs&: memo)) {
675 changed = true;
676 continue;
677 }
678
679 // Detect a variable as an expression of other variables.
680 std::optional<unsigned> idx;
681 if (!(idx = cst.findConstraintWithNonZeroAt(colIdx: pos, /*isEq=*/true)))
682 continue;
683
684 if (detectAsExpr(cst, pos, idx: *idx, context, exprs&: memo)) {
685 changed = true;
686 continue;
687 }
688 }
689 // This loop is guaranteed to reach a fixed point - since once an
690 // variable's explicit form is computed (in memo[pos]), it's not updated
691 // again.
692 } while (changed);
693}
694
695/// Computes the lower and upper bounds of the first 'num' dimensional
696/// variables (starting at 'offset') as affine maps of the remaining
697/// variables (dimensional and symbolic variables). Local variables are
698/// themselves explicitly computed as affine functions of other variables in
699/// this process if needed.
700void FlatLinearConstraints::getSliceBounds(unsigned offset, unsigned num,
701 MLIRContext *context,
702 SmallVectorImpl<AffineMap> *lbMaps,
703 SmallVectorImpl<AffineMap> *ubMaps,
704 bool closedUB,
705 bool allowMultiResultUB) {
706 assert(offset + num <= getNumDimVars() && "invalid range");
707
708 // Basic simplification.
709 normalizeConstraintsByGCD();
710
711 LLVM_DEBUG(llvm::dbgs() << "getSliceBounds for variables at positions ["
712 << offset << ", " << offset + num << ")\n");
713 LLVM_DEBUG(dumpPretty());
714
715 // Record computed/detected variables.
716 SmallVector<AffineExpr, 8> memo(getNumVars());
717 computeUnknownVars(cst: *this, context, offset, num, memo);
718
719 int64_t ubAdjustment = closedUB ? 0 : 1;
720
721 // Set the lower and upper bound maps for all the variables that were
722 // computed as affine expressions of the rest as the "detected expr" and
723 // "detected expr + 1" respectively; set the undetected ones to null.
724 std::optional<FlatLinearConstraints> tmpClone;
725 for (unsigned pos = 0; pos < num; pos++) {
726 unsigned numMapDims = getNumDimVars() - num;
727 unsigned numMapSymbols = getNumSymbolVars();
728 AffineExpr expr = memo[pos + offset];
729 if (expr)
730 expr = simplifyAffineExpr(expr, numDims: numMapDims, numSymbols: numMapSymbols);
731
732 AffineMap &lbMap = (*lbMaps)[pos];
733 AffineMap &ubMap = (*ubMaps)[pos];
734
735 if (expr) {
736 lbMap = AffineMap::get(dimCount: numMapDims, symbolCount: numMapSymbols, result: expr);
737 ubMap = AffineMap::get(dimCount: numMapDims, symbolCount: numMapSymbols, result: expr + ubAdjustment);
738 } else {
739 // TODO: Whenever there are local variables in the dependence
740 // constraints, we'll conservatively over-approximate, since we don't
741 // always explicitly compute them above (in the while loop).
742 if (getNumLocalVars() == 0) {
743 // Work on a copy so that we don't update this constraint system.
744 if (!tmpClone) {
745 tmpClone.emplace(args: FlatLinearConstraints(*this));
746 // Removing redundant inequalities is necessary so that we don't get
747 // redundant loop bounds.
748 tmpClone->removeRedundantInequalities();
749 }
750 std::tie(args&: lbMap, args&: ubMap) = tmpClone->getLowerAndUpperBound(
751 pos, offset, num, symStartPos: getNumDimVars(), /*localExprs=*/{}, context,
752 closedUB);
753 }
754
755 // If the above fails, we'll just use the constant lower bound and the
756 // constant upper bound (if they exist) as the slice bounds.
757 if (!lbMap || lbMap.getNumResults() != 1) {
758 LLVM_DEBUG(llvm::dbgs()
759 << "WARNING: Potentially over-approximating slice lb\n");
760 auto lbConst = getConstantBound64(type: BoundType::LB, pos: pos + offset);
761 if (lbConst.has_value()) {
762 lbMap = AffineMap::get(dimCount: numMapDims, symbolCount: numMapSymbols,
763 result: getAffineConstantExpr(constant: *lbConst, context));
764 }
765 }
766 // An upper bound of several results is the min of them, for e.g.
767 // the bound of a tiled loop clamped at the end of the data looks like:
768 // `min(%i * 64 + 64, 1000)`. Falling back to the constant bound
769 // the way the lower one does would drop the tile-relative result and
770 // leave nothing but the extent of the data, turning a slice of a single
771 // tile into a slice of everything from the tile onwards.
772 if (!ubMap || ubMap.getNumResults() == 0 ||
773 (!allowMultiResultUB && ubMap.getNumResults() != 1)) {
774 LLVM_DEBUG(llvm::dbgs()
775 << "WARNING: Potentially over-approximating slice ub\n");
776 auto ubConst = getConstantBound64(type: BoundType::UB, pos: pos + offset);
777 if (ubConst.has_value()) {
778 ubMap = AffineMap::get(
779 dimCount: numMapDims, symbolCount: numMapSymbols,
780 result: getAffineConstantExpr(constant: *ubConst + ubAdjustment, context));
781 }
782 }
783 }
784
785 LLVM_DEBUG(llvm::dbgs() << "Slice bounds:\n");
786 LLVM_DEBUG(llvm::dbgs() << "lb map for pos = " << Twine(pos + offset)
787 << ", expr: " << lbMap << '\n');
788 LLVM_DEBUG(llvm::dbgs() << "ub map for pos = " << Twine(pos + offset)
789 << ", expr: " << ubMap << '\n');
790 }
791}
792
793LogicalResult FlatLinearConstraints::flattenAlignedMapAndMergeLocals(
794 AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
795 bool addConservativeSemiAffineBounds) {
796 FlatLinearConstraints localCst;
797 if (failed(Result: getFlattenedAffineExprs(map, flattenedExprs, localVarCst: &localCst,
798 addConservativeSemiAffineBounds))) {
799 LLVM_DEBUG(llvm::dbgs()
800 << "composition unimplemented for semi-affine maps\n");
801 return failure();
802 }
803
804 // Add localCst information.
805 if (localCst.getNumLocalVars() > 0) {
806 unsigned numLocalVars = getNumLocalVars();
807 // Insert local dims of localCst at the beginning.
808 insertLocalVar(/*pos=*/0, /*num=*/localCst.getNumLocalVars());
809 // Insert local dims of `this` at the end of localCst.
810 localCst.appendLocalVar(/*num=*/numLocalVars);
811 // Dimensions of localCst and this constraint set match. Append localCst to
812 // this constraint set.
813 append(other: localCst);
814 }
815
816 return success();
817}
818
819LogicalResult FlatLinearConstraints::addBound(
820 BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound,
821 AddConservativeSemiAffineBounds addSemiAffineBounds) {
822 assert(boundMap.getNumDims() == getNumDimVars() && "dim mismatch");
823 assert(boundMap.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");
824 assert(pos < getNumDimAndSymbolVars() && "invalid position");
825 assert((type != BoundType::EQ || isClosedBound) &&
826 "EQ bound must be closed.");
827
828 // Equality follows the logic of lower bound except that we add an equality
829 // instead of an inequality.
830 assert((type != BoundType::EQ || boundMap.getNumResults() == 1) &&
831 "single result expected");
832 bool lower = type == BoundType::LB || type == BoundType::EQ;
833
834 std::vector<SmallVector<int64_t, 8>> flatExprs;
835 if (failed(Result: flattenAlignedMapAndMergeLocals(
836 map: boundMap, flattenedExprs: &flatExprs,
837 addConservativeSemiAffineBounds: addSemiAffineBounds == AddConservativeSemiAffineBounds::Yes)))
838 return failure();
839 assert(flatExprs.size() == boundMap.getNumResults());
840
841 // Add one (in)equality for each result.
842 for (const auto &flatExpr : flatExprs) {
843 // Inline size chosen empirically based on compilation profiling.
844 // Profiled: 7.1M calls, avg=5.3+-3.0. N=8 covers 82% of cases inline.
845 SmallVector<int64_t, 8> ineq(getNumCols(), 0);
846 // Dims and symbols.
847 for (unsigned j = 0, e = boundMap.getNumInputs(); j < e; j++) {
848 ineq[j] = lower ? -flatExpr[j] : flatExpr[j];
849 }
850 // Invalid bound: pos appears in `boundMap`.
851 // TODO: This should be an assertion. Fix `addDomainFromSliceMaps` and/or
852 // its callers to prevent invalid bounds from being added.
853 if (ineq[pos] != 0)
854 continue;
855 ineq[pos] = lower ? 1 : -1;
856 // Local columns of `ineq` are at the beginning.
857 unsigned j = getNumDimVars() + getNumSymbolVars();
858 unsigned end = flatExpr.size() - 1;
859 for (unsigned i = boundMap.getNumInputs(); i < end; i++, j++) {
860 ineq[j] = lower ? -flatExpr[i] : flatExpr[i];
861 }
862 // Make the bound closed in if flatExpr is open. The inequality is always
863 // created in the upper bound form, so the adjustment is -1.
864 int64_t boundAdjustment = (isClosedBound || type == BoundType::EQ) ? 0 : -1;
865 // Constant term.
866 ineq[getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
867 : flatExpr[flatExpr.size() - 1]) +
868 boundAdjustment;
869 type == BoundType::EQ ? addEquality(eq: ineq) : addInequality(inEq: ineq);
870 }
871
872 return success();
873}
874
875LogicalResult FlatLinearConstraints::addBound(
876 BoundType type, unsigned pos, AffineMap boundMap,
877 AddConservativeSemiAffineBounds addSemiAffineBounds) {
878 return addBound(type, pos, boundMap,
879 /*isClosedBound=*/type != BoundType::UB, addSemiAffineBounds);
880}
881
882/// Compute an explicit representation for local vars. For all systems coming
883/// from MLIR integer sets, maps, or expressions where local vars were
884/// introduced to model floordivs and mods, this always succeeds.
885LogicalResult
886FlatLinearConstraints::computeLocalVars(SmallVectorImpl<AffineExpr> &memo,
887 MLIRContext *context) const {
888 unsigned numDims = getNumDimVars();
889 unsigned numSyms = getNumSymbolVars();
890
891 // Initialize dimensional and symbolic variables.
892 for (unsigned i = 0; i < numDims; i++)
893 memo[i] = getAffineDimExpr(position: i, context);
894 for (unsigned i = numDims, e = numDims + numSyms; i < e; i++)
895 memo[i] = getAffineSymbolExpr(position: i - numDims, context);
896
897 bool changed;
898 do {
899 // Each time `changed` is true at the end of this iteration, one or more
900 // local vars would have been detected as floordivs and set in memo; so the
901 // number of null entries in memo[...] strictly reduces; so this converges.
902 changed = false;
903 for (unsigned i = 0, e = getNumLocalVars(); i < e; ++i)
904 if (!memo[numDims + numSyms + i] &&
905 detectAsFloorDiv(cst: *this, /*pos=*/numDims + numSyms + i, context, exprs&: memo))
906 changed = true;
907 } while (changed);
908
909 ArrayRef<AffineExpr> localExprs =
910 ArrayRef<AffineExpr>(memo).take_back(N: getNumLocalVars());
911 return success(
912 IsSuccess: llvm::all_of(Range&: localExprs, P: [](AffineExpr expr) { return expr; }));
913}
914
915/// Given an equality or inequality (`isEquality` used to disambiguate) of `cst`
916/// at `idx`, traverse and sum up `AffineExpr`s of all known ids other than the
917/// `pos`th. Known `AffineExpr`s are given in `exprs` (unknowns are null). If
918/// the equality/inequality contains any unknown id, return None. Otherwise
919/// return sum as `AffineExpr`.
920static std::optional<AffineExpr> getAsExpr(const FlatLinearConstraints &cst,
921 unsigned pos, MLIRContext *context,
922 ArrayRef<AffineExpr> exprs,
923 unsigned idx, bool isEquality) {
924 // Initialize with a `0` expression.
925 auto expr = getAffineConstantExpr(constant: 0, context);
926
927 SmallVector<int64_t, 8> row =
928 isEquality ? cst.getEquality64(idx) : cst.getInequality64(idx);
929
930 // Traverse `idx`th equality and construct the possible affine expression in
931 // terms of known identifiers.
932 unsigned j, e;
933 for (j = 0, e = cst.getNumVars(); j < e; ++j) {
934 if (j == pos)
935 continue;
936 int64_t c = row[j];
937 if (c == 0)
938 continue;
939 // If any of the involved IDs hasn't been found yet, we can't proceed.
940 if (!exprs[j])
941 break;
942 expr = expr + exprs[j] * c;
943 }
944 if (j < e)
945 // Can't construct expression as it depends on a yet uncomputed
946 // identifier.
947 return std::nullopt;
948
949 // Add constant term to AffineExpr.
950 expr = expr + row[cst.getNumVars()];
951 return expr;
952}
953
954std::optional<int64_t> FlatLinearConstraints::getConstantBoundOnDimSize(
955 MLIRContext *context, unsigned pos, AffineMap *lb, AffineMap *ub,
956 unsigned *minLbPos, unsigned *minUbPos) const {
957
958 assert(pos < getNumDimVars() && "Invalid identifier position");
959
960 auto freeOfUnknownLocalVars = [&](ArrayRef<int64_t> cst,
961 ArrayRef<AffineExpr> whiteListCols) {
962 for (int i = getNumDimAndSymbolVars(), e = cst.size() - 1; i < e; ++i) {
963 if (whiteListCols[i] && whiteListCols[i].isSymbolicOrConstant())
964 continue;
965 if (cst[i] != 0)
966 return false;
967 }
968 return true;
969 };
970
971 // Detect the necesary local variables first.
972 SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());
973 (void)computeLocalVars(memo, context);
974
975 // Find an equality for 'pos'^th identifier that equates it to some function
976 // of the symbolic identifiers (+ constant).
977 int eqPos = findEqualityToConstant(pos, /*symbolic=*/true);
978 // If the equality involves a local var that can not be expressed as a
979 // symbolic or constant affine expression, we bail out.
980 if (eqPos != -1 && freeOfUnknownLocalVars(getEquality64(idx: eqPos), memo)) {
981 // This identifier can only take a single value.
982 if (lb && detectAsExpr(cst: *this, pos, idx: eqPos, context, exprs&: memo)) {
983 AffineExpr equalityExpr =
984 simplifyAffineExpr(expr: memo[pos], numDims: 0, numSymbols: getNumSymbolVars());
985 *lb = AffineMap::get(/*dimCount=*/0, symbolCount: getNumSymbolVars(), result: equalityExpr);
986 if (ub)
987 *ub = *lb;
988 }
989 if (minLbPos)
990 *minLbPos = eqPos;
991 if (minUbPos)
992 *minUbPos = eqPos;
993 return 1;
994 }
995
996 // Positions of constraints that are lower/upper bounds on the variable.
997 SmallVector<unsigned, 4> lbIndices, ubIndices;
998
999 // Note inequalities that give lower and upper bounds.
1000 getLowerAndUpperBoundIndices(pos, lbIndices: &lbIndices, ubIndices: &ubIndices,
1001 /*eqIndices=*/nullptr, /*offset=*/0,
1002 /*num=*/getNumDimVars());
1003
1004 std::optional<int64_t> minDiff = std::nullopt;
1005 unsigned minLbPosition = 0, minUbPosition = 0;
1006 AffineExpr minLbExpr, minUbExpr;
1007
1008 // Traverse each lower bound and upper bound pair, to compute the difference
1009 // between them.
1010 for (unsigned ubPos : ubIndices) {
1011 // Construct sum of all ids other than `pos`th in the given upper bound row.
1012 std::optional<AffineExpr> maybeUbExpr =
1013 getAsExpr(cst: *this, pos, context, exprs: memo, idx: ubPos, /*isEquality=*/false);
1014 if (!maybeUbExpr.has_value() || !(*maybeUbExpr).isSymbolicOrConstant())
1015 continue;
1016
1017 // Canonical form of an inequality that constrains the upper bound on
1018 // an id `x_i` is of the form:
1019 // `c_1*x_1 + c_2*x_2 + ... + c_0 >= 0`, where `c_i` <= -1.
1020 // Therefore the upper bound on `x_i` will be
1021 // `(
1022 // sum(c_j*x_j) where j != i
1023 // +
1024 // c_0
1025 // )
1026 // /
1027 // -(c_i)`. Divison here is a floorDiv.
1028 AffineExpr ubExpr = maybeUbExpr->floorDiv(v: -atIneq64(i: ubPos, j: pos));
1029 assert(-atIneq64(ubPos, pos) > 0 && "invalid upper bound index");
1030
1031 // Go over each lower bound.
1032 for (unsigned lbPos : lbIndices) {
1033 // Construct sum of all ids other than `pos`th in the given lower bound
1034 // row.
1035 std::optional<AffineExpr> maybeLbExpr =
1036 getAsExpr(cst: *this, pos, context, exprs: memo, idx: lbPos, /*isEquality=*/false);
1037 if (!maybeLbExpr.has_value() || !(*maybeLbExpr).isSymbolicOrConstant())
1038 continue;
1039
1040 // Canonical form of an inequality that is constraining the lower bound
1041 // on an id `x_i is of the form:
1042 // `c_1*x_1 + c_2*x_2 + ... + c_0 >= 0`, where `c_i` >= 1.
1043 // Therefore upperBound on `x_i` will be
1044 // `-(
1045 // sum(c_j*x_j) where j != i
1046 // +
1047 // c_0
1048 // )
1049 // /
1050 // c_i`. Divison here is a ceilDiv.
1051 int64_t divisor = atIneq64(i: lbPos, j: pos);
1052 // We convert the `ceilDiv` for floordiv with the formula:
1053 // `expr ceildiv divisor is (expr + divisor - 1) floordiv divisor`,
1054 // since uniformly keeping divisons as `floorDiv` helps their
1055 // simplification.
1056 AffineExpr lbExpr = (-(*maybeLbExpr) + divisor - 1).floorDiv(v: divisor);
1057 assert(atIneq64(lbPos, pos) > 0 && "invalid lower bound index");
1058
1059 AffineExpr difference =
1060 simplifyAffineExpr(expr: ubExpr - lbExpr + 1, numDims: 0, numSymbols: getNumSymbolVars());
1061 // If the difference is not constant, ignore the lower bound - upper bound
1062 // pair.
1063 auto constantDiff = dyn_cast<AffineConstantExpr>(Val&: difference);
1064 if (!constantDiff)
1065 continue;
1066
1067 int64_t diffValue = constantDiff.getValue();
1068 // This bound is non-negative by definition.
1069 diffValue = std::max<int64_t>(a: diffValue, b: 0);
1070 if (!minDiff || diffValue < *minDiff) {
1071 minDiff = diffValue;
1072 minLbPosition = lbPos;
1073 minUbPosition = ubPos;
1074 minLbExpr = lbExpr;
1075 minUbExpr = ubExpr;
1076 }
1077 }
1078 }
1079
1080 // Populate outputs where available and needed.
1081 if (lb && minDiff) {
1082 *lb = AffineMap::get(/*dimCount=*/0, symbolCount: getNumSymbolVars(), result: minLbExpr);
1083 }
1084 if (ub)
1085 *ub = AffineMap::get(/*dimCount=*/0, symbolCount: getNumSymbolVars(), result: minUbExpr);
1086 if (minLbPos)
1087 *minLbPos = minLbPosition;
1088 if (minUbPos)
1089 *minUbPos = minUbPosition;
1090
1091 return minDiff;
1092}
1093
1094IntegerSet FlatLinearConstraints::getAsIntegerSet(MLIRContext *context) const {
1095 if (getNumConstraints() == 0)
1096 // Return universal set (always true): 0 == 0.
1097 return IntegerSet::get(dimCount: getNumDimVars(), symbolCount: getNumSymbolVars(),
1098 constraints: getAffineConstantExpr(/*constant=*/0, context),
1099 /*eqFlags=*/true);
1100
1101 // Construct local references.
1102 SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());
1103
1104 if (failed(Result: computeLocalVars(memo, context))) {
1105 // Check if the local variables without an explicit representation have
1106 // zero coefficients everywhere.
1107 SmallVector<unsigned> noLocalRepVars;
1108 unsigned numDimsSymbols = getNumDimAndSymbolVars();
1109 for (unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
1110 if (!memo[i] && !isColZero(/*pos=*/i))
1111 noLocalRepVars.push_back(Elt: i - numDimsSymbols);
1112 }
1113 if (!noLocalRepVars.empty()) {
1114 LLVM_DEBUG({
1115 llvm::dbgs() << "local variables at position(s) "
1116 << llvm::interleaved(noLocalRepVars)
1117 << " do not have an explicit representation in:\n";
1118 this->dump();
1119 });
1120 return IntegerSet();
1121 }
1122 }
1123
1124 ArrayRef<AffineExpr> localExprs =
1125 ArrayRef<AffineExpr>(memo).take_back(N: getNumLocalVars());
1126
1127 // Construct the IntegerSet from the equalities/inequalities.
1128 unsigned numDims = getNumDimVars();
1129 unsigned numSyms = getNumSymbolVars();
1130
1131 SmallVector<bool, 16> eqFlags(getNumConstraints());
1132 std::fill(first: eqFlags.begin(), last: eqFlags.begin() + getNumEqualities(), value: true);
1133 std::fill(first: eqFlags.begin() + getNumEqualities(), last: eqFlags.end(), value: false);
1134
1135 SmallVector<AffineExpr, 8> exprs;
1136 exprs.reserve(N: getNumConstraints());
1137
1138 for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
1139 exprs.push_back(Elt: getAffineExprFromFlatForm(flatExprs: getEquality64(idx: i), numDims,
1140 numSymbols: numSyms, localExprs, context));
1141 for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
1142 exprs.push_back(Elt: getAffineExprFromFlatForm(flatExprs: getInequality64(idx: i), numDims,
1143 numSymbols: numSyms, localExprs, context));
1144 return IntegerSet::get(dimCount: numDims, symbolCount: numSyms, constraints: exprs, eqFlags);
1145}
1146
1147//===----------------------------------------------------------------------===//
1148// FlatLinearValueConstraints
1149//===----------------------------------------------------------------------===//
1150
1151// Construct from an IntegerSet.
1152FlatLinearValueConstraints::FlatLinearValueConstraints(IntegerSet set,
1153 ValueRange operands,
1154 bool *error)
1155 : FlatLinearConstraints(set.getNumInequalities(), set.getNumEqualities(),
1156 set.getNumDims() + set.getNumSymbols() + 1,
1157 set.getNumDims(), set.getNumSymbols(),
1158 /*numLocals=*/0) {
1159 assert(error && "expected a valid error flag");
1160 assert((operands.empty() || set.getNumInputs() == operands.size()) &&
1161 "operand count mismatch");
1162 *error = false;
1163 // Set the values for the non-local variables.
1164 for (unsigned i = 0, e = operands.size(); i < e; ++i)
1165 setValue(pos: i, val: operands[i]);
1166
1167 // Flatten expressions and add them to the constraint system.
1168 std::vector<SmallVector<int64_t, 8>> flatExprs;
1169 FlatLinearConstraints localVarCst;
1170 if (failed(Result: getFlattenedAffineExprs(set, flattenedExprs: &flatExprs, localVarCst: &localVarCst))) {
1171 // Flattening is unimplemented for semi-affine integer sets.
1172 *error = true;
1173 return;
1174 }
1175 assert(flatExprs.size() == set.getNumConstraints());
1176 insertVar(kind: VarKind::Local, pos: getNumVarKind(kind: VarKind::Local),
1177 /*num=*/localVarCst.getNumLocalVars());
1178
1179 for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
1180 const auto &flatExpr = flatExprs[i];
1181 assert(flatExpr.size() == getNumCols());
1182 if (set.getEqFlags()[i]) {
1183 addEquality(eq: flatExpr);
1184 } else {
1185 addInequality(inEq: flatExpr);
1186 }
1187 }
1188 // Add the other constraints involving local vars from flattening.
1189 append(other: localVarCst);
1190}
1191
1192FailureOr<FlatLinearValueConstraints>
1193FlatLinearValueConstraints::create(IntegerSet set, ValueRange operands) {
1194 bool error = false;
1195 FlatLinearValueConstraints cst(set, operands, &error);
1196 if (error)
1197 return failure();
1198 return cst;
1199}
1200
1201unsigned FlatLinearValueConstraints::appendDimVar(ValueRange vals) {
1202 unsigned pos = getNumDimVars();
1203 return insertVar(kind: VarKind::SetDim, pos, vals);
1204}
1205
1206unsigned FlatLinearValueConstraints::appendSymbolVar(ValueRange vals) {
1207 unsigned pos = getNumSymbolVars();
1208 return insertVar(kind: VarKind::Symbol, pos, vals);
1209}
1210
1211unsigned FlatLinearValueConstraints::insertDimVar(unsigned pos,
1212 ValueRange vals) {
1213 return insertVar(kind: VarKind::SetDim, pos, vals);
1214}
1215
1216unsigned FlatLinearValueConstraints::insertSymbolVar(unsigned pos,
1217 ValueRange vals) {
1218 return insertVar(kind: VarKind::Symbol, pos, vals);
1219}
1220
1221unsigned FlatLinearValueConstraints::insertVar(VarKind kind, unsigned pos,
1222 unsigned num) {
1223 unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
1224
1225 return absolutePos;
1226}
1227
1228unsigned FlatLinearValueConstraints::insertVar(VarKind kind, unsigned pos,
1229 ValueRange vals) {
1230 assert(!vals.empty() && "expected ValueRange with Values.");
1231 assert(kind != VarKind::Local &&
1232 "values cannot be attached to local variables.");
1233 unsigned num = vals.size();
1234 unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
1235
1236 // If a Value is provided, insert it; otherwise use std::nullopt.
1237 for (unsigned i = 0, e = vals.size(); i < e; ++i)
1238 if (vals[i])
1239 setValue(pos: absolutePos + i, val: vals[i]);
1240
1241 return absolutePos;
1242}
1243
1244/// Checks if two constraint systems are in the same space, i.e., if they are
1245/// associated with the same set of variables, appearing in the same order.
1246static bool areVarsAligned(const FlatLinearValueConstraints &a,
1247 const FlatLinearValueConstraints &b) {
1248 if (a.getNumDomainVars() != b.getNumDomainVars() ||
1249 a.getNumRangeVars() != b.getNumRangeVars() ||
1250 a.getNumSymbolVars() != b.getNumSymbolVars())
1251 return false;
1252 SmallVector<std::optional<Value>> aMaybeValues = a.getMaybeValues(),
1253 bMaybeValues = b.getMaybeValues();
1254 return std::equal(first1: aMaybeValues.begin(), last1: aMaybeValues.end(),
1255 first2: bMaybeValues.begin(), last2: bMaybeValues.end());
1256}
1257
1258/// Calls areVarsAligned to check if two constraint systems have the same set
1259/// of variables in the same order.
1260bool FlatLinearValueConstraints::areVarsAlignedWithOther(
1261 const FlatLinearConstraints &other) {
1262 return areVarsAligned(a: *this, b: other);
1263}
1264
1265/// Checks if the SSA values associated with `cst`'s variables in range
1266/// [start, end) are unique.
1267[[maybe_unused]] static bool
1268areVarsUnique(const FlatLinearValueConstraints &cst, unsigned start,
1269 unsigned end) {
1270
1271 assert(start <= cst.getNumDimAndSymbolVars() &&
1272 "Start position out of bounds");
1273 assert(end <= cst.getNumDimAndSymbolVars() && "End position out of bounds");
1274
1275 if (start >= end)
1276 return true;
1277
1278 SmallPtrSet<Value, 8> uniqueVars;
1279 SmallVector<std::optional<Value>, 8> maybeValuesAll = cst.getMaybeValues();
1280 ArrayRef<std::optional<Value>> maybeValues = {maybeValuesAll.data() + start,
1281 maybeValuesAll.data() + end};
1282
1283 for (std::optional<Value> val : maybeValues)
1284 if (val && !uniqueVars.insert(Ptr: *val).second)
1285 return false;
1286
1287 return true;
1288}
1289
1290/// Checks if the SSA values associated with `cst`'s variables are unique.
1291[[maybe_unused]] static bool
1292areVarsUnique(const FlatLinearValueConstraints &cst) {
1293 return areVarsUnique(cst, start: 0, end: cst.getNumDimAndSymbolVars());
1294}
1295
1296/// Checks if the SSA values associated with `cst`'s variables of kind `kind`
1297/// are unique.
1298[[maybe_unused]] static bool
1299areVarsUnique(const FlatLinearValueConstraints &cst, VarKind kind) {
1300
1301 if (kind == VarKind::SetDim)
1302 return areVarsUnique(cst, start: 0, end: cst.getNumDimVars());
1303 if (kind == VarKind::Symbol)
1304 return areVarsUnique(cst, start: cst.getNumDimVars(),
1305 end: cst.getNumDimAndSymbolVars());
1306 llvm_unreachable("Unexpected VarKind");
1307}
1308
1309/// Merge and align the variables of A and B starting at 'offset', so that
1310/// both constraint systems get the union of the contained variables that is
1311/// dimension-wise and symbol-wise unique; both constraint systems are updated
1312/// so that they have the union of all variables, with A's original
1313/// variables appearing first followed by any of B's variables that didn't
1314/// appear in A. Local variables in B that have the same division
1315/// representation as local variables in A are merged into one. We allow A
1316/// and B to have non-unique values for their variables; in such cases, they are
1317/// still aligned with the variables appearing first aligned with those
1318/// appearing first in the other system from left to right.
1319// E.g.: Input: A has ((%i, %j) [%M, %N]) and B has (%k, %j) [%P, %N, %M])
1320// Output: both A, B have (%i, %j, %k) [%M, %N, %P]
1321static void mergeAndAlignVars(unsigned offset, FlatLinearValueConstraints *a,
1322 FlatLinearValueConstraints *b) {
1323 assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
1324
1325 assert(llvm::all_of(
1326 llvm::drop_begin(a->getMaybeValues(), offset),
1327 [](const std::optional<Value> &var) { return var.has_value(); }));
1328
1329 assert(llvm::all_of(
1330 llvm::drop_begin(b->getMaybeValues(), offset),
1331 [](const std::optional<Value> &var) { return var.has_value(); }));
1332
1333 SmallVector<Value, 4> aDimValues;
1334 a->getValues(start: offset, end: a->getNumDimVars(), values: &aDimValues);
1335
1336 {
1337 // Merge dims from A into B.
1338 unsigned d = offset;
1339 for (Value aDimValue : aDimValues) {
1340 unsigned loc;
1341 // Find from the position `d` since we'd like to also consider the
1342 // possibility of multiple variables with the same `Value`. We align with
1343 // the next appearing one.
1344 if (b->findVar(val: aDimValue, pos: &loc, offset: d)) {
1345 assert(loc >= offset && "A's dim appears in B's aligned range");
1346 assert(loc < b->getNumDimVars() &&
1347 "A's dim appears in B's non-dim position");
1348 b->swapVar(posA: d, posB: loc);
1349 } else {
1350 b->insertDimVar(pos: d, vals: aDimValue);
1351 }
1352 d++;
1353 }
1354 // Dimensions that are in B, but not in A, are added at the end.
1355 for (unsigned t = a->getNumDimVars(), e = b->getNumDimVars(); t < e; t++) {
1356 a->appendDimVar(vals: b->getValue(pos: t));
1357 }
1358 assert(a->getNumDimVars() == b->getNumDimVars() &&
1359 "expected same number of dims");
1360 }
1361
1362 // Merge and align symbols of A and B
1363 a->mergeSymbolVars(other&: *b);
1364 // Merge and align locals of A and B
1365 a->mergeLocalVars(other&: *b);
1366
1367 assert(areVarsAligned(*a, *b) && "IDs expected to be aligned");
1368}
1369
1370// Call 'mergeAndAlignVars' to align constraint systems of 'this' and 'other'.
1371void FlatLinearValueConstraints::mergeAndAlignVarsWithOther(
1372 unsigned offset, FlatLinearValueConstraints *other) {
1373 mergeAndAlignVars(offset, a: this, b: other);
1374}
1375
1376/// Merge and align symbols of `this` and `other` such that both get union of
1377/// of symbols. Existing symbols need not be unique; they will be aligned from
1378/// left to right with duplicates aligned in the same order. Symbols with Value
1379/// as `None` are considered to be inequal to all other symbols.
1380void FlatLinearValueConstraints::mergeSymbolVars(
1381 FlatLinearValueConstraints &other) {
1382
1383 SmallVector<Value, 4> aSymValues;
1384 getValues(start: getNumDimVars(), end: getNumDimAndSymbolVars(), values: &aSymValues);
1385
1386 // Merge symbols: merge symbols into `other` first from `this`.
1387 unsigned s = other.getNumDimVars();
1388 for (Value aSymValue : aSymValues) {
1389 unsigned loc;
1390 // If the var is a symbol in `other`, then align it, otherwise assume that
1391 // it is a new symbol. Search in `other` starting at position `s` since the
1392 // left of it is aligned.
1393 if (other.findVar(val: aSymValue, pos: &loc, offset: s) && loc >= other.getNumDimVars() &&
1394 loc < other.getNumDimAndSymbolVars())
1395 other.swapVar(posA: s, posB: loc);
1396 else
1397 other.insertSymbolVar(pos: s - other.getNumDimVars(), vals: aSymValue);
1398 s++;
1399 }
1400
1401 // Symbols that are in other, but not in this, are added at the end.
1402 for (unsigned t = other.getNumDimVars() + getNumSymbolVars(),
1403 e = other.getNumDimAndSymbolVars();
1404 t < e; t++)
1405 insertSymbolVar(pos: getNumSymbolVars(), vals: other.getValue(pos: t));
1406
1407 assert(getNumSymbolVars() == other.getNumSymbolVars() &&
1408 "expected same number of symbols");
1409}
1410
1411void FlatLinearValueConstraints::removeVarRange(VarKind kind, unsigned varStart,
1412 unsigned varLimit) {
1413 IntegerPolyhedron::removeVarRange(kind, varStart, varLimit);
1414}
1415
1416AffineMap
1417FlatLinearValueConstraints::computeAlignedMap(AffineMap map,
1418 ValueRange operands) const {
1419 assert(map.getNumInputs() == operands.size() && "number of inputs mismatch");
1420
1421 SmallVector<Value> dims, syms;
1422#ifndef NDEBUG
1423 SmallVector<Value> newSyms;
1424 SmallVector<Value> *newSymsPtr = &newSyms;
1425#else
1426 SmallVector<Value> *newSymsPtr = nullptr;
1427#endif // NDEBUG
1428
1429 dims.reserve(N: getNumDimVars());
1430 syms.reserve(N: getNumSymbolVars());
1431 for (unsigned i = 0, e = getNumVarKind(kind: VarKind::SetDim); i < e; ++i) {
1432 Identifier id = space.getId(kind: VarKind::SetDim, pos: i);
1433 dims.push_back(Elt: id.hasValue() ? Value(id.getValue<Value>()) : Value());
1434 }
1435 for (unsigned i = 0, e = getNumVarKind(kind: VarKind::Symbol); i < e; ++i) {
1436 Identifier id = space.getId(kind: VarKind::Symbol, pos: i);
1437 syms.push_back(Elt: id.hasValue() ? Value(id.getValue<Value>()) : Value());
1438 }
1439
1440 AffineMap alignedMap =
1441 alignAffineMapWithValues(map, operands, dims, syms, newSyms: newSymsPtr);
1442 // All symbols are already part of this FlatAffineValueConstraints.
1443 assert(syms.size() == newSymsPtr->size() && "unexpected new/missing symbols");
1444 assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
1445 "unexpected new/missing symbols");
1446 return alignedMap;
1447}
1448
1449bool FlatLinearValueConstraints::findVar(Value val, unsigned *pos,
1450 unsigned offset) const {
1451 SmallVector<std::optional<Value>> maybeValues = getMaybeValues();
1452 for (unsigned i = offset, e = maybeValues.size(); i < e; ++i)
1453 if (maybeValues[i] && maybeValues[i].value() == val) {
1454 *pos = i;
1455 return true;
1456 }
1457 return false;
1458}
1459
1460bool FlatLinearValueConstraints::containsVar(Value val) const {
1461 unsigned pos;
1462 return findVar(val, pos: &pos, offset: 0);
1463}
1464
1465void FlatLinearValueConstraints::addBound(BoundType type, Value val,
1466 int64_t value) {
1467 unsigned pos;
1468 if (!findVar(val, pos: &pos))
1469 // This is a pre-condition for this method.
1470 assert(0 && "var not found");
1471 addBound(type, pos, value);
1472}
1473
1474void FlatLinearConstraints::printSpace(raw_ostream &os) const {
1475 IntegerPolyhedron::printSpace(os);
1476 os << "(";
1477 for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++)
1478 os << "None\t";
1479 for (unsigned i = getVarKindOffset(kind: VarKind::Local),
1480 e = getVarKindEnd(kind: VarKind::Local);
1481 i < e; ++i)
1482 os << "Local\t";
1483 os << "const)\n";
1484}
1485
1486void FlatLinearValueConstraints::printSpace(raw_ostream &os) const {
1487 IntegerPolyhedron::printSpace(os);
1488 os << "(";
1489 for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++) {
1490 if (hasValue(pos: i))
1491 os << "Value\t";
1492 else
1493 os << "None\t";
1494 }
1495 for (unsigned i = getVarKindOffset(kind: VarKind::Local),
1496 e = getVarKindEnd(kind: VarKind::Local);
1497 i < e; ++i)
1498 os << "Local\t";
1499 os << "const)\n";
1500}
1501
1502void FlatLinearValueConstraints::projectOut(Value val) {
1503 unsigned pos;
1504 bool ret = findVar(val, pos: &pos);
1505 assert(ret);
1506 (void)ret;
1507 fourierMotzkinEliminate(pos);
1508}
1509
1510LogicalResult FlatLinearValueConstraints::unionBoundingBox(
1511 const FlatLinearValueConstraints &otherCst) {
1512 assert(otherCst.getNumDimVars() == getNumDimVars() && "dims mismatch");
1513 SmallVector<std::optional<Value>> maybeValues = getMaybeValues(),
1514 otherMaybeValues =
1515 otherCst.getMaybeValues();
1516 assert(std::equal(maybeValues.begin(), maybeValues.begin() + getNumDimVars(),
1517 otherMaybeValues.begin(),
1518 otherMaybeValues.begin() + getNumDimVars()) &&
1519 "dim values mismatch");
1520 assert(otherCst.getNumLocalVars() == 0 && "local vars not supported here");
1521 assert(getNumLocalVars() == 0 && "local vars not supported yet here");
1522
1523 // Align `other` to this.
1524 if (!areVarsAligned(a: *this, b: otherCst)) {
1525 FlatLinearValueConstraints otherCopy(otherCst);
1526 mergeAndAlignVars(/*offset=*/getNumDimVars(), a: this, b: &otherCopy);
1527 return IntegerPolyhedron::unionBoundingBox(other: otherCopy);
1528 }
1529
1530 return IntegerPolyhedron::unionBoundingBox(other: otherCst);
1531}
1532
1533//===----------------------------------------------------------------------===//
1534// Helper functions
1535//===----------------------------------------------------------------------===//
1536
1537AffineMap mlir::alignAffineMapWithValues(AffineMap map, ValueRange operands,
1538 ValueRange dims, ValueRange syms,
1539 SmallVector<Value> *newSyms) {
1540 assert(operands.size() == map.getNumInputs() &&
1541 "expected same number of operands and map inputs");
1542 MLIRContext *ctx = map.getContext();
1543 Builder builder(ctx);
1544 SmallVector<AffineExpr> dimReplacements(map.getNumDims(), {});
1545 unsigned numSymbols = syms.size();
1546 SmallVector<AffineExpr> symReplacements(map.getNumSymbols(), {});
1547 if (newSyms) {
1548 newSyms->clear();
1549 newSyms->append(in_start: syms.begin(), in_end: syms.end());
1550 }
1551
1552 for (const auto &operand : llvm::enumerate(First&: operands)) {
1553 // Compute replacement dim/sym of operand.
1554 AffineExpr replacement;
1555 auto dimIt = llvm::find(Range&: dims, Val: operand.value());
1556 auto symIt = llvm::find(Range&: syms, Val: operand.value());
1557 if (dimIt != dims.end()) {
1558 replacement =
1559 builder.getAffineDimExpr(position: std::distance(first: dims.begin(), last: dimIt));
1560 } else if (symIt != syms.end()) {
1561 replacement =
1562 builder.getAffineSymbolExpr(position: std::distance(first: syms.begin(), last: symIt));
1563 } else {
1564 // This operand is neither a dimension nor a symbol. Add it as a new
1565 // symbol.
1566 replacement = builder.getAffineSymbolExpr(position: numSymbols++);
1567 if (newSyms)
1568 newSyms->push_back(Elt: operand.value());
1569 }
1570 // Add to corresponding replacements vector.
1571 if (operand.index() < map.getNumDims()) {
1572 dimReplacements[operand.index()] = replacement;
1573 } else {
1574 symReplacements[operand.index() - map.getNumDims()] = replacement;
1575 }
1576 }
1577
1578 return map.replaceDimsAndSymbols(dimReplacements, symReplacements,
1579 numResultDims: dims.size(), numResultSyms: numSymbols);
1580}
1581
1582LogicalResult
1583mlir::getMultiAffineFunctionFromMap(AffineMap map,
1584 MultiAffineFunction &multiAff) {
1585 FlatLinearConstraints cst;
1586 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
1587 LogicalResult result = getFlattenedAffineExprs(map, flattenedExprs: &flattenedExprs, localVarCst: &cst);
1588
1589 if (result.failed())
1590 return failure();
1591
1592 DivisionRepr divs = cst.getLocalReprs();
1593 assert(divs.hasAllReprs() &&
1594 "AffineMap cannot produce divs without local representation");
1595
1596 // TODO: We shouldn't have to do this conversion.
1597 Matrix<DynamicAPInt> mat(map.getNumResults(),
1598 map.getNumInputs() + divs.getNumDivs() + 1);
1599 for (unsigned i = 0, e = flattenedExprs.size(); i < e; ++i)
1600 for (unsigned j = 0, f = flattenedExprs[i].size(); j < f; ++j)
1601 mat(i, j) = flattenedExprs[i][j];
1602
1603 multiAff = MultiAffineFunction(
1604 PresburgerSpace::getRelationSpace(numDomain: map.getNumDims(), numRange: map.getNumResults(),
1605 numSymbols: map.getNumSymbols(), numLocals: divs.getNumDivs()),
1606 mat, divs);
1607
1608 return success();
1609}
1610