MLIR  21.0.0git
FlatLinearValueConstraints.cpp
Go to the documentation of this file.
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 
10 
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 
27 using namespace mlir;
28 using namespace presburger;
29 
30 //===----------------------------------------------------------------------===//
31 // AffineExprFlattener
32 //===----------------------------------------------------------------------===//
33 
34 namespace {
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'.
40 struct AffineExprFlattener : public 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(nDims, nSymbols)) {};
51 
52 private:
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  localVarCst.addLocalFloorDiv(dividend, divisor);
64  }
65 
66  LogicalResult addLocalIdSemiAffine(ArrayRef<int64_t> lhs,
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.
80 struct SemiAffineExprFlattener : public AffineExprFlattener {
81  using AffineExprFlattener::AffineExprFlattener;
82 
83  LogicalResult addLocalIdSemiAffine(ArrayRef<int64_t> lhs,
85  AffineExpr localExpr) override {
86  auto result =
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(VarKind::Local);
103 
104  // r >= 0 (Can ALWAYS be added)
105  localVarCst.addBound(BoundType::LB, rPos, 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(bSubR.begin() + rPos, -1);
111  // Note: bSubR = b - r
112  // So this adds the bound b - r >= 1 (equivalent to r < b)
113  localVarCst.addBound(BoundType::LB, bSubR, 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).
134 static LogicalResult
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(flattenResult))
152  return failure();
153  }
154 
155  assert(flattener.operandExprStack.size() == exprs.size());
156  flattenedExprs->clear();
157  flattenedExprs->assign(flattener.operandExprStack.begin(),
158  flattener.operandExprStack.end());
159 
160  if (localVarCst)
161  localVarCst->clearAndCopyFrom(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).
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({expr}, numDims, numSymbols, &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).
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 =
198  return success();
199  }
201  map.getResults(), map.getNumDims(), map.getNumSymbols(), flattenedExprs,
202  localVarCst, addConservativeSemiAffineBounds);
203 }
204 
206  IntegerSet set, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
207  FlatLinearConstraints *localVarCst) {
208  if (set.getNumConstraints() == 0) {
209  if (localVarCst)
210  *localVarCst =
212  return success();
213  }
215  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.
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(flattenAlignedMapAndMergeLocals(other, &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(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.
301 static bool detectAsMod(const FlatLinearConstraints &cst, unsigned pos,
302  unsigned offset, unsigned num, int64_t lbConst,
303  int64_t ubConst, MLIRContext *context,
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(curEquality, 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(curEquality, 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(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(curEquality, 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(coefficientAtPos);
370  else
371  dividendExpr = dividendExpr.floorDiv(-coefficientAtPos);
372 
373  // Simplify the expression.
374  dividendExpr = simplifyAffineExpr(dividendExpr, cst.getNumDimVars(),
375  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>(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(BoundType::UB, 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(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.
417 static bool detectAsFloorDiv(const FlatLinearConstraints &cst, unsigned pos,
418  MLIRContext *context,
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(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(divisor);
444  return true;
445 }
446 
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(7);
457  } else {
458  llvm::errs() << ((row[j] >= 0) ? "+ " : "") << row[j] << ' ';
459  }
460  } else {
461  std::string var = std::string("c_") + std::to_string(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(7);
473  if (row[j] != 0)
474  firstNonZero = false;
475  }
476  }
477 }
478 
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?
487  isEq ? getEquality64(rowPos) : getInequality64(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 
499 std::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 + offset, &lbIndices, &ubIndices, &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(a[i]);
518  }
519  };
520 
523  unsigned dimCount = symStartPos - num;
524  unsigned symCount = getNumDimAndSymbolVars() - symStartPos;
525  lbExprs.reserve(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  std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
534  auto expr =
535  getAffineExprFromFlatForm(lb, dimCount, symCount, localExprs, context);
536  // expr ceildiv divisor is (expr + divisor - 1) floordiv divisor
537  int64_t divisor = std::abs(ineq[pos + offset]);
538  expr = (expr + divisor - 1).floorDiv(divisor);
539  lbExprs.push_back(expr);
540  }
541 
543  ubExprs.reserve(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(ub, dimCount, symCount, localExprs, context);
551  expr = expr.floorDiv(std::abs(ineq[pos + offset]));
552  int64_t ubAdjustment = closedUB ? 0 : 1;
553  ubExprs.push_back(expr + ubAdjustment);
554  }
555 
556  // Equalities. It's both a lower and a upper bound.
558  for (auto idx : eqIndices) {
559  auto eq = getEquality64(idx);
560  addCoeffs(eq, b);
561  if (eq[pos + offset] > 0)
562  std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());
563 
564  // Extract the upper bound (in terms of other coeff's + const).
565  auto expr =
566  getAffineExprFromFlatForm(b, dimCount, symCount, localExprs, context);
567  expr = expr.floorDiv(std::abs(eq[pos + offset]));
568  // Upper bound is exclusive.
569  ubExprs.push_back(expr + 1);
570  // Lower bound.
571  expr =
572  getAffineExprFromFlatForm(b, dimCount, symCount, localExprs, context);
573  expr = expr.ceilDiv(std::abs(eq[pos + offset]));
574  lbExprs.push_back(expr);
575  }
576 
577  auto lbMap = AffineMap::get(dimCount, symCount, lbExprs, context);
578  auto ubMap = AffineMap::get(dimCount, symCount, 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.
587 static bool detectAsExpr(const FlatLinearConstraints &cst, unsigned pos,
588  unsigned idx, MLIRContext *context,
590  // Initialize with a `0` expression.
591  auto expr = getAffineConstantExpr(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(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(idx, cst.getNumVars());
614  int64_t vPos = cst.atEq64(idx, pos);
615  assert(vPos != 0 && "expected non-zero here");
616  if (vPos > 0)
617  expr = (-expr).floorDiv(vPos);
618  else
619  // vPos < 0.
620  expr = expr.floorDiv(-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`.
630  MLIRContext *context, unsigned offset,
631  unsigned num,
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(i, context);
637  else if (i >= offset + num)
638  memo[i] = getAffineDimExpr(i - num, context);
639  }
640  for (unsigned i = cst.getNumDimVars(), e = cst.getNumDimAndSymbolVars();
641  i < e; i++)
642  memo[i] = getAffineSymbolExpr(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(BoundType::LB, pos);
654  auto ubConst = cst.getConstantBound64(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(*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, *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, 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(pos, /*isEq=*/true)))
682  continue;
683 
684  if (detectAsExpr(cst, pos, *idx, context, 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.
700 void FlatLinearConstraints::getSliceBounds(unsigned offset, unsigned num,
701  MLIRContext *context,
704  bool closedUB) {
705  assert(offset + num <= getNumDimVars() && "invalid range");
706 
707  // Basic simplification.
708  normalizeConstraintsByGCD();
709 
710  LLVM_DEBUG(llvm::dbgs() << "getSliceBounds for variables at positions ["
711  << offset << ", " << offset + num << ")\n");
712  LLVM_DEBUG(dumpPretty());
713 
714  // Record computed/detected variables.
715  SmallVector<AffineExpr, 8> memo(getNumVars());
716  computeUnknownVars(*this, context, offset, num, memo);
717 
718  int64_t ubAdjustment = closedUB ? 0 : 1;
719 
720  // Set the lower and upper bound maps for all the variables that were
721  // computed as affine expressions of the rest as the "detected expr" and
722  // "detected expr + 1" respectively; set the undetected ones to null.
723  std::optional<FlatLinearConstraints> tmpClone;
724  for (unsigned pos = 0; pos < num; pos++) {
725  unsigned numMapDims = getNumDimVars() - num;
726  unsigned numMapSymbols = getNumSymbolVars();
727  AffineExpr expr = memo[pos + offset];
728  if (expr)
729  expr = simplifyAffineExpr(expr, numMapDims, numMapSymbols);
730 
731  AffineMap &lbMap = (*lbMaps)[pos];
732  AffineMap &ubMap = (*ubMaps)[pos];
733 
734  if (expr) {
735  lbMap = AffineMap::get(numMapDims, numMapSymbols, expr);
736  ubMap = AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
737  } else {
738  // TODO: Whenever there are local variables in the dependence
739  // constraints, we'll conservatively over-approximate, since we don't
740  // always explicitly compute them above (in the while loop).
741  if (getNumLocalVars() == 0) {
742  // Work on a copy so that we don't update this constraint system.
743  if (!tmpClone) {
744  tmpClone.emplace(FlatLinearConstraints(*this));
745  // Removing redundant inequalities is necessary so that we don't get
746  // redundant loop bounds.
747  tmpClone->removeRedundantInequalities();
748  }
749  std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
750  pos, offset, num, getNumDimVars(), /*localExprs=*/{}, context,
751  closedUB);
752  }
753 
754  // If the above fails, we'll just use the constant lower bound and the
755  // constant upper bound (if they exist) as the slice bounds.
756  // TODO: being conservative for the moment in cases that
757  // lead to multiple bounds - until getConstDifference in LoopFusion.cpp is
758  // fixed (b/126426796).
759  if (!lbMap || lbMap.getNumResults() != 1) {
760  LLVM_DEBUG(llvm::dbgs()
761  << "WARNING: Potentially over-approximating slice lb\n");
762  auto lbConst = getConstantBound64(BoundType::LB, pos + offset);
763  if (lbConst.has_value()) {
764  lbMap = AffineMap::get(numMapDims, numMapSymbols,
765  getAffineConstantExpr(*lbConst, context));
766  }
767  }
768  if (!ubMap || ubMap.getNumResults() != 1) {
769  LLVM_DEBUG(llvm::dbgs()
770  << "WARNING: Potentially over-approximating slice ub\n");
771  auto ubConst = getConstantBound64(BoundType::UB, pos + offset);
772  if (ubConst.has_value()) {
773  ubMap = AffineMap::get(
774  numMapDims, numMapSymbols,
775  getAffineConstantExpr(*ubConst + ubAdjustment, context));
776  }
777  }
778  }
779 
780  LLVM_DEBUG(llvm::dbgs() << "Slice bounds:\n");
781  LLVM_DEBUG(llvm::dbgs() << "lb map for pos = " << Twine(pos + offset)
782  << ", expr: " << lbMap << '\n');
783  LLVM_DEBUG(llvm::dbgs() << "ub map for pos = " << Twine(pos + offset)
784  << ", expr: " << ubMap << '\n');
785  }
786 }
787 
789  AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
790  bool addConservativeSemiAffineBounds) {
791  FlatLinearConstraints localCst;
792  if (failed(getFlattenedAffineExprs(map, flattenedExprs, &localCst,
793  addConservativeSemiAffineBounds))) {
794  LLVM_DEBUG(llvm::dbgs()
795  << "composition unimplemented for semi-affine maps\n");
796  return failure();
797  }
798 
799  // Add localCst information.
800  if (localCst.getNumLocalVars() > 0) {
801  unsigned numLocalVars = getNumLocalVars();
802  // Insert local dims of localCst at the beginning.
803  insertLocalVar(/*pos=*/0, /*num=*/localCst.getNumLocalVars());
804  // Insert local dims of `this` at the end of localCst.
805  localCst.appendLocalVar(/*num=*/numLocalVars);
806  // Dimensions of localCst and this constraint set match. Append localCst to
807  // this constraint set.
808  append(localCst);
809  }
810 
811  return success();
812 }
813 
815  BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound,
816  AddConservativeSemiAffineBounds addSemiAffineBounds) {
817  assert(boundMap.getNumDims() == getNumDimVars() && "dim mismatch");
818  assert(boundMap.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");
819  assert(pos < getNumDimAndSymbolVars() && "invalid position");
820  assert((type != BoundType::EQ || isClosedBound) &&
821  "EQ bound must be closed.");
822 
823  // Equality follows the logic of lower bound except that we add an equality
824  // instead of an inequality.
825  assert((type != BoundType::EQ || boundMap.getNumResults() == 1) &&
826  "single result expected");
827  bool lower = type == BoundType::LB || type == BoundType::EQ;
828 
829  std::vector<SmallVector<int64_t, 8>> flatExprs;
830  if (failed(flattenAlignedMapAndMergeLocals(
831  boundMap, &flatExprs,
832  addSemiAffineBounds == AddConservativeSemiAffineBounds::Yes)))
833  return failure();
834  assert(flatExprs.size() == boundMap.getNumResults());
835 
836  // Add one (in)equality for each result.
837  for (const auto &flatExpr : flatExprs) {
838  SmallVector<int64_t> ineq(getNumCols(), 0);
839  // Dims and symbols.
840  for (unsigned j = 0, e = boundMap.getNumInputs(); j < e; j++) {
841  ineq[j] = lower ? -flatExpr[j] : flatExpr[j];
842  }
843  // Invalid bound: pos appears in `boundMap`.
844  // TODO: This should be an assertion. Fix `addDomainFromSliceMaps` and/or
845  // its callers to prevent invalid bounds from being added.
846  if (ineq[pos] != 0)
847  continue;
848  ineq[pos] = lower ? 1 : -1;
849  // Local columns of `ineq` are at the beginning.
850  unsigned j = getNumDimVars() + getNumSymbolVars();
851  unsigned end = flatExpr.size() - 1;
852  for (unsigned i = boundMap.getNumInputs(); i < end; i++, j++) {
853  ineq[j] = lower ? -flatExpr[i] : flatExpr[i];
854  }
855  // Make the bound closed in if flatExpr is open. The inequality is always
856  // created in the upper bound form, so the adjustment is -1.
857  int64_t boundAdjustment = (isClosedBound || type == BoundType::EQ) ? 0 : -1;
858  // Constant term.
859  ineq[getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
860  : flatExpr[flatExpr.size() - 1]) +
861  boundAdjustment;
862  type == BoundType::EQ ? addEquality(ineq) : addInequality(ineq);
863  }
864 
865  return success();
866 }
867 
869  BoundType type, unsigned pos, AffineMap boundMap,
870  AddConservativeSemiAffineBounds addSemiAffineBounds) {
871  return addBound(type, pos, boundMap,
872  /*isClosedBound=*/type != BoundType::UB, addSemiAffineBounds);
873 }
874 
875 /// Compute an explicit representation for local vars. For all systems coming
876 /// from MLIR integer sets, maps, or expressions where local vars were
877 /// introduced to model floordivs and mods, this always succeeds.
878 LogicalResult
880  MLIRContext *context) const {
881  unsigned numDims = getNumDimVars();
882  unsigned numSyms = getNumSymbolVars();
883 
884  // Initialize dimensional and symbolic variables.
885  for (unsigned i = 0; i < numDims; i++)
886  memo[i] = getAffineDimExpr(i, context);
887  for (unsigned i = numDims, e = numDims + numSyms; i < e; i++)
888  memo[i] = getAffineSymbolExpr(i - numDims, context);
889 
890  bool changed;
891  do {
892  // Each time `changed` is true at the end of this iteration, one or more
893  // local vars would have been detected as floordivs and set in memo; so the
894  // number of null entries in memo[...] strictly reduces; so this converges.
895  changed = false;
896  for (unsigned i = 0, e = getNumLocalVars(); i < e; ++i)
897  if (!memo[numDims + numSyms + i] &&
898  detectAsFloorDiv(*this, /*pos=*/numDims + numSyms + i, context, memo))
899  changed = true;
900  } while (changed);
901 
902  ArrayRef<AffineExpr> localExprs =
903  ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());
904  return success(
905  llvm::all_of(localExprs, [](AffineExpr expr) { return expr; }));
906 }
907 
908 /// Given an equality or inequality (`isEquality` used to disambiguate) of `cst`
909 /// at `idx`, traverse and sum up `AffineExpr`s of all known ids other than the
910 /// `pos`th. Known `AffineExpr`s are given in `exprs` (unknowns are null). If
911 /// the equality/inequality contains any unknown id, return None. Otherwise
912 /// return sum as `AffineExpr`.
913 static std::optional<AffineExpr> getAsExpr(const FlatLinearConstraints &cst,
914  unsigned pos, MLIRContext *context,
915  ArrayRef<AffineExpr> exprs,
916  unsigned idx, bool isEquality) {
917  // Initialize with a `0` expression.
918  auto expr = getAffineConstantExpr(0, context);
919 
921  isEquality ? cst.getEquality64(idx) : cst.getInequality64(idx);
922 
923  // Traverse `idx`th equality and construct the possible affine expression in
924  // terms of known identifiers.
925  unsigned j, e;
926  for (j = 0, e = cst.getNumVars(); j < e; ++j) {
927  if (j == pos)
928  continue;
929  int64_t c = row[j];
930  if (c == 0)
931  continue;
932  // If any of the involved IDs hasn't been found yet, we can't proceed.
933  if (!exprs[j])
934  break;
935  expr = expr + exprs[j] * c;
936  }
937  if (j < e)
938  // Can't construct expression as it depends on a yet uncomputed
939  // identifier.
940  return std::nullopt;
941 
942  // Add constant term to AffineExpr.
943  expr = expr + row[cst.getNumVars()];
944  return expr;
945 }
946 
948  MLIRContext *context, unsigned pos, AffineMap *lb, AffineMap *ub,
949  unsigned *minLbPos, unsigned *minUbPos) const {
950 
951  assert(pos < getNumDimVars() && "Invalid identifier position");
952 
953  auto freeOfUnknownLocalVars = [&](ArrayRef<int64_t> cst,
954  ArrayRef<AffineExpr> whiteListCols) {
955  for (int i = getNumDimAndSymbolVars(), e = cst.size() - 1; i < e; ++i) {
956  if (whiteListCols[i] && whiteListCols[i].isSymbolicOrConstant())
957  continue;
958  if (cst[i] != 0)
959  return false;
960  }
961  return true;
962  };
963 
964  // Detect the necesary local variables first.
965  SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());
966  (void)computeLocalVars(memo, context);
967 
968  // Find an equality for 'pos'^th identifier that equates it to some function
969  // of the symbolic identifiers (+ constant).
970  int eqPos = findEqualityToConstant(pos, /*symbolic=*/true);
971  // If the equality involves a local var that can not be expressed as a
972  // symbolic or constant affine expression, we bail out.
973  if (eqPos != -1 && freeOfUnknownLocalVars(getEquality64(eqPos), memo)) {
974  // This identifier can only take a single value.
975  if (lb && detectAsExpr(*this, pos, eqPos, context, memo)) {
976  AffineExpr equalityExpr =
977  simplifyAffineExpr(memo[pos], 0, getNumSymbolVars());
978  *lb = AffineMap::get(/*dimCount=*/0, getNumSymbolVars(), equalityExpr);
979  if (ub)
980  *ub = *lb;
981  }
982  if (minLbPos)
983  *minLbPos = eqPos;
984  if (minUbPos)
985  *minUbPos = eqPos;
986  return 1;
987  }
988 
989  // Positions of constraints that are lower/upper bounds on the variable.
990  SmallVector<unsigned, 4> lbIndices, ubIndices;
991 
992  // Note inequalities that give lower and upper bounds.
993  getLowerAndUpperBoundIndices(pos, &lbIndices, &ubIndices,
994  /*eqIndices=*/nullptr, /*offset=*/0,
995  /*num=*/getNumDimVars());
996 
997  std::optional<int64_t> minDiff = std::nullopt;
998  unsigned minLbPosition = 0, minUbPosition = 0;
999  AffineExpr minLbExpr, minUbExpr;
1000 
1001  // Traverse each lower bound and upper bound pair, to compute the difference
1002  // between them.
1003  for (unsigned ubPos : ubIndices) {
1004  // Construct sum of all ids other than `pos`th in the given upper bound row.
1005  std::optional<AffineExpr> maybeUbExpr =
1006  getAsExpr(*this, pos, context, memo, ubPos, /*isEquality=*/false);
1007  if (!maybeUbExpr.has_value() || !(*maybeUbExpr).isSymbolicOrConstant())
1008  continue;
1009 
1010  // Canonical form of an inequality that constrains the upper bound on
1011  // an id `x_i` is of the form:
1012  // `c_1*x_1 + c_2*x_2 + ... + c_0 >= 0`, where `c_i` <= -1.
1013  // Therefore the upper bound on `x_i` will be
1014  // `(
1015  // sum(c_j*x_j) where j != i
1016  // +
1017  // c_0
1018  // )
1019  // /
1020  // -(c_i)`. Divison here is a floorDiv.
1021  AffineExpr ubExpr = maybeUbExpr->floorDiv(-atIneq64(ubPos, pos));
1022  assert(-atIneq64(ubPos, pos) > 0 && "invalid upper bound index");
1023 
1024  // Go over each lower bound.
1025  for (unsigned lbPos : lbIndices) {
1026  // Construct sum of all ids other than `pos`th in the given lower bound
1027  // row.
1028  std::optional<AffineExpr> maybeLbExpr =
1029  getAsExpr(*this, pos, context, memo, lbPos, /*isEquality=*/false);
1030  if (!maybeLbExpr.has_value() || !(*maybeLbExpr).isSymbolicOrConstant())
1031  continue;
1032 
1033  // Canonical form of an inequality that is constraining the lower bound
1034  // on an id `x_i is of the form:
1035  // `c_1*x_1 + c_2*x_2 + ... + c_0 >= 0`, where `c_i` >= 1.
1036  // Therefore upperBound on `x_i` will be
1037  // `-(
1038  // sum(c_j*x_j) where j != i
1039  // +
1040  // c_0
1041  // )
1042  // /
1043  // c_i`. Divison here is a ceilDiv.
1044  int64_t divisor = atIneq64(lbPos, pos);
1045  // We convert the `ceilDiv` for floordiv with the formula:
1046  // `expr ceildiv divisor is (expr + divisor - 1) floordiv divisor`,
1047  // since uniformly keeping divisons as `floorDiv` helps their
1048  // simplification.
1049  AffineExpr lbExpr = (-(*maybeLbExpr) + divisor - 1).floorDiv(divisor);
1050  assert(atIneq64(lbPos, pos) > 0 && "invalid lower bound index");
1051 
1052  AffineExpr difference =
1053  simplifyAffineExpr(ubExpr - lbExpr + 1, 0, getNumSymbolVars());
1054  // If the difference is not constant, ignore the lower bound - upper bound
1055  // pair.
1056  auto constantDiff = dyn_cast<AffineConstantExpr>(difference);
1057  if (!constantDiff)
1058  continue;
1059 
1060  int64_t diffValue = constantDiff.getValue();
1061  // This bound is non-negative by definition.
1062  diffValue = std::max<int64_t>(diffValue, 0);
1063  if (!minDiff || diffValue < *minDiff) {
1064  minDiff = diffValue;
1065  minLbPosition = lbPos;
1066  minUbPosition = ubPos;
1067  minLbExpr = lbExpr;
1068  minUbExpr = ubExpr;
1069  }
1070  }
1071  }
1072 
1073  // Populate outputs where available and needed.
1074  if (lb && minDiff) {
1075  *lb = AffineMap::get(/*dimCount=*/0, getNumSymbolVars(), minLbExpr);
1076  }
1077  if (ub)
1078  *ub = AffineMap::get(/*dimCount=*/0, getNumSymbolVars(), minUbExpr);
1079  if (minLbPos)
1080  *minLbPos = minLbPosition;
1081  if (minUbPos)
1082  *minUbPos = minUbPosition;
1083 
1084  return minDiff;
1085 }
1086 
1088  if (getNumConstraints() == 0)
1089  // Return universal set (always true): 0 == 0.
1090  return IntegerSet::get(getNumDimVars(), getNumSymbolVars(),
1091  getAffineConstantExpr(/*constant=*/0, context),
1092  /*eqFlags=*/true);
1093 
1094  // Construct local references.
1095  SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());
1096 
1097  if (failed(computeLocalVars(memo, context))) {
1098  // Check if the local variables without an explicit representation have
1099  // zero coefficients everywhere.
1100  SmallVector<unsigned> noLocalRepVars;
1101  unsigned numDimsSymbols = getNumDimAndSymbolVars();
1102  for (unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
1103  if (!memo[i] && !isColZero(/*pos=*/i))
1104  noLocalRepVars.push_back(i - numDimsSymbols);
1105  }
1106  if (!noLocalRepVars.empty()) {
1107  LLVM_DEBUG({
1108  llvm::dbgs() << "local variables at position(s) "
1109  << llvm::interleaved(noLocalRepVars)
1110  << " do not have an explicit representation in:\n";
1111  this->dump();
1112  });
1113  return IntegerSet();
1114  }
1115  }
1116 
1117  ArrayRef<AffineExpr> localExprs =
1118  ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());
1119 
1120  // Construct the IntegerSet from the equalities/inequalities.
1121  unsigned numDims = getNumDimVars();
1122  unsigned numSyms = getNumSymbolVars();
1123 
1124  SmallVector<bool, 16> eqFlags(getNumConstraints());
1125  std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(), true);
1126  std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(), false);
1127 
1129  exprs.reserve(getNumConstraints());
1130 
1131  for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
1132  exprs.push_back(getAffineExprFromFlatForm(getEquality64(i), numDims,
1133  numSyms, localExprs, context));
1134  for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
1135  exprs.push_back(getAffineExprFromFlatForm(getInequality64(i), numDims,
1136  numSyms, localExprs, context));
1137  return IntegerSet::get(numDims, numSyms, exprs, eqFlags);
1138 }
1139 
1140 //===----------------------------------------------------------------------===//
1141 // FlatLinearValueConstraints
1142 //===----------------------------------------------------------------------===//
1143 
1144 // Construct from an IntegerSet.
1146  ValueRange operands)
1147  : FlatLinearConstraints(set.getNumInequalities(), set.getNumEqualities(),
1148  set.getNumDims() + set.getNumSymbols() + 1,
1149  set.getNumDims(), set.getNumSymbols(),
1150  /*numLocals=*/0) {
1151  assert((operands.empty() || set.getNumInputs() == operands.size()) &&
1152  "operand count mismatch");
1153  // Set the values for the non-local variables.
1154  for (unsigned i = 0, e = operands.size(); i < e; ++i)
1155  setValue(i, operands[i]);
1156 
1157  // Flatten expressions and add them to the constraint system.
1158  std::vector<SmallVector<int64_t, 8>> flatExprs;
1159  FlatLinearConstraints localVarCst;
1160  if (failed(getFlattenedAffineExprs(set, &flatExprs, &localVarCst))) {
1161  assert(false && "flattening unimplemented for semi-affine integer sets");
1162  return;
1163  }
1164  assert(flatExprs.size() == set.getNumConstraints());
1165  insertVar(VarKind::Local, getNumVarKind(VarKind::Local),
1166  /*num=*/localVarCst.getNumLocalVars());
1167 
1168  for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
1169  const auto &flatExpr = flatExprs[i];
1170  assert(flatExpr.size() == getNumCols());
1171  if (set.getEqFlags()[i]) {
1172  addEquality(flatExpr);
1173  } else {
1174  addInequality(flatExpr);
1175  }
1176  }
1177  // Add the other constraints involving local vars from flattening.
1178  append(localVarCst);
1179 }
1180 
1182  unsigned pos = getNumDimVars();
1183  return insertVar(VarKind::SetDim, pos, vals);
1184 }
1185 
1187  unsigned pos = getNumSymbolVars();
1188  return insertVar(VarKind::Symbol, pos, vals);
1189 }
1190 
1192  ValueRange vals) {
1193  return insertVar(VarKind::SetDim, pos, vals);
1194 }
1195 
1197  ValueRange vals) {
1198  return insertVar(VarKind::Symbol, pos, vals);
1199 }
1200 
1202  unsigned num) {
1203  unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
1204 
1205  return absolutePos;
1206 }
1207 
1209  ValueRange vals) {
1210  assert(!vals.empty() && "expected ValueRange with Values.");
1211  assert(kind != VarKind::Local &&
1212  "values cannot be attached to local variables.");
1213  unsigned num = vals.size();
1214  unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
1215 
1216  // If a Value is provided, insert it; otherwise use std::nullopt.
1217  for (unsigned i = 0, e = vals.size(); i < e; ++i)
1218  if (vals[i])
1219  setValue(absolutePos + i, vals[i]);
1220 
1221  return absolutePos;
1222 }
1223 
1224 /// Checks if two constraint systems are in the same space, i.e., if they are
1225 /// associated with the same set of variables, appearing in the same order.
1227  const FlatLinearValueConstraints &b) {
1228  if (a.getNumDomainVars() != b.getNumDomainVars() ||
1229  a.getNumRangeVars() != b.getNumRangeVars() ||
1231  return false;
1233  bMaybeValues = b.getMaybeValues();
1234  return std::equal(aMaybeValues.begin(), aMaybeValues.end(),
1235  bMaybeValues.begin(), bMaybeValues.end());
1236 }
1237 
1238 /// Calls areVarsAligned to check if two constraint systems have the same set
1239 /// of variables in the same order.
1241  const FlatLinearConstraints &other) {
1242  return areVarsAligned(*this, other);
1243 }
1244 
1245 /// Checks if the SSA values associated with `cst`'s variables in range
1246 /// [start, end) are unique.
1247 static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique(
1248  const FlatLinearValueConstraints &cst, unsigned start, unsigned end) {
1249 
1250  assert(start <= cst.getNumDimAndSymbolVars() &&
1251  "Start position out of bounds");
1252  assert(end <= cst.getNumDimAndSymbolVars() && "End position out of bounds");
1253 
1254  if (start >= end)
1255  return true;
1256 
1257  SmallPtrSet<Value, 8> uniqueVars;
1258  SmallVector<std::optional<Value>, 8> maybeValuesAll = cst.getMaybeValues();
1259  ArrayRef<std::optional<Value>> maybeValues = {maybeValuesAll.data() + start,
1260  maybeValuesAll.data() + end};
1261 
1262  for (std::optional<Value> val : maybeValues)
1263  if (val && !uniqueVars.insert(*val).second)
1264  return false;
1265 
1266  return true;
1267 }
1268 
1269 /// Checks if the SSA values associated with `cst`'s variables are unique.
1270 static bool LLVM_ATTRIBUTE_UNUSED
1272  return areVarsUnique(cst, 0, cst.getNumDimAndSymbolVars());
1273 }
1274 
1275 /// Checks if the SSA values associated with `cst`'s variables of kind `kind`
1276 /// are unique.
1277 static bool LLVM_ATTRIBUTE_UNUSED
1279 
1280  if (kind == VarKind::SetDim)
1281  return areVarsUnique(cst, 0, cst.getNumDimVars());
1282  if (kind == VarKind::Symbol)
1283  return areVarsUnique(cst, cst.getNumDimVars(),
1284  cst.getNumDimAndSymbolVars());
1285  llvm_unreachable("Unexpected VarKind");
1286 }
1287 
1288 /// Merge and align the variables of A and B starting at 'offset', so that
1289 /// both constraint systems get the union of the contained variables that is
1290 /// dimension-wise and symbol-wise unique; both constraint systems are updated
1291 /// so that they have the union of all variables, with A's original
1292 /// variables appearing first followed by any of B's variables that didn't
1293 /// appear in A. Local variables in B that have the same division
1294 /// representation as local variables in A are merged into one. We allow A
1295 /// and B to have non-unique values for their variables; in such cases, they are
1296 /// still aligned with the variables appearing first aligned with those
1297 /// appearing first in the other system from left to right.
1298 // E.g.: Input: A has ((%i, %j) [%M, %N]) and B has (%k, %j) [%P, %N, %M])
1299 // Output: both A, B have (%i, %j, %k) [%M, %N, %P]
1300 static void mergeAndAlignVars(unsigned offset, FlatLinearValueConstraints *a,
1302  assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
1303 
1304  assert(llvm::all_of(
1305  llvm::drop_begin(a->getMaybeValues(), offset),
1306  [](const std::optional<Value> &var) { return var.has_value(); }));
1307 
1308  assert(llvm::all_of(
1309  llvm::drop_begin(b->getMaybeValues(), offset),
1310  [](const std::optional<Value> &var) { return var.has_value(); }));
1311 
1312  SmallVector<Value, 4> aDimValues;
1313  a->getValues(offset, a->getNumDimVars(), &aDimValues);
1314 
1315  {
1316  // Merge dims from A into B.
1317  unsigned d = offset;
1318  for (Value aDimValue : aDimValues) {
1319  unsigned loc;
1320  // Find from the position `d` since we'd like to also consider the
1321  // possibility of multiple variables with the same `Value`. We align with
1322  // the next appearing one.
1323  if (b->findVar(aDimValue, &loc, d)) {
1324  assert(loc >= offset && "A's dim appears in B's aligned range");
1325  assert(loc < b->getNumDimVars() &&
1326  "A's dim appears in B's non-dim position");
1327  b->swapVar(d, loc);
1328  } else {
1329  b->insertDimVar(d, aDimValue);
1330  }
1331  d++;
1332  }
1333  // Dimensions that are in B, but not in A, are added at the end.
1334  for (unsigned t = a->getNumDimVars(), e = b->getNumDimVars(); t < e; t++) {
1335  a->appendDimVar(b->getValue(t));
1336  }
1337  assert(a->getNumDimVars() == b->getNumDimVars() &&
1338  "expected same number of dims");
1339  }
1340 
1341  // Merge and align symbols of A and B
1342  a->mergeSymbolVars(*b);
1343  // Merge and align locals of A and B
1344  a->mergeLocalVars(*b);
1345 
1346  assert(areVarsAligned(*a, *b) && "IDs expected to be aligned");
1347 }
1348 
1349 // Call 'mergeAndAlignVars' to align constraint systems of 'this' and 'other'.
1351  unsigned offset, FlatLinearValueConstraints *other) {
1352  mergeAndAlignVars(offset, this, other);
1353 }
1354 
1355 /// Merge and align symbols of `this` and `other` such that both get union of
1356 /// of symbols. Existing symbols need not be unique; they will be aligned from
1357 /// left to right with duplicates aligned in the same order. Symbols with Value
1358 /// as `None` are considered to be inequal to all other symbols.
1360  FlatLinearValueConstraints &other) {
1361 
1362  SmallVector<Value, 4> aSymValues;
1363  getValues(getNumDimVars(), getNumDimAndSymbolVars(), &aSymValues);
1364 
1365  // Merge symbols: merge symbols into `other` first from `this`.
1366  unsigned s = other.getNumDimVars();
1367  for (Value aSymValue : aSymValues) {
1368  unsigned loc;
1369  // If the var is a symbol in `other`, then align it, otherwise assume that
1370  // it is a new symbol. Search in `other` starting at position `s` since the
1371  // left of it is aligned.
1372  if (other.findVar(aSymValue, &loc, s) && loc >= other.getNumDimVars() &&
1373  loc < other.getNumDimAndSymbolVars())
1374  other.swapVar(s, loc);
1375  else
1376  other.insertSymbolVar(s - other.getNumDimVars(), aSymValue);
1377  s++;
1378  }
1379 
1380  // Symbols that are in other, but not in this, are added at the end.
1381  for (unsigned t = other.getNumDimVars() + getNumSymbolVars(),
1382  e = other.getNumDimAndSymbolVars();
1383  t < e; t++)
1385 
1386  assert(getNumSymbolVars() == other.getNumSymbolVars() &&
1387  "expected same number of symbols");
1388 }
1389 
1391  unsigned varLimit) {
1392  IntegerPolyhedron::removeVarRange(kind, varStart, varLimit);
1393 }
1394 
1395 AffineMap
1397  ValueRange operands) const {
1398  assert(map.getNumInputs() == operands.size() && "number of inputs mismatch");
1399 
1400  SmallVector<Value> dims, syms;
1401 #ifndef NDEBUG
1402  SmallVector<Value> newSyms;
1403  SmallVector<Value> *newSymsPtr = &newSyms;
1404 #else
1405  SmallVector<Value> *newSymsPtr = nullptr;
1406 #endif // NDEBUG
1407 
1408  dims.reserve(getNumDimVars());
1409  syms.reserve(getNumSymbolVars());
1410  for (unsigned i = 0, e = getNumVarKind(VarKind::SetDim); i < e; ++i) {
1411  Identifier id = space.getId(VarKind::SetDim, i);
1412  dims.push_back(id.hasValue() ? Value(id.getValue<Value>()) : Value());
1413  }
1414  for (unsigned i = 0, e = getNumVarKind(VarKind::Symbol); i < e; ++i) {
1415  Identifier id = space.getId(VarKind::Symbol, i);
1416  syms.push_back(id.hasValue() ? Value(id.getValue<Value>()) : Value());
1417  }
1418 
1419  AffineMap alignedMap =
1420  alignAffineMapWithValues(map, operands, dims, syms, newSymsPtr);
1421  // All symbols are already part of this FlatAffineValueConstraints.
1422  assert(syms.size() == newSymsPtr->size() && "unexpected new/missing symbols");
1423  assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
1424  "unexpected new/missing symbols");
1425  return alignedMap;
1426 }
1427 
1429  unsigned offset) const {
1431  for (unsigned i = offset, e = maybeValues.size(); i < e; ++i)
1432  if (maybeValues[i] && maybeValues[i].value() == val) {
1433  *pos = i;
1434  return true;
1435  }
1436  return false;
1437 }
1438 
1440  unsigned pos;
1441  return findVar(val, &pos, 0);
1442 }
1443 
1445  int64_t value) {
1446  unsigned pos;
1447  if (!findVar(val, &pos))
1448  // This is a pre-condition for this method.
1449  assert(0 && "var not found");
1450  addBound(type, pos, value);
1451 }
1452 
1453 void FlatLinearConstraints::printSpace(raw_ostream &os) const {
1455  os << "(";
1456  for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++)
1457  os << "None\t";
1458  for (unsigned i = getVarKindOffset(VarKind::Local),
1459  e = getVarKindEnd(VarKind::Local);
1460  i < e; ++i)
1461  os << "Local\t";
1462  os << "const)\n";
1463 }
1464 
1465 void FlatLinearValueConstraints::printSpace(raw_ostream &os) const {
1467  os << "(";
1468  for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++) {
1469  if (hasValue(i))
1470  os << "Value\t";
1471  else
1472  os << "None\t";
1473  }
1474  for (unsigned i = getVarKindOffset(VarKind::Local),
1475  e = getVarKindEnd(VarKind::Local);
1476  i < e; ++i)
1477  os << "Local\t";
1478  os << "const)\n";
1479 }
1480 
1482  unsigned pos;
1483  bool ret = findVar(val, &pos);
1484  assert(ret);
1485  (void)ret;
1487 }
1488 
1490  const FlatLinearValueConstraints &otherCst) {
1491  assert(otherCst.getNumDimVars() == getNumDimVars() && "dims mismatch");
1493  otherMaybeValues =
1494  otherCst.getMaybeValues();
1495  assert(std::equal(maybeValues.begin(), maybeValues.begin() + getNumDimVars(),
1496  otherMaybeValues.begin(),
1497  otherMaybeValues.begin() + getNumDimVars()) &&
1498  "dim values mismatch");
1499  assert(otherCst.getNumLocalVars() == 0 && "local vars not supported here");
1500  assert(getNumLocalVars() == 0 && "local vars not supported yet here");
1501 
1502  // Align `other` to this.
1503  if (!areVarsAligned(*this, otherCst)) {
1504  FlatLinearValueConstraints otherCopy(otherCst);
1505  mergeAndAlignVars(/*offset=*/getNumDimVars(), this, &otherCopy);
1506  return IntegerPolyhedron::unionBoundingBox(otherCopy);
1507  }
1508 
1509  return IntegerPolyhedron::unionBoundingBox(otherCst);
1510 }
1511 
1512 //===----------------------------------------------------------------------===//
1513 // Helper functions
1514 //===----------------------------------------------------------------------===//
1515 
1517  ValueRange dims, ValueRange syms,
1518  SmallVector<Value> *newSyms) {
1519  assert(operands.size() == map.getNumInputs() &&
1520  "expected same number of operands and map inputs");
1521  MLIRContext *ctx = map.getContext();
1522  Builder builder(ctx);
1523  SmallVector<AffineExpr> dimReplacements(map.getNumDims(), {});
1524  unsigned numSymbols = syms.size();
1525  SmallVector<AffineExpr> symReplacements(map.getNumSymbols(), {});
1526  if (newSyms) {
1527  newSyms->clear();
1528  newSyms->append(syms.begin(), syms.end());
1529  }
1530 
1531  for (const auto &operand : llvm::enumerate(operands)) {
1532  // Compute replacement dim/sym of operand.
1533  AffineExpr replacement;
1534  auto dimIt = llvm::find(dims, operand.value());
1535  auto symIt = llvm::find(syms, operand.value());
1536  if (dimIt != dims.end()) {
1537  replacement =
1538  builder.getAffineDimExpr(std::distance(dims.begin(), dimIt));
1539  } else if (symIt != syms.end()) {
1540  replacement =
1541  builder.getAffineSymbolExpr(std::distance(syms.begin(), symIt));
1542  } else {
1543  // This operand is neither a dimension nor a symbol. Add it as a new
1544  // symbol.
1545  replacement = builder.getAffineSymbolExpr(numSymbols++);
1546  if (newSyms)
1547  newSyms->push_back(operand.value());
1548  }
1549  // Add to corresponding replacements vector.
1550  if (operand.index() < map.getNumDims()) {
1551  dimReplacements[operand.index()] = replacement;
1552  } else {
1553  symReplacements[operand.index() - map.getNumDims()] = replacement;
1554  }
1555  }
1556 
1557  return map.replaceDimsAndSymbols(dimReplacements, symReplacements,
1558  dims.size(), numSymbols);
1559 }
1560 
1561 LogicalResult
1563  MultiAffineFunction &multiAff) {
1565  std::vector<SmallVector<int64_t, 8>> flattenedExprs;
1566  LogicalResult result = getFlattenedAffineExprs(map, &flattenedExprs, &cst);
1567 
1568  if (result.failed())
1569  return failure();
1570 
1571  DivisionRepr divs = cst.getLocalReprs();
1572  assert(divs.hasAllReprs() &&
1573  "AffineMap cannot produce divs without local representation");
1574 
1575  // TODO: We shouldn't have to do this conversion.
1577  map.getNumInputs() + divs.getNumDivs() + 1);
1578  for (unsigned i = 0, e = flattenedExprs.size(); i < e; ++i)
1579  for (unsigned j = 0, f = flattenedExprs[i].size(); j < f; ++j)
1580  mat(i, j) = flattenedExprs[i][j];
1581 
1582  multiAff = MultiAffineFunction(
1583  PresburgerSpace::getRelationSpace(map.getNumDims(), map.getNumResults(),
1584  map.getNumSymbols(), divs.getNumDivs()),
1585  mat, divs);
1586 
1587  return success();
1588 }
static bool detectAsFloorDiv(const FlatLinearConstraints &cst, unsigned pos, MLIRContext *context, SmallVectorImpl< AffineExpr > &exprs)
Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables ...
static bool detectAsMod(const FlatLinearConstraints &cst, unsigned pos, unsigned offset, unsigned num, int64_t lbConst, int64_t ubConst, MLIRContext *context, SmallVectorImpl< AffineExpr > &memo)
static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique(const FlatLinearValueConstraints &cst, unsigned start, unsigned end)
Checks if the SSA values associated with cst's variables in range [start, end) are unique.
static void computeUnknownVars(const FlatLinearConstraints &cst, MLIRContext *context, unsigned offset, unsigned num, SmallVectorImpl< AffineExpr > &memo)
Compute a representation of num identifiers starting at offset in cst as affine expressions involving...
static LogicalResult getFlattenedAffineExprs(ArrayRef< AffineExpr > exprs, unsigned numDims, unsigned numSymbols, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *localVarCst, bool addConservativeSemiAffineBounds=false)
static bool areVarsAligned(const FlatLinearValueConstraints &a, const FlatLinearValueConstraints &b)
Checks if two constraint systems are in the same space, i.e., if they are associated with the same se...
static bool detectAsExpr(const FlatLinearConstraints &cst, unsigned pos, unsigned idx, MLIRContext *context, SmallVectorImpl< AffineExpr > &exprs)
Express the pos^th identifier of cst as an affine expression in terms of other identifiers,...
static void mergeAndAlignVars(unsigned offset, FlatLinearValueConstraints *a, FlatLinearValueConstraints *b)
Merge and align the variables of A and B starting at 'offset', so that both constraint systems get th...
static std::optional< AffineExpr > getAsExpr(const FlatLinearConstraints &cst, unsigned pos, MLIRContext *context, ArrayRef< AffineExpr > exprs, unsigned idx, bool isEquality)
Given an equality or inequality (isEquality used to disambiguate) of cst at idx, traverse and sum up ...
union mlir::linalg::@1215::ArityGroupAndKind::Kind kind
Base type for affine expression.
Definition: AffineExpr.h:68
AffineExpr floorDiv(uint64_t v) const
Definition: AffineExpr.cpp:930
AffineExprKind getKind() const
Return the classification for this type.
Definition: AffineExpr.cpp:35
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:46
MLIRContext * getContext() const
Definition: AffineMap.cpp:339
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
unsigned getNumSymbols() const
Definition: AffineMap.cpp:394
unsigned getNumDims() const
Definition: AffineMap.cpp:390
ArrayRef< AffineExpr > getResults() const
Definition: AffineMap.cpp:403
unsigned getNumResults() const
Definition: AffineMap.cpp:398
AffineMap replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements, unsigned numResultDims, unsigned numResultSyms) const
This method substitutes any uses of dimensions and symbols (e.g.
Definition: AffineMap.cpp:496
unsigned getNumInputs() const
Definition: AffineMap.cpp:399
This class is a general helper class for creating context-global objects like types,...
Definition: Builders.h:50
AffineExpr getAffineSymbolExpr(unsigned position)
Definition: Builders.cpp:363
AffineExpr getAffineDimExpr(unsigned position)
Definition: Builders.cpp:359
FlatLinearConstraints is an extension of IntegerPolyhedron.
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
LogicalResult flattenAlignedMapAndMergeLocals(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, bool addConservativeSemiAffineBounds=false)
Given an affine map that is aligned with this constraint system:
unsigned appendLocalVar(unsigned num=1)
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatLinearConstraints.
void dumpRow(ArrayRef< int64_t > row, bool fixedColWidth=true) const
An easier to read dump of a row of the same width as the number of columns.
void dumpPretty() const
A more human-readable version of dump().
AddConservativeSemiAffineBounds
Flag to control if conservative semi-affine bounds should be added in addBound().
LogicalResult composeMatchingMap(AffineMap other)
Composes an affine map whose dimensions and symbols match one to one with the dimensions and symbols ...
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool closedUB=false)
Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an...
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound, AddConservativeSemiAffineBounds=AddConservativeSemiAffineBounds::No)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
std::pair< AffineMap, AffineMap > getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num, unsigned symStartPos, ArrayRef< AffineExpr > localExprs, MLIRContext *context, bool closedUB=false) const
Gets the lower and upper bound of the offset + posth variable treating [0, offset) U [offset + num,...
LogicalResult computeLocalVars(SmallVectorImpl< AffineExpr > &memo, MLIRContext *context) const
Compute an explicit representation for local vars.
std::optional< int64_t > getConstantBoundOnDimSize(MLIRContext *context, unsigned pos, AffineMap *lb=nullptr, AffineMap *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const
Returns a non-negative constant bound on the extent (upper bound - lower bound) of the specified vari...
FlatLinearValueConstraints represents an extension of FlatLinearConstraints where each non-local vari...
unsigned appendDimVar(unsigned num=1)
Append variables of the specified kind after the last variable of that kind.
unsigned insertDimVar(unsigned pos, ValueRange vals)
LogicalResult unionBoundingBox(const FlatLinearValueConstraints &other)
Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this ...
void mergeAndAlignVarsWithOther(unsigned offset, FlatLinearValueConstraints *other)
Merge and align the variables of this and other starting at offset, so that both constraint systems g...
SmallVector< std::optional< Value > > getMaybeValues() const
unsigned insertSymbolVar(unsigned pos, unsigned num=1)
bool hasValue(unsigned pos) const
Returns true if the pos^th variable has an associated Value.
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th variable.
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatAffineValueConstraints.
void mergeSymbolVars(FlatLinearValueConstraints &other)
Merge and align symbols of this and other such that both get union of of symbols that are unique.
void projectOut(Value val)
Projects out the variable that is associate with Value.
bool containsVar(Value val) const
Returns true if a variable with the specified Value exists, false otherwise.
void removeVarRange(presburger::VarKind kind, unsigned varStart, unsigned varLimit) override
Removes variables in the column range [varStart, varLimit), and copies any remaining valid data into ...
unsigned insertSymbolVar(unsigned pos, ValueRange vals)
bool findVar(Value val, unsigned *pos, unsigned offset=0) const
Looks up the position of the variable with the specified Value starting with variables at offset offs...
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound, AddConservativeSemiAffineBounds=AddConservativeSemiAffineBounds::No)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
bool areVarsAlignedWithOther(const FlatLinearConstraints &other)
Returns true if this constraint system and other are in the same space, i.e., if they are associated ...
AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const
Align map with this constraint system based on operands.
void getValues(unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
Returns the Values associated with variables in range [start, end).
FlatLinearValueConstraints(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< std::optional< Value >> valArgs)
Constructs a constraint system reserving memory for the specified number of constraints and variables...
void setValue(unsigned pos, Value val)
Sets the Value associated with the pos^th variable.
unsigned insertDimVar(unsigned pos, unsigned num=1)
Insert variables of the specified kind at position pos.
unsigned insertVar(presburger::VarKind kind, unsigned pos, unsigned num=1) override
Insert num variables of the specified kind at position pos.
An integer set representing a conjunction of one or more affine equalities and inequalities.
Definition: IntegerSet.h:44
unsigned getNumDims() const
Definition: IntegerSet.cpp:15
static IntegerSet get(unsigned dimCount, unsigned symbolCount, ArrayRef< AffineExpr > constraints, ArrayRef< bool > eqFlags)
unsigned getNumInputs() const
Definition: IntegerSet.cpp:17
unsigned getNumConstraints() const
Definition: IntegerSet.cpp:21
ArrayRef< AffineExpr > getConstraints() const
Definition: IntegerSet.cpp:41
ArrayRef< bool > getEqFlags() const
Returns the equality bits, which specify whether each of the constraints is an equality or inequality...
Definition: IntegerSet.cpp:51
unsigned getNumSymbols() const
Definition: IntegerSet.cpp:16
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:60
virtual void addLocalFloorDivId(ArrayRef< int64_t > dividend, int64_t divisor, AffineExpr localExpr)
virtual LogicalResult addLocalIdSemiAffine(ArrayRef< int64_t > lhs, ArrayRef< int64_t > rhs, AffineExpr localExpr)
Add a local identifier (needed to flatten a mod, floordiv, ceildiv, mul expr) when the rhs is a symbo...
SimpleAffineExprFlattener(unsigned numDims, unsigned numSymbols)
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:387
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
Class storing division representation of local variables of a constraint system.
Definition: Utils.h:117
bool hasAllReprs() const
Definition: Utils.h:133
unsigned getNumDivs() const
Definition: Utils.h:125
An Identifier stores a pointer to an object, such as a Value or an Operation.
An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affin...
virtual void swapVar(unsigned posA, unsigned posB)
Swap the posA^th variable with the posB^th variable.
int64_t atEq64(unsigned i, unsigned j) const
The same, but casts to int64_t.
unsigned getVarKindEnd(VarKind kind) const
Return the index at Which the specified kind of vars ends.
std::optional< unsigned > findConstraintWithNonZeroAt(unsigned colIdx, bool isEq) const
Finds a constraint with a non-zero coefficient at colIdx in equality (isEq=true) or inequality (isEq=...
SmallVector< int64_t, 8 > getEquality64(unsigned idx) const
The same, but casts to int64_t.
std::optional< int64_t > getConstantBound64(BoundType type, unsigned pos) const
The same, but casts to int64_t.
unsigned getNumVarKind(VarKind kind) const
Get the number of vars of the specified kind.
void addLocalFloorDiv(ArrayRef< DynamicAPInt > dividend, const DynamicAPInt &divisor)
Adds a new local variable as the floordiv of an affine function of other variables,...
void append(const IntegerRelation &other)
Appends constraints from other into this.
void addEquality(ArrayRef< DynamicAPInt > eq)
Adds an equality from the coefficients specified in eq.
unsigned getNumCols() const
Returns the number of columns in the constraint system.
DivisionRepr getLocalReprs(std::vector< MaybeLocalRepr > *repr=nullptr) const
Returns a DivisonRepr representing the division representation of local variables in the constraint s...
virtual void clearAndCopyFrom(const IntegerRelation &other)
Replaces the contents of this IntegerRelation with other.
void addInequality(ArrayRef< DynamicAPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
unsigned mergeLocalVars(IntegerRelation &other)
Adds additional local vars to the sets such that they both have the union of the local vars in each s...
SmallVector< int64_t, 8 > getInequality64(unsigned idx) const
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of vars starts.
virtual void fourierMotzkinEliminate(unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr)
Eliminates the variable at the specified position using Fourier-Motzkin variable elimination,...
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain...
Definition: PWMAFunction.h:41
Identifier getId(VarKind kind, unsigned pos) const
Get the identifier of pos^th variable of the specified kind.
static PresburgerSpace getSetSpace(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)
static void printSpace(std::ostream &os, int count)
Definition: RunnerUtils.h:98
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:344
BoundType
The type of bound: equal, lower bound or upper bound.
VarKind
Kind of variable.
MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst, ArrayRef< bool > foundRepr, unsigned pos, MutableArrayRef< DynamicAPInt > dividend, DynamicAPInt &divisor)
Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed...
Definition: Utils.cpp:227
Fraction abs(const Fraction &f)
Definition: Fraction.h:107
Include the generated interface declarations.
const FrozenRewritePatternSet GreedyRewriteConfig bool * changed
AffineMap alignAffineMapWithValues(AffineMap map, ValueRange operands, ValueRange dims, ValueRange syms, SmallVector< Value > *newSyms=nullptr)
Re-indexes the dimensions and symbols of an affine map with given operands values to align with dims ...
@ Mod
RHS of mod is always a constant or a symbolic expression with a positive value.
AffineExpr getAffineExprFromFlatForm(ArrayRef< int64_t > flatExprs, unsigned numDims, unsigned numSymbols, ArrayRef< AffineExpr > localExprs, MLIRContext *context)
Constructs an affine expression from a flat ArrayRef.
AffineExpr getAffineConstantExpr(int64_t constant, MLIRContext *context)
Definition: AffineExpr.cpp:645
LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, SmallVectorImpl< int64_t > *flattenedExpr, FlatLinearConstraints *cst=nullptr, bool addConservativeSemiAffineBounds=false)
Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the dimensions,...
LogicalResult getFlattenedAffineExprs(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *cst=nullptr, bool addConservativeSemiAffineBounds=false)
Flattens the result expressions of the map to their corresponding flattened forms and set in 'flatten...
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
AffineExpr getAffineDimExpr(unsigned position, MLIRContext *context)
These free functions allow clients of the API to not use classes in detail.
Definition: AffineExpr.cpp:621
LogicalResult getMultiAffineFunctionFromMap(AffineMap map, presburger::MultiAffineFunction &multiAff)
AffineExpr getAffineSymbolExpr(unsigned position, MLIRContext *context)
Definition: AffineExpr.cpp:631
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.