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