19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/InterleavedRange.h"
24 #include "llvm/Support/raw_ostream.h"
27 #define DEBUG_TYPE "flat-value-constraints"
30 using namespace presburger;
50 AffineExprFlattener(
unsigned nDims,
unsigned nSymbols)
82 struct SemiAffineExprFlattener :
public AffineExprFlattener {
83 using AffineExprFlattener::AffineExprFlattener;
90 assert(succeeded(result) &&
91 "unexpected failure in SimpleAffineExprFlattener");
112 bSubR.insert(bSubR.begin() + rPos, -1);
141 bool addConservativeSemiAffineBounds =
false) {
148 auto flattenExprs = [&](AffineExprFlattener &flattener) -> LogicalResult {
151 for (
auto expr : exprs) {
152 auto flattenResult = flattener.walkPostOrder(expr);
153 if (failed(flattenResult))
157 assert(flattener.operandExprStack.size() == exprs.size());
158 flattenedExprs->clear();
159 flattenedExprs->assign(flattener.operandExprStack.begin(),
160 flattener.operandExprStack.end());
168 if (addConservativeSemiAffineBounds) {
169 SemiAffineExprFlattener flattener(numDims, numSymbols);
170 return flattenExprs(flattener);
173 AffineExprFlattener flattener(numDims, numSymbols);
174 return flattenExprs(flattener);
180 AffineExpr expr,
unsigned numDims,
unsigned numSymbols,
182 bool addConservativeSemiAffineBounds) {
183 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
186 localVarCst, addConservativeSemiAffineBounds);
187 *flattenedExpr = flattenedExprs[0];
204 localVarCst, addConservativeSemiAffineBounds);
229 assert(other.
getNumDims() == getNumDimVars() &&
"dim mismatch");
230 assert(other.
getNumSymbols() == getNumSymbolVars() &&
"symbol mismatch");
232 std::vector<SmallVector<int64_t, 8>> flatExprs;
233 if (failed(flattenAlignedMapAndMergeLocals(other, &flatExprs)))
246 for (
unsigned r = 0, e = flatExprs.size(); r < e; r++) {
247 const auto &flatExpr = flatExprs[r];
255 for (
unsigned i = 0, f = other.
getNumInputs(); i < f; i++) {
257 eqToAdd[e + i] = -flatExpr[i];
260 unsigned j = getNumDimVars() + getNumSymbolVars();
261 unsigned end = flatExpr.size() - 1;
263 eqToAdd[
j] = -flatExpr[i];
267 eqToAdd[getNumCols() - 1] = -flatExpr[flatExpr.size() - 1];
270 addEquality(eqToAdd);
304 unsigned offset,
unsigned num, int64_t lbConst,
307 assert(pos < cst.
getNumVars() &&
"invalid position");
311 if (lbConst != 0 || ubConst < 1)
313 int64_t divisor = ubConst + 1;
317 curEquality < numEqualities; curEquality++) {
318 int64_t coefficientAtPos = cst.
atEq64(curEquality, pos);
321 if (coefficientAtPos == 0)
337 unsigned quotientCount = 0;
338 int quotientPosition = -1;
339 int quotientSign = 1;
347 int64_t coefficientOfCurVar = cst.
atEq64(curEquality, curVar);
349 if (coefficientOfCurVar == 0)
352 if (coefficientOfCurVar % (divisor * coefficientAtPos) == 0) {
354 quotientPosition = curVar;
355 quotientSign = (coefficientOfCurVar * coefficientAtPos) > 0 ? 1 : -1;
362 dividendExpr = dividendExpr + memo[curVar] * coefficientOfCurVar;
370 if (coefficientAtPos > 0)
371 dividendExpr = (-dividendExpr).floorDiv(coefficientAtPos);
373 dividendExpr = dividendExpr.floorDiv(-coefficientAtPos);
382 auto dimExpr = dyn_cast<AffineDimExpr>(dividendExpr);
387 if (quotientCount >= 1) {
392 unsigned dimExprPos = dimExpr.getPosition();
393 unsigned dimExprCol = dimExprPos < offset ? dimExprPos : dimExprPos + num;
397 if (ub && *ub < divisor)
400 memo[pos] = dimExpr % divisor;
403 if (quotientCount == 1 && !memo[quotientPosition])
404 memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;
422 assert(pos < cst.
getNumVars() &&
"invalid position");
426 for (
unsigned i = 0, e = cst.
getNumVars(); i < e; ++i)
440 for (
unsigned c = 0, f = cst.
getNumVars(); c < f; c++)
441 if (dividend[c] != 0)
442 dividendExpr = dividendExpr + dividend[c] * exprs[c];
445 exprs[pos] = dividendExpr.floorDiv(divisor);
450 bool fixedColWidth)
const {
451 unsigned ncols = getNumCols();
452 bool firstNonZero =
true;
453 for (
unsigned j = 0;
j < ncols;
j++) {
454 if (
j == ncols - 1) {
456 if (row[
j] == 0 && !firstNonZero) {
458 llvm::errs().indent(7);
460 llvm::errs() << ((row[
j] >= 0) ?
"+ " :
"") << row[
j] <<
' ';
463 std::string var = std::string(
"c_") + std::to_string(
j);
465 llvm::errs() <<
"+ " << var <<
' ';
466 else if (row[
j] == -1)
467 llvm::errs() <<
"- " << var <<
' ';
468 else if (row[
j] >= 2)
469 llvm::errs() <<
"+ " << row[
j] <<
'*' << var <<
' ';
470 else if (row[
j] <= -2)
471 llvm::errs() <<
"- " << -row[
j] <<
'*' << var <<
' ';
472 else if (fixedColWidth)
474 llvm::errs().indent(7);
476 firstNonZero =
false;
482 assert(hasConsistentState());
483 llvm::errs() <<
"Constraints (" << getNumDimVars() <<
" dims, "
484 << getNumSymbolVars() <<
" symbols, " << getNumLocalVars()
485 <<
" locals), (" << getNumConstraints() <<
" constraints)\n";
486 auto dumpConstraint = [&](
unsigned rowPos,
bool isEq) {
489 isEq ? getEquality64(rowPos) : getInequality64(rowPos);
491 llvm::errs() << (isEq ?
"=" :
">=") <<
" 0\n";
494 for (
unsigned i = 0, e = getNumInequalities(); i < e; i++)
495 dumpConstraint(i,
false);
496 for (
unsigned i = 0, e = getNumEqualities(); i < e; i++)
497 dumpConstraint(i,
true);
498 llvm::errs() <<
'\n';
502 unsigned pos,
unsigned offset,
unsigned num,
unsigned symStartPos,
504 bool closedUB)
const {
505 assert(pos + offset < getNumDimVars() &&
"invalid dim start pos");
506 assert(symStartPos >= (pos + offset) &&
"invalid sym start pos");
507 assert(getNumLocalVars() == localExprs.size() &&
508 "incorrect local exprs count");
511 getLowerAndUpperBoundIndices(pos + offset, &lbIndices, &ubIndices, &eqIndices,
517 for (
unsigned i = 0, e = a.size(); i < e; ++i) {
518 if (i < offset || i >= offset + num)
525 unsigned dimCount = symStartPos - num;
526 unsigned symCount = getNumDimAndSymbolVars() - symStartPos;
527 lbExprs.reserve(lbIndices.size() + eqIndices.size());
529 for (
auto idx : lbIndices) {
530 auto ineq = getInequality64(idx);
535 std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
539 int64_t divisor =
std::abs(ineq[pos + offset]);
540 expr = (expr + divisor - 1).floorDiv(divisor);
541 lbExprs.push_back(expr);
545 ubExprs.reserve(ubIndices.size() + eqIndices.size());
547 for (
auto idx : ubIndices) {
548 auto ineq = getInequality64(idx);
553 expr = expr.floorDiv(
std::abs(ineq[pos + offset]));
554 int64_t ubAdjustment = closedUB ? 0 : 1;
555 ubExprs.push_back(expr + ubAdjustment);
560 for (
auto idx : eqIndices) {
561 auto eq = getEquality64(idx);
563 if (eq[pos + offset] > 0)
564 std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());
569 expr = expr.floorDiv(
std::abs(eq[pos + offset]));
571 ubExprs.push_back(expr + 1);
575 expr = expr.ceilDiv(
std::abs(eq[pos + offset]));
576 lbExprs.push_back(expr);
579 auto lbMap =
AffineMap::get(dimCount, symCount, lbExprs, context);
580 auto ubMap =
AffineMap::get(dimCount, symCount, ubExprs, context);
582 return {lbMap, ubMap};
601 int64_t c = cst.
atEq64(idx,
j);
607 expr = expr + exprs[
j] * c;
616 int64_t vPos = cst.
atEq64(idx, pos);
617 assert(vPos != 0 &&
"expected non-zero here");
619 expr = (-expr).floorDiv(vPos);
622 expr = expr.floorDiv(-vPos);
639 else if (i >= offset + num)
651 for (
unsigned pos = 0, f = cst.
getNumVars(); pos < f; pos++) {
657 if (lbConst.has_value() && ubConst.has_value()) {
659 if (*lbConst == *ubConst) {
667 if (
detectAsMod(cst, pos, offset, num, *lbConst, *ubConst, context,
682 std::optional<unsigned> idx;
707 assert(offset + num <= getNumDimVars() &&
"invalid range");
710 normalizeConstraintsByGCD();
712 LLVM_DEBUG(llvm::dbgs() <<
"getSliceBounds for variables at positions ["
713 << offset <<
", " << offset + num <<
")\n");
714 LLVM_DEBUG(dumpPretty());
720 int64_t ubAdjustment = closedUB ? 0 : 1;
725 std::optional<FlatLinearConstraints> tmpClone;
726 for (
unsigned pos = 0; pos < num; pos++) {
727 unsigned numMapDims = getNumDimVars() - num;
728 unsigned numMapSymbols = getNumSymbolVars();
738 ubMap =
AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
743 if (getNumLocalVars() == 0) {
749 tmpClone->removeRedundantInequalities();
751 std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
752 pos, offset, num, getNumDimVars(), {}, context,
762 LLVM_DEBUG(llvm::dbgs()
763 <<
"WARNING: Potentially over-approximating slice lb\n");
764 auto lbConst = getConstantBound64(
BoundType::LB, pos + offset);
765 if (lbConst.has_value()) {
771 LLVM_DEBUG(llvm::dbgs()
772 <<
"WARNING: Potentially over-approximating slice ub\n");
773 auto ubConst = getConstantBound64(
BoundType::UB, pos + offset);
774 if (ubConst.has_value()) {
776 numMapDims, numMapSymbols,
782 LLVM_DEBUG(llvm::dbgs() <<
"Slice bounds:\n");
783 LLVM_DEBUG(llvm::dbgs() <<
"lb map for pos = " << Twine(pos + offset)
784 <<
", expr: " << lbMap <<
'\n');
785 LLVM_DEBUG(llvm::dbgs() <<
"ub map for pos = " << Twine(pos + offset)
786 <<
", expr: " << ubMap <<
'\n');
792 bool addConservativeSemiAffineBounds) {
795 addConservativeSemiAffineBounds))) {
796 LLVM_DEBUG(llvm::dbgs()
797 <<
"composition unimplemented for semi-affine maps\n");
803 unsigned numLocalVars = getNumLocalVars();
819 assert(boundMap.
getNumDims() == getNumDimVars() &&
"dim mismatch");
820 assert(boundMap.
getNumSymbols() == getNumSymbolVars() &&
"symbol mismatch");
821 assert(pos < getNumDimAndSymbolVars() &&
"invalid position");
823 "EQ bound must be closed.");
828 "single result expected");
831 std::vector<SmallVector<int64_t, 8>> flatExprs;
832 if (failed(flattenAlignedMapAndMergeLocals(
833 boundMap, &flatExprs,
834 addSemiAffineBounds == AddConservativeSemiAffineBounds::Yes)))
839 for (
const auto &flatExpr : flatExprs) {
843 ineq[
j] = lower ? -flatExpr[
j] : flatExpr[
j];
850 ineq[pos] = lower ? 1 : -1;
852 unsigned j = getNumDimVars() + getNumSymbolVars();
853 unsigned end = flatExpr.size() - 1;
854 for (
unsigned i = boundMap.
getNumInputs(); i < end; i++,
j++) {
855 ineq[
j] = lower ? -flatExpr[i] : flatExpr[i];
859 int64_t boundAdjustment = (isClosedBound || type ==
BoundType::EQ) ? 0 : -1;
861 ineq[getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
862 : flatExpr[flatExpr.size() - 1]) +
864 type ==
BoundType::EQ ? addEquality(ineq) : addInequality(ineq);
873 return addBound(type, pos, boundMap,
883 unsigned numDims = getNumDimVars();
884 unsigned numSyms = getNumSymbolVars();
887 for (
unsigned i = 0; i < numDims; i++)
889 for (
unsigned i = numDims, e = numDims + numSyms; i < e; i++)
898 for (
unsigned i = 0, e = getNumLocalVars(); i < e; ++i)
899 if (!memo[numDims + numSyms + i] &&
907 llvm::all_of(localExprs, [](
AffineExpr expr) {
return expr; }));
918 unsigned idx,
bool isEquality) {
937 expr = expr + exprs[
j] * c;
951 unsigned *minLbPos,
unsigned *minUbPos)
const {
953 assert(pos < getNumDimVars() &&
"Invalid identifier position");
957 for (
int i = getNumDimAndSymbolVars(), e = cst.size() - 1; i < e; ++i) {
958 if (whiteListCols[i] && whiteListCols[i].isSymbolicOrConstant())
968 (void)computeLocalVars(memo, context);
972 int eqPos = findEqualityToConstant(pos,
true);
975 if (eqPos != -1 && freeOfUnknownLocalVars(getEquality64(eqPos), memo)) {
977 if (lb &&
detectAsExpr(*
this, pos, eqPos, context, memo)) {
995 getLowerAndUpperBoundIndices(pos, &lbIndices, &ubIndices,
999 std::optional<int64_t> minDiff = std::nullopt;
1000 unsigned minLbPosition = 0, minUbPosition = 0;
1005 for (
unsigned ubPos : ubIndices) {
1007 std::optional<AffineExpr> maybeUbExpr =
1008 getAsExpr(*
this, pos, context, memo, ubPos,
false);
1009 if (!maybeUbExpr.has_value() || !(*maybeUbExpr).isSymbolicOrConstant())
1024 assert(-atIneq64(ubPos, pos) > 0 &&
"invalid upper bound index");
1027 for (
unsigned lbPos : lbIndices) {
1030 std::optional<AffineExpr> maybeLbExpr =
1031 getAsExpr(*
this, pos, context, memo, lbPos,
false);
1032 if (!maybeLbExpr.has_value() || !(*maybeLbExpr).isSymbolicOrConstant())
1046 int64_t divisor = atIneq64(lbPos, pos);
1051 AffineExpr lbExpr = (-(*maybeLbExpr) + divisor - 1).floorDiv(divisor);
1052 assert(atIneq64(lbPos, pos) > 0 &&
"invalid lower bound index");
1058 auto constantDiff = dyn_cast<AffineConstantExpr>(difference);
1062 int64_t diffValue = constantDiff.getValue();
1064 diffValue = std::max<int64_t>(diffValue, 0);
1065 if (!minDiff || diffValue < *minDiff) {
1066 minDiff = diffValue;
1067 minLbPosition = lbPos;
1068 minUbPosition = ubPos;
1076 if (lb && minDiff) {
1082 *minLbPos = minLbPosition;
1084 *minUbPos = minUbPosition;
1090 if (getNumConstraints() == 0)
1099 if (failed(computeLocalVars(memo, context))) {
1103 unsigned numDimsSymbols = getNumDimAndSymbolVars();
1104 for (
unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
1105 if (!memo[i] && !isColZero(i))
1106 noLocalRepVars.push_back(i - numDimsSymbols);
1108 if (!noLocalRepVars.empty()) {
1110 llvm::dbgs() <<
"local variables at position(s) "
1111 << llvm::interleaved(noLocalRepVars)
1112 <<
" do not have an explicit representation in:\n";
1123 unsigned numDims = getNumDimVars();
1124 unsigned numSyms = getNumSymbolVars();
1127 std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(),
true);
1128 std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(),
false);
1131 exprs.reserve(getNumConstraints());
1133 for (
unsigned i = 0, e = getNumEqualities(); i < e; ++i)
1135 numSyms, localExprs, context));
1136 for (
unsigned i = 0, e = getNumInequalities(); i < e; ++i)
1138 numSyms, localExprs, context));
1150 set.getNumDims() + set.getNumSymbols() + 1,
1151 set.getNumDims(), set.getNumSymbols(),
1153 assert((operands.empty() || set.
getNumInputs() == operands.size()) &&
1154 "operand count mismatch");
1156 for (
unsigned i = 0, e = operands.size(); i < e; ++i)
1160 std::vector<SmallVector<int64_t, 8>> flatExprs;
1163 assert(
false &&
"flattening unimplemented for semi-affine integer sets");
1170 for (
unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
1171 const auto &flatExpr = flatExprs[i];
1185 return insertVar(VarKind::SetDim, pos, vals);
1190 return insertVar(VarKind::Symbol, pos, vals);
1195 return insertVar(VarKind::SetDim, pos, vals);
1200 return insertVar(VarKind::Symbol, pos, vals);
1205 unsigned absolutePos = IntegerPolyhedron::insertVar(
kind, pos, num);
1212 assert(!vals.empty() &&
"expected ValueRange with Values.");
1213 assert(
kind != VarKind::Local &&
1214 "values cannot be attached to local variables.");
1215 unsigned num = vals.size();
1216 unsigned absolutePos = IntegerPolyhedron::insertVar(
kind, pos, num);
1219 for (
unsigned i = 0, e = vals.size(); i < e; ++i)
1221 setValue(absolutePos + i, vals[i]);
1236 return std::equal(aMaybeValues.begin(), aMaybeValues.end(),
1237 bMaybeValues.begin(), bMaybeValues.end());
1253 "Start position out of bounds");
1262 maybeValuesAll.data() + end};
1264 for (std::optional<Value> val : maybeValues)
1265 if (val && !uniqueVars.insert(*val).second)
1272 static bool LLVM_ATTRIBUTE_UNUSED
1279 static bool LLVM_ATTRIBUTE_UNUSED
1282 if (
kind == VarKind::SetDim)
1284 if (
kind == VarKind::Symbol)
1287 llvm_unreachable(
"Unexpected VarKind");
1304 assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
1306 assert(llvm::all_of(
1308 [](
const std::optional<Value> &var) { return var.has_value(); }));
1310 assert(llvm::all_of(
1312 [](
const std::optional<Value> &var) { return var.has_value(); }));
1319 unsigned d = offset;
1320 for (
Value aDimValue : aDimValues) {
1325 if (b->
findVar(aDimValue, &loc, d)) {
1326 assert(loc >= offset &&
"A's dim appears in B's aligned range");
1327 assert(loc < b->getNumDimVars() &&
1328 "A's dim appears in B's non-dim position");
1340 "expected same number of dims");
1369 for (
Value aSymValue : aSymValues) {
1389 "expected same number of symbols");
1393 unsigned varLimit) {
1394 IntegerPolyhedron::removeVarRange(
kind, varStart, varLimit);
1400 assert(map.
getNumInputs() == operands.size() &&
"number of inputs mismatch");
1412 for (
unsigned i = 0, e =
getNumVarKind(VarKind::SetDim); i < e; ++i) {
1416 for (
unsigned i = 0, e =
getNumVarKind(VarKind::Symbol); i < e; ++i) {
1424 assert(syms.size() == newSymsPtr->size() &&
"unexpected new/missing symbols");
1425 assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
1426 "unexpected new/missing symbols");
1431 unsigned offset)
const {
1433 for (
unsigned i = offset, e = maybeValues.size(); i < e; ++i)
1434 if (maybeValues[i] && maybeValues[i].value() == val) {
1451 assert(0 &&
"var not found");
1485 bool ret =
findVar(val, &pos);
1497 assert(std::equal(maybeValues.begin(), maybeValues.begin() +
getNumDimVars(),
1498 otherMaybeValues.begin(),
1500 "dim values mismatch");
1501 assert(otherCst.
getNumLocalVars() == 0 &&
"local vars not supported here");
1502 assert(
getNumLocalVars() == 0 &&
"local vars not supported yet here");
1508 return IntegerPolyhedron::unionBoundingBox(otherCopy);
1511 return IntegerPolyhedron::unionBoundingBox(otherCst);
1522 "expected same number of operands and map inputs");
1526 unsigned numSymbols = syms.size();
1530 newSyms->append(syms.begin(), syms.end());
1536 auto dimIt = llvm::find(dims, operand.value());
1537 auto symIt = llvm::find(syms, operand.value());
1538 if (dimIt != dims.end()) {
1541 }
else if (symIt != syms.end()) {
1549 newSyms->push_back(operand.value());
1553 dimReplacements[operand.index()] = replacement;
1555 symReplacements[operand.index() - map.
getNumDims()] = replacement;
1560 dims.size(), numSymbols);
1567 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
1570 if (result.failed())
1575 "AffineMap cannot produce divs without local representation");
1580 for (
unsigned i = 0, e = flattenedExprs.size(); i < e; ++i)
1581 for (
unsigned j = 0, f = flattenedExprs[i].size();
j < f; ++
j)
1582 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::@1197::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.