20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/raw_ostream.h"
27 #define DEBUG_TYPE "flat-value-constraints"
30 using namespace presburger;
49 AffineExprFlattener(
unsigned nDims,
unsigned nSymbols)
85 AffineExprFlattener flattener(numDims, numSymbols);
88 for (
auto expr : exprs) {
89 if (!expr.isPureAffine())
92 auto flattenResult = flattener.walkPostOrder(expr);
97 assert(flattener.operandExprStack.size() == exprs.size());
98 flattenedExprs->clear();
99 flattenedExprs->assign(flattener.operandExprStack.begin(),
100 flattener.operandExprStack.end());
115 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
117 &flattenedExprs, localVarCst);
118 *flattenedExpr = flattenedExprs[0];
160 assert(other.
getNumDims() == getNumDimVars() &&
"dim mismatch");
161 assert(other.
getNumSymbols() == getNumSymbolVars() &&
"symbol mismatch");
163 std::vector<SmallVector<int64_t, 8>> flatExprs;
164 if (
failed(flattenAlignedMapAndMergeLocals(other, &flatExprs)))
177 for (
unsigned r = 0, e = flatExprs.size(); r < e; r++) {
178 const auto &flatExpr = flatExprs[r];
186 for (
unsigned i = 0, f = other.
getNumInputs(); i < f; i++) {
188 eqToAdd[e + i] = -flatExpr[i];
191 unsigned j = getNumDimVars() + getNumSymbolVars();
192 unsigned end = flatExpr.size() - 1;
194 eqToAdd[
j] = -flatExpr[i];
198 eqToAdd[getNumCols() - 1] = -flatExpr[flatExpr.size() - 1];
201 addEquality(eqToAdd);
235 unsigned offset,
unsigned num, int64_t lbConst,
238 assert(pos < cst.
getNumVars() &&
"invalid position");
242 if (lbConst != 0 || ubConst < 1)
244 int64_t divisor = ubConst + 1;
248 curEquality < numEqualities; curEquality++) {
249 int64_t coefficientAtPos = cst.
atEq64(curEquality, pos);
252 if (coefficientAtPos == 0)
268 unsigned quotientCount = 0;
269 int quotientPosition = -1;
270 int quotientSign = 1;
278 int64_t coefficientOfCurVar = cst.
atEq64(curEquality, curVar);
280 if (coefficientOfCurVar == 0)
283 if (coefficientOfCurVar % (divisor * coefficientAtPos) == 0) {
285 quotientPosition = curVar;
286 quotientSign = (coefficientOfCurVar * coefficientAtPos) > 0 ? 1 : -1;
293 dividendExpr = dividendExpr + memo[curVar] * coefficientOfCurVar;
301 if (coefficientAtPos > 0)
302 dividendExpr = (-dividendExpr).
floorDiv(coefficientAtPos);
304 dividendExpr = dividendExpr.
floorDiv(-coefficientAtPos);
313 auto dimExpr = dyn_cast<AffineDimExpr>(dividendExpr);
318 if (quotientCount >= 1) {
323 unsigned dimExprPos = dimExpr.getPosition();
324 unsigned dimExprCol = dimExprPos < offset ? dimExprPos : dimExprPos + num;
328 if (ub && *ub < divisor)
331 memo[pos] = dimExpr % divisor;
334 if (quotientCount == 1 && !memo[quotientPosition])
335 memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;
353 assert(pos < cst.
getNumVars() &&
"invalid position");
357 for (
unsigned i = 0, e = cst.
getNumVars(); i < e; ++i)
371 for (
unsigned c = 0, f = cst.
getNumVars(); c < f; c++)
372 if (dividend[c] != 0)
373 dividendExpr = dividendExpr + dividend[c] * exprs[c];
376 exprs[pos] = dividendExpr.floorDiv(divisor);
381 unsigned pos,
unsigned offset,
unsigned num,
unsigned symStartPos,
383 bool closedUB)
const {
384 assert(pos + offset < getNumDimVars() &&
"invalid dim start pos");
385 assert(symStartPos >= (pos + offset) &&
"invalid sym start pos");
386 assert(getNumLocalVars() == localExprs.size() &&
387 "incorrect local exprs count");
390 getLowerAndUpperBoundIndices(pos + offset, &lbIndices, &ubIndices, &eqIndices,
396 for (
unsigned i = 0, e = a.size(); i < e; ++i) {
397 if (i < offset || i >= offset + num)
404 unsigned dimCount = symStartPos - num;
405 unsigned symCount = getNumDimAndSymbolVars() - symStartPos;
406 lbExprs.reserve(lbIndices.size() + eqIndices.size());
408 for (
auto idx : lbIndices) {
409 auto ineq = getInequality64(idx);
414 std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
418 int64_t divisor =
std::abs(ineq[pos + offset]);
419 expr = (expr + divisor - 1).
floorDiv(divisor);
420 lbExprs.push_back(expr);
424 ubExprs.reserve(ubIndices.size() + eqIndices.size());
426 for (
auto idx : ubIndices) {
427 auto ineq = getInequality64(idx);
432 expr = expr.floorDiv(
std::abs(ineq[pos + offset]));
433 int64_t ubAdjustment = closedUB ? 0 : 1;
434 ubExprs.push_back(expr + ubAdjustment);
439 for (
auto idx : eqIndices) {
440 auto eq = getEquality64(idx);
442 if (eq[pos + offset] > 0)
443 std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());
448 expr = expr.floorDiv(
std::abs(eq[pos + offset]));
450 ubExprs.push_back(expr + 1);
454 expr = expr.ceilDiv(
std::abs(eq[pos + offset]));
455 lbExprs.push_back(expr);
458 auto lbMap =
AffineMap::get(dimCount, symCount, lbExprs, context);
459 auto ubMap =
AffineMap::get(dimCount, symCount, ubExprs, context);
461 return {lbMap, ubMap};
474 assert(offset + num <= getNumDimVars() &&
"invalid range");
477 normalizeConstraintsByGCD();
479 LLVM_DEBUG(llvm::dbgs() <<
"getSliceBounds for first " << num
486 for (
unsigned i = 0, e = getNumDimVars(); i < e; i++) {
489 else if (i >= offset + num)
492 for (
unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++)
500 for (
unsigned pos = 0; pos < getNumVars(); pos++) {
506 if (lbConst.has_value() && ubConst.has_value()) {
508 if (*lbConst == *ubConst) {
516 if (
detectAsMod(*
this, pos, offset, num, *lbConst, *ubConst, context,
532 if (!findConstraintWithNonZeroAt(pos,
true, &idx)) {
539 for (
j = 0, e = getNumVars();
j < e; ++
j) {
542 int64_t c = atEq64(idx,
j);
548 expr = expr + memo[
j] * c;
556 expr = expr + atEq64(idx, getNumVars());
557 int64_t vPos = atEq64(idx, pos);
558 assert(vPos != 0 &&
"expected non-zero here");
573 int64_t ubAdjustment = closedUB ? 0 : 1;
578 std::optional<FlatLinearConstraints> tmpClone;
579 for (
unsigned pos = 0; pos < num; pos++) {
580 unsigned numMapDims = getNumDimVars() - num;
581 unsigned numMapSymbols = getNumSymbolVars();
591 ubMap =
AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
596 if (getNumLocalVars() == 0) {
602 tmpClone->removeRedundantInequalities();
604 std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
605 pos, offset, num, getNumDimVars(), {}, context,
615 LLVM_DEBUG(llvm::dbgs()
616 <<
"WARNING: Potentially over-approximating slice lb\n");
617 auto lbConst = getConstantBound64(
BoundType::LB, pos + offset);
618 if (lbConst.has_value()) {
624 LLVM_DEBUG(llvm::dbgs()
625 <<
"WARNING: Potentially over-approximating slice ub\n");
626 auto ubConst = getConstantBound64(
BoundType::UB, pos + offset);
627 if (ubConst.has_value()) {
629 numMapDims, numMapSymbols,
634 LLVM_DEBUG(llvm::dbgs()
635 <<
"lb map for pos = " << Twine(pos + offset) <<
", expr: ");
636 LLVM_DEBUG(lbMap.
dump(););
637 LLVM_DEBUG(llvm::dbgs()
638 <<
"ub map for pos = " << Twine(pos + offset) <<
", expr: ");
639 LLVM_DEBUG(ubMap.
dump(););
647 LLVM_DEBUG(llvm::dbgs()
648 <<
"composition unimplemented for semi-affine maps\n");
654 unsigned numLocalVars = getNumLocalVars();
669 bool isClosedBound) {
670 assert(boundMap.
getNumDims() == getNumDimVars() &&
"dim mismatch");
671 assert(boundMap.
getNumSymbols() == getNumSymbolVars() &&
"symbol mismatch");
672 assert(pos < getNumDimAndSymbolVars() &&
"invalid position");
674 "EQ bound must be closed.");
679 "single result expected");
682 std::vector<SmallVector<int64_t, 8>> flatExprs;
683 if (
failed(flattenAlignedMapAndMergeLocals(boundMap, &flatExprs)))
688 for (
const auto &flatExpr : flatExprs) {
692 ineq[
j] = lower ? -flatExpr[
j] : flatExpr[
j];
699 ineq[pos] = lower ? 1 : -1;
701 unsigned j = getNumDimVars() + getNumSymbolVars();
702 unsigned end = flatExpr.size() - 1;
703 for (
unsigned i = boundMap.
getNumInputs(); i < end; i++,
j++) {
704 ineq[
j] = lower ? -flatExpr[i] : flatExpr[i];
708 int64_t boundAdjustment = (isClosedBound || type ==
BoundType::EQ) ? 0 : -1;
710 ineq[getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
711 : flatExpr[flatExpr.size() - 1]) +
713 type ==
BoundType::EQ ? addEquality(ineq) : addInequality(ineq);
730 unsigned numDims = getNumDimVars();
731 unsigned numSyms = getNumSymbolVars();
734 for (
unsigned i = 0; i < numDims; i++)
736 for (
unsigned i = numDims, e = numDims + numSyms; i < e; i++)
745 for (
unsigned i = 0, e = getNumLocalVars(); i < e; ++i)
746 if (!memo[numDims + numSyms + i] &&
754 llvm::all_of(localExprs, [](
AffineExpr expr) {
return expr; }));
758 if (getNumConstraints() == 0)
767 if (
failed(computeLocalVars(memo, context))) {
771 unsigned numDimsSymbols = getNumDimAndSymbolVars();
772 for (
unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
773 if (!memo[i] && !isColZero(i))
774 noLocalRepVars.push_back(i - numDimsSymbols);
776 if (!noLocalRepVars.empty()) {
778 llvm::dbgs() <<
"local variables at position(s) ";
779 llvm::interleaveComma(noLocalRepVars, llvm::dbgs());
780 llvm::dbgs() <<
" do not have an explicit representation in:\n";
791 unsigned numDims = getNumDimVars();
792 unsigned numSyms = getNumSymbolVars();
795 std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(),
true);
796 std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(),
false);
799 exprs.reserve(getNumConstraints());
801 for (
unsigned i = 0, e = getNumEqualities(); i < e; ++i)
803 numSyms, localExprs, context));
804 for (
unsigned i = 0, e = getNumInequalities(); i < e; ++i)
806 numSyms, localExprs, context));
818 set.getNumDims() + set.getNumSymbols() + 1,
819 set.getNumDims(), set.getNumSymbols(),
821 assert(operands.empty() ||
822 set.
getNumInputs() == operands.size() &&
"operand count mismatch");
824 for (
unsigned i = 0, e = operands.size(); i < e; ++i)
828 std::vector<SmallVector<int64_t, 8>> flatExprs;
831 assert(
false &&
"flattening unimplemented for semi-affine integer sets");
838 for (
unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
839 const auto &flatExpr = flatExprs[i];
853 return insertVar(VarKind::SetDim, pos, vals);
858 return insertVar(VarKind::Symbol, pos, vals);
863 return insertVar(VarKind::SetDim, pos, vals);
868 return insertVar(VarKind::Symbol, pos, vals);
873 unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
880 assert(!vals.empty() &&
"expected ValueRange with Values.");
881 assert(kind != VarKind::Local &&
882 "values cannot be attached to local variables.");
883 unsigned num = vals.size();
884 unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);
887 for (
unsigned i = 0, e = vals.size(); i < e; ++i)
904 return std::equal(aMaybeValues.begin(), aMaybeValues.end(),
905 bMaybeValues.begin(), bMaybeValues.end());
921 "Start position out of bounds");
930 maybeValuesAll.data() + end};
932 for (std::optional<Value> val : maybeValues)
933 if (val && !uniqueVars.insert(*val).second)
940 static bool LLVM_ATTRIBUTE_UNUSED
947 static bool LLVM_ATTRIBUTE_UNUSED
950 if (kind == VarKind::SetDim)
952 if (kind == VarKind::Symbol)
955 llvm_unreachable(
"Unexpected VarKind");
972 assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
976 [](
const std::optional<Value> &var) { return var.has_value(); }));
980 [](
const std::optional<Value> &var) { return var.has_value(); }));
988 for (
Value aDimValue : aDimValues) {
993 if (b->
findVar(aDimValue, &loc, d)) {
994 assert(loc >= offset &&
"A's dim appears in B's aligned range");
995 assert(loc < b->getNumDimVars() &&
996 "A's dim appears in B's non-dim position");
1008 "expected same number of dims");
1037 for (
Value aSymValue : aSymValues) {
1057 "expected same number of symbols");
1061 unsigned varLimit) {
1062 IntegerPolyhedron::removeVarRange(kind, varStart, varLimit);
1068 assert(map.
getNumInputs() == operands.size() &&
"number of inputs mismatch");
1080 for (
unsigned i = 0, e =
getNumVarKind(VarKind::SetDim); i < e; ++i) {
1084 for (
unsigned i = 0, e =
getNumVarKind(VarKind::Symbol); i < e; ++i) {
1092 assert(syms.size() == newSymsPtr->size() &&
"unexpected new/missing symbols");
1093 assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
1094 "unexpected new/missing symbols");
1099 unsigned offset)
const {
1101 for (
unsigned i = offset, e = maybeValues.size(); i < e; ++i)
1102 if (maybeValues[i] && maybeValues[i].value() == val) {
1119 assert(0 &&
"var not found");
1153 bool ret =
findVar(val, &pos);
1165 assert(std::equal(maybeValues.begin(), maybeValues.begin() +
getNumDimVars(),
1166 otherMaybeValues.begin(),
1168 "dim values mismatch");
1169 assert(otherCst.
getNumLocalVars() == 0 &&
"local vars not supported here");
1170 assert(
getNumLocalVars() == 0 &&
"local vars not supported yet here");
1176 return IntegerPolyhedron::unionBoundingBox(otherCopy);
1179 return IntegerPolyhedron::unionBoundingBox(otherCst);
1190 "expected same number of operands and map inputs");
1194 unsigned numSymbols = syms.size();
1198 newSyms->append(syms.begin(), syms.end());
1204 auto dimIt = llvm::find(dims, operand.value());
1205 auto symIt = llvm::find(syms, operand.value());
1206 if (dimIt != dims.end()) {
1209 }
else if (symIt != syms.end()) {
1217 newSyms->push_back(operand.value());
1221 dimReplacements[operand.index()] = replacement;
1223 symReplacements[operand.index() - map.
getNumDims()] = replacement;
1228 dims.size(), numSymbols);
1235 std::vector<SmallVector<int64_t, 8>> flattenedExprs;
1243 "AffineMap cannot produce divs without local representation");
1247 for (
unsigned i = 0, e = flattenedExprs.size(); i < e; ++i)
1248 for (
unsigned j = 0, f = flattenedExprs[i].size();
j < f; ++
j)
1249 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...
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.
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.
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.
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...
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)
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.
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.
unsigned getNumDomainVars() const
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 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.
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
virtual void fourierMotzkinEliminate(unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr)
Eliminates the variable at the specified position using Fourier-Motzkin variable elimination,...
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...
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< MPInt > dividend, MPInt &divisor)
Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed...
Fraction abs(const Fraction &f)
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt floorDiv(const MPInt &lhs, const MPInt &rhs)
Include the generated interface declarations.
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.