16 #include "llvm/ADT/STLFunctionalExtras.h"
17 #include "llvm/ADT/SmallBitVector.h"
18 #include "llvm/Support/raw_ostream.h"
25 using namespace presburger;
26 using llvm::dynamicAPIntFromInt64;
33 DynamicAPInt &divisor) {
34 assert(divisor > 0 &&
"divisor must be non-negative!");
39 DynamicAPInt gcd = llvm::gcd(
abs(dividend.front()), divisor);
48 for (
size_t i = 1, m = dividend.size() - 1; i < m; i++) {
49 gcd = llvm::gcd(
abs(dividend[i]), gcd);
55 std::transform(dividend.begin(), dividend.end(), dividend.begin(),
56 [gcd](DynamicAPInt &n) { return floorDiv(n, gcd); });
99 unsigned ubIneq,
unsigned lbIneq,
101 DynamicAPInt &divisor) {
103 assert(pos <= cst.
getNumVars() &&
"Invalid variable position");
105 "Invalid upper bound inequality position");
107 "Invalid upper bound inequality position");
108 assert(expr.size() == cst.
getNumCols() &&
"Invalid expression size");
109 assert(cst.
atIneq(lbIneq, pos) > 0 &&
"lbIneq is not a lower bound!");
110 assert(cst.
atIneq(ubIneq, pos) < 0 &&
"ubIneq is not an upper bound!");
113 divisor = cst.
atIneq(lbIneq, pos);
117 unsigned i = 0, e = 0;
130 DynamicAPInt c = divisor - 1 - constantSum;
134 if (!(0 <= c && c <= divisor - 1))
142 expr[i] = cst.
atIneq(ubIneq, i);
167 DynamicAPInt &divisor) {
169 assert(pos <= cst.
getNumVars() &&
"Invalid variable position");
171 assert(expr.size() == cst.
getNumCols() &&
"Invalid expression size");
176 DynamicAPInt tempDiv = cst.
atEq(eqInd, pos);
179 int signDiv = tempDiv < 0 ? -1 : 1;
182 divisor = tempDiv * signDiv;
184 for (
unsigned i = 0, e = cst.
getNumVars(); i < e; ++i)
186 expr[i] = -signDiv * cst.
atEq(eqInd, i);
201 for (
unsigned c = 0, e = cst.
getNumVars(); c < e; ++c) {
205 if (!foundRepr[c] && dividend[c] != 0) {
230 assert(pos < cst.
getNumVars() &&
"invalid position");
231 assert(foundRepr.size() == cst.
getNumVars() &&
232 "Size of foundRepr does not match total number of variables");
233 assert(dividend.size() == cst.
getNumCols() &&
"Invalid dividend size");
239 for (
unsigned ubPos : ubIndices) {
240 for (
unsigned lbPos : lbIndices) {
242 if (
getDivRepr(cst, pos, ubPos, lbPos, dividend, divisor).failed())
249 repr.repr.inequalityPair = {ubPos, lbPos};
253 for (
unsigned eqPos : eqIndices) {
255 if (
getDivRepr(cst, pos, eqPos, dividend, divisor).failed())
262 repr.repr.equalityIdx = eqPos;
272 DynamicAPInt divisorDynamicAPInt;
274 cst, foundRepr, pos, dividendDynamicAPInt, divisorDynamicAPInt);
276 divisor = unsigned(int64_t(divisorDynamicAPInt));
283 llvm::SmallBitVector vec(len,
false);
284 vec.set(setOffset, setOffset + numSet);
292 "Spaces should be compatible.");
306 for (
unsigned i = initLocals, e = divsB.
getNumDivs(); i < e; ++i)
316 const DynamicAPInt &divisor,
317 unsigned localVarIdx) {
318 assert(divisor > 0 &&
"divisor must be positive!");
319 assert(dividend[localVarIdx] == 0 &&
320 "Local to be set to division must have zero coeff!");
322 ineq[localVarIdx] = -divisor;
328 const DynamicAPInt &divisor,
329 unsigned localVarIdx) {
330 assert(divisor > 0 &&
"divisor must be positive!");
331 assert(dividend[localVarIdx] == 0 &&
332 "Local to be set to division must have zero coeff!");
334 std::transform(dividend.begin(), dividend.end(), ineq.begin(),
335 std::negate<DynamicAPInt>());
336 ineq[localVarIdx] = divisor;
337 ineq.back() += divisor - 1;
343 for (
const DynamicAPInt &elem : range) {
344 gcd = llvm::gcd(gcd,
abs(elem));
353 if ((gcd == 0) || (gcd == 1))
355 for (DynamicAPInt &elem : range)
361 DynamicAPInt &denom) {
362 assert(denom > 0 &&
"denom must be positive!");
363 DynamicAPInt gcd = llvm::gcd(
gcdRange(num), denom);
366 for (DynamicAPInt &coeff : num)
374 negatedCoeffs.reserve(coeffs.size());
375 for (
const DynamicAPInt &coeff : coeffs)
376 negatedCoeffs.emplace_back(-coeff);
377 return negatedCoeffs;
383 coeffs.reserve(ineq.size());
384 for (
const DynamicAPInt &coeff : ineq)
385 coeffs.emplace_back(-coeff);
392 assert(point.size() ==
getNumNonDivs() &&
"Incorrect point size");
399 for (
unsigned i = 0, e =
getNumDivs(); i < e; ++i) {
405 DynamicAPInt divVal(0);
424 divVal = std::inner_product(point.begin(), point.end(), dividend.begin(),
427 divVal += dividend.back();
429 divVal = floorDiv(divVal, denoms[i]);
432 divValues[i] = divVal;
461 if (denoms[i] != denoms[
j])
469 bool mergeResult = merge(i,
j);
478 denoms.erase(denoms.begin() +
j);
487 for (
unsigned i = 0, e =
getNumDivs(); i < e; ++i) {
495 const DynamicAPInt &divisor) {
496 assert(pos <=
getNumDivs() &&
"Invalid insertion position");
497 assert(dividend.size() ==
getNumVars() + 1 &&
"Incorrect dividend size");
500 denoms.insert(denoms.begin() + pos, divisor);
505 assert(pos <=
getNumDivs() &&
"Invalid insertion position");
508 denoms.insert(denoms.begin() + pos, num, DynamicAPInt(0));
512 os <<
"Dividends:\n";
514 os <<
"Denominators\n";
515 for (
const DynamicAPInt &denom : denoms)
525 std::transform(range.begin(), range.end(), result.begin(),
526 dynamicAPIntFromInt64);
532 std::transform(range.begin(), range.end(), result.begin(),
533 int64fromDynamicAPInt);
538 assert(a.size() == b.size() &&
539 "dot product is only valid for vectors of equal sizes!");
541 for (
unsigned i = 0, e = a.size(); i < e; i++)
552 unsigned len = a.size() + b.size() - 1;
561 std::vector<Fraction> convolution;
562 convolution.reserve(len);
563 for (
unsigned k = 0; k < len; ++k) {
565 for (
unsigned l = 0; l <= k; ++l)
566 sum += getCoeff(a, l) * getCoeff(b, k - l);
567 convolution.emplace_back(sum);
573 return llvm::all_of(arr, [](
const Fraction &f) {
return f == 0; });
static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos, unsigned ubIneq, unsigned lbIneq, MutableArrayRef< DynamicAPInt > expr, DynamicAPInt &divisor)
Check if the pos^th variable can be represented as a division using upper bound inequality at positio...
static bool checkExplicitRepresentation(const IntegerRelation &cst, ArrayRef< bool > foundRepr, ArrayRef< DynamicAPInt > dividend, unsigned pos)
static void normalizeDivisionByGCD(MutableArrayRef< DynamicAPInt > dividend, DynamicAPInt &divisor)
Normalize a division's dividend and the divisor by their GCD.
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.
unsigned getNumNonDivs() const
unsigned getNumVars() const
unsigned getDivOffset() const
void print(raw_ostream &os) const
unsigned getNumDivs() const
SmallVector< std::optional< DynamicAPInt >, 4 > divValuesAt(ArrayRef< DynamicAPInt > point) const
DynamicAPInt & getDenom(unsigned i)
void insertDiv(unsigned pos, ArrayRef< DynamicAPInt > dividend, const DynamicAPInt &divisor)
void setDiv(unsigned i, ArrayRef< DynamicAPInt > dividend, const DynamicAPInt &divisor)
MutableArrayRef< DynamicAPInt > getDividend(unsigned i)
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
DynamicAPInt atIneq(unsigned i, unsigned j) const
Returns the value at the specified inequality row and column.
virtual unsigned insertVar(VarKind kind, unsigned pos, unsigned num=1)
Insert num variables of the specified kind at position pos.
DynamicAPInt atEq(unsigned i, unsigned j) const
Returns the value at the specified equality 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
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.
void normalizeDiv(MutableArrayRef< DynamicAPInt > num, DynamicAPInt &denom)
Normalize the given (numerator, denominator) pair by dividing out the common factors between them.
SmallVector< DynamicAPInt, 8 > getDynamicAPIntVec(ArrayRef< int64_t > range)
Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables ...
DynamicAPInt gcdRange(ArrayRef< DynamicAPInt > range)
Compute the gcd of the range.
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...
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 ...
SmallVector< DynamicAPInt, 8 > getNegatedCoeffs(ArrayRef< DynamicAPInt > coeffs)
Return coeffs with all the elements negated.
Fraction abs(const Fraction &f)
Fraction dotProduct(ArrayRef< Fraction > a, ArrayRef< Fraction > b)
Compute the dot product of two vectors.
SmallVector< int64_t, 8 > getInt64Vec(ArrayRef< DynamicAPInt > range)
Return the given array as an array of int64_t.
SmallVector< DynamicAPInt, 8 > getDivUpperBound(ArrayRef< DynamicAPInt > dividend, const DynamicAPInt &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 ...
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.
llvm::SmallBitVector getSubrangeBitVector(unsigned len, unsigned setOffset, unsigned numSet)
SmallVector< DynamicAPInt, 8 > getDivLowerBound(ArrayRef< DynamicAPInt > dividend, const DynamicAPInt &divisor, unsigned localVarIdx)
DynamicAPInt normalizeRange(MutableArrayRef< DynamicAPInt > range)
Divide the range by its gcd and return the gcd.
SmallVector< DynamicAPInt, 8 > getComplementIneq(ArrayRef< DynamicAPInt > ineq)
Return the complement of the given inequality.
Include the generated interface declarations.
const FrozenRewritePatternSet GreedyRewriteConfig bool * changed
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.