MLIR  19.0.0git
Namespaces | Classes | Enumerations | Functions
mlir::presburger Namespace Reference

Namespaces

 detail
 

Classes

struct  Fraction
 A class to represent fractions. More...
 
class  IntegerRelation
 An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine constraints. More...
 
class  IntegerPolyhedron
 An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affine constraints. More...
 
class  LinearTransform
 
class  Matrix
 This is a class to represent a resizable matrix. More...
 
class  IntMatrix
 
class  FracMatrix
 
class  MPInt
 This class provides support for multi-precision arithmetic. More...
 
class  PresburgerRelation
 A PresburgerRelation represents a union of IntegerRelations that live in the same PresburgerSpace with support for union, intersection, subtraction, and complement operations, as well as sampling. More...
 
class  PresburgerSet
 
class  Identifier
 An Identifier stores a pointer to an object, such as a Value or an Operation. More...
 
class  PresburgerSpace
 PresburgerSpace is the space of all possible values of a tuple of integer valued variables/variables. More...
 
class  MultiAffineFunction
 This class represents a multi-affine function with the domain as Z^d, where d is the number of domain variables of the function. More...
 
class  PWMAFunction
 This class represents a piece-wise MultiAffineFunction. More...
 
class  QuasiPolynomial
 
class  SimplexBase
 The Simplex class implements a version of the Simplex and Generalized Basis Reduction algorithms, which can perform analysis of integer sets with affine inequalities and equalities. More...
 
class  LexSimplexBase
 Simplex class using the lexicographic pivot rule. More...
 
class  LexSimplex
 A class for lexicographic optimization without any symbols. More...
 
struct  SymbolicLexOpt
 Represents the result of a symbolic lexicographic optimization computation. More...
 
class  SymbolicLexSimplex
 A class to perform symbolic lexicographic optimization, i.e., to find, for every assignment to the symbols the specified symbolDomain, the lexicographically minimum value integer value attained by the non-symbol variables. More...
 
class  Simplex
 The Simplex class uses the Normal pivot rule and supports integer emptiness checks as well as detecting redundancies. More...
 
class  SimplexRollbackScopeExit
 Takes a snapshot of the simplex state on construction and rolls back to the snapshot on destruction. More...
 
class  MaybeOptimum
 
struct  MaybeLocalRepr
 MaybeLocalRepr contains the indices of the constraints that can be expressed as a floordiv of an affine function. More...
 
class  DivisionRepr
 Class storing division representation of local variables of a constraint system. More...
 
class  SetCoalescer
 The SetCoalescer class contains all functionality concerning the coalesce heuristic. More...
 
class  GBRSimplex
 Given a simplex for a polytope, construct a new simplex whose variables are identified with a pair of points (x, y) in the original polytope. More...
 

Enumerations

enum class  BoundType { EQ , LB , UB }
 The type of bound: equal, lower bound or upper bound. More...
 
enum class  VarKind {
  Symbol , Local , Domain , Range ,
  SetDim = Range
}
 Kind of variable. More...
 
enum class  OrderingKind {
  EQ , NE , LT , LE ,
  GT , GE
}
 Enum representing a binary comparison operator: equal, not equal, less than, less than or equal, greater than, greater than or equal. More...
 
enum class  OptimumKind { Empty , Unbounded , Bounded }
 This class represents the result of operations optimizing something subject to some constraints. More...
 
enum class  ReprKind { Inequality , Equality , None }
 ReprKind enum is used to set the constraint type in MaybeLocalRepr. More...
 

Functions

int compare (const Fraction &x, const Fraction &y)
 Three-way comparison between two fractions. More...
 
MPInt floor (const Fraction &f)
 
MPInt ceil (const Fraction &f)
 
Fraction operator- (const Fraction &x)
 
bool operator< (const Fraction &x, const Fraction &y)
 
bool operator<= (const Fraction &x, const Fraction &y)
 
bool operator== (const Fraction &x, const Fraction &y)
 
bool operator!= (const Fraction &x, const Fraction &y)
 
bool operator> (const Fraction &x, const Fraction &y)
 
bool operator>= (const Fraction &x, const Fraction &y)
 
Fraction abs (const Fraction &f)
 
Fraction reduce (const Fraction &f)
 
Fraction operator* (const Fraction &x, const Fraction &y)
 
Fraction operator/ (const Fraction &x, const Fraction &y)
 
Fraction operator+ (const Fraction &x, const Fraction &y)
 
Fraction operator- (const Fraction &x, const Fraction &y)
 
MPInt round (const Fraction &f)
 
Fractionoperator+= (Fraction &x, const Fraction &y)
 
Fractionoperator-= (Fraction &x, const Fraction &y)
 
Fractionoperator/= (Fraction &x, const Fraction &y)
 
Fractionoperator*= (Fraction &x, const Fraction &y)
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &os, const Fraction &x)
 
llvm::hash_code hash_value (const MPInt &x)
 Redeclarations of friend declaration above to make it discoverable by lookups. More...
 
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. More...
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mpintFromInt64 (int64_t x)
 
llvm::raw_ostream & operator<< (llvm::raw_ostream &os, const MPInt &x)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mod (const MPInt &lhs, const MPInt &rhs)
 is always non-negative. More...
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt abs (const MPInt &x)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt ceilDiv (const MPInt &lhs, const MPInt &rhs)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt floorDiv (const MPInt &lhs, const MPInt &rhs)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt gcd (const MPInt &a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt lcm (const MPInt &a, const MPInt &b)
 Returns the least common multiple of 'a' and 'b'. More...
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPIntoperator+= (MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPIntoperator-= (MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPIntoperator*= (MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPIntoperator/= (MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPIntoperator%= (MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator+ (const MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator- (const MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator* (const MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator/ (const MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator% (const MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator+ (int64_t a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator- (int64_t a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator* (int64_t a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator/ (int64_t a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt operator% (int64_t a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator== (const MPInt &a, int64_t b)
 We provide special implementations of the comparison operators rather than calling through as above, as this would result in a 1.2x slowdown. More...
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator!= (const MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator> (const MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator< (const MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator<= (const MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator>= (const MPInt &a, int64_t b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator== (int64_t a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator!= (int64_t a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator> (int64_t a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator< (int64_t a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator<= (int64_t a, const MPInt &b)
 
LLVM_ATTRIBUTE_ALWAYS_INLINE bool operator>= (int64_t a, const MPInt &b)
 
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 is subject to the inequalities 0 <= expr - d*q <= c - 1 (quotient remainder theorem). More...
 
SmallVector< MPInt, 8 > getDivLowerBound (ArrayRef< MPInt > dividend, const MPInt &divisor, unsigned localVarIdx)
 
llvm::SmallBitVector getSubrangeBitVector (unsigned len, unsigned setOffset, unsigned numSet)
 
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 (where the divisor is a positive constant). More...
 
SmallVector< int64_t, 8 > getInt64Vec (ArrayRef< MPInt > range)
 Return the given array as an array of int64_t. More...
 
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 as a floordiv of an affine function. More...
 
MaybeLocalRepr computeSingleVarRepr (const IntegerRelation &cst, ArrayRef< bool > foundRepr, unsigned pos, SmallVector< int64_t, 8 > &dividend, unsigned &divisor)
 The following overload using int64_t is required for a callsite in AffineStructures.h. More...
 
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 the local vars in each set, without changing the set of points that lie in A and B. More...
 
MPInt gcdRange (ArrayRef< MPInt > range)
 Compute the gcd of the range. More...
 
MPInt normalizeRange (MutableArrayRef< MPInt > range)
 Divide the range by its gcd and return the gcd. More...
 
void normalizeDiv (MutableArrayRef< MPInt > num, MPInt &denom)
 Normalize the given (numerator, denominator) pair by dividing out the common factors between them. More...
 
SmallVector< MPInt, 8 > getNegatedCoeffs (ArrayRef< MPInt > coeffs)
 Return coeffs with all the elements negated. More...
 
SmallVector< MPInt, 8 > getComplementIneq (ArrayRef< MPInt > ineq)
 Return the complement of the given inequality. More...
 
Fraction dotProduct (ArrayRef< Fraction > a, ArrayRef< Fraction > b)
 Compute the dot product of two vectors. More...
 
std::vector< FractionmultiplyPolynomials (ArrayRef< Fraction > a, ArrayRef< Fraction > b)
 Find the product of two polynomials, each given by an array of coefficients. More...
 
bool isRangeZero (ArrayRef< Fraction > arr)
 

Enumeration Type Documentation

◆ BoundType

The type of bound: equal, lower bound or upper bound.

Enumerator
EQ 
LB 
UB 

Definition at line 35 of file IntegerRelation.h.

◆ OptimumKind

This class represents the result of operations optimizing something subject to some constraints.

If the constraints were not satisfiable the, kind will be Empty. If the optimum is unbounded, the kind is Unbounded, and if the optimum is bounded, the kind will be Bounded and optimum holds the optimal value.

Enumerator
Empty 
Unbounded 
Bounded 

Definition at line 34 of file Utils.h.

◆ OrderingKind

Enum representing a binary comparison operator: equal, not equal, less than, less than or equal, greater than, greater than or equal.

Enumerator
EQ 
NE 
LT 
LE 
GT 
GE 

Definition at line 28 of file PWMAFunction.h.

◆ ReprKind

ReprKind enum is used to set the constraint type in MaybeLocalRepr.

Enumerator
Inequality 
Equality 
None 

Definition at line 91 of file Utils.h.

◆ VarKind

Kind of variable.

Implementation wise SetDims are treated as Range vars, and spaces with no distinction between dimension vars are treated as relations with zero domain vars.

Enumerator
Symbol 
Local 
Domain 
Range 
SetDim 

Definition at line 29 of file PresburgerSpace.h.

Function Documentation

◆ abs() [1/2]

Fraction mlir::presburger::abs ( const Fraction f)
inline

◆ abs() [2/2]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::abs ( const MPInt x)

Definition at line 370 of file MPInt.h.

◆ ceil()

MPInt mlir::presburger::ceil ( const Fraction f)
inline

◆ ceilDiv()

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::ceilDiv ( const MPInt lhs,
const MPInt rhs 
)

◆ compare()

int mlir::presburger::compare ( const Fraction x,
const Fraction y 
)
inline

Three-way comparison between two fractions.

Returns +1, 0, and -1 if the first fraction is greater than, equal to, or less than the second fraction, respectively.

Definition at line 65 of file Fraction.h.

References mlir::presburger::Fraction::den, and mlir::presburger::Fraction::num.

Referenced by llvm::cl::OptionValue< mlir::OpPassManager >::compare(), mlir::impl::findAttrSorted(), mlir::getValuesSortedByKey(), matchSelectReduction(), operator!=(), operator<(), operator<=(), operator==(), operator>(), and operator>=().

◆ computeSingleVarRepr() [1/2]

MaybeLocalRepr mlir::presburger::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 as a floordiv of an affine function.

Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables (where the divisor is a positive constant).

If the representation could be computed, dividend and divisor are set, in which case, denominator will be positive. If the representation could not be computed, the kind attribute in MaybeLocalRepr is set to None.

foundRepr contains a boolean for each variable indicating if the explicit representation for that variable has already been computed. Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed as a floordiv of an affine function. If the representation could be computed, dividend and denominator are set. If the representation could not be computed, the kind attribute in MaybeLocalRepr is set to None.

Definition at line 232 of file Utils.cpp.

References checkExplicitRepresentation(), Equality, mlir::failed(), getDivRepr(), mlir::presburger::IntegerRelation::getLowerAndUpperBoundIndices(), mlir::presburger::IntegerRelation::getNumCols(), mlir::presburger::IntegerRelation::getNumVars(), Inequality, and mlir::presburger::MaybeLocalRepr::kind.

Referenced by computeSingleVarRepr(), detectAsFloorDiv(), and mlir::presburger::IntegerRelation::getLocalReprs().

◆ computeSingleVarRepr() [2/2]

MaybeLocalRepr mlir::presburger::computeSingleVarRepr ( const IntegerRelation cst,
ArrayRef< bool >  foundRepr,
unsigned  pos,
SmallVector< int64_t, 8 > &  dividend,
unsigned &  divisor 
)

The following overload using int64_t is required for a callsite in AffineStructures.h.

Definition at line 275 of file Utils.cpp.

References computeSingleVarRepr(), getInt64Vec(), and mlir::presburger::IntegerRelation::getNumCols().

◆ dotProduct()

Fraction mlir::presburger::dotProduct ( ArrayRef< Fraction a,
ArrayRef< Fraction b 
)

Compute the dot product of two vectors.

The vectors must have the same sizes.

Definition at line 533 of file Utils.cpp.

Referenced by mlir::presburger::detail::getNonOrthogonalVector(), mlir::presburger::FracMatrix::gramSchmidt(), mlir::presburger::FracMatrix::LLL(), and substituteMuInTerm().

◆ floor()

MPInt mlir::presburger::floor ( const Fraction f)
inline

◆ floorDiv()

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::floorDiv ( const MPInt lhs,
const MPInt rhs 
)

◆ gcd()

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::gcd ( const MPInt a,
const MPInt b 
)

◆ gcdRange()

MPInt mlir::presburger::gcdRange ( ArrayRef< MPInt range)

Compute the gcd of the range.

Definition at line 346 of file Utils.cpp.

References abs(), and gcd().

Referenced by normalizeDiv(), and normalizeRange().

◆ getComplementIneq()

SmallVector< MPInt, 8 > mlir::presburger::getComplementIneq ( ArrayRef< MPInt ineq)

Return the complement of the given inequality.

The complement of a_1 x_1 + ... + a_n x_ + c >= 0 is a_1 x_1 + ... + a_n x_ + c < 0, i.e., -a_1 x_1 - ... - a_n x_ - c - 1 >= 0, since all the variables are constrained to be integers.

Definition at line 381 of file Utils.cpp.

Referenced by mlir::presburger::SymbolicLexSimplex::computeSymbolicIntegerLexMin(), and mlir::presburger::LexSimplex::isRedundantInequality().

◆ getDivLowerBound()

SmallVector< MPInt, 8 > mlir::presburger::getDivLowerBound ( ArrayRef< MPInt dividend,
const MPInt divisor,
unsigned  localVarIdx 
)

◆ getDivUpperBound()

SmallVector< MPInt, 8 > mlir::presburger::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 is subject to the inequalities 0 <= expr - d*q <= c - 1 (quotient remainder theorem).

Rearranging, we get the bounds on q: d*q <= expr <= d*q + d - 1.

getDivUpperBound returns d*q <= expr, and getDivLowerBound returns expr <= d*q + d - 1.

The parameter dividend corresponds to expr above, divisor to d, and localVarIdx to the position of q in the coefficient list.

The coefficient of q in dividend must be zero, as it is not allowed for local variable to be a floor division of an expression involving itself. The divisor must be positive.

Definition at line 321 of file Utils.cpp.

Referenced by addDivisionConstraints(), mlir::presburger::IntegerRelation::addLocalFloorDiv(), and mlir::presburger::MultiAffineFunction::getLexSet().

◆ getInt64Vec()

SmallVector< int64_t, 8 > mlir::presburger::getInt64Vec ( ArrayRef< MPInt range)

◆ getMPIntVec()

SmallVector< MPInt, 8 > mlir::presburger::getMPIntVec ( ArrayRef< int64_t >  range)

Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables (where the divisor is a positive constant).

foundRepr contains a boolean for each variable indicating if the explicit representation for that variable has already been computed. Return the given array as an array of MPInts.

Definition at line 521 of file Utils.cpp.

References mpintFromInt64().

Referenced by mlir::presburger::IntegerRelation::addBound(), mlir::presburger::IntegerRelation::addEquality(), mlir::presburger::IntegerRelation::addInequality(), mlir::presburger::IntegerRelation::addLocalFloorDiv(), mlir::presburger::IntegerRelation::containsPoint(), mlir::presburger::PresburgerRelation::containsPoint(), mlir::presburger::IntegerRelation::containsPointNoLocal(), mlir::presburger::IntegerRelation::setAndEliminate(), mlir::presburger::MultiAffineFunction::valueAt(), and mlir::presburger::PWMAFunction::valueAt().

◆ getNegatedCoeffs()

SmallVector< MPInt, 8 > mlir::presburger::getNegatedCoeffs ( ArrayRef< MPInt coeffs)

Return coeffs with all the elements negated.

Definition at line 373 of file Utils.cpp.

Referenced by getIneqCoeffsFromIdx().

◆ getSubrangeBitVector()

llvm::SmallBitVector mlir::presburger::getSubrangeBitVector ( unsigned  len,
unsigned  setOffset,
unsigned  numSet 
)

Definition at line 287 of file Utils.cpp.

◆ hash_value()

llvm::hash_code mlir::presburger::hash_value ( const MPInt x)

◆ int64FromMPInt()

static int64_t mlir::presburger::int64FromMPInt ( const MPInt x)
inlinestatic

This just calls through to the operator int64_t, but it's useful when a function pointer is required.

(Although this is marked inline, it is still possible to obtain and use a function pointer to this.)

Definition at line 261 of file MPInt.h.

Referenced by mlir::presburger::IntegerRelation::computeConstantLowerOrUpperBound64(), mlir::presburger::IntegerRelation::getConstantBound64(), mlir::presburger::IntegerRelation::getConstantBoundOnDimSize64(), and getInt64Vec().

◆ isRangeZero()

bool mlir::presburger::isRangeZero ( ArrayRef< Fraction arr)

Definition at line 569 of file Utils.cpp.

◆ lcm()

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::lcm ( const MPInt a,
const MPInt b 
)

◆ mergeLocalVars()

void mlir::presburger::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 the local vars in each set, without changing the set of points that lie in A and B.

While taking union, if a local var in any set has a division representation which is a duplicate of division representation, of another local var in any set, it is not added to the final union of local vars and is instead merged.

On every possible merge, merge(i, j) is called. i, j are position of local variables in both sets which are being merged. If merge(i, j) returns true, the divisions are merged, otherwise the divisions are not merged.

Definition at line 295 of file Utils.cpp.

References mlir::presburger::DivisionRepr::getDenom(), mlir::presburger::DivisionRepr::getDividend(), mlir::presburger::IntegerRelation::getLocalReprs(), mlir::presburger::DivisionRepr::getNumDivs(), mlir::presburger::IntegerRelation::getNumLocalVars(), mlir::presburger::IntegerRelation::getSpace(), mlir::presburger::IntegerRelation::insertVar(), mlir::presburger::PresburgerSpace::isCompatible(), Local, mlir::presburger::DivisionRepr::removeDuplicateDivs(), and mlir::presburger::DivisionRepr::setDiv().

Referenced by mlir::affine::FlatAffineRelation::compose(), and mlir::presburger::IntegerRelation::mergeLocalVars().

◆ mod()

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::mod ( const MPInt lhs,
const MPInt rhs 
)

is always non-negative.

Definition at line 393 of file MPInt.h.

Referenced by mlir::presburger::LexSimplexBase::addCut().

◆ mpintFromInt64()

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::mpintFromInt64 ( int64_t  x)

Definition at line 262 of file MPInt.h.

Referenced by getMPIntVec().

◆ multiplyPolynomials()

std::vector< Fraction > mlir::presburger::multiplyPolynomials ( ArrayRef< Fraction a,
ArrayRef< Fraction b 
)

Find the product of two polynomials, each given by an array of coefficients.

Find the product of two polynomials, each given by an array of coefficients, by taking the convolution.

Definition at line 544 of file Utils.cpp.

Referenced by mlir::presburger::detail::computeNumTerms().

◆ normalizeDiv()

void mlir::presburger::normalizeDiv ( MutableArrayRef< MPInt num,
MPInt denom 
)

Normalize the given (numerator, denominator) pair by dividing out the common factors between them.

The numerator here is an affine expression with integer coefficients. The denominator must be positive.

Definition at line 365 of file Utils.cpp.

References gcd(), and gcdRange().

Referenced by mlir::presburger::DivisionRepr::normalizeDivs().

◆ normalizeRange()

MPInt mlir::presburger::normalizeRange ( MutableArrayRef< MPInt range)

Divide the range by its gcd and return the gcd.

Definition at line 356 of file Utils.cpp.

References gcd(), and gcdRange().

Referenced by mlir::presburger::SymbolicLexSimplex::computeSymbolicIntegerLexMin(), and mlir::presburger::IntMatrix::normalizeRow().

◆ operator!=() [1/3]

bool mlir::presburger::operator!= ( const Fraction x,
const Fraction y 
)
inline

Definition at line 92 of file Fraction.h.

References compare().

◆ operator!=() [2/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator!= ( const MPInt a,
int64_t  b 
)

Definition at line 558 of file MPInt.h.

◆ operator!=() [3/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator!= ( int64_t  a,
const MPInt b 
)

Definition at line 588 of file MPInt.h.

◆ operator%() [1/2]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::operator% ( const MPInt a,
int64_t  b 
)

Definition at line 532 of file MPInt.h.

◆ operator%() [2/2]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::operator% ( int64_t  a,
const MPInt b 
)

Definition at line 547 of file MPInt.h.

◆ operator%=()

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt& mlir::presburger::operator%= ( MPInt a,
int64_t  b 
)

Definition at line 517 of file MPInt.h.

◆ operator*() [1/3]

Fraction mlir::presburger::operator* ( const Fraction x,
const Fraction y 
)
inline

◆ operator*() [2/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::operator* ( const MPInt a,
int64_t  b 
)

Definition at line 526 of file MPInt.h.

◆ operator*() [3/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::operator* ( int64_t  a,
const MPInt b 
)

Definition at line 541 of file MPInt.h.

◆ operator*=() [1/2]

Fraction& mlir::presburger::operator*= ( Fraction x,
const Fraction y 
)
inline

Definition at line 153 of file Fraction.h.

◆ operator*=() [2/2]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt& mlir::presburger::operator*= ( MPInt a,
int64_t  b 
)

Definition at line 511 of file MPInt.h.

◆ operator+() [1/3]

Fraction mlir::presburger::operator+ ( const Fraction x,
const Fraction y 
)
inline

◆ operator+() [2/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::operator+ ( const MPInt a,
int64_t  b 
)

Definition at line 520 of file MPInt.h.

◆ operator+() [3/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::operator+ ( int64_t  a,
const MPInt b 
)

Definition at line 535 of file MPInt.h.

◆ operator+=() [1/2]

Fraction& mlir::presburger::operator+= ( Fraction x,
const Fraction y 
)
inline

Definition at line 138 of file Fraction.h.

◆ operator+=() [2/2]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt& mlir::presburger::operator+= ( MPInt a,
int64_t  b 
)

Convenience operator overloads for int64_t.

Definition at line 505 of file MPInt.h.

◆ operator-() [1/4]

Fraction mlir::presburger::operator- ( const Fraction x)
inline

Definition at line 78 of file Fraction.h.

References mlir::presburger::Fraction::den, and mlir::presburger::Fraction::num.

◆ operator-() [2/4]

Fraction mlir::presburger::operator- ( const Fraction x,
const Fraction y 
)
inline

◆ operator-() [3/4]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::operator- ( const MPInt a,
int64_t  b 
)

Definition at line 523 of file MPInt.h.

◆ operator-() [4/4]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::operator- ( int64_t  a,
const MPInt b 
)

Definition at line 538 of file MPInt.h.

◆ operator-=() [1/2]

Fraction& mlir::presburger::operator-= ( Fraction x,
const Fraction y 
)
inline

Definition at line 143 of file Fraction.h.

◆ operator-=() [2/2]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt& mlir::presburger::operator-= ( MPInt a,
int64_t  b 
)

Definition at line 508 of file MPInt.h.

◆ operator/() [1/3]

Fraction mlir::presburger::operator/ ( const Fraction x,
const Fraction y 
)
inline

◆ operator/() [2/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::operator/ ( const MPInt a,
int64_t  b 
)

Definition at line 529 of file MPInt.h.

◆ operator/() [3/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mlir::presburger::operator/ ( int64_t  a,
const MPInt b 
)

Definition at line 544 of file MPInt.h.

◆ operator/=() [1/2]

Fraction& mlir::presburger::operator/= ( Fraction x,
const Fraction y 
)
inline

Definition at line 148 of file Fraction.h.

◆ operator/=() [2/2]

LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt& mlir::presburger::operator/= ( MPInt a,
int64_t  b 
)

Definition at line 514 of file MPInt.h.

◆ operator<() [1/3]

bool mlir::presburger::operator< ( const Fraction x,
const Fraction y 
)
inline

◆ operator<() [2/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator< ( const MPInt a,
int64_t  b 
)

Definition at line 568 of file MPInt.h.

◆ operator<() [3/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator< ( int64_t  a,
const MPInt b 
)

Definition at line 598 of file MPInt.h.

◆ operator<<() [1/2]

llvm::raw_ostream& mlir::presburger::operator<< ( llvm::raw_ostream &  os,
const Fraction x 
)
inline

Definition at line 158 of file Fraction.h.

References mlir::presburger::Fraction::print().

◆ operator<<() [2/2]

llvm::raw_ostream & mlir::presburger::operator<< ( llvm::raw_ostream &  os,
const MPInt x 
)

Definition at line 34 of file MPInt.cpp.

References mlir::presburger::MPInt::print().

◆ operator<=() [1/3]

bool mlir::presburger::operator<= ( const Fraction x,
const Fraction y 
)
inline

Definition at line 84 of file Fraction.h.

References compare().

Referenced by mlir::ValueBoundsConstraintSet::BoundBuilder::operator<=().

◆ operator<=() [2/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator<= ( const MPInt a,
int64_t  b 
)

Definition at line 573 of file MPInt.h.

◆ operator<=() [3/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator<= ( int64_t  a,
const MPInt b 
)

Definition at line 603 of file MPInt.h.

◆ operator==() [1/3]

bool mlir::presburger::operator== ( const Fraction x,
const Fraction y 
)
inline

Definition at line 88 of file Fraction.h.

References compare().

◆ operator==() [2/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator== ( const MPInt a,
int64_t  b 
)

We provide special implementations of the comparison operators rather than calling through as above, as this would result in a 1.2x slowdown.

Definition at line 553 of file MPInt.h.

◆ operator==() [3/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator== ( int64_t  a,
const MPInt b 
)

Definition at line 583 of file MPInt.h.

◆ operator>() [1/3]

bool mlir::presburger::operator> ( const Fraction x,
const Fraction y 
)
inline

Definition at line 96 of file Fraction.h.

References compare().

Referenced by mlir::ValueBoundsConstraintSet::BoundBuilder::operator>().

◆ operator>() [2/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator> ( const MPInt a,
int64_t  b 
)

Definition at line 563 of file MPInt.h.

◆ operator>() [3/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator> ( int64_t  a,
const MPInt b 
)

Definition at line 593 of file MPInt.h.

◆ operator>=() [1/3]

bool mlir::presburger::operator>= ( const Fraction x,
const Fraction y 
)
inline

◆ operator>=() [2/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator>= ( const MPInt a,
int64_t  b 
)

Definition at line 578 of file MPInt.h.

◆ operator>=() [3/3]

LLVM_ATTRIBUTE_ALWAYS_INLINE bool mlir::presburger::operator>= ( int64_t  a,
const MPInt b 
)

Definition at line 608 of file MPInt.h.

◆ reduce()

Fraction mlir::presburger::reduce ( const Fraction f)
inline

◆ round()

MPInt mlir::presburger::round ( const Fraction f)
inline