MLIR  17.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 class  Kind { FlatAffineConstraints , FlatAffineValueConstraints , IntegerRelation , 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...
 
MPInt atEq (unsigned i, unsigned j) const
 Returns the value at the specified equality row and column. More...
 
int64_t atEq64 (unsigned i, unsigned j) const
 The same, but casts to int64_t. More...
 
MPIntatEq (unsigned i, unsigned j)
 
MPInt atIneq (unsigned i, unsigned j) const
 Returns the value at the specified inequality row and column. More...
 
int64_t atIneq64 (unsigned i, unsigned j) const
 The same, but casts to int64_t. More...
 
MPIntatIneq (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< MPIntgetEquality (unsigned idx) const
 
ArrayRef< MPIntgetInequality (unsigned idx) const
 
SmallVector< int64_t, 8 > getEquality64 (unsigned idx) const
 The same, but casts to int64_t. More...
 
SmallVector< int64_t, 8 > getInequality64 (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< MPInt > inEq)
 Adds an inequality (>= 0) from the coefficients specified in inEq. More...
 
void addInequality (ArrayRef< int64_t > inEq)
 
void addEquality (ArrayRef< MPInt > eq)
 Adds an equality from the coefficients specified in eq. More...
 
void addEquality (ArrayRef< int64_t > eq)
 
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< MPInt, 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< MPInt > values)
 Sets the values.size() variables starting at pos to the specified values and removes them. More...
 
void setAndEliminate (unsigned pos, ArrayRef< int64_t > values)
 
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...
 
std::optional< SmallVector< MPInt, 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...
 
std::optional< MPIntcomputeVolume () const
 Compute an overapproximation of the number of integer points in the relation. More...
 
bool containsPoint (ArrayRef< MPInt > point) const
 Returns true if the given point satisfies the constraints, or false otherwise. More...
 
bool containsPoint (ArrayRef< int64_t > point) const
 
std::optional< SmallVector< MPInt, 8 > > containsPointNoLocal (ArrayRef< MPInt > 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...
 
std::optional< SmallVector< MPInt, 8 > > containsPointNoLocal (ArrayRef< int64_t > point) const
 
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, const MPInt &value)
 Adds a constant bound for the specified variable. More...
 
void addBound (BoundType type, unsigned pos, int64_t value)
 
void addBound (BoundType type, ArrayRef< MPInt > expr, const MPInt &value)
 Adds a constant bound for the specified expression. More...
 
void addBound (BoundType type, ArrayRef< int64_t > expr, int64_t value)
 
void addLocalFloorDiv (ArrayRef< MPInt > dividend, const MPInt &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 addLocalFloorDiv (ArrayRef< int64_t > dividend, int64_t divisor)
 
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...
 
std::optional< MPIntgetConstantBoundOnDimSize (unsigned pos, SmallVectorImpl< MPInt > *lb=nullptr, MPInt *boundFloorDivisor=nullptr, SmallVectorImpl< MPInt > *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...
 
std::optional< int64_t > getConstantBoundOnDimSize64 (unsigned pos, SmallVectorImpl< int64_t > *lb=nullptr, int64_t *boundFloorDivisor=nullptr, SmallVectorImpl< int64_t > *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const
 The same, but casts to int64_t. More...
 
std::optional< MPIntgetConstantBound (BoundType type, unsigned pos) const
 Returns the constant bound for the pos^th variable if there is one; std::nullopt otherwise. More...
 
std::optional< int64_t > getConstantBound64 (BoundType type, unsigned pos) const
 The same, but casts to int64_t. 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>
std::optional< MPIntcomputeConstantLowerOrUpperBound (unsigned pos)
 Returns the constant lower bound bound if isLower is true, and the upper bound if isLower is false. More...
 
template<bool isLower>
std::optional< int64_t > computeConstantLowerOrUpperBound64 (unsigned pos)
 The same, but casts to int64_t. 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

constexpr static 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 53 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 399 of file IntegerRelation.h.

◆ Kind

All derived classes of IntegerRelation.

Enumerator
FlatAffineConstraints 
FlatAffineValueConstraints 
IntegerRelation 
IntegerPolyhedron 

Definition at line 56 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 65 of file IntegerRelation.h.

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

Referenced by getConstantBound(), and getUniverse().

◆ 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 76 of file IntegerRelation.h.

◆ ~IntegerRelation()

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

Member Function Documentation

◆ addBound() [1/4]

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

Definition at line 409 of file IntegerRelation.h.

References addBound(), and mlir::presburger::getMPIntVec().

◆ addBound() [2/4]

void IntegerRelation::addBound ( BoundType  type,
ArrayRef< MPInt expr,
const MPInt value 
)

Adds a constant bound for the specified expression.

Definition at line 1300 of file IntegerRelation.cpp.

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

◆ addBound() [3/4]

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

Adds a constant bound for the specified variable.

Definition at line 1285 of file IntegerRelation.cpp.

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

Referenced by addBound(), and mlir::presburger::MultiAffineFunction::getLexSet().

◆ addBound() [4/4]

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

Definition at line 403 of file IntegerRelation.h.

References addBound().

◆ addEquality() [1/2]

void mlir::presburger::IntegerRelation::addEquality ( ArrayRef< int64_t >  eq)
inline

Definition at line 272 of file IntegerRelation.h.

References addEquality(), and mlir::presburger::getMPIntVec().

Referenced by addEquality().

◆ addEquality() [2/2]

void IntegerRelation::addEquality ( ArrayRef< MPInt eq)

◆ addInequality() [1/2]

void mlir::presburger::IntegerRelation::addInequality ( ArrayRef< int64_t >  inEq)
inline

Definition at line 267 of file IntegerRelation.h.

References addInequality(), and mlir::presburger::getMPIntVec().

◆ addInequality() [2/2]

void IntegerRelation::addInequality ( ArrayRef< MPInt inEq)

◆ addLocalFloorDiv() [1/2]

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

Definition at line 419 of file IntegerRelation.h.

References addLocalFloorDiv(), and mlir::presburger::getMPIntVec().

◆ addLocalFloorDiv() [2/2]

void IntegerRelation::addLocalFloorDiv ( ArrayRef< MPInt dividend,
const MPInt 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 1316 of file IntegerRelation.cpp.

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

Referenced by mlir::FlatAffineValueConstraints::addAffineForOpDomain(), and addLocalFloorDiv().

◆ 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 271 of file IntegerRelation.cpp.

References getNumVarKind(), and insertVar().

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 2232 of file IntegerRelation.cpp.

References compose(), and inverse().

◆ 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 2238 of file IntegerRelation.cpp.

References compose().

◆ atEq() [1/2]

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

Definition at line 143 of file IntegerRelation.h.

References equalities.

◆ atEq() [2/2]

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

◆ atEq64()

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

The same, but casts to int64_t.

This is unsafe and will assert-fail if the value does not fit in an int64_t.

Definition at line 140 of file IntegerRelation.h.

References equalities.

Referenced by detectAsMod(), and mlir::FlatAffineValueConstraints::getSliceBounds().

◆ atIneq() [1/2]

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

Definition at line 154 of file IntegerRelation.h.

References inequalities.

◆ atIneq() [2/2]

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

◆ atIneq64()

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

The same, but casts to int64_t.

This is unsafe and will assert-fail if the value does not fit in an int64_t.

Definition at line 151 of file IntegerRelation.h.

References inequalities.

◆ classof()

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

Definition at line 92 of file IntegerRelation.h.

◆ clearAndCopyFrom()

void IntegerRelation::clearAndCopyFrom ( const IntegerRelation other)
virtual

Replaces the contents of this IntegerRelation with other.

Definition at line 464 of file IntegerRelation.cpp.

Referenced by fourierMotzkinEliminate().

◆ clearConstraints()

void IntegerRelation::clearConstraints ( )

Removes all equalities and inequalities.

Definition at line 381 of file IntegerRelation.cpp.

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

Referenced by unionBoundingBox().

◆ clone()

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

Definition at line 35 of file IntegerRelation.cpp.

◆ 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 2206 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(), and applyRange().

◆ computeConstantLowerOrUpperBound()

template<bool isLower>
std::optional< MPInt > 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 1522 of file IntegerRelation.cpp.

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

◆ computeConstantLowerOrUpperBound64()

template<bool isLower>
std::optional<int64_t> mlir::presburger::IntegerRelation::computeConstantLowerOrUpperBound64 ( unsigned  pos)
inlineprotected

The same, but casts to int64_t.

This is unsafe and will assert-fail if the value does not fit in an int64_t.

Definition at line 691 of file IntegerRelation.h.

References mlir::presburger::int64FromMPInt().

◆ 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 169 of file IntegerRelation.cpp.

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

◆ computeVolume()

std::optional< MPInt > 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 1085 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 1361 of file IntegerRelation.cpp.

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

Referenced by constantFoldVarRange().

◆ 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 1374 of file IntegerRelation.cpp.

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

◆ containsPoint() [1/2]

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

Definition at line 375 of file IntegerRelation.h.

References containsPoint(), and mlir::presburger::getMPIntVec().

◆ containsPoint() [2/2]

bool IntegerRelation::containsPoint ( ArrayRef< MPInt 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 886 of file IntegerRelation.cpp.

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

Referenced by containsPoint(), and findIntegerSample().

◆ containsPointNoLocal() [1/2]

std::optional<SmallVector<MPInt, 8> > mlir::presburger::IntegerRelation::containsPointNoLocal ( ArrayRef< int64_t >  point) const
inline

Definition at line 383 of file IntegerRelation.h.

References containsPointNoLocal(), and mlir::presburger::getMPIntVec().

◆ containsPointNoLocal() [2/2]

std::optional< SmallVector< MPInt, 8 > > IntegerRelation::containsPointNoLocal ( ArrayRef< MPInt 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 907 of file IntegerRelation.cpp.

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

Referenced by mlir::presburger::PresburgerRelation::containsPoint(), and containsPointNoLocal().

◆ convertToLocal()

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

◆ convertVarKind() [1/2]

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

Definition at line 546 of file IntegerRelation.h.

References convertVarKind(), and getNumVarKind().

◆ convertVarKind() [2/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 1258 of file IntegerRelation.cpp.

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

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

◆ 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 1141 of file IntegerRelation.cpp.

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

Referenced by 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 471 of file IntegerRelation.cpp.

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

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

◆ findIntegerLexMin()

MaybeOptimum< SmallVector< MPInt, 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 108 of file IntegerRelation.cpp.

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

◆ findIntegerSample()

std::optional< SmallVector< MPInt, 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 768 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 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 89 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 230 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::PWMAFunction::removeOutputs(), and mlir::presburger::Symbol.

◆ 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 1739 of file IntegerRelation.cpp.

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

Referenced by 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 698 of file IntegerRelation.h.

References gaussianEliminateVars(), and mlir::success().

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 972 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 960 of file IntegerRelation.cpp.

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

Referenced by fourierMotzkinEliminate(), 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 679 of file IntegerRelation.cpp.

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

Referenced by findIntegerSample().

◆ getConstantBound()

std::optional< MPInt > IntegerRelation::getConstantBound ( BoundType  type,
unsigned  pos 
) const

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

Definition at line 1578 of file IntegerRelation.cpp.

References IntegerRelation().

Referenced by getConstantBound64(), and unionBoundingBox().

◆ getConstantBound64()

std::optional<int64_t> mlir::presburger::IntegerRelation::getConstantBound64 ( BoundType  type,
unsigned  pos 
) const
inline

The same, but casts to int64_t.

This is unsafe and will assert-fail if the value does not fit in an int64_t.

Definition at line 505 of file IntegerRelation.h.

References getConstantBound(), and mlir::presburger::int64FromMPInt().

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

◆ getConstantBoundOnDimSize()

std::optional< MPInt > IntegerRelation::getConstantBoundOnDimSize ( unsigned  pos,
SmallVectorImpl< MPInt > *  lb = nullptr,
MPInt boundFloorDivisor = nullptr,
SmallVectorImpl< MPInt > *  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 std::nullopt if it's not a constant.

This constant bound is guaranteed to be non-negative. Returns std::nullopt 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 1395 of file IntegerRelation.cpp.

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

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

◆ getConstantBoundOnDimSize64()

std::optional<int64_t> mlir::presburger::IntegerRelation::getConstantBoundOnDimSize64 ( unsigned  pos,
SmallVectorImpl< int64_t > *  lb = nullptr,
int64_t *  boundFloorDivisor = nullptr,
SmallVectorImpl< int64_t > *  ub = nullptr,
unsigned *  minLbPos = nullptr,
unsigned *  minUbPos = nullptr 
) const
inline

The same, but casts to int64_t.

This is unsafe and will assert-fail if the value does not fit in an int64_t.

Definition at line 482 of file IntegerRelation.h.

References getConstantBoundOnDimSize(), mlir::presburger::getInt64Vec(), and mlir::presburger::int64FromMPInt().

Referenced by mlir::MemRefRegion::getConstantBoundingSizeAndShape(), and mlir::MemRefRegion::getConstantBoundOnDimSize().

◆ getCounts()

IntegerRelation::CountsSnapshot IntegerRelation::getCounts ( ) const

◆ getDomainSet()

IntegerPolyhedron IntegerRelation::getDomainSet ( ) const

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

Definition at line 2143 of file IntegerRelation.cpp.

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

Referenced by compose(), and intersectDomain().

◆ getEquality()

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

◆ getEquality64()

SmallVector<int64_t, 8> mlir::presburger::IntegerRelation::getEquality64 ( unsigned  idx) const
inline

The same, but casts to int64_t.

This is unsafe and will assert-fail if the value does not fit in an int64_t.

Definition at line 196 of file IntegerRelation.h.

References equalities, mlir::presburger::getInt64Vec(), and mlir::presburger::Matrix::getRow().

Referenced by mlir::FlatAffineValueConstraints::getAsIntegerSet(), and mlir::FlatAffineValueConstraints::getLowerAndUpperBound().

◆ getInequality()

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

◆ getInequality64()

SmallVector<int64_t, 8> mlir::presburger::IntegerRelation::getInequality64 ( unsigned  idx) const
inline

◆ getKind()

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

Return the kind of this IntegerRelation.

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

Definition at line 90 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 918 of file IntegerRelation.cpp.

References mlir::presburger::DivisionRepr::clearRepr(), mlir::presburger::computeSingleVarRepr(), mlir::presburger::DivisionRepr::getDenom(), mlir::presburger::DivisionRepr::getDividend(), getNumDimAndSymbolVars(), getNumLocalVars(), getNumVars(), getVarKindOffset(), and mlir::presburger::Local.

Referenced by mlir::getMultiAffineFunctionFromMap(), 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 389 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 161 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 2157 of file IntegerRelation.cpp.

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

Referenced by compose(), and intersectRange().

◆ 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 85 of file IntegerRelation.h.

References IntegerRelation(), and space.

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 226 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

◆ 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 220 of file IntegerRelation.h.

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

◆ 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 440 of file IntegerRelation.cpp.

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

Referenced by fourierMotzkinEliminate(), 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 493 of file IntegerRelation.cpp.

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

Referenced by isEmpty().

◆ hasOnlyDivLocals()

bool IntegerRelation::hasOnlyDivLocals ( ) const

Check whether all local ids have a division representation.

Definition at line 1197 of file IntegerRelation.cpp.

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

Referenced by 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 262 of file IntegerRelation.cpp.

References equalities, getNumVarKind(), inequalities, mlir::presburger::Matrix::insertColumns(), mlir::presburger::PresburgerSpace::insertVar(), and space.

Referenced by appendVar(), convertVarKind(), mlir::presburger::MultiAffineFunction::getAsRelation(), mlir::presburger::IntegerPolyhedron::insertVar(), 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 71 of file IntegerRelation.cpp.

References append(), and mergeLocalVars().

Referenced by mlir::presburger::IntegerPolyhedron::intersect(), and mlir::presburger::PresburgerRelation::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 2170 of file IntegerRelation.cpp.

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

Referenced by mlir::presburger::MultiAffineFunction::isEqual().

◆ 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 2186 of file IntegerRelation.cpp.

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

Referenced by compose().

◆ 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 2199 of file IntegerRelation.cpp.

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

Referenced by applyDomain(), and intersectDomain().

◆ 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 2089 of file IntegerRelation.cpp.

References findConstraintWithNonZeroAt().

Referenced by fourierMotzkinEliminate(), 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 596 of file IntegerRelation.cpp.

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

Referenced by mlir::checkMemrefAccessDependence(), mlir::presburger::PresburgerRelation::intersect(), removeRedundantInequalities(), mlir::simplifyConstrainedMinMaxOp(), 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 656 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 78 of file IntegerRelation.cpp.

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

Referenced by mlir::presburger::MultiAffineFunction::isEqual().

◆ 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 1598 of file IntegerRelation.cpp.

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

Referenced by checkIfHyperRectangular().

◆ 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 720 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 83 of file IntegerRelation.cpp.

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

◆ 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 1166 of file IntegerRelation.cpp.

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

Referenced by mlir::FlatAffineRelation::compose(), mlir::MemRefAccess::getAccessRelation(), 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 2240 of file IntegerRelation.cpp.

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

Referenced by print().

◆ projectOut() [1/2]

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

Definition at line 429 of file IntegerRelation.h.

References projectOut().

Referenced by projectOut().

◆ projectOut() [2/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 1895 of file IntegerRelation.cpp.

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

Referenced by computeConstantLowerOrUpperBound().

◆ 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 358 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 2127 of file IntegerRelation.cpp.

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

Referenced by createSeparationCondition().

◆ removeInequality()

void IntegerRelation::removeInequality ( unsigned  pos)

◆ removeInequalityRange()

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

Definition at line 364 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 1054 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().

◆ removeRedundantInequalities()

void IntegerRelation::removeRedundantInequalities ( )

◆ 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 1216 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(), 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 1628 of file IntegerRelation.cpp.

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

Referenced by createSeparationCondition(), fourierMotzkinEliminate(), mlir::simplifyIntegerSet(), and unionBoundingBox().

◆ removeVar() [1/2]

void IntegerRelation::removeVar ( unsigned  pos)

Removes the specified variable from the system.

Definition at line 294 of file IntegerRelation.cpp.

References removeVarRange().

◆ removeVar() [2/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 290 of file IntegerRelation.cpp.

References removeVarRange().

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

◆ removeVarRange() [1/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 312 of file IntegerRelation.cpp.

References mlir::presburger::Domain, getNumVarKind(), getNumVars(), getVarKindOffset(), mlir::presburger::Local, min(), mlir::presburger::Range, removeVarRange(), and mlir::presburger::Symbol.

◆ removeVarRange() [2/2]

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

◆ setAndEliminate() [1/2]

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

Definition at line 318 of file IntegerRelation.h.

References mlir::presburger::getMPIntVec(), and setAndEliminate().

◆ setAndEliminate() [2/2]

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

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

Definition at line 448 of file IntegerRelation.cpp.

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

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

◆ 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 586 of file IntegerRelation.h.

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

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 43 of file IntegerRelation.cpp.

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

◆ 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 48 of file IntegerRelation.cpp.

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

◆ 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 258 of file IntegerRelation.cpp.

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

Referenced by 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 370 of file IntegerRelation.cpp.

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

Referenced by convertVarKind().

◆ truncate()

void IntegerRelation::truncate ( const CountsSnapshot counts)

◆ truncateVarKind() [1/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 155 of file IntegerRelation.cpp.

References mlir::presburger::PresburgerSpace::getNumVarKind(), mlir::presburger::IntegerRelation::CountsSnapshot::getSpace(), and truncateVarKind().

◆ truncateVarKind() [2/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 149 of file IntegerRelation.cpp.

References getNumVarKind(), and removeVarRange().

Referenced by truncate(), and truncateVarKind().

◆ 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 1979 of file IntegerRelation.cpp.

References addInequality(), append(), clearConstraints(), copy(), mlir::failure(), getCommonConstraints(), getConstantBound(), getConstantBoundOnDimSize(), getNumCols(), getNumDimVars(), getNumLocalVars(), getNumSymbolVars(), mlir::presburger::PresburgerSpace::getRelationSpace(), getSpace(), mlir::presburger::PresburgerSpace::isEqual(), max(), min(), removeTrivialRedundancy(), space, and mlir::success().

Member Data Documentation

◆ equalities

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

◆ inequalities

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

◆ kExplosionFactor

constexpr static unsigned mlir::presburger::IntegerRelation::kExplosionFactor = 32
staticconstexprprotected

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 778 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: