24 using namespace presburger;
32 assert(divisor > 0 &&
"divisor must be non-negative!");
33 if (divisor == 0 || dividend.empty())
46 for (
size_t i = 1, m = dividend.size() - 1; i < m; i++) {
53 std::transform(dividend.begin(), dividend.end(), dividend.begin(),
54 [
gcd](
MPInt &n) { return floorDiv(n, gcd); });
97 unsigned ubIneq,
unsigned lbIneq,
100 assert(pos <= cst.
getNumVars() &&
"Invalid variable position");
102 "Invalid upper bound inequality position");
104 "Invalid upper bound inequality position");
105 assert(expr.size() == cst.
getNumCols() &&
"Invalid expression size");
106 assert(cst.
atIneq(lbIneq, pos) > 0 &&
"lbIneq is not a lower bound!");
107 assert(cst.
atIneq(ubIneq, pos) < 0 &&
"ubIneq is not an upper bound!");
110 divisor = cst.
atIneq(lbIneq, pos);
114 unsigned i = 0, e = 0;
127 MPInt c = divisor - 1 - constantSum;
131 if (!(0 <= c && c <= divisor - 1))
139 expr[i] = cst.
atIneq(ubIneq, i);
165 assert(pos <= cst.
getNumVars() &&
"Invalid variable position");
167 assert(expr.size() == cst.
getNumCols() &&
"Invalid expression size");
175 int signDiv = tempDiv < 0 ? -1 : 1;
178 divisor = tempDiv * signDiv;
180 for (
unsigned i = 0, e = cst.
getNumVars(); i < e; ++i)
182 expr[i] = -signDiv * cst.
atEq(eqInd, i);
197 for (
unsigned c = 0, e = cst.
getNumVars(); c < e; ++c) {
201 if (!foundRepr[c] && dividend[c] != 0) {
228 assert(pos < cst.
getNumVars() &&
"invalid position");
229 assert(foundRepr.size() == cst.
getNumVars() &&
230 "Size of foundRepr does not match total number of variables");
231 assert(dividend.size() == cst.
getNumCols() &&
"Invalid dividend size");
237 for (
unsigned ubPos : ubIndices) {
238 for (
unsigned lbPos : lbIndices) {
247 repr.repr.inequalityPair = {ubPos, lbPos};
251 for (
unsigned eqPos : eqIndices) {
260 repr.repr.equalityIdx = eqPos;
274 divisor = unsigned(int64_t(divisorMPInt));
281 llvm::SmallBitVector vec(len,
false);
282 vec.set(setOffset, setOffset + numSet);
290 "Spaces should be compatible.");
304 for (
unsigned i = initLocals, e = divsB.
getNumDivs(); i < e; ++i)
313 const MPInt &divisor,
314 unsigned localVarIdx) {
315 assert(divisor > 0 &&
"divisor must be positive!");
316 assert(dividend[localVarIdx] == 0 &&
317 "Local to be set to division must have zero coeff!");
319 ineq[localVarIdx] = -divisor;
324 const MPInt &divisor,
325 unsigned localVarIdx) {
326 assert(divisor > 0 &&
"divisor must be positive!");
327 assert(dividend[localVarIdx] == 0 &&
328 "Local to be set to division must have zero coeff!");
330 std::transform(dividend.begin(), dividend.end(), ineq.begin(),
331 std::negate<MPInt>());
332 ineq[localVarIdx] = divisor;
333 ineq.back() += divisor - 1;
339 for (
const MPInt &elem : range) {
349 if ((
gcd == 0) || (
gcd == 1))
351 for (
MPInt &elem : range)
357 assert(denom > 0 &&
"denom must be positive!");
359 for (
MPInt &coeff : num)
366 negatedCoeffs.reserve(coeffs.size());
367 for (
const MPInt &coeff : coeffs)
368 negatedCoeffs.emplace_back(-coeff);
369 return negatedCoeffs;
374 coeffs.reserve(ineq.size());
375 for (
const MPInt &coeff : ineq)
376 coeffs.emplace_back(-coeff);
383 assert(point.size() ==
getNumNonDivs() &&
"Incorrect point size");
389 for (
unsigned i = 0, e =
getNumDivs(); i < e; ++i) {
414 divVal = std::inner_product(point.begin(), point.end(), dividend.begin(),
417 divVal += dividend.back();
419 divVal =
floorDiv(divVal, denoms[i]);
422 divValues[i] = divVal;
451 if (denoms[i] != denoms[
j])
459 bool mergeResult = merge(i,
j);
468 denoms.erase(denoms.begin() +
j);
477 for (
unsigned i = 0, e =
getNumDivs(); i < e; ++i) {
485 const MPInt &divisor) {
486 assert(pos <=
getNumDivs() &&
"Invalid insertion position");
487 assert(dividend.size() ==
getNumVars() + 1 &&
"Incorrect dividend size");
490 denoms.insert(denoms.begin() + pos, divisor);
495 assert(pos <=
getNumDivs() &&
"Invalid insertion position");
498 denoms.insert(denoms.begin() + pos, num,
MPInt(0));
502 os <<
"Dividends:\n";
504 os <<
"Denominators\n";
505 for (
unsigned i = 0, e = denoms.size(); i < e; ++i)
506 os << denoms[i] <<
" ";
514 std::transform(range.begin(), range.end(), result.begin(),
mpintFromInt64);
520 std::transform(range.begin(), range.end(), result.begin(),
int64FromMPInt);
static void normalizeDivisionByGCD(MutableArrayRef< MPInt > dividend, MPInt &divisor)
Normalize a division's dividend and the divisor by their GCD.
static bool checkExplicitRepresentation(const IntegerRelation &cst, ArrayRef< bool > foundRepr, ArrayRef< MPInt > dividend, unsigned pos)
static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos, unsigned ubIneq, unsigned lbIneq, MutableArrayRef< MPInt > expr, MPInt &divisor)
Check if the pos^th variable can be represented as a division using upper bound inequality at positio...
Class storing division representation of local variables of a constraint system.
void removeDuplicateDivs(llvm::function_ref< bool(unsigned i, unsigned j)> merge)
Removes duplicate divisions.
MPInt & getDenom(unsigned i)
unsigned getNumNonDivs() const
unsigned getNumVars() const
SmallVector< std::optional< MPInt >, 4 > divValuesAt(ArrayRef< MPInt > point) const
unsigned getDivOffset() const
void print(raw_ostream &os) const
unsigned getNumDivs() const
void insertDiv(unsigned pos, ArrayRef< MPInt > dividend, const MPInt &divisor)
void setDiv(unsigned i, ArrayRef< MPInt > dividend, const MPInt &divisor)
MutableArrayRef< MPInt > getDividend(unsigned i)
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
MPInt atEq(unsigned i, unsigned j) const
Returns the value at the specified equality row and column.
virtual unsigned insertVar(VarKind kind, unsigned pos, unsigned num=1)
Insert num variables of the specified kind at position pos.
MPInt atIneq(unsigned i, unsigned j) const
Returns the value at the specified inequality row and column.
unsigned getNumVars() const
unsigned getNumLocalVars() const
unsigned getNumCols() const
Returns the number of columns in the constraint system.
void getLowerAndUpperBoundIndices(unsigned pos, SmallVectorImpl< unsigned > *lbIndices, SmallVectorImpl< unsigned > *ubIndices, SmallVectorImpl< unsigned > *eqIndices=nullptr, unsigned offset=0, unsigned num=0) const
Gather positions of all lower and upper bounds of the variable at pos, and optionally any equalities ...
DivisionRepr getLocalReprs(std::vector< MaybeLocalRepr > *repr=nullptr) const
Returns a DivisonRepr representing the division representation of local variables in the constraint s...
unsigned getNumInequalities() const
const PresburgerSpace & getSpace() const
Returns a reference to the underlying space.
unsigned getNumEqualities() const
This class provides support for multi-precision arithmetic.
void insertRows(unsigned pos, unsigned count)
Insert rows having positions pos, pos + 1, ...
void removeColumn(unsigned pos)
unsigned appendExtraRow()
Add an extra row at the bottom of the matrix and return its position.
void addToColumn(unsigned sourceColumn, unsigned targetColumn, const T &scale)
Add scale multiples of the source column to the target column.
void print(raw_ostream &os) const
Print the matrix.
void insertColumn(unsigned pos)
MutableArrayRef< T > getRow(unsigned row)
Get a [Mutable]ArrayRef corresponding to the specified row.
void insertColumns(unsigned pos, unsigned count)
Insert columns having positions pos, pos + 1, ...
void removeRow(unsigned pos)
bool isCompatible(const PresburgerSpace &other) const
Returns true if both the spaces are compatible i.e.
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt gcd(const MPInt &a, const MPInt &b)
SmallVector< MPInt, 8 > getDivLowerBound(ArrayRef< MPInt > dividend, const MPInt &divisor, unsigned localVarIdx)
SmallVector< MPInt, 8 > getDivUpperBound(ArrayRef< MPInt > dividend, const MPInt &divisor, unsigned localVarIdx)
If q is defined to be equal to expr floordiv d, this equivalent to saying that q is an integer and q ...
void mergeLocalVars(IntegerRelation &relA, IntegerRelation &relB, llvm::function_ref< bool(unsigned i, unsigned j)> merge)
Given two relations, A and B, add additional local vars to the sets such that both have the union of ...
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt abs(const MPInt &x)
static int64_t int64FromMPInt(const MPInt &x)
This just calls through to the operator int64_t, but it's useful when a function pointer is required.
MPInt gcdRange(ArrayRef< MPInt > range)
Compute the gcd of the range.
void normalizeDiv(MutableArrayRef< MPInt > num, MPInt &denom)
Normalize the given (numerator, denominator) pair by dividing out the common factors between them.
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mpintFromInt64(int64_t 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...
SmallVector< MPInt, 8 > getMPIntVec(ArrayRef< int64_t > range)
Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables ...
SmallVector< MPInt, 8 > getNegatedCoeffs(ArrayRef< MPInt > coeffs)
Return coeffs with all the elements negated.
MPInt normalizeRange(MutableArrayRef< MPInt > range)
Divide the range by its gcd and return the gcd.
SmallVector< int64_t, 8 > getInt64Vec(ArrayRef< MPInt > range)
Return the given array as an array of int64_t.
llvm::SmallBitVector getSubrangeBitVector(unsigned len, unsigned setOffset, unsigned numSet)
SmallVector< MPInt, 8 > getComplementIneq(ArrayRef< MPInt > ineq)
Return the complement of the given inequality.
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.
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
This class represents an efficient way to signal success or failure.
MaybeLocalRepr contains the indices of the constraints that can be expressed as a floordiv of an affi...
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.