18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/InterleavedRange.h"
22 #include "llvm/Support/raw_ostream.h"
25 #define DEBUG_TYPE "flat-value-constraints"
28 using namespace presburger;
48 AffineExprFlattener(
unsigned nDims,
unsigned nSymbols)
80 struct SemiAffineExprFlattener :
public AffineExprFlattener {
81 using AffineExprFlattener::AffineExprFlattener;
88 assert(succeeded(result) &&
89 "unexpected failure in SimpleAffineExprFlattener");
110 bSubR.insert(bSubR.begin() + rPos, -1);
139 bool addConservativeSemiAffineBounds =
false) {
146 auto flattenExprs = [&](AffineExprFlattener &flattener) -> LogicalResult {
149 for (
auto expr : exprs) {
150 auto flattenResult = flattener.walkPostOrder(expr);
151 if (failed(flattenResult))
155 assert(flattener.operandExprStack.size() == exprs.size());
156 flattenedExprs->clear();
157 flattenedExprs->assign(flattener.operandExprStack.begin(),
158 flattener.operandExprStack.end());
166 if (addConservativeSemiAffineBounds) {
167 SemiAffineExprFlattener flattener(numDims, numSymbols);
168 return flattenExprs(flattener);
171 AffineExprFlattener flattener(numDims, numSymbols);
172 return flattenExprs(flattener);
178 AffineExpr expr,
unsigned numDims,
unsigned numSymbols,
180 bool addConservativeSemiAffineBounds) {
181 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
184 localVarCst, addConservativeSemiAffineBounds);
185 *flattenedExpr = flattenedExprs[0];
202 localVarCst, addConservativeSemiAffineBounds);
227 assert(other.
getNumDims() == getNumDimVars() &&
"dim mismatch");
228 assert(other.
getNumSymbols() == getNumSymbolVars() &&
"symbol mismatch");
230 std::vector<SmallVector<int64_t, 8>> flatExprs;
231 if (failed(flattenAlignedMapAndMergeLocals(other, &flatExprs)))
244 for (
unsigned r = 0, e = flatExprs.size(); r < e; r++) {
245 const auto &flatExpr = flatExprs[r];
253 for (
unsigned i = 0, f = other.
getNumInputs(); i < f; i++) {
255 eqToAdd[e + i] = -flatExpr[i];
258 unsigned j = getNumDimVars() + getNumSymbolVars();
259 unsigned end = flatExpr.size() - 1;
261 eqToAdd[
j] = -flatExpr[i];
265 eqToAdd[getNumCols() - 1] = -flatExpr[flatExpr.size() - 1];
268 addEquality(eqToAdd);
302 unsigned offset,
unsigned num, int64_t lbConst,
305 assert(pos < cst.
getNumVars() &&
"invalid position");
309 if (lbConst != 0 || ubConst < 1)
311 int64_t divisor = ubConst + 1;
315 curEquality < numEqualities; curEquality++) {
316 int64_t coefficientAtPos = cst.
atEq64(curEquality, pos);
319 if (coefficientAtPos == 0)
335 unsigned quotientCount = 0;
336 int quotientPosition = -1;
337 int quotientSign = 1;
345 int64_t coefficientOfCurVar = cst.
atEq64(curEquality, curVar);
347 if (coefficientOfCurVar == 0)
350 if (coefficientOfCurVar % (divisor * coefficientAtPos) == 0) {
352 quotientPosition = curVar;
353 quotientSign = (coefficientOfCurVar * coefficientAtPos) > 0 ? 1 : -1;
360 dividendExpr = dividendExpr + memo[curVar] * coefficientOfCurVar;
368 if (coefficientAtPos > 0)
369 dividendExpr = (-dividendExpr).floorDiv(coefficientAtPos);
371 dividendExpr = dividendExpr.floorDiv(-coefficientAtPos);
380 auto dimExpr = dyn_cast<AffineDimExpr>(dividendExpr);
385 if (quotientCount >= 1) {
390 unsigned dimExprPos = dimExpr.getPosition();
391 unsigned dimExprCol = dimExprPos < offset ? dimExprPos : dimExprPos + num;
395 if (ub && *ub < divisor)
398 memo[pos] = dimExpr % divisor;
401 if (quotientCount == 1 && !memo[quotientPosition])
402 memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;
420 assert(pos < cst.
getNumVars() &&
"invalid position");
424 for (
unsigned i = 0, e = cst.
getNumVars(); i < e; ++i)
438 for (
unsigned c = 0, f = cst.
getNumVars(); c < f; c++)
439 if (dividend[c] != 0)
440 dividendExpr = dividendExpr + dividend[c] * exprs[c];
443 exprs[pos] = dividendExpr.floorDiv(divisor);
448 bool fixedColWidth)
const {
449 unsigned ncols = getNumCols();
450 bool firstNonZero =
true;
451 for (
unsigned j = 0;
j < ncols;
j++) {
452 if (
j == ncols - 1) {
454 if (row[
j] == 0 && !firstNonZero) {
456 llvm::errs().indent(7);
458 llvm::errs() << ((row[
j] >= 0) ?
"+ " :
"") << row[
j] <<
' ';
461 std::string var = std::string(
"c_") + std::to_string(
j);
463 llvm::errs() <<
"+ " << var <<
' ';
464 else if (row[
j] == -1)
465 llvm::errs() <<
"- " << var <<
' ';
466 else if (row[
j] >= 2)
467 llvm::errs() <<
"+ " << row[
j] <<
'*' << var <<
' ';
468 else if (row[
j] <= -2)
469 llvm::errs() <<
"- " << -row[
j] <<
'*' << var <<
' ';
470 else if (fixedColWidth)
472 llvm::errs().indent(7);
474 firstNonZero =
false;
480 assert(hasConsistentState());
481 llvm::errs() <<
"Constraints (" << getNumDimVars() <<
" dims, "
482 << getNumSymbolVars() <<
" symbols, " << getNumLocalVars()
483 <<
" locals), (" << getNumConstraints() <<
" constraints)\n";
484 auto dumpConstraint = [&](
unsigned rowPos,
bool isEq) {
487 isEq ? getEquality64(rowPos) : getInequality64(rowPos);
489 llvm::errs() << (isEq ?
"=" :
">=") <<
" 0\n";
492 for (
unsigned i = 0, e = getNumInequalities(); i < e; i++)
493 dumpConstraint(i,
false);
494 for (
unsigned i = 0, e = getNumEqualities(); i < e; i++)
495 dumpConstraint(i,
true);
496 llvm::errs() <<
'\n';
500 unsigned pos,
unsigned offset,
unsigned num,
unsigned symStartPos,
502 bool closedUB)
const {
503 assert(pos + offset < getNumDimVars() &&
"invalid dim start pos");
504 assert(symStartPos >= (pos + offset) &&
"invalid sym start pos");
505 assert(getNumLocalVars() == localExprs.size() &&
506 "incorrect local exprs count");
509 getLowerAndUpperBoundIndices(pos + offset, &lbIndices, &ubIndices, &eqIndices,
515 for (
unsigned i = 0, e = a.size(); i < e; ++i) {
516 if (i < offset || i >= offset + num)
523 unsigned dimCount = symStartPos - num;
524 unsigned symCount = getNumDimAndSymbolVars() - symStartPos;
525 lbExprs.reserve(lbIndices.size() + eqIndices.size());
527 for (
auto idx : lbIndices) {
528 auto ineq = getInequality64(idx);
533 std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
537 int64_t divisor =
std::abs(ineq[pos + offset]);
538 expr = (expr + divisor - 1).floorDiv(divisor);
539 lbExprs.push_back(expr);
543 ubExprs.reserve(ubIndices.size() + eqIndices.size());
545 for (
auto idx : ubIndices) {
546 auto ineq = getInequality64(idx);
551 expr = expr.floorDiv(
std::abs(ineq[pos + offset]));
552 int64_t ubAdjustment = closedUB ? 0 : 1;
553 ubExprs.push_back(expr + ubAdjustment);
558 for (
auto idx : eqIndices) {
559 auto eq = getEquality64(idx);
561 if (eq[pos + offset] > 0)
562 std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());
567 expr = expr.floorDiv(
std::abs(eq[pos + offset]));
569 ubExprs.push_back(expr + 1);
573 expr = expr.ceilDiv(
std::abs(eq[pos + offset]));
574 lbExprs.push_back(expr);
577 auto lbMap =
AffineMap::get(dimCount, symCount, lbExprs, context);
578 auto ubMap =
AffineMap::get(dimCount, symCount, ubExprs, context);
580 return {lbMap, ubMap};
599 int64_t c = cst.
atEq64(idx,
j);
605 expr = expr + exprs[
j] * c;
614 int64_t vPos = cst.
atEq64(idx, pos);
615 assert(vPos != 0 &&
"expected non-zero here");
617 expr = (-expr).floorDiv(vPos);
620 expr = expr.floorDiv(-vPos);
637 else if (i >= offset + num)
649 for (
unsigned pos = 0, f = cst.
getNumVars(); pos < f; pos++) {
655 if (lbConst.has_value() && ubConst.has_value()) {
657 if (*lbConst == *ubConst) {
665 if (
detectAsMod(cst, pos, offset, num, *lbConst, *ubConst, context,
680 std::optional<unsigned> idx;
705 assert(offset + num <= getNumDimVars() &&
"invalid range");
708 normalizeConstraintsByGCD();
710 LLVM_DEBUG(llvm::dbgs() <<
"getSliceBounds for variables at positions ["
711 << offset <<
", " << offset + num <<
")\n");
712 LLVM_DEBUG(dumpPretty());
718 int64_t ubAdjustment = closedUB ? 0 : 1;
723 std::optional<FlatLinearConstraints> tmpClone;
724 for (
unsigned pos = 0; pos < num; pos++) {
725 unsigned numMapDims = getNumDimVars() - num;
726 unsigned numMapSymbols = getNumSymbolVars();
736 ubMap =
AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
741 if (getNumLocalVars() == 0) {
747 tmpClone->removeRedundantInequalities();
749 std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
750 pos, offset, num, getNumDimVars(), {}, context,
760 LLVM_DEBUG(llvm::dbgs()
761 <<
"WARNING: Potentially over-approximating slice lb\n");
762 auto lbConst = getConstantBound64(
BoundType::LB, pos + offset);
763 if (lbConst.has_value()) {
769 LLVM_DEBUG(llvm::dbgs()
770 <<
"WARNING: Potentially over-approximating slice ub\n");
771 auto ubConst = getConstantBound64(
BoundType::UB, pos + offset);
772 if (ubConst.has_value()) {
774 numMapDims, numMapSymbols,
780 LLVM_DEBUG(llvm::dbgs() <<
"Slice bounds:\n");
781 LLVM_DEBUG(llvm::dbgs() <<
"lb map for pos = " << Twine(pos + offset)
782 <<
", expr: " << lbMap <<
'\n');
783 LLVM_DEBUG(llvm::dbgs() <<
"ub map for pos = " << Twine(pos + offset)
784 <<
", expr: " << ubMap <<
'\n');
790 bool addConservativeSemiAffineBounds) {
793 addConservativeSemiAffineBounds))) {
794 LLVM_DEBUG(llvm::dbgs()
795 <<
"composition unimplemented for semi-affine maps\n");
801 unsigned numLocalVars = getNumLocalVars();
817 assert(boundMap.
getNumDims() == getNumDimVars() &&
"dim mismatch");
818 assert(boundMap.
getNumSymbols() == getNumSymbolVars() &&
"symbol mismatch");
819 assert(pos < getNumDimAndSymbolVars() &&
"invalid position");
821 "EQ bound must be closed.");
826 "single result expected");
829 std::vector<SmallVector<int64_t, 8>> flatExprs;
830 if (failed(flattenAlignedMapAndMergeLocals(
831 boundMap, &flatExprs,
832 addSemiAffineBounds == AddConservativeSemiAffineBounds::Yes)))
837 for (
const auto &flatExpr : flatExprs) {
841 ineq[
j] = lower ? -flatExpr[
j] : flatExpr[
j];
848 ineq[pos] = lower ? 1 : -1;
850 unsigned j = getNumDimVars() + getNumSymbolVars();
851 unsigned end = flatExpr.size() - 1;
852 for (
unsigned i = boundMap.
getNumInputs(); i < end; i++,
j++) {
853 ineq[
j] = lower ? -flatExpr[i] : flatExpr[i];
857 int64_t boundAdjustment = (isClosedBound || type ==
BoundType::EQ) ? 0 : -1;
859 ineq[getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
860 : flatExpr[flatExpr.size() - 1]) +
862 type ==
BoundType::EQ ? addEquality(ineq) : addInequality(ineq);
871 return addBound(type, pos, boundMap,
881 unsigned numDims = getNumDimVars();
882 unsigned numSyms = getNumSymbolVars();
885 for (
unsigned i = 0; i < numDims; i++)
887 for (
unsigned i = numDims, e = numDims + numSyms; i < e; i++)
896 for (
unsigned i = 0, e = getNumLocalVars(); i < e; ++i)
897 if (!memo[numDims + numSyms + i] &&
905 llvm::all_of(localExprs, [](
AffineExpr expr) {
return expr; }));
916 unsigned idx,
bool isEquality) {
935 expr = expr + exprs[
j] * c;
949 unsigned *minLbPos,
unsigned *minUbPos)
const {
951 assert(pos < getNumDimVars() &&
"Invalid identifier position");
955 for (
int i = getNumDimAndSymbolVars(), e = cst.size() - 1; i < e; ++i) {
956 if (whiteListCols[i] && whiteListCols[i].isSymbolicOrConstant())
966 (void)computeLocalVars(memo, context);
970 int eqPos = findEqualityToConstant(pos,
true);
973 if (eqPos != -1 && freeOfUnknownLocalVars(getEquality64(eqPos), memo)) {
975 if (lb &&
detectAsExpr(*
this, pos, eqPos, context, memo)) {
993 getLowerAndUpperBoundIndices(pos, &lbIndices, &ubIndices,
997 std::optional<int64_t> minDiff = std::nullopt;
998 unsigned minLbPosition = 0, minUbPosition = 0;
1003 for (
unsigned ubPos : ubIndices) {
1005 std::optional<AffineExpr> maybeUbExpr =
1006 getAsExpr(*
this, pos, context, memo, ubPos,
false);
1007 if (!maybeUbExpr.has_value() || !(*maybeUbExpr).isSymbolicOrConstant())
1022 assert(-atIneq64(ubPos, pos) > 0 &&
"invalid upper bound index");
1025 for (
unsigned lbPos : lbIndices) {
1028 std::optional<AffineExpr> maybeLbExpr =
1029 getAsExpr(*
this, pos, context, memo, lbPos,
false);
1030 if (!maybeLbExpr.has_value() || !(*maybeLbExpr).isSymbolicOrConstant())
1044 int64_t divisor = atIneq64(lbPos, pos);
1049 AffineExpr lbExpr = (-(*maybeLbExpr) + divisor - 1).floorDiv(divisor);
1050 assert(atIneq64(lbPos, pos) > 0 &&
"invalid lower bound index");
1056 auto constantDiff = dyn_cast<AffineConstantExpr>(difference);
1060 int64_t diffValue = constantDiff.getValue();
1062 diffValue = std::max<int64_t>(diffValue, 0);
1063 if (!minDiff || diffValue < *minDiff) {
1064 minDiff = diffValue;
1065 minLbPosition = lbPos;
1066 minUbPosition = ubPos;
1074 if (lb && minDiff) {
1080 *minLbPos = minLbPosition;
1082 *minUbPos = minUbPosition;
1088 if (getNumConstraints() == 0)
1097 if (failed(computeLocalVars(memo, context))) {
1101 unsigned numDimsSymbols = getNumDimAndSymbolVars();
1102 for (
unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
1103 if (!memo[i] && !isColZero(i))
1104 noLocalRepVars.push_back(i - numDimsSymbols);
1106 if (!noLocalRepVars.empty()) {
1108 llvm::dbgs() <<
"local variables at position(s) "
1109 << llvm::interleaved(noLocalRepVars)
1110 <<
" do not have an explicit representation in:\n";
1121 unsigned numDims = getNumDimVars();
1122 unsigned numSyms = getNumSymbolVars();
1125 std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(),
true);
1126 std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(),
false);
1129 exprs.reserve(getNumConstraints());
1131 for (
unsigned i = 0, e = getNumEqualities(); i < e; ++i)
1133 numSyms, localExprs, context));
1134 for (
unsigned i = 0, e = getNumInequalities(); i < e; ++i)
1136 numSyms, localExprs, context));
1148 set.getNumDims() + set.getNumSymbols() + 1,
1149 set.getNumDims(), set.getNumSymbols(),
1151 assert((operands.empty() || set.
getNumInputs() == operands.size()) &&
1152 "operand count mismatch");
1154 for (
unsigned i = 0, e = operands.size(); i < e; ++i)
1158 std::vector<SmallVector<int64_t, 8>> flatExprs;
1161 assert(
false &&
"flattening unimplemented for semi-affine integer sets");
1168 for (
unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
1169 const auto &flatExpr = flatExprs[i];
1183 return insertVar(VarKind::SetDim, pos, vals);
1188 return insertVar(VarKind::Symbol, pos, vals);
1193 return insertVar(VarKind::SetDim, pos, vals);
1198 return insertVar(VarKind::Symbol, pos, vals);
1203 unsigned absolutePos = IntegerPolyhedron::insertVar(
kind, pos, num);
1210 assert(!vals.empty() &&
"expected ValueRange with Values.");
1211 assert(
kind != VarKind::Local &&
1212 "values cannot be attached to local variables.");
1213 unsigned num = vals.size();
1214 unsigned absolutePos = IntegerPolyhedron::insertVar(
kind, pos, num);
1217 for (
unsigned i = 0, e = vals.size(); i < e; ++i)
1219 setValue(absolutePos + i, vals[i]);
1234 return std::equal(aMaybeValues.begin(), aMaybeValues.end(),
1235 bMaybeValues.begin(), bMaybeValues.end());
1251 "Start position out of bounds");
1260 maybeValuesAll.data() + end};
1262 for (std::optional<Value> val : maybeValues)
1263 if (val && !uniqueVars.insert(*val).second)
1270 static bool LLVM_ATTRIBUTE_UNUSED
1277 static bool LLVM_ATTRIBUTE_UNUSED
1280 if (
kind == VarKind::SetDim)
1282 if (
kind == VarKind::Symbol)
1285 llvm_unreachable(
"Unexpected VarKind");
1302 assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
1304 assert(llvm::all_of(
1306 [](
const std::optional<Value> &var) { return var.has_value(); }));
1308 assert(llvm::all_of(
1310 [](
const std::optional<Value> &var) { return var.has_value(); }));
1317 unsigned d = offset;
1318 for (
Value aDimValue : aDimValues) {
1323 if (b->
findVar(aDimValue, &loc, d)) {
1324 assert(loc >= offset &&
"A's dim appears in B's aligned range");
1325 assert(loc < b->getNumDimVars() &&
1326 "A's dim appears in B's non-dim position");
1338 "expected same number of dims");
1367 for (
Value aSymValue : aSymValues) {
1387 "expected same number of symbols");
1391 unsigned varLimit) {
1392 IntegerPolyhedron::removeVarRange(
kind, varStart, varLimit);
1398 assert(map.
getNumInputs() == operands.size() &&
"number of inputs mismatch");
1410 for (
unsigned i = 0, e =
getNumVarKind(VarKind::SetDim); i < e; ++i) {
1414 for (
unsigned i = 0, e =
getNumVarKind(VarKind::Symbol); i < e; ++i) {
1422 assert(syms.size() == newSymsPtr->size() &&
"unexpected new/missing symbols");
1423 assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
1424 "unexpected new/missing symbols");
1429 unsigned offset)
const {
1431 for (
unsigned i = offset, e = maybeValues.size(); i < e; ++i)
1432 if (maybeValues[i] && maybeValues[i].value() == val) {
1449 assert(0 &&
"var not found");
1483 bool ret =
findVar(val, &pos);
1495 assert(std::equal(maybeValues.begin(), maybeValues.begin() +
getNumDimVars(),
1496 otherMaybeValues.begin(),
1498 "dim values mismatch");
1499 assert(otherCst.
getNumLocalVars() == 0 &&
"local vars not supported here");
1500 assert(
getNumLocalVars() == 0 &&
"local vars not supported yet here");
1506 return IntegerPolyhedron::unionBoundingBox(otherCopy);
1509 return IntegerPolyhedron::unionBoundingBox(otherCst);
1520 "expected same number of operands and map inputs");
1524 unsigned numSymbols = syms.size();
1528 newSyms->append(syms.begin(), syms.end());
1534 auto dimIt = llvm::find(dims, operand.value());
1535 auto symIt = llvm::find(syms, operand.value());
1536 if (dimIt != dims.end()) {
1539 }
else if (symIt != syms.end()) {
1547 newSyms->push_back(operand.value());
1551 dimReplacements[operand.index()] = replacement;
1553 symReplacements[operand.index() - map.
getNumDims()] = replacement;
1558 dims.size(), numSymbols);
1565 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
1568 if (result.failed())
1573 "AffineMap cannot produce divs without local representation");
1578 for (
unsigned i = 0, e = flattenedExprs.size(); i < e; ++i)
1579 for (
unsigned j = 0, f = flattenedExprs[i].size();
j < f; ++
j)
1580 mat(i,
j) = flattenedExprs[i][
j];
static bool detectAsFloorDiv(const FlatLinearConstraints &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 bool detectAsMod(const FlatLinearConstraints &cst, unsigned pos, unsigned offset, unsigned num, int64_t lbConst, int64_t ubConst, MLIRContext *context, SmallVectorImpl< AffineExpr > &memo)
static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique(const FlatLinearValueConstraints &cst, unsigned start, unsigned end)
Checks if the SSA values associated with cst's variables in range [start, end) are unique.
static void computeUnknownVars(const FlatLinearConstraints &cst, MLIRContext *context, unsigned offset, unsigned num, SmallVectorImpl< AffineExpr > &memo)
Compute a representation of num identifiers starting at offset in cst as affine expressions involving...
static LogicalResult getFlattenedAffineExprs(ArrayRef< AffineExpr > exprs, unsigned numDims, unsigned numSymbols, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *localVarCst, bool addConservativeSemiAffineBounds=false)
static bool areVarsAligned(const FlatLinearValueConstraints &a, const FlatLinearValueConstraints &b)
Checks if two constraint systems are in the same space, i.e., if they are associated with the same se...
static bool detectAsExpr(const FlatLinearConstraints &cst, unsigned pos, unsigned idx, MLIRContext *context, SmallVectorImpl< AffineExpr > &exprs)
Express the pos^th identifier of cst as an affine expression in terms of other identifiers,...
static void mergeAndAlignVars(unsigned offset, FlatLinearValueConstraints *a, FlatLinearValueConstraints *b)
Merge and align the variables of A and B starting at 'offset', so that both constraint systems get th...
static std::optional< AffineExpr > getAsExpr(const FlatLinearConstraints &cst, unsigned pos, MLIRContext *context, ArrayRef< AffineExpr > exprs, unsigned idx, bool isEquality)
Given an equality or inequality (isEquality used to disambiguate) of cst at idx, traverse and sum up ...
union mlir::linalg::@1215::ArityGroupAndKind::Kind kind
Base type for affine expression.
AffineExpr floorDiv(uint64_t v) const
AffineExprKind getKind() const
Return the classification for this type.
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
MLIRContext * getContext() const
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
This class is a general helper class for creating context-global objects like types,...
AffineExpr getAffineSymbolExpr(unsigned position)
AffineExpr getAffineDimExpr(unsigned position)
FlatLinearConstraints is an extension of IntegerPolyhedron.
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
LogicalResult flattenAlignedMapAndMergeLocals(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, bool addConservativeSemiAffineBounds=false)
Given an affine map that is aligned with this constraint system:
unsigned appendLocalVar(unsigned num=1)
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatLinearConstraints.
void dumpRow(ArrayRef< int64_t > row, bool fixedColWidth=true) const
An easier to read dump of a row of the same width as the number of columns.
void dumpPretty() const
A more human-readable version of dump().
AddConservativeSemiAffineBounds
Flag to control if conservative semi-affine bounds should be added in addBound().
LogicalResult composeMatchingMap(AffineMap other)
Composes an affine map whose dimensions and symbols match one to one with the dimensions and symbols ...
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool closedUB=false)
Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an...
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound, AddConservativeSemiAffineBounds=AddConservativeSemiAffineBounds::No)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
std::pair< AffineMap, AffineMap > getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num, unsigned symStartPos, ArrayRef< AffineExpr > localExprs, MLIRContext *context, bool closedUB=false) const
Gets the lower and upper bound of the offset + posth variable treating [0, offset) U [offset + num,...
LogicalResult computeLocalVars(SmallVectorImpl< AffineExpr > &memo, MLIRContext *context) const
Compute an explicit representation for local vars.
std::optional< int64_t > getConstantBoundOnDimSize(MLIRContext *context, unsigned pos, AffineMap *lb=nullptr, AffineMap *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const
Returns a non-negative constant bound on the extent (upper bound - lower bound) of the specified vari...
FlatLinearValueConstraints represents an extension of FlatLinearConstraints where each non-local vari...
unsigned appendDimVar(unsigned num=1)
Append variables of the specified kind after the last variable of that kind.
unsigned insertDimVar(unsigned pos, ValueRange vals)
LogicalResult unionBoundingBox(const FlatLinearValueConstraints &other)
Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this ...
void mergeAndAlignVarsWithOther(unsigned offset, FlatLinearValueConstraints *other)
Merge and align the variables of this and other starting at offset, so that both constraint systems g...
SmallVector< std::optional< Value > > getMaybeValues() const
unsigned insertSymbolVar(unsigned pos, unsigned num=1)
bool hasValue(unsigned pos) const
Returns true if the pos^th variable has an associated Value.
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th variable.
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatAffineValueConstraints.
void mergeSymbolVars(FlatLinearValueConstraints &other)
Merge and align symbols of this and other such that both get union of of symbols that are unique.
void projectOut(Value val)
Projects out the variable that is associate with Value.
bool containsVar(Value val) const
Returns true if a variable with the specified Value exists, false otherwise.
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)
unsigned appendSymbolVar(unsigned num=1)
unsigned insertSymbolVar(unsigned pos, 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...
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound, AddConservativeSemiAffineBounds=AddConservativeSemiAffineBounds::No)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
bool areVarsAlignedWithOther(const FlatLinearConstraints &other)
Returns true if this constraint system and other are in the same space, i.e., if they are associated ...
AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const
Align map with this constraint system based on operands.
void getValues(unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
Returns the Values associated with variables in range [start, end).
FlatLinearValueConstraints(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...
void setValue(unsigned pos, Value val)
Sets the Value associated with the pos^th variable.
unsigned insertDimVar(unsigned pos, unsigned num=1)
Insert variables of the specified kind at position pos.
unsigned insertVar(presburger::VarKind kind, unsigned pos, unsigned num=1) override
Insert num variables of the specified kind at position pos.
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)
virtual LogicalResult addLocalIdSemiAffine(ArrayRef< int64_t > lhs, ArrayRef< int64_t > rhs, AffineExpr localExpr)
Add a local identifier (needed to flatten a mod, floordiv, ceildiv, mul expr) when the rhs is a symbo...
SimpleAffineExprFlattener(unsigned numDims, unsigned numSymbols)
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...
Class storing division representation of local variables of a constraint system.
unsigned getNumDivs() const
An Identifier stores a pointer to an object, such as a Value or an Operation.
An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affin...
virtual void swapVar(unsigned posA, unsigned posB)
Swap the posA^th variable with the posB^th variable.
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.
std::optional< unsigned > findConstraintWithNonZeroAt(unsigned colIdx, bool isEq) const
Finds a constraint with a non-zero coefficient at colIdx in equality (isEq=true) or inequality (isEq=...
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.
void addLocalFloorDiv(ArrayRef< DynamicAPInt > dividend, const DynamicAPInt &divisor)
Adds a new local variable as the floordiv of an affine function of other variables,...
unsigned getNumDomainVars() const
unsigned getNumVars() const
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.
unsigned getNumRangeVars() const
unsigned getNumLocalVars() const
unsigned getNumDimAndSymbolVars() const
unsigned getNumCols() const
Returns the number of columns in the constraint system.
DivisionRepr getLocalReprs(std::vector< MaybeLocalRepr > *repr=nullptr) const
Returns a DivisonRepr representing the division representation of local variables in the constraint s...
virtual void clearAndCopyFrom(const IntegerRelation &other)
Replaces the contents of this IntegerRelation with other.
void addInequality(ArrayRef< DynamicAPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
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...
SmallVector< int64_t, 8 > getInequality64(unsigned idx) const
unsigned getNumEqualities() const
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of vars starts.
unsigned getNumDimVars() const
virtual void fourierMotzkinEliminate(unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr)
Eliminates the variable at the specified position using Fourier-Motzkin variable elimination,...
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain...
Identifier getId(VarKind kind, unsigned pos) const
Get the identifier of pos^th variable of the specified kind.
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)
BoundType
The type of bound: equal, lower bound or upper bound.
MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst, ArrayRef< bool > foundRepr, unsigned pos, MutableArrayRef< DynamicAPInt > dividend, DynamicAPInt &divisor)
Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed...
Fraction abs(const Fraction &f)
Include the generated interface declarations.
const FrozenRewritePatternSet GreedyRewriteConfig bool * changed
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 ...
@ Mod
RHS of mod is always a constant or a symbolic expression with a positive value.
AffineExpr getAffineExprFromFlatForm(ArrayRef< int64_t > flatExprs, unsigned numDims, unsigned numSymbols, ArrayRef< AffineExpr > localExprs, MLIRContext *context)
Constructs an affine expression from a flat ArrayRef.
AffineExpr getAffineConstantExpr(int64_t constant, MLIRContext *context)
LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, SmallVectorImpl< int64_t > *flattenedExpr, FlatLinearConstraints *cst=nullptr, bool addConservativeSemiAffineBounds=false)
Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the dimensions,...
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...
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
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)
AffineExpr getAffineSymbolExpr(unsigned position, MLIRContext *context)
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.