MLIR
19.0.0git
|
Classes | |
class | GeneratingFunction |
class | SlowMPInt |
A simple class providing multi-precision arithmetic. More... | |
Typedefs | |
using | PolyhedronH = IntegerRelation |
A polyhedron in H-representation is a set of inequalities in d variables with integer coefficients. More... | |
using | PolyhedronV = IntMatrix |
A polyhedron in V-representation is a set of rays and points, i.e., vectors, stored as rows of a matrix. More... | |
using | ConeH = PolyhedronH |
A cone in either representation is a special case of a polyhedron in that representation. More... | |
using | ConeV = PolyhedronV |
using | ParamPoint = FracMatrix |
using | Point = SmallVector< Fraction > |
Functions | |
PolyhedronH | defineHRep (int numVars, int numSymbols=0) |
MPInt | getIndex (const ConeV &cone) |
Get the index of a cone, i.e., the volume of the parallelepiped spanned by its generators, which is equal to the number of integer points in its fundamental parallelepiped. More... | |
ConeV | getDual (ConeH cone) |
Given a cone in H-representation, return its dual. More... | |
ConeH | getDual (ConeV cone) |
Given a cone in V-representation, return its dual. More... | |
GeneratingFunction | computeUnimodularConeGeneratingFunction (ParamPoint vertex, int sign, const ConeH &cone) |
Compute the generating function for a unimodular cone. More... | |
std::optional< ParamPoint > | solveParametricEquations (FracMatrix equations) |
Find the solution of a set of equations that express affine constraints between a set of variables and a set of parameters. More... | |
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 each region, produce a pairwise disjoint list of regions (chambers) and identify the generating function of the polytope in each chamber. More... | |
std::vector< std::pair< PresburgerSet, GeneratingFunction > > | computePolytopeGeneratingFunction (const PolyhedronH &poly) |
Compute the generating function corresponding to a polytope. More... | |
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 those of the given vectors that are not null. More... | |
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), where P is a polynomial, in which the coefficients are QuasiPolynomials over d parameters (distinct from s), and and Q is a polynomial with Fraction coefficients. More... | |
QuasiPolynomial | computeNumTerms (const GeneratingFunction &gf) |
Find the number of terms in a generating function, as a quasipolynomial in the parameter space of the input function. More... | |
LLVM_ATTRIBUTE_ALWAYS_INLINE bool | addOverflow (int64_t x, int64_t y, int64_t &result) |
If builtin intrinsics for overflow-checked arithmetic are available, use them. More... | |
LLVM_ATTRIBUTE_ALWAYS_INLINE bool | subOverflow (int64_t x, int64_t y, int64_t &result) |
LLVM_ATTRIBUTE_ALWAYS_INLINE bool | mulOverflow (int64_t x, int64_t y, int64_t &result) |
LLVM_ATTRIBUTE_ALWAYS_INLINE bool | divWouldOverflow (int64_t x, int64_t y) |
llvm::raw_ostream & | operator<< (llvm::raw_ostream &os, const SlowMPInt &x) |
SlowMPInt | mod (const SlowMPInt &lhs, const SlowMPInt &rhs) |
Returns the remainder of dividing LHS by RHS. More... | |
SlowMPInt | lcm (const SlowMPInt &a, const SlowMPInt &b) |
Returns the least common multiple of 'a' and 'b'. More... | |
SlowMPInt | abs (const SlowMPInt &x) |
Redeclarations of friend declarations above to make it discoverable by lookups. More... | |
SlowMPInt | ceilDiv (const SlowMPInt &lhs, const SlowMPInt &rhs) |
SlowMPInt | floorDiv (const SlowMPInt &lhs, const SlowMPInt &rhs) |
SlowMPInt | gcd (const SlowMPInt &a, const SlowMPInt &b) |
llvm::hash_code | hash_value (const SlowMPInt &x) |
SlowMPInt & | operator+= (SlowMPInt &a, int64_t b) |
SlowMPInt & | operator-= (SlowMPInt &a, int64_t b) |
SlowMPInt & | operator*= (SlowMPInt &a, int64_t b) |
SlowMPInt & | operator/= (SlowMPInt &a, int64_t b) |
SlowMPInt & | operator%= (SlowMPInt &a, int64_t b) |
bool | operator== (const SlowMPInt &a, int64_t b) |
bool | operator!= (const SlowMPInt &a, int64_t b) |
bool | operator> (const SlowMPInt &a, int64_t b) |
bool | operator< (const SlowMPInt &a, int64_t b) |
bool | operator<= (const SlowMPInt &a, int64_t b) |
bool | operator>= (const SlowMPInt &a, int64_t b) |
SlowMPInt | operator+ (const SlowMPInt &a, int64_t b) |
SlowMPInt | operator- (const SlowMPInt &a, int64_t b) |
SlowMPInt | operator* (const SlowMPInt &a, int64_t b) |
SlowMPInt | operator/ (const SlowMPInt &a, int64_t b) |
SlowMPInt | operator% (const SlowMPInt &a, int64_t b) |
bool | operator== (int64_t a, const SlowMPInt &b) |
bool | operator!= (int64_t a, const SlowMPInt &b) |
bool | operator> (int64_t a, const SlowMPInt &b) |
bool | operator< (int64_t a, const SlowMPInt &b) |
bool | operator<= (int64_t a, const SlowMPInt &b) |
bool | operator>= (int64_t a, const SlowMPInt &b) |
SlowMPInt | operator+ (int64_t a, const SlowMPInt &b) |
SlowMPInt | operator- (int64_t a, const SlowMPInt &b) |
SlowMPInt | operator* (int64_t a, const SlowMPInt &b) |
SlowMPInt | operator/ (int64_t a, const SlowMPInt &b) |
SlowMPInt | operator% (int64_t a, const SlowMPInt &b) |
using mlir::presburger::detail::ConeH = typedef PolyhedronH |
A cone in either representation is a special case of a polyhedron in that representation.
Definition at line 49 of file Barvinok.h.
using mlir::presburger::detail::ConeV = typedef PolyhedronV |
Definition at line 50 of file Barvinok.h.
using mlir::presburger::detail::ParamPoint = typedef FracMatrix |
Definition at line 28 of file GeneratingFunction.h.
using mlir::presburger::detail::Point = typedef SmallVector<Fraction> |
Definition at line 31 of file GeneratingFunction.h.
using mlir::presburger::detail::PolyhedronH = typedef IntegerRelation |
A polyhedron in H-representation is a set of inequalities in d variables with integer coefficients.
Definition at line 41 of file Barvinok.h.
using mlir::presburger::detail::PolyhedronV = typedef IntMatrix |
A polyhedron in V-representation is a set of rays and points, i.e., vectors, stored as rows of a matrix.
Definition at line 45 of file Barvinok.h.
Redeclarations of friend declarations above to make it discoverable by lookups.
Referenced by computeNumTerms(), and computeUnimodularConeGeneratingFunction().
LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::detail::addOverflow | ( | int64_t | x, |
int64_t | y, | ||
int64_t & | result | ||
) |
If builtin intrinsics for overflow-checked arithmetic are available, use them.
Otherwise, call through to LLVM's overflow-checked arithmetic functionality. Those functions also have such macro-gated uses of intrinsics but they are not always_inlined, which is important for us to achieve high-performance; calling the functions directly would result in a slowdown of 1.15x.
Definition at line 45 of file MPInt.h.
Referenced by mlir::presburger::MPInt::operator+(), and mlir::presburger::MPInt::operator+=().
std::vector< std::pair< PresburgerSet, GeneratingFunction > > mlir::presburger::detail::computeChamberDecomposition | ( | unsigned | numSymbols, |
ArrayRef< std::pair< PresburgerSet, GeneratingFunction >> | regionsAndGeneratingFunctions | ||
) |
Given a list of possibly intersecting regions (PresburgerSet) and the generating functions active in each region, produce a pairwise disjoint list of regions (chambers) and identify the generating function of the polytope in each chamber.
This is an implementation of the Clauss-Loechner algorithm for chamber decomposition.
"Disjoint" here means that the intersection of two chambers is no full- dimensional.
The returned list partitions the universe into parts depending on which subset of GFs is active there, and gives the sum of active GFs for each part.
We maintain a list of pairwise disjoint chambers and the generating functions corresponding to each one. We iterate over the list of regions, each time adding the current region's generating function to the chambers where it is active and separating the chambers where it is not.
Given the region each generating function is active in, for each subset of generating functions the region that (the sum of) precisely this subset is in, is the intersection of the regions that these are active in, intersected with the complements of the remaining regions.
Definition at line 241 of file Barvinok.cpp.
References mlir::presburger::PresburgerSpace::getSetSpace(), mlir::presburger::PresburgerSet::getUniverse(), mlir::presburger::PresburgerSet::intersect(), and mlir::presburger::PresburgerRelation::isFullDim().
Referenced by computePolytopeGeneratingFunction().
QuasiPolynomial mlir::presburger::detail::computeNumTerms | ( | const GeneratingFunction & | gf | ) |
Find the number of terms in a generating function, as a quasipolynomial in the parameter space of the input function.
We have a generating function of the form f_p(x) = \sum_i sign_i * (x^n_i(p)) / (\prod_j (1 - x^d_{ij})
The generating function must be such that for all values of the parameters, the number of terms is finite.
where sign_i is ±1, n_i \in Q^p -> Q^d is the sum of the vectors d_{ij}, weighted by the floors of d affine functions on p parameters. d_{ij} \in Q^d are vectors.
We need to find the number of terms of the form x^t in the expansion of this function. However, direct substitution (x = (1, ..., 1)) causes the denominator to become zero.
We therefore use the following procedure instead:
Verdoolaege, Sven, et al. "Counting integer points in parametric polytopes using Barvinok's rational functions." Algorithmica 48 (2007): 37-66.
Definition at line 690 of file Barvinok.cpp.
References abs(), getBinomialCoefficients(), getCoefficientInRationalFunction(), mlir::presburger::detail::GeneratingFunction::getDenominators(), getNonOrthogonalVector(), mlir::presburger::detail::GeneratingFunction::getNumerators(), mlir::presburger::detail::GeneratingFunction::getNumParams(), mlir::presburger::detail::GeneratingFunction::getSigns(), mlir::presburger::multiplyPolynomials(), normalizeDenominatorExponents(), mlir::presburger::QuasiPolynomial::simplify(), and substituteMuInTerm().
std::vector< std::pair< PresburgerSet, GeneratingFunction > > mlir::presburger::detail::computePolytopeGeneratingFunction | ( | const PolyhedronH & | poly | ) |
Compute the generating function corresponding to a polytope.
For a polytope expressed as a set of n inequalities, compute the generating function corresponding to the lattice points included in the polytope.
All tangent cones of the polytope must be unimodular.
This algorithm has three main steps:
Verdoolaege, Sven, et al. "Counting integer points in parametric polytopes using Barvinok's rational functions." Algorithmica 48 (2007): 37-66.
Definition at line 314 of file Barvinok.cpp.
References mlir::presburger::IntegerRelation::addInequality(), mlir::presburger::Matrix< T >::addToRow(), computeChamberDecomposition(), computeUnimodularConeGeneratingFunction(), defineHRep(), mlir::presburger::IntegerRelation::getInequalities(), mlir::presburger::IntegerRelation::getNumInequalities(), mlir::presburger::IntegerRelation::getNumRangeVars(), mlir::presburger::IntegerRelation::getNumSymbolVars(), mlir::presburger::PresburgerSpace::getRelationSpace(), mlir::presburger::Matrix< T >::getRow(), mlir::presburger::Matrix< T >::setRow(), solveParametricEquations(), and mlir::presburger::Matrix< T >::splitByBitset().
GeneratingFunction mlir::presburger::detail::computeUnimodularConeGeneratingFunction | ( | ParamPoint | vertex, |
int | sign, | ||
const ConeH & | cone | ||
) |
Compute the generating function for a unimodular cone.
The input cone must be unimodular; it assert-fails otherwise.
This consists of a single term of the form sign * x^num / prod_j (1 - x^den_j)
sign is either +1 or -1. den_j is defined as the set of generators of the cone. num is computed by expressing the vertex as a weighted sum of the generators, and then taking the floor of the coefficients.
Definition at line 81 of file Barvinok.cpp.
References abs(), mlir::presburger::FracMatrix::determinant(), getDual(), getIndex(), mlir::presburger::IntegerRelation::getInequalities(), mlir::presburger::Matrix< T >::getNumColumns(), mlir::presburger::IntegerRelation::getNumInequalities(), mlir::presburger::Matrix< T >::getNumRows(), mlir::presburger::IntegerRelation::getNumVars(), mlir::presburger::Matrix< T >::getRow(), mlir::presburger::Matrix< T >::negateRow(), mlir::presburger::Matrix< T >::preMultiplyWithRow(), mlir::presburger::Matrix< T >::removeRow(), mlir::presburger::Matrix< T >::setRow(), and mlir::presburger::Matrix< T >::transpose().
Referenced by computePolytopeGeneratingFunction().
|
inline |
Definition at line 52 of file Barvinok.h.
References mlir::presburger::PresburgerSpace::getSetSpace().
Referenced by computePolytopeGeneratingFunction(), and getDual().
LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::detail::divWouldOverflow | ( | int64_t | x, |
int64_t | y | ||
) |
Definition at line 274 of file MPInt.h.
References min().
Referenced by mlir::presburger::MPInt::operator/(), and mlir::presburger::MPInt::operator/=().
QuasiPolynomial mlir::presburger::detail::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), where P is a polynomial, in which the coefficients are QuasiPolynomials over d parameters (distinct from s), and and Q is a polynomial with Fraction coefficients.
We use the following recursive formula to find the coefficient of s^power in the rational function given by P(s)/Q(s).
Let P[i] denote the coefficient of s^i in the polynomial P(s). (P/Q)[r] = if (r == 0) then P[0]/Q[0] else (P[r] - {Σ_{i=1}^r (P/Q)[r-i] * Q[i])}/(Q[0]) We therefore recursively call getCoefficientInRationalFunction
on all i \in [0, power).
https://math.ucdavis.edu/~deloera/researchsummary/ barvinokalgorithm-latte1.pdf, p. 1285
Definition at line 516 of file Barvinok.cpp.
Referenced by computeNumTerms().
Given a cone in H-representation, return its dual.
Assuming that the input cone is pointed at the origin, converts it to its dual in V-representation.
The dual cone is in V-representation. This assumes that the input is pointed at the origin; it assert-fails otherwise.
Essentially we just remove the all-zeroes constant column.
Definition at line 22 of file Barvinok.cpp.
References mlir::presburger::Matrix< T >::at(), mlir::presburger::IntegerRelation::atIneq(), mlir::presburger::IntegerRelation::getNumCols(), and mlir::presburger::IntegerRelation::getNumInequalities().
Referenced by computeUnimodularConeGeneratingFunction().
Given a cone in V-representation, return its dual.
Converts a cone in V-representation to the H-representation of its dual, pointed at the origin (not at the original vertex).
The dual cone is in H-representation. The returned cone is pointed at the origin.
Essentially adds a column consisting only of zeroes to the end.
Definition at line 47 of file Barvinok.cpp.
References mlir::presburger::IntegerRelation::addInequality(), defineHRep(), mlir::presburger::Matrix< T >::getNumColumns(), mlir::presburger::Matrix< T >::getNumRows(), mlir::presburger::Matrix< T >::getRow(), and mlir::presburger::Matrix< T >::insertColumn().
Get the index of a cone, i.e., the volume of the parallelepiped spanned by its generators, which is equal to the number of integer points in its fundamental parallelepiped.
Find the index of a cone in V-representation.
If the index is 1, the cone is unimodular. Barvinok, A., and J. E. Pommersheim. "An algorithmic theory of lattice points in polyhedra." p. 107 If it has more rays than the dimension, return 0.
Definition at line 64 of file Barvinok.cpp.
References mlir::presburger::IntMatrix::determinant(), mlir::presburger::Matrix< T >::getNumColumns(), and mlir::presburger::Matrix< T >::getNumRows().
Referenced by computeUnimodularConeGeneratingFunction().
Find a vector that is not orthogonal to any of the given vectors, i.e., has nonzero dot product with those of the given vectors that are not null.
We use an iterative procedure to find a vector not orthogonal to a given set, ignoring the null vectors.
If any of the vectors is null, it is ignored.
Let the inputs be {x_1, ..., x_k}, all vectors of length n.
In the following, vs[:i] means the elements of vs up to and including the i'th one, <vs, us> means the dot product of vs and us, vs ++ [v] means the vector vs with the new element v appended to it.
We proceed iteratively; for steps d = 0, ... n-1, we construct a vector which is not orthogonal to any of {x_1[:d], ..., x_n[:d]}, ignoring the null vectors. At step d = 0, we let vs = [1]. Clearly this is not orthogonal to any vector in the set {x_1[0], ..., x_n[0]}, except the null ones, which we ignore. At step d > 0 , we need a number v s.t. <x_i[:d], vs++[v]> != 0 for all i. => <x_i[:d-1], vs> + x_i[d]*v != 0 => v != - <x_i[:d-1], vs> / x_i[d] We compute this value for all x_i, and then set v to be the maximum element of this set plus one. Thus v is outside the set as desired, and we append it to vs to obtain the result of the d'th step.
Definition at line 473 of file Barvinok.cpp.
References mlir::presburger::dotProduct(), and max().
Referenced by computeNumTerms().
llvm::hash_code mlir::presburger::detail::hash_value | ( | const SlowMPInt & | x | ) |
Referenced by mlir::presburger::hash_value().
Returns the least common multiple of 'a' and 'b'.
Returns the remainder of dividing LHS by RHS.
The RHS is always expected to be positive, and the result is always non-negative.
LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::detail::mulOverflow | ( | int64_t | x, |
int64_t | y, | ||
int64_t & | result | ||
) |
Definition at line 61 of file MPInt.h.
Referenced by mlir::presburger::MPInt::operator*(), and mlir::presburger::MPInt::operator*=().
bool mlir::presburger::detail::operator!= | ( | const SlowMPInt & | a, |
int64_t | b | ||
) |
bool mlir::presburger::detail::operator!= | ( | int64_t | a, |
const SlowMPInt & | b | ||
) |
bool mlir::presburger::detail::operator< | ( | const SlowMPInt & | a, |
int64_t | b | ||
) |
bool mlir::presburger::detail::operator< | ( | int64_t | a, |
const SlowMPInt & | b | ||
) |
llvm::raw_ostream& mlir::presburger::detail::operator<< | ( | llvm::raw_ostream & | os, |
const SlowMPInt & | x | ||
) |
bool mlir::presburger::detail::operator<= | ( | const SlowMPInt & | a, |
int64_t | b | ||
) |
bool mlir::presburger::detail::operator<= | ( | int64_t | a, |
const SlowMPInt & | b | ||
) |
bool mlir::presburger::detail::operator== | ( | const SlowMPInt & | a, |
int64_t | b | ||
) |
bool mlir::presburger::detail::operator== | ( | int64_t | a, |
const SlowMPInt & | b | ||
) |
bool mlir::presburger::detail::operator> | ( | const SlowMPInt & | a, |
int64_t | b | ||
) |
bool mlir::presburger::detail::operator> | ( | int64_t | a, |
const SlowMPInt & | b | ||
) |
bool mlir::presburger::detail::operator>= | ( | const SlowMPInt & | a, |
int64_t | b | ||
) |
bool mlir::presburger::detail::operator>= | ( | int64_t | a, |
const SlowMPInt & | b | ||
) |
std::optional< ParamPoint > mlir::presburger::detail::solveParametricEquations | ( | FracMatrix | equations | ) |
Find the solution of a set of equations that express affine constraints between a set of variables and a set of parameters.
We use Gaussian elimination to find the solution to a set of d equations of the form a_1 x_1 + ...
The solution expresses each variable as an affine function of the parameters.
If there is no solution, return null.
The solution expresses each x_i as an affine function of the m_i, and is therefore represented as a matrix of size d x (p+1). If there is no solution, we return null.
Definition at line 163 of file Barvinok.cpp.
References mlir::presburger::Matrix< T >::addToRow(), mlir::presburger::FracMatrix::determinant(), mlir::presburger::Matrix< T >::getNumColumns(), mlir::presburger::Matrix< T >::getNumRows(), mlir::presburger::Matrix< T >::getSubMatrix(), mlir::presburger::Matrix< T >::negateMatrix(), mlir::presburger::Matrix< T >::scaleRow(), and mlir::presburger::Matrix< T >::swapRows().
Referenced by computePolytopeGeneratingFunction().
LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::detail::subOverflow | ( | int64_t | x, |
int64_t | y, | ||
int64_t & | result | ||
) |
Definition at line 53 of file MPInt.h.
Referenced by mlir::presburger::MPInt::operator-(), and mlir::presburger::MPInt::operator-=().