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 presburger;
49 AffineExprFlattener(
unsigned nDims,
unsigned nSymbols)
78 localVarCst->
reset(numDims, numSymbols);
82 AffineExprFlattener flattener(numDims, numSymbols);
85 for (
auto expr : exprs) {
86 if (!expr.isPureAffine())
89 flattener.walkPostOrder(expr);
92 assert(flattener.operandExprStack.size() == exprs.size());
93 flattenedExprs->clear();
94 flattenedExprs->assign(flattener.operandExprStack.begin(),
95 flattener.operandExprStack.end());
110 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
112 &flattenedExprs, localVarCst);
113 *flattenedExpr = flattenedExprs[0];
147 std::unique_ptr<FlatAffineValueConstraints>
149 return std::make_unique<FlatAffineValueConstraints>(*
this);
156 set.getNumDims() + set.getNumSymbols() + 1,
161 if (operands.empty()) {
164 assert(set.
getNumInputs() == operands.size() &&
"operand count mismatch");
165 values.assign(operands.begin(), operands.end());
169 std::vector<SmallVector<int64_t, 8>> flatExprs;
172 assert(
false &&
"flattening unimplemented for semi-affine integer sets");
179 for (
unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
180 const auto &flatExpr = flatExprs[i];
207 unsigned nIvs = ivs.size();
208 assert(nIvs == lbs.size() &&
"expected as many lower bounds as ivs");
209 assert(nIvs == ubs.size() &&
"expected as many upper bounds as ivs");
219 for (
int ivIdx = 0, e = nIvs; ivIdx < e; ++ivIdx) {
224 llvm_unreachable(
"Unexpected FlatAffineValueConstraints creation error");
229 llvm_unreachable(
"Unexpected FlatAffineValueConstraints creation error");
235 unsigned numReservedEqualities,
236 unsigned newNumReservedCols,
238 unsigned newNumSymbols,
239 unsigned newNumLocals) {
240 assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 &&
243 numReservedEqualities, newNumReservedCols,
244 newNumDims, newNumSymbols, newNumLocals);
248 unsigned newNumSymbols,
249 unsigned newNumLocals) {
251 newNumDims + newNumSymbols + newNumLocals + 1,
252 newNumDims, newNumSymbols, newNumLocals);
256 unsigned numReservedInequalities,
unsigned numReservedEqualities,
257 unsigned newNumReservedCols,
unsigned newNumDims,
unsigned newNumSymbols,
259 assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 &&
262 if (!valArgs.empty())
263 newVals.assign(valArgs.begin(), valArgs.end());
266 numReservedInequalities, numReservedEqualities, newNumReservedCols,
267 newNumDims, newNumSymbols, newNumLocals, newVals);
271 unsigned newNumSymbols,
272 unsigned newNumLocals,
274 reset(0, 0, newNumDims + newNumSymbols + newNumLocals + 1, newNumDims,
275 newNumSymbols, newNumLocals, valArgs);
280 return insertVar(VarKind::SetDim, pos, vals);
285 return insertVar(VarKind::Symbol, pos, vals);
290 return insertVar(VarKind::SetDim, pos, vals);
295 return insertVar(VarKind::Symbol, pos, vals);
300 unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
302 if (kind != VarKind::Local) {
303 values.insert(
values.begin() + absolutePos, num, std::nullopt);
312 assert(!vals.empty() &&
"expected ValueRange with Values.");
313 assert(kind != VarKind::Local &&
314 "values cannot be attached to local variables.");
315 unsigned num = vals.size();
316 unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
319 for (
unsigned i = 0; i < num; ++i)
321 vals[i] ? std::optional<Value>(vals[i]) : std::nullopt);
329 values, [](
const std::optional<Value> &var) {
return var.has_value(); });
355 "Start position out of bounds");
364 for (std::optional<Value> val : maybeValues) {
365 if (val && !uniqueVars.insert(*val).second)
372 static bool LLVM_ATTRIBUTE_UNUSED
379 static bool LLVM_ATTRIBUTE_UNUSED
382 if (kind == VarKind::SetDim)
384 if (kind == VarKind::Symbol)
387 llvm_unreachable(
"Unexpected VarKind");
401 assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
408 [](
const std::optional<Value> &var) { return var.has_value(); }));
412 [](
const std::optional<Value> &var) { return var.has_value(); }));
420 for (
auto aDimValue : aDimValues) {
422 if (b->
findVar(aDimValue, &loc)) {
423 assert(loc >= offset &&
"A's dim appears in B's aligned range");
424 assert(loc < b->getNumDimVars() &&
425 "A's dim appears in B's non-dim position");
437 "expected same number of dims");
467 std::vector<SmallVector<int64_t, 8>> flatExprs;
481 for (
unsigned r = 0, e = flatExprs.size(); r < e; r++) {
482 const auto &flatExpr = flatExprs[r];
490 for (
unsigned i = 0, f = other.
getNumInputs(); i < f; i++) {
492 eqToAdd[e + i] = -flatExpr[i];
496 unsigned end = flatExpr.size() - 1;
498 eqToAdd[
j] = -flatExpr[i];
502 eqToAdd[
getNumCols() - 1] = -flatExpr[flatExpr.size() - 1];
515 pos < cst->getNumDimAndSymbolVars()) {
528 assert(
areVarsUnique(*
this, VarKind::Symbol) &&
"Symbol vars are not unique");
529 assert(
areVarsUnique(other, VarKind::Symbol) &&
"Symbol vars are not unique");
536 for (
Value aSymValue : aSymValues) {
555 "expected same number of symbols");
556 assert(
areVarsUnique(*
this, VarKind::Symbol) &&
"Symbol vars are not unique");
557 assert(
areVarsUnique(other, VarKind::Symbol) &&
"Symbol vars are not unique");
569 for (
auto iv : loopIVs) {
580 "non-terminal symbol / loop IV expected");
586 loop.emitWarning(
"failed to add domain info to constraint system"));
593 addBound(BoundType::EQ, val, constOp.value());
600 if (!
findVar(forOp.getInductionVar(), &pos)) {
601 assert(
false &&
"Value not found");
605 int64_t step = forOp.getStep();
607 if (!forOp.hasConstantLowerBound())
608 LLVM_DEBUG(forOp.emitWarning(
"domain conservatively approximated"));
616 int64_t lb = forOp.getConstantLowerBound();
618 dividend.back() -= lb;
630 if (forOp.hasConstantLowerBound()) {
631 addBound(BoundType::LB, pos, forOp.getConstantLowerBound());
635 forOp.getLowerBoundOperands())))
639 if (forOp.hasConstantUpperBound()) {
640 addBound(BoundType::UB, pos, forOp.getConstantUpperBound() - 1);
644 return addBound(BoundType::UB, pos, forOp.getUpperBoundMap(),
645 forOp.getUpperBoundOperands());
649 AffineParallelOp parallelOp) {
651 for (
auto iv : parallelOp.getIVs()) {
654 assert(
false &&
"variable expected for the IV value");
658 AffineMap lowerBound = parallelOp.getLowerBoundMap(ivPos);
662 parallelOp.getLowerBoundsOperands())))
665 auto upperBound = parallelOp.getUpperBoundMap(ivPos);
666 if (upperBound.isConstant())
667 addBound(BoundType::UB, pos, upperBound.getSingleConstantResult());
669 parallelOp.getUpperBoundsOperands())))
679 assert(lbMaps.size() == ubMaps.size());
682 for (
unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
685 assert(!lbMap || lbMap.
getNumInputs() == operands.size());
686 assert(!ubMap || ubMap.
getNumInputs() == operands.size());
743 return IntegerPolyhedron::hasConsistentState() &&
749 IntegerPolyhedron::removeVarRange(kind, varStart, varLimit);
752 if (kind != VarKind::Local) {
754 values.begin() + varLimit + offset);
779 int64_t lbConst, int64_t ubConst,
782 assert(pos < cst.
getNumVars() &&
"invalid position");
786 if (lbConst != 0 || ubConst < 1)
788 int64_t divisor = ubConst + 1;
792 curEquality < numEqualities; curEquality++) {
793 int64_t coefficientAtPos = cst.
atEq64(curEquality, pos);
796 if (coefficientAtPos == 0)
812 unsigned quotientCount = 0;
813 int quotientPosition = -1;
814 int quotientSign = 1;
822 int64_t coefficientOfCurVar = cst.
atEq64(curEquality, curVar);
824 if (coefficientOfCurVar == 0)
827 if (coefficientOfCurVar % (divisor * coefficientAtPos) == 0) {
829 quotientPosition = curVar;
830 quotientSign = (coefficientOfCurVar * coefficientAtPos) > 0 ? 1 : -1;
837 dividendExpr = dividendExpr + memo[curVar] * coefficientOfCurVar;
845 if (coefficientAtPos > 0)
846 dividendExpr = (-dividendExpr).
floorDiv(coefficientAtPos);
848 dividendExpr = dividendExpr.floorDiv(-coefficientAtPos);
862 if (quotientCount >= 1) {
864 FlatAffineValueConstraints::BoundType::UB, dimExpr.getPosition());
867 if (ub && *ub < divisor)
870 memo[pos] = dimExpr % divisor;
873 if (quotientCount == 1 && !memo[quotientPosition])
874 memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;
892 assert(pos < cst.
getNumVars() &&
"invalid position");
896 for (
unsigned i = 0, e = cst.
getNumVars(); i < e; ++i)
905 if (ulPair.kind ==
ReprKind::None || ulPair.kind == ReprKind::Equality)
910 for (
unsigned c = 0, f = cst.
getNumVars(); c < f; c++)
911 if (dividend[c] != 0)
912 dividendExpr = dividendExpr + dividend[c] * exprs[c];
915 exprs[pos] = dividendExpr.floorDiv(divisor);
919 std::pair<AffineMap, AffineMap>
921 unsigned pos,
unsigned offset,
unsigned num,
unsigned symStartPos,
923 assert(pos + offset <
getNumDimVars() &&
"invalid dim start pos");
924 assert(symStartPos >= (pos + offset) &&
"invalid sym start pos");
926 "incorrect local exprs count");
935 for (
unsigned i = 0, e = a.size(); i < e; ++i) {
936 if (i < offset || i >= offset + num)
943 unsigned dimCount = symStartPos - num;
945 lbExprs.reserve(lbIndices.size() + eqIndices.size());
947 for (
auto idx : lbIndices) {
953 std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
957 int64_t divisor =
std::abs(ineq[pos + offset]);
958 expr = (expr + divisor - 1).
floorDiv(divisor);
959 lbExprs.push_back(expr);
963 ubExprs.reserve(ubIndices.size() + eqIndices.size());
965 for (
auto idx : ubIndices) {
971 expr = expr.floorDiv(
std::abs(ineq[pos + offset]));
973 ubExprs.push_back(expr + 1);
978 for (
auto idx : eqIndices) {
981 if (eq[pos + offset] > 0)
982 std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());
987 expr = expr.floorDiv(
std::abs(eq[pos + offset]));
989 ubExprs.push_back(expr + 1);
993 expr = expr.ceilDiv(
std::abs(eq[pos + offset]));
994 lbExprs.push_back(expr);
997 auto lbMap =
AffineMap::get(dimCount, symCount, lbExprs, context);
998 auto ubMap =
AffineMap::get(dimCount, symCount, ubExprs, context);
1000 return {lbMap, ubMap};
1009 unsigned offset,
unsigned num,
MLIRContext *context,
1017 LLVM_DEBUG(llvm::dbgs() <<
"getSliceBounds for first " << num
1027 else if (i >= offset + num)
1038 for (
unsigned pos = 0; pos <
getNumVars(); pos++) {
1044 if (lbConst.has_value() && ubConst.has_value()) {
1046 if (*lbConst == *ubConst) {
1054 if (
detectAsMod(*
this, pos, *lbConst, *ubConst, memo, context)) {
1085 expr = expr + memo[
j] * c;
1094 int64_t vPos =
atEq64(idx, pos);
1095 assert(vPos != 0 &&
"expected non-zero here");
1100 expr = expr.floorDiv(-vPos);
1110 int64_t ubAdjustment = getClosedUB ? 0 : 1;
1115 std::optional<FlatAffineValueConstraints> tmpClone;
1116 for (
unsigned pos = 0; pos < num; pos++) {
1128 ubMap =
AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
1139 tmpClone->removeRedundantInequalities();
1141 std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
1151 LLVM_DEBUG(llvm::dbgs()
1152 <<
"WARNING: Potentially over-approximating slice lb\n");
1154 if (lbConst.has_value()) {
1160 LLVM_DEBUG(llvm::dbgs()
1161 <<
"WARNING: Potentially over-approximating slice ub\n");
1163 if (ubConst.has_value()) {
1165 numMapDims, numMapSymbols,
1170 LLVM_DEBUG(llvm::dbgs()
1171 <<
"lb map for pos = " << Twine(pos + offset) <<
", expr: ");
1172 LLVM_DEBUG(lbMap.
dump(););
1173 LLVM_DEBUG(llvm::dbgs()
1174 <<
"ub map for pos = " << Twine(pos + offset) <<
", expr: ");
1175 LLVM_DEBUG(ubMap.
dump(););
1183 LLVM_DEBUG(llvm::dbgs()
1184 <<
"composition unimplemented for semi-affine maps\n");
1205 bool isClosedBound) {
1209 assert((type != BoundType::EQ || isClosedBound) &&
1210 "EQ bound must be closed.");
1214 assert((type != BoundType::EQ || boundMap.
getNumResults() == 1) &&
1215 "single result expected");
1216 bool lower = type == BoundType::LB || type == BoundType::EQ;
1218 std::vector<SmallVector<int64_t, 8>> flatExprs;
1224 for (
const auto &flatExpr : flatExprs) {
1228 ineq[
j] = lower ? -flatExpr[
j] : flatExpr[
j];
1235 ineq[pos] = lower ? 1 : -1;
1238 unsigned end = flatExpr.size() - 1;
1239 for (
unsigned i = boundMap.
getNumInputs(); i < end; i++,
j++) {
1240 ineq[
j] = lower ? -flatExpr[i] : flatExpr[i];
1244 int64_t boundAdjustment = (isClosedBound || type == BoundType::EQ) ? 0 : -1;
1246 ineq[
getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
1247 : flatExpr[flatExpr.size() - 1]) +
1257 return addBound(type, pos, boundMap, type != BoundType::UB);
1263 assert(map.
getNumInputs() == operands.size() &&
"number of inputs mismatch");
1287 assert(syms.size() == newSymsPtr->size() &&
"unexpected new/missing symbols");
1288 assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
1289 "unexpected new/missing symbols");
1298 auto map = boundMap;
1303 for (
auto operand : operands)
1320 assert(
values.size() == lbMaps.size());
1321 assert(lbMaps.size() == ubMaps.size());
1323 for (
unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
1330 assert(!lbMap || lbMap.
getNumInputs() == operands.size());
1331 assert(!ubMap || ubMap.
getNumInputs() == operands.size());
1362 for (
const auto &mayBeVar :
values) {
1363 if (mayBeVar && *mayBeVar == val) {
1373 return llvm::any_of(
values, [&](
const std::optional<Value> &mayBeVar) {
1374 return mayBeVar && *mayBeVar == val;
1379 IntegerPolyhedron::swapVar(posA, posB);
1387 values[posB] = std::nullopt;
1389 values[posA] = std::nullopt;
1399 assert(0 &&
"var not found");
1422 if (
auto *otherValueSet =
1423 dyn_cast<const FlatAffineValueConstraints>(&other)) {
1424 *
this = *otherValueSet;
1433 unsigned pos,
bool darkShadow,
bool *isResultIntegerExact) {
1436 newVals.erase(newVals.begin() + pos);
1438 IntegerPolyhedron::fourierMotzkinEliminate(pos, darkShadow,
1439 isResultIntegerExact);
1446 bool ret =
findVar(val, &pos);
1458 "dim values mismatch");
1459 assert(otherCst.
getNumLocalVars() == 0 &&
"local vars not supported here");
1460 assert(
getNumLocalVars() == 0 &&
"local vars not supported yet here");
1466 return IntegerPolyhedron::unionBoundingBox(otherCopy);
1469 return IntegerPolyhedron::unionBoundingBox(otherCst);
1482 for (
unsigned i = 0; i < numDims; i++)
1484 for (
unsigned i = numDims, e = numDims + numSyms; i < e; i++)
1494 if (!memo[numDims + numSyms + i] &&
1502 llvm::all_of(localExprs, [](
AffineExpr expr) {
return expr; }));
1511 assert(pos < numDims &&
"invalid position");
1518 "one or more local exprs do not have an explicit representation");
1526 bound.append(inequality.begin(), inequality.begin() + pos);
1527 bound.append(inequality.begin() + pos + 1, inequality.end());
1529 if (inequality[pos] > 0)
1531 std::transform(bound.begin(), bound.end(), bound.begin(),
1532 std::negate<int64_t>());
1539 localExprs, context);
1546 operands.append(trailingOperands.begin(), trailingOperands.end());
1566 for (
unsigned i = numDimsSymbols, e =
getNumVars(); i < e; ++i) {
1568 noLocalRepVars.push_back(i - numDimsSymbols);
1570 if (!noLocalRepVars.empty()) {
1572 llvm::dbgs() <<
"local variables at position(s) ";
1573 llvm::interleaveComma(noLocalRepVars, llvm::dbgs());
1574 llvm::dbgs() <<
" do not have an explicit representation in:\n";
1597 numSyms, localExprs, context));
1600 numSyms, localExprs, context));
1608 "expected same number of operands and map inputs");
1612 unsigned numSymbols = syms.size();
1616 newSyms->append(syms.begin(), syms.end());
1622 auto dimIt = std::find(dims.begin(), dims.end(), operand.value());
1623 auto symIt = std::find(syms.begin(), syms.end(), operand.value());
1624 if (dimIt != dims.end()) {
1627 }
else if (symIt != syms.end()) {
1635 newSyms->push_back(operand.value());
1639 dimReplacements[operand.index()] = replacement;
1641 symReplacements[operand.index() - map.
getNumDims()] = replacement;
1646 dims.size(), numSymbols);
1666 "Domain of this and range of other do not match");
1669 "Domain of this and range of other do not match");
1705 if (relMaybeValues[i].has_value())
1710 if (thisMaybeValues[rangeIdx].has_value())
1711 rel.
setValue(rangeIdx, *thisMaybeValues[rangeIdx]);
1727 for (
unsigned i = 0; i < oldDomain; ++i)
1728 swapVar(i, oldDomain + oldRange + i);
1738 "Var cannot be inserted at invalid position");
1745 "Var cannot be inserted at invalid position");
1761 unsigned varLimit) {
1763 if (varStart >= varLimit)
1769 if (kind != VarKind::SetDim)
1775 unsigned intersectDomainRHS = varStart;
1779 if (intersectDomainLHS > intersectDomainRHS)
1781 if (intersectRangeLHS > intersectRangeRHS)
1788 std::vector<SmallVector<int64_t, 8>> flatExprs;
1805 std::fill(eq.begin(), eq.end(), 0);
1807 for (
unsigned j = 0, f = oldDimNum;
j < f; ++
j)
1808 eq[
j] = flatExprs[i][
j];
1809 for (
unsigned j = oldDimNum, f = oldCols;
j < f; ++
j)
1810 eq[
j + numRangeVars] = flatExprs[i][
j];
1812 eq[numDomainVars + i] = -1;
1842 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
1850 "AffineMap cannot produce divs without local representation");
1854 for (
unsigned i = 0, e = flattenedExprs.size(); i < e; ++i)
1855 for (
unsigned j = 0, f = flattenedExprs[i].size();
j < f; ++
j)
1856 mat(i,
j) = flattenedExprs[i][
j];
static bool areVarsAligned(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...
static void turnSymbolIntoDim(FlatAffineValueConstraints *cst, Value value)
static bool detectAsMod(const FlatAffineValueConstraints &cst, unsigned pos, int64_t lbConst, int64_t ubConst, SmallVectorImpl< AffineExpr > &memo, MLIRContext *context)
static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique(const FlatAffineValueConstraints &cst, unsigned start, unsigned end)
Checks if the SSA values associated with cst's variables in range [start, end) are unique.
static LogicalResult getFlattenedAffineExprs(ArrayRef< AffineExpr > exprs, unsigned numDims, unsigned numSymbols, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatAffineValueConstraints *localVarCst)
static bool detectAsFloorDiv(const FlatAffineValueConstraints &cst, unsigned pos, MLIRContext *context, SmallVectorImpl< AffineExpr > &exprs)
Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables ...
static void mergeAndAlignVars(unsigned offset, FlatAffineValueConstraints *a, FlatAffineValueConstraints *b)
Merge and align the variables of A and B starting at 'offset', so that both constraint systems get th...
static LogicalResult computeLocalVars(const FlatAffineValueConstraints &cst, SmallVectorImpl< AffineExpr > &memo, MLIRContext *context)
Compute an explicit representation for local vars.
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
An integer constant appearing in affine expression.
A dimensional identifier appearing in an affine expression.
unsigned getPosition() const
Base type for affine expression.
constexpr bool isa() const
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.
MLIRContext * getContext() const
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 getNumSymbols() const
unsigned getNumDims() const
ArrayRef< AffineExpr > getResults() const
unsigned getNumResults() const
AffineMap replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements, unsigned numResultDims, unsigned numResultSyms) const
This method substitutes any uses of dimensions and symbols (e.g.
unsigned getNumInputs() const
AffineExpr getResult(unsigned idx) const
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={})
This class is a general helper class for creating context-global objects like types,...
AffineExpr getAffineSymbolExpr(unsigned position)
AffineExpr getAffineDimExpr(unsigned position)
A FlatAffineRelation represents a set of ordered pairs (domain -> range) where "domain" and "range" a...
unsigned getNumRangeDims() const
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)
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 represents an extension of IntegerPolyhedron where each non-local variable...
void clearAndCopyFrom(const IntegerRelation &other) override
Replaces the contents of this FlatAffineValueConstraints with other.
unsigned appendLocalVar(unsigned num=1)
void swapVar(unsigned posA, unsigned posB) override
Swap the posA^th variable with the posB^th variable.
void addInductionVarOrTerminalSymbol(Value val)
Add the specified values as a dim or symbol var depending on its nature, if it already doesn't exist ...
unsigned insertSymbolVar(unsigned pos, unsigned num=1)
void addAffineIfOpDomain(AffineIfOp ifOp)
Adds constraints imposed by the affine.if operation.
LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
void fourierMotzkinEliminate(unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr) override
Eliminates the variable at the specified position using Fourier-Motzkin variable elimination,...
bool hasConsistentState() const override
Returns false if the fields corresponding to various variable counts, or equality/inequality buffer s...
bool hasValues() const
Returns true if at least one variable has an associated Value.
unsigned insertVar(presburger::VarKind kind, unsigned pos, unsigned num=1) override
Insert num variables of the specified kind at position pos.
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th variable.
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 ...
unsigned insertLocalVar(unsigned pos, unsigned num=1)
ArrayRef< std::optional< Value > > getMaybeValues() const
std::unique_ptr< FlatAffineValueConstraints > clone() const
Clones this object.
LogicalResult addAffineParallelOpDomain(AffineParallelOp parallelOp)
Add constraints (lower and upper bounds) for the specified 'affine.parallel' operation's Value using ...
bool hasValue(unsigned pos) const
Returns true if the pos^th variable has an associated Value.
void setValue(unsigned pos, Value val)
Sets the Value associated with the pos^th variable.
AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const
Align map with this constraint system based on operands.
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
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 variable treating [0, offset) U [offset + num,...
void projectOut(Value val)
Projects out the variable that is associate with Value.
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR i...
void mergeAndAlignVarsWithOther(unsigned offset, FlatAffineValueConstraints *other)
Merge and align the variables of this and other starting at offset, so that both constraint systems g...
SmallVector< std::optional< Value >, 8 > values
Values corresponding to the (column) non-local variables of this constraint system appearing in the o...
unsigned appendDimVar(ValueRange vals)
Append variables of the specified kind after the last variable of that kind.
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 ...
void mergeSymbolVars(FlatAffineValueConstraints &other)
Merge and align symbols of this and other such that both get union of of symbols that are unique.
void getValues(unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
Returns the Values associated with variables in range [start, end).
bool findVar(Value val, unsigned *pos) const
Looks up the position of the variable with the specified Value.
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 printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatAffineConstraints.
bool areVarsAlignedWithOther(const FlatAffineValueConstraints &other)
Returns true if this constraint system and other are in the same space, i.e., if they are associated ...
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...
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 variables (starting at offset) as an...
unsigned insertDimVar(unsigned pos, unsigned num=1)
Insert variables of the specified kind at position pos.
static FlatAffineValueConstraints getHyperrectangular(ValueRange ivs, ValueRange lbs, ValueRange ubs)
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...
FlatAffineValueConstraints(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< std::optional< Value >> valArgs={})
Constructs a constraint system reserving memory for the specified number of constraints and variables...
LogicalResult composeMatchingMap(AffineMap other)
Composes an affine map whose dimensions and symbols match one to one with the dimensions and symbols ...
bool containsVar(Value val) const
Returns true if an variable with the specified Value exists, false otherwise.
unsigned appendSymbolVar(ValueRange vals)
LogicalResult flattenAlignedMapAndMergeLocals(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs)
Given an affine map that is aligned with this constraint system:
LogicalResult unionBoundingBox(const FlatAffineValueConstraints &other)
Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this ...
An integer set representing a conjunction of one or more affine equalities and inequalities.
unsigned getNumDims() const
static IntegerSet get(unsigned dimCount, unsigned symbolCount, ArrayRef< AffineExpr > constraints, ArrayRef< bool > eqFlags)
unsigned getNumInputs() const
unsigned getNumConstraints() const
ArrayRef< AffineExpr > getConstraints() const
ArrayRef< bool > getEqFlags() const
Returns the equality bits, which specify whether each of the constraints is an equality or inequality...
unsigned getNumSymbols() const
MLIRContext is the top-level object for a collection of MLIR operations.
virtual void addLocalFloorDivId(ArrayRef< int64_t > dividend, int64_t divisor, AffineExpr localExpr)
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.
Specialization of arith.constant op that returns an integer of index type.
Class storing division representation of local variables of a constraint system.
unsigned getNumDivs() const
An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affin...
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
int64_t atEq64(unsigned i, unsigned j) const
The same, but casts to int64_t.
unsigned getVarKindEnd(VarKind kind) const
Return the index at Which the specified kind of vars ends.
void addInequality(ArrayRef< MPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
void addEquality(ArrayRef< MPInt > eq)
Adds an equality from the coefficients specified in eq.
void normalizeConstraintsByGCD()
Normalized each constraints by the GCD of its coefficients.
SmallVector< int64_t, 8 > getEquality64(unsigned idx) const
The same, but casts to int64_t.
unsigned getNumSymbolVars() const
std::optional< int64_t > getConstantBound64(BoundType type, unsigned pos) const
The same, but casts to int64_t.
unsigned getNumVarKind(VarKind kind) const
Get the number of vars of the specified kind.
VarKind getVarKindAt(unsigned pos) const
Return the VarKind of the var at the specified position.
void convertToLocal(VarKind kind, unsigned varStart, unsigned varLimit)
void addLocalFloorDiv(ArrayRef< MPInt > dividend, const MPInt &divisor)
Adds a new local variable as the floordiv of an affine function of other variables,...
unsigned getNumVars() const
void append(const IntegerRelation &other)
Appends constraints from other into this.
void setDimSymbolSeparation(unsigned newSymbolCount)
Changes the partition between dimensions and symbols.
unsigned getNumLocalVars() const
unsigned getNumDimAndSymbolVars() const
unsigned getNumCols() const
Returns the number of columns in the constraint system.
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 variable at pos, and optionally any equalities ...
BoundType
The type of bound: equal, lower bound or upper bound.
DivisionRepr getLocalReprs(std::vector< MaybeLocalRepr > *repr=nullptr) const
Returns a DivisonRepr representing the division representation of local variables in the constraint s...
void removeRedundantLocalVars()
Removes local variables using equalities.
unsigned mergeLocalVars(IntegerRelation &other)
Adds additional local vars to the sets such that they both have the union of the local vars in each s...
unsigned getNumConstraints() const
unsigned getNumInequalities() const
SmallVector< int64_t, 8 > getInequality64(unsigned idx) 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...
unsigned getNumEqualities() const
bool isColZero(unsigned pos) const
Returns true if the pos^th column is all zero for both inequalities and equalities.
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of vars starts.
unsigned getNumDimVars() const
This is a class to represent a resizable matrix.
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain...
PresburgerSpace is the space of all possible values of a tuple of integer valued variables/variables.
static PresburgerSpace getSetSpace(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)
static void printSpace(std::ostream &os, int count)
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt abs(const MPInt &x)
MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst, ArrayRef< bool > foundRepr, unsigned pos, MutableArrayRef< MPInt > dividend, MPInt &divisor)
Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed...
Include the generated interface declarations.
AffineMap simplifyAffineMap(AffineMap map)
Simplifies an affine map by simplifying its underlying AffineExpr results.
void canonicalizeSetAndOperands(IntegerSet *set, SmallVectorImpl< Value > *operands)
Canonicalizes an integer set the same way canonicalizeMapAndOperands does for affine maps.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
int64_t floorDiv(int64_t lhs, int64_t rhs)
Returns the result of MLIR's floordiv operation on constants.
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 ...
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
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.
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, FlatAffineValueConstraints *cst=nullptr)
Flattens the result expressions of the map to their corresponding flattened forms and set in 'flatten...
bool isTopLevelValue(Value value)
TODO: These should be renamed if they are on the mlir namespace.
AffineExpr getAffineConstantExpr(int64_t constant, 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...
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,...
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
bool isAffineForInductionVar(Value val)
Returns true if the provided value is the induction variable of an AffineForOp.
void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Modifies both map and operands in-place so as to:
AffineExpr getAffineDimExpr(unsigned position, MLIRContext *context)
These free functions allow clients of the API to not use classes in detail.
LogicalResult getMultiAffineFunctionFromMap(AffineMap map, presburger::MultiAffineFunction &multiAff)
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
AffineExpr getAffineSymbolExpr(unsigned position, MLIRContext *context)
This class represents an efficient way to signal success or failure.
bool failed() const
Returns true if the provided LogicalResult corresponds to a failure value.
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.