21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
26 #define DEBUG_TYPE "affine-structures"
29 using namespace affine;
30 using namespace presburger;
40 LLVM_DEBUG(llvm::dbgs()
41 <<
"only valid terminal symbols and affine IVs supported\n");
47 if (failed(this->addAffineForOpDomain(loop))) {
49 loop.emitWarning(
"failed to add domain info to constraint system"));
56 appendDimVar(parallel.getIVs());
57 if (failed(this->addAffineParallelOpDomain(parallel))) {
58 LLVM_DEBUG(parallel.emitWarning(
59 "failed to add domain info to constraint system"));
69 addBound(BoundType::EQ, val, constOp.value());
77 if (!findVar(forOp.getInductionVar(), &pos)) {
78 assert(
false &&
"Value not found");
82 int64_t step = forOp.getStepAsInt();
84 if (!forOp.hasConstantLowerBound())
85 LLVM_DEBUG(forOp.emitWarning(
"domain conservatively approximated"));
93 int64_t lb = forOp.getConstantLowerBound();
95 dividend.back() -= lb;
96 addLocalFloorDiv(dividend, step);
102 eq[getNumCols() - 2] = -step;
107 if (forOp.hasConstantLowerBound()) {
108 addBound(BoundType::LB, pos, forOp.getConstantLowerBound());
111 if (failed(addBound(BoundType::LB, pos, forOp.getLowerBoundMap(),
112 forOp.getLowerBoundOperands())))
116 if (forOp.hasConstantUpperBound()) {
117 addBound(BoundType::UB, pos, forOp.getConstantUpperBound() - 1);
121 return addBound(BoundType::UB, pos, forOp.getUpperBoundMap(),
122 forOp.getUpperBoundOperands());
126 AffineParallelOp parallelOp) {
128 for (
Value iv : parallelOp.getIVs()) {
130 if (!findVar(iv, &pos)) {
131 assert(
false &&
"variable expected for the IV value");
135 AffineMap lowerBound = parallelOp.getLowerBoundMap(ivPos);
138 else if (failed(addBound(BoundType::LB, pos, lowerBound,
139 parallelOp.getLowerBoundsOperands())))
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())))
157 assert(lbMaps.size() == ubMaps.size());
158 assert(lbMaps.size() <= getNumDimVars());
160 for (
unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
163 assert(!lbMap || lbMap.
getNumInputs() == operands.size());
164 assert(!ubMap || ubMap.
getNumInputs() == operands.size());
175 !isa<AffineConstantExpr>(lbMap.
getResult(0))) {
187 if (failed(addAffineForOpDomain(loop)))
195 if (lbMap && failed(addBound(BoundType::LB, i, lbMap, operands)))
197 if (ubMap && failed(addBound(BoundType::UB, i, ubMap, operands)))
216 mergeAndAlignVarsWithOther(0, &cst);
230 for (
Value operand : operands) {
231 if (failed(addInductionVarOrTerminalSymbol(operand)))
234 return addBound(type, pos, computeAlignedMap(map, operands));
249 assert(values.size() == lbMaps.size());
250 assert(lbMaps.size() == ubMaps.size());
252 for (
unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
254 if (!findVar(values[i], &pos))
259 assert(!lbMap || lbMap.
getNumInputs() == operands.size());
260 assert(!ubMap || ubMap.
getNumInputs() == operands.size());
266 if (failed(addBound(BoundType::EQ, pos, lbMap, operands)))
276 if (failed(addBound(BoundType::LB, pos, lbMap, operands)))
278 if (failed(addBound(BoundType::UB, pos, ubMap, operands)))
282 if (failed(this->addAffineForOpDomain(loop)))
291 return composeMatchingMap(
299 pos < cst->getNumDimAndSymbolVars()) {
309 for (
unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++) {
311 loopIVs.push_back(getValue(i));
314 for (
auto iv : loopIVs) {
322 unsigned numDims = getNumDimVars();
323 unsigned numSyms = getNumSymbolVars();
325 assert(pos < numDims &&
"invalid position");
326 assert(ineqPos < getNumInequalities() &&
"invalid inequality position");
330 if (failed(computeLocalVars(memo, context)))
332 "one or more local exprs do not have an explicit representation");
338 bound.reserve(getNumCols() - 1);
340 bound.append(inequality.begin(), inequality.begin() + pos);
341 bound.append(inequality.begin() + pos + 1, inequality.end());
343 if (inequality[pos] > 0)
345 std::transform(bound.begin(), bound.end(), bound.begin(),
346 std::negate<int64_t>());
353 localExprs, context);
357 getValues(0, pos, &operands);
359 getValues(pos + 1, getNumDimAndSymbolVars(), &trailingOperands);
360 operands.append(trailingOperands.begin(), trailingOperands.end());
368 getNumDomainDims() + getNumRangeDims());
381 "Domain of this and range of other do not match");
383 "Values of domain of this and range of other do not match");
400 mergeSymbolVars(rel);
411 convertToLocal(VarKind::SetDim, getNumDomainDims() - removeDims,
414 auto thisMaybeValues = getMaybeValues(VarKind::SetDim);
419 if (relMaybeValues[i].has_value())
420 setValue(i, *relMaybeValues[i]);
422 for (
unsigned i = 0, e = getNumRangeDims(); i < e; ++i) {
424 if (thisMaybeValues[rangeIdx].has_value())
425 rel.
setValue(rangeIdx, *thisMaybeValues[rangeIdx]);
436 unsigned oldDomain = getNumDomainDims();
437 unsigned oldRange = getNumRangeDims();
439 appendRangeVar(oldDomain);
441 for (
unsigned i = 0; i < oldDomain; ++i)
442 swapVar(i, oldDomain + oldRange + i);
444 removeVarRange(0, oldDomain);
446 numDomainDims = oldRange;
447 numRangeDims = oldDomain;
451 assert(pos <= getNumDomainDims() &&
452 "Var cannot be inserted at invalid position");
453 insertDimVar(pos, num);
454 numDomainDims += num;
458 assert(pos <= getNumRangeDims() &&
459 "Var cannot be inserted at invalid position");
460 insertDimVar(getNumDomainDims() + pos, num);
465 insertDimVar(getNumDomainDims(), num);
466 numDomainDims += num;
470 insertDimVar(getNumDimVars(), num);
476 assert(varLimit <= getNumVarKind(
kind));
477 if (varStart >= varLimit)
483 if (
kind != VarKind::SetDim)
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());
493 if (intersectDomainLHS > intersectDomainRHS)
494 numDomainDims -= intersectDomainLHS - intersectDomainRHS;
495 if (intersectRangeLHS > intersectRangeRHS)
496 numRangeDims -= intersectRangeLHS - intersectRangeRHS;
502 std::vector<SmallVector<int64_t, 8>> flatExprs;
508 const unsigned oldCols = localVarCst.
getNumCols();
510 const unsigned numDomainVars = map.
getNumDims();
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];
531 eq[numDomainVars + i] = -1;
547 for (
unsigned i = 0, e = affineMap.
getNumDims(); i < e; ++i)
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.
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
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 ...
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...
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...
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
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 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.
unsigned getNumSymbolVars() const
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 getNumDimAndSymbolVars() const
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.
unsigned getNumDimVars() const
PresburgerSpace getRangeSpace() const
bool isAffineInductionVar(Value val)
Returns true if the provided value is the induction variable of an AffineForOp or AffineParallelOp.
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:
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...
void canonicalizeSetAndOperands(IntegerSet *set, SmallVectorImpl< Value > *operands)
Canonicalizes an integer set the same way canonicalizeMapAndOperands does for affine maps.
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...
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.
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.