MLIR  19.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"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include <optional>
25 
26 #define DEBUG_TYPE "flat-value-constraints"
27 
28 using namespace mlir;
29 using namespace presburger;
30 
31 //===----------------------------------------------------------------------===//
32 // AffineExprFlattener
33 //===----------------------------------------------------------------------===//
34 
35 namespace {
36 
37 // See comments for SimpleAffineExprFlattener.
38 // An AffineExprFlattener extends a SimpleAffineExprFlattener by recording
39 // constraint information associated with mod's, floordiv's, and ceildiv's
40 // in FlatLinearConstraints 'localVarCst'.
41 struct AffineExprFlattener : public SimpleAffineExprFlattener {
42 public:
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 
67 } // namespace
68 
69 // Flattens the expressions in map. Returns failure if 'expr' was unable to be
70 // flattened. For example two specific cases:
71 // 1. semi-affine expressions not handled yet.
72 // 2. has poison expression (i.e., division by zero).
73 static LogicalResult
75  unsigned numSymbols,
76  std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
77  FlatLinearConstraints *localVarCst) {
78  if (exprs.empty()) {
79  if (localVarCst)
80  *localVarCst = FlatLinearConstraints(numDims, numSymbols);
81  return success();
82  }
83 
84  AffineExprFlattener flattener(numDims, numSymbols);
85  // Use the same flattener to simplify each expression successively. This way
86  // local variables / expressions are shared.
87  for (auto expr : exprs) {
88  if (!expr.isPureAffine())
89  return failure();
90  // has poison expression
91  auto flattenResult = flattener.walkPostOrder(expr);
92  if (failed(flattenResult))
93  return failure();
94  }
95 
96  assert(flattener.operandExprStack.size() == exprs.size());
97  flattenedExprs->clear();
98  flattenedExprs->assign(flattener.operandExprStack.begin(),
99  flattener.operandExprStack.end());
100 
101  if (localVarCst)
102  localVarCst->clearAndCopyFrom(flattener.localVarCst);
103 
104  return success();
105 }
106 
107 // Flattens 'expr' into 'flattenedExpr'. Returns failure if 'expr' was unable to
108 // be flattened (semi-affine expressions not handled yet).
111  unsigned numSymbols,
112  SmallVectorImpl<int64_t> *flattenedExpr,
113  FlatLinearConstraints *localVarCst) {
114  std::vector<SmallVector<int64_t, 8>> flattenedExprs;
115  LogicalResult ret = ::getFlattenedAffineExprs({expr}, numDims, numSymbols,
116  &flattenedExprs, localVarCst);
117  *flattenedExpr = flattenedExprs[0];
118  return ret;
119 }
120 
121 /// Flattens the expressions in map. Returns failure if 'expr' was unable to be
122 /// flattened (i.e., semi-affine expressions not handled yet).
124  AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
125  FlatLinearConstraints *localVarCst) {
126  if (map.getNumResults() == 0) {
127  if (localVarCst)
128  *localVarCst =
130  return success();
131  }
133  map.getNumSymbols(), flattenedExprs,
134  localVarCst);
135 }
136 
138  IntegerSet set, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
139  FlatLinearConstraints *localVarCst) {
140  if (set.getNumConstraints() == 0) {
141  if (localVarCst)
142  *localVarCst =
144  return success();
145  }
147  set.getNumSymbols(), flattenedExprs,
148  localVarCst);
149 }
150 
151 //===----------------------------------------------------------------------===//
152 // FlatLinearConstraints
153 //===----------------------------------------------------------------------===//
154 
155 // Similar to `composeMap` except that no Values need be associated with the
156 // constraint system nor are they looked at -- the dimensions and symbols of
157 // `other` are expected to correspond 1:1 to `this` system.
159  assert(other.getNumDims() == getNumDimVars() && "dim mismatch");
160  assert(other.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");
161 
162  std::vector<SmallVector<int64_t, 8>> flatExprs;
163  if (failed(flattenAlignedMapAndMergeLocals(other, &flatExprs)))
164  return failure();
165  assert(flatExprs.size() == other.getNumResults());
166 
167  // Add dimensions corresponding to the map's results.
168  insertDimVar(/*pos=*/0, /*num=*/other.getNumResults());
169 
170  // We add one equality for each result connecting the result dim of the map to
171  // the other variables.
172  // E.g.: if the expression is 16*i0 + i1, and this is the r^th
173  // iteration/result of the value map, we are adding the equality:
174  // d_r - 16*i0 - i1 = 0. Similarly, when flattening (i0 + 1, i0 + 8*i2), we
175  // add two equalities: d_0 - i0 - 1 == 0, d1 - i0 - 8*i2 == 0.
176  for (unsigned r = 0, e = flatExprs.size(); r < e; r++) {
177  const auto &flatExpr = flatExprs[r];
178  assert(flatExpr.size() >= other.getNumInputs() + 1);
179 
180  SmallVector<int64_t, 8> eqToAdd(getNumCols(), 0);
181  // Set the coefficient for this result to one.
182  eqToAdd[r] = 1;
183 
184  // Dims and symbols.
185  for (unsigned i = 0, f = other.getNumInputs(); i < f; i++) {
186  // Negate `eq[r]` since the newly added dimension will be set to this one.
187  eqToAdd[e + i] = -flatExpr[i];
188  }
189  // Local columns of `eq` are at the beginning.
190  unsigned j = getNumDimVars() + getNumSymbolVars();
191  unsigned end = flatExpr.size() - 1;
192  for (unsigned i = other.getNumInputs(); i < end; i++, j++) {
193  eqToAdd[j] = -flatExpr[i];
194  }
195 
196  // Constant term.
197  eqToAdd[getNumCols() - 1] = -flatExpr[flatExpr.size() - 1];
198 
199  // Add the equality connecting the result of the map to this constraint set.
200  addEquality(eqToAdd);
201  }
202 
203  return success();
204 }
205 
206 // Determine whether the variable at 'pos' (say var_r) can be expressed as
207 // modulo of another known variable (say var_n) w.r.t a constant. For example,
208 // if the following constraints hold true:
209 // ```
210 // 0 <= var_r <= divisor - 1
211 // var_n - (divisor * q_expr) = var_r
212 // ```
213 // where `var_n` is a known variable (called dividend), and `q_expr` is an
214 // `AffineExpr` (called the quotient expression), `var_r` can be written as:
215 //
216 // `var_r = var_n mod divisor`.
217 //
218 // Additionally, in a special case of the above constaints where `q_expr` is an
219 // variable itself that is not yet known (say `var_q`), it can be written as a
220 // floordiv in the following way:
221 //
222 // `var_q = var_n floordiv divisor`.
223 //
224 // First 'num' dimensional variables starting at 'offset' are
225 // derived/to-be-derived in terms of the remaining variables. The remaining
226 // variables are assigned trivial affine expressions in `memo`. For example,
227 // memo is initilized as follows for a `cst` with 5 dims, when offset=2, num=2:
228 // memo ==> d0 d1 . . d2 ...
229 // cst ==> c0 c1 c2 c3 c4 ...
230 //
231 // Returns true if the above mod or floordiv are detected, updating 'memo' with
232 // these new expressions. Returns false otherwise.
233 static bool detectAsMod(const FlatLinearConstraints &cst, unsigned pos,
234  unsigned offset, unsigned num, int64_t lbConst,
235  int64_t ubConst, MLIRContext *context,
237  assert(pos < cst.getNumVars() && "invalid position");
238 
239  // Check if a divisor satisfying the condition `0 <= var_r <= divisor - 1` can
240  // be determined.
241  if (lbConst != 0 || ubConst < 1)
242  return false;
243  int64_t divisor = ubConst + 1;
244 
245  // Check for the aforementioned conditions in each equality.
246  for (unsigned curEquality = 0, numEqualities = cst.getNumEqualities();
247  curEquality < numEqualities; curEquality++) {
248  int64_t coefficientAtPos = cst.atEq64(curEquality, pos);
249  // If current equality does not involve `var_r`, continue to the next
250  // equality.
251  if (coefficientAtPos == 0)
252  continue;
253 
254  // Constant term should be 0 in this equality.
255  if (cst.atEq64(curEquality, cst.getNumCols() - 1) != 0)
256  continue;
257 
258  // Traverse through the equality and construct the dividend expression
259  // `dividendExpr`, to contain all the variables which are known and are
260  // not divisible by `(coefficientAtPos * divisor)`. Hope here is that the
261  // `dividendExpr` gets simplified into a single variable `var_n` discussed
262  // above.
263  auto dividendExpr = getAffineConstantExpr(0, context);
264 
265  // Track the terms that go into quotient expression, later used to detect
266  // additional floordiv.
267  unsigned quotientCount = 0;
268  int quotientPosition = -1;
269  int quotientSign = 1;
270 
271  // Consider each term in the current equality.
272  unsigned curVar, e;
273  for (curVar = 0, e = cst.getNumDimAndSymbolVars(); curVar < e; ++curVar) {
274  // Ignore var_r.
275  if (curVar == pos)
276  continue;
277  int64_t coefficientOfCurVar = cst.atEq64(curEquality, curVar);
278  // Ignore vars that do not contribute to the current equality.
279  if (coefficientOfCurVar == 0)
280  continue;
281  // Check if the current var goes into the quotient expression.
282  if (coefficientOfCurVar % (divisor * coefficientAtPos) == 0) {
283  quotientCount++;
284  quotientPosition = curVar;
285  quotientSign = (coefficientOfCurVar * coefficientAtPos) > 0 ? 1 : -1;
286  continue;
287  }
288  // Variables that are part of dividendExpr should be known.
289  if (!memo[curVar])
290  break;
291  // Append the current variable to the dividend expression.
292  dividendExpr = dividendExpr + memo[curVar] * coefficientOfCurVar;
293  }
294 
295  // Can't construct expression as it depends on a yet uncomputed var.
296  if (curVar < e)
297  continue;
298 
299  // Express `var_r` in terms of the other vars collected so far.
300  if (coefficientAtPos > 0)
301  dividendExpr = (-dividendExpr).floorDiv(coefficientAtPos);
302  else
303  dividendExpr = dividendExpr.floorDiv(-coefficientAtPos);
304 
305  // Simplify the expression.
306  dividendExpr = simplifyAffineExpr(dividendExpr, cst.getNumDimVars(),
307  cst.getNumSymbolVars());
308  // Only if the final dividend expression is just a single var (which we call
309  // `var_n`), we can proceed.
310  // TODO: Handle AffineSymbolExpr as well. There is no reason to restrict it
311  // to dims themselves.
312  auto dimExpr = dyn_cast<AffineDimExpr>(dividendExpr);
313  if (!dimExpr)
314  continue;
315 
316  // Express `var_r` as `var_n % divisor` and store the expression in `memo`.
317  if (quotientCount >= 1) {
318  // Find the column corresponding to `dimExpr`. `num` columns starting at
319  // `offset` correspond to previously unknown variables. The column
320  // corresponding to the trivially known `dimExpr` can be on either side
321  // of these.
322  unsigned dimExprPos = dimExpr.getPosition();
323  unsigned dimExprCol = dimExprPos < offset ? dimExprPos : dimExprPos + num;
324  auto ub = cst.getConstantBound64(BoundType::UB, dimExprCol);
325  // If `var_n` has an upperbound that is less than the divisor, mod can be
326  // eliminated altogether.
327  if (ub && *ub < divisor)
328  memo[pos] = dimExpr;
329  else
330  memo[pos] = dimExpr % divisor;
331  // If a unique quotient `var_q` was seen, it can be expressed as
332  // `var_n floordiv divisor`.
333  if (quotientCount == 1 && !memo[quotientPosition])
334  memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;
335 
336  return true;
337  }
338  }
339  return false;
340 }
341 
342 /// Check if the pos^th variable can be expressed as a floordiv of an affine
343 /// function of other variables (where the divisor is a positive constant)
344 /// given the initial set of expressions in `exprs`. If it can be, the
345 /// corresponding position in `exprs` is set as the detected affine expr. For
346 /// eg: 4q <= i + j <= 4q + 3 <=> q = (i + j) floordiv 4. An equality can
347 /// also yield a floordiv: eg. 4q = i + j <=> q = (i + j) floordiv 4. 32q + 28
348 /// <= i <= 32q + 31 => q = i floordiv 32.
349 static bool detectAsFloorDiv(const FlatLinearConstraints &cst, unsigned pos,
350  MLIRContext *context,
352  assert(pos < cst.getNumVars() && "invalid position");
353 
354  // Get upper-lower bound pair for this variable.
355  SmallVector<bool, 8> foundRepr(cst.getNumVars(), false);
356  for (unsigned i = 0, e = cst.getNumVars(); i < e; ++i)
357  if (exprs[i])
358  foundRepr[i] = true;
359 
360  SmallVector<int64_t, 8> dividend(cst.getNumCols());
361  unsigned divisor;
362  auto ulPair = computeSingleVarRepr(cst, foundRepr, pos, dividend, divisor);
363 
364  // No upper-lower bound pair found for this var.
365  if (ulPair.kind == ReprKind::None || ulPair.kind == ReprKind::Equality)
366  return false;
367 
368  // Construct the dividend expression.
369  auto dividendExpr = getAffineConstantExpr(dividend.back(), context);
370  for (unsigned c = 0, f = cst.getNumVars(); c < f; c++)
371  if (dividend[c] != 0)
372  dividendExpr = dividendExpr + dividend[c] * exprs[c];
373 
374  // Successfully detected the floordiv.
375  exprs[pos] = dividendExpr.floorDiv(divisor);
376  return true;
377 }
378 
379 std::pair<AffineMap, AffineMap> FlatLinearConstraints::getLowerAndUpperBound(
380  unsigned pos, unsigned offset, unsigned num, unsigned symStartPos,
381  ArrayRef<AffineExpr> localExprs, MLIRContext *context,
382  bool closedUB) const {
383  assert(pos + offset < getNumDimVars() && "invalid dim start pos");
384  assert(symStartPos >= (pos + offset) && "invalid sym start pos");
385  assert(getNumLocalVars() == localExprs.size() &&
386  "incorrect local exprs count");
387 
388  SmallVector<unsigned, 4> lbIndices, ubIndices, eqIndices;
389  getLowerAndUpperBoundIndices(pos + offset, &lbIndices, &ubIndices, &eqIndices,
390  offset, num);
391 
392  /// Add to 'b' from 'a' in set [0, offset) U [offset + num, symbStartPos).
393  auto addCoeffs = [&](ArrayRef<int64_t> a, SmallVectorImpl<int64_t> &b) {
394  b.clear();
395  for (unsigned i = 0, e = a.size(); i < e; ++i) {
396  if (i < offset || i >= offset + num)
397  b.push_back(a[i]);
398  }
399  };
400 
403  unsigned dimCount = symStartPos - num;
404  unsigned symCount = getNumDimAndSymbolVars() - symStartPos;
405  lbExprs.reserve(lbIndices.size() + eqIndices.size());
406  // Lower bound expressions.
407  for (auto idx : lbIndices) {
408  auto ineq = getInequality64(idx);
409  // Extract the lower bound (in terms of other coeff's + const), i.e., if
410  // i - j + 1 >= 0 is the constraint, 'pos' is for i the lower bound is j
411  // - 1.
412  addCoeffs(ineq, lb);
413  std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
414  auto expr =
415  getAffineExprFromFlatForm(lb, dimCount, symCount, localExprs, context);
416  // expr ceildiv divisor is (expr + divisor - 1) floordiv divisor
417  int64_t divisor = std::abs(ineq[pos + offset]);
418  expr = (expr + divisor - 1).floorDiv(divisor);
419  lbExprs.push_back(expr);
420  }
421 
423  ubExprs.reserve(ubIndices.size() + eqIndices.size());
424  // Upper bound expressions.
425  for (auto idx : ubIndices) {
426  auto ineq = getInequality64(idx);
427  // Extract the upper bound (in terms of other coeff's + const).
428  addCoeffs(ineq, ub);
429  auto expr =
430  getAffineExprFromFlatForm(ub, dimCount, symCount, localExprs, context);
431  expr = expr.floorDiv(std::abs(ineq[pos + offset]));
432  int64_t ubAdjustment = closedUB ? 0 : 1;
433  ubExprs.push_back(expr + ubAdjustment);
434  }
435 
436  // Equalities. It's both a lower and a upper bound.
438  for (auto idx : eqIndices) {
439  auto eq = getEquality64(idx);
440  addCoeffs(eq, b);
441  if (eq[pos + offset] > 0)
442  std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());
443 
444  // Extract the upper bound (in terms of other coeff's + const).
445  auto expr =
446  getAffineExprFromFlatForm(b, dimCount, symCount, localExprs, context);
447  expr = expr.floorDiv(std::abs(eq[pos + offset]));
448  // Upper bound is exclusive.
449  ubExprs.push_back(expr + 1);
450  // Lower bound.
451  expr =
452  getAffineExprFromFlatForm(b, dimCount, symCount, localExprs, context);
453  expr = expr.ceilDiv(std::abs(eq[pos + offset]));
454  lbExprs.push_back(expr);
455  }
456 
457  auto lbMap = AffineMap::get(dimCount, symCount, lbExprs, context);
458  auto ubMap = AffineMap::get(dimCount, symCount, ubExprs, context);
459 
460  return {lbMap, ubMap};
461 }
462 
463 /// Computes the lower and upper bounds of the first 'num' dimensional
464 /// variables (starting at 'offset') as affine maps of the remaining
465 /// variables (dimensional and symbolic variables). Local variables are
466 /// themselves explicitly computed as affine functions of other variables in
467 /// this process if needed.
468 void FlatLinearConstraints::getSliceBounds(unsigned offset, unsigned num,
469  MLIRContext *context,
472  bool closedUB) {
473  assert(offset + num <= getNumDimVars() && "invalid range");
474 
475  // Basic simplification.
476  normalizeConstraintsByGCD();
477 
478  LLVM_DEBUG(llvm::dbgs() << "getSliceBounds for first " << num
479  << " variables\n");
480  LLVM_DEBUG(dump());
481 
482  // Record computed/detected variables.
483  SmallVector<AffineExpr, 8> memo(getNumVars());
484  // Initialize dimensional and symbolic variables.
485  for (unsigned i = 0, e = getNumDimVars(); i < e; i++) {
486  if (i < offset)
487  memo[i] = getAffineDimExpr(i, context);
488  else if (i >= offset + num)
489  memo[i] = getAffineDimExpr(i - num, context);
490  }
491  for (unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++)
492  memo[i] = getAffineSymbolExpr(i - getNumDimVars(), context);
493 
494  bool changed;
495  do {
496  changed = false;
497  // Identify yet unknown variables as constants or mod's / floordiv's of
498  // other variables if possible.
499  for (unsigned pos = 0; pos < getNumVars(); pos++) {
500  if (memo[pos])
501  continue;
502 
503  auto lbConst = getConstantBound64(BoundType::LB, pos);
504  auto ubConst = getConstantBound64(BoundType::UB, pos);
505  if (lbConst.has_value() && ubConst.has_value()) {
506  // Detect equality to a constant.
507  if (*lbConst == *ubConst) {
508  memo[pos] = getAffineConstantExpr(*lbConst, context);
509  changed = true;
510  continue;
511  }
512 
513  // Detect a variable as modulo of another variable w.r.t a
514  // constant.
515  if (detectAsMod(*this, pos, offset, num, *lbConst, *ubConst, context,
516  memo)) {
517  changed = true;
518  continue;
519  }
520  }
521 
522  // Detect a variable as a floordiv of an affine function of other
523  // variables (divisor is a positive constant).
524  if (detectAsFloorDiv(*this, pos, context, memo)) {
525  changed = true;
526  continue;
527  }
528 
529  // Detect a variable as an expression of other variables.
530  unsigned idx;
531  if (!findConstraintWithNonZeroAt(pos, /*isEq=*/true, &idx)) {
532  continue;
533  }
534 
535  // Build AffineExpr solving for variable 'pos' in terms of all others.
536  auto expr = getAffineConstantExpr(0, context);
537  unsigned j, e;
538  for (j = 0, e = getNumVars(); j < e; ++j) {
539  if (j == pos)
540  continue;
541  int64_t c = atEq64(idx, j);
542  if (c == 0)
543  continue;
544  // If any of the involved IDs hasn't been found yet, we can't proceed.
545  if (!memo[j])
546  break;
547  expr = expr + memo[j] * c;
548  }
549  if (j < e)
550  // Can't construct expression as it depends on a yet uncomputed
551  // variable.
552  continue;
553 
554  // Add constant term to AffineExpr.
555  expr = expr + atEq64(idx, getNumVars());
556  int64_t vPos = atEq64(idx, pos);
557  assert(vPos != 0 && "expected non-zero here");
558  if (vPos > 0)
559  expr = (-expr).floorDiv(vPos);
560  else
561  // vPos < 0.
562  expr = expr.floorDiv(-vPos);
563  // Successfully constructed expression.
564  memo[pos] = expr;
565  changed = true;
566  }
567  // This loop is guaranteed to reach a fixed point - since once an
568  // variable's explicit form is computed (in memo[pos]), it's not updated
569  // again.
570  } while (changed);
571 
572  int64_t ubAdjustment = closedUB ? 0 : 1;
573 
574  // Set the lower and upper bound maps for all the variables that were
575  // computed as affine expressions of the rest as the "detected expr" and
576  // "detected expr + 1" respectively; set the undetected ones to null.
577  std::optional<FlatLinearConstraints> tmpClone;
578  for (unsigned pos = 0; pos < num; pos++) {
579  unsigned numMapDims = getNumDimVars() - num;
580  unsigned numMapSymbols = getNumSymbolVars();
581  AffineExpr expr = memo[pos + offset];
582  if (expr)
583  expr = simplifyAffineExpr(expr, numMapDims, numMapSymbols);
584 
585  AffineMap &lbMap = (*lbMaps)[pos];
586  AffineMap &ubMap = (*ubMaps)[pos];
587 
588  if (expr) {
589  lbMap = AffineMap::get(numMapDims, numMapSymbols, expr);
590  ubMap = AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
591  } else {
592  // TODO: Whenever there are local variables in the dependence
593  // constraints, we'll conservatively over-approximate, since we don't
594  // always explicitly compute them above (in the while loop).
595  if (getNumLocalVars() == 0) {
596  // Work on a copy so that we don't update this constraint system.
597  if (!tmpClone) {
598  tmpClone.emplace(FlatLinearConstraints(*this));
599  // Removing redundant inequalities is necessary so that we don't get
600  // redundant loop bounds.
601  tmpClone->removeRedundantInequalities();
602  }
603  std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
604  pos, offset, num, getNumDimVars(), /*localExprs=*/{}, context,
605  closedUB);
606  }
607 
608  // If the above fails, we'll just use the constant lower bound and the
609  // constant upper bound (if they exist) as the slice bounds.
610  // TODO: being conservative for the moment in cases that
611  // lead to multiple bounds - until getConstDifference in LoopFusion.cpp is
612  // fixed (b/126426796).
613  if (!lbMap || lbMap.getNumResults() > 1) {
614  LLVM_DEBUG(llvm::dbgs()
615  << "WARNING: Potentially over-approximating slice lb\n");
616  auto lbConst = getConstantBound64(BoundType::LB, pos + offset);
617  if (lbConst.has_value()) {
618  lbMap = AffineMap::get(numMapDims, numMapSymbols,
619  getAffineConstantExpr(*lbConst, context));
620  }
621  }
622  if (!ubMap || ubMap.getNumResults() > 1) {
623  LLVM_DEBUG(llvm::dbgs()
624  << "WARNING: Potentially over-approximating slice ub\n");
625  auto ubConst = getConstantBound64(BoundType::UB, pos + offset);
626  if (ubConst.has_value()) {
627  ubMap = AffineMap::get(
628  numMapDims, numMapSymbols,
629  getAffineConstantExpr(*ubConst + ubAdjustment, context));
630  }
631  }
632  }
633  LLVM_DEBUG(llvm::dbgs()
634  << "lb map for pos = " << Twine(pos + offset) << ", expr: ");
635  LLVM_DEBUG(lbMap.dump(););
636  LLVM_DEBUG(llvm::dbgs()
637  << "ub map for pos = " << Twine(pos + offset) << ", expr: ");
638  LLVM_DEBUG(ubMap.dump(););
639  }
640 }
641 
643  AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs) {
644  FlatLinearConstraints localCst;
645  if (failed(getFlattenedAffineExprs(map, flattenedExprs, &localCst))) {
646  LLVM_DEBUG(llvm::dbgs()
647  << "composition unimplemented for semi-affine maps\n");
648  return failure();
649  }
650 
651  // Add localCst information.
652  if (localCst.getNumLocalVars() > 0) {
653  unsigned numLocalVars = getNumLocalVars();
654  // Insert local dims of localCst at the beginning.
655  insertLocalVar(/*pos=*/0, /*num=*/localCst.getNumLocalVars());
656  // Insert local dims of `this` at the end of localCst.
657  localCst.appendLocalVar(/*num=*/numLocalVars);
658  // Dimensions of localCst and this constraint set match. Append localCst to
659  // this constraint set.
660  append(localCst);
661  }
662 
663  return success();
664 }
665 
667  AffineMap boundMap,
668  bool isClosedBound) {
669  assert(boundMap.getNumDims() == getNumDimVars() && "dim mismatch");
670  assert(boundMap.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");
671  assert(pos < getNumDimAndSymbolVars() && "invalid position");
672  assert((type != BoundType::EQ || isClosedBound) &&
673  "EQ bound must be closed.");
674 
675  // Equality follows the logic of lower bound except that we add an equality
676  // instead of an inequality.
677  assert((type != BoundType::EQ || boundMap.getNumResults() == 1) &&
678  "single result expected");
679  bool lower = type == BoundType::LB || type == BoundType::EQ;
680 
681  std::vector<SmallVector<int64_t, 8>> flatExprs;
682  if (failed(flattenAlignedMapAndMergeLocals(boundMap, &flatExprs)))
683  return failure();
684  assert(flatExprs.size() == boundMap.getNumResults());
685 
686  // Add one (in)equality for each result.
687  for (const auto &flatExpr : flatExprs) {
688  SmallVector<int64_t> ineq(getNumCols(), 0);
689  // Dims and symbols.
690  for (unsigned j = 0, e = boundMap.getNumInputs(); j < e; j++) {
691  ineq[j] = lower ? -flatExpr[j] : flatExpr[j];
692  }
693  // Invalid bound: pos appears in `boundMap`.
694  // TODO: This should be an assertion. Fix `addDomainFromSliceMaps` and/or
695  // its callers to prevent invalid bounds from being added.
696  if (ineq[pos] != 0)
697  continue;
698  ineq[pos] = lower ? 1 : -1;
699  // Local columns of `ineq` are at the beginning.
700  unsigned j = getNumDimVars() + getNumSymbolVars();
701  unsigned end = flatExpr.size() - 1;
702  for (unsigned i = boundMap.getNumInputs(); i < end; i++, j++) {
703  ineq[j] = lower ? -flatExpr[i] : flatExpr[i];
704  }
705  // Make the bound closed in if flatExpr is open. The inequality is always
706  // created in the upper bound form, so the adjustment is -1.
707  int64_t boundAdjustment = (isClosedBound || type == BoundType::EQ) ? 0 : -1;
708  // Constant term.
709  ineq[getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
710  : flatExpr[flatExpr.size() - 1]) +
711  boundAdjustment;
712  type == BoundType::EQ ? addEquality(ineq) : addInequality(ineq);
713  }
714 
715  return success();
716 }
717 
719  AffineMap boundMap) {
720  return addBound(type, pos, boundMap, /*isClosedBound=*/type != BoundType::UB);
721 }
722 
723 /// Compute an explicit representation for local vars. For all systems coming
724 /// from MLIR integer sets, maps, or expressions where local vars were
725 /// introduced to model floordivs and mods, this always succeeds.
728  MLIRContext *context) const {
729  unsigned numDims = getNumDimVars();
730  unsigned numSyms = getNumSymbolVars();
731 
732  // Initialize dimensional and symbolic variables.
733  for (unsigned i = 0; i < numDims; i++)
734  memo[i] = getAffineDimExpr(i, context);
735  for (unsigned i = numDims, e = numDims + numSyms; i < e; i++)
736  memo[i] = getAffineSymbolExpr(i - numDims, context);
737 
738  bool changed;
739  do {
740  // Each time `changed` is true at the end of this iteration, one or more
741  // local vars would have been detected as floordivs and set in memo; so the
742  // number of null entries in memo[...] strictly reduces; so this converges.
743  changed = false;
744  for (unsigned i = 0, e = getNumLocalVars(); i < e; ++i)
745  if (!memo[numDims + numSyms + i] &&
746  detectAsFloorDiv(*this, /*pos=*/numDims + numSyms + i, context, memo))
747  changed = true;
748  } while (changed);
749 
750  ArrayRef<AffineExpr> localExprs =
751  ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());
752  return success(
753  llvm::all_of(localExprs, [](AffineExpr expr) { return expr; }));
754 }
755 
757  if (getNumConstraints() == 0)
758  // Return universal set (always true): 0 == 0.
759  return IntegerSet::get(getNumDimVars(), getNumSymbolVars(),
760  getAffineConstantExpr(/*constant=*/0, context),
761  /*eqFlags=*/true);
762 
763  // Construct local references.
764  SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());
765 
766  if (failed(computeLocalVars(memo, context))) {
767  // Check if the local variables without an explicit representation have
768  // zero coefficients everywhere.
769  SmallVector<unsigned> noLocalRepVars;
770  unsigned numDimsSymbols = getNumDimAndSymbolVars();
771  for (unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
772  if (!memo[i] && !isColZero(/*pos=*/i))
773  noLocalRepVars.push_back(i - numDimsSymbols);
774  }
775  if (!noLocalRepVars.empty()) {
776  LLVM_DEBUG({
777  llvm::dbgs() << "local variables at position(s) ";
778  llvm::interleaveComma(noLocalRepVars, llvm::dbgs());
779  llvm::dbgs() << " do not have an explicit representation in:\n";
780  this->dump();
781  });
782  return IntegerSet();
783  }
784  }
785 
786  ArrayRef<AffineExpr> localExprs =
787  ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());
788 
789  // Construct the IntegerSet from the equalities/inequalities.
790  unsigned numDims = getNumDimVars();
791  unsigned numSyms = getNumSymbolVars();
792 
793  SmallVector<bool, 16> eqFlags(getNumConstraints());
794  std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(), true);
795  std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(), false);
796 
798  exprs.reserve(getNumConstraints());
799 
800  for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
801  exprs.push_back(getAffineExprFromFlatForm(getEquality64(i), numDims,
802  numSyms, localExprs, context));
803  for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
804  exprs.push_back(getAffineExprFromFlatForm(getInequality64(i), numDims,
805  numSyms, localExprs, context));
806  return IntegerSet::get(numDims, numSyms, exprs, eqFlags);
807 }
808 
809 //===----------------------------------------------------------------------===//
810 // FlatLinearValueConstraints
811 //===----------------------------------------------------------------------===//
812 
813 // Construct from an IntegerSet.
815  ValueRange operands)
816  : FlatLinearConstraints(set.getNumInequalities(), set.getNumEqualities(),
817  set.getNumDims() + set.getNumSymbols() + 1,
818  set.getNumDims(), set.getNumSymbols(),
819  /*numLocals=*/0) {
820  // Populate values.
821  if (operands.empty()) {
822  values.resize(getNumDimAndSymbolVars(), std::nullopt);
823  } else {
824  assert(set.getNumInputs() == operands.size() && "operand count mismatch");
825  values.assign(operands.begin(), operands.end());
826  }
827 
828  // Flatten expressions and add them to the constraint system.
829  std::vector<SmallVector<int64_t, 8>> flatExprs;
830  FlatLinearConstraints localVarCst;
831  if (failed(getFlattenedAffineExprs(set, &flatExprs, &localVarCst))) {
832  assert(false && "flattening unimplemented for semi-affine integer sets");
833  return;
834  }
835  assert(flatExprs.size() == set.getNumConstraints());
836  insertVar(VarKind::Local, getNumVarKind(VarKind::Local),
837  /*num=*/localVarCst.getNumLocalVars());
838 
839  for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
840  const auto &flatExpr = flatExprs[i];
841  assert(flatExpr.size() == getNumCols());
842  if (set.getEqFlags()[i]) {
843  addEquality(flatExpr);
844  } else {
845  addInequality(flatExpr);
846  }
847  }
848  // Add the other constraints involving local vars from flattening.
849  append(localVarCst);
850 }
851 
853  unsigned pos = getNumDimVars();
854  return insertVar(VarKind::SetDim, pos, vals);
855 }
856 
858  unsigned pos = getNumSymbolVars();
859  return insertVar(VarKind::Symbol, pos, vals);
860 }
861 
863  ValueRange vals) {
864  return insertVar(VarKind::SetDim, pos, vals);
865 }
866 
868  ValueRange vals) {
869  return insertVar(VarKind::Symbol, pos, vals);
870 }
871 
872 unsigned FlatLinearValueConstraints::insertVar(VarKind kind, unsigned pos,
873  unsigned num) {
874  unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
875 
876  if (kind != VarKind::Local) {
877  values.insert(values.begin() + absolutePos, num, std::nullopt);
878  assert(values.size() == getNumDimAndSymbolVars());
879  }
880 
881  return absolutePos;
882 }
883 
884 unsigned FlatLinearValueConstraints::insertVar(VarKind kind, unsigned pos,
885  ValueRange vals) {
886  assert(!vals.empty() && "expected ValueRange with Values.");
887  assert(kind != VarKind::Local &&
888  "values cannot be attached to local variables.");
889  unsigned num = vals.size();
890  unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
891 
892  // If a Value is provided, insert it; otherwise use std::nullopt.
893  for (unsigned i = 0; i < num; ++i)
894  values.insert(values.begin() + absolutePos + i,
895  vals[i] ? std::optional<Value>(vals[i]) : std::nullopt);
896 
897  assert(values.size() == getNumDimAndSymbolVars());
898  return absolutePos;
899 }
900 
901 /// Checks if two constraint systems are in the same space, i.e., if they are
902 /// associated with the same set of variables, appearing in the same order.
904  const FlatLinearValueConstraints &b) {
905  return a.getNumDimVars() == b.getNumDimVars() &&
906  a.getNumSymbolVars() == b.getNumSymbolVars() &&
907  a.getNumVars() == b.getNumVars() &&
908  a.getMaybeValues().equals(b.getMaybeValues());
909 }
910 
911 /// Calls areVarsAligned to check if two constraint systems have the same set
912 /// of variables in the same order.
914  const FlatLinearConstraints &other) {
915  return areVarsAligned(*this, other);
916 }
917 
918 /// Checks if the SSA values associated with `cst`'s variables in range
919 /// [start, end) are unique.
920 static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique(
921  const FlatLinearValueConstraints &cst, unsigned start, unsigned end) {
922 
923  assert(start <= cst.getNumDimAndSymbolVars() &&
924  "Start position out of bounds");
925  assert(end <= cst.getNumDimAndSymbolVars() && "End position out of bounds");
926 
927  if (start >= end)
928  return true;
929 
930  SmallPtrSet<Value, 8> uniqueVars;
931  ArrayRef<std::optional<Value>> maybeValues =
932  cst.getMaybeValues().slice(start, end - start);
933  for (std::optional<Value> val : maybeValues) {
934  if (val && !uniqueVars.insert(*val).second)
935  return false;
936  }
937  return true;
938 }
939 
940 /// Checks if the SSA values associated with `cst`'s variables are unique.
941 static bool LLVM_ATTRIBUTE_UNUSED
943  return areVarsUnique(cst, 0, cst.getNumDimAndSymbolVars());
944 }
945 
946 /// Checks if the SSA values associated with `cst`'s variables of kind `kind`
947 /// are unique.
948 static bool LLVM_ATTRIBUTE_UNUSED
950 
951  if (kind == VarKind::SetDim)
952  return areVarsUnique(cst, 0, cst.getNumDimVars());
953  if (kind == VarKind::Symbol)
954  return areVarsUnique(cst, cst.getNumDimVars(),
955  cst.getNumDimAndSymbolVars());
956  llvm_unreachable("Unexpected VarKind");
957 }
958 
959 /// Merge and align the variables of A and B starting at 'offset', so that
960 /// both constraint systems get the union of the contained variables that is
961 /// dimension-wise and symbol-wise unique; both constraint systems are updated
962 /// so that they have the union of all variables, with A's original
963 /// variables appearing first followed by any of B's variables that didn't
964 /// appear in A. Local variables in B that have the same division
965 /// representation as local variables in A are merged into one. We allow A
966 /// and B to have non-unique values for their variables; in such cases, they are
967 /// still aligned with the variables appearing first aligned with those
968 /// appearing first in the other system from left to right.
969 // E.g.: Input: A has ((%i, %j) [%M, %N]) and B has (%k, %j) [%P, %N, %M])
970 // Output: both A, B have (%i, %j, %k) [%M, %N, %P]
971 static void mergeAndAlignVars(unsigned offset, FlatLinearValueConstraints *a,
973  assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
974 
975  assert(llvm::all_of(
976  llvm::drop_begin(a->getMaybeValues(), offset),
977  [](const std::optional<Value> &var) { return var.has_value(); }));
978 
979  assert(llvm::all_of(
980  llvm::drop_begin(b->getMaybeValues(), offset),
981  [](const std::optional<Value> &var) { return var.has_value(); }));
982 
983  SmallVector<Value, 4> aDimValues;
984  a->getValues(offset, a->getNumDimVars(), &aDimValues);
985 
986  {
987  // Merge dims from A into B.
988  unsigned d = offset;
989  for (Value aDimValue : aDimValues) {
990  unsigned loc;
991  // Find from the position `d` since we'd like to also consider the
992  // possibility of multiple variables with the same `Value`. We align with
993  // the next appearing one.
994  if (b->findVar(aDimValue, &loc, d)) {
995  assert(loc >= offset && "A's dim appears in B's aligned range");
996  assert(loc < b->getNumDimVars() &&
997  "A's dim appears in B's non-dim position");
998  b->swapVar(d, loc);
999  } else {
1000  b->insertDimVar(d, aDimValue);
1001  }
1002  d++;
1003  }
1004  // Dimensions that are in B, but not in A, are added at the end.
1005  for (unsigned t = a->getNumDimVars(), e = b->getNumDimVars(); t < e; t++) {
1006  a->appendDimVar(b->getValue(t));
1007  }
1008  assert(a->getNumDimVars() == b->getNumDimVars() &&
1009  "expected same number of dims");
1010  }
1011 
1012  // Merge and align symbols of A and B
1013  a->mergeSymbolVars(*b);
1014  // Merge and align locals of A and B
1015  a->mergeLocalVars(*b);
1016 
1017  assert(areVarsAligned(*a, *b) && "IDs expected to be aligned");
1018 }
1019 
1020 // Call 'mergeAndAlignVars' to align constraint systems of 'this' and 'other'.
1022  unsigned offset, FlatLinearValueConstraints *other) {
1023  mergeAndAlignVars(offset, this, other);
1024 }
1025 
1026 /// Merge and align symbols of `this` and `other` such that both get union of
1027 /// of symbols. Existing symbols need not be unique; they will be aligned from
1028 /// left to right with duplicates aligned in the same order. Symbols with Value
1029 /// as `None` are considered to be inequal to all other symbols.
1031  FlatLinearValueConstraints &other) {
1032 
1033  SmallVector<Value, 4> aSymValues;
1034  getValues(getNumDimVars(), getNumDimAndSymbolVars(), &aSymValues);
1035 
1036  // Merge symbols: merge symbols into `other` first from `this`.
1037  unsigned s = other.getNumDimVars();
1038  for (Value aSymValue : aSymValues) {
1039  unsigned loc;
1040  // If the var is a symbol in `other`, then align it, otherwise assume that
1041  // it is a new symbol. Search in `other` starting at position `s` since the
1042  // left of it is aligned.
1043  if (other.findVar(aSymValue, &loc, s) && loc >= other.getNumDimVars() &&
1044  loc < other.getNumDimAndSymbolVars())
1045  other.swapVar(s, loc);
1046  else
1047  other.insertSymbolVar(s - other.getNumDimVars(), aSymValue);
1048  s++;
1049  }
1050 
1051  // Symbols that are in other, but not in this, are added at the end.
1052  for (unsigned t = other.getNumDimVars() + getNumSymbolVars(),
1053  e = other.getNumDimAndSymbolVars();
1054  t < e; t++)
1056 
1057  assert(getNumSymbolVars() == other.getNumSymbolVars() &&
1058  "expected same number of symbols");
1059 }
1060 
1062  return IntegerPolyhedron::hasConsistentState() &&
1063  values.size() == getNumDimAndSymbolVars();
1064 }
1065 
1067  unsigned varLimit) {
1068  IntegerPolyhedron::removeVarRange(kind, varStart, varLimit);
1069  unsigned offset = getVarKindOffset(kind);
1070 
1071  if (kind != VarKind::Local) {
1072  values.erase(values.begin() + varStart + offset,
1073  values.begin() + varLimit + offset);
1074  }
1075 }
1076 
1077 AffineMap
1079  ValueRange operands) const {
1080  assert(map.getNumInputs() == operands.size() && "number of inputs mismatch");
1081 
1082  SmallVector<Value> dims, syms;
1083 #ifndef NDEBUG
1084  SmallVector<Value> newSyms;
1085  SmallVector<Value> *newSymsPtr = &newSyms;
1086 #else
1087  SmallVector<Value> *newSymsPtr = nullptr;
1088 #endif // NDEBUG
1089 
1090  dims.reserve(getNumDimVars());
1091  syms.reserve(getNumSymbolVars());
1092  for (unsigned i = getVarKindOffset(VarKind::SetDim),
1093  e = getVarKindEnd(VarKind::SetDim);
1094  i < e; ++i)
1095  dims.push_back(values[i] ? *values[i] : Value());
1096  for (unsigned i = getVarKindOffset(VarKind::Symbol),
1097  e = getVarKindEnd(VarKind::Symbol);
1098  i < e; ++i)
1099  syms.push_back(values[i] ? *values[i] : Value());
1100 
1101  AffineMap alignedMap =
1102  alignAffineMapWithValues(map, operands, dims, syms, newSymsPtr);
1103  // All symbols are already part of this FlatAffineValueConstraints.
1104  assert(syms.size() == newSymsPtr->size() && "unexpected new/missing symbols");
1105  assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
1106  "unexpected new/missing symbols");
1107  return alignedMap;
1108 }
1109 
1111  unsigned offset) const {
1112  unsigned i = offset;
1113  for (const auto &mayBeVar :
1114  ArrayRef<std::optional<Value>>(values).drop_front(offset)) {
1115  if (mayBeVar && *mayBeVar == val) {
1116  *pos = i;
1117  return true;
1118  }
1119  i++;
1120  }
1121  return false;
1122 }
1123 
1125  return llvm::any_of(values, [&](const std::optional<Value> &mayBeVar) {
1126  return mayBeVar && *mayBeVar == val;
1127  });
1128 }
1129 
1130 void FlatLinearValueConstraints::swapVar(unsigned posA, unsigned posB) {
1131  IntegerPolyhedron::swapVar(posA, posB);
1132 
1133  if (getVarKindAt(posA) == VarKind::Local &&
1134  getVarKindAt(posB) == VarKind::Local)
1135  return;
1136 
1137  // Treat value of a local variable as std::nullopt.
1138  if (getVarKindAt(posA) == VarKind::Local)
1139  values[posB] = std::nullopt;
1140  else if (getVarKindAt(posB) == VarKind::Local)
1141  values[posA] = std::nullopt;
1142  else
1143  std::swap(values[posA], values[posB]);
1144 }
1145 
1147  int64_t value) {
1148  unsigned pos;
1149  if (!findVar(val, &pos))
1150  // This is a pre-condition for this method.
1151  assert(0 && "var not found");
1152  addBound(type, pos, value);
1153 }
1154 
1155 void FlatLinearConstraints::printSpace(raw_ostream &os) const {
1157  os << "(";
1158  for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++)
1159  os << "None\t";
1160  for (unsigned i = getVarKindOffset(VarKind::Local),
1161  e = getVarKindEnd(VarKind::Local);
1162  i < e; ++i)
1163  os << "Local\t";
1164  os << "const)\n";
1165 }
1166 
1167 void FlatLinearValueConstraints::printSpace(raw_ostream &os) const {
1169  os << "(";
1170  for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++) {
1171  if (hasValue(i))
1172  os << "Value\t";
1173  else
1174  os << "None\t";
1175  }
1176  for (unsigned i = getVarKindOffset(VarKind::Local),
1177  e = getVarKindEnd(VarKind::Local);
1178  i < e; ++i)
1179  os << "Local\t";
1180  os << "const)\n";
1181 }
1182 
1184  const IntegerRelation &other) {
1185 
1186  if (auto *otherValueSet =
1187  dyn_cast<const FlatLinearValueConstraints>(&other)) {
1188  *this = *otherValueSet;
1189  } else {
1190  *static_cast<IntegerRelation *>(this) = other;
1191  values.clear();
1192  values.resize(getNumDimAndSymbolVars(), std::nullopt);
1193  }
1194 }
1195 
1197  unsigned pos, bool darkShadow, bool *isResultIntegerExact) {
1199  if (getVarKindAt(pos) != VarKind::Local)
1200  newVals.erase(newVals.begin() + pos);
1201  // Note: Base implementation discards all associated Values.
1202  IntegerPolyhedron::fourierMotzkinEliminate(pos, darkShadow,
1203  isResultIntegerExact);
1204  values = newVals;
1205  assert(values.size() == getNumDimAndSymbolVars());
1206 }
1207 
1209  unsigned pos;
1210  bool ret = findVar(val, &pos);
1211  assert(ret);
1212  (void)ret;
1214 }
1215 
1217  const FlatLinearValueConstraints &otherCst) {
1218  assert(otherCst.getNumDimVars() == getNumDimVars() && "dims mismatch");
1219  assert(otherCst.getMaybeValues()
1220  .slice(0, getNumDimVars())
1221  .equals(getMaybeValues().slice(0, getNumDimVars())) &&
1222  "dim values mismatch");
1223  assert(otherCst.getNumLocalVars() == 0 && "local vars not supported here");
1224  assert(getNumLocalVars() == 0 && "local vars not supported yet here");
1225 
1226  // Align `other` to this.
1227  if (!areVarsAligned(*this, otherCst)) {
1228  FlatLinearValueConstraints otherCopy(otherCst);
1229  mergeAndAlignVars(/*offset=*/getNumDimVars(), this, &otherCopy);
1230  return IntegerPolyhedron::unionBoundingBox(otherCopy);
1231  }
1232 
1233  return IntegerPolyhedron::unionBoundingBox(otherCst);
1234 }
1235 
1236 //===----------------------------------------------------------------------===//
1237 // Helper functions
1238 //===----------------------------------------------------------------------===//
1239 
1241  ValueRange dims, ValueRange syms,
1242  SmallVector<Value> *newSyms) {
1243  assert(operands.size() == map.getNumInputs() &&
1244  "expected same number of operands and map inputs");
1245  MLIRContext *ctx = map.getContext();
1246  Builder builder(ctx);
1247  SmallVector<AffineExpr> dimReplacements(map.getNumDims(), {});
1248  unsigned numSymbols = syms.size();
1249  SmallVector<AffineExpr> symReplacements(map.getNumSymbols(), {});
1250  if (newSyms) {
1251  newSyms->clear();
1252  newSyms->append(syms.begin(), syms.end());
1253  }
1254 
1255  for (const auto &operand : llvm::enumerate(operands)) {
1256  // Compute replacement dim/sym of operand.
1257  AffineExpr replacement;
1258  auto dimIt = llvm::find(dims, operand.value());
1259  auto symIt = llvm::find(syms, operand.value());
1260  if (dimIt != dims.end()) {
1261  replacement =
1262  builder.getAffineDimExpr(std::distance(dims.begin(), dimIt));
1263  } else if (symIt != syms.end()) {
1264  replacement =
1265  builder.getAffineSymbolExpr(std::distance(syms.begin(), symIt));
1266  } else {
1267  // This operand is neither a dimension nor a symbol. Add it as a new
1268  // symbol.
1269  replacement = builder.getAffineSymbolExpr(numSymbols++);
1270  if (newSyms)
1271  newSyms->push_back(operand.value());
1272  }
1273  // Add to corresponding replacements vector.
1274  if (operand.index() < map.getNumDims()) {
1275  dimReplacements[operand.index()] = replacement;
1276  } else {
1277  symReplacements[operand.index() - map.getNumDims()] = replacement;
1278  }
1279  }
1280 
1281  return map.replaceDimsAndSymbols(dimReplacements, symReplacements,
1282  dims.size(), numSymbols);
1283 }
1284 
1287  MultiAffineFunction &multiAff) {
1289  std::vector<SmallVector<int64_t, 8>> flattenedExprs;
1290  LogicalResult result = getFlattenedAffineExprs(map, &flattenedExprs, &cst);
1291 
1292  if (result.failed())
1293  return failure();
1294 
1295  DivisionRepr divs = cst.getLocalReprs();
1296  assert(divs.hasAllReprs() &&
1297  "AffineMap cannot produce divs without local representation");
1298 
1299  // TODO: We shouldn't have to do this conversion.
1300  Matrix<MPInt> mat(map.getNumResults(), map.getNumInputs() + divs.getNumDivs() + 1);
1301  for (unsigned i = 0, e = flattenedExprs.size(); i < e; ++i)
1302  for (unsigned j = 0, f = flattenedExprs[i].size(); j < f; ++j)
1303  mat(i, j) = flattenedExprs[i][j];
1304 
1305  multiAff = MultiAffineFunction(
1306  PresburgerSpace::getRelationSpace(map.getNumDims(), map.getNumResults(),
1307  map.getNumSymbols(), divs.getNumDivs()),
1308  mat, divs);
1309 
1310  return success();
1311 }
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 LogicalResult getFlattenedAffineExprs(ArrayRef< AffineExpr > exprs, unsigned numDims, unsigned numSymbols, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *localVarCst)
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 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 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...
Base type for affine expression.
Definition: AffineExpr.h:69
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:47
MLIRContext * getContext() const
Definition: AffineMap.cpp:327
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
unsigned getNumSymbols() const
Definition: AffineMap.cpp:384
unsigned getNumDims() const
Definition: AffineMap.cpp:380
ArrayRef< AffineExpr > getResults() const
Definition: AffineMap.cpp:393
unsigned getNumResults() const
Definition: AffineMap.cpp:388
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:486
unsigned getNumInputs() const
Definition: AffineMap.cpp:389
void dump() const
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:375
AffineExpr getAffineDimExpr(unsigned position)
Definition: Builders.cpp:371
FlatLinearConstraints is an extension of IntegerPolyhedron.
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
unsigned appendLocalVar(unsigned num=1)
LogicalResult flattenAlignedMapAndMergeLocals(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs)
Given an affine map that is aligned with this constraint system:
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatLinearConstraints.
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
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...
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.
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.
void clearAndCopyFrom(const IntegerRelation &other) override
Replaces the contents of this FlatLinearValueConstraints with other.
void swapVar(unsigned posA, unsigned posB) override
Swap the posA^th variable with the posB^th variable.
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...
unsigned insertSymbolVar(unsigned pos, unsigned num=1)
void fourierMotzkinEliminate(unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr) override
Eliminates the variable at the specified position using Fourier-Motzkin variable elimination,...
SmallVector< std::optional< Value >, 8 > values
Values corresponding to the (column) non-local variables of this constraint system appearing in the o...
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.
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
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.
bool hasConsistentState() const override
Returns false if the fields corresponding to various variable counts, or equality/inequality buffer s...
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...
ArrayRef< std::optional< Value > > getMaybeValues() const
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...
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)
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:378
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:118
bool hasAllReprs() const
Definition: Utils.h:134
unsigned getNumDivs() const
Definition: Utils.h:126
An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affin...
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
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.
void addInequality(ArrayRef< MPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
void addEquality(ArrayRef< MPInt > eq)
Adds an equality from the coefficients specified in eq.
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.
VarKind getVarKindAt(unsigned pos) const
Return the VarKind of the var at the specified position.
void addLocalFloorDiv(ArrayRef< MPInt > dividend, const MPInt &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.
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.
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...
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of vars starts.
friend MPInt floorDiv(const MPInt &lhs, const MPInt &rhs)
Definition: MPInt.h:382
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain...
Definition: PWMAFunction.h:41
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:285
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< MPInt > dividend, MPInt &divisor)
Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed...
Definition: Utils.cpp:232
Fraction abs(const Fraction &f)
Definition: Fraction.h:104
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt floorDiv(const MPInt &lhs, const MPInt &rhs)
Definition: MPInt.h:382
Include the generated interface declarations.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
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 ...
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, SmallVectorImpl< int64_t > *flattenedExpr, FlatLinearConstraints *cst=nullptr)
Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the dimensions,...
AffineExpr getAffineExprFromFlatForm(ArrayRef< int64_t > flatExprs, unsigned numDims, unsigned numSymbols, ArrayRef< AffineExpr > localExprs, MLIRContext *context)
Constructs an affine expression from a flat ArrayRef.
LogicalResult getFlattenedAffineExprs(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *cst=nullptr)
Flattens the result expressions of the map to their corresponding flattened forms and set in 'flatten...
AffineExpr getAffineConstantExpr(int64_t constant, MLIRContext *context)
Definition: AffineExpr.cpp:623
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:599
LogicalResult getMultiAffineFunctionFromMap(AffineMap map, presburger::MultiAffineFunction &multiAff)
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:72
AffineExpr getAffineSymbolExpr(unsigned position, MLIRContext *context)
Definition: AffineExpr.cpp:609
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
bool failed() const
Returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:44
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.