MLIR  16.0.0git
Classes | Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes | Static Protected Attributes | List of all members
mlir::presburger::IntegerRelation Class Reference

An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine constraints. More...

#include "mlir/Analysis/Presburger/IntegerRelation.h"

+ Inheritance diagram for mlir::presburger::IntegerRelation:
+ Collaboration diagram for mlir::presburger::IntegerRelation:

Classes

struct  CountsSnapshot
 The struct CountsSnapshot stores the count of each VarKind, and also of each constraint type. More...
 

Public Types

enum  Kind { Kind::FlatAffineConstraints, Kind::FlatAffineValueConstraints, Kind::IntegerRelation, Kind::IntegerPolyhedron }
 All derived classes of IntegerRelation. More...
 
enum  BoundType { EQ, LB, UB }
 The type of bound: equal, lower bound or upper bound. More...
 

Public Member Functions

 IntegerRelation (unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, const PresburgerSpace &space)
 Constructs a relation reserving memory for the specified number of constraints and variables. More...
 
 IntegerRelation (const PresburgerSpace &space)
 Constructs a relation with the specified number of dimensions and symbols. More...
 
virtual ~IntegerRelation ()=default
 
virtual Kind getKind () const
 Return the kind of this IntegerRelation. More...
 
std::unique_ptr< IntegerRelationclone () const
 
const PresburgerSpacegetSpace () const
 Returns a reference to the underlying space. More...
 
void setSpace (const PresburgerSpace &oSpace)
 Set the space to oSpace, which should have the same number of ids as the current space. More...
 
void setSpaceExceptLocals (const PresburgerSpace &oSpace)
 Set the space to oSpace, which should not have any local ids. More...
 
PresburgerSpace getSpaceWithoutLocals () const
 Returns a copy of the space without locals. More...
 
void append (const IntegerRelation &other)
 Appends constraints from other into this. More...
 
IntegerRelation intersect (IntegerRelation other) const
 Return the intersection of the two relations. More...
 
bool isEqual (const IntegerRelation &other) const
 Return whether this and other are equal. More...
 
bool isSubsetOf (const IntegerRelation &other) const
 Return whether this is a subset of the given IntegerRelation. More...
 
int64_t atEq (unsigned i, unsigned j) const
 Returns the value at the specified equality row and column. More...
 
int64_t & atEq (unsigned i, unsigned j)
 
int64_t atIneq (unsigned i, unsigned j) const
 Returns the value at the specified inequality row and column. More...
 
int64_t & atIneq (unsigned i, unsigned j)
 
unsigned getNumConstraints () const
 
unsigned getNumDomainVars () const
 
unsigned getNumRangeVars () const
 
unsigned getNumSymbolVars () const
 
unsigned getNumLocalVars () const
 
unsigned getNumDimVars () const
 
unsigned getNumDimAndSymbolVars () const
 
unsigned getNumVars () const
 
unsigned getNumCols () const
 Returns the number of columns in the constraint system. More...
 
unsigned getNumEqualities () const
 
unsigned getNumInequalities () const
 
unsigned getNumReservedEqualities () const
 
unsigned getNumReservedInequalities () const
 
ArrayRef< int64_t > getEquality (unsigned idx) const
 
ArrayRef< int64_t > getInequality (unsigned idx) const
 
unsigned getNumVarKind (VarKind kind) const
 Get the number of vars of the specified kind. More...
 
unsigned getVarKindOffset (VarKind kind) const
 Return the index at which the specified kind of vars starts. More...
 
unsigned getVarKindEnd (VarKind kind) const
 Return the index at Which the specified kind of vars ends. More...
 
unsigned getVarKindOverlap (VarKind kind, unsigned varStart, unsigned varLimit) const
 Get the number of elements of the specified kind in the range [varStart, varLimit). More...
 
VarKind getVarKindAt (unsigned pos) const
 Return the VarKind of the var at the specified position. More...
 
CountsSnapshot getCounts () const
 
void truncate (const CountsSnapshot &counts)
 
virtual unsigned insertVar (VarKind kind, unsigned pos, unsigned num=1)
 Insert num variables of the specified kind at position pos. More...
 
unsigned appendVar (VarKind kind, unsigned num=1)
 Append num variables of the specified kind after the last variable of that kind. More...
 
void addInequality (ArrayRef< int64_t > inEq)
 Adds an inequality (>= 0) from the coefficients specified in inEq. More...
 
void addEquality (ArrayRef< int64_t > eq)
 Adds an equality from the coefficients specified in eq. More...
 
virtual void eliminateRedundantLocalVar (unsigned posA, unsigned posB)
 Eliminate the posB^th local variable, replacing every instance of it with the posA^th local variable. More...
 
void removeVar (VarKind kind, unsigned pos)
 Removes variables of the specified kind with the specified pos (or within the specified range) from the system. More...
 
virtual void removeVarRange (VarKind kind, unsigned varStart, unsigned varLimit)
 
void removeVar (unsigned pos)
 Removes the specified variable from the system. More...
 
void removeEquality (unsigned pos)
 
void removeInequality (unsigned pos)
 
void removeEqualityRange (unsigned start, unsigned end)
 Remove the (in)equalities at positions [start, end). More...
 
void removeInequalityRange (unsigned start, unsigned end)
 
MaybeOptimum< SmallVector< Fraction, 8 > > findRationalLexMin () const
 Get the lexicographically minimum rational point satisfying the constraints. More...
 
MaybeOptimum< SmallVector< int64_t, 8 > > findIntegerLexMin () const
 Same as above, but returns lexicographically minimal integer point. More...
 
virtual void swapVar (unsigned posA, unsigned posB)
 Swap the posA^th variable with the posB^th variable. More...
 
void clearConstraints ()
 Removes all equalities and inequalities. More...
 
void setAndEliminate (unsigned pos, ArrayRef< int64_t > values)
 Sets the values.size() variables starting at pos to the specified values and removes them. More...
 
virtual void clearAndCopyFrom (const IntegerRelation &other)
 Replaces the contents of this IntegerRelation with other. More...
 
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 on it. More...
 
bool isEmpty () const
 Checks for emptiness by performing variable elimination on all variables, running the GCD test on each equality constraint, and checking for invalid constraints. More...
 
bool isEmptyByGCDTest () const
 Runs the GCD test on all equality constraints. More...
 
bool isIntegerEmpty () const
 Returns true if the set of constraints is found to have no solution, false if a solution exists. More...
 
Matrix getBoundedDirections () const
 Returns a matrix where each row is a vector along which the polytope is bounded. More...
 
Optional< SmallVector< int64_t, 8 > > findIntegerSample () const
 Find an integer sample point satisfying the constraints using a branch and bound algorithm with generalized basis reduction, with some additional processing using Simplex for unbounded sets. More...
 
Optional< uint64_t > computeVolume () const
 Compute an overapproximation of the number of integer points in the relation. More...
 
bool containsPoint (ArrayRef< int64_t > point) const
 Returns true if the given point satisfies the constraints, or false otherwise. More...
 
Optional< SmallVector< int64_t, 8 > > containsPointNoLocal (ArrayRef< int64_t > point) const
 Given the values of non-local vars, return a satisfying assignment to the local if one exists, or an empty optional otherwise. More...
 
DivisionRepr getLocalReprs (std::vector< MaybeLocalRepr > *repr=nullptr) const
 Returns a DivisonRepr representing the division representation of local variables in the constraint system. More...
 
void addBound (BoundType type, unsigned pos, int64_t value)
 Adds a constant bound for the specified variable. More...
 
void addBound (BoundType type, ArrayRef< int64_t > expr, int64_t value)
 Adds a constant bound for the specified expression. More...
 
void addLocalFloorDiv (ArrayRef< int64_t > dividend, int64_t divisor)
 Adds a new local variable as the floordiv of an affine function of other variables, the coefficients of which are provided in dividend and with respect to a positive constant divisor. More...
 
void projectOut (unsigned pos, unsigned num)
 Projects out (aka eliminates) num variables starting at position pos. More...
 
void projectOut (unsigned pos)
 
LogicalResult constantFoldVar (unsigned pos)
 Tries to fold the specified variable to a constant using a trivial equality detection; if successful, the constant is substituted for the variable everywhere in the constraint system and then removed from the system. More...
 
void constantFoldVarRange (unsigned pos, unsigned num)
 This method calls constantFoldVar for the specified range of variables, num variables starting at position pos. More...
 
LogicalResult unionBoundingBox (const IntegerRelation &other)
 Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this set and that of other, with the symbols being treated specially. More...
 
Optional< int64_t > getConstantBoundOnDimSize (unsigned pos, SmallVectorImpl< int64_t > *lb=nullptr, int64_t *boundFloorDivisor=nullptr, SmallVectorImpl< int64_t > *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const
 Returns the smallest known constant bound for the extent of the specified variable (pos^th), i.e., the smallest known constant that is greater than or equal to 'exclusive upper bound' - 'lower bound' of the variable. More...
 
Optional< int64_t > getConstantBound (BoundType type, unsigned pos) const
 Returns the constant bound for the pos^th variable if there is one; None otherwise. More...
 
void removeIndependentConstraints (unsigned pos, unsigned num)
 Removes constraints that are independent of (i.e., do not have a coefficient) variables in the range [pos, pos + num). More...
 
bool isHyperRectangular (unsigned pos, unsigned num) const
 Returns true if the set can be trivially detected as being hyper-rectangular on the specified contiguous set of variables. More...
 
void removeTrivialRedundancy ()
 Removes duplicate constraints, trivially true constraints, and constraints that can be detected as redundant as a result of differing only in their constant term part. More...
 
void removeRedundantInequalities ()
 A more expensive check than removeTrivialRedundancy to detect redundant inequalities. More...
 
void removeRedundantConstraints ()
 Removes redundant constraints using Simplex. More...
 
void removeDuplicateDivs ()
 
void convertVarKind (VarKind srcKind, unsigned varStart, unsigned varLimit, VarKind dstKind, unsigned pos)
 Converts variables of kind srcKind in the range [varStart, varLimit) to variables of kind dstKind. More...
 
void convertVarKind (VarKind srcKind, unsigned varStart, unsigned varLimit, VarKind dstKind)
 
void convertToLocal (VarKind kind, unsigned varStart, unsigned varLimit)
 
unsigned mergeLocalVars (IntegerRelation &other)
 Adds additional local vars to the sets such that they both have the union of the local vars in each set, without changing the set of points that lie in this and other. More...
 
bool hasOnlyDivLocals () const
 Check whether all local ids have a division representation. More...
 
void setDimSymbolSeparation (unsigned newSymbolCount)
 Changes the partition between dimensions and symbols. More...
 
IntegerPolyhedron getDomainSet () const
 Return a set corresponding to all points in the domain of the relation. More...
 
IntegerPolyhedron getRangeSet () const
 Return a set corresponding to all points in the range of the relation. More...
 
void intersectDomain (const IntegerPolyhedron &poly)
 Intersect the given poly with the domain in-place. More...
 
void intersectRange (const IntegerPolyhedron &poly)
 Intersect the given poly with the range in-place. More...
 
void inverse ()
 Invert the relation i.e., swap its domain and range. More...
 
void compose (const IntegerRelation &rel)
 Let the relation this be R1, and the relation rel be R2. More...
 
void applyDomain (const IntegerRelation &rel)
 Given a relation rel, apply the relation to the domain of this relation. More...
 
void applyRange (const IntegerRelation &rel)
 Given a relation rel, apply the relation to the range of this relation. More...
 
PresburgerRelation computeReprWithOnlyDivLocals () const
 Compute an equivalent representation of the same set, such that all local vars in all disjuncts have division representations. More...
 
SymbolicLexMin findSymbolicIntegerLexMin () const
 Compute the symbolic integer lexmin of the relation. More...
 
PresburgerRelation subtract (const PresburgerRelation &set) const
 Return the set difference of this set and the given set, i.e., return this \ set. More...
 
void print (raw_ostream &os) const
 
void dump () const
 

Static Public Member Functions

static IntegerRelation getUniverse (const PresburgerSpace &space)
 Return a system with no constraints, i.e., one which is satisfied by all points. More...
 
static bool classof (const IntegerRelation *cst)
 

Protected Member Functions

bool hasInvalidConstraint () const
 Checks all rows of equality/inequality constraints for trivial contradictions (for example: 1 == 0, 0 >= 1), which may have surfaced after elimination. More...
 
template<bool isLower>
Optional< int64_t > computeConstantLowerOrUpperBound (unsigned pos)
 Returns the constant lower bound bound if isLower is true, and the upper bound if isLower is false. More...
 
LogicalResult gaussianEliminateVar (unsigned position)
 Eliminates a single variable at position from equality and inequality constraints. More...
 
void removeRedundantLocalVars ()
 Removes local variables using equalities. More...
 
unsigned gaussianEliminateVars (unsigned posStart, unsigned posLimit)
 Eliminates variables from equality and inequality constraints in column range [posStart, posLimit). More...
 
virtual void fourierMotzkinEliminate (unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr)
 Eliminates the variable at the specified position using Fourier-Motzkin variable elimination, but uses Gaussian elimination if there is an equality involving that variable. More...
 
void gcdTightenInequalities ()
 Tightens inequalities given that we are dealing with integer spaces. More...
 
void normalizeConstraintsByGCD ()
 Normalized each constraints by the GCD of its coefficients. More...
 
bool findConstraintWithNonZeroAt (unsigned colIdx, bool isEq, unsigned *rowIdx) const
 Searches for a constraint with a non-zero coefficient at colIdx in equality (isEq=true) or inequality (isEq=false) constraints. More...
 
bool isColZero (unsigned pos) const
 Returns true if the pos^th column is all zero for both inequalities and equalities. More...
 
virtual bool hasConsistentState () const
 Returns false if the fields corresponding to various variable counts, or equality/inequality buffer sizes aren't consistent; true otherwise. More...
 
virtual void printSpace (raw_ostream &os) const
 Prints the number of constraints, dimensions, symbols and locals in the IntegerRelation. More...
 
void removeVarRange (unsigned varStart, unsigned varLimit)
 Removes variables in the column range [varStart, varLimit), and copies any remaining valid data into place, updates member variables, and resizes arrays as needed. More...
 
void truncateVarKind (VarKind kind, unsigned num)
 Truncate the vars of the specified kind to the specified number by dropping some vars at the end. More...
 
void truncateVarKind (VarKind kind, const CountsSnapshot &counts)
 Truncate the vars to the number in the space of the specified CountsSnapshot. More...
 

Protected Attributes

PresburgerSpace space
 
Matrix equalities
 Coefficients of affine equalities (in == 0 form). More...
 
Matrix inequalities
 Coefficients of affine inequalities (in >= 0 form). More...
 

Static Protected Attributes

static constexpr unsigned kExplosionFactor = 32
 A parameter that controls detection of an unrealistic number of constraints. More...
 

Detailed Description

An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine constraints.

Affine constraints can be inequalities or equalities in the form:

Inequality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} + c_n >= 0 Equality : c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} + c_n == 0

where c_0, c_1, ..., c_n are integers and n is the total number of variables in the space.

Such a relation corresponds to the set of integer points lying in a convex polyhedron. For example, consider the relation: (x) -> (y) : (1 <= x <= 7, x = 2y) These can be thought of as points in the polyhedron: (x, y) : (1 <= x <= 7, x = 2y) This relation contains the pairs (2, 1), (4, 2), and (6, 3).

Since IntegerRelation makes a distinction between dimensions, VarKind::Range and VarKind::Domain should be used to refer to dimension variables.

Definition at line 52 of file IntegerRelation.h.

Member Enumeration Documentation

◆ BoundType

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

Enumerator
EQ 
LB 
UB 

Definition at line 367 of file IntegerRelation.h.

◆ Kind

All derived classes of IntegerRelation.

Enumerator
FlatAffineConstraints 
FlatAffineValueConstraints 
IntegerRelation 
IntegerPolyhedron 

Definition at line 55 of file IntegerRelation.h.

Constructor & Destructor Documentation

◆ IntegerRelation() [1/2]

mlir::presburger::IntegerRelation::IntegerRelation ( unsigned  numReservedInequalities,
unsigned  numReservedEqualities,
unsigned  numReservedCols,
const PresburgerSpace space 
)
inline

Constructs a relation reserving memory for the specified number of constraints and variables.

Definition at line 64 of file IntegerRelation.h.

References mlir::presburger::PresburgerSpace::getNumVars().

Referenced by mlir::FlatAffineValueConstraints::appendLocalVar(), getCommonConstraints(), and getConstantBound().

◆ IntegerRelation() [2/2]

mlir::presburger::IntegerRelation::IntegerRelation ( const PresburgerSpace space)
inlineexplicit

Constructs a relation with the specified number of dimensions and symbols.

Definition at line 75 of file IntegerRelation.h.

References ~IntegerRelation().

◆ ~IntegerRelation()

virtual mlir::presburger::IntegerRelation::~IntegerRelation ( )
virtualdefault

Referenced by IntegerRelation().

Member Function Documentation

◆ addBound() [1/2]

void IntegerRelation::addBound ( BoundType  type,
unsigned  pos,
int64_t  value 
)

Adds a constant bound for the specified variable.

Definition at line 1283 of file IntegerRelation.cpp.

References mlir::presburger::Matrix::appendExtraRow(), equalities, getNumCols(), inequalities, and value.

◆ addBound() [2/2]

void IntegerRelation::addBound ( BoundType  type,
ArrayRef< int64_t >  expr,
int64_t  value 
)

Adds a constant bound for the specified expression.

Definition at line 1297 of file IntegerRelation.cpp.

References mlir::presburger::Matrix::appendExtraRow(), getNumCols(), mlir::presburger::Matrix::getNumRows(), and inequalities.

◆ addEquality()

void IntegerRelation::addEquality ( ArrayRef< int64_t >  eq)

◆ addInequality()

void IntegerRelation::addInequality ( ArrayRef< int64_t >  inEq)

◆ addLocalFloorDiv()

void IntegerRelation::addLocalFloorDiv ( ArrayRef< int64_t >  dividend,
int64_t  divisor 
)

Adds a new local variable as the floordiv of an affine function of other variables, the coefficients of which are provided in dividend and with respect to a positive constant divisor.

Adds a new local variable as the floordiv of an affine function of other variables, the coefficients of which are provided in 'dividend' and with respect to a positive constant 'divisor'.

Two constraints are added to the system to capture equivalence with the floordiv: q = dividend floordiv c <=> c*q <= dividend <= c*q + c - 1.

Two constraints are added to the system to capture equivalence with the floordiv. q = expr floordiv c <=> c*q <= expr <= c*q + c - 1.

Definition at line 1313 of file IntegerRelation.cpp.

References addInequality(), appendVar(), mlir::presburger::getDivLowerBound(), mlir::presburger::getDivUpperBound(), getNumCols(), and mlir::presburger::Local.

Referenced by mlir::FlatAffineValueConstraints::addAffineForOpDomain().

◆ append()

void IntegerRelation::append ( const IntegerRelation other)

◆ appendVar()

unsigned IntegerRelation::appendVar ( VarKind  kind,
unsigned  num = 1 
)

Append num variables of the specified kind after the last variable of that kind.

The coefficient columns corresponding to the added variables are initialized to zero. Return the absolute column position (i.e., not relative to the kind of variable) of the first appended variable.

Definition at line 269 of file IntegerRelation.cpp.

Referenced by addLocalFloorDiv(), mlir::FlatAffineValueConstraints::appendDimVar(), mlir::FlatAffineValueConstraints::appendLocalVar(), mlir::FlatAffineValueConstraints::appendSymbolVar(), compose(), intersectDomain(), and intersectRange().

◆ applyDomain()

void IntegerRelation::applyDomain ( const IntegerRelation rel)

Given a relation rel, apply the relation to the domain of this relation.

R1: i -> j : (0 <= i < 2, j = i) R2: i -> k : (k = i floordiv 2) R3: k -> j : (0 <= k < 1, 2k <= j <= 2k + 1)

R1 = {(0, 0), (1, 1)}. R2 maps both 0 and 1 to 0. So R3 = {(0, 0), (0, 1)}.

Formally, R1.applyDomain(R2) = R2.inverse().compose(R1).

Definition at line 2230 of file IntegerRelation.cpp.

References compose(), and inverse().

Referenced by setDimSymbolSeparation().

◆ applyRange()

void IntegerRelation::applyRange ( const IntegerRelation rel)

Given a relation rel, apply the relation to the range of this relation.

Formally, R1.applyRange(R2) is the same as R1.compose(R2) but we provide this for uniformity with applyDomain.

Definition at line 2236 of file IntegerRelation.cpp.

References compose().

Referenced by setDimSymbolSeparation().

◆ atEq() [1/2]

int64_t mlir::presburger::IntegerRelation::atEq ( unsigned  i,
unsigned  j 
) const
inline

◆ atEq() [2/2]

int64_t& mlir::presburger::IntegerRelation::atEq ( unsigned  i,
unsigned  j 
)
inline

Definition at line 137 of file IntegerRelation.h.

References equalities.

◆ atIneq() [1/2]

int64_t mlir::presburger::IntegerRelation::atIneq ( unsigned  i,
unsigned  j 
) const
inline

◆ atIneq() [2/2]

int64_t& mlir::presburger::IntegerRelation::atIneq ( unsigned  i,
unsigned  j 
)
inline

Definition at line 143 of file IntegerRelation.h.

References inequalities.

◆ classof()

static bool mlir::presburger::IntegerRelation::classof ( const IntegerRelation cst)
inlinestatic

Definition at line 91 of file IntegerRelation.h.

References clone().

◆ clearAndCopyFrom()

void IntegerRelation::clearAndCopyFrom ( const IntegerRelation other)
virtual

Replaces the contents of this IntegerRelation with other.

Definition at line 462 of file IntegerRelation.cpp.

Referenced by fourierMotzkinEliminate().

◆ clearConstraints()

void IntegerRelation::clearConstraints ( )

Removes all equalities and inequalities.

Definition at line 379 of file IntegerRelation.cpp.

References equalities, inequalities, and mlir::presburger::Matrix::resizeVertically().

◆ clone()

std::unique_ptr< IntegerRelation > IntegerRelation::clone ( ) const

Definition at line 33 of file IntegerRelation.cpp.

Referenced by classof(), and mlir::presburger::IntegerPolyhedron::classof().

◆ compose()

void IntegerRelation::compose ( const IntegerRelation rel)

Let the relation this be R1, and the relation rel be R2.

Modifies R1 to be the composition of R1 and R2: R1;R2.

Formally, if R1: A -> B, and R2: B -> C, then this function returns a relation R3: A -> C such that a point (a, c) belongs to R3 iff there exists b such that (a, b) is in R1 and, (b, c) is in R2.

Definition at line 2204 of file IntegerRelation.cpp.

References appendVar(), convertVarKind(), mlir::presburger::Domain, getDomainSet(), getNumRangeVars(), getRangeSet(), getSpace(), intersectRange(), mlir::presburger::Local, and mlir::presburger::Range.

Referenced by applyDomain(), applyRange(), mlir::FlatAffineRelation::getNumRangeDims(), and setDimSymbolSeparation().

◆ computeConstantLowerOrUpperBound()

template<bool isLower>
Optional< int64_t > IntegerRelation::computeConstantLowerOrUpperBound ( unsigned  pos)
protected

Returns the constant lower bound bound if isLower is true, and the upper bound if isLower is false.

Definition at line 1520 of file IntegerRelation.cpp.

References atEq(), atIneq(), mlir::ceilDiv(), findEqualityToConstant(), mlir::floorDiv(), getNumCols(), getNumInequalities(), getNumVars(), mlir::presburger::None, and projectOut().

Referenced by setDimSymbolSeparation().

◆ computeReprWithOnlyDivLocals()

PresburgerRelation IntegerRelation::computeReprWithOnlyDivLocals ( ) const

Compute an equivalent representation of the same set, such that all local vars in all disjuncts have division representations.

This representation may involve local vars that correspond to divisions, and may also be a union of convex disjuncts.

Definition at line 168 of file IntegerRelation.cpp.

References copy(), mlir::presburger::PWMAFunction::getDomain(), getLocalReprs(), getNumLocalVars(), getNumVars(), mlir::presburger::PresburgerSpace::getSetSpace(), getSpace(), getVarKindOffset(), mlir::presburger::SymbolicLexMin::lexmin, mlir::presburger::Local, mlir::presburger::PresburgerSpace::removeVarRange(), mlir::presburger::PresburgerRelation::setSpace(), space, swapVar(), mlir::presburger::SymbolicLexMin::unboundedDomain, and mlir::presburger::PresburgerSet::unionSet().

Referenced by setDimSymbolSeparation().

◆ computeVolume()

Optional< uint64_t > IntegerRelation::computeVolume ( ) const

Compute an overapproximation of the number of integer points in the relation.

Symbol vars currently not supported. If the computed overapproximation is infinite, an empty optional is returned.

Definition at line 1083 of file IntegerRelation.cpp.

References mlir::presburger::Simplex::computeIntegerBounds(), getNumDimAndSymbolVars(), getNumSymbolVars(), getNumVars(), mlir::presburger::SimplexBase::isEmpty(), max(), and min().

◆ constantFoldVar()

LogicalResult IntegerRelation::constantFoldVar ( unsigned  pos)

Tries to fold the specified variable to a constant using a trivial equality detection; if successful, the constant is substituted for the variable everywhere in the constraint system and then removed from the system.

Definition at line 1358 of file IntegerRelation.cpp.

References atEq(), mlir::failure(), findEqualityToConstant(), getNumCols(), getNumVars(), setAndEliminate(), and mlir::success().

Referenced by constantFoldVarRange(), and projectOut().

◆ constantFoldVarRange()

void IntegerRelation::constantFoldVarRange ( unsigned  pos,
unsigned  num 
)

This method calls constantFoldVar for the specified range of variables, num variables starting at position pos.

Definition at line 1371 of file IntegerRelation.cpp.

References constantFoldVar(), and mlir::failed().

Referenced by projectOut().

◆ containsPoint()

bool IntegerRelation::containsPoint ( ArrayRef< int64_t >  point) const

Returns true if the given point satisfies the constraints, or false otherwise.

A point satisfies an equality iff the value of the equality at the expression is zero, and it satisfies an inequality iff the value of the inequality at that point is non-negative.

Takes the values of all vars including locals.

Definition at line 884 of file IntegerRelation.cpp.

References getEquality(), getInequality(), getNumEqualities(), getNumInequalities(), and valueAt().

Referenced by findIntegerSample().

◆ containsPointNoLocal()

Optional< SmallVector< int64_t, 8 > > IntegerRelation::containsPointNoLocal ( ArrayRef< int64_t >  point) const

Given the values of non-local vars, return a satisfying assignment to the local if one exists, or an empty optional otherwise.

Just substitute the values given and check if an integer sample exists for the local vars.

TODO: this could be made more efficient by handling divisions separately. Instead of finding an integer sample over all the locals, we can first compute the values of the locals that have division representations and only use the integer emptiness check for the locals that don't have this. Handling this correctly requires ordering the divs, though.

Definition at line 905 of file IntegerRelation.cpp.

References copy(), findIntegerSample(), getNumLocalVars(), getNumVars(), getVarKindOffset(), mlir::presburger::Local, and setAndEliminate().

Referenced by mlir::presburger::PresburgerRelation::containsPoint().

◆ convertToLocal()

void mlir::presburger::IntegerRelation::convertToLocal ( VarKind  kind,
unsigned  varStart,
unsigned  varLimit 
)
inline

◆ convertVarKind() [1/2]

void IntegerRelation::convertVarKind ( VarKind  srcKind,
unsigned  varStart,
unsigned  varLimit,
VarKind  dstKind,
unsigned  pos 
)

Converts variables of kind srcKind in the range [varStart, varLimit) to variables of kind dstKind.

If pos is given, the variables are placed at position pos of dstKind, otherwise they are placed after all the other variables of kind dstKind. The internal ordering among the moved variables is preserved.

Definition at line 1256 of file IntegerRelation.cpp.

References getNumVarKind(), getVarKindOffset(), insertVar(), removeVarRange(), and swapVar().

Referenced by compose(), convertToLocal(), convertVarKind(), getDomainSet(), getRangeSet(), inverse(), and projectOut().

◆ convertVarKind() [2/2]

void mlir::presburger::IntegerRelation::convertVarKind ( VarKind  srcKind,
unsigned  varStart,
unsigned  varLimit,
VarKind  dstKind 
)
inline

Definition at line 481 of file IntegerRelation.h.

References convertVarKind(), and getNumVarKind().

◆ dump()

void IntegerRelation::dump ( ) const

◆ eliminateRedundantLocalVar()

void IntegerRelation::eliminateRedundantLocalVar ( unsigned  posA,
unsigned  posB 
)
virtual

Eliminate the posB^th local variable, replacing every instance of it with the posA^th local variable.

This should be used when the two local variables are known to always take the same values.

Definition at line 1139 of file IntegerRelation.cpp.

References mlir::presburger::Matrix::addToColumn(), equalities, getNumLocalVars(), getVarKindOffset(), inequalities, mlir::presburger::Local, and removeVar().

Referenced by mlir::presburger::MultiAffineFunction::mergeLocalVars(), mergeLocalVars(), and removeDuplicateDivs().

◆ findConstraintWithNonZeroAt()

bool IntegerRelation::findConstraintWithNonZeroAt ( unsigned  colIdx,
bool  isEq,
unsigned rowIdx 
) const
protected

Searches for a constraint with a non-zero coefficient at colIdx in equality (isEq=true) or inequality (isEq=false) constraints.

Returns true and sets row found in search in rowIdx, false otherwise.

Definition at line 469 of file IntegerRelation.cpp.

References atEq(), atIneq(), getNumCols(), getNumEqualities(), and getNumInequalities().

Referenced by gaussianEliminateVar(), gaussianEliminateVars(), mlir::FlatAffineValueConstraints::getSliceBounds(), and isColZero().

◆ findIntegerLexMin()

MaybeOptimum< SmallVector< int64_t, 8 > > IntegerRelation::findIntegerLexMin ( ) const

Same as above, but returns lexicographically minimal integer point.

Note: this should be used only when the lexmin is really required. For a generic integer sampling operation, findIntegerSample is more robust and should be preferred. Note that Domain is minimized first, then range.

Definition at line 107 of file IntegerRelation.cpp.

References mlir::presburger::LexSimplex::findIntegerLexMin(), mlir::presburger::MaybeOptimum< T >::getKind(), getNumDimAndSymbolVars(), getNumSymbolVars(), getNumVars(), and mlir::presburger::MaybeOptimum< T >::isBounded().

◆ findIntegerSample()

Optional< SmallVector< int64_t, 8 > > IntegerRelation::findIntegerSample ( ) const

Find an integer sample point satisfying the constraints using a branch and bound algorithm with generalized basis reduction, with some additional processing using Simplex for unbounded sets.

Let this set be S.

Returns an integer sample point if one exists, or an empty Optional otherwise. The returned value also includes values of local ids.

If S is bounded then we directly call into the GBR sampling algorithm. Otherwise, there are some unbounded directions, i.e., vectors v such that S extends to infinity along v or -v. In this case we use an algorithm described in the integer set library (isl) manual and used by the isl_set_sample function in that library. The algorithm is:

1) Apply a unimodular transform T to S to obtain S*T, such that all dimensions in which S*T is bounded lie in the linear span of a prefix of the dimensions.

2) Construct a set B by removing all constraints that involve the unbounded dimensions and then deleting the unbounded dimensions. Note that B is a Bounded set.

3) Try to obtain a sample from B using the GBR sampling algorithm. If no sample is found, return that S is empty.

4) Otherwise, substitute the obtained sample into S*T to obtain a set C. C is a full-dimensional Cone and always contains a sample.

5) Obtain an integer sample from C.

6) Return T*v, where v is the concatenation of the samples from B and C.

The following is a sketch of a proof that a) If the algorithm returns empty, then S is empty. b) If the algorithm returns a sample, it is a valid sample in S.

The algorithm returns empty only if B is empty, in which case S*T is certainly empty since B was obtained by removing constraints and then deleting unconstrained dimensions from S*T. Since T is unimodular, a vector v is in S*T iff T*v is in S. So in this case, since S*T is empty, S is empty too.

Otherwise, the algorithm substitutes the sample from B into S*T. All the constraints of S*T that did not involve unbounded dimensions are satisfied by this substitution. All dimensions in the linear span of the dimensions outside the prefix are unbounded in S*T (step 1). Substituting values for the bounded dimensions cannot make these dimensions bounded, and these are the only remaining dimensions in C, so C is unbounded along every vector (in the positive or negative direction, or both). C is hence a full-dimensional cone and therefore always contains an integer point.

Concatenating the samples from B and C gives a sample v in S*T, so the returned sample T*v is a sample in S.

Definition at line 766 of file IntegerRelation.cpp.

References mlir::presburger::LinearTransform::applyTo(), atIneq(), mlir::presburger::ceil(), containsPoint(), mlir::presburger::Simplex::findIntegerSample(), getBoundedDirections(), getNumInequalities(), getNumVars(), mlir::presburger::Simplex::getRationalSample(), mlir::presburger::SimplexBase::isEmpty(), isEmptyByGCDTest(), mlir::presburger::Simplex::isUnbounded(), mlir::presburger::LinearTransform::makeTransformToColumnEchelon(), mlir::presburger::LinearTransform::postMultiplyWithColumn(), removeConstraintsInvolvingVarRange(), removeVarRange(), and setAndEliminate().

Referenced by containsPointNoLocal(), and isIntegerEmpty().

◆ findRationalLexMin()

MaybeOptimum< SmallVector< Fraction, 8 > > IntegerRelation::findRationalLexMin ( ) const

Get the lexicographically minimum rational point satisfying the constraints.

Returns an empty optional if the relation is empty or if the lexmin is unbounded. Symbols are not supported and will result in assert-failure. Note that Domain is minimized first, then range.

Definition at line 87 of file IntegerRelation.cpp.

References mlir::presburger::LexSimplex::findRationalLexMin(), getNumDimAndSymbolVars(), getNumSymbolVars(), getNumVars(), and mlir::presburger::MaybeOptimum< T >::isBounded().

◆ findSymbolicIntegerLexMin()

SymbolicLexMin IntegerRelation::findSymbolicIntegerLexMin ( ) const

Compute the symbolic integer lexmin of the relation.

This finds, for every assignment to the symbols and domain, the lexicographically minimum value attained by the range.

For example, the symbolic lexmin of the set

(x, y)[a, b, c] : (a <= x, b <= x, x <= c)

can be written as

x = a if b <= a, a <= c x = b if a < b, b <= c

This function is stored in the lexmin function in the result. Some assignments to the symbols might make the set empty. Such points are not part of the function's domain. In the above example, this happens when max(a, b) > c.

For some values of the symbols, the lexmin may be unbounded. SymbolicLexMin stores these parts of the symbolic domain in a separate PresburgerSet, unboundedDomain.

Definition at line 229 of file IntegerRelation.cpp.

References mlir::presburger::SymbolicLexSimplex::computeSymbolicIntegerLexMin(), mlir::presburger::Domain, getNumDomainVars(), getNumLocalVars(), mlir::presburger::PWMAFunction::getNumOutputs(), getNumSymbolVars(), getNumVars(), mlir::presburger::PresburgerSpace::getSetSpace(), getVarKindEnd(), getVarKindOffset(), mlir::presburger::SymbolicLexMin::lexmin, mlir::presburger::Symbol, and mlir::presburger::PWMAFunction::truncateOutput().

Referenced by setDimSymbolSeparation().

◆ fourierMotzkinEliminate()

void IntegerRelation::fourierMotzkinEliminate ( unsigned  pos,
bool  darkShadow = false,
bool *  isResultIntegerExact = nullptr 
)
protectedvirtual

Eliminates the variable at the specified position using Fourier-Motzkin variable elimination, but uses Gaussian elimination if there is an equality involving that variable.

If the result of the elimination is integer exact, *isResultIntegerExact is set to true. If darkShadow is set to true, a potential under approximation (subset) of the rational shadow / exact integer shadow is computed.

Create the new system which has one variable less.

Reimplemented in mlir::FlatAffineValueConstraints.

Definition at line 1737 of file IntegerRelation.cpp.

References atEq(), atIneq(), clearAndCopyFrom(), dump(), gaussianEliminateVar(), gcdTightenInequalities(), getNumCols(), getNumEqualities(), getNumInequalities(), getNumVars(), getSpace(), mlir::presburger::PresburgerSpace::getVarKindAt(), mlir::presburger::PresburgerSpace::getVarKindOffset(), hasConsistentState(), isColZero(), mlir::lcm(), mlir::presburger::lcm(), removeVar(), mlir::presburger::PresburgerSpace::removeVarRange(), and mlir::succeeded().

Referenced by gaussianEliminateVar(), isEmpty(), and projectOut().

◆ gaussianEliminateVar()

LogicalResult mlir::presburger::IntegerRelation::gaussianEliminateVar ( unsigned  position)
inlineprotected

Eliminates a single variable at position from equality and inequality constraints.

Returns success if the variable was eliminated, and failure otherwise.

Definition at line 627 of file IntegerRelation.h.

References findConstraintWithNonZeroAt(), fourierMotzkinEliminate(), gaussianEliminateVars(), gcdTightenInequalities(), hasConsistentState(), isColZero(), normalizeConstraintsByGCD(), printSpace(), removeRedundantLocalVars(), removeVarRange(), mlir::success(), and truncateVarKind().

Referenced by fourierMotzkinEliminate().

◆ gaussianEliminateVars()

unsigned IntegerRelation::gaussianEliminateVars ( unsigned  posStart,
unsigned  posLimit 
)
protected

Eliminates variables from equality and inequality constraints in column range [posStart, posLimit).

Returns the number of variables eliminated.

Definition at line 970 of file IntegerRelation.cpp.

References eliminateFromConstraint(), equalities, findConstraintWithNonZeroAt(), gcdTightenInequalities(), getNumEqualities(), getNumInequalities(), getNumVars(), hasConsistentState(), inequalities, mlir::presburger::Matrix::normalizeRow(), removeEquality(), and removeVarRange().

Referenced by gaussianEliminateVar(), isEmpty(), and projectOut().

◆ gcdTightenInequalities()

void IntegerRelation::gcdTightenInequalities ( )
protected

Tightens inequalities given that we are dealing with integer spaces.

This is similar to the GCD test but applied to inequalities. The constant term can be reduced to the preceding multiple of the GCD of the coefficients, i.e., 64*i - 100 >= 0 => 64*i - 128 >= 0 (since 'i' is an integer). This is a fast method (linear in the number of coefficients).

This is analogous to the GCD test but applied to inequalities. The constant term can be reduced to the preceding multiple of the GCD of the coefficients, i.e., 64*i - 100 >= 0 => 64*i - 128 >= 0 (since 'i' is an integer). This is a fast method - linear in the number of coefficients.

Definition at line 958 of file IntegerRelation.cpp.

References atIneq(), mlir::floorDiv(), mlir::presburger::gcd(), getNumCols(), getNumInequalities(), inequalities, and mlir::presburger::Matrix::normalizeRow().

Referenced by fourierMotzkinEliminate(), gaussianEliminateVar(), gaussianEliminateVars(), projectOut(), removeRedundantConstraints(), and removeTrivialRedundancy().

◆ getBoundedDirections()

Matrix IntegerRelation::getBoundedDirections ( ) const

Returns a matrix where each row is a vector along which the polytope is bounded.

The span of the returned vectors is guaranteed to contain all such vectors. The returned vectors are NOT guaranteed to be linearly independent. This function should not be called on empty sets.

Definition at line 678 of file IntegerRelation.cpp.

References atEq(), atIneq(), getNumCols(), getNumEqualities(), getNumInequalities(), mlir::presburger::Simplex::isBoundedAlongConstraint(), and mlir::presburger::SimplexBase::isEmpty().

Referenced by findIntegerSample().

◆ getConstantBound()

Optional< int64_t > IntegerRelation::getConstantBound ( BoundType  type,
unsigned  pos 
) const

Returns the constant bound for the pos^th variable if there is one; None otherwise.

Definition at line 1576 of file IntegerRelation.cpp.

References IntegerRelation(), and mlir::presburger::None.

Referenced by canonicalizeMinMaxOp(), computeDirectionVector(), detectAsMod(), mlir::FlatAffineValueConstraints::getSliceBounds(), mlir::linalg::getUpperBoundForIndex(), mlir::normalizeMemRefType(), and projectOut().

◆ getConstantBoundOnDimSize()

Optional< int64_t > IntegerRelation::getConstantBoundOnDimSize ( unsigned  pos,
SmallVectorImpl< int64_t > *  lb = nullptr,
int64_t *  boundFloorDivisor = nullptr,
SmallVectorImpl< int64_t > *  ub = nullptr,
unsigned minLbPos = nullptr,
unsigned minUbPos = nullptr 
) const

Returns the smallest known constant bound for the extent of the specified variable (pos^th), i.e., the smallest known constant that is greater than or equal to 'exclusive upper bound' - 'lower bound' of the variable.

Returns a non-negative constant bound on the extent (upper bound - lower bound) of the specified variable if it is found to be a constant; returns None if it's not a constant.

This constant bound is guaranteed to be non-negative. Returns None if it's not a constant. This method employs trivial (low complexity / cost) checks and detection. Symbolic variables are treated specially, i.e., it looks for constant differences between affine expressions involving only the symbolic variables. lb and ub (along with the boundFloorDivisor) are set to represent the lower and upper bound associated with the constant difference: lb, ub have the coefficients, and boundFloorDivisor, their divisor. minLbPos and minUbPos if non-null are set to the position of the constant lower bound and upper bound respectively (to the same if they are from an equality). Ex: if the lower bound is [(s0 + s2 - 1) floordiv 32] for a system with three symbolic variables, *lb = [1, 0, 1], lbDivisor = 32. See comments at function definition for examples.

This methods treats symbolic variables specially, i.e., it looks for constant differences between affine expressions involving only the symbolic variables. See comments at function definition for example. 'lb', if provided, is set to the lower bound associated with the constant difference. Note that 'lb' is purely symbolic and thus will contain the coefficients of the symbolic variables and the constant coefficient.

Definition at line 1392 of file IntegerRelation.cpp.

References atEq(), atIneq(), mlir::presburger::ceilDiv(), findEqualityToConstant(), getEquality(), getLowerAndUpperBoundIndices(), getNumCols(), getNumDimAndSymbolVars(), getNumDimVars(), getNumInequalities(), getNumSymbolVars(), and mlir::presburger::None.

Referenced by createFullTiles(), createSeparationCondition(), projectOut(), and unionBoundingBox().

◆ getCounts()

IntegerRelation::CountsSnapshot IntegerRelation::getCounts ( ) const

◆ getDomainSet()

IntegerPolyhedron IntegerRelation::getDomainSet ( ) const

◆ getEquality()

ArrayRef<int64_t> mlir::presburger::IntegerRelation::getEquality ( unsigned  idx) const
inline

◆ getInequality()

ArrayRef<int64_t> mlir::presburger::IntegerRelation::getInequality ( unsigned  idx) const
inline

◆ getKind()

virtual Kind mlir::presburger::IntegerRelation::getKind ( ) const
inlinevirtual

Return the kind of this IntegerRelation.

Reimplemented in mlir::presburger::IntegerPolyhedron, and mlir::FlatAffineValueConstraints.

Definition at line 89 of file IntegerRelation.h.

References IntegerRelation.

Referenced by mlir::presburger::IntegerPolyhedron::classof().

◆ getLocalReprs()

DivisionRepr IntegerRelation::getLocalReprs ( std::vector< MaybeLocalRepr > *  repr = nullptr) const

Returns a DivisonRepr representing the division representation of local variables in the constraint system.

If repr is not nullptr, the equality and pairs of inequality constraints identified by their position indices using which an explicit representation for each local variable can be computed are set in repr in the form of a MaybeLocalRepr struct. If no such inequality pair/equality can be found, the kind attribute in MaybeLocalRepr is set to None.

Definition at line 916 of file IntegerRelation.cpp.

References getNumDimAndSymbolVars(), getNumLocalVars(), getNumVars(), getVarKindOffset(), and mlir::presburger::Local.

Referenced by computeReprWithOnlyDivLocals(), getSetDifference(), hasOnlyDivLocals(), mlir::presburger::mergeLocalVars(), and removeDuplicateDivs().

◆ getLowerAndUpperBoundIndices()

void IntegerRelation::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 on it.

Gather all lower and upper bounds of the variable at pos, and optionally any equalities on it.

In addition, the bounds are to be independent of variables in position range [offset, offset + num).

Definition at line 387 of file IntegerRelation.cpp.

References atEq(), atIneq(), getEquality(), getInequality(), getNumCols(), getNumEqualities(), getNumInequalities(), and getNumVars().

Referenced by mlir::presburger::computeSingleVarRepr(), createSeparationCondition(), getConstantBoundOnDimSize(), and mlir::FlatAffineValueConstraints::getLowerAndUpperBound().

◆ getNumCols()

unsigned mlir::presburger::IntegerRelation::getNumCols ( ) const
inline

◆ getNumConstraints()

unsigned mlir::presburger::IntegerRelation::getNumConstraints ( ) const
inline

◆ getNumDimAndSymbolVars()

unsigned mlir::presburger::IntegerRelation::getNumDimAndSymbolVars ( ) const
inline

◆ getNumDimVars()

unsigned mlir::presburger::IntegerRelation::getNumDimVars ( ) const
inline

◆ getNumDomainVars()

unsigned mlir::presburger::IntegerRelation::getNumDomainVars ( ) const
inline

◆ getNumEqualities()

unsigned mlir::presburger::IntegerRelation::getNumEqualities ( ) const
inline

◆ getNumInequalities()

unsigned mlir::presburger::IntegerRelation::getNumInequalities ( ) const
inline

◆ getNumLocalVars()

unsigned mlir::presburger::IntegerRelation::getNumLocalVars ( ) const
inline

◆ getNumRangeVars()

unsigned mlir::presburger::IntegerRelation::getNumRangeVars ( ) const
inline

Definition at line 150 of file IntegerRelation.h.

References mlir::presburger::PresburgerSpace::getNumRangeVars(), and space.

Referenced by compose(), and intersectDomain().

◆ getNumReservedEqualities()

unsigned mlir::presburger::IntegerRelation::getNumReservedEqualities ( ) const
inline

◆ getNumReservedInequalities()

unsigned mlir::presburger::IntegerRelation::getNumReservedInequalities ( ) const
inline

◆ getNumSymbolVars()

unsigned mlir::presburger::IntegerRelation::getNumSymbolVars ( ) const
inline

◆ getNumVarKind()

unsigned mlir::presburger::IntegerRelation::getNumVarKind ( VarKind  kind) const
inline

◆ getNumVars()

unsigned mlir::presburger::IntegerRelation::getNumVars ( ) const
inline

◆ getRangeSet()

IntegerPolyhedron IntegerRelation::getRangeSet ( ) const

Return a set corresponding to all points in the range of the relation.

Definition at line 2155 of file IntegerRelation.cpp.

References convertVarKind(), mlir::presburger::Domain, getNumVarKind(), and mlir::presburger::Local.

Referenced by compose(), mlir::FlatAffineRelation::FlatAffineRelation(), intersectRange(), and setDimSymbolSeparation().

◆ getSpace()

const PresburgerSpace& mlir::presburger::IntegerRelation::getSpace ( ) const
inline

◆ getSpaceWithoutLocals()

PresburgerSpace mlir::presburger::IntegerRelation::getSpaceWithoutLocals ( ) const
inline

◆ getUniverse()

static IntegerRelation mlir::presburger::IntegerRelation::getUniverse ( const PresburgerSpace space)
inlinestatic

Return a system with no constraints, i.e., one which is satisfied by all points.

Definition at line 84 of file IntegerRelation.h.

References IntegerRelation.

Referenced by mlir::presburger::PresburgerRelation::complement(), and mlir::presburger::PresburgerRelation::getUniverse().

◆ getVarKindAt()

VarKind mlir::presburger::IntegerRelation::getVarKindAt ( unsigned  pos) const
inline

Return the VarKind of the var at the specified position.

Definition at line 208 of file IntegerRelation.h.

References mlir::presburger::PresburgerSpace::getVarKindAt(), and space.

Referenced by mlir::FlatAffineValueConstraints::fourierMotzkinEliminate(), and mlir::FlatAffineValueConstraints::swapVar().

◆ getVarKindEnd()

unsigned mlir::presburger::IntegerRelation::getVarKindEnd ( VarKind  kind) const
inline

Return the index at Which the specified kind of vars ends.

Definition at line 196 of file IntegerRelation.h.

Referenced by mlir::FlatAffineValueConstraints::computeAlignedMap(), findSymbolicIntegerLexMin(), inverse(), and mlir::FlatAffineValueConstraints::printSpace().

◆ getVarKindOffset()

unsigned mlir::presburger::IntegerRelation::getVarKindOffset ( VarKind  kind) const
inline

◆ getVarKindOverlap()

unsigned mlir::presburger::IntegerRelation::getVarKindOverlap ( VarKind  kind,
unsigned  varStart,
unsigned  varLimit 
) const
inline

Get the number of elements of the specified kind in the range [varStart, varLimit).

Definition at line 202 of file IntegerRelation.h.

◆ hasConsistentState()

bool IntegerRelation::hasConsistentState ( ) const
protectedvirtual

Returns false if the fields corresponding to various variable counts, or equality/inequality buffer sizes aren't consistent; true otherwise.

This is meant to be used within an assert internally.

Reimplemented in mlir::FlatAffineValueConstraints.

Definition at line 438 of file IntegerRelation.cpp.

References equalities, mlir::presburger::Matrix::hasConsistentState(), and inequalities.

Referenced by fourierMotzkinEliminate(), gaussianEliminateVar(), gaussianEliminateVars(), hasInvalidConstraint(), isEmptyByGCDTest(), and print().

◆ hasInvalidConstraint()

bool IntegerRelation::hasInvalidConstraint ( ) const
protected

Checks all rows of equality/inequality constraints for trivial contradictions (for example: 1 == 0, 0 >= 1), which may have surfaced after elimination.

Returns true if an invalid constraint is found; false otherwise.

Definition at line 491 of file IntegerRelation.cpp.

References atEq(), atIneq(), getNumCols(), getNumEqualities(), getNumInequalities(), and hasConsistentState().

Referenced by isEmpty(), and setDimSymbolSeparation().

◆ hasOnlyDivLocals()

bool IntegerRelation::hasOnlyDivLocals ( ) const

Check whether all local ids have a division representation.

Definition at line 1195 of file IntegerRelation.cpp.

References getLocalReprs(), and mlir::presburger::DivisionRepr::hasAllReprs().

Referenced by convertToLocal(), and mlir::presburger::PresburgerRelation::hasOnlyDivLocals().

◆ insertVar()

unsigned IntegerRelation::insertVar ( VarKind  kind,
unsigned  pos,
unsigned  num = 1 
)
virtual

Insert num variables of the specified kind at position pos.

Positions are relative to the kind of variable. The coefficient columns corresponding to the added variables are initialized to zero. Return the absolute column position (i.e., not relative to the kind of variable) of the first added variable.

Reimplemented in mlir::presburger::IntegerPolyhedron, and mlir::FlatAffineValueConstraints.

Definition at line 260 of file IntegerRelation.cpp.

Referenced by mlir::presburger::IntegerPolyhedron::classof(), convertVarKind(), mlir::presburger::IntegerRelation::CountsSnapshot::getNumEqs(), and mlir::presburger::mergeLocalVars().

◆ intersect()

IntegerRelation IntegerRelation::intersect ( IntegerRelation  other) const

Return the intersection of the two relations.

If there are locals, they will be merged.

Definition at line 69 of file IntegerRelation.cpp.

References append(), and mergeLocalVars().

Referenced by getSpaceWithoutLocals(), mlir::presburger::PresburgerRelation::intersect(), and mlir::presburger::IntegerPolyhedron::intersect().

◆ intersectDomain()

void IntegerRelation::intersectDomain ( const IntegerPolyhedron poly)

Intersect the given poly with the domain in-place.

Formally, let the relation this be R: A -> B and poly is C, then this operation modifies R to be (A intersection C) -> B.

Definition at line 2168 of file IntegerRelation.cpp.

References append(), appendVar(), getDomainSet(), getNumRangeVars(), getSpace(), inverse(), mergeLocalVars(), and mlir::presburger::Range.

Referenced by setDimSymbolSeparation().

◆ intersectRange()

void IntegerRelation::intersectRange ( const IntegerPolyhedron poly)

Intersect the given poly with the range in-place.

Formally, let the relation this be R: A -> B and poly is C, then this operation modifies R to be A -> (B intersection C).

Definition at line 2184 of file IntegerRelation.cpp.

References append(), appendVar(), mlir::presburger::Domain, getNumDomainVars(), getRangeSet(), getSpace(), and mergeLocalVars().

Referenced by compose(), and setDimSymbolSeparation().

◆ inverse()

void IntegerRelation::inverse ( )

Invert the relation i.e., swap its domain and range.

Formally, let the relation this be R: A -> B, then this operation modifies R to be B -> A.

Definition at line 2197 of file IntegerRelation.cpp.

References convertVarKind(), mlir::presburger::Domain, getNumVarKind(), getVarKindEnd(), and mlir::presburger::Range.

Referenced by applyDomain(), mlir::FlatAffineRelation::getNumRangeDims(), intersectDomain(), and setDimSymbolSeparation().

◆ isColZero()

bool IntegerRelation::isColZero ( unsigned  pos) const
protected

Returns true if the pos^th column is all zero for both inequalities and equalities.

Definition at line 2087 of file IntegerRelation.cpp.

References findConstraintWithNonZeroAt().

Referenced by fourierMotzkinEliminate(), gaussianEliminateVar(), and mlir::FlatAffineValueConstraints::getAsIntegerSet().

◆ isEmpty()

bool IntegerRelation::isEmpty ( ) const

Checks for emptiness by performing variable elimination on all variables, running the GCD test on each equality constraint, and checking for invalid constraints.

Returns true if the GCD test fails for any equality, or if any invalid constraints are discovered on any row. Returns false otherwise.

Definition at line 594 of file IntegerRelation.cpp.

References fourierMotzkinEliminate(), gaussianEliminateVars(), getBestVarToEliminate(), getNumConstraints(), getNumVars(), hasInvalidConstraint(), isEmptyByGCDTest(), kExplosionFactor, and removeRedundantLocalVars().

Referenced by canonicalizeMinMaxOp(), mlir::checkMemrefAccessDependence(), mlir::presburger::PresburgerRelation::intersect(), removeRedundantInequalities(), and mlir::simplifyIntegerSet().

◆ isEmptyByGCDTest()

bool IntegerRelation::isEmptyByGCDTest ( ) const

Runs the GCD test on all equality constraints.

Returns true if this test fails on any equality. Returns false otherwise. This test can be used to disprove the existence of a solution. If it returns true, no integer solution to the equality constraints can exist.

Definition at line 655 of file IntegerRelation.cpp.

References mlir::presburger::abs(), atEq(), mlir::presburger::gcd(), getNumCols(), getNumEqualities(), and hasConsistentState().

Referenced by findIntegerSample(), getSetDifference(), and isEmpty().

◆ isEqual()

bool IntegerRelation::isEqual ( const IntegerRelation other) const

Return whether this and other are equal.

This is integer-exact and somewhat expensive, since it uses the integer emptiness check (see IntegerRelation::findIntegerSample()).

Definition at line 76 of file IntegerRelation.cpp.

References getSpace(), mlir::presburger::PresburgerSpace::isCompatible(), mlir::presburger::PresburgerRelation::isEqual(), and space.

Referenced by getSpaceWithoutLocals().

◆ isHyperRectangular()

bool IntegerRelation::isHyperRectangular ( unsigned  pos,
unsigned  num 
) const

Returns true if the set can be trivially detected as being hyper-rectangular on the specified contiguous set of variables.

Definition at line 1596 of file IntegerRelation.cpp.

References atEq(), atIneq(), getNumCols(), getNumEqualities(), and getNumInequalities().

Referenced by checkIfHyperRectangular(), and projectOut().

◆ isIntegerEmpty()

bool IntegerRelation::isIntegerEmpty ( ) const

Returns true if the set of constraints is found to have no solution, false if a solution exists.

Uses the same algorithm as findIntegerSample.

Definition at line 719 of file IntegerRelation.cpp.

References findIntegerSample().

Referenced by mlir::presburger::PresburgerRelation::isIntegerEmpty().

◆ isSubsetOf()

bool IntegerRelation::isSubsetOf ( const IntegerRelation other) const

Return whether this is a subset of the given IntegerRelation.

This is integer-exact and somewhat expensive, since it uses the integer emptiness check (see IntegerRelation::findIntegerSample()).

Definition at line 81 of file IntegerRelation.cpp.

References getSpace(), mlir::presburger::PresburgerSpace::isCompatible(), mlir::presburger::PresburgerRelation::isSubsetOf(), and space.

Referenced by getSpaceWithoutLocals(), and mlir::presburger::MultiAffineFunction::isEqualWhereDomainsOverlap().

◆ mergeLocalVars()

unsigned IntegerRelation::mergeLocalVars ( IntegerRelation other)

Adds additional local vars to the sets such that they both have the union of the local vars in each set, without changing the set of points that lie in this and other.

Adds additional local ids to the sets such that they both have the union of the local ids in each set, without changing the set of points that lie in this and other.

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

[Local vars of this] [Non-merged local vars of other]

The relative ordering of local vars is same as before.

After merging, if the i^th local variable in one set has a known division representation, then the i^th local variable in the other set either has the same division representation or no known division representation.

The spaces of both relations should be compatible.

Returns the number of non-merged local vars of other, i.e. the number of locals that have been added to this.

To detect local ids that always take the same value, each local id is represented as a floordiv with constant denominator in terms of other ids. After extracting these divisions, local ids in other with the same division representation as some other local id in any set are considered duplicate and are merged.

It is possible that division representation for some local id cannot be obtained, and thus these local ids are not considered for detecting duplicates.

Definition at line 1164 of file IntegerRelation.cpp.

References eliminateRedundantLocalVar(), getNumLocalVars(), and mlir::presburger::mergeLocalVars().

Referenced by mlir::FlatAffineRelation::compose(), convertToLocal(), getSetDifference(), intersect(), intersectDomain(), intersectRange(), and mergeAndAlignVars().

◆ normalizeConstraintsByGCD()

void IntegerRelation::normalizeConstraintsByGCD ( )
protected

◆ print()

void IntegerRelation::print ( raw_ostream &  os) const

◆ printSpace()

void IntegerRelation::printSpace ( raw_ostream &  os) const
protectedvirtual

Prints the number of constraints, dimensions, symbols and locals in the IntegerRelation.

Reimplemented in mlir::FlatAffineValueConstraints.

Definition at line 2238 of file IntegerRelation.cpp.

References getNumConstraints(), mlir::presburger::PresburgerSpace::print(), and space.

Referenced by gaussianEliminateVar(), and print().

◆ projectOut() [1/2]

void IntegerRelation::projectOut ( unsigned  pos,
unsigned  num 
)

Projects out (aka eliminates) num variables starting at position pos.

The resulting constraint system is the shadow along the dimensions that still exist. This method may not always be integer exact.

Definition at line 1893 of file IntegerRelation.cpp.

References fourierMotzkinEliminate(), gaussianEliminateVars(), gcdTightenInequalities(), getBestVarToEliminate(), getNumCols(), getNumVars(), and normalizeConstraintsByGCD().

Referenced by computeConstantLowerOrUpperBound().

◆ projectOut() [2/2]

void mlir::presburger::IntegerRelation::projectOut ( unsigned  pos)
inline

◆ removeDuplicateDivs()

void IntegerRelation::removeDuplicateDivs ( )

◆ removeEquality()

void IntegerRelation::removeEquality ( unsigned  pos)

◆ removeEqualityRange()

void IntegerRelation::removeEqualityRange ( unsigned  start,
unsigned  end 
)

Remove the (in)equalities at positions [start, end).

Definition at line 356 of file IntegerRelation.cpp.

References equalities, and mlir::presburger::Matrix::removeRows().

Referenced by truncate().

◆ removeIndependentConstraints()

void IntegerRelation::removeIndependentConstraints ( unsigned  pos,
unsigned  num 
)

Removes constraints that are independent of (i.e., do not have a coefficient) variables in the range [pos, pos + num).

Definition at line 2125 of file IntegerRelation.cpp.

References getIndependentConstraints(), getNumVars(), removeEquality(), and removeInequality().

Referenced by createSeparationCondition(), and projectOut().

◆ removeInequality()

void IntegerRelation::removeInequality ( unsigned  pos)

◆ removeInequalityRange()

void IntegerRelation::removeInequalityRange ( unsigned  start,
unsigned  end 
)

Definition at line 362 of file IntegerRelation.cpp.

References inequalities, and mlir::presburger::Matrix::removeRows().

Referenced by truncate().

◆ removeRedundantConstraints()

void IntegerRelation::removeRedundantConstraints ( )

Removes redundant constraints using Simplex.

Although the algorithm can theoretically take exponential time in the worst case (rare), it is known to perform much better in the average case. If V is the number of vertices in the polytope and C is the number of constraints, the algorithm takes O(VC) time.

Definition at line 1052 of file IntegerRelation.cpp.

References mlir::presburger::Matrix::copyRow(), mlir::presburger::Simplex::detectRedundant(), equalities, gcdTightenInequalities(), getNumEqualities(), getNumInequalities(), inequalities, mlir::presburger::Simplex::isMarkedRedundant(), and mlir::presburger::Matrix::resizeVertically().

Referenced by projectOut().

◆ removeRedundantInequalities()

void IntegerRelation::removeRedundantInequalities ( )

A more expensive check than removeTrivialRedundancy to detect redundant inequalities.

Definition at line 1020 of file IntegerRelation.cpp.

References atIneq(), mlir::presburger::Matrix::copyRow(), mlir::presburger::Matrix::fillRow(), getNumCols(), getNumInequalities(), inequalities, isEmpty(), mlir::presburger::Matrix::negateRow(), and mlir::presburger::Matrix::resizeVertically().

Referenced by projectOut().

◆ removeRedundantLocalVars()

void IntegerRelation::removeRedundantLocalVars ( )
protected

Removes local variables using equalities.

Each equality is checked if it can be reduced to the form: e = affine-expr, where e is a local variable and affine-expr is an affine expression not containing e. If an equality satisfies this form, the local variable is replaced in each constraint and then removed. The equality used to replace this local variable is also removed.

Definition at line 1214 of file IntegerRelation.cpp.

References mlir::presburger::abs(), atEq(), eliminateFromConstraint(), equalities, getNumDimAndSymbolVars(), getNumEqualities(), getNumInequalities(), getNumVars(), mlir::presburger::Matrix::normalizeRow(), removeEquality(), and removeVar().

Referenced by mlir::FlatAffineRelation::compose(), gaussianEliminateVar(), and isEmpty().

◆ removeTrivialRedundancy()

void IntegerRelation::removeTrivialRedundancy ( )

Removes duplicate constraints, trivially true constraints, and constraints that can be detected as redundant as a result of differing only in their constant term part.

A constraint of the form <non-negative constant> >= 0 is considered trivially true. This method is a linear time method on the constraints, does a single scan, and updates in place. It also normalizes constraints by their GCD and performs GCD tightening on inequalities.

A constraint of the form <non-negative constant> >= 0 is considered trivially true.

Definition at line 1626 of file IntegerRelation.cpp.

References atIneq(), mlir::presburger::Matrix::copyRow(), gcdTightenInequalities(), getNumCols(), getNumInequalities(), inequalities, normalizeConstraintsByGCD(), and mlir::presburger::Matrix::resizeVertically().

Referenced by createSeparationCondition(), projectOut(), and mlir::simplifyIntegerSet().

◆ removeVar() [1/2]

void IntegerRelation::removeVar ( VarKind  kind,
unsigned  pos 
)

Removes variables of the specified kind with the specified pos (or within the specified range) from the system.

The specified location is relative to the first variable of the specified kind.

Definition at line 288 of file IntegerRelation.cpp.

Referenced by createSeparationCondition(), eliminateRedundantLocalVar(), fourierMotzkinEliminate(), and removeRedundantLocalVars().

◆ removeVar() [2/2]

void IntegerRelation::removeVar ( unsigned  pos)

Removes the specified variable from the system.

Definition at line 292 of file IntegerRelation.cpp.

References removeVarRange().

◆ removeVarRange() [1/2]

void IntegerRelation::removeVarRange ( VarKind  kind,
unsigned  varStart,
unsigned  varLimit 
)
virtual

◆ removeVarRange() [2/2]

void IntegerRelation::removeVarRange ( unsigned  varStart,
unsigned  varLimit 
)
protected

Removes variables in the column range [varStart, varLimit), and copies any remaining valid data into place, updates member variables, and resizes arrays as needed.

Definition at line 310 of file IntegerRelation.cpp.

References getNumVars().

◆ setAndEliminate()

void IntegerRelation::setAndEliminate ( unsigned  pos,
ArrayRef< int64_t >  values 
)

Sets the values.size() variables starting at pos to the specified values and removes them.

Definition at line 446 of file IntegerRelation.cpp.

References mlir::presburger::Matrix::addToColumn(), equalities, getNumCols(), getNumVars(), inequalities, and removeVarRange().

Referenced by constantFoldVar(), containsPointNoLocal(), and findIntegerSample().

◆ setDimSymbolSeparation()

void mlir::presburger::IntegerRelation::setDimSymbolSeparation ( unsigned  newSymbolCount)
inline

Changes the partition between dimensions and symbols.

Depending on the new symbol count, either a chunk of dimensional variables immediately before the split become symbols, or some of the symbols immediately after the split become dimensions.

Definition at line 521 of file IntegerRelation.h.

References applyDomain(), applyRange(), compose(), computeConstantLowerOrUpperBound(), computeReprWithOnlyDivLocals(), dump(), findSymbolicIntegerLexMin(), getDomainSet(), getRangeSet(), hasInvalidConstraint(), intersectDomain(), intersectRange(), inverse(), print(), mlir::presburger::PresburgerSpace::setVarSymbolSeperation(), space, and subtract().

Referenced by createFullTiles(), createSeparationCondition(), and turnSymbolIntoDim().

◆ setSpace()

void IntegerRelation::setSpace ( const PresburgerSpace oSpace)

Set the space to oSpace, which should have the same number of ids as the current space.

Definition at line 41 of file IntegerRelation.cpp.

References mlir::presburger::PresburgerSpace::getNumVars(), and space.

Referenced by getSpace().

◆ setSpaceExceptLocals()

void IntegerRelation::setSpaceExceptLocals ( const PresburgerSpace oSpace)

Set the space to oSpace, which should not have any local ids.

oSpace can have fewer ids than the current space; in that case, the the extra ids in this that are not accounted for by oSpace will be considered as local ids. oSpace should not have more ids than the current space; this will result in an assert failure.

Definition at line 46 of file IntegerRelation.cpp.

References mlir::presburger::PresburgerSpace::getNumLocalVars(), mlir::presburger::PresburgerSpace::getNumVars(), getNumVars(), mlir::presburger::PresburgerSpace::insertVar(), mlir::presburger::Local, and space.

Referenced by getSpace().

◆ subtract()

PresburgerRelation IntegerRelation::subtract ( const PresburgerRelation set) const

Return the set difference of this set and the given set, i.e., return this \ set.

Definition at line 256 of file IntegerRelation.cpp.

References mlir::presburger::PresburgerRelation::subtract().

Referenced by setDimSymbolSeparation(), and mlir::presburger::IntegerPolyhedron::subtract().

◆ swapVar()

void IntegerRelation::swapVar ( unsigned  posA,
unsigned  posB 
)
virtual

Swap the posA^th variable with the posB^th variable.

Reimplemented in mlir::FlatAffineValueConstraints.

Definition at line 368 of file IntegerRelation.cpp.

References equalities, getNumVars(), inequalities, and mlir::presburger::Matrix::swapColumns().

Referenced by computeReprWithOnlyDivLocals(), and convertVarKind().

◆ truncate()

void IntegerRelation::truncate ( const CountsSnapshot counts)

◆ truncateVarKind() [1/2]

void IntegerRelation::truncateVarKind ( VarKind  kind,
unsigned  num 
)
protected

Truncate the vars of the specified kind to the specified number by dropping some vars at the end.

num must be less than the current number.

Definition at line 148 of file IntegerRelation.cpp.

Referenced by gaussianEliminateVar(), and truncate().

◆ truncateVarKind() [2/2]

void IntegerRelation::truncateVarKind ( VarKind  kind,
const CountsSnapshot counts 
)
protected

Truncate the vars to the number in the space of the specified CountsSnapshot.

Definition at line 154 of file IntegerRelation.cpp.

◆ unionBoundingBox()

LogicalResult IntegerRelation::unionBoundingBox ( const IntegerRelation other)

Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this set and that of other, with the symbols being treated specially.

For each of the dimensions, the min of the lower bounds (symbolic) and the max of the upper bounds (symbolic) is computed to determine such a bounding box. other is expected to have the same dimensional variables as this constraint system (in the same order).

E.g.: 1) this = {0 <= d0 <= 127}, other = {16 <= d0 <= 192}, output = {0 <= d0 <= 192} 2) this = {s0 + 5 <= d0 <= s0 + 20}, other = {s0 + 1 <= d0 <= s0 + 9}, output = {s0 + 1 <= d0 <= s0 + 20} 3) this = {0 <= d0 <= 5, 1 <= d1 <= 9} other = {2 <= d0 <= 6, 5 <= d1 <= 15}, output = {0 <= d0 <= 6, 1 <= d1 <= 15}

Definition at line 1977 of file IntegerRelation.cpp.

References mlir::failure(), getCommonConstraints(), getConstantBoundOnDimSize(), getNumCols(), getNumDimVars(), getNumLocalVars(), getNumSymbolVars(), mlir::presburger::PresburgerSpace::getRelationSpace(), getSpace(), mlir::presburger::PresburgerSpace::isEqual(), and space.

Referenced by projectOut().

Member Data Documentation

◆ equalities

Matrix mlir::presburger::IntegerRelation::equalities
protected

◆ inequalities

Matrix mlir::presburger::IntegerRelation::inequalities
protected

◆ kExplosionFactor

constexpr unsigned mlir::presburger::IntegerRelation::kExplosionFactor = 32
staticprotected

A parameter that controls detection of an unrealistic number of constraints.

If the number of constraints is this many times the number of variables, we consider such a system out of line with the intended use case of IntegerRelation.

Definition at line 707 of file IntegerRelation.h.

Referenced by isEmpty().

◆ space

PresburgerSpace mlir::presburger::IntegerRelation::space
protected

The documentation for this class was generated from the following files: