MLIR  16.0.0git
mlir::presburger::IntegerPolyhedron Class Reference

An IntegerPolyhedron 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::IntegerPolyhedron:
Collaboration diagram for mlir::presburger::IntegerPolyhedron:

## Public Member Functions

IntegerPolyhedron (unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, const PresburgerSpace &space)
Constructs a set reserving memory for the specified number of constraints and variables. More...

IntegerPolyhedron (const PresburgerSpace &space)
Constructs a relation with the specified number of dimensions and symbols. More...

IntegerPolyhedron (const IntegerRelation &rel)
Construct a set from an IntegerRelation. More...

IntegerPolyhedron (IntegerRelation &&rel)
Construct a set from an IntegerRelation, but instead of creating a copy, use move constructor. More...

Kind getKind () const override
Return the kind of this IntegerRelation. More...

std::unique_ptr< IntegerPolyhedronclone () const

unsigned insertVar (VarKind kind, unsigned pos, unsigned num=1) override
Insert num variables of the specified kind at position pos. More...

IntegerPolyhedron intersect (const IntegerPolyhedron &other) const
Return the intersection of the two relations. More...

PresburgerSet subtract (const PresburgerSet &other) const
Return the set difference of this set and the given set, i.e., return this \ set. More...

Public Member Functions inherited from mlir::presburger::IntegerRelation
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

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)

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

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

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

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

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

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

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

Optional< MPIntgetConstantBound (BoundType type, unsigned pos) const
Returns the constant bound for the pos^th variable if there is one; None otherwise. More...

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

Static Public Member Functions inherited from mlir::presburger::IntegerRelation
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)

Public Types inherited from mlir::presburger::IntegerRelation
enum  Kind { Kind::FlatAffineConstraints, Kind::FlatAffineValueConstraints, Kind::IntegerRelation, Kind::IntegerPolyhedron }
All derived classes of IntegerRelation. More...

enum  BoundType { EQ, LB, UB }
The type of bound: equal, lower bound or upper bound. More...

Protected Member Functions inherited from mlir::presburger::IntegerRelation
bool hasInvalidConstraint () const
Checks all rows of equality/inequality constraints for trivial contradictions (for example: 1 == 0, 0 >= 1), which may have surfaced after elimination. More...

template<bool isLower>
Optional< 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>
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 inherited from mlir::presburger::IntegerRelation
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 inherited from mlir::presburger::IntegerRelation
static constexpr unsigned kExplosionFactor = 32
A parameter that controls detection of an unrealistic number of constraints. More...

## Detailed Description

An IntegerPolyhedron 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.

An IntegerPolyhedron is similar to an IntegerRelation but it does not make a distinction between Domain and Range variables. Internally, IntegerPolyhedron is implemented as a IntegerRelation with zero domain vars.

Since IntegerPolyhedron does not make a distinction between kinds of dimensions, VarKind::SetDim should be used to refer to dimension variables.

Definition at line 804 of file IntegerRelation.h.

## ◆ IntegerPolyhedron() [1/4]

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

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

Definition at line 808 of file IntegerRelation.h.

## ◆ IntegerPolyhedron() [2/4]

 mlir::presburger::IntegerPolyhedron::IntegerPolyhedron ( const PresburgerSpace & space )
inlineexplicit

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

Definition at line 819 of file IntegerRelation.h.

## ◆ IntegerPolyhedron() [3/4]

 mlir::presburger::IntegerPolyhedron::IntegerPolyhedron ( const IntegerRelation & rel )
inlineexplicit

Construct a set from an IntegerRelation.

The relation should have no domain vars.

Definition at line 826 of file IntegerRelation.h.

## ◆ IntegerPolyhedron() [4/4]

 mlir::presburger::IntegerPolyhedron::IntegerPolyhedron ( IntegerRelation && rel )
inlineexplicit

Construct a set from an IntegerRelation, but instead of creating a copy, use move constructor.

The relation should have no domain vars.

Definition at line 834 of file IntegerRelation.h.

## ◆ classof()

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

Definition at line 848 of file IntegerRelation.h.

## ◆ clone()

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

Definition at line 38 of file IntegerRelation.cpp.

## ◆ getKind()

 Kind mlir::presburger::IntegerPolyhedron::getKind ( ) const
inlineoverridevirtual

Return the kind of this IntegerRelation.

Reimplemented from mlir::presburger::IntegerRelation.

Reimplemented in mlir::FlatAffineValueConstraints.

Definition at line 846 of file IntegerRelation.h.

## ◆ getUniverse()

 static IntegerPolyhedron mlir::presburger::IntegerPolyhedron::getUniverse ( const PresburgerSpace & space )
inlinestatic

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

Definition at line 841 of file IntegerRelation.h.

## ◆ insertVar()

 unsigned IntegerPolyhedron::insertVar ( VarKind kind, unsigned pos, unsigned num = 1 )
overridevirtual

Insert num variables of the specified kind at position pos.

Positions are relative to the kind of variable. Return the absolute column position (i.e., not relative to the kind of variable) of the first added variable.

Reimplemented from mlir::presburger::IntegerRelation.

Reimplemented in mlir::FlatAffineValueConstraints.

Definition at line 2263 of file IntegerRelation.cpp.

## ◆ intersect()

 IntegerPolyhedron IntegerPolyhedron::intersect ( const IntegerPolyhedron & other ) const

Return the intersection of the two relations.

If there are locals, they will be merged.

Definition at line 2270 of file IntegerRelation.cpp.

## ◆ subtract()

 PresburgerSet IntegerPolyhedron::subtract ( const PresburgerSet & other ) const

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

Definition at line 2274 of file IntegerRelation.cpp.

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