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/raw_ostream.h"
26 #define DEBUG_TYPE "flat-value-constraints"
29 using namespace presburger;
48 AffineExprFlattener(
unsigned nDims,
unsigned nSymbols)
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];
155 assert(other.
getNumDims() == getNumDimVars() &&
"dim mismatch");
156 assert(other.
getNumSymbols() == getNumSymbolVars() &&
"symbol mismatch");
158 std::vector<SmallVector<int64_t, 8>> flatExprs;
159 if (
failed(flattenAlignedMapAndMergeLocals(other, &flatExprs)))
172 for (
unsigned r = 0, e = flatExprs.size(); r < e; r++) {
173 const auto &flatExpr = flatExprs[r];
181 for (
unsigned i = 0, f = other.
getNumInputs(); i < f; i++) {
183 eqToAdd[e + i] = -flatExpr[i];
186 unsigned j = getNumDimVars() + getNumSymbolVars();
187 unsigned end = flatExpr.size() - 1;
189 eqToAdd[
j] = -flatExpr[i];
193 eqToAdd[getNumCols() - 1] = -flatExpr[flatExpr.size() - 1];
196 addEquality(eqToAdd);
230 unsigned offset,
unsigned num, int64_t lbConst,
233 assert(pos < cst.
getNumVars() &&
"invalid position");
237 if (lbConst != 0 || ubConst < 1)
239 int64_t divisor = ubConst + 1;
243 curEquality < numEqualities; curEquality++) {
244 int64_t coefficientAtPos = cst.
atEq64(curEquality, pos);
247 if (coefficientAtPos == 0)
263 unsigned quotientCount = 0;
264 int quotientPosition = -1;
265 int quotientSign = 1;
273 int64_t coefficientOfCurVar = cst.
atEq64(curEquality, curVar);
275 if (coefficientOfCurVar == 0)
278 if (coefficientOfCurVar % (divisor * coefficientAtPos) == 0) {
280 quotientPosition = curVar;
281 quotientSign = (coefficientOfCurVar * coefficientAtPos) > 0 ? 1 : -1;
288 dividendExpr = dividendExpr + memo[curVar] * coefficientOfCurVar;
296 if (coefficientAtPos > 0)
297 dividendExpr = (-dividendExpr).
floorDiv(coefficientAtPos);
299 dividendExpr = dividendExpr.
floorDiv(-coefficientAtPos);
313 if (quotientCount >= 1) {
319 unsigned dimExprCol = dimExprPos < offset ? dimExprPos : dimExprPos + num;
323 if (ub && *ub < divisor)
326 memo[pos] = dimExpr % divisor;
329 if (quotientCount == 1 && !memo[quotientPosition])
330 memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;
348 assert(pos < cst.
getNumVars() &&
"invalid position");
352 for (
unsigned i = 0, e = cst.
getNumVars(); i < e; ++i)
366 for (
unsigned c = 0, f = cst.
getNumVars(); c < f; c++)
367 if (dividend[c] != 0)
368 dividendExpr = dividendExpr + dividend[c] * exprs[c];
371 exprs[pos] = dividendExpr.floorDiv(divisor);
376 unsigned pos,
unsigned offset,
unsigned num,
unsigned symStartPos,
378 bool closedUB)
const {
379 assert(pos + offset < getNumDimVars() &&
"invalid dim start pos");
380 assert(symStartPos >= (pos + offset) &&
"invalid sym start pos");
381 assert(getNumLocalVars() == localExprs.size() &&
382 "incorrect local exprs count");
385 getLowerAndUpperBoundIndices(pos + offset, &lbIndices, &ubIndices, &eqIndices,
391 for (
unsigned i = 0, e = a.size(); i < e; ++i) {
392 if (i < offset || i >= offset + num)
399 unsigned dimCount = symStartPos - num;
400 unsigned symCount = getNumDimAndSymbolVars() - symStartPos;
401 lbExprs.reserve(lbIndices.size() + eqIndices.size());
403 for (
auto idx : lbIndices) {
404 auto ineq = getInequality64(idx);
409 std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
413 int64_t divisor =
std::abs(ineq[pos + offset]);
414 expr = (expr + divisor - 1).
floorDiv(divisor);
415 lbExprs.push_back(expr);
419 ubExprs.reserve(ubIndices.size() + eqIndices.size());
421 for (
auto idx : ubIndices) {
422 auto ineq = getInequality64(idx);
427 expr = expr.floorDiv(
std::abs(ineq[pos + offset]));
428 int64_t ubAdjustment = closedUB ? 0 : 1;
429 ubExprs.push_back(expr + ubAdjustment);
434 for (
auto idx : eqIndices) {
435 auto eq = getEquality64(idx);
437 if (eq[pos + offset] > 0)
438 std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());
443 expr = expr.floorDiv(
std::abs(eq[pos + offset]));
445 ubExprs.push_back(expr + 1);
449 expr = expr.ceilDiv(
std::abs(eq[pos + offset]));
450 lbExprs.push_back(expr);
453 auto lbMap =
AffineMap::get(dimCount, symCount, lbExprs, context);
454 auto ubMap =
AffineMap::get(dimCount, symCount, ubExprs, context);
456 return {lbMap, ubMap};
469 assert(offset + num <= getNumDimVars() &&
"invalid range");
472 normalizeConstraintsByGCD();
474 LLVM_DEBUG(llvm::dbgs() <<
"getSliceBounds for first " << num
481 for (
unsigned i = 0, e = getNumDimVars(); i < e; i++) {
484 else if (i >= offset + num)
487 for (
unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++)
495 for (
unsigned pos = 0; pos < getNumVars(); pos++) {
501 if (lbConst.has_value() && ubConst.has_value()) {
503 if (*lbConst == *ubConst) {
511 if (
detectAsMod(*
this, pos, offset, num, *lbConst, *ubConst, context,
527 if (!findConstraintWithNonZeroAt(pos,
true, &idx)) {
534 for (
j = 0, e = getNumVars();
j < e; ++
j) {
537 int64_t c = atEq64(idx,
j);
543 expr = expr + memo[
j] * c;
551 expr = expr + atEq64(idx, getNumVars());
552 int64_t vPos = atEq64(idx, pos);
553 assert(vPos != 0 &&
"expected non-zero here");
568 int64_t ubAdjustment = closedUB ? 0 : 1;
573 std::optional<FlatLinearConstraints> tmpClone;
574 for (
unsigned pos = 0; pos < num; pos++) {
575 unsigned numMapDims = getNumDimVars() - num;
576 unsigned numMapSymbols = getNumSymbolVars();
586 ubMap =
AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
591 if (getNumLocalVars() == 0) {
597 tmpClone->removeRedundantInequalities();
599 std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
600 pos, offset, num, getNumDimVars(), {}, context,
610 LLVM_DEBUG(llvm::dbgs()
611 <<
"WARNING: Potentially over-approximating slice lb\n");
612 auto lbConst = getConstantBound64(
BoundType::LB, pos + offset);
613 if (lbConst.has_value()) {
619 LLVM_DEBUG(llvm::dbgs()
620 <<
"WARNING: Potentially over-approximating slice ub\n");
621 auto ubConst = getConstantBound64(
BoundType::UB, pos + offset);
622 if (ubConst.has_value()) {
624 numMapDims, numMapSymbols,
629 LLVM_DEBUG(llvm::dbgs()
630 <<
"lb map for pos = " << Twine(pos + offset) <<
", expr: ");
631 LLVM_DEBUG(lbMap.
dump(););
632 LLVM_DEBUG(llvm::dbgs()
633 <<
"ub map for pos = " << Twine(pos + offset) <<
", expr: ");
634 LLVM_DEBUG(ubMap.
dump(););
642 LLVM_DEBUG(llvm::dbgs()
643 <<
"composition unimplemented for semi-affine maps\n");
649 unsigned numLocalVars = getNumLocalVars();
664 bool isClosedBound) {
665 assert(boundMap.
getNumDims() == getNumDimVars() &&
"dim mismatch");
666 assert(boundMap.
getNumSymbols() == getNumSymbolVars() &&
"symbol mismatch");
667 assert(pos < getNumDimAndSymbolVars() &&
"invalid position");
669 "EQ bound must be closed.");
674 "single result expected");
677 std::vector<SmallVector<int64_t, 8>> flatExprs;
678 if (
failed(flattenAlignedMapAndMergeLocals(boundMap, &flatExprs)))
683 for (
const auto &flatExpr : flatExprs) {
687 ineq[
j] = lower ? -flatExpr[
j] : flatExpr[
j];
694 ineq[pos] = lower ? 1 : -1;
696 unsigned j = getNumDimVars() + getNumSymbolVars();
697 unsigned end = flatExpr.size() - 1;
698 for (
unsigned i = boundMap.
getNumInputs(); i < end; i++,
j++) {
699 ineq[
j] = lower ? -flatExpr[i] : flatExpr[i];
703 int64_t boundAdjustment = (isClosedBound || type ==
BoundType::EQ) ? 0 : -1;
705 ineq[getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
706 : flatExpr[flatExpr.size() - 1]) +
708 type ==
BoundType::EQ ? addEquality(ineq) : addInequality(ineq);
725 unsigned numDims = getNumDimVars();
726 unsigned numSyms = getNumSymbolVars();
729 for (
unsigned i = 0; i < numDims; i++)
731 for (
unsigned i = numDims, e = numDims + numSyms; i < e; i++)
740 for (
unsigned i = 0, e = getNumLocalVars(); i < e; ++i)
741 if (!memo[numDims + numSyms + i] &&
749 llvm::all_of(localExprs, [](
AffineExpr expr) {
return expr; }));
753 if (getNumConstraints() == 0)
762 if (
failed(computeLocalVars(memo, context))) {
766 unsigned numDimsSymbols = getNumDimAndSymbolVars();
767 for (
unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
768 if (!memo[i] && !isColZero(i))
769 noLocalRepVars.push_back(i - numDimsSymbols);
771 if (!noLocalRepVars.empty()) {
773 llvm::dbgs() <<
"local variables at position(s) ";
774 llvm::interleaveComma(noLocalRepVars, llvm::dbgs());
775 llvm::dbgs() <<
" do not have an explicit representation in:\n";
786 unsigned numDims = getNumDimVars();
787 unsigned numSyms = getNumSymbolVars();
790 std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(),
true);
791 std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(),
false);
794 exprs.reserve(getNumConstraints());
796 for (
unsigned i = 0, e = getNumEqualities(); i < e; ++i)
798 numSyms, localExprs, context));
799 for (
unsigned i = 0, e = getNumInequalities(); i < e; ++i)
801 numSyms, localExprs, context));
813 set.getNumDims() + set.getNumSymbols() + 1,
814 set.getNumDims(), set.getNumSymbols(),
817 if (operands.empty()) {
820 assert(set.
getNumInputs() == operands.size() &&
"operand count mismatch");
821 values.assign(operands.begin(), operands.end());
825 std::vector<SmallVector<int64_t, 8>> flatExprs;
828 assert(
false &&
"flattening unimplemented for semi-affine integer sets");
835 for (
unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
836 const auto &flatExpr = flatExprs[i];
850 return insertVar(VarKind::SetDim, pos, vals);
855 return insertVar(VarKind::Symbol, pos, vals);
860 return insertVar(VarKind::SetDim, pos, vals);
865 return insertVar(VarKind::Symbol, pos, vals);
870 unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
872 if (kind != VarKind::Local) {
873 values.insert(
values.begin() + absolutePos, num, std::nullopt);
882 assert(!vals.empty() &&
"expected ValueRange with Values.");
883 assert(kind != VarKind::Local &&
884 "values cannot be attached to local variables.");
885 unsigned num = vals.size();
886 unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
889 for (
unsigned i = 0; i < num; ++i)
891 vals[i] ? std::optional<Value>(vals[i]) : std::nullopt);
920 "Start position out of bounds");
929 for (std::optional<Value> val : maybeValues) {
930 if (val && !uniqueVars.insert(*val).second)
937 static bool LLVM_ATTRIBUTE_UNUSED
944 static bool LLVM_ATTRIBUTE_UNUSED
947 if (kind == VarKind::SetDim)
949 if (kind == VarKind::Symbol)
952 llvm_unreachable(
"Unexpected VarKind");
966 assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
973 [](
const std::optional<Value> &var) { return var.has_value(); }));
977 [](
const std::optional<Value> &var) { return var.has_value(); }));
985 for (
auto aDimValue : aDimValues) {
987 if (b->
findVar(aDimValue, &loc)) {
988 assert(loc >= offset &&
"A's dim appears in B's aligned range");
989 assert(loc < b->getNumDimVars() &&
990 "A's dim appears in B's non-dim position");
1002 "expected same number of dims");
1026 assert(
areVarsUnique(*
this, VarKind::Symbol) &&
"Symbol vars are not unique");
1027 assert(
areVarsUnique(other, VarKind::Symbol) &&
"Symbol vars are not unique");
1034 for (
Value aSymValue : aSymValues) {
1053 "expected same number of symbols");
1054 assert(
areVarsUnique(*
this, VarKind::Symbol) &&
"Symbol vars are not unique");
1055 assert(
areVarsUnique(other, VarKind::Symbol) &&
"Symbol vars are not unique");
1059 return IntegerPolyhedron::hasConsistentState() &&
1064 unsigned varLimit) {
1065 IntegerPolyhedron::removeVarRange(kind, varStart, varLimit);
1068 if (kind != VarKind::Local) {
1070 values.begin() + varLimit + offset);
1077 assert(map.
getNumInputs() == operands.size() &&
"number of inputs mismatch");
1101 assert(syms.size() == newSymsPtr->size() &&
"unexpected new/missing symbols");
1102 assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
1103 "unexpected new/missing symbols");
1109 for (
const auto &mayBeVar :
values) {
1110 if (mayBeVar && *mayBeVar == val) {
1120 return llvm::any_of(
values, [&](
const std::optional<Value> &mayBeVar) {
1121 return mayBeVar && *mayBeVar == val;
1126 IntegerPolyhedron::swapVar(posA, posB);
1134 values[posB] = std::nullopt;
1136 values[posA] = std::nullopt;
1146 assert(0 &&
"var not found");
1181 if (
auto *otherValueSet =
1182 dyn_cast<const FlatLinearValueConstraints>(&other)) {
1183 *
this = *otherValueSet;
1192 unsigned pos,
bool darkShadow,
bool *isResultIntegerExact) {
1195 newVals.erase(newVals.begin() + pos);
1197 IntegerPolyhedron::fourierMotzkinEliminate(pos, darkShadow,
1198 isResultIntegerExact);
1205 bool ret =
findVar(val, &pos);
1217 "dim values mismatch");
1218 assert(otherCst.
getNumLocalVars() == 0 &&
"local vars not supported here");
1219 assert(
getNumLocalVars() == 0 &&
"local vars not supported yet here");
1225 return IntegerPolyhedron::unionBoundingBox(otherCopy);
1228 return IntegerPolyhedron::unionBoundingBox(otherCst);
1239 "expected same number of operands and map inputs");
1243 unsigned numSymbols = syms.size();
1247 newSyms->append(syms.begin(), syms.end());
1253 auto dimIt = llvm::find(dims, operand.value());
1254 auto symIt = llvm::find(syms, operand.value());
1255 if (dimIt != dims.end()) {
1258 }
else if (symIt != syms.end()) {
1266 newSyms->push_back(operand.value());
1270 dimReplacements[operand.index()] = replacement;
1272 symReplacements[operand.index() - map.
getNumDims()] = replacement;
1277 dims.size(), numSymbols);
1284 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
1292 "AffineMap cannot produce divs without local representation");
1296 for (
unsigned i = 0, e = flattenedExprs.size(); i < e; ++i)
1297 for (
unsigned j = 0, f = flattenedExprs[i].size();
j < f; ++
j)
1298 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 LogicalResult getFlattenedAffineExprs(ArrayRef< AffineExpr > exprs, unsigned numDims, unsigned numSymbols, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *localVarCst)
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 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 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...
A dimensional identifier appearing in an affine expression.
unsigned getPosition() const
Base type for affine expression.
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
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.
unsigned appendLocalVar(unsigned num=1)
LogicalResult flattenAlignedMapAndMergeLocals(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs)
Given an affine map that is aligned with this constraint system:
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatLinearConstraints.
LogicalResult addBound(presburger::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...
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...
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.
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.
void clearAndCopyFrom(const IntegerRelation &other) override
Replaces the contents of this FlatLinearValueConstraints with other.
void swapVar(unsigned posA, unsigned posB) override
Swap the posA^th variable with the posB^th variable.
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...
unsigned insertSymbolVar(unsigned pos, unsigned num=1)
void fourierMotzkinEliminate(unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr) override
Eliminates the variable at the specified position using Fourier-Motzkin variable elimination,...
SmallVector< std::optional< Value >, 8 > values
Values corresponding to the (column) non-local variables of this constraint system appearing in the o...
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.
LogicalResult addBound(presburger::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 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.
bool hasConsistentState() const override
Returns false if the fields corresponding to various variable counts, or equality/inequality buffer s...
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 ...
bool findVar(Value val, unsigned *pos) const
Looks up the position of the variable with the specified Value.
unsigned appendDimVar(ValueRange vals)
unsigned appendSymbolVar(unsigned num=1)
unsigned insertSymbolVar(unsigned pos, ValueRange vals)
ArrayRef< std::optional< Value > > getMaybeValues() const
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...
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)
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 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.
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 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.
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.
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 getNumEqualities() const
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of vars starts.
unsigned getNumDimVars() const
friend MPInt floorDiv(const MPInt &lhs, const MPInt &rhs)
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain...
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.
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...
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt floorDiv(const MPInt &lhs, const MPInt &rhs)
This header declares functions that assist transformations in the MemRef dialect.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
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 getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, SmallVectorImpl< int64_t > *flattenedExpr, FlatLinearConstraints *cst=nullptr)
Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the dimensions,...
AffineExpr getAffineExprFromFlatForm(ArrayRef< int64_t > flatExprs, unsigned numDims, unsigned numSymbols, ArrayRef< AffineExpr > localExprs, MLIRContext *context)
Constructs an affine expression from a flat ArrayRef.
LogicalResult getFlattenedAffineExprs(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *cst=nullptr)
Flattens the result expressions of the map to their corresponding flattened forms and set in 'flatten...
AffineExpr getAffineConstantExpr(int64_t constant, MLIRContext *context)
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)
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.