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" 30 #define DEBUG_TYPE "affine-structures" 33 using namespace presburger;
48 AffineExprFlattener(
unsigned nDims,
unsigned nSymbols)
77 localVarCst->
reset(numDims, numSymbols);
81 AffineExprFlattener flattener(numDims, numSymbols);
84 for (
auto expr : exprs) {
85 if (!expr.isPureAffine())
88 flattener.walkPostOrder(expr);
91 assert(flattener.operandExprStack.size() == exprs.size());
92 flattenedExprs->clear();
93 flattenedExprs->assign(flattener.operandExprStack.begin(),
94 flattener.operandExprStack.end());
109 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
111 &flattenedExprs, localVarCst);
112 *flattenedExpr = flattenedExprs[0];
133 if (
set.getNumConstraints() == 0) {
134 localVarCst->
reset(
set.getNumDims(),
set.getNumSymbols());
138 set.getNumSymbols(), flattenedExprs,
146 std::unique_ptr<FlatAffineValueConstraints>
148 return std::make_unique<FlatAffineValueConstraints>(*this);
154 set.getNumDims() + set.getNumSymbols() + 1,
163 std::vector<SmallVector<int64_t, 8>> flatExprs;
166 assert(
false &&
"flattening unimplemented for semi-affine integer sets");
169 assert(flatExprs.size() ==
set.getNumConstraints());
173 for (
unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
174 const auto &flatExpr = flatExprs[i];
176 if (
set.getEqFlags()[i]) {
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");
213 for (
int ivIdx = 0, e = nIvs; ivIdx < e; ++ivIdx) {
218 llvm_unreachable(
"Unexpected FlatAffineValueConstraints creation error");
223 llvm_unreachable(
"Unexpected FlatAffineValueConstraints creation error");
229 unsigned numReservedEqualities,
230 unsigned newNumReservedCols,
232 unsigned newNumSymbols,
233 unsigned newNumLocals) {
234 assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 &&
237 numReservedEqualities, newNumReservedCols,
238 newNumDims, newNumSymbols, newNumLocals);
242 unsigned newNumSymbols,
243 unsigned newNumLocals) {
245 newNumDims + newNumSymbols + newNumLocals + 1,
246 newNumDims, newNumSymbols, newNumLocals);
250 unsigned numReservedInequalities,
unsigned numReservedEqualities,
251 unsigned newNumReservedCols,
unsigned newNumDims,
unsigned newNumSymbols,
253 assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 &&
256 if (!valArgs.empty())
257 newVals.assign(valArgs.begin(), valArgs.end());
260 numReservedInequalities, numReservedEqualities, newNumReservedCols,
261 newNumDims, newNumSymbols, newNumLocals, newVals);
265 unsigned newNumSymbols,
266 unsigned newNumLocals,
268 reset(0, 0, newNumDims + newNumSymbols + newNumLocals + 1, newNumDims,
269 newNumSymbols, newNumLocals, valArgs);
274 insertId(IdKind::SetDim, pos, vals);
280 insertId(IdKind::Symbol, pos, vals);
286 return insertId(IdKind::SetDim, pos, vals);
291 return insertId(IdKind::Symbol, pos, vals);
296 unsigned absolutePos = IntegerPolyhedron::insertId(kind, pos, num);
298 if (kind != IdKind::Local) {
308 assert(!vals.empty() &&
"expected ValueRange with Values.");
309 assert(kind != IdKind::Local &&
310 "values cannot be attached to local identifiers.");
311 unsigned num = vals.size();
312 unsigned absolutePos = IntegerPolyhedron::insertId(kind, pos, num);
315 for (
unsigned i = 0; i < num; ++i)
325 return id.hasValue();
352 "Start position out of bounds");
362 if (val.hasValue() && !uniqueIds.insert(val.getValue()).second)
369 static bool LLVM_ATTRIBUTE_UNUSED
376 static bool LLVM_ATTRIBUTE_UNUSED
379 if (kind == IdKind::SetDim)
381 if (kind == IdKind::Symbol)
383 llvm_unreachable(
"Unexpected IdKind");
416 for (
auto aDimValue : aDimValues) {
418 if (b->
findId(aDimValue, &loc)) {
419 assert(loc >= offset &&
"A's dim appears in B's aligned range");
421 "A's dim appears in B's non-dim position");
433 "expected same number of dims");
441 assert(
areIdsAligned(*a, *b) &&
"IDs expected to be aligned");
463 std::vector<SmallVector<int64_t, 8>> flatExprs;
477 for (
unsigned r = 0, e = flatExprs.size(); r < e; r++) {
478 const auto &flatExpr = flatExprs[r];
486 for (
unsigned i = 0, f = other.
getNumInputs(); i < f; i++) {
488 eqToAdd[e + i] = -flatExpr[i];
492 unsigned end = flatExpr.size() - 1;
493 for (
unsigned i = other.
getNumInputs(); i < end; i++, j++) {
494 eqToAdd[j] = -flatExpr[i];
498 eqToAdd[
getNumCols() - 1] = -flatExpr[flatExpr.size() - 1];
524 assert(
areIdsUnique(*
this, IdKind::Symbol) &&
"Symbol ids are not unique");
525 assert(
areIdsUnique(other, IdKind::Symbol) &&
"Symbol ids are not unique");
532 for (
Value aSymValue : aSymValues) {
551 "expected same number of symbols");
552 assert(
areIdsUnique(*
this, IdKind::Symbol) &&
"Symbol ids are not unique");
553 assert(
areIdsUnique(other, IdKind::Symbol) &&
"Symbol ids are not unique");
565 for (
auto iv : loopIVs) {
576 "non-terminal symbol / loop IV expected");
582 loop.emitWarning(
"failed to add domain info to constraint system"));
589 addBound(BoundType::EQ, val, constOp.value());
596 if (!
findId(forOp.getInductionVar(), &pos)) {
597 assert(
false &&
"Value not found");
601 int64_t step = forOp.getStep();
603 if (!forOp.hasConstantLowerBound())
604 LLVM_DEBUG(forOp.emitWarning(
"domain conservatively approximated"));
612 int64_t lb = forOp.getConstantLowerBound();
614 dividend.back() -= lb;
626 if (forOp.hasConstantLowerBound()) {
627 addBound(BoundType::LB, pos, forOp.getConstantLowerBound());
631 forOp.getLowerBoundOperands())))
635 if (forOp.hasConstantUpperBound()) {
636 addBound(BoundType::UB, pos, forOp.getConstantUpperBound() - 1);
640 return addBound(BoundType::UB, pos, forOp.getUpperBoundMap(),
641 forOp.getUpperBoundOperands());
648 assert(lbMaps.size() == ubMaps.size());
651 for (
unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
654 assert(!lbMap || lbMap.
getNumInputs() == operands.size());
655 assert(!ubMap || ubMap.
getNumInputs() == operands.size());
700 cst.setValues(0, cst.getNumDimAndSymbolIds(), operands);
710 return IntegerPolyhedron::hasConsistentState() &&
716 IntegerPolyhedron::removeIdRange(kind, idStart, idLimit);
719 if (kind != IdKind::Local) {
721 values.begin() + idLimit + offset);
746 int64_t lbConst, int64_t ubConst,
749 assert(pos < cst.
getNumIds() &&
"invalid position");
753 if (lbConst != 0 || ubConst < 1)
755 int64_t divisor = ubConst + 1;
759 curEquality < numEqualities; curEquality++) {
760 int64_t coefficientAtPos = cst.
atEq(curEquality, pos);
763 if (coefficientAtPos == 0)
779 unsigned quotientCount = 0;
780 int quotientPosition = -1;
781 int quotientSign = 1;
789 int64_t coefficientOfCurId = cst.
atEq(curEquality, curId);
791 if (coefficientOfCurId == 0)
794 if (coefficientOfCurId % (divisor * coefficientAtPos) == 0) {
796 quotientPosition = curId;
797 quotientSign = (coefficientOfCurId * coefficientAtPos) > 0 ? 1 : -1;
804 dividendExpr = dividendExpr + memo[curId] * coefficientOfCurId;
812 if (coefficientAtPos > 0)
813 dividendExpr = (-dividendExpr).
floorDiv(coefficientAtPos);
815 dividendExpr = dividendExpr.floorDiv(-coefficientAtPos);
829 if (quotientCount >= 1) {
831 dimExpr.getPosition());
834 if (ub.hasValue() && ub.getValue() < divisor)
837 memo[pos] = dimExpr % divisor;
840 if (quotientCount == 1 && !memo[quotientPosition])
841 memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;
859 assert(pos < cst.
getNumIds() &&
"invalid position");
863 for (
unsigned i = 0, e = cst.
getNumIds(); i < e; ++i)
872 if (ulPair.kind == ReprKind::None || ulPair.kind == ReprKind::Equality)
877 for (
unsigned c = 0, f = cst.
getNumIds(); c < f; c++)
878 if (dividend[c] != 0)
879 dividendExpr = dividendExpr + dividend[c] * exprs[c];
882 exprs[pos] = dividendExpr.floorDiv(divisor);
886 std::pair<AffineMap, AffineMap>
888 unsigned pos,
unsigned offset,
unsigned num,
unsigned symStartPos,
890 assert(pos + offset <
getNumDimIds() &&
"invalid dim start pos");
891 assert(symStartPos >= (pos + offset) &&
"invalid sym start pos");
893 "incorrect local exprs count");
902 for (
unsigned i = 0, e = a.size(); i < e; ++i) {
903 if (i < offset || i >= offset + num)
910 unsigned dimCount = symStartPos - num;
912 lbExprs.reserve(lbIndices.size() + eqIndices.size());
914 for (
auto idx : lbIndices) {
920 std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
924 int64_t divisor = std::abs(ineq[pos + offset]);
925 expr = (expr + divisor - 1).
floorDiv(divisor);
926 lbExprs.push_back(expr);
930 ubExprs.reserve(ubIndices.size() + eqIndices.size());
932 for (
auto idx : ubIndices) {
938 expr = expr.floorDiv(std::abs(ineq[pos + offset]));
940 ubExprs.push_back(expr + 1);
945 for (
auto idx : eqIndices) {
948 if (eq[pos + offset] > 0)
949 std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());
954 expr = expr.floorDiv(std::abs(eq[pos + offset]));
956 ubExprs.push_back(expr + 1);
960 expr = expr.ceilDiv(std::abs(eq[pos + offset]));
961 lbExprs.push_back(expr);
964 auto lbMap =
AffineMap::get(dimCount, symCount, lbExprs, context);
965 auto ubMap =
AffineMap::get(dimCount, symCount, ubExprs, context);
967 return {lbMap, ubMap};
976 unsigned offset,
unsigned num,
MLIRContext *context,
984 LLVM_DEBUG(llvm::dbgs() <<
"getSliceBounds for first " << num
985 <<
" identifiers\n");
994 else if (i >= offset + num)
1005 for (
unsigned pos = 0; pos <
getNumIds(); pos++) {
1011 if (lbConst.hasValue() && ubConst.hasValue()) {
1013 if (lbConst.getValue() == ubConst.getValue()) {
1021 if (
detectAsMod(*
this, pos, lbConst.getValue(), ubConst.getValue(),
1044 for (j = 0, e =
getNumIds(); j < e; ++j) {
1047 int64_t c =
atEq(idx, j);
1053 expr = expr + memo[j] * c;
1062 int64_t vPos =
atEq(idx, pos);
1063 assert(vPos != 0 &&
"expected non-zero here");
1068 expr = expr.floorDiv(-vPos);
1078 int64_t ubAdjustment = getClosedUB ? 0 : 1;
1084 for (
unsigned pos = 0; pos < num; pos++) {
1096 ubMap =
AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
1107 tmpClone->removeRedundantInequalities();
1109 std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
1119 LLVM_DEBUG(llvm::dbgs()
1120 <<
"WARNING: Potentially over-approximating slice lb\n");
1122 if (lbConst.hasValue()) {
1124 numMapDims, numMapSymbols,
1129 LLVM_DEBUG(llvm::dbgs()
1130 <<
"WARNING: Potentially over-approximating slice ub\n");
1132 if (ubConst.hasValue()) {
1136 ubConst.getValue() + ubAdjustment, context));
1140 LLVM_DEBUG(llvm::dbgs()
1141 <<
"lb map for pos = " << Twine(pos + offset) <<
", expr: ");
1142 LLVM_DEBUG(lbMap.
dump(););
1143 LLVM_DEBUG(llvm::dbgs()
1144 <<
"ub map for pos = " << Twine(pos + offset) <<
", expr: ");
1145 LLVM_DEBUG(ubMap.
dump(););
1153 LLVM_DEBUG(llvm::dbgs()
1154 <<
"composition unimplemented for semi-affine maps\n");
1175 bool isClosedBound) {
1179 assert((type != BoundType::EQ || isClosedBound) &&
1180 "EQ bound must be closed.");
1184 assert((type != BoundType::EQ || boundMap.
getNumResults() == 1) &&
1185 "single result expected");
1186 bool lower = type == BoundType::LB || type == BoundType::EQ;
1188 std::vector<SmallVector<int64_t, 8>> flatExprs;
1194 for (
const auto &flatExpr : flatExprs) {
1198 ineq[
j] = lower ? -flatExpr[
j] : flatExpr[
j];
1205 ineq[pos] = lower ? 1 : -1;
1208 unsigned end = flatExpr.size() - 1;
1209 for (
unsigned i = boundMap.
getNumInputs(); i < end; i++, j++) {
1210 ineq[j] = lower ? -flatExpr[i] : flatExpr[i];
1214 int64_t boundAdjustment = (isClosedBound || type == BoundType::EQ) ? 0 : -1;
1216 ineq[
getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
1217 : flatExpr[flatExpr.size() - 1]) +
1227 return addBound(type, pos, boundMap, type != BoundType::UB);
1233 assert(map.
getNumInputs() == operands.size() &&
"number of inputs mismatch");
1257 assert(syms.size() == newSymsPtr->size() &&
"unexpected new/missing symbols");
1258 assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
1259 "unexpected new/missing symbols");
1268 auto map = boundMap;
1273 for (
auto operand : operands)
1290 assert(values.size() == lbMaps.size());
1291 assert(lbMaps.size() == ubMaps.size());
1293 for (
unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
1295 if (!
findId(values[i], &pos))
1300 assert(!lbMap || lbMap.
getNumInputs() == operands.size());
1301 assert(!ubMap || ubMap.
getNumInputs() == operands.size());
1332 for (
const auto &mayBeId :
values) {
1333 if (mayBeId.hasValue() && mayBeId.getValue() == val) {
1344 return mayBeId.hasValue() && mayBeId.getValue() == val;
1349 IntegerPolyhedron::swapId(posA, posB);
1368 assert(0 &&
"id not found");
1391 if (
auto *otherValueSet =
1392 dyn_cast<const FlatAffineValueConstraints>(&other)) {
1393 *
this = *otherValueSet;
1402 unsigned pos,
bool darkShadow,
bool *isResultIntegerExact) {
1405 newVals.erase(newVals.begin() + pos);
1407 IntegerPolyhedron::fourierMotzkinEliminate(pos, darkShadow,
1408 isResultIntegerExact);
1415 bool ret =
findId(val, &pos);
1427 "dim values mismatch");
1428 assert(otherCst.
getNumLocalIds() == 0 &&
"local ids not supported here");
1429 assert(
getNumLocalIds() == 0 &&
"local ids not supported yet here");
1435 return IntegerPolyhedron::unionBoundingBox(otherCopy);
1438 return IntegerPolyhedron::unionBoundingBox(otherCst);
1451 for (
unsigned i = 0; i < numDims; i++)
1453 for (
unsigned i = numDims, e = numDims + numSyms; i < e; i++)
1463 if (!memo[numDims + numSyms + i] &&
1471 llvm::all_of(localExprs, [](
AffineExpr expr) {
return expr; }));
1480 assert(pos < numDims &&
"invalid position");
1487 "one or more local exprs do not have an explicit representation");
1495 bound.append(inequality.begin(), inequality.begin() + pos);
1496 bound.append(inequality.begin() + pos + 1, inequality.end());
1498 if (inequality[pos] > 0)
1500 std::transform(bound.begin(), bound.end(), bound.begin(),
1501 std::negate<int64_t>());
1508 localExprs, context);
1515 operands.append(trailingOperands.begin(), trailingOperands.end());
1535 for (
unsigned i = numDimsSymbols, e =
getNumIds(); i < e; ++i) {
1537 noLocalRepVars.push_back(i - numDimsSymbols);
1539 if (!noLocalRepVars.empty()) {
1541 llvm::dbgs() <<
"local variables at position(s) ";
1542 llvm::interleaveComma(noLocalRepVars, llvm::dbgs());
1543 llvm::dbgs() <<
" do not have an explicit representation in:\n";
1566 localExprs, context));
1569 numSyms, localExprs, context));
1577 "expected same number of operands and map inputs");
1581 unsigned numSymbols = syms.size();
1585 newSyms->append(syms.begin(), syms.end());
1591 auto dimIt = std::find(dims.begin(), dims.end(), operand.value());
1592 auto symIt = std::find(syms.begin(), syms.end(), operand.value());
1593 if (dimIt != dims.end()) {
1596 }
else if (symIt != syms.end()) {
1604 newSyms->push_back(operand.value());
1608 dimReplacements[operand.index()] = replacement;
1610 symReplacements[operand.index() - map.
getNumDims()] = replacement;
1615 dims.size(), numSymbols);
1622 getNumDomainDims() + getNumRangeDims());
1635 "Domain of this and range of other do not match");
1636 assert(std::equal(
values.begin(),
values.begin() + getNumDomainDims(),
1638 "Domain of this and range of other do not match");
1667 getNumDomainDims());
1677 for (
unsigned i = 0, e = getNumRangeDims(); i < e; ++i) {
1679 if (thisMaybeValues[rangeIdx].
hasValue())
1691 unsigned oldDomain = getNumDomainDims();
1692 unsigned oldRange = getNumRangeDims();
1694 appendRangeId(oldDomain);
1696 for (
unsigned i = 0; i < oldDomain; ++i)
1697 swapId(i, oldDomain + oldRange + i);
1701 numDomainDims = oldRange;
1702 numRangeDims = oldDomain;
1706 assert(pos <= getNumDomainDims() &&
1707 "Id cannot be inserted at invalid position");
1709 numDomainDims += num;
1713 assert(pos <= getNumRangeDims() &&
1714 "Id cannot be inserted at invalid position");
1716 numRangeDims += num;
1721 numDomainDims += num;
1726 numRangeDims += num;
1732 if (idStart >= idLimit)
1738 if (kind != IdKind::SetDim)
1743 unsigned intersectDomainLHS =
std::min(idLimit, getNumDomainDims());
1744 unsigned intersectDomainRHS = idStart;
1746 unsigned intersectRangeRHS =
std::max(idStart, getNumDomainDims());
1748 if (intersectDomainLHS > intersectDomainRHS)
1749 numDomainDims -= intersectDomainLHS - intersectDomainRHS;
1750 if (intersectRangeLHS > intersectRangeRHS)
1751 numRangeDims -= intersectRangeLHS - intersectRangeRHS;
1757 std::vector<SmallVector<int64_t, 8>> flatExprs;
1774 std::fill(eq.begin(), eq.end(), 0);
1776 for (
unsigned j = 0, f = oldDimNum;
j < f; ++
j)
1777 eq[
j] = flatExprs[i][
j];
1778 for (
unsigned j = oldDimNum, f = oldCols;
j < f; ++
j)
1779 eq[
j + numRangeIds] = flatExprs[i][
j];
1781 eq[numDomainIds + i] = -1;
Include the generated interface declarations.
void addLocalFloorDiv(ArrayRef< int64_t > dividend, int64_t divisor)
Adds a new local identifier as the floordiv of an affine function of other identifiers, the coefficients of which are provided in dividend and with respect to a positive constant divisor.
unsigned getNumDomainDims() const
Returns the number of identifiers 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)
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.
void insertDomainId(unsigned pos, unsigned num=1)
Insert num identifiers of the specified kind after the pos identifier of that kind.
unsigned getNumSymbols() const
unsigned getNumDims() const
unsigned mergeLocalIds(IntegerRelation &other)
Adds additional local ids to the sets such that they both have the union of the local ids in each set...
AffineExpr getAffineConstantExpr(int64_t constant, MLIRContext *context)
void addEquality(ArrayRef< int64_t > eq)
Adds an equality from the coefficients specified in eq.
LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, SmallVectorImpl< int64_t > *flattenedExpr, FlatAffineValueConstraints *cst=nullptr)
Flattens 'expr' into 'flattenedExpr', 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 identifier 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 identifier has an associated Value.
void convertLoopIVSymbolsToDims()
Changes all symbol identifiers which are loop IVs to dim identifiers.
void removeIdRange(presburger::IdKind kind, unsigned idStart, unsigned idLimit) override
Removes identifiers in the column range [idStart, idLimit), and copies any remaining valid data into ...
bool hasValues() const
Returns true if at least one identifier has an associated Value.
static IntegerSet get(unsigned dimCount, unsigned symbolCount, ArrayRef< AffineExpr > constraints, ArrayRef< bool > eqFlags)
unsigned insertSymbolId(unsigned pos, unsigned num=1)
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value...
AffineExpr getAffineSymbolExpr(unsigned position)
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 ...
ArrayRef< int64_t > getInequality(unsigned idx) const
void addAffineIfOpDomain(AffineIfOp ifOp)
Adds constraints imposed by the affine.if operation.
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 identifier at pos from the inequality at ineqPos as a 1-d affine value map ...
LogicalResult flattenAlignedMapAndMergeLocals(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs)
Given an affine map that is aligned with this constraint system:
unsigned getPosition() const
unsigned getNumIdKind(IdKind kind) const
Get the number of ids of the specified kind.
LogicalResult getRelationFromMap(AffineMap &map, FlatAffineRelation &rel)
Builds a relation from the given AffineMap/AffineValueMap map, containing all pairs of the form opera...
An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affin...
An integer constant appearing in affine expression.
BoundType
The type of bound: equal, lower bound or upper bound.
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.
unsigned insertDimId(unsigned pos, unsigned num=1)
Insert identifiers of the specified kind at position pos.
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
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.
AffineExpr getResult(unsigned idx) const
static void printSpace(std::ostream &os, int count)
unsigned getNumEqualities() const
bool containsId(Value val) const
Returns true if an identifier with the specified Value exists, false otherwise.
unsigned getNumInputs() const
void addInequality(ArrayRef< int64_t > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
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 iden...
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
This class represents an efficient way to signal success or failure.
ArrayRef< Optional< Value > > getMaybeValues() const
void fourierMotzkinEliminate(unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr) override
Eliminates the identifier at the specified position using Fourier-Motzkin variable elimination...
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
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's floordiv operation on constants.
bool isColZero(unsigned pos) const
Returns true if the pos^th column is all zero for both inequalities and equalities.
IdKind
Kind of identifier.
unsigned getNumInequalities() const
void removeIdRange(IdKind kind, unsigned idStart, unsigned idLimit) override
Removes identifiers in the column range [idStart, idLimit), and copies any remaining valid data into ...
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
unsigned getNumLocalIds() const
unsigned insertLocalId(unsigned pos, unsigned num=1)
void appendRangeId(unsigned num=1)
void addInductionVarOrTerminalSymbol(Value val)
Add the specified values as a dim or symbol id depending on its nature, if it already doesn't exist i...
static bool detectAsFloorDiv(const FlatAffineValueConstraints &cst, unsigned pos, MLIRContext *context, SmallVectorImpl< AffineExpr > &exprs)
Check if the pos^th identifier can be expressed as a floordiv of an affine function of other identifi...
bool areIdsAlignedWithOther(const FlatAffineValueConstraints &other)
Returns true if this constraint system and other are in the same space, i.e., if they are associated ...
AffineExpr getAffineSymbolExpr(unsigned position, MLIRContext *context)
void fullyComposeAffineMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Given an affine map map and its input operands, this method composes into map, maps of AffineApplyOps...
AffineMap replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements, unsigned numResultDims, unsigned numResultSyms) const
This method substitutes any uses of dimensions and symbols (e.g.
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
unsigned appendLocalId(unsigned num=1)
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 ...
ArrayRef< int64_t > getEquality(unsigned idx) const
Base type for affine expression.
void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Modifies both map and operands in-place so as to:
IdKind getIdKindAt(unsigned pos) const
Return the IdKind of the id at the specified position.
unsigned getNumConstraints() const
bool hasConsistentState() const override
Returns false if the fields corresponding to various identifier counts, or equality/inequality buffer...
virtual void addLocalFloorDivId(ArrayRef< int64_t > dividend, int64_t divisor, AffineExpr localExpr)
unsigned getNumResults() const
void appendDomainId(unsigned num=1)
Append num identifiers of the specified kind after the last identifier of that kind.
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
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's are immutable like Type's, and they are uniqued...
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.
void insertRangeId(unsigned pos, unsigned num=1)
AffineMap getAffineMap() const
ArrayRef< AffineExpr > getResults() const
unsigned getNumSymbolIds() const
Eliminates identifier at the specified position using Fourier-Motzkin variable elimination.
SmallVector< Optional< Value >, 8 > values
Values corresponding to the (column) non-local identifiers of this constraint system appearing in the...
AffineExpr getAffineDimExpr(unsigned position, MLIRContext *context)
These free functions allow clients of the API to not use classes in detail.
MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst, ArrayRef< bool > foundRepr, unsigned pos, SmallVector< int64_t, 8 > ÷nd, unsigned &divisor)
Check if the pos^th identifier can be expressed as a floordiv of an affine function of other identifi...
void swapId(unsigned posA, unsigned posB) override
Swap the posA^th identifier with the posB^th identifier.
unsigned insertId(presburger::IdKind kind, unsigned pos, unsigned num=1) override
Insert num identifiers of the specified kind at position pos.
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
unsigned getIdKindOffset(IdKind kind) const
Return the index at which the specified kind of id starts.
void projectOut(Value val)
Projects out the identifier 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 ...
static bool areIdsAligned(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...
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.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
unsigned appendSymbolId(ValueRange vals)
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.
void normalizeConstraintsByGCD()
Normalized each constraints by the GCD of its coefficients.
void convertToLocal(IdKind kind, unsigned idStart, unsigned idLimit)
This class is a general helper class for creating context-global objects like types, attributes, and affine expressions.
unsigned getIdKindEnd(IdKind kind) const
Return the index at Which the specified kind of id ends.
AffineMap simplifyAffineMap(AffineMap map)
Simplifies an affine map by simplifying its underlying AffineExpr results.
FlatAffineValueConstraints represents an extension of IntegerPolyhedron where each non-local identifi...
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 identifier at pos, and optionally any equalitie...
static bool LLVM_ATTRIBUTE_UNUSED areIdsUnique(const FlatAffineValueConstraints &cst, unsigned start, unsigned end)
Checks if the SSA values associated with cst's identifiers in range [start, end) are unique...
A dimensional identifier appearing in an affine expression.
Specialization of arith.constant op that returns an integer of index type.
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
int64_t atEq(unsigned i, unsigned j) const
Returns the value at the specified equality row and column.
unsigned getNumCols() const
Returns the number of columns in the constraint system.
MLIRContext is the top-level object for a collection of MLIR operations.
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR i...
void mergeSymbolIds(FlatAffineValueConstraints &other)
Merge and align symbols of this and other such that both get union of of symbols that are unique...
AffineExpr getAffineDimExpr(unsigned position)
void inverse()
Swap domain and range of the relation.
void setValue(unsigned pos, Value val)
Sets the Value associated with the pos^th identifier.
FlatAffineValueConstraints getDomainSet() const
Returns a set corresponding to the domain/range of the affine relation.
unsigned getNumDimIds() const
unsigned getNumRangeDims() const
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th identifier.
void mergeAndAlignIdsWithOther(unsigned offset, FlatAffineValueConstraints *other)
Merge and align the identifiers of this and other starting at offset, so that both constraint systems...
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes...
unsigned getNumIds() const
static LogicalResult computeLocalVars(const FlatAffineValueConstraints &cst, SmallVectorImpl< AffineExpr > &memo, MLIRContext *context)
Compute an explicit representation for local vars.
MLIRContext * getContext() const
PresburgerSpace is the space of all possible values of a tuple of integer valued variables/identifier...
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 'flatten...
static void mergeAndAlignIds(unsigned offset, FlatAffineValueConstraints *a, FlatAffineValueConstraints *b)
Merge and align the identifiers of A and B starting at 'offset', so that both constraint systems get ...
bool findId(Value val, unsigned *pos) const
Looks up the position of the identifier with the specified Value.
void getValues(unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
Returns the Values associated with identifiers in range [start, end).
ArrayRef< Value > getOperands() const
void compose(const FlatAffineRelation &other)
Given affine relation other: (domainOther -> rangeOther), this operation takes the composition of oth...
unsigned appendDimId(ValueRange vals)
Append identifiers of the specified kind after the last identifier of that kind.
void reset(AffineMap map, ValueRange operands, ValueRange results={})
This class provides an abstraction over the different types of ranges over Values.
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 identifie...
static void turnSymbolIntoDim(FlatAffineValueConstraints *cst, Value id)
Optional< int64_t > getConstantBound(BoundType type, unsigned pos) const
Returns the constant bound for the pos^th identifier if there is one; None otherwise.
unsigned getNumDimAndSymbolIds() const
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 identifiers (starting at offset) as ...
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 identifier at the specified position with constraints being drawn from the speci...
An integer set representing a conjunction of one or more affine equalities and inequalities.