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"
31 #define DEBUG_TYPE "affine-structures"
34 using namespace affine;
35 using namespace presburger;
44 "non-terminal symbol / loop IV expected");
48 if (
failed(this->addAffineForOpDomain(loop)))
50 loop.emitWarning(
"failed to add domain info to constraint system"));
54 appendDimVar(parallel.getIVs());
55 if (
failed(this->addAffineParallelOpDomain(parallel)))
56 LLVM_DEBUG(parallel.emitWarning(
57 "failed to add domain info to constraint system"));
65 addBound(BoundType::EQ, val, constOp.value());
72 if (!findVar(forOp.getInductionVar(), &pos)) {
73 assert(
false &&
"Value not found");
77 int64_t step = forOp.getStepAsInt();
79 if (!forOp.hasConstantLowerBound())
80 LLVM_DEBUG(forOp.emitWarning(
"domain conservatively approximated"));
88 int64_t lb = forOp.getConstantLowerBound();
90 dividend.back() -= lb;
91 addLocalFloorDiv(dividend, step);
97 eq[getNumCols() - 2] = -step;
102 if (forOp.hasConstantLowerBound()) {
103 addBound(BoundType::LB, pos, forOp.getConstantLowerBound());
106 if (
failed(addBound(BoundType::LB, pos, forOp.getLowerBoundMap(),
107 forOp.getLowerBoundOperands())))
111 if (forOp.hasConstantUpperBound()) {
112 addBound(BoundType::UB, pos, forOp.getConstantUpperBound() - 1);
116 return addBound(BoundType::UB, pos, forOp.getUpperBoundMap(),
117 forOp.getUpperBoundOperands());
121 AffineParallelOp parallelOp) {
123 for (
Value iv : parallelOp.getIVs()) {
125 if (!findVar(iv, &pos)) {
126 assert(
false &&
"variable expected for the IV value");
130 AffineMap lowerBound = parallelOp.getLowerBoundMap(ivPos);
133 else if (
failed(addBound(BoundType::LB, pos, lowerBound,
134 parallelOp.getLowerBoundsOperands())))
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())))
152 assert(lbMaps.size() == ubMaps.size());
153 assert(lbMaps.size() <= getNumDimVars());
155 for (
unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
158 assert(!lbMap || lbMap.
getNumInputs() == operands.size());
159 assert(!ubMap || ubMap.
getNumInputs() == operands.size());
170 !isa<AffineConstantExpr>(lbMap.
getResult(0))) {
182 if (
failed(addAffineForOpDomain(loop)))
190 if (lbMap &&
failed(addBound(BoundType::LB, i, lbMap, operands)))
192 if (ubMap &&
failed(addBound(BoundType::UB, i, ubMap, operands)))
211 mergeAndAlignVarsWithOther(0, &cst);
225 for (
auto operand : operands)
226 addInductionVarOrTerminalSymbol(operand);
227 return addBound(type, pos, computeAlignedMap(map, operands));
242 assert(values.size() == lbMaps.size());
243 assert(lbMaps.size() == ubMaps.size());
245 for (
unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
247 if (!findVar(values[i], &pos))
252 assert(!lbMap || lbMap.
getNumInputs() == operands.size());
253 assert(!ubMap || ubMap.
getNumInputs() == operands.size());
259 if (
failed(addBound(BoundType::EQ, pos, lbMap, operands)))
269 if (
failed(addBound(BoundType::LB, pos, lbMap, operands)))
271 if (
failed(addBound(BoundType::UB, pos, ubMap, operands)))
275 if (
failed(this->addAffineForOpDomain(loop)))
284 return composeMatchingMap(
292 pos < cst->getNumDimAndSymbolVars()) {
302 for (
unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++) {
304 loopIVs.push_back(getValue(i));
307 for (
auto iv : loopIVs) {
315 unsigned numDims = getNumDimVars();
316 unsigned numSyms = getNumSymbolVars();
318 assert(pos < numDims &&
"invalid position");
319 assert(ineqPos < getNumInequalities() &&
"invalid inequality position");
323 if (
failed(computeLocalVars(memo, context)))
325 "one or more local exprs do not have an explicit representation");
331 bound.reserve(getNumCols() - 1);
333 bound.append(inequality.begin(), inequality.begin() + pos);
334 bound.append(inequality.begin() + pos + 1, inequality.end());
336 if (inequality[pos] > 0)
338 std::transform(bound.begin(), bound.end(), bound.begin(),
339 std::negate<int64_t>());
346 localExprs, context);
350 getValues(0, pos, &operands);
352 getValues(pos + 1, getNumDimAndSymbolVars(), &trailingOperands);
353 operands.append(trailingOperands.begin(), trailingOperands.end());
361 getNumDomainDims() + getNumRangeDims());
374 "Domain of this and range of other do not match");
375 assert(std::equal(values.begin(), values.begin() + getNumDomainDims(),
377 "Domain of this and range of other do not match");
394 mergeSymbolVars(rel);
405 convertToLocal(VarKind::SetDim, getNumDomainDims() - removeDims,
408 auto thisMaybeValues = getMaybeValues(VarKind::SetDim);
413 if (relMaybeValues[i].has_value())
414 setValue(i, *relMaybeValues[i]);
416 for (
unsigned i = 0, e = getNumRangeDims(); i < e; ++i) {
418 if (thisMaybeValues[rangeIdx].has_value())
419 rel.
setValue(rangeIdx, *thisMaybeValues[rangeIdx]);
430 unsigned oldDomain = getNumDomainDims();
431 unsigned oldRange = getNumRangeDims();
433 appendRangeVar(oldDomain);
435 for (
unsigned i = 0; i < oldDomain; ++i)
436 swapVar(i, oldDomain + oldRange + i);
438 removeVarRange(0, oldDomain);
440 numDomainDims = oldRange;
441 numRangeDims = oldDomain;
445 assert(pos <= getNumDomainDims() &&
446 "Var cannot be inserted at invalid position");
447 insertDimVar(pos, num);
448 numDomainDims += num;
452 assert(pos <= getNumRangeDims() &&
453 "Var cannot be inserted at invalid position");
454 insertDimVar(getNumDomainDims() + pos, num);
459 insertDimVar(getNumDomainDims(), num);
460 numDomainDims += num;
464 insertDimVar(getNumDimVars(), num);
470 assert(varLimit <= getNumVarKind(kind));
471 if (varStart >= varLimit)
477 if (kind != VarKind::SetDim)
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());
487 if (intersectDomainLHS > intersectDomainRHS)
488 numDomainDims -= intersectDomainLHS - intersectDomainRHS;
489 if (intersectRangeLHS > intersectRangeRHS)
490 numRangeDims -= intersectRangeLHS - intersectRangeRHS;
496 std::vector<SmallVector<int64_t, 8>> flatExprs;
513 std::fill(eq.begin(), eq.end(), 0);
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];
520 eq[numDomainVars + i] = -1;
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.
unsigned getPosition() const
Base type for affine expression.
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
int64_t getSingleConstantResult() const
Returns the constant result of this map.
bool isConstant() const
Returns true if this affine map has only constant results.
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
unsigned getNumDims() const
unsigned getNumResults() const
unsigned getNumInputs() const
AffineExpr getResult(unsigned idx) const
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 ...
unsigned appendDimVar(ValueRange vals)
bool findVar(Value val, unsigned *pos, unsigned offset=0) const
Looks up the position of the variable with the specified Value starting with variables at offset offs...
ArrayRef< std::optional< Value > > getMaybeValues() const
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.
MLIRContext is the top-level object for a collection of MLIR operations.
This class provides an abstraction over the different types of ranges over Values.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
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
AffineMap getAffineMap() 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 ...
void appendRangeVar(unsigned num=1)
unsigned getNumRangeDims() const
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.
unsigned getNumSymbolVars() const
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 getNumDimAndSymbolVars() const
unsigned getNumCols() const
Returns the number of columns in the constraint system.
void removeRedundantLocalVars()
Removes local variables using equalities.
unsigned getNumDimVars() const
void fullyComposeAffineMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Given an affine map map and its input operands, this method composes into map, maps of AffineApplyOps...
bool isAffineInductionVar(Value val)
Returns true if the provided value is the induction variable of an AffineForOp or AffineParallelOp.
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.
void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Modifies both map and operands in-place so as to:
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...
void canonicalizeSetAndOperands(IntegerSet *set, SmallVectorImpl< Value > *operands)
Canonicalizes an integer set the same way canonicalizeMapAndOperands does for affine maps.
AffineParallelOp getAffineParallelInductionVarOwner(Value val)
Returns true if the provided value is among the induction variables of an AffineParallelOp.
BoundType
The type of bound: equal, lower bound or upper bound.
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 ...
Include the generated interface declarations.
AffineMap simplifyAffineMap(AffineMap map)
Simplifies an affine map by simplifying its underlying AffineExpr results.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
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.
AffineExpr getAffineExprFromFlatForm(ArrayRef< int64_t > flatExprs, unsigned numDims, unsigned numSymbols, ArrayRef< AffineExpr > localExprs, MLIRContext *context)
Constructs an affine expression from a flat ArrayRef.
LogicalResult getFlattenedAffineExprs(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *cst=nullptr)
Flattens the result expressions of the map to their corresponding flattened forms and set in 'flatten...
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
This class represents an efficient way to signal success or failure.
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.