MLIR  21.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 
19 #include "mlir/IR/IntegerSet.h"
20 #include "mlir/Support/LLVM.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 "affine-structures"
27 
28 using namespace mlir;
29 using namespace affine;
30 using namespace presburger;
31 
32 LogicalResult
34  if (containsVar(val))
35  return success();
36 
37  // Caller is expected to fully compose map/operands if necessary.
38  if (val.getDefiningOp<affine::AffineApplyOp>() ||
39  (!isValidSymbol(val) && !isAffineInductionVar(val))) {
40  LLVM_DEBUG(llvm::dbgs()
41  << "only valid terminal symbols and affine IVs supported\n");
42  return failure();
43  }
44  // Outer loop IVs could be used in forOp's bounds.
45  if (auto loop = getForInductionVarOwner(val)) {
46  appendDimVar(val);
47  if (failed(this->addAffineForOpDomain(loop))) {
48  LLVM_DEBUG(
49  loop.emitWarning("failed to add domain info to constraint system"));
50  return failure();
51  }
52  return success();
53  }
54 
55  if (auto parallel = getAffineParallelInductionVarOwner(val)) {
56  appendDimVar(parallel.getIVs());
57  if (failed(this->addAffineParallelOpDomain(parallel))) {
58  LLVM_DEBUG(parallel.emitWarning(
59  "failed to add domain info to constraint system"));
60  return failure();
61  }
62  return success();
63  }
64 
65  // Add top level symbol.
66  appendSymbolVar(val);
67  // Check if the symbol is a constant.
68  if (std::optional<int64_t> constOp = getConstantIntValue(val))
69  addBound(BoundType::EQ, val, constOp.value());
70  return success();
71 }
72 
73 LogicalResult
75  unsigned pos;
76  // Pre-condition for this method.
77  if (!findVar(forOp.getInductionVar(), &pos)) {
78  assert(false && "Value not found");
79  return failure();
80  }
81 
82  int64_t step = forOp.getStepAsInt();
83  if (step != 1) {
84  if (!forOp.hasConstantLowerBound())
85  LLVM_DEBUG(forOp.emitWarning("domain conservatively approximated"));
86  else {
87  // Add constraints for the stride.
88  // (iv - lb) % step = 0 can be written as:
89  // (iv - lb) - step * q = 0 where q = (iv - lb) / step.
90  // Add local variable 'q' and add the above equality.
91  // The first constraint is q = (iv - lb) floordiv step
92  SmallVector<int64_t, 8> dividend(getNumCols(), 0);
93  int64_t lb = forOp.getConstantLowerBound();
94  dividend[pos] = 1;
95  dividend.back() -= lb;
96  addLocalFloorDiv(dividend, step);
97  // Second constraint: (iv - lb) - step * q = 0.
98  SmallVector<int64_t, 8> eq(getNumCols(), 0);
99  eq[pos] = 1;
100  eq.back() -= lb;
101  // For the local var just added above.
102  eq[getNumCols() - 2] = -step;
103  addEquality(eq);
104  }
105  }
106 
107  if (forOp.hasConstantLowerBound()) {
108  addBound(BoundType::LB, pos, forOp.getConstantLowerBound());
109  } else {
110  // Non-constant lower bound case.
111  if (failed(addBound(BoundType::LB, pos, forOp.getLowerBoundMap(),
112  forOp.getLowerBoundOperands())))
113  return failure();
114  }
115 
116  if (forOp.hasConstantUpperBound()) {
117  addBound(BoundType::UB, pos, forOp.getConstantUpperBound() - 1);
118  return success();
119  }
120  // Non-constant upper bound case.
121  return addBound(BoundType::UB, pos, forOp.getUpperBoundMap(),
122  forOp.getUpperBoundOperands());
123 }
124 
126  AffineParallelOp parallelOp) {
127  size_t ivPos = 0;
128  for (Value iv : parallelOp.getIVs()) {
129  unsigned pos;
130  if (!findVar(iv, &pos)) {
131  assert(false && "variable expected for the IV value");
132  return failure();
133  }
134 
135  AffineMap lowerBound = parallelOp.getLowerBoundMap(ivPos);
136  if (lowerBound.isConstant())
137  addBound(BoundType::LB, pos, lowerBound.getSingleConstantResult());
138  else if (failed(addBound(BoundType::LB, pos, lowerBound,
139  parallelOp.getLowerBoundsOperands())))
140  return failure();
141 
142  auto upperBound = parallelOp.getUpperBoundMap(ivPos);
143  if (upperBound.isConstant())
144  addBound(BoundType::UB, pos, upperBound.getSingleConstantResult() - 1);
145  else if (failed(addBound(BoundType::UB, pos, upperBound,
146  parallelOp.getUpperBoundsOperands())))
147  return failure();
148  ++ivPos;
149  }
150  return success();
151 }
152 
153 LogicalResult
155  ArrayRef<AffineMap> ubMaps,
156  ArrayRef<Value> operands) {
157  assert(lbMaps.size() == ubMaps.size());
158  assert(lbMaps.size() <= getNumDimVars());
159 
160  for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
161  AffineMap lbMap = lbMaps[i];
162  AffineMap ubMap = ubMaps[i];
163  assert(!lbMap || lbMap.getNumInputs() == operands.size());
164  assert(!ubMap || ubMap.getNumInputs() == operands.size());
165 
166  // Check if this slice is just an equality along this dimension. If so,
167  // retrieve the existing loop it equates to and add it to the system.
168  if (lbMap && ubMap && lbMap.getNumResults() == 1 &&
169  ubMap.getNumResults() == 1 &&
170  lbMap.getResult(0) + 1 == ubMap.getResult(0) &&
171  // The condition above will be true for maps describing a single
172  // iteration (e.g., lbMap.getResult(0) = 0, ubMap.getResult(0) = 1).
173  // Make sure we skip those cases by checking that the lb result is not
174  // just a constant.
175  !isa<AffineConstantExpr>(lbMap.getResult(0))) {
176  // Limited support: we expect the lb result to be just a loop dimension.
177  // Not supported otherwise for now.
178  AffineDimExpr result = dyn_cast<AffineDimExpr>(lbMap.getResult(0));
179  if (!result)
180  return failure();
181 
182  AffineForOp loop =
183  getForInductionVarOwner(operands[result.getPosition()]);
184  if (!loop)
185  return failure();
186 
187  if (failed(addAffineForOpDomain(loop)))
188  return failure();
189  continue;
190  }
191 
192  // This slice refers to a loop that doesn't exist in the IR yet. Add its
193  // bounds to the system assuming its dimension variable position is the
194  // same as the position of the loop in the loop nest.
195  if (lbMap && failed(addBound(BoundType::LB, i, lbMap, operands)))
196  return failure();
197  if (ubMap && failed(addBound(BoundType::UB, i, ubMap, operands)))
198  return failure();
199  }
200  return success();
201 }
202 
204  IntegerSet set = ifOp.getIntegerSet();
205  // Canonicalize set and operands to ensure unique values for
206  // FlatAffineValueConstraints below and for early simplification.
207  SmallVector<Value> operands(ifOp.getOperands());
208  canonicalizeSetAndOperands(&set, &operands);
209 
210  // Create the base constraints from the integer set attached to ifOp.
211  FlatAffineValueConstraints cst(set, operands);
212 
213  // Merge the constraints from ifOp to the current domain. We need first merge
214  // and align the IDs from both constraints, and then append the constraints
215  // from the ifOp into the current one.
216  mergeAndAlignVarsWithOther(0, &cst);
217  append(cst);
218 }
219 
220 LogicalResult FlatAffineValueConstraints::addBound(BoundType type, unsigned pos,
221  AffineMap boundMap,
222  ValueRange boundOperands) {
223  // Fully compose map and operands; canonicalize and simplify so that we
224  // transitively get to terminal symbols or loop IVs.
225  auto map = boundMap;
226  SmallVector<Value, 4> operands(boundOperands.begin(), boundOperands.end());
227  fullyComposeAffineMapAndOperands(&map, &operands);
228  map = simplifyAffineMap(map);
229  canonicalizeMapAndOperands(&map, &operands);
230  for (Value operand : operands) {
231  if (failed(addInductionVarOrTerminalSymbol(operand)))
232  return failure();
233  }
234  return addBound(type, pos, computeAlignedMap(map, operands));
235 }
236 
237 // Adds slice lower bounds represented by lower bounds in 'lbMaps' and upper
238 // bounds in 'ubMaps' to each value in `values' that appears in the constraint
239 // system. Note that both lower/upper bounds share the same operand list
240 // 'operands'.
241 // This function assumes 'values.size' == 'lbMaps.size' == 'ubMaps.size', and
242 // skips any null AffineMaps in 'lbMaps' or 'ubMaps'.
243 // Note that both lower/upper bounds use operands from 'operands'.
244 // Returns failure for unimplemented cases such as semi-affine expressions or
245 // expressions with mod/floordiv.
247  ArrayRef<Value> values, ArrayRef<AffineMap> lbMaps,
248  ArrayRef<AffineMap> ubMaps, ArrayRef<Value> operands) {
249  assert(values.size() == lbMaps.size());
250  assert(lbMaps.size() == ubMaps.size());
251 
252  for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
253  unsigned pos;
254  if (!findVar(values[i], &pos))
255  continue;
256 
257  AffineMap lbMap = lbMaps[i];
258  AffineMap ubMap = ubMaps[i];
259  assert(!lbMap || lbMap.getNumInputs() == operands.size());
260  assert(!ubMap || ubMap.getNumInputs() == operands.size());
261 
262  // Check if this slice is just an equality along this dimension.
263  if (lbMap && ubMap && lbMap.getNumResults() == 1 &&
264  ubMap.getNumResults() == 1 &&
265  lbMap.getResult(0) + 1 == ubMap.getResult(0)) {
266  if (failed(addBound(BoundType::EQ, pos, lbMap, operands)))
267  return failure();
268  continue;
269  }
270 
271  // If lower or upper bound maps are null or provide no results, it implies
272  // that the source loop was not at all sliced, and the entire loop will be a
273  // part of the slice.
274  if (lbMap && lbMap.getNumResults() != 0 && ubMap &&
275  ubMap.getNumResults() != 0) {
276  if (failed(addBound(BoundType::LB, pos, lbMap, operands)))
277  return failure();
278  if (failed(addBound(BoundType::UB, pos, ubMap, operands)))
279  return failure();
280  } else {
281  auto loop = getForInductionVarOwner(values[i]);
282  if (failed(this->addAffineForOpDomain(loop)))
283  return failure();
284  }
285  }
286  return success();
287 }
288 
289 LogicalResult
291  return composeMatchingMap(
292  computeAlignedMap(vMap->getAffineMap(), vMap->getOperands()));
293 }
294 
295 // Turn a symbol into a dimension.
297  unsigned pos;
298  if (cst->findVar(value, &pos) && pos >= cst->getNumDimVars() &&
299  pos < cst->getNumDimAndSymbolVars()) {
300  cst->swapVar(pos, cst->getNumDimVars());
301  cst->setDimSymbolSeparation(cst->getNumSymbolVars() - 1);
302  }
303 }
304 
305 // Changes all symbol variables which are loop IVs to dim variables.
307  // Gather all symbols which are loop IVs.
308  SmallVector<Value, 4> loopIVs;
309  for (unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++) {
310  if (hasValue(i) && getForInductionVarOwner(getValue(i)))
311  loopIVs.push_back(getValue(i));
312  }
313  // Turn each symbol in 'loopIVs' into a dim variable.
314  for (auto iv : loopIVs) {
315  turnSymbolIntoDim(this, iv);
316  }
317 }
318 
320  unsigned pos, unsigned ineqPos, AffineValueMap &vmap,
321  MLIRContext *context) const {
322  unsigned numDims = getNumDimVars();
323  unsigned numSyms = getNumSymbolVars();
324 
325  assert(pos < numDims && "invalid position");
326  assert(ineqPos < getNumInequalities() && "invalid inequality position");
327 
328  // Get expressions for local vars.
329  SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());
330  if (failed(computeLocalVars(memo, context)))
331  assert(false &&
332  "one or more local exprs do not have an explicit representation");
333  auto localExprs = ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());
334 
335  // Compute the AffineExpr lower/upper bound for this inequality.
336  SmallVector<int64_t, 8> inequality = getInequality64(ineqPos);
338  bound.reserve(getNumCols() - 1);
339  // Everything other than the coefficient at `pos`.
340  bound.append(inequality.begin(), inequality.begin() + pos);
341  bound.append(inequality.begin() + pos + 1, inequality.end());
342 
343  if (inequality[pos] > 0)
344  // Lower bound.
345  std::transform(bound.begin(), bound.end(), bound.begin(),
346  std::negate<int64_t>());
347  else
348  // Upper bound (which is exclusive).
349  bound.back() += 1;
350 
351  // Convert to AffineExpr (tree) form.
352  auto boundExpr = getAffineExprFromFlatForm(bound, numDims - 1, numSyms,
353  localExprs, context);
354 
355  // Get the values to bind to this affine expr (all dims and symbols).
356  SmallVector<Value, 4> operands;
357  getValues(0, pos, &operands);
358  SmallVector<Value, 4> trailingOperands;
359  getValues(pos + 1, getNumDimAndSymbolVars(), &trailingOperands);
360  operands.append(trailingOperands.begin(), trailingOperands.end());
361  vmap.reset(AffineMap::get(numDims - 1, numSyms, boundExpr), operands);
362 }
363 
365  FlatAffineValueConstraints domain = *this;
366  // Convert all range variables to local variables.
367  domain.convertToLocal(VarKind::SetDim, getNumDomainDims(),
368  getNumDomainDims() + getNumRangeDims());
369  return domain;
370 }
371 
373  FlatAffineValueConstraints range = *this;
374  // Convert all domain variables to local variables.
375  range.convertToLocal(VarKind::SetDim, 0, getNumDomainDims());
376  return range;
377 }
378 
380  assert(getNumDomainDims() == other.getNumRangeDims() &&
381  "Domain of this and range of other do not match");
382  assert(space.getDomainSpace().isAligned(other.getSpace().getRangeSpace()) &&
383  "Values of domain of this and range of other do not match");
384 
385  FlatAffineRelation rel = other;
386 
387  // Convert `rel` from
388  // [otherDomain] -> [otherRange]
389  // to
390  // [otherDomain] -> [otherRange thisRange]
391  // and `this` from
392  // [thisDomain] -> [thisRange]
393  // to
394  // [otherDomain thisDomain] -> [thisRange].
395  unsigned removeDims = rel.getNumRangeDims();
396  insertDomainVar(0, rel.getNumDomainDims());
397  rel.appendRangeVar(getNumRangeDims());
398 
399  // Merge symbol and local variables.
400  mergeSymbolVars(rel);
401  mergeLocalVars(rel);
402 
403  // Convert `rel` from [otherDomain] -> [otherRange thisRange] to
404  // [otherDomain] -> [thisRange] by converting first otherRange range vars
405  // to local vars.
406  rel.convertToLocal(VarKind::SetDim, rel.getNumDomainDims(),
407  rel.getNumDomainDims() + removeDims);
408  // Convert `this` from [otherDomain thisDomain] -> [thisRange] to
409  // [otherDomain] -> [thisRange] by converting last thisDomain domain vars
410  // to local vars.
411  convertToLocal(VarKind::SetDim, getNumDomainDims() - removeDims,
412  getNumDomainDims());
413 
414  auto thisMaybeValues = getMaybeValues(VarKind::SetDim);
415  auto relMaybeValues = rel.getMaybeValues(VarKind::SetDim);
416 
417  // Add and match domain of `rel` to domain of `this`.
418  for (unsigned i = 0, e = rel.getNumDomainDims(); i < e; ++i)
419  if (relMaybeValues[i].has_value())
420  setValue(i, *relMaybeValues[i]);
421  // Add and match range of `this` to range of `rel`.
422  for (unsigned i = 0, e = getNumRangeDims(); i < e; ++i) {
423  unsigned rangeIdx = rel.getNumDomainDims() + i;
424  if (thisMaybeValues[rangeIdx].has_value())
425  rel.setValue(rangeIdx, *thisMaybeValues[rangeIdx]);
426  }
427 
428  // Append `this` to `rel` and simplify constraints.
429  rel.append(*this);
431 
432  *this = rel;
433 }
434 
436  unsigned oldDomain = getNumDomainDims();
437  unsigned oldRange = getNumRangeDims();
438  // Add new range vars.
439  appendRangeVar(oldDomain);
440  // Swap new vars with domain.
441  for (unsigned i = 0; i < oldDomain; ++i)
442  swapVar(i, oldDomain + oldRange + i);
443  // Remove the swapped domain.
444  removeVarRange(0, oldDomain);
445  // Set domain and range as inverse.
446  numDomainDims = oldRange;
447  numRangeDims = oldDomain;
448 }
449 
450 void FlatAffineRelation::insertDomainVar(unsigned pos, unsigned num) {
451  assert(pos <= getNumDomainDims() &&
452  "Var cannot be inserted at invalid position");
453  insertDimVar(pos, num);
454  numDomainDims += num;
455 }
456 
457 void FlatAffineRelation::insertRangeVar(unsigned pos, unsigned num) {
458  assert(pos <= getNumRangeDims() &&
459  "Var cannot be inserted at invalid position");
460  insertDimVar(getNumDomainDims() + pos, num);
461  numRangeDims += num;
462 }
463 
465  insertDimVar(getNumDomainDims(), num);
466  numDomainDims += num;
467 }
468 
470  insertDimVar(getNumDimVars(), num);
471  numRangeDims += num;
472 }
473 
475  unsigned varLimit) {
476  assert(varLimit <= getNumVarKind(kind));
477  if (varStart >= varLimit)
478  return;
479 
481 
482  // If kind is not SetDim, domain and range don't need to be updated.
483  if (kind != VarKind::SetDim)
484  return;
485 
486  // Compute number of domain and range variables to remove. This is done by
487  // intersecting the range of domain/range vars with range of vars to remove.
488  unsigned intersectDomainLHS = std::min(varLimit, getNumDomainDims());
489  unsigned intersectDomainRHS = varStart;
490  unsigned intersectRangeLHS = std::min(varLimit, getNumDimVars());
491  unsigned intersectRangeRHS = std::max(varStart, getNumDomainDims());
492 
493  if (intersectDomainLHS > intersectDomainRHS)
494  numDomainDims -= intersectDomainLHS - intersectDomainRHS;
495  if (intersectRangeLHS > intersectRangeRHS)
496  numRangeDims -= intersectRangeLHS - intersectRangeRHS;
497 }
498 
500  IntegerRelation &rel) {
501  // Get flattened affine expressions.
502  std::vector<SmallVector<int64_t, 8>> flatExprs;
503  FlatAffineValueConstraints localVarCst;
504  if (failed(getFlattenedAffineExprs(map, &flatExprs, &localVarCst)))
505  return failure();
506 
507  const unsigned oldDimNum = localVarCst.getNumDimVars();
508  const unsigned oldCols = localVarCst.getNumCols();
509  const unsigned numRangeVars = map.getNumResults();
510  const unsigned numDomainVars = map.getNumDims();
511 
512  // Add range as the new expressions.
513  localVarCst.appendDimVar(numRangeVars);
514 
515  // Add identifiers to the local constraints as getFlattenedAffineExprs creates
516  // a FlatLinearConstraints with no identifiers.
517  for (unsigned i = 0, e = localVarCst.getNumDimAndSymbolVars(); i < e; ++i)
518  localVarCst.setValue(i, Value());
519 
520  // Add equalities between source and range.
521  SmallVector<int64_t, 8> eq(localVarCst.getNumCols());
522  for (unsigned i = 0, e = map.getNumResults(); i < e; ++i) {
523  // Zero fill.
524  llvm::fill(eq, 0);
525  // Fill equality.
526  for (unsigned j = 0, f = oldDimNum; j < f; ++j)
527  eq[j] = flatExprs[i][j];
528  for (unsigned j = oldDimNum, f = oldCols; j < f; ++j)
529  eq[j + numRangeVars] = flatExprs[i][j];
530  // Set this dimension to -1 to equate lhs and rhs and add equality.
531  eq[numDomainVars + i] = -1;
532  localVarCst.addEquality(eq);
533  }
534 
535  rel = localVarCst;
536  return success();
537 }
538 
540  IntegerRelation &rel) {
541 
542  AffineMap affineMap = map.getAffineMap();
543  if (failed(getRelationFromMap(affineMap, rel)))
544  return failure();
545 
546  // Set identifiers for domain and symbol variables.
547  for (unsigned i = 0, e = affineMap.getNumDims(); i < e; ++i)
548  rel.setId(VarKind::SetDim, i, Identifier(map.getOperand(i)));
549 
550  const unsigned mapNumResults = affineMap.getNumResults();
551  for (unsigned i = 0, e = rel.getNumSymbolVars(); i < e; ++i)
552  rel.setId(
553  VarKind::Symbol, i,
554  Identifier(map.getOperand(rel.getNumDimVars() + i - mapNumResults)));
555 
556  return success();
557 }
static void turnSymbolIntoDim(FlatAffineValueConstraints *cst, Value value)
union mlir::linalg::@1221::ArityGroupAndKind::Kind kind
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
A dimensional identifier appearing in an affine expression.
Definition: AffineExpr.h:223
unsigned getPosition() const
Definition: AffineExpr.cpp:348
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:46
int64_t getSingleConstantResult() const
Returns the constant result of this map.
Definition: AffineMap.cpp:377
bool isConstant() const
Returns true if this affine map has only constant results.
Definition: AffineMap.cpp:373
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
unsigned getNumDims() const
Definition: AffineMap.cpp:390
unsigned getNumResults() const
Definition: AffineMap.cpp:398
unsigned getNumInputs() const
Definition: AffineMap.cpp:399
AffineExpr getResult(unsigned idx) const
Definition: AffineMap.cpp:407
SmallVector< std::optional< Value > > getMaybeValues() const
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, unsigned offset=0) const
Looks up the position of the variable with the specified Value starting with variables at offset offs...
void setValue(unsigned pos, Value val)
Sets the Value associated with the pos^th variable.
An integer set representing a conjunction of one or more affine equalities and inequalities.
Definition: IntegerSet.h:44
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:60
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:387
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes.
Value getOperand(unsigned i) const
ArrayRef< Value > getOperands() const
void reset(AffineMap map, ValueRange operands, ValueRange results={})
A FlatAffineRelation represents a set of ordered pairs (domain -> range) where "domain" and "range" a...
void appendDomainVar(unsigned num=1)
Append num variables of the specified kind after the last variable of that kind.
void compose(const FlatAffineRelation &other)
Given affine relation other: (domainOther -> rangeOther), this operation takes the composition of oth...
unsigned getNumDomainDims() const
Returns the number of variables corresponding to domain/range of relation.
void inverse()
Swap domain and range of the relation.
FlatAffineValueConstraints getDomainSet() const
Returns a set corresponding to the domain/range of the affine relation.
void removeVarRange(VarKind kind, unsigned varStart, unsigned varLimit) override
Removes variables in the column range [varStart, varLimit), and copies any remaining valid data into ...
FlatAffineValueConstraints getRangeSet() const
void insertRangeVar(unsigned pos, unsigned num=1)
void insertDomainVar(unsigned pos, unsigned num=1)
Insert num variables of the specified kind after the pos variable of that kind.
FlatAffineValueConstraints is an extension of FlatLinearValueConstraints with helper functions for Af...
void addAffineIfOpDomain(AffineIfOp ifOp)
Adds constraints imposed by the affine.if operation.
void convertLoopIVSymbolsToDims()
Changes all symbol variables which are loop IVs to dim variables.
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 ...
LogicalResult addAffineParallelOpDomain(AffineParallelOp parallelOp)
Add constraints (lower and upper bounds) for the specified 'affine.parallel' operation's Value using ...
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR i...
void addBound(presburger::BoundType type, Value val, int64_t value)
Adds a constant bound for the variable associated with the given Value.
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...
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...
LogicalResult composeMap(const AffineValueMap *vMap)
Composes the affine value map with this FlatAffineValueConstrains, adding the results of the map as d...
LogicalResult addInductionVarOrTerminalSymbol(Value val)
Add the specified values as a dim or symbol var depending on its nature, if it already doesn't exist ...
An Identifier stores a pointer to an object, such as a Value or an Operation.
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
void setId(VarKind kind, unsigned i, Identifier id)
Set the identifier for the ith variable of the specified kind of the IntegerRelation's PresburgerSpac...
virtual void swapVar(unsigned posA, unsigned posB)
Swap the posA^th variable with the posB^th variable.
void convertToLocal(VarKind kind, unsigned varStart, unsigned varLimit)
void append(const IntegerRelation &other)
Appends constraints from other into this.
void addEquality(ArrayRef< DynamicAPInt > eq)
Adds an equality from the coefficients specified in eq.
void setDimSymbolSeparation(unsigned newSymbolCount)
Changes the partition between dimensions and symbols.
unsigned getNumCols() const
Returns the number of columns in the constraint system.
void removeRedundantLocalVars()
Removes local variables using equalities.
const PresburgerSpace & getSpace() const
Returns a reference to the underlying space.
PresburgerSpace getRangeSpace() const
bool isAffineInductionVar(Value val)
Returns true if the provided value is the induction variable of an AffineForOp or AffineParallelOp.
Definition: AffineOps.cpp:2754
AffineForOp getForInductionVarOwner(Value val)
Returns the loop parent of an induction variable.
Definition: AffineOps.cpp:2758
void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Modifies both map and operands in-place so as to:
Definition: AffineOps.cpp:1621
void fullyComposeAffineMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands, bool composeAffineMin=false)
Given an affine map map and its input operands, this method composes into map, maps of AffineApplyOps...
Definition: AffineOps.cpp:1262
void canonicalizeSetAndOperands(IntegerSet *set, SmallVectorImpl< Value > *operands)
Canonicalizes an integer set the same way canonicalizeMapAndOperands does for affine maps.
Definition: AffineOps.cpp:1626
LogicalResult getRelationFromMap(AffineMap &map, presburger::IntegerRelation &rel)
Builds a relation from the given AffineMap/AffineValueMap map, containing all pairs of the form opera...
bool isValidSymbol(Value value)
Returns true if the given value can be used as a symbol in the region of the closest surrounding op t...
Definition: AffineOps.cpp:413
AffineParallelOp getAffineParallelInductionVarOwner(Value val)
Returns true if the provided value is among the induction variables of an AffineParallelOp.
Definition: AffineOps.cpp:2769
BoundType
The type of bound: equal, lower bound or upper bound.
VarKind
Kind of variable.
void mergeLocalVars(IntegerRelation &relA, IntegerRelation &relB, llvm::function_ref< bool(unsigned i, unsigned j)> merge)
Given two relations, A and B, add additional local vars to the sets such that both have the union of ...
Definition: Utils.cpp:288
Include the generated interface declarations.
AffineMap simplifyAffineMap(AffineMap map)
Simplifies an affine map by simplifying its underlying AffineExpr results.
Definition: AffineMap.cpp:766
std::optional< int64_t > getConstantIntValue(OpFoldResult ofr)
If ofr is a constant integer or an IntegerAttr, return the integer.
AffineExpr getAffineExprFromFlatForm(ArrayRef< int64_t > flatExprs, unsigned numDims, unsigned numSymbols, ArrayRef< AffineExpr > localExprs, MLIRContext *context)
Constructs an affine expression from a flat ArrayRef.
LogicalResult getFlattenedAffineExprs(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *cst=nullptr, bool addConservativeSemiAffineBounds=false)
Flattens the result expressions of the map to their corresponding flattened forms and set in 'flatten...
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.