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