MLIR  16.0.0git
AffineStructures.cpp
Go to the documentation of this file.
1 //===- AffineStructures.cpp - MLIR Affine Structures Class-----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Structures for affine/polyhedral analysis of affine dialect ops.
10 //
11 //===----------------------------------------------------------------------===//
12 
21 #include "mlir/IR/IntegerSet.h"
22 #include "mlir/Support/LLVM.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/raw_ostream.h"
29 
30 #define DEBUG_TYPE "affine-structures"
31 
32 using namespace mlir;
33 using namespace presburger;
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 FlatAffineValueConstraints '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  FlatAffineValueConstraints *localVarCst) {
76  if (exprs.empty()) {
77  localVarCst->reset(numDims, numSymbols);
78  return success();
79  }
80 
81  AffineExprFlattener flattener(numDims, numSymbols);
82  // Use the same flattener to simplify each expression successively. This way
83  // local variables / expressions are shared.
84  for (auto expr : exprs) {
85  if (!expr.isPureAffine())
86  return failure();
87 
88  flattener.walkPostOrder(expr);
89  }
90 
91  assert(flattener.operandExprStack.size() == exprs.size());
92  flattenedExprs->clear();
93  flattenedExprs->assign(flattener.operandExprStack.begin(),
94  flattener.operandExprStack.end());
95 
96  if (localVarCst)
97  localVarCst->clearAndCopyFrom(flattener.localVarCst);
98 
99  return success();
100 }
101 
102 // Flattens 'expr' into 'flattenedExpr'. Returns failure if 'expr' was unable to
103 // be flattened (semi-affine expressions not handled yet).
106  unsigned numSymbols,
107  SmallVectorImpl<int64_t> *flattenedExpr,
108  FlatAffineValueConstraints *localVarCst) {
109  std::vector<SmallVector<int64_t, 8>> flattenedExprs;
110  LogicalResult ret = ::getFlattenedAffineExprs({expr}, numDims, numSymbols,
111  &flattenedExprs, localVarCst);
112  *flattenedExpr = flattenedExprs[0];
113  return ret;
114 }
115 
116 /// Flattens the expressions in map. Returns failure if 'expr' was unable to be
117 /// flattened (i.e., semi-affine expressions not handled yet).
119  AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
120  FlatAffineValueConstraints *localVarCst) {
121  if (map.getNumResults() == 0) {
122  localVarCst->reset(map.getNumDims(), map.getNumSymbols());
123  return success();
124  }
126  map.getNumSymbols(), flattenedExprs,
127  localVarCst);
128 }
129 
131  IntegerSet set, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
132  FlatAffineValueConstraints *localVarCst) {
133  if (set.getNumConstraints() == 0) {
134  localVarCst->reset(set.getNumDims(), set.getNumSymbols());
135  return success();
136  }
137  return ::getFlattenedAffineExprs(set.getConstraints(), set.getNumDims(),
138  set.getNumSymbols(), flattenedExprs,
139  localVarCst);
140 }
141 
142 //===----------------------------------------------------------------------===//
143 // FlatAffineConstraints / FlatAffineValueConstraints.
144 //===----------------------------------------------------------------------===//
145 
146 std::unique_ptr<FlatAffineValueConstraints>
148  return std::make_unique<FlatAffineValueConstraints>(*this);
149 }
150 
151 // Construct from an IntegerSet.
153  : IntegerPolyhedron(set.getNumInequalities(), set.getNumEqualities(),
154  set.getNumDims() + set.getNumSymbols() + 1,
155  PresburgerSpace::getSetSpace(set.getNumDims(),
156  set.getNumSymbols(),
157  /*numLocals=*/0)) {
158 
159  // Resize values.
161 
162  // Flatten expressions and add them to the constraint system.
163  std::vector<SmallVector<int64_t, 8>> flatExprs;
164  FlatAffineValueConstraints localVarCst;
165  if (failed(getFlattenedAffineExprs(set, &flatExprs, &localVarCst))) {
166  assert(false && "flattening unimplemented for semi-affine integer sets");
167  return;
168  }
169  assert(flatExprs.size() == set.getNumConstraints());
170  insertVar(VarKind::Local, getNumVarKind(VarKind::Local),
171  /*num=*/localVarCst.getNumLocalVars());
172 
173  for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
174  const auto &flatExpr = flatExprs[i];
175  assert(flatExpr.size() == getNumCols());
176  if (set.getEqFlags()[i]) {
177  addEquality(flatExpr);
178  } else {
179  addInequality(flatExpr);
180  }
181  }
182  // Add the other constraints involving local vars from flattening.
183  append(localVarCst);
184 }
185 
186 // Construct a hyperrectangular constraint set from ValueRanges that represent
187 // induction variables, lower and upper bounds. `ivs`, `lbs` and `ubs` are
188 // expected to match one to one. The order of variables and constraints is:
189 //
190 // ivs | lbs | ubs | eq/ineq
191 // ----+-----+-----+---------
192 // 1 -1 0 >= 0
193 // ----+-----+-----+---------
194 // -1 0 1 >= 0
195 //
196 // All dimensions as set as VarKind::SetDim.
199  ValueRange ubs) {
201  unsigned nIvs = ivs.size();
202  assert(nIvs == lbs.size() && "expected as many lower bounds as ivs");
203  assert(nIvs == ubs.size() && "expected as many upper bounds as ivs");
204 
205  if (nIvs == 0)
206  return res;
207 
208  res.appendDimVar(ivs);
209  unsigned lbsStart = res.appendDimVar(lbs);
210  unsigned ubsStart = res.appendDimVar(ubs);
211 
212  MLIRContext *ctx = ivs.front().getContext();
213  for (int ivIdx = 0, e = nIvs; ivIdx < e; ++ivIdx) {
214  // iv - lb >= 0
215  AffineMap lb = AffineMap::get(/*dimCount=*/3 * nIvs, /*symbolCount=*/0,
216  getAffineDimExpr(lbsStart + ivIdx, ctx));
217  if (failed(res.addBound(BoundType::LB, ivIdx, lb)))
218  llvm_unreachable("Unexpected FlatAffineValueConstraints creation error");
219  // -iv + ub >= 0
220  AffineMap ub = AffineMap::get(/*dimCount=*/3 * nIvs, /*symbolCount=*/0,
221  getAffineDimExpr(ubsStart + ivIdx, ctx));
222  if (failed(res.addBound(BoundType::UB, ivIdx, ub)))
223  llvm_unreachable("Unexpected FlatAffineValueConstraints creation error");
224  }
225  return res;
226 }
227 
228 void FlatAffineValueConstraints::reset(unsigned numReservedInequalities,
229  unsigned numReservedEqualities,
230  unsigned newNumReservedCols,
231  unsigned newNumDims,
232  unsigned newNumSymbols,
233  unsigned newNumLocals) {
234  assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 &&
235  "minimum 1 column");
236  *this = FlatAffineValueConstraints(numReservedInequalities,
237  numReservedEqualities, newNumReservedCols,
238  newNumDims, newNumSymbols, newNumLocals);
239 }
240 
241 void FlatAffineValueConstraints::reset(unsigned newNumDims,
242  unsigned newNumSymbols,
243  unsigned newNumLocals) {
244  reset(/*numReservedInequalities=*/0, /*numReservedEqualities=*/0,
245  /*numReservedCols=*/newNumDims + newNumSymbols + newNumLocals + 1,
246  newNumDims, newNumSymbols, newNumLocals);
247 }
248 
250  unsigned numReservedInequalities, unsigned numReservedEqualities,
251  unsigned newNumReservedCols, unsigned newNumDims, unsigned newNumSymbols,
252  unsigned newNumLocals, ArrayRef<Value> valArgs) {
253  assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 &&
254  "minimum 1 column");
255  SmallVector<Optional<Value>, 8> newVals;
256  if (!valArgs.empty())
257  newVals.assign(valArgs.begin(), valArgs.end());
258 
260  numReservedInequalities, numReservedEqualities, newNumReservedCols,
261  newNumDims, newNumSymbols, newNumLocals, newVals);
262 }
263 
264 void FlatAffineValueConstraints::reset(unsigned newNumDims,
265  unsigned newNumSymbols,
266  unsigned newNumLocals,
267  ArrayRef<Value> valArgs) {
268  reset(0, 0, newNumDims + newNumSymbols + newNumLocals + 1, newNumDims,
269  newNumSymbols, newNumLocals, valArgs);
270 }
271 
273  unsigned pos = getNumDimVars();
274  return insertVar(VarKind::SetDim, pos, vals);
275 }
276 
278  unsigned pos = getNumSymbolVars();
279  return insertVar(VarKind::Symbol, pos, vals);
280 }
281 
283  ValueRange vals) {
284  return insertVar(VarKind::SetDim, pos, vals);
285 }
286 
288  ValueRange vals) {
289  return insertVar(VarKind::Symbol, pos, vals);
290 }
291 
292 unsigned FlatAffineValueConstraints::insertVar(VarKind kind, unsigned pos,
293  unsigned num) {
294  unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
295 
296  if (kind != VarKind::Local) {
297  values.insert(values.begin() + absolutePos, num, None);
298  assert(values.size() == getNumDimAndSymbolVars());
299  }
300 
301  return absolutePos;
302 }
303 
304 unsigned FlatAffineValueConstraints::insertVar(VarKind kind, unsigned pos,
305  ValueRange vals) {
306  assert(!vals.empty() && "expected ValueRange with Values.");
307  assert(kind != VarKind::Local &&
308  "values cannot be attached to local variables.");
309  unsigned num = vals.size();
310  unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
311 
312  // If a Value is provided, insert it; otherwise use None.
313  for (unsigned i = 0; i < num; ++i)
314  values.insert(values.begin() + absolutePos + i,
315  vals[i] ? Optional<Value>(vals[i]) : None);
316 
317  assert(values.size() == getNumDimAndSymbolVars());
318  return absolutePos;
319 }
320 
322  return llvm::any_of(
323  values, [](const Optional<Value> &var) { return var.has_value(); });
324 }
325 
326 /// Checks if two constraint systems are in the same space, i.e., if they are
327 /// associated with the same set of variables, appearing in the same order.
329  const FlatAffineValueConstraints &b) {
330  return a.getNumDimVars() == b.getNumDimVars() &&
331  a.getNumSymbolVars() == b.getNumSymbolVars() &&
332  a.getNumVars() == b.getNumVars() &&
333  a.getMaybeValues().equals(b.getMaybeValues());
334 }
335 
336 /// Calls areVarsAligned to check if two constraint systems have the same set
337 /// of variables in the same order.
339  const FlatAffineValueConstraints &other) {
340  return areVarsAligned(*this, other);
341 }
342 
343 /// Checks if the SSA values associated with `cst`'s variables in range
344 /// [start, end) are unique.
345 static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique(
346  const FlatAffineValueConstraints &cst, unsigned start, unsigned end) {
347 
348  assert(start <= cst.getNumDimAndSymbolVars() &&
349  "Start position out of bounds");
350  assert(end <= cst.getNumDimAndSymbolVars() && "End position out of bounds");
351 
352  if (start >= end)
353  return true;
354 
355  SmallPtrSet<Value, 8> uniqueVars;
356  ArrayRef<Optional<Value>> maybeValues =
357  cst.getMaybeValues().slice(start, end - start);
358  for (Optional<Value> val : maybeValues) {
359  if (val && !uniqueVars.insert(*val).second)
360  return false;
361  }
362  return true;
363 }
364 
365 /// Checks if the SSA values associated with `cst`'s variables are unique.
366 static bool LLVM_ATTRIBUTE_UNUSED
368  return areVarsUnique(cst, 0, cst.getNumDimAndSymbolVars());
369 }
370 
371 /// Checks if the SSA values associated with `cst`'s variables of kind `kind`
372 /// are unique.
373 static bool LLVM_ATTRIBUTE_UNUSED
375 
376  if (kind == VarKind::SetDim)
377  return areVarsUnique(cst, 0, cst.getNumDimVars());
378  if (kind == VarKind::Symbol)
379  return areVarsUnique(cst, cst.getNumDimVars(),
380  cst.getNumDimAndSymbolVars());
381  llvm_unreachable("Unexpected VarKind");
382 }
383 
384 /// Merge and align the variables of A and B starting at 'offset', so that
385 /// both constraint systems get the union of the contained variables that is
386 /// dimension-wise and symbol-wise unique; both constraint systems are updated
387 /// so that they have the union of all variables, with A's original
388 /// variables appearing first followed by any of B's variables that didn't
389 /// appear in A. Local variables in B that have the same division
390 /// representation as local variables in A are merged into one.
391 // E.g.: Input: A has ((%i, %j) [%M, %N]) and B has (%k, %j) [%P, %N, %M])
392 // Output: both A, B have (%i, %j, %k) [%M, %N, %P]
393 static void mergeAndAlignVars(unsigned offset, FlatAffineValueConstraints *a,
395  assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
396  // A merge/align isn't meaningful if a cst's vars aren't distinct.
397  assert(areVarsUnique(*a) && "A's values aren't unique");
398  assert(areVarsUnique(*b) && "B's values aren't unique");
399 
400  assert(
401  llvm::all_of(llvm::drop_begin(a->getMaybeValues(), offset),
402  [](const Optional<Value> &var) { return var.has_value(); }));
403 
404  assert(
405  llvm::all_of(llvm::drop_begin(b->getMaybeValues(), offset),
406  [](const Optional<Value> &var) { return var.has_value(); }));
407 
408  SmallVector<Value, 4> aDimValues;
409  a->getValues(offset, a->getNumDimVars(), &aDimValues);
410 
411  {
412  // Merge dims from A into B.
413  unsigned d = offset;
414  for (auto aDimValue : aDimValues) {
415  unsigned loc;
416  if (b->findVar(aDimValue, &loc)) {
417  assert(loc >= offset && "A's dim appears in B's aligned range");
418  assert(loc < b->getNumDimVars() &&
419  "A's dim appears in B's non-dim position");
420  b->swapVar(d, loc);
421  } else {
422  b->insertDimVar(d, aDimValue);
423  }
424  d++;
425  }
426  // Dimensions that are in B, but not in A, are added at the end.
427  for (unsigned t = a->getNumDimVars(), e = b->getNumDimVars(); t < e; t++) {
428  a->appendDimVar(b->getValue(t));
429  }
430  assert(a->getNumDimVars() == b->getNumDimVars() &&
431  "expected same number of dims");
432  }
433 
434  // Merge and align symbols of A and B
435  a->mergeSymbolVars(*b);
436  // Merge and align locals of A and B
437  a->mergeLocalVars(*b);
438 
439  assert(areVarsAligned(*a, *b) && "IDs expected to be aligned");
440 }
441 
442 // Call 'mergeAndAlignVars' to align constraint systems of 'this' and 'other'.
444  unsigned offset, FlatAffineValueConstraints *other) {
445  mergeAndAlignVars(offset, this, other);
446 }
447 
450  return composeMatchingMap(
451  computeAlignedMap(vMap->getAffineMap(), vMap->getOperands()));
452 }
453 
454 // Similar to `composeMap` except that no Values need be associated with the
455 // constraint system nor are they looked at -- the dimensions and symbols of
456 // `other` are expected to correspond 1:1 to `this` system.
458  assert(other.getNumDims() == getNumDimVars() && "dim mismatch");
459  assert(other.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");
460 
461  std::vector<SmallVector<int64_t, 8>> flatExprs;
462  if (failed(flattenAlignedMapAndMergeLocals(other, &flatExprs)))
463  return failure();
464  assert(flatExprs.size() == other.getNumResults());
465 
466  // Add dimensions corresponding to the map's results.
467  insertDimVar(/*pos=*/0, /*num=*/other.getNumResults());
468 
469  // We add one equality for each result connecting the result dim of the map to
470  // the other variables.
471  // E.g.: if the expression is 16*i0 + i1, and this is the r^th
472  // iteration/result of the value map, we are adding the equality:
473  // d_r - 16*i0 - i1 = 0. Similarly, when flattening (i0 + 1, i0 + 8*i2), we
474  // add two equalities: d_0 - i0 - 1 == 0, d1 - i0 - 8*i2 == 0.
475  for (unsigned r = 0, e = flatExprs.size(); r < e; r++) {
476  const auto &flatExpr = flatExprs[r];
477  assert(flatExpr.size() >= other.getNumInputs() + 1);
478 
479  SmallVector<int64_t, 8> eqToAdd(getNumCols(), 0);
480  // Set the coefficient for this result to one.
481  eqToAdd[r] = 1;
482 
483  // Dims and symbols.
484  for (unsigned i = 0, f = other.getNumInputs(); i < f; i++) {
485  // Negate `eq[r]` since the newly added dimension will be set to this one.
486  eqToAdd[e + i] = -flatExpr[i];
487  }
488  // Local columns of `eq` are at the beginning.
489  unsigned j = getNumDimVars() + getNumSymbolVars();
490  unsigned end = flatExpr.size() - 1;
491  for (unsigned i = other.getNumInputs(); i < end; i++, j++) {
492  eqToAdd[j] = -flatExpr[i];
493  }
494 
495  // Constant term.
496  eqToAdd[getNumCols() - 1] = -flatExpr[flatExpr.size() - 1];
497 
498  // Add the equality connecting the result of the map to this constraint set.
499  addEquality(eqToAdd);
500  }
501 
502  return success();
503 }
504 
505 // Turn a symbol into a dimension.
507  unsigned pos;
508  if (cst->findVar(value, &pos) && pos >= cst->getNumDimVars() &&
509  pos < cst->getNumDimAndSymbolVars()) {
510  cst->swapVar(pos, cst->getNumDimVars());
511  cst->setDimSymbolSeparation(cst->getNumSymbolVars() - 1);
512  }
513 }
514 
515 /// Merge and align symbols of `this` and `other` such that both get union of
516 /// of symbols that are unique. Symbols in `this` and `other` should be
517 /// unique. Symbols with Value as `None` are considered to be inequal to all
518 /// other symbols.
521 
522  assert(areVarsUnique(*this, VarKind::Symbol) && "Symbol vars are not unique");
523  assert(areVarsUnique(other, VarKind::Symbol) && "Symbol vars are not unique");
524 
525  SmallVector<Value, 4> aSymValues;
527 
528  // Merge symbols: merge symbols into `other` first from `this`.
529  unsigned s = other.getNumDimVars();
530  for (Value aSymValue : aSymValues) {
531  unsigned loc;
532  // If the var is a symbol in `other`, then align it, otherwise assume that
533  // it is a new symbol
534  if (other.findVar(aSymValue, &loc) && loc >= other.getNumDimVars() &&
535  loc < other.getNumDimAndSymbolVars())
536  other.swapVar(s, loc);
537  else
538  other.insertSymbolVar(s - other.getNumDimVars(), aSymValue);
539  s++;
540  }
541 
542  // Symbols that are in other, but not in this, are added at the end.
543  for (unsigned t = other.getNumDimVars() + getNumSymbolVars(),
544  e = other.getNumDimAndSymbolVars();
545  t < e; t++)
547 
548  assert(getNumSymbolVars() == other.getNumSymbolVars() &&
549  "expected same number of symbols");
550  assert(areVarsUnique(*this, VarKind::Symbol) && "Symbol vars are not unique");
551  assert(areVarsUnique(other, VarKind::Symbol) && "Symbol vars are not unique");
552 }
553 
554 // Changes all symbol variables which are loop IVs to dim variables.
556  // Gather all symbols which are loop IVs.
557  SmallVector<Value, 4> loopIVs;
558  for (unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++) {
560  loopIVs.push_back(getValue(i));
561  }
562  // Turn each symbol in 'loopIVs' into a dim variable.
563  for (auto iv : loopIVs) {
564  turnSymbolIntoDim(this, iv);
565  }
566 }
567 
569  if (containsVar(val))
570  return;
571 
572  // Caller is expected to fully compose map/operands if necessary.
573  assert((isTopLevelValue(val) || isForInductionVar(val)) &&
574  "non-terminal symbol / loop IV expected");
575  // Outer loop IVs could be used in forOp's bounds.
576  if (auto loop = getForInductionVarOwner(val)) {
577  appendDimVar(val);
578  if (failed(this->addAffineForOpDomain(loop)))
579  LLVM_DEBUG(
580  loop.emitWarning("failed to add domain info to constraint system"));
581  return;
582  }
583  // Add top level symbol.
584  appendSymbolVar(val);
585  // Check if the symbol is a constant.
586  if (auto constOp = val.getDefiningOp<arith::ConstantIndexOp>())
587  addBound(BoundType::EQ, val, constOp.value());
588 }
589 
592  unsigned pos;
593  // Pre-condition for this method.
594  if (!findVar(forOp.getInductionVar(), &pos)) {
595  assert(false && "Value not found");
596  return failure();
597  }
598 
599  int64_t step = forOp.getStep();
600  if (step != 1) {
601  if (!forOp.hasConstantLowerBound())
602  LLVM_DEBUG(forOp.emitWarning("domain conservatively approximated"));
603  else {
604  // Add constraints for the stride.
605  // (iv - lb) % step = 0 can be written as:
606  // (iv - lb) - step * q = 0 where q = (iv - lb) / step.
607  // Add local variable 'q' and add the above equality.
608  // The first constraint is q = (iv - lb) floordiv step
609  SmallVector<int64_t, 8> dividend(getNumCols(), 0);
610  int64_t lb = forOp.getConstantLowerBound();
611  dividend[pos] = 1;
612  dividend.back() -= lb;
613  addLocalFloorDiv(dividend, step);
614  // Second constraint: (iv - lb) - step * q = 0.
616  eq[pos] = 1;
617  eq.back() -= lb;
618  // For the local var just added above.
619  eq[getNumCols() - 2] = -step;
620  addEquality(eq);
621  }
622  }
623 
624  if (forOp.hasConstantLowerBound()) {
625  addBound(BoundType::LB, pos, forOp.getConstantLowerBound());
626  } else {
627  // Non-constant lower bound case.
628  if (failed(addBound(BoundType::LB, pos, forOp.getLowerBoundMap(),
629  forOp.getLowerBoundOperands())))
630  return failure();
631  }
632 
633  if (forOp.hasConstantUpperBound()) {
634  addBound(BoundType::UB, pos, forOp.getConstantUpperBound() - 1);
635  return success();
636  }
637  // Non-constant upper bound case.
638  return addBound(BoundType::UB, pos, forOp.getUpperBoundMap(),
639  forOp.getUpperBoundOperands());
640 }
641 
644  ArrayRef<AffineMap> ubMaps,
645  ArrayRef<Value> operands) {
646  assert(lbMaps.size() == ubMaps.size());
647  assert(lbMaps.size() <= getNumDimVars());
648 
649  for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
650  AffineMap lbMap = lbMaps[i];
651  AffineMap ubMap = ubMaps[i];
652  assert(!lbMap || lbMap.getNumInputs() == operands.size());
653  assert(!ubMap || ubMap.getNumInputs() == operands.size());
654 
655  // Check if this slice is just an equality along this dimension. If so,
656  // retrieve the existing loop it equates to and add it to the system.
657  if (lbMap && ubMap && lbMap.getNumResults() == 1 &&
658  ubMap.getNumResults() == 1 &&
659  lbMap.getResult(0) + 1 == ubMap.getResult(0) &&
660  // The condition above will be true for maps describing a single
661  // iteration (e.g., lbMap.getResult(0) = 0, ubMap.getResult(0) = 1).
662  // Make sure we skip those cases by checking that the lb result is not
663  // just a constant.
664  !lbMap.getResult(0).isa<AffineConstantExpr>()) {
665  // Limited support: we expect the lb result to be just a loop dimension.
666  // Not supported otherwise for now.
667  AffineDimExpr result = lbMap.getResult(0).dyn_cast<AffineDimExpr>();
668  if (!result)
669  return failure();
670 
671  AffineForOp loop =
672  getForInductionVarOwner(operands[result.getPosition()]);
673  if (!loop)
674  return failure();
675 
676  if (failed(addAffineForOpDomain(loop)))
677  return failure();
678  continue;
679  }
680 
681  // This slice refers to a loop that doesn't exist in the IR yet. Add its
682  // bounds to the system assuming its dimension variable position is the
683  // same as the position of the loop in the loop nest.
684  if (lbMap && failed(addBound(BoundType::LB, i, lbMap, operands)))
685  return failure();
686  if (ubMap && failed(addBound(BoundType::UB, i, ubMap, operands)))
687  return failure();
688  }
689  return success();
690 }
691 
693  // Create the base constraints from the integer set attached to ifOp.
694  FlatAffineValueConstraints cst(ifOp.getIntegerSet());
695 
696  // Bind vars in the constraints to ifOp operands.
697  SmallVector<Value, 4> operands = ifOp.getOperands();
698  cst.setValues(0, cst.getNumDimAndSymbolVars(), operands);
699 
700  // Merge the constraints from ifOp to the current domain. We need first merge
701  // and align the IDs from both constraints, and then append the constraints
702  // from the ifOp into the current one.
704  append(cst);
705 }
706 
708  return IntegerPolyhedron::hasConsistentState() &&
709  values.size() == getNumDimAndSymbolVars();
710 }
711 
713  unsigned varLimit) {
714  IntegerPolyhedron::removeVarRange(kind, varStart, varLimit);
715  unsigned offset = getVarKindOffset(kind);
716 
717  if (kind != VarKind::Local) {
718  values.erase(values.begin() + varStart + offset,
719  values.begin() + varLimit + offset);
720  }
721 }
722 
723 // Determine whether the variable at 'pos' (say var_r) can be expressed as
724 // modulo of another known variable (say var_n) w.r.t a constant. For example,
725 // if the following constraints hold true:
726 // ```
727 // 0 <= var_r <= divisor - 1
728 // var_n - (divisor * q_expr) = var_r
729 // ```
730 // where `var_n` is a known variable (called dividend), and `q_expr` is an
731 // `AffineExpr` (called the quotient expression), `var_r` can be written as:
732 //
733 // `var_r = var_n mod divisor`.
734 //
735 // Additionally, in a special case of the above constaints where `q_expr` is an
736 // variable itself that is not yet known (say `var_q`), it can be written as a
737 // floordiv in the following way:
738 //
739 // `var_q = var_n floordiv divisor`.
740 //
741 // Returns true if the above mod or floordiv are detected, updating 'memo' with
742 // these new expressions. Returns false otherwise.
743 static bool detectAsMod(const FlatAffineValueConstraints &cst, unsigned pos,
744  int64_t lbConst, int64_t ubConst,
746  MLIRContext *context) {
747  assert(pos < cst.getNumVars() && "invalid position");
748 
749  // Check if a divisor satisfying the condition `0 <= var_r <= divisor - 1` can
750  // be determined.
751  if (lbConst != 0 || ubConst < 1)
752  return false;
753  int64_t divisor = ubConst + 1;
754 
755  // Check for the aforementioned conditions in each equality.
756  for (unsigned curEquality = 0, numEqualities = cst.getNumEqualities();
757  curEquality < numEqualities; curEquality++) {
758  int64_t coefficientAtPos = cst.atEq64(curEquality, pos);
759  // If current equality does not involve `var_r`, continue to the next
760  // equality.
761  if (coefficientAtPos == 0)
762  continue;
763 
764  // Constant term should be 0 in this equality.
765  if (cst.atEq64(curEquality, cst.getNumCols() - 1) != 0)
766  continue;
767 
768  // Traverse through the equality and construct the dividend expression
769  // `dividendExpr`, to contain all the variables which are known and are
770  // not divisible by `(coefficientAtPos * divisor)`. Hope here is that the
771  // `dividendExpr` gets simplified into a single variable `var_n` discussed
772  // above.
773  auto dividendExpr = getAffineConstantExpr(0, context);
774 
775  // Track the terms that go into quotient expression, later used to detect
776  // additional floordiv.
777  unsigned quotientCount = 0;
778  int quotientPosition = -1;
779  int quotientSign = 1;
780 
781  // Consider each term in the current equality.
782  unsigned curVar, e;
783  for (curVar = 0, e = cst.getNumDimAndSymbolVars(); curVar < e; ++curVar) {
784  // Ignore var_r.
785  if (curVar == pos)
786  continue;
787  int64_t coefficientOfCurVar = cst.atEq64(curEquality, curVar);
788  // Ignore vars that do not contribute to the current equality.
789  if (coefficientOfCurVar == 0)
790  continue;
791  // Check if the current var goes into the quotient expression.
792  if (coefficientOfCurVar % (divisor * coefficientAtPos) == 0) {
793  quotientCount++;
794  quotientPosition = curVar;
795  quotientSign = (coefficientOfCurVar * coefficientAtPos) > 0 ? 1 : -1;
796  continue;
797  }
798  // Variables that are part of dividendExpr should be known.
799  if (!memo[curVar])
800  break;
801  // Append the current variable to the dividend expression.
802  dividendExpr = dividendExpr + memo[curVar] * coefficientOfCurVar;
803  }
804 
805  // Can't construct expression as it depends on a yet uncomputed var.
806  if (curVar < e)
807  continue;
808 
809  // Express `var_r` in terms of the other vars collected so far.
810  if (coefficientAtPos > 0)
811  dividendExpr = (-dividendExpr).floorDiv(coefficientAtPos);
812  else
813  dividendExpr = dividendExpr.floorDiv(-coefficientAtPos);
814 
815  // Simplify the expression.
816  dividendExpr = simplifyAffineExpr(dividendExpr, cst.getNumDimVars(),
817  cst.getNumSymbolVars());
818  // Only if the final dividend expression is just a single var (which we call
819  // `var_n`), we can proceed.
820  // TODO: Handle AffineSymbolExpr as well. There is no reason to restrict it
821  // to dims themselves.
822  auto dimExpr = dividendExpr.dyn_cast<AffineDimExpr>();
823  if (!dimExpr)
824  continue;
825 
826  // Express `var_r` as `var_n % divisor` and store the expression in `memo`.
827  if (quotientCount >= 1) {
828  auto ub = cst.getConstantBound64(
829  FlatAffineValueConstraints::BoundType::UB, dimExpr.getPosition());
830  // If `var_n` has an upperbound that is less than the divisor, mod can be
831  // eliminated altogether.
832  if (ub && *ub < divisor)
833  memo[pos] = dimExpr;
834  else
835  memo[pos] = dimExpr % divisor;
836  // If a unique quotient `var_q` was seen, it can be expressed as
837  // `var_n floordiv divisor`.
838  if (quotientCount == 1 && !memo[quotientPosition])
839  memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;
840 
841  return true;
842  }
843  }
844  return false;
845 }
846 
847 /// Check if the pos^th variable can be expressed as a floordiv of an affine
848 /// function of other variables (where the divisor is a positive constant)
849 /// given the initial set of expressions in `exprs`. If it can be, the
850 /// corresponding position in `exprs` is set as the detected affine expr. For
851 /// eg: 4q <= i + j <= 4q + 3 <=> q = (i + j) floordiv 4. An equality can
852 /// also yield a floordiv: eg. 4q = i + j <=> q = (i + j) floordiv 4. 32q + 28
853 /// <= i <= 32q + 31 => q = i floordiv 32.
855  unsigned pos, MLIRContext *context,
857  assert(pos < cst.getNumVars() && "invalid position");
858 
859  // Get upper-lower bound pair for this variable.
860  SmallVector<bool, 8> foundRepr(cst.getNumVars(), false);
861  for (unsigned i = 0, e = cst.getNumVars(); i < e; ++i)
862  if (exprs[i])
863  foundRepr[i] = true;
864 
865  SmallVector<int64_t, 8> dividend(cst.getNumCols());
866  unsigned divisor;
867  auto ulPair = computeSingleVarRepr(cst, foundRepr, pos, dividend, divisor);
868 
869  // No upper-lower bound pair found for this var.
870  if (ulPair.kind == ReprKind::None || ulPair.kind == ReprKind::Equality)
871  return false;
872 
873  // Construct the dividend expression.
874  auto dividendExpr = getAffineConstantExpr(dividend.back(), context);
875  for (unsigned c = 0, f = cst.getNumVars(); c < f; c++)
876  if (dividend[c] != 0)
877  dividendExpr = dividendExpr + dividend[c] * exprs[c];
878 
879  // Successfully detected the floordiv.
880  exprs[pos] = dividendExpr.floorDiv(divisor);
881  return true;
882 }
883 
884 std::pair<AffineMap, AffineMap>
886  unsigned pos, unsigned offset, unsigned num, unsigned symStartPos,
887  ArrayRef<AffineExpr> localExprs, MLIRContext *context) const {
888  assert(pos + offset < getNumDimVars() && "invalid dim start pos");
889  assert(symStartPos >= (pos + offset) && "invalid sym start pos");
890  assert(getNumLocalVars() == localExprs.size() &&
891  "incorrect local exprs count");
892 
893  SmallVector<unsigned, 4> lbIndices, ubIndices, eqIndices;
894  getLowerAndUpperBoundIndices(pos + offset, &lbIndices, &ubIndices, &eqIndices,
895  offset, num);
896 
897  /// Add to 'b' from 'a' in set [0, offset) U [offset + num, symbStartPos).
898  auto addCoeffs = [&](ArrayRef<int64_t> a, SmallVectorImpl<int64_t> &b) {
899  b.clear();
900  for (unsigned i = 0, e = a.size(); i < e; ++i) {
901  if (i < offset || i >= offset + num)
902  b.push_back(a[i]);
903  }
904  };
905 
908  unsigned dimCount = symStartPos - num;
909  unsigned symCount = getNumDimAndSymbolVars() - symStartPos;
910  lbExprs.reserve(lbIndices.size() + eqIndices.size());
911  // Lower bound expressions.
912  for (auto idx : lbIndices) {
913  auto ineq = getInequality64(idx);
914  // Extract the lower bound (in terms of other coeff's + const), i.e., if
915  // i - j + 1 >= 0 is the constraint, 'pos' is for i the lower bound is j
916  // - 1.
917  addCoeffs(ineq, lb);
918  std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
919  auto expr =
920  getAffineExprFromFlatForm(lb, dimCount, symCount, localExprs, context);
921  // expr ceildiv divisor is (expr + divisor - 1) floordiv divisor
922  int64_t divisor = std::abs(ineq[pos + offset]);
923  expr = (expr + divisor - 1).floorDiv(divisor);
924  lbExprs.push_back(expr);
925  }
926 
928  ubExprs.reserve(ubIndices.size() + eqIndices.size());
929  // Upper bound expressions.
930  for (auto idx : ubIndices) {
931  auto ineq = getInequality64(idx);
932  // Extract the upper bound (in terms of other coeff's + const).
933  addCoeffs(ineq, ub);
934  auto expr =
935  getAffineExprFromFlatForm(ub, dimCount, symCount, localExprs, context);
936  expr = expr.floorDiv(std::abs(ineq[pos + offset]));
937  // Upper bound is exclusive.
938  ubExprs.push_back(expr + 1);
939  }
940 
941  // Equalities. It's both a lower and a upper bound.
943  for (auto idx : eqIndices) {
944  auto eq = getEquality64(idx);
945  addCoeffs(eq, b);
946  if (eq[pos + offset] > 0)
947  std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());
948 
949  // Extract the upper bound (in terms of other coeff's + const).
950  auto expr =
951  getAffineExprFromFlatForm(b, dimCount, symCount, localExprs, context);
952  expr = expr.floorDiv(std::abs(eq[pos + offset]));
953  // Upper bound is exclusive.
954  ubExprs.push_back(expr + 1);
955  // Lower bound.
956  expr =
957  getAffineExprFromFlatForm(b, dimCount, symCount, localExprs, context);
958  expr = expr.ceilDiv(std::abs(eq[pos + offset]));
959  lbExprs.push_back(expr);
960  }
961 
962  auto lbMap = AffineMap::get(dimCount, symCount, lbExprs, context);
963  auto ubMap = AffineMap::get(dimCount, symCount, ubExprs, context);
964 
965  return {lbMap, ubMap};
966 }
967 
968 /// Computes the lower and upper bounds of the first 'num' dimensional
969 /// variables (starting at 'offset') as affine maps of the remaining
970 /// variables (dimensional and symbolic variables). Local variables are
971 /// themselves explicitly computed as affine functions of other variables in
972 /// this process if needed.
974  unsigned offset, unsigned num, MLIRContext *context,
976  bool getClosedUB) {
977  assert(num < getNumDimVars() && "invalid range");
978 
979  // Basic simplification.
981 
982  LLVM_DEBUG(llvm::dbgs() << "getSliceBounds for first " << num
983  << " variables\n");
984  LLVM_DEBUG(dump());
985 
986  // Record computed/detected variables.
988  // Initialize dimensional and symbolic variables.
989  for (unsigned i = 0, e = getNumDimVars(); i < e; i++) {
990  if (i < offset)
991  memo[i] = getAffineDimExpr(i, context);
992  else if (i >= offset + num)
993  memo[i] = getAffineDimExpr(i - num, context);
994  }
995  for (unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++)
996  memo[i] = getAffineSymbolExpr(i - getNumDimVars(), context);
997 
998  bool changed;
999  do {
1000  changed = false;
1001  // Identify yet unknown variables as constants or mod's / floordiv's of
1002  // other variables if possible.
1003  for (unsigned pos = 0; pos < getNumVars(); pos++) {
1004  if (memo[pos])
1005  continue;
1006 
1007  auto lbConst = getConstantBound64(BoundType::LB, pos);
1008  auto ubConst = getConstantBound64(BoundType::UB, pos);
1009  if (lbConst.has_value() && ubConst.has_value()) {
1010  // Detect equality to a constant.
1011  if (lbConst.value() == ubConst.value()) {
1012  memo[pos] = getAffineConstantExpr(lbConst.value(), context);
1013  changed = true;
1014  continue;
1015  }
1016 
1017  // Detect an variable as modulo of another variable w.r.t a
1018  // constant.
1019  if (detectAsMod(*this, pos, lbConst.value(), ubConst.value(), memo,
1020  context)) {
1021  changed = true;
1022  continue;
1023  }
1024  }
1025 
1026  // Detect an variable as a floordiv of an affine function of other
1027  // variables (divisor is a positive constant).
1028  if (detectAsFloorDiv(*this, pos, context, memo)) {
1029  changed = true;
1030  continue;
1031  }
1032 
1033  // Detect an variable as an expression of other variables.
1034  unsigned idx;
1035  if (!findConstraintWithNonZeroAt(pos, /*isEq=*/true, &idx)) {
1036  continue;
1037  }
1038 
1039  // Build AffineExpr solving for variable 'pos' in terms of all others.
1040  auto expr = getAffineConstantExpr(0, context);
1041  unsigned j, e;
1042  for (j = 0, e = getNumVars(); j < e; ++j) {
1043  if (j == pos)
1044  continue;
1045  int64_t c = atEq64(idx, j);
1046  if (c == 0)
1047  continue;
1048  // If any of the involved IDs hasn't been found yet, we can't proceed.
1049  if (!memo[j])
1050  break;
1051  expr = expr + memo[j] * c;
1052  }
1053  if (j < e)
1054  // Can't construct expression as it depends on a yet uncomputed
1055  // variable.
1056  continue;
1057 
1058  // Add constant term to AffineExpr.
1059  expr = expr + atEq64(idx, getNumVars());
1060  int64_t vPos = atEq64(idx, pos);
1061  assert(vPos != 0 && "expected non-zero here");
1062  if (vPos > 0)
1063  expr = (-expr).floorDiv(vPos);
1064  else
1065  // vPos < 0.
1066  expr = expr.floorDiv(-vPos);
1067  // Successfully constructed expression.
1068  memo[pos] = expr;
1069  changed = true;
1070  }
1071  // This loop is guaranteed to reach a fixed point - since once an
1072  // variable's explicit form is computed (in memo[pos]), it's not updated
1073  // again.
1074  } while (changed);
1075 
1076  int64_t ubAdjustment = getClosedUB ? 0 : 1;
1077 
1078  // Set the lower and upper bound maps for all the variables that were
1079  // computed as affine expressions of the rest as the "detected expr" and
1080  // "detected expr + 1" respectively; set the undetected ones to null.
1082  for (unsigned pos = 0; pos < num; pos++) {
1083  unsigned numMapDims = getNumDimVars() - num;
1084  unsigned numMapSymbols = getNumSymbolVars();
1085  AffineExpr expr = memo[pos + offset];
1086  if (expr)
1087  expr = simplifyAffineExpr(expr, numMapDims, numMapSymbols);
1088 
1089  AffineMap &lbMap = (*lbMaps)[pos];
1090  AffineMap &ubMap = (*ubMaps)[pos];
1091 
1092  if (expr) {
1093  lbMap = AffineMap::get(numMapDims, numMapSymbols, expr);
1094  ubMap = AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
1095  } else {
1096  // TODO: Whenever there are local variables in the dependence
1097  // constraints, we'll conservatively over-approximate, since we don't
1098  // always explicitly compute them above (in the while loop).
1099  if (getNumLocalVars() == 0) {
1100  // Work on a copy so that we don't update this constraint system.
1101  if (!tmpClone) {
1102  tmpClone.emplace(FlatAffineValueConstraints(*this));
1103  // Removing redundant inequalities is necessary so that we don't get
1104  // redundant loop bounds.
1105  tmpClone->removeRedundantInequalities();
1106  }
1107  std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
1108  pos, offset, num, getNumDimVars(), /*localExprs=*/{}, context);
1109  }
1110 
1111  // If the above fails, we'll just use the constant lower bound and the
1112  // constant upper bound (if they exist) as the slice bounds.
1113  // TODO: being conservative for the moment in cases that
1114  // lead to multiple bounds - until getConstDifference in LoopFusion.cpp is
1115  // fixed (b/126426796).
1116  if (!lbMap || lbMap.getNumResults() > 1) {
1117  LLVM_DEBUG(llvm::dbgs()
1118  << "WARNING: Potentially over-approximating slice lb\n");
1119  auto lbConst = getConstantBound64(BoundType::LB, pos + offset);
1120  if (lbConst.has_value()) {
1121  lbMap =
1122  AffineMap::get(numMapDims, numMapSymbols,
1123  getAffineConstantExpr(lbConst.value(), context));
1124  }
1125  }
1126  if (!ubMap || ubMap.getNumResults() > 1) {
1127  LLVM_DEBUG(llvm::dbgs()
1128  << "WARNING: Potentially over-approximating slice ub\n");
1129  auto ubConst = getConstantBound64(BoundType::UB, pos + offset);
1130  if (ubConst.has_value()) {
1131  ubMap = AffineMap::get(
1132  numMapDims, numMapSymbols,
1133  getAffineConstantExpr(ubConst.value() + ubAdjustment, context));
1134  }
1135  }
1136  }
1137  LLVM_DEBUG(llvm::dbgs()
1138  << "lb map for pos = " << Twine(pos + offset) << ", expr: ");
1139  LLVM_DEBUG(lbMap.dump(););
1140  LLVM_DEBUG(llvm::dbgs()
1141  << "ub map for pos = " << Twine(pos + offset) << ", expr: ");
1142  LLVM_DEBUG(ubMap.dump(););
1143  }
1144 }
1145 
1147  AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs) {
1148  FlatAffineValueConstraints localCst;
1149  if (failed(getFlattenedAffineExprs(map, flattenedExprs, &localCst))) {
1150  LLVM_DEBUG(llvm::dbgs()
1151  << "composition unimplemented for semi-affine maps\n");
1152  return failure();
1153  }
1154 
1155  // Add localCst information.
1156  if (localCst.getNumLocalVars() > 0) {
1157  unsigned numLocalVars = getNumLocalVars();
1158  // Insert local dims of localCst at the beginning.
1159  insertLocalVar(/*pos=*/0, /*num=*/localCst.getNumLocalVars());
1160  // Insert local dims of `this` at the end of localCst.
1161  localCst.appendLocalVar(/*num=*/numLocalVars);
1162  // Dimensions of localCst and this constraint set match. Append localCst to
1163  // this constraint set.
1164  append(localCst);
1165  }
1166 
1167  return success();
1168 }
1169 
1171  AffineMap boundMap,
1172  bool isClosedBound) {
1173  assert(boundMap.getNumDims() == getNumDimVars() && "dim mismatch");
1174  assert(boundMap.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");
1175  assert(pos < getNumDimAndSymbolVars() && "invalid position");
1176  assert((type != BoundType::EQ || isClosedBound) &&
1177  "EQ bound must be closed.");
1178 
1179  // Equality follows the logic of lower bound except that we add an equality
1180  // instead of an inequality.
1181  assert((type != BoundType::EQ || boundMap.getNumResults() == 1) &&
1182  "single result expected");
1183  bool lower = type == BoundType::LB || type == BoundType::EQ;
1184 
1185  std::vector<SmallVector<int64_t, 8>> flatExprs;
1186  if (failed(flattenAlignedMapAndMergeLocals(boundMap, &flatExprs)))
1187  return failure();
1188  assert(flatExprs.size() == boundMap.getNumResults());
1189 
1190  // Add one (in)equality for each result.
1191  for (const auto &flatExpr : flatExprs) {
1192  SmallVector<int64_t> ineq(getNumCols(), 0);
1193  // Dims and symbols.
1194  for (unsigned j = 0, e = boundMap.getNumInputs(); j < e; j++) {
1195  ineq[j] = lower ? -flatExpr[j] : flatExpr[j];
1196  }
1197  // Invalid bound: pos appears in `boundMap`.
1198  // TODO: This should be an assertion. Fix `addDomainFromSliceMaps` and/or
1199  // its callers to prevent invalid bounds from being added.
1200  if (ineq[pos] != 0)
1201  continue;
1202  ineq[pos] = lower ? 1 : -1;
1203  // Local columns of `ineq` are at the beginning.
1204  unsigned j = getNumDimVars() + getNumSymbolVars();
1205  unsigned end = flatExpr.size() - 1;
1206  for (unsigned i = boundMap.getNumInputs(); i < end; i++, j++) {
1207  ineq[j] = lower ? -flatExpr[i] : flatExpr[i];
1208  }
1209  // Make the bound closed in if flatExpr is open. The inequality is always
1210  // created in the upper bound form, so the adjustment is -1.
1211  int64_t boundAdjustment = (isClosedBound || type == BoundType::EQ) ? 0 : -1;
1212  // Constant term.
1213  ineq[getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
1214  : flatExpr[flatExpr.size() - 1]) +
1215  boundAdjustment;
1216  type == BoundType::EQ ? addEquality(ineq) : addInequality(ineq);
1217  }
1218 
1219  return success();
1220 }
1221 
1223  AffineMap boundMap) {
1224  return addBound(type, pos, boundMap, /*isClosedBound=*/type != BoundType::UB);
1225 }
1226 
1227 AffineMap
1229  ValueRange operands) const {
1230  assert(map.getNumInputs() == operands.size() && "number of inputs mismatch");
1231 
1232  SmallVector<Value> dims, syms;
1233 #ifndef NDEBUG
1234  SmallVector<Value> newSyms;
1235  SmallVector<Value> *newSymsPtr = &newSyms;
1236 #else
1237  SmallVector<Value> *newSymsPtr = nullptr;
1238 #endif // NDEBUG
1239 
1240  dims.reserve(getNumDimVars());
1241  syms.reserve(getNumSymbolVars());
1242  for (unsigned i = getVarKindOffset(VarKind::SetDim),
1243  e = getVarKindEnd(VarKind::SetDim);
1244  i < e; ++i)
1245  dims.push_back(values[i] ? *values[i] : Value());
1246  for (unsigned i = getVarKindOffset(VarKind::Symbol),
1247  e = getVarKindEnd(VarKind::Symbol);
1248  i < e; ++i)
1249  syms.push_back(values[i] ? *values[i] : Value());
1250 
1251  AffineMap alignedMap =
1252  alignAffineMapWithValues(map, operands, dims, syms, newSymsPtr);
1253  // All symbols are already part of this FlatAffineConstraints.
1254  assert(syms.size() == newSymsPtr->size() && "unexpected new/missing symbols");
1255  assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
1256  "unexpected new/missing symbols");
1257  return alignedMap;
1258 }
1259 
1261  AffineMap boundMap,
1262  ValueRange boundOperands) {
1263  // Fully compose map and operands; canonicalize and simplify so that we
1264  // transitively get to terminal symbols or loop IVs.
1265  auto map = boundMap;
1266  SmallVector<Value, 4> operands(boundOperands.begin(), boundOperands.end());
1267  fullyComposeAffineMapAndOperands(&map, &operands);
1268  map = simplifyAffineMap(map);
1269  canonicalizeMapAndOperands(&map, &operands);
1270  for (auto operand : operands)
1272  return addBound(type, pos, computeAlignedMap(map, operands));
1273 }
1274 
1275 // Adds slice lower bounds represented by lower bounds in 'lbMaps' and upper
1276 // bounds in 'ubMaps' to each value in `values' that appears in the constraint
1277 // system. Note that both lower/upper bounds share the same operand list
1278 // 'operands'.
1279 // This function assumes 'values.size' == 'lbMaps.size' == 'ubMaps.size', and
1280 // skips any null AffineMaps in 'lbMaps' or 'ubMaps'.
1281 // Note that both lower/upper bounds use operands from 'operands'.
1282 // Returns failure for unimplemented cases such as semi-affine expressions or
1283 // expressions with mod/floordiv.
1286  ArrayRef<AffineMap> ubMaps, ArrayRef<Value> operands) {
1287  assert(values.size() == lbMaps.size());
1288  assert(lbMaps.size() == ubMaps.size());
1289 
1290  for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
1291  unsigned pos;
1292  if (!findVar(values[i], &pos))
1293  continue;
1294 
1295  AffineMap lbMap = lbMaps[i];
1296  AffineMap ubMap = ubMaps[i];
1297  assert(!lbMap || lbMap.getNumInputs() == operands.size());
1298  assert(!ubMap || ubMap.getNumInputs() == operands.size());
1299 
1300  // Check if this slice is just an equality along this dimension.
1301  if (lbMap && ubMap && lbMap.getNumResults() == 1 &&
1302  ubMap.getNumResults() == 1 &&
1303  lbMap.getResult(0) + 1 == ubMap.getResult(0)) {
1304  if (failed(addBound(BoundType::EQ, pos, lbMap, operands)))
1305  return failure();
1306  continue;
1307  }
1308 
1309  // If lower or upper bound maps are null or provide no results, it implies
1310  // that the source loop was not at all sliced, and the entire loop will be a
1311  // part of the slice.
1312  if (lbMap && lbMap.getNumResults() != 0 && ubMap &&
1313  ubMap.getNumResults() != 0) {
1314  if (failed(addBound(BoundType::LB, pos, lbMap, operands)))
1315  return failure();
1316  if (failed(addBound(BoundType::UB, pos, ubMap, operands)))
1317  return failure();
1318  } else {
1319  auto loop = getForInductionVarOwner(values[i]);
1320  if (failed(this->addAffineForOpDomain(loop)))
1321  return failure();
1322  }
1323  }
1324  return success();
1325 }
1326 
1327 bool FlatAffineValueConstraints::findVar(Value val, unsigned *pos) const {
1328  unsigned i = 0;
1329  for (const auto &mayBeVar : values) {
1330  if (mayBeVar && *mayBeVar == val) {
1331  *pos = i;
1332  return true;
1333  }
1334  i++;
1335  }
1336  return false;
1337 }
1338 
1340  return llvm::any_of(values, [&](const Optional<Value> &mayBeVar) {
1341  return mayBeVar && *mayBeVar == val;
1342  });
1343 }
1344 
1345 void FlatAffineValueConstraints::swapVar(unsigned posA, unsigned posB) {
1346  IntegerPolyhedron::swapVar(posA, posB);
1347 
1348  if (getVarKindAt(posA) == VarKind::Local &&
1349  getVarKindAt(posB) == VarKind::Local)
1350  return;
1351 
1352  // Treat value of a local variable as None.
1353  if (getVarKindAt(posA) == VarKind::Local)
1354  values[posB] = None;
1355  else if (getVarKindAt(posB) == VarKind::Local)
1356  values[posA] = None;
1357  else
1358  std::swap(values[posA], values[posB]);
1359 }
1360 
1362  int64_t value) {
1363  unsigned pos;
1364  if (!findVar(val, &pos))
1365  // This is a pre-condition for this method.
1366  assert(0 && "var not found");
1367  addBound(type, pos, value);
1368 }
1369 
1370 void FlatAffineValueConstraints::printSpace(raw_ostream &os) const {
1372  os << "(";
1373  for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++) {
1374  if (hasValue(i))
1375  os << "Value ";
1376  else
1377  os << "None ";
1378  }
1379  for (unsigned i = getVarKindOffset(VarKind::Local),
1380  e = getVarKindEnd(VarKind::Local);
1381  i < e; ++i)
1382  os << "Local ";
1383  os << " const)\n";
1384 }
1385 
1387  const IntegerRelation &other) {
1388 
1389  if (auto *otherValueSet =
1390  dyn_cast<const FlatAffineValueConstraints>(&other)) {
1391  *this = *otherValueSet;
1392  } else {
1393  *static_cast<IntegerRelation *>(this) = other;
1394  values.clear();
1395  values.resize(getNumDimAndSymbolVars(), None);
1396  }
1397 }
1398 
1400  unsigned pos, bool darkShadow, bool *isResultIntegerExact) {
1401  SmallVector<Optional<Value>, 8> newVals = values;
1402  if (getVarKindAt(pos) != VarKind::Local)
1403  newVals.erase(newVals.begin() + pos);
1404  // Note: Base implementation discards all associated Values.
1405  IntegerPolyhedron::fourierMotzkinEliminate(pos, darkShadow,
1406  isResultIntegerExact);
1407  values = newVals;
1408  assert(values.size() == getNumDimAndSymbolVars());
1409 }
1410 
1412  unsigned pos;
1413  bool ret = findVar(val, &pos);
1414  assert(ret);
1415  (void)ret;
1417 }
1418 
1420  const FlatAffineValueConstraints &otherCst) {
1421  assert(otherCst.getNumDimVars() == getNumDimVars() && "dims mismatch");
1422  assert(otherCst.getMaybeValues()
1423  .slice(0, getNumDimVars())
1424  .equals(getMaybeValues().slice(0, getNumDimVars())) &&
1425  "dim values mismatch");
1426  assert(otherCst.getNumLocalVars() == 0 && "local vars not supported here");
1427  assert(getNumLocalVars() == 0 && "local vars not supported yet here");
1428 
1429  // Align `other` to this.
1430  if (!areVarsAligned(*this, otherCst)) {
1431  FlatAffineValueConstraints otherCopy(otherCst);
1432  mergeAndAlignVars(/*offset=*/getNumDimVars(), this, &otherCopy);
1433  return IntegerPolyhedron::unionBoundingBox(otherCopy);
1434  }
1435 
1436  return IntegerPolyhedron::unionBoundingBox(otherCst);
1437 }
1438 
1439 /// Compute an explicit representation for local vars. For all systems coming
1440 /// from MLIR integer sets, maps, or expressions where local vars were
1441 /// introduced to model floordivs and mods, this always succeeds.
1444  MLIRContext *context) {
1445  unsigned numDims = cst.getNumDimVars();
1446  unsigned numSyms = cst.getNumSymbolVars();
1447 
1448  // Initialize dimensional and symbolic variables.
1449  for (unsigned i = 0; i < numDims; i++)
1450  memo[i] = getAffineDimExpr(i, context);
1451  for (unsigned i = numDims, e = numDims + numSyms; i < e; i++)
1452  memo[i] = getAffineSymbolExpr(i - numDims, context);
1453 
1454  bool changed;
1455  do {
1456  // Each time `changed` is true at the end of this iteration, one or more
1457  // local vars would have been detected as floordivs and set in memo; so the
1458  // number of null entries in memo[...] strictly reduces; so this converges.
1459  changed = false;
1460  for (unsigned i = 0, e = cst.getNumLocalVars(); i < e; ++i)
1461  if (!memo[numDims + numSyms + i] &&
1462  detectAsFloorDiv(cst, /*pos=*/numDims + numSyms + i, context, memo))
1463  changed = true;
1464  } while (changed);
1465 
1466  ArrayRef<AffineExpr> localExprs =
1467  ArrayRef<AffineExpr>(memo).take_back(cst.getNumLocalVars());
1468  return success(
1469  llvm::all_of(localExprs, [](AffineExpr expr) { return expr; }));
1470 }
1471 
1473  unsigned pos, unsigned ineqPos, AffineValueMap &vmap,
1474  MLIRContext *context) const {
1475  unsigned numDims = getNumDimVars();
1476  unsigned numSyms = getNumSymbolVars();
1477 
1478  assert(pos < numDims && "invalid position");
1479  assert(ineqPos < getNumInequalities() && "invalid inequality position");
1480 
1481  // Get expressions for local vars.
1483  if (failed(computeLocalVars(*this, memo, context)))
1484  assert(false &&
1485  "one or more local exprs do not have an explicit representation");
1486  auto localExprs = ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());
1487 
1488  // Compute the AffineExpr lower/upper bound for this inequality.
1489  SmallVector<int64_t, 8> inequality = getInequality64(ineqPos);
1491  bound.reserve(getNumCols() - 1);
1492  // Everything other than the coefficient at `pos`.
1493  bound.append(inequality.begin(), inequality.begin() + pos);
1494  bound.append(inequality.begin() + pos + 1, inequality.end());
1495 
1496  if (inequality[pos] > 0)
1497  // Lower bound.
1498  std::transform(bound.begin(), bound.end(), bound.begin(),
1499  std::negate<int64_t>());
1500  else
1501  // Upper bound (which is exclusive).
1502  bound.back() += 1;
1503 
1504  // Convert to AffineExpr (tree) form.
1505  auto boundExpr = getAffineExprFromFlatForm(bound, numDims - 1, numSyms,
1506  localExprs, context);
1507 
1508  // Get the values to bind to this affine expr (all dims and symbols).
1509  SmallVector<Value, 4> operands;
1510  getValues(0, pos, &operands);
1511  SmallVector<Value, 4> trailingOperands;
1512  getValues(pos + 1, getNumDimAndSymbolVars(), &trailingOperands);
1513  operands.append(trailingOperands.begin(), trailingOperands.end());
1514  vmap.reset(AffineMap::get(numDims - 1, numSyms, boundExpr), operands);
1515 }
1516 
1517 IntegerSet
1519  if (getNumConstraints() == 0)
1520  // Return universal set (always true): 0 == 0.
1522  getAffineConstantExpr(/*constant=*/0, context),
1523  /*eqFlags=*/true);
1524 
1525  // Construct local references.
1527 
1528  if (failed(computeLocalVars(*this, memo, context))) {
1529  // Check if the local variables without an explicit representation have
1530  // zero coefficients everywhere.
1531  SmallVector<unsigned> noLocalRepVars;
1532  unsigned numDimsSymbols = getNumDimAndSymbolVars();
1533  for (unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
1534  if (!memo[i] && !isColZero(/*pos=*/i))
1535  noLocalRepVars.push_back(i - numDimsSymbols);
1536  }
1537  if (!noLocalRepVars.empty()) {
1538  LLVM_DEBUG({
1539  llvm::dbgs() << "local variables at position(s) ";
1540  llvm::interleaveComma(noLocalRepVars, llvm::dbgs());
1541  llvm::dbgs() << " do not have an explicit representation in:\n";
1542  this->dump();
1543  });
1544  return IntegerSet();
1545  }
1546  }
1547 
1548  ArrayRef<AffineExpr> localExprs =
1549  ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());
1550 
1551  // Construct the IntegerSet from the equalities/inequalities.
1552  unsigned numDims = getNumDimVars();
1553  unsigned numSyms = getNumSymbolVars();
1554 
1556  std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(), true);
1557  std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(), false);
1558 
1560  exprs.reserve(getNumConstraints());
1561 
1562  for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
1563  exprs.push_back(getAffineExprFromFlatForm(getEquality64(i), numDims,
1564  numSyms, localExprs, context));
1565  for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
1566  exprs.push_back(getAffineExprFromFlatForm(getInequality64(i), numDims,
1567  numSyms, localExprs, context));
1568  return IntegerSet::get(numDims, numSyms, exprs, eqFlags);
1569 }
1570 
1572  ValueRange dims, ValueRange syms,
1573  SmallVector<Value> *newSyms) {
1574  assert(operands.size() == map.getNumInputs() &&
1575  "expected same number of operands and map inputs");
1576  MLIRContext *ctx = map.getContext();
1577  Builder builder(ctx);
1578  SmallVector<AffineExpr> dimReplacements(map.getNumDims(), {});
1579  unsigned numSymbols = syms.size();
1580  SmallVector<AffineExpr> symReplacements(map.getNumSymbols(), {});
1581  if (newSyms) {
1582  newSyms->clear();
1583  newSyms->append(syms.begin(), syms.end());
1584  }
1585 
1586  for (const auto &operand : llvm::enumerate(operands)) {
1587  // Compute replacement dim/sym of operand.
1588  AffineExpr replacement;
1589  auto dimIt = std::find(dims.begin(), dims.end(), operand.value());
1590  auto symIt = std::find(syms.begin(), syms.end(), operand.value());
1591  if (dimIt != dims.end()) {
1592  replacement =
1593  builder.getAffineDimExpr(std::distance(dims.begin(), dimIt));
1594  } else if (symIt != syms.end()) {
1595  replacement =
1596  builder.getAffineSymbolExpr(std::distance(syms.begin(), symIt));
1597  } else {
1598  // This operand is neither a dimension nor a symbol. Add it as a new
1599  // symbol.
1600  replacement = builder.getAffineSymbolExpr(numSymbols++);
1601  if (newSyms)
1602  newSyms->push_back(operand.value());
1603  }
1604  // Add to corresponding replacements vector.
1605  if (operand.index() < map.getNumDims()) {
1606  dimReplacements[operand.index()] = replacement;
1607  } else {
1608  symReplacements[operand.index() - map.getNumDims()] = replacement;
1609  }
1610  }
1611 
1612  return map.replaceDimsAndSymbols(dimReplacements, symReplacements,
1613  dims.size(), numSymbols);
1614 }
1615 
1617  FlatAffineValueConstraints domain = *this;
1618  // Convert all range variables to local variables.
1619  domain.convertToLocal(VarKind::SetDim, getNumDomainDims(),
1620  getNumDomainDims() + getNumRangeDims());
1621  return domain;
1622 }
1623 
1625  FlatAffineValueConstraints range = *this;
1626  // Convert all domain variables to local variables.
1627  range.convertToLocal(VarKind::SetDim, 0, getNumDomainDims());
1628  return range;
1629 }
1630 
1632  assert(getNumDomainDims() == other.getNumRangeDims() &&
1633  "Domain of this and range of other do not match");
1634  assert(std::equal(values.begin(), values.begin() + getNumDomainDims(),
1635  other.values.begin() + other.getNumDomainDims()) &&
1636  "Domain of this and range of other do not match");
1637 
1638  FlatAffineRelation rel = other;
1639 
1640  // Convert `rel` from
1641  // [otherDomain] -> [otherRange]
1642  // to
1643  // [otherDomain] -> [otherRange thisRange]
1644  // and `this` from
1645  // [thisDomain] -> [thisRange]
1646  // to
1647  // [otherDomain thisDomain] -> [thisRange].
1648  unsigned removeDims = rel.getNumRangeDims();
1649  insertDomainVar(0, rel.getNumDomainDims());
1650  rel.appendRangeVar(getNumRangeDims());
1651 
1652  // Merge symbol and local variables.
1653  mergeSymbolVars(rel);
1654  mergeLocalVars(rel);
1655 
1656  // Convert `rel` from [otherDomain] -> [otherRange thisRange] to
1657  // [otherDomain] -> [thisRange] by converting first otherRange range vars
1658  // to local vars.
1659  rel.convertToLocal(VarKind::SetDim, rel.getNumDomainDims(),
1660  rel.getNumDomainDims() + removeDims);
1661  // Convert `this` from [otherDomain thisDomain] -> [thisRange] to
1662  // [otherDomain] -> [thisRange] by converting last thisDomain domain vars
1663  // to local vars.
1664  convertToLocal(VarKind::SetDim, getNumDomainDims() - removeDims,
1665  getNumDomainDims());
1666 
1667  auto thisMaybeValues = getMaybeValues(VarKind::SetDim);
1668  auto relMaybeValues = rel.getMaybeValues(VarKind::SetDim);
1669 
1670  // Add and match domain of `rel` to domain of `this`.
1671  for (unsigned i = 0, e = rel.getNumDomainDims(); i < e; ++i)
1672  if (relMaybeValues[i].has_value())
1673  setValue(i, relMaybeValues[i].value());
1674  // Add and match range of `this` to range of `rel`.
1675  for (unsigned i = 0, e = getNumRangeDims(); i < e; ++i) {
1676  unsigned rangeIdx = rel.getNumDomainDims() + i;
1677  if (thisMaybeValues[rangeIdx].has_value())
1678  rel.setValue(rangeIdx, thisMaybeValues[rangeIdx].value());
1679  }
1680 
1681  // Append `this` to `rel` and simplify constraints.
1682  rel.append(*this);
1684 
1685  *this = rel;
1686 }
1687 
1689  unsigned oldDomain = getNumDomainDims();
1690  unsigned oldRange = getNumRangeDims();
1691  // Add new range vars.
1692  appendRangeVar(oldDomain);
1693  // Swap new vars with domain.
1694  for (unsigned i = 0; i < oldDomain; ++i)
1695  swapVar(i, oldDomain + oldRange + i);
1696  // Remove the swapped domain.
1697  removeVarRange(0, oldDomain);
1698  // Set domain and range as inverse.
1699  numDomainDims = oldRange;
1700  numRangeDims = oldDomain;
1701 }
1702 
1703 void FlatAffineRelation::insertDomainVar(unsigned pos, unsigned num) {
1704  assert(pos <= getNumDomainDims() &&
1705  "Var cannot be inserted at invalid position");
1706  insertDimVar(pos, num);
1707  numDomainDims += num;
1708 }
1709 
1710 void FlatAffineRelation::insertRangeVar(unsigned pos, unsigned num) {
1711  assert(pos <= getNumRangeDims() &&
1712  "Var cannot be inserted at invalid position");
1713  insertDimVar(getNumDomainDims() + pos, num);
1714  numRangeDims += num;
1715 }
1716 
1718  insertDimVar(getNumDomainDims(), num);
1719  numDomainDims += num;
1720 }
1721 
1723  insertDimVar(getNumDimVars(), num);
1724  numRangeDims += num;
1725 }
1726 
1727 void FlatAffineRelation::removeVarRange(VarKind kind, unsigned varStart,
1728  unsigned varLimit) {
1729  assert(varLimit <= getNumVarKind(kind));
1730  if (varStart >= varLimit)
1731  return;
1732 
1733  FlatAffineValueConstraints::removeVarRange(kind, varStart, varLimit);
1734 
1735  // If kind is not SetDim, domain and range don't need to be updated.
1736  if (kind != VarKind::SetDim)
1737  return;
1738 
1739  // Compute number of domain and range variables to remove. This is done by
1740  // intersecting the range of domain/range vars with range of vars to remove.
1741  unsigned intersectDomainLHS = std::min(varLimit, getNumDomainDims());
1742  unsigned intersectDomainRHS = varStart;
1743  unsigned intersectRangeLHS = std::min(varLimit, getNumDimVars());
1744  unsigned intersectRangeRHS = std::max(varStart, getNumDomainDims());
1745 
1746  if (intersectDomainLHS > intersectDomainRHS)
1747  numDomainDims -= intersectDomainLHS - intersectDomainRHS;
1748  if (intersectRangeLHS > intersectRangeRHS)
1749  numRangeDims -= intersectRangeLHS - intersectRangeRHS;
1750 }
1751 
1753  FlatAffineRelation &rel) {
1754  // Get flattened affine expressions.
1755  std::vector<SmallVector<int64_t, 8>> flatExprs;
1756  FlatAffineValueConstraints localVarCst;
1757  if (failed(getFlattenedAffineExprs(map, &flatExprs, &localVarCst)))
1758  return failure();
1759 
1760  unsigned oldDimNum = localVarCst.getNumDimVars();
1761  unsigned oldCols = localVarCst.getNumCols();
1762  unsigned numRangeVars = map.getNumResults();
1763  unsigned numDomainVars = map.getNumDims();
1764 
1765  // Add range as the new expressions.
1766  localVarCst.appendDimVar(numRangeVars);
1767 
1768  // Add equalities between source and range.
1769  SmallVector<int64_t, 8> eq(localVarCst.getNumCols());
1770  for (unsigned i = 0, e = map.getNumResults(); i < e; ++i) {
1771  // Zero fill.
1772  std::fill(eq.begin(), eq.end(), 0);
1773  // Fill equality.
1774  for (unsigned j = 0, f = oldDimNum; j < f; ++j)
1775  eq[j] = flatExprs[i][j];
1776  for (unsigned j = oldDimNum, f = oldCols; j < f; ++j)
1777  eq[j + numRangeVars] = flatExprs[i][j];
1778  // Set this dimension to -1 to equate lhs and rhs and add equality.
1779  eq[numDomainVars + i] = -1;
1780  localVarCst.addEquality(eq);
1781  }
1782 
1783  // Create relation and return success.
1784  rel = FlatAffineRelation(numDomainVars, numRangeVars, localVarCst);
1785  return success();
1786 }
1787 
1789  FlatAffineRelation &rel) {
1790 
1791  AffineMap affineMap = map.getAffineMap();
1792  if (failed(getRelationFromMap(affineMap, rel)))
1793  return failure();
1794 
1795  // Set symbol values for domain dimensions and symbols.
1796  for (unsigned i = 0, e = rel.getNumDomainDims(); i < e; ++i)
1797  rel.setValue(i, map.getOperand(i));
1798  for (unsigned i = rel.getNumDimVars(), e = rel.getNumDimAndSymbolVars();
1799  i < e; ++i)
1800  rel.setValue(i, map.getOperand(i - rel.getNumRangeDims()));
1801 
1802  return success();
1803 }
1804 
1807  MultiAffineFunction &multiAff) {
1809  std::vector<SmallVector<int64_t, 8>> flattenedExprs;
1810  LogicalResult result = getFlattenedAffineExprs(map, &flattenedExprs, &cst);
1811 
1812  if (result.failed())
1813  return failure();
1814 
1815  DivisionRepr divs = cst.getLocalReprs();
1816  assert(divs.hasAllReprs() &&
1817  "AffineMap cannot produce divs without local representation");
1818 
1819  // TODO: We shouldn't have to do this conversion.
1820  Matrix mat(map.getNumResults(), map.getNumInputs() + divs.getNumDivs() + 1);
1821  for (unsigned i = 0, e = flattenedExprs.size(); i < e; ++i)
1822  for (unsigned j = 0, f = flattenedExprs[i].size(); j < f; ++j)
1823  mat(i, j) = flattenedExprs[i][j];
1824 
1825  multiAff = MultiAffineFunction(
1826  PresburgerSpace::getRelationSpace(map.getNumDims(), map.getNumResults(),
1827  map.getNumSymbols(), divs.getNumDivs()),
1828  mat, divs);
1829 
1830  return success();
1831 }
Include the generated interface declarations.
unsigned getNumDomainDims() const
Returns the number of variables corresponding to domain/range of relation.
static LogicalResult getFlattenedAffineExprs(ArrayRef< AffineExpr > exprs, unsigned numDims, unsigned numSymbols, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatAffineValueConstraints *localVarCst)
unsigned appendSymbolVar(ValueRange vals)
Class storing division representation of local variables of a constraint system.
Definition: Utils.h:117
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt abs(const MPInt &x)
Definition: MPInt.h:370
void reset(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals=0)
Clears any existing data and reserves memory for the specified constraints.
unsigned getNumSymbols() const
Definition: AffineMap.cpp:298
unsigned getNumDims() const
Definition: AffineMap.cpp:294
unsigned insertVar(presburger::VarKind kind, unsigned pos, unsigned num=1) override
Insert num variables of the specified kind at position pos.
AffineExpr getAffineConstantExpr(int64_t constant, MLIRContext *context)
Definition: AffineExpr.cpp:513
LogicalResult getMultiAffineFunctionFromMap(AffineMap map, presburger::MultiAffineFunction &multiAff)
LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, SmallVectorImpl< int64_t > *flattenedExpr, FlatAffineValueConstraints *cst=nullptr)
Flattens &#39;expr&#39; into &#39;flattenedExpr&#39;, which contains the coefficients of the dimensions, symbols, and additional variables that represent floor divisions of dimensions, symbols, and in turn other floor divisions.
std::pair< AffineMap, AffineMap > getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num, unsigned symStartPos, ArrayRef< AffineExpr > localExprs, MLIRContext *context) const
Gets the lower and upper bound of the offset + posth variable treating [0, offset) U [offset + num...
A FlatAffineRelation represents a set of ordered pairs (domain -> range) where "domain" and "range" a...
bool hasValue(unsigned pos) const
Returns true if the pos^th variable has an associated Value.
void convertLoopIVSymbolsToDims()
Changes all symbol variables which are loop IVs to dim variables.
bool hasValues() const
Returns true if at least one variable has an associated Value.
static IntegerSet get(unsigned dimCount, unsigned symbolCount, ArrayRef< AffineExpr > constraints, ArrayRef< bool > eqFlags)
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)
Definition: Builders.cpp:323
bool containsVar(Value mayBeVar) const
Returns true if an variable with the specified Value exists, false otherwise.
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 ...
static bool areVarsAligned(const FlatAffineValueConstraints &a, const FlatAffineValueConstraints &b)
Checks if two constraint systems are in the same space, i.e., if they are associated with the same se...
DivisionRepr getLocalReprs(std::vector< MaybeLocalRepr > *repr=nullptr) const
Returns a DivisonRepr representing the division representation of local variables in the constraint s...
void addAffineIfOpDomain(AffineIfOp ifOp)
Adds constraints imposed by the affine.if operation.
This is a class to represent a resizable matrix.
Definition: Matrix.h:35
static FlatAffineValueConstraints getHyperrectangular(ValueRange ivs, ValueRange lbs, ValueRange ubs)
void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos, AffineValueMap &vmap, MLIRContext *context) const
Returns the bound for the variable at pos from the inequality at ineqPos as a 1-d affine value map (a...
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of vars starts.
unsigned appendDimVar(ValueRange vals)
Append variables of the specified kind after the last variable of that kind.
LogicalResult flattenAlignedMapAndMergeLocals(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs)
Given an affine map that is aligned with this constraint system:
void mergeSymbolVars(FlatAffineValueConstraints &other)
Merge and align symbols of this and other such that both get union of of symbols that are unique...
unsigned getPosition() const
Definition: AffineExpr.cpp:311
bool hasAllReprs() const
Definition: Utils.h:133
LogicalResult getRelationFromMap(AffineMap &map, FlatAffineRelation &rel)
Builds a relation from the given AffineMap/AffineValueMap map, containing all pairs of the form opera...
void insertRangeVar(unsigned pos, unsigned num=1)
An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affin...
An integer constant appearing in affine expression.
Definition: AffineExpr.h:232
BoundType
The type of bound: equal, lower bound or upper bound.
void mergeAndAlignVarsWithOther(unsigned offset, FlatAffineValueConstraints *other)
Merge and align the variables of this and other starting at offset, so that both constraint systems g...
static constexpr const bool value
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:890
bool failed() const
Returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:44
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
void addLocalFloorDiv(ArrayRef< MPInt > dividend, const MPInt &divisor)
Adds a new local variable as the floordiv of an affine function of other variables, the coefficients of which are provided in dividend and with respect to a positive constant divisor.
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
void removeRedundantLocalVars()
Removes local variables using equalities.
int64_t atEq64(unsigned i, unsigned j) const
The same, but casts to int64_t.
AffineExpr getResult(unsigned idx) const
Definition: AffineMap.cpp:311
static void printSpace(std::ostream &os, int count)
Definition: RunnerUtils.h:88
unsigned getNumInputs() const
Definition: AffineMap.cpp:303
unsigned insertDimVar(unsigned pos, unsigned num=1)
Insert variables of the specified kind at position pos.
unsigned getVarKindEnd(VarKind kind) const
Return the index at Which the specified kind of vars ends.
LogicalResult addSliceBounds(ArrayRef< Value > values, ArrayRef< AffineMap > lbMaps, ArrayRef< AffineMap > ubMaps, ArrayRef< Value > operands)
Adds slice lower bounds represented by lower bounds in lbMaps and upper bounds in ubMaps to each vari...
U dyn_cast() const
Definition: AffineExpr.h:281
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...
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
ArrayRef< Optional< Value > > getMaybeValues() const
void fourierMotzkinEliminate(unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr) override
Eliminates the variable at the specified position using Fourier-Motzkin variable elimination, but uses Gaussian elimination if there is an equality involving that variable.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
void swapVar(unsigned posA, unsigned posB) override
Swap the posA^th variable with the posB^th variable.
AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const
Align map with this constraint system based on operands.
int64_t floorDiv(int64_t lhs, int64_t rhs)
Returns the result of MLIR&#39;s floordiv operation on constants.
Definition: MathExtras.h:33
bool isColZero(unsigned pos) const
Returns true if the pos^th column is all zero for both inequalities and equalities.
SmallVector< int64_t, 8 > getEquality64(unsigned idx) const
The same, but casts to int64_t.
Optional< int64_t > getConstantBound64(BoundType type, unsigned pos) const
The same, but casts to int64_t.
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
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:222
void addInductionVarOrTerminalSymbol(Value val)
Add the specified values as a dim or symbol var depending on its nature, if it already doesn&#39;t exist ...
static bool detectAsFloorDiv(const FlatAffineValueConstraints &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 ...
void removeVarRange(VarKind kind, unsigned varStart, unsigned varLimit) override
Removes variables in the column range [varStart, varLimit), and copies any remaining valid data into ...
AffineExpr getAffineSymbolExpr(unsigned position, MLIRContext *context)
Definition: AffineExpr.cpp:498
void fullyComposeAffineMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Given an affine map map and its input operands, this method composes into map, maps of AffineApplyOps...
Definition: AffineOps.cpp:701
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:392
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:232
LogicalResult addDomainFromSliceMaps(ArrayRef< AffineMap > lbMaps, ArrayRef< AffineMap > ubMaps, ArrayRef< Value > operands)
Adds constraints (lower and upper bounds) for each loop in the loop nest described by the bound maps ...
Base type for affine expression.
Definition: AffineExpr.h:68
void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Modifies both map and operands in-place so as to:
Definition: AffineOps.cpp:1066
void appendRangeVar(unsigned num=1)
bool hasConsistentState() const override
Returns false if the fields corresponding to various variable counts, or equality/inequality buffer s...
virtual void addLocalFloorDivId(ArrayRef< int64_t > dividend, int64_t divisor, AffineExpr localExpr)
unsigned getNumResults() const
Definition: AffineMap.cpp:302
VarKind
Kind of variable.
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
SmallVector< int64_t, 8 > getInequality64(unsigned idx) const
FlatAffineValueConstraints getRangeSet() const
bool findConstraintWithNonZeroAt(unsigned colIdx, bool isEq, unsigned *rowIdx) const
Searches for a constraint with a non-zero coefficient at colIdx in equality (isEq=true) or inequality...
A multi-dimensional affine map Affine map&#39;s are immutable like Type&#39;s, and they are uniqued...
Definition: AffineMap.h:42
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatAffineConstraints.
bool isForInductionVar(Value val)
Returns true if the provided value is the induction variable of a AffineForOp.
Definition: AffineOps.cpp:2138
unsigned getNumDivs() const
Definition: Utils.h:125
AffineMap getAffineMap() const
static void turnSymbolIntoDim(FlatAffineValueConstraints *cst, Value value)
ArrayRef< AffineExpr > getResults() const
Definition: AffineMap.cpp:307
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.
SmallVector< Optional< Value >, 8 > values
Values corresponding to the (column) non-local variables of this constraint system appearing in the o...
AffineExpr getAffineDimExpr(unsigned position, MLIRContext *context)
These free functions allow clients of the API to not use classes in detail.
Definition: AffineExpr.cpp:488
bool findVar(Value val, unsigned *pos) const
Looks up the position of the variable with the specified Value.
bool isa() const
Definition: AffineExpr.h:270
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
void projectOut(Value val)
Projects out the variable that is associate with Value.
LogicalResult unionBoundingBox(const FlatAffineValueConstraints &other)
Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this ...
LogicalResult composeMap(const AffineValueMap *vMap)
Composes the affine value map with this FlatAffineValueConstrains, adding the results of the map as d...
AffineForOp getForInductionVarOwner(Value val)
Returns the loop parent of an induction variable.
Definition: AffineOps.cpp:2144
static void mergeAndAlignVars(unsigned offset, FlatAffineValueConstraints *a, FlatAffineValueConstraints *b)
Merge and align the variables of A and B starting at &#39;offset&#39;, so that both constraint systems get th...
unsigned insertLocalVar(unsigned pos, unsigned num=1)
void appendDomainVar(unsigned num=1)
Append num variables of the specified kind after the last variable of that kind.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
static bool detectAsMod(const FlatAffineValueConstraints &cst, unsigned pos, int64_t lbConst, int64_t ubConst, SmallVectorImpl< AffineExpr > &memo, MLIRContext *context)
void append(const IntegerRelation &other)
Appends constraints from other into this.
bool isTopLevelValue(Value value)
TODO: These should be renamed if they are on the mlir namespace.
Definition: AffineOps.cpp:231
void normalizeConstraintsByGCD()
Normalized each constraints by the GCD of its coefficients.
This class is a general helper class for creating context-global objects like types, attributes, and affine expressions.
Definition: Builders.h:49
AffineMap simplifyAffineMap(AffineMap map)
Simplifies an affine map by simplifying its underlying AffineExpr results.
Definition: AffineMap.cpp:634
FlatAffineValueConstraints represents an extension of IntegerPolyhedron where each non-local variable...
void setDimSymbolSeparation(unsigned newSymbolCount)
Changes the partition between dimensions and symbols.
void getLowerAndUpperBoundIndices(unsigned pos, SmallVectorImpl< unsigned > *lbIndices, SmallVectorImpl< unsigned > *ubIndices, SmallVectorImpl< unsigned > *eqIndices=nullptr, unsigned offset=0, unsigned num=0) const
Gather positions of all lower and upper bounds of the variable at pos, and optionally any equalities ...
A dimensional identifier appearing in an affine expression.
Definition: AffineExpr.h:216
Specialization of arith.constant op that returns an integer of index type.
Definition: Arithmetic.h:80
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
unsigned getNumCols() const
Returns the number of columns in the constraint system.
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:56
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified &#39;affine.for&#39; operation&#39;s Value using IR i...
void insertDomainVar(unsigned pos, unsigned num=1)
Insert num variables of the specified kind after the pos variable of that kind.
unsigned getNumVarKind(VarKind kind) const
Get the number of vars of the specified kind.
AffineExpr getAffineDimExpr(unsigned position)
Definition: Builders.cpp:319
static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique(const FlatAffineValueConstraints &cst, unsigned start, unsigned end)
Checks if the SSA values associated with cst&#39;s variables in range [start, end) are unique...
void inverse()
Swap domain and range of the relation.
void convertToLocal(VarKind kind, unsigned varStart, unsigned varLimit)
void setValue(unsigned pos, Value val)
Sets the Value associated with the pos^th variable.
FlatAffineValueConstraints getDomainSet() const
Returns a set corresponding to the domain/range of the affine relation.
unsigned getNumRangeDims() const
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th variable.
void dump() const
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes...
void addInequality(ArrayRef< MPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
static LogicalResult computeLocalVars(const FlatAffineValueConstraints &cst, SmallVectorImpl< AffineExpr > &memo, MLIRContext *context)
Compute an explicit representation for local vars.
MLIRContext * getContext() const
Definition: AffineMap.cpp:253
PresburgerSpace is the space of all possible values of a tuple of integer valued variables/variables...
LogicalResult composeMatchingMap(AffineMap other)
Composes an affine map whose dimensions and symbols match one to one with the dimensions and symbols ...
void clearAndCopyFrom(const IntegerRelation &other) override
Replaces the contents of this FlatAffineValueConstraints with other.
std::unique_ptr< FlatAffineValueConstraints > clone() const
Clones this object.
LogicalResult getFlattenedAffineExprs(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatAffineValueConstraints *cst=nullptr)
Flattens the result expressions of the map to their corresponding flattened forms and set in &#39;flatten...
VarKind getVarKindAt(unsigned pos) const
Return the VarKind of the var at the specified position.
void addEquality(ArrayRef< MPInt > eq)
Adds an equality from the coefficients specified in eq.
bool areVarsAlignedWithOther(const FlatAffineValueConstraints &other)
Returns true if this constraint system and other are in the same space, i.e., if they are associated ...
void getValues(unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
Returns the Values associated with variables in range [start, end).
ArrayRef< Value > getOperands() const
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain...
Definition: PWMAFunction.h:36
void compose(const FlatAffineRelation &other)
Given affine relation other: (domainOther -> rangeOther), this operation takes the composition of oth...
void reset(AffineMap map, ValueRange operands, ValueRange results={})
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:345
FlatAffineValueConstraints(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< Optional< Value >> valArgs={})
Constructs a constraint system reserving memory for the specified number of constraints and variables...
unsigned appendLocalVar(unsigned num=1)
unsigned insertSymbolVar(unsigned pos, unsigned num=1)
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool getClosedUB=false)
Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an...
static PresburgerSpace getSetSpace(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
Value getOperand(unsigned i) const
LogicalResult addBound(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 removeVarRange(presburger::VarKind kind, unsigned varStart, unsigned varLimit) override
Removes variables in the column range [varStart, varLimit), and copies any remaining valid data into ...
An integer set representing a conjunction of one or more affine equalities and inequalities.
Definition: IntegerSet.h:44