MLIR  17.0.0git
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.

◆ BoundType

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

Enumerator
EQ
LB
UB

Definition at line 399 of file IntegerRelation.h.

◆ Kind

 strong

All derived classes of IntegerRelation.

Enumerator
FlatAffineConstraints
FlatAffineValueConstraints
IntegerRelation
IntegerPolyhedron

Definition at line 56 of file IntegerRelation.h.

◆ 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

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

Definition at line 409 of file IntegerRelation.h.

 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.

 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.

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

Definition at line 403 of file IntegerRelation.h.

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

Definition at line 272 of file IntegerRelation.h.

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

Adds an equality from the coefficients specified in eq.

Definition at line 276 of file IntegerRelation.cpp.

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

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

Definition at line 267 of file IntegerRelation.h.

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

Adds an inequality (>= 0) from the coefficients specified in inEq.

Definition at line 283 of file IntegerRelation.cpp.

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

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

Definition at line 419 of file IntegerRelation.h.

 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.

◆ append()

 void IntegerRelation::append ( const IntegerRelation & other )

Appends constraints from other into this.

This is equivalent to an intersection with no simplification of any sort attempted.

Definition at line 56 of file IntegerRelation.cpp.

◆ 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().

◆ 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

Returns the value at the specified equality row and column.

Definition at line 137 of file IntegerRelation.h.

References equalities.

◆ 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

Returns the value at the specified inequality row and column.

Definition at line 146 of file IntegerRelation.h.

References inequalities.

◆ 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.

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.

◆ computeConstantLowerOrUpperBound64()

template<bool isLower>
 std::optional 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.

◆ 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.

◆ 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.

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

Definition at line 551 of file IntegerRelation.h.

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

◆ 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

Definition at line 2263 of file IntegerRelation.cpp.

References print().

◆ 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.

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().

◆ 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.

◆ 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.

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.

◆ 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.

◆ 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.

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.

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.

◆ 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.

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 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().

◆ 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.

◆ getConstantBoundOnDimSize64()

 std::optional 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.

◆ getCounts()

 IntegerRelation::CountsSnapshot IntegerRelation::getCounts ( ) const

Definition at line 145 of file IntegerRelation.cpp.

References getNumEqualities(), getNumInequalities(), and getSpace().

◆ 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.

Referenced by compose(), and intersectDomain().

◆ getEquality()

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

◆ getEquality64()

 SmallVector 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.

◆ getInequality()

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

◆ getInequality64()

 SmallVector mlir::presburger::IntegerRelation::getInequality64 ( unsigned idx ) const
inline

Definition at line 199 of file IntegerRelation.h.

◆ 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.

◆ 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.

◆ getNumCols()

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

◆ getNumConstraints()

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

Definition at line 156 of file IntegerRelation.h.

References getNumEqualities(), and getNumInequalities().

◆ 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

Get the number of vars of the specified kind.

Definition at line 204 of file IntegerRelation.h.

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

◆ 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.

Referenced by compose(), and intersectRange().

◆ getSpace()

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

Returns a reference to the underlying space.

Definition at line 98 of file IntegerRelation.h.

References space.

◆ getSpaceWithoutLocals()

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

Returns a copy of the space without locals.

Definition at line 112 of file IntegerRelation.h.

Referenced by getSetDifference().

◆ 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.

◆ 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.

◆ getVarKindEnd()

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

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

Definition at line 214 of file IntegerRelation.h.

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

◆ getVarKindOffset()

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

Return the index at which the specified kind of vars starts.

Definition at line 209 of file IntegerRelation.h.

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

◆ 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.

◆ 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.

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.

◆ 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().

◆ 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.

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.

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.

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.

◆ 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.

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.

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.

◆ 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.

◆ normalizeConstraintsByGCD()

 void IntegerRelation::normalizeConstraintsByGCD ( )
protected

Normalized each constraints by the GCD of its coefficients.

Definition at line 486 of file IntegerRelation.cpp.

◆ print()

 void IntegerRelation::print ( raw_ostream & os ) const

Definition at line 2245 of file IntegerRelation.cpp.

Referenced by dump(), and mlir::presburger::PresburgerRelation::print().

◆ 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.

Referenced by computeConstantLowerOrUpperBound().

◆ removeDuplicateDivs()

 void IntegerRelation::removeDuplicateDivs ( )

Definition at line 1201 of file IntegerRelation.cpp.

Referenced by getSetDifference().

◆ removeEquality()

 void IntegerRelation::removeEquality ( unsigned pos )

Definition at line 350 of file IntegerRelation.cpp.

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

◆ 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.

Referenced by createSeparationCondition().

◆ removeInequality()

 void IntegerRelation::removeInequality ( unsigned pos )

Definition at line 354 of file IntegerRelation.cpp.

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

◆ 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.

◆ removeRedundantInequalities()

 void IntegerRelation::removeRedundantInequalities ( )

A more expensive check than removeTrivialRedundancy to detect redundant inequalities.

Definition at line 1022 of file IntegerRelation.cpp.

◆ 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.

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.

◆ 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().

◆ 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.

◆ removeVarRange() [2/2]

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

Reimplemented in mlir::FlatAffineRelation, and mlir::FlatAffineValueConstraints.

Definition at line 296 of file IntegerRelation.cpp.

◆ 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.

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.

◆ 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.

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.

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.

◆ 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.

◆ equalities

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

Coefficients of affine equalities (in == 0 form).

Definition at line 783 of file IntegerRelation.h.

◆ inequalities

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

Coefficients of affine inequalities (in >= 0 form).

Definition at line 786 of file IntegerRelation.h.

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