19 #include "llvm/ADT/STLFunctionalExtras.h"
20 #include "llvm/ADT/SmallBitVector.h"
21 #include "llvm/Support/raw_ostream.h"
33 using namespace presburger;
41 assert(divisor > 0 &&
"divisor must be non-negative!");
42 if (divisor == 0 || dividend.empty())
55 for (
size_t i = 1, m = dividend.size() - 1; i < m; i++) {
62 std::transform(dividend.begin(), dividend.end(), dividend.begin(),
63 [
gcd](
MPInt &n) { return floorDiv(n, gcd); });
106 unsigned ubIneq,
unsigned lbIneq,
109 assert(pos <= cst.
getNumVars() &&
"Invalid variable position");
111 "Invalid upper bound inequality position");
113 "Invalid upper bound inequality position");
114 assert(expr.size() == cst.
getNumCols() &&
"Invalid expression size");
115 assert(cst.
atIneq(lbIneq, pos) > 0 &&
"lbIneq is not a lower bound!");
116 assert(cst.
atIneq(ubIneq, pos) < 0 &&
"ubIneq is not an upper bound!");
119 divisor = cst.
atIneq(lbIneq, pos);
123 unsigned i = 0, e = 0;
136 MPInt c = divisor - 1 - constantSum;
140 if (!(0 <= c && c <= divisor - 1))
148 expr[i] = cst.
atIneq(ubIneq, i);
174 assert(pos <= cst.
getNumVars() &&
"Invalid variable position");
176 assert(expr.size() == cst.
getNumCols() &&
"Invalid expression size");
184 int signDiv = tempDiv < 0 ? -1 : 1;
187 divisor = tempDiv * signDiv;
189 for (
unsigned i = 0, e = cst.
getNumVars(); i < e; ++i)
191 expr[i] = -signDiv * cst.
atEq(eqInd, i);
206 for (
unsigned c = 0, e = cst.
getNumVars(); c < e; ++c) {
210 if (!foundRepr[c] && dividend[c] != 0) {
237 assert(pos < cst.
getNumVars() &&
"invalid position");
238 assert(foundRepr.size() == cst.
getNumVars() &&
239 "Size of foundRepr does not match total number of variables");
240 assert(dividend.size() == cst.
getNumCols() &&
"Invalid dividend size");
246 for (
unsigned ubPos : ubIndices) {
247 for (
unsigned lbPos : lbIndices) {
256 repr.repr.inequalityPair = {ubPos, lbPos};
260 for (
unsigned eqPos : eqIndices) {
269 repr.repr.equalityIdx = eqPos;
283 divisor = unsigned(int64_t(divisorMPInt));
290 llvm::SmallBitVector vec(len,
false);
291 vec.set(setOffset, setOffset + numSet);
299 "Spaces should be compatible.");
313 for (
unsigned i = initLocals, e = divsB.
getNumDivs(); i < e; ++i)
322 const MPInt &divisor,
323 unsigned localVarIdx) {
324 assert(divisor > 0 &&
"divisor must be positive!");
325 assert(dividend[localVarIdx] == 0 &&
326 "Local to be set to division must have zero coeff!");
328 ineq[localVarIdx] = -divisor;
333 const MPInt &divisor,
334 unsigned localVarIdx) {
335 assert(divisor > 0 &&
"divisor must be positive!");
336 assert(dividend[localVarIdx] == 0 &&
337 "Local to be set to division must have zero coeff!");
339 std::transform(dividend.begin(), dividend.end(), ineq.begin(),
340 std::negate<MPInt>());
341 ineq[localVarIdx] = divisor;
342 ineq.back() += divisor - 1;
348 for (
const MPInt &elem : range) {
358 if ((
gcd == 0) || (
gcd == 1))
360 for (
MPInt &elem : range)
366 assert(denom > 0 &&
"denom must be positive!");
368 for (
MPInt &coeff : num)
375 negatedCoeffs.reserve(coeffs.size());
376 for (
const MPInt &coeff : coeffs)
377 negatedCoeffs.emplace_back(-coeff);
378 return negatedCoeffs;
383 coeffs.reserve(ineq.size());
384 for (
const MPInt &coeff : ineq)
385 coeffs.emplace_back(-coeff);
392 assert(point.size() ==
getNumNonDivs() &&
"Incorrect point size");
398 for (
unsigned i = 0, e =
getNumDivs(); i < e; ++i) {
423 divVal = std::inner_product(point.begin(), point.end(), dividend.begin(),
426 divVal += dividend.back();
428 divVal =
floorDiv(divVal, denoms[i]);
431 divValues[i] = divVal;
460 if (denoms[i] != denoms[
j])
468 bool mergeResult = merge(i,
j);
477 denoms.erase(denoms.begin() +
j);
486 for (
unsigned i = 0, e =
getNumDivs(); i < e; ++i) {
494 const MPInt &divisor) {
495 assert(pos <=
getNumDivs() &&
"Invalid insertion position");
496 assert(dividend.size() ==
getNumVars() + 1 &&
"Incorrect dividend size");
499 denoms.insert(denoms.begin() + pos, divisor);
504 assert(pos <=
getNumDivs() &&
"Invalid insertion position");
507 denoms.insert(denoms.begin() + pos, num,
MPInt(0));
511 os <<
"Dividends:\n";
513 os <<
"Denominators\n";
514 for (
const MPInt &denom : denoms)
523 std::transform(range.begin(), range.end(), result.begin(),
mpintFromInt64);
529 std::transform(range.begin(), range.end(), result.begin(),
int64FromMPInt);
534 assert(a.size() == b.size() &&
535 "dot product is only valid for vectors of equal sizes!");
537 for (
unsigned i = 0, e = a.size(); i < e; i++)
548 unsigned len = a.size() + b.size() - 1;
558 std::vector<Fraction> convolution;
559 convolution.reserve(len);
560 for (
unsigned k = 0; k < len; ++k) {
562 for (
unsigned l = 0; l <= k; ++l)
563 sum += getCoeff(a, l) * getCoeff(b, k - l);
564 convolution.push_back(sum);
570 return llvm::all_of(arr, [&](
Fraction f) {
return f == 0; });
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 ...
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...
Fraction abs(const Fraction &f)
Fraction dotProduct(ArrayRef< Fraction > a, ArrayRef< Fraction > b)
Compute the dot product of two vectors.
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.
bool isRangeZero(ArrayRef< Fraction > arr)
std::vector< Fraction > multiplyPolynomials(ArrayRef< Fraction > a, ArrayRef< Fraction > b)
Find the product of two polynomials, each given by an array of coefficients.
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)
Include the generated interface declarations.
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.
A class to represent fractions.
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.