11 #include "llvm/ADT/Sequence.h"
16 using namespace presburger;
25 ConeV dual(numIneq, numVar, 0, 0);
31 for (
auto i : llvm::seq<int>(0, numIneq)) {
32 assert(cone.
atIneq(i, numVar) == 0 &&
33 "H-representation of cone is not centred at the origin!");
34 for (
unsigned j = 0;
j < numVar; ++
j) {
55 for (
unsigned i = 0; i < rows; ++i)
109 std::vector<Point> denominator(numIneq);
111 for (
auto i : llvm::seq<int>(0, numVar)) {
112 row = generators.
getRow(i);
113 denominator[i] =
Point(row);
133 for (
auto i : llvm::seq<int>(0, numColumns)) {
134 for (
auto j : llvm::seq<int>(0, numRows))
135 ithCol[
j] = vertex(
j, i);
148 std::vector({numerator}),
149 std::vector({denominator}));
162 std::optional<ParamPoint>
179 for (
unsigned i = 0; i < d; ++i) {
182 if (equations(i, i) != 0)
184 for (
unsigned j = i + 1;
j < d; ++
j) {
185 if (equations(
j, i) == 0)
191 Fraction diagElement = equations(i, i);
194 for (
unsigned j = 0;
j < d; ++
j) {
197 if (equations(
j, i) == 0)
201 Fraction currentElement = equations(
j, i);
203 -currentElement / diagElement);
208 for (
unsigned i = 0; i < d; ++i)
209 equations.
scaleRow(i, 1 / equations(i, i));
240 std::vector<std::pair<PresburgerSet, GeneratingFunction>>
242 unsigned numSymbols,
ArrayRef<std::pair<PresburgerSet, GeneratingFunction>>
243 regionsAndGeneratingFunctions) {
244 assert(!regionsAndGeneratingFunctions.empty() &&
245 "there must be at least one chamber!");
248 std::vector<std::pair<PresburgerSet, GeneratingFunction>> chambers = {
268 for (
const auto &[region, generatingFunction] :
269 regionsAndGeneratingFunctions) {
270 std::vector<std::pair<PresburgerSet, GeneratingFunction>> newChambers;
272 for (
const auto &[currentRegion, currentGeneratingFunction] : chambers) {
278 newChambers.emplace_back(currentRegion, currentGeneratingFunction);
283 newChambers.emplace_back(intersection,
284 currentGeneratingFunction + generatingFunction);
285 newChambers.emplace_back(currentRegion.subtract(region),
286 currentGeneratingFunction);
288 chambers = std::move(newChambers);
313 std::vector<std::pair<PresburgerSet, GeneratingFunction>>
321 std::vector<ParamPoint> vertices;
324 std::vector<std::pair<PresburgerSet, GeneratingFunction>>
325 regionsAndGeneratingFunctions;
335 for (
unsigned i = numIneqs - numVars; i < numIneqs; ++i)
348 FracMatrix b2c2(numIneqs - numVars, numSymbols + 1);
350 remainder.getSubMatrix(0, numIneqs - numVars - 1, 0, numVars - 1));
351 b2c2 =
FracMatrix(remainder.getSubMatrix(0, numIneqs - numVars - 1, numVars,
352 numVars + numSymbols));
356 std::optional<ParamPoint> vertex =
361 if (std::find(vertices.begin(), vertices.end(), vertex) != vertices.end())
365 vertices.push_back(*vertex);
395 FracMatrix activeRegion(numIneqs - numVars, numSymbols + 1);
396 for (
unsigned i = 0; i < numIneqs - numVars; i++) {
397 activeRegion.
setRow(i, vertex->preMultiplyWithRow(a2.
getRow(i)));
415 for (
unsigned j = 0, e = subset.getNumRows();
j < e; ++
j) {
417 for (
unsigned k = 0; k < numVars; ++k)
418 ineq[k] = subset(
j, k);
428 for (
const std::pair<int, ConeH> &signedCone : unimodCones) {
429 auto [sign, cone] = signedCone;
430 vertexGf = vertexGf +
435 regionsAndGeneratingFunctions.emplace_back(
PresburgerSet(activeRegionRel),
437 }
while (std::next_permutation(indicator.begin(), indicator.end()));
475 unsigned dim = vectors[0].size();
477 llvm::all_of(vectors,
478 [&](
const Point &vector) {
return vector.size() == dim; }) &&
479 "all vectors need to be the same size!");
485 for (
unsigned d = 1; d < dim; ++d) {
487 maxDisallowedValue = -
Fraction(1, 0);
488 for (
const Point &vector : vectors) {
495 maxDisallowedValue =
std::max(maxDisallowedValue, disallowedValue);
497 newPoint.push_back(maxDisallowedValue + 1);
518 assert(!den.empty() &&
"division by empty denominator in rational function!");
520 unsigned numParam = num[0].getNumInputs();
526 "the quasipolynomials should all belong to the same space!");
528 std::vector<QuasiPolynomial> coefficients;
529 coefficients.reserve(power + 1);
531 coefficients.push_back(num[0] / den[0]);
532 for (
unsigned i = 1; i <= power; ++i) {
534 coefficients.push_back(i < num.size() ? num[i]
539 unsigned limit = std::min<unsigned long>(i, den.size() - 1);
540 for (
unsigned j = 1;
j <= limit; ++
j)
541 coefficients[i] = coefficients[i] -
544 coefficients[i] = coefficients[i] / den[0];
546 return coefficients[power].simplify();
557 std::pair<QuasiPolynomial, std::vector<Fraction>>
559 const std::vector<Point> &ds,
const Point &mu) {
560 unsigned numDims = mu.size();
562 for (
const Point &d : ds)
563 assert(d.size() == numDims &&
564 "μ has to have the same number of dimensions as the generators!");
575 coefficients.reserve(numDims);
576 for (
const Point &d : ds)
582 std::vector<std::vector<SmallVector<Fraction>>> affine;
583 affine.reserve(numDims);
584 for (
unsigned j = 0;
j < numDims; ++
j)
585 affine.push_back({SmallVector<Fraction>(vTranspose.getRow(j))});
590 std::vector<Fraction> dens;
591 dens.reserve(ds.size());
594 for (
const Point &d : ds) {
610 std::vector<Fraction> &dens) {
613 unsigned numNegExps = 0;
615 for (
const auto &den : dens) {
630 if (numNegExps % 2 == 1)
640 std::vector<QuasiPolynomial> coefficients;
641 coefficients.reserve(r + 1);
642 coefficients.emplace_back(numParams, 1);
643 for (
unsigned j = 1;
j <= r; ++
j)
645 coefficients.push_back(
656 std::vector<Fraction> coefficients;
657 coefficients.reserve((int64_t)
floor(r));
658 coefficients.emplace_back(1);
659 for (
unsigned j = 1;
j <= r; ++
j)
660 coefficients.push_back(coefficients[
j - 1] * (n - (
j - 1)) / (
j));
696 std::vector<Point> allDenominators;
698 allDenominators.insert(allDenominators.end(), den.begin(), den.end());
704 for (
unsigned i = 0, e = ds.size(); i < e; ++i) {
709 auto [numExp, dens] =
733 unsigned r = dens.size();
734 if (dens.size() % 2 == 1)
758 std::vector<QuasiPolynomial> numeratorCoefficients =
763 std::vector<std::vector<Fraction>> eachTermDenCoefficients;
764 std::vector<Fraction> singleTermDenCoefficients;
765 eachTermDenCoefficients.reserve(r);
768 eachTermDenCoefficients.push_back(
775 std::vector<Fraction> denominatorCoefficients;
776 denominatorCoefficients = eachTermDenCoefficients[0];
777 for (
unsigned j = 1, e = eachTermDenCoefficients.size();
j < e; ++
j)
779 eachTermDenCoefficients[
j]);
783 denominatorCoefficients) *
std::pair< QuasiPolynomial, std::vector< Fraction > > substituteMuInTerm(unsigned numParams, const ParamPoint &v, const std::vector< Point > &ds, const Point &mu)
Substitute x_i = t^μ_i in one term of a generating function, returning a quasipolynomial which repres...
std::vector< QuasiPolynomial > getBinomialCoefficients(const QuasiPolynomial &n, unsigned r)
Compute the binomial coefficients nCi for 0 ≤ i ≤ r, where n is a QuasiPolynomial.
void normalizeDenominatorExponents(int &sign, QuasiPolynomial &num, std::vector< Fraction > &dens)
Normalize all denominator exponents dens to their absolute values by multiplying and dividing by the ...
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
Fraction determinant(FracMatrix *inverse=nullptr) const
MPInt determinant(IntMatrix *inverse=nullptr) 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 ...
void addInequality(ArrayRef< MPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
unsigned getNumSymbolVars() const
MPInt atIneq(unsigned i, unsigned j) const
Returns the value at the specified inequality row and column.
unsigned getNumVars() const
unsigned getNumRangeVars() const
unsigned getNumCols() const
Returns the number of columns in the constraint system.
IntMatrix getInequalities() const
unsigned getNumInequalities() const
This class provides support for multi-precision arithmetic.
unsigned getNumRows() const
Matrix< T > getSubMatrix(unsigned fromRow, unsigned toRow, unsigned fromColumn, unsigned toColumn) const
void scaleRow(unsigned row, const T &scale)
Multiply the specified row by a factor of scale.
void insertColumn(unsigned pos)
MutableArrayRef< T > getRow(unsigned row)
Get a [Mutable]ArrayRef corresponding to the specified row.
void setRow(unsigned row, ArrayRef< T > elems)
Set the specified row to elems.
std::pair< Matrix< T >, Matrix< T > > splitByBitset(ArrayRef< int > indicator)
Split the rows of a matrix into two matrices according to which bits are 1 and which are 0 in a given...
void removeRow(unsigned pos)
unsigned getNumColumns() const
Matrix< T > transpose() const
SmallVector< T, 8 > preMultiplyWithRow(ArrayRef< T > rowVec) const
The given vector is interpreted as a row vector v.
void negateMatrix()
Negate the entire matrix.
void swapRows(unsigned row, unsigned otherRow)
Swap the given rows.
void addToRow(unsigned sourceRow, unsigned targetRow, const T &scale)
Add scale multiples of the source row to the target row.
void negateRow(unsigned row)
Negate the specified row.
T & at(unsigned row, unsigned column)
Access the element at the specified row and column.
bool isFullDim() const
Return whether the given PresburgerRelation is full-dimensional.
PresburgerSet intersect(const PresburgerRelation &set) const
static PresburgerSet getUniverse(const PresburgerSpace &space)
Return a universe set of the specified type that contains all points.
static PresburgerSpace getSetSpace(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)
static PresburgerSpace getRelationSpace(unsigned numDomain=0, unsigned numRange=0, unsigned numSymbols=0, unsigned numLocals=0)
QuasiPolynomial simplify()
unsigned getNumInputs() const
unsigned getNumParams() const
std::vector< ParamPoint > getNumerators() const
std::vector< std::vector< Point > > getDenominators() const
SmallVector< int > getSigns() const
std::vector< std::pair< PresburgerSet, GeneratingFunction > > computeChamberDecomposition(unsigned numSymbols, ArrayRef< std::pair< PresburgerSet, GeneratingFunction >> regionsAndGeneratingFunctions)
Given a list of possibly intersecting regions (PresburgerSet) and the generating functions active in ...
std::optional< ParamPoint > solveParametricEquations(FracMatrix equations)
Find the solution of a set of equations that express affine constraints between a set of variables an...
SlowMPInt abs(const SlowMPInt &x)
Redeclarations of friend declarations above to make it discoverable by lookups.
SmallVector< Fraction > Point
ConeV getDual(ConeH cone)
Given a cone in H-representation, return its dual.
QuasiPolynomial computeNumTerms(const GeneratingFunction &gf)
Find the number of terms in a generating function, as a quasipolynomial in the parameter space of the...
Point getNonOrthogonalVector(ArrayRef< Point > vectors)
Find a vector that is not orthogonal to any of the given vectors, i.e., has nonzero dot product with ...
GeneratingFunction computeUnimodularConeGeneratingFunction(ParamPoint vertex, int sign, const ConeH &cone)
Compute the generating function for a unimodular cone.
PolyhedronH defineHRep(int numVars, int numSymbols=0)
std::vector< std::pair< PresburgerSet, GeneratingFunction > > computePolytopeGeneratingFunction(const PolyhedronH &poly)
Compute the generating function corresponding to a polytope.
MPInt getIndex(const ConeV &cone)
Get the index of a cone, i.e., the volume of the parallelepiped spanned by its generators,...
QuasiPolynomial getCoefficientInRationalFunction(unsigned power, ArrayRef< QuasiPolynomial > num, ArrayRef< Fraction > den)
Find the coefficient of a given power of s in a rational function given by P(s)/Q(s),...
Fraction dotProduct(ArrayRef< Fraction > a, ArrayRef< Fraction > b)
Compute the dot product of two vectors.
std::vector< Fraction > multiplyPolynomials(ArrayRef< Fraction > a, ArrayRef< Fraction > b)
Find the product of two polynomials, each given by an array of coefficients.
MPInt floor(const Fraction &f)
Include the generated interface declarations.
A class to represent fractions.
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.