FlatLinearConstraints is an extension of IntegerPolyhedron. More...

#include "mlir/Analysis/FlatLinearValueConstraints.h"

Inheritance diagram for mlir::FlatLinearConstraints:

Public Types
enum class	AddConservativeSemiAffineBounds { No = 0 , Yes }
	Flag to control if conservative semi-affine bounds should be added in `addBound()`. More...

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

Public Member Functions
	FlatLinearConstraints (unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals)
	Constructs a constraint system reserving memory for the specified number of constraints and variables. More...

	FlatLinearConstraints (unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)
	Constructs a constraint system with the specified number of dimensions and symbols. More...

	FlatLinearConstraints (const IntegerPolyhedron &fac)

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

LogicalResult	addBound (presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound, AddConservativeSemiAffineBounds=AddConservativeSemiAffineBounds::No)
	Adds a bound for the variable at the specified position with constraints being drawn from the specified bound map. More...

LogicalResult	addBound (presburger::BoundType type, unsigned pos, AffineMap boundMap, AddConservativeSemiAffineBounds=AddConservativeSemiAffineBounds::No)
	Adds a bound for the variable at the specified position with constraints being drawn from the specified bound map. More...

IntegerSet	getAsIntegerSet (MLIRContext *context) const
	Returns the constraint system as an integer set. More...

void	getSliceBounds (unsigned offset, unsigned num, MLIRContext context, SmallVectorImpl< AffineMap > lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool closedUB=false)
	Computes the lower and upper bounds of the first `num` dimensional variables (starting at `offset`) as an affine map of the remaining variables (dimensional and symbolic). More...

LogicalResult	composeMatchingMap (AffineMap other)
	Composes an affine map whose dimensions and symbols match one to one with the dimensions and symbols of this FlatLinearConstraints. More...

std::pair< AffineMap, AffineMap >	getLowerAndUpperBound (unsigned pos, unsigned offset, unsigned num, unsigned symStartPos, ArrayRef< AffineExpr > localExprs, MLIRContext *context, bool closedUB=false) const
	Gets the lower and upper bound of the `offset` + `pos`th variable treating [0, offset) U [offset + num, symStartPos) as dimensions and [symStartPos, getNumDimAndSymbolVars) as symbols, and `pos` lies in [0, num). More...

unsigned	insertDimVar (unsigned pos, unsigned num=1)
	Insert variables of the specified kind at position `pos`. More...

unsigned	insertSymbolVar (unsigned pos, unsigned num=1)

unsigned	insertLocalVar (unsigned pos, unsigned num=1)

unsigned	appendDimVar (unsigned num=1)
	Append variables of the specified kind after the last variable of that kind. More...

unsigned	appendSymbolVar (unsigned num=1)

unsigned	appendLocalVar (unsigned num=1)

Public Member Functions inherited from mlir::presburger::IntegerPolyhedron
	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 PresburgerSpace &space, IntMatrix inequalities)
	Constructs a relation with the specified number of dimensions and symbols and adds the given inequalities. More...

	IntegerPolyhedron (const PresburgerSpace &space, FracMatrix inequalities)
	Constructs a relation with the specified number of dimensions and symbols and adds the given inequalities, after normalizing row-wise to integer values. 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< IntegerPolyhedron >	clone () 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< IntegerRelation >	clone () const

const PresburgerSpace &	getSpace () 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...

void	setId (VarKind kind, unsigned i, Identifier id)
	Set the identifier for the ith variable of the specified kind of the IntegerRelation's PresburgerSpace. More...

void	resetIds ()

ArrayRef< Identifier >	getIds (VarKind kind)
	Get the identifiers for the variables of specified varKind. 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	isObviouslyEqual (const IntegerRelation &other) const
	Perform a quick equality check on `this` and `other`. More...

bool	isSubsetOf (const IntegerRelation &other) const
	Return whether this is a subset of the given IntegerRelation. More...

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

DynamicAPInt &	atEq (unsigned i, unsigned j)

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

DynamicAPInt &	atIneq (unsigned i, unsigned j)

unsigned	getNumConstraints () const

unsigned	getNumDomainVars () const

unsigned	getNumRangeVars () const

unsigned	getNumSymbolVars () const

unsigned	getNumLocalVars () const

unsigned	getNumDimVars () const

unsigned	getNumDimAndSymbolVars () const

unsigned	getNumVars () const

unsigned	getNumCols () const
	Returns the number of columns in the constraint system. More...

unsigned	getNumEqualities () const

unsigned	getNumInequalities () const

unsigned	getNumReservedEqualities () const

unsigned	getNumReservedInequalities () const

ArrayRef< DynamicAPInt >	getEquality (unsigned idx) const

ArrayRef< DynamicAPInt >	getInequality (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

IntMatrix	getInequalities () 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< DynamicAPInt > inEq)
	Adds an inequality (>= 0) from the coefficients specified in `inEq`. More...

void	addInequality (ArrayRef< int64_t > inEq)

void	addEquality (ArrayRef< DynamicAPInt > 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< DynamicAPInt, 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< DynamicAPInt > values)
	Sets the `values.size()` variables starting at `po`s 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	isObviouslyEmpty () const
	Performs GCD checks and invalid constraint checks. 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...

IntMatrix	getBoundedDirections () const
	Returns a matrix where each row is a vector along which the polytope is bounded. More...

std::optional< SmallVector< DynamicAPInt, 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< DynamicAPInt >	computeVolume () const
	Compute an overapproximation of the number of integer points in the relation. More...

bool	containsPoint (ArrayRef< DynamicAPInt > 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< DynamicAPInt, 8 > >	containsPointNoLocal (ArrayRef< DynamicAPInt > 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< DynamicAPInt, 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 DynamicAPInt &value)
	Adds a constant bound for the specified variable. More...

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

void	addBound (BoundType type, ArrayRef< DynamicAPInt > expr, const DynamicAPInt &value)
	Adds a constant bound for the specified expression. More...

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

void	addLocalFloorDiv (ArrayRef< DynamicAPInt > dividend, const DynamicAPInt &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< DynamicAPInt >	getConstantBoundOnDimSize (unsigned pos, SmallVectorImpl< DynamicAPInt > lb=nullptr, DynamicAPInt boundFloorDivisor=nullptr, SmallVectorImpl< DynamicAPInt > 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< DynamicAPInt >	getConstantBound (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	simplify ()
	Simplify the constraint system by removing canonicalizing constraints and removing redundant constraints. More...

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)

void	mergeAndAlignSymbols (IntegerRelation &other)
	Merge and align symbol variables of `this` and `other` with respect to identifiers. More...

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

void	mergeAndCompose (const IntegerRelation &other)
	Given a relation `other: (A -> B)`, this operation merges the symbol and local variables and then takes the composition of `other` on `this: (B -> C)`. More...

PresburgerRelation	computeReprWithOnlyDivLocals () const
	Compute an equivalent representation of the same set, such that all local vars in all disjuncts have division representations. More...

SymbolicLexOpt	findSymbolicIntegerLexMin () const
	Compute the symbolic integer lexmin of the relation. More...

SymbolicLexOpt	findSymbolicIntegerLexMax () const
	Same as findSymbolicIntegerLexMin but produces lexmax instead of lexmin. 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	removeTrivialEqualities ()

bool	isFullDim ()

void	print (raw_ostream &os) const

void	dump () const

Protected Types
using	VarKind = presburger::VarKind

Protected Member Functions
LogicalResult	computeLocalVars (SmallVectorImpl< AffineExpr > &memo, MLIRContext *context) const
	Compute an explicit representation for local vars. More...

LogicalResult	flattenAlignedMapAndMergeLocals (AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, bool addConservativeSemiAffineBounds=false)
	Given an affine map that is aligned with this constraint system: More...

void	printSpace (raw_ostream &os) const override
	Prints the number of constraints, dimensions, symbols and locals in the FlatLinearConstraints. 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>
std::optional< DynamicAPInt >	computeConstantLowerOrUpperBound (unsigned pos)
	Returns the constant lower 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...

bool	gaussianEliminate ()
	Perform a Gaussian elimination operation to reduce all equations to standard form. 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...

bool	removeDuplicateConstraints ()
	Checks for identical inequalities and eliminates redundant inequalities. 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...

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

Additional Inherited Members
Static Public Member Functions inherited from mlir::presburger::IntegerPolyhedron
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 IntegerRelation	getEmpty (const PresburgerSpace &space)
	Return an empty system containing an invalid equation 0 = 1. More...

static bool	classof (const IntegerRelation *cst)

Protected Attributes inherited from mlir::presburger::IntegerRelation
PresburgerSpace	space

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

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

Static Protected Attributes inherited from mlir::presburger::IntegerRelation
constexpr static unsigned	kExplosionFactor = 32
	A parameter that controls detection of an unrealistic number of constraints. More...

Detailed Description

FlatLinearConstraints is an extension of IntegerPolyhedron.

It provides an AffineExpr-based API.

Definition at line 33 of file FlatLinearValueConstraints.h.

Member Typedef Documentation

◆ VarKind

using mlir::FlatLinearConstraints::VarKind = presburger::VarKind

protected

Definition at line 198 of file FlatLinearValueConstraints.h.

Member Enumeration Documentation

◆ AddConservativeSemiAffineBounds

enum mlir::FlatLinearConstraints::AddConservativeSemiAffineBounds

strong

Flag to control if conservative semi-affine bounds should be added in addBound().

Enumerator
No
Yes

Definition at line 70 of file FlatLinearValueConstraints.h.

Constructor & Destructor Documentation

◆ FlatLinearConstraints() [1/3]

mlir::FlatLinearConstraints::FlatLinearConstraints	(	unsigned	numReservedInequalities,
		unsigned	numReservedEqualities,
		unsigned	numReservedCols,
		unsigned	numDims,
		unsigned	numSymbols,
		unsigned	numLocals
	)

inline

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

valArgs are the optional SSA values associated with each dimension/symbol. These must either be empty or match the number of dimensions and symbols.

Definition at line 39 of file FlatLinearValueConstraints.h.

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

◆ FlatLinearConstraints() [2/3]

mlir::FlatLinearConstraints::FlatLinearConstraints	(	unsigned	numDims = `0`,
		unsigned	numSymbols = `0`,
		unsigned	numLocals = `0`
	)

inline

Constructs a constraint system with the specified number of dimensions and symbols.

valArgs are the optional SSA values associated with each dimension/symbol. These must either be empty or match the number of dimensions and symbols.

Definition at line 54 of file FlatLinearValueConstraints.h.

◆ FlatLinearConstraints() [3/3]

mlir::FlatLinearConstraints::FlatLinearConstraints ( const IntegerPolyhedron & fac )

inline

Definition at line 62 of file FlatLinearValueConstraints.h.

Member Function Documentation

◆ addBound() [1/2]

LogicalResult FlatLinearConstraints::addBound	(	presburger::BoundType	type,
		unsigned	pos,
		AffineMap	boundMap,
		AddConservativeSemiAffineBounds	addSemiAffineBounds = `AddConservativeSemiAffineBounds::No`
	)

Adds a bound for the variable at the specified position with constraints being drawn from the specified bound map.

In case of an EQ bound, the bound map is expected to have exactly one result. In case of a LB/UB, the bound map may have more than one result, for each of which an inequality is added.

Conservative bounds for semi-affine expressions will be added if AddConservativeSemiAffineBounds is set to Yes. This currently only covers semi-affine mod expressions, so addBound() will still fail if it encounters a semi-affine floordiv, ceildiv, or mul. Note: If enabled it is possible for the resulting constraint set to become empty if a precondition of a conservative bound is found not to hold.

Note: The dimensions/symbols of this FlatLinearConstraints must match the dimensions/symbols of the affine map. By default the lower bound is closed and the upper bound is open.

Definition at line 791 of file FlatLinearValueConstraints.cpp.

References mlir::presburger::UB.

◆ addBound() [2/2]

LogicalResult FlatLinearConstraints::addBound	(	presburger::BoundType	type,
		unsigned	pos,
		AffineMap	boundMap,
		bool	isClosedBound,
		AddConservativeSemiAffineBounds	addSemiAffineBounds = `AddConservativeSemiAffineBounds::No`
	)

Adds a bound for the variable at the specified position with constraints being drawn from the specified bound map.

In case of an EQ bound, the bound map is expected to have exactly one result. In case of a LB/UB, the bound map may have more than one result, for each of which an inequality is added.

The bound can be added as open or closed by specifying isClosedBound. In case of a LB/UB, isClosedBound = false means the bound is added internally as a closed bound by +1/-1 respectively. In case of an EQ bound, it can only be added as a closed bound.

Conservative bounds for semi-affine expressions will be added if AddConservativeSemiAffineBounds is set to Yes. This currently only covers semi-affine mod expressions, so addBound() will still fail if it encounters a semi-affine floordiv, ceildiv, or mul. Note: If enabled it is possible for the resulting constraint set to become empty if a precondition of a conservative bound is found not to hold.

Note: The dimensions/symbols of this FlatLinearConstraints must match the dimensions/symbols of the affine map.

Definition at line 737 of file FlatLinearValueConstraints.cpp.

References mlir::presburger::EQ, mlir::AffineMap::getNumDims(), mlir::AffineMap::getNumInputs(), mlir::AffineMap::getNumResults(), mlir::AffineMap::getNumSymbols(), and mlir::presburger::LB.

Referenced by mlir::ValueBoundsConstraintSet::addBound(), mlir::ValueBoundsConstraintSet::BoundBuilder::operator<(), mlir::ValueBoundsConstraintSet::BoundBuilder::operator==(), and mlir::ValueBoundsConstraintSet::BoundBuilder::operator>=().

◆ appendDimVar()

unsigned mlir::FlatLinearConstraints::appendDimVar ( unsigned num = 1 )

inline

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

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

Note: Empty Values are allowed in vals.

Definition at line 187 of file FlatLinearValueConstraints.h.

References mlir::presburger::IntegerRelation::appendVar().

◆ appendLocalVar()

unsigned mlir::FlatLinearConstraints::appendLocalVar ( unsigned num = 1 )

inline

Definition at line 193 of file FlatLinearValueConstraints.h.

References mlir::presburger::IntegerRelation::appendVar().

Referenced by flattenAlignedMapAndMergeLocals().

◆ appendSymbolVar()

unsigned mlir::FlatLinearConstraints::appendSymbolVar ( unsigned num = 1 )

inline

Definition at line 190 of file FlatLinearValueConstraints.h.

References mlir::presburger::IntegerRelation::appendVar().

◆ composeMatchingMap()

LogicalResult FlatLinearConstraints::composeMatchingMap ( AffineMap other )

Composes an affine map whose dimensions and symbols match one to one with the dimensions and symbols of this FlatLinearConstraints.

The results of the map other are added as the leading dimensions of this constraint system. Returns failure if other is a semi-affine map.

Definition at line 227 of file FlatLinearValueConstraints.cpp.

References mlir::AffineMap::getNumDims(), mlir::AffineMap::getNumResults(), and mlir::AffineMap::getNumSymbols().

Referenced by mlir::affine::normalizeMemRefType().

◆ computeLocalVars()

LogicalResult FlatLinearConstraints::computeLocalVars	(	SmallVectorImpl< AffineExpr > &	memo,
		MLIRContext *	context
	)		const

protected

Compute an explicit representation for local vars.

For all systems coming from MLIR integer sets, maps, or expressions where local vars were introduced to model floordivs and mods, this always succeeds.

Definition at line 802 of file FlatLinearValueConstraints.cpp.

References detectAsFloorDiv(), mlir::getAffineDimExpr(), and mlir::getAffineSymbolExpr().

◆ flattenAlignedMapAndMergeLocals()

LogicalResult FlatLinearConstraints::flattenAlignedMapAndMergeLocals	(	AffineMap	map,
		std::vector< SmallVector< int64_t, 8 >> *	flattenedExprs,
		bool	addConservativeSemiAffineBounds = `false`
	)

protected

Given an affine map that is aligned with this constraint system:

Flatten the map.
Add newly introduced local columns at the beginning of this constraint system (local column pos 0).
Add equalities that define the new local columns to this constraint system.
Return the flattened expressions via flattenedExprs.

Note: This is a shared helper function of addLowerOrUpperBound and composeMatchingMap.

Definition at line 711 of file FlatLinearValueConstraints.cpp.

References appendLocalVar(), mlir::getFlattenedAffineExprs(), and mlir::presburger::IntegerRelation::getNumLocalVars().

◆ getAsIntegerSet()

IntegerSet FlatLinearConstraints::getAsIntegerSet ( MLIRContext * context ) const

Returns the constraint system as an integer set.

Returns a null integer set if the system has no constraints, or if an integer set couldn't be constructed as a result of a local variable's explicit representation not being known and such a local variable appearing in any of the constraints.

Definition at line 831 of file FlatLinearValueConstraints.cpp.

References mlir::IntegerSet::get(), mlir::getAffineConstantExpr(), and mlir::getAffineExprFromFlatForm().

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

◆ getKind()

Kind mlir::FlatLinearConstraints::getKind ( ) const

inlineoverridevirtual

Return the kind of this object.

Reimplemented from mlir::presburger::IntegerRelation.

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

Definition at line 66 of file FlatLinearValueConstraints.h.

References mlir::presburger::IntegerRelation::FlatLinearConstraints.

◆ getLowerAndUpperBound()

std::pair< AffineMap, AffineMap > FlatLinearConstraints::getLowerAndUpperBound	(	unsigned	pos,
		unsigned	offset,
		unsigned	num,
		unsigned	symStartPos,
		ArrayRef< AffineExpr >	localExprs,
		MLIRContext *	context,
		bool	closedUB = `false`
	)		const

Gets the lower and upper bound of the offset + posth variable treating [0, offset) U [offset + num, symStartPos) as dimensions and [symStartPos, getNumDimAndSymbolVars) as symbols, and pos lies in [0, num).

The multi-dimensional maps in the returned pair represent the max and min of potentially multiple affine expressions. localExprs holds pre-computed AffineExpr's for all local variables in the system.

By default the returned lower bounds are closed and upper bounds are open. If closedUb is true, the upper bound is closed.

Add to 'b' from 'a' in set [0, offset) U [offset + num, symbStartPos).

Definition at line 448 of file FlatLinearValueConstraints.cpp.

References mlir::presburger::abs(), mlir::AffineMap::get(), and mlir::getAffineExprFromFlatForm().

◆ getSliceBounds()

void FlatLinearConstraints::getSliceBounds	(	unsigned	offset,
		unsigned	num,
		MLIRContext *	context,
		SmallVectorImpl< AffineMap > *	lbMaps,
		SmallVectorImpl< AffineMap > *	ubMaps,
		bool	closedUB = `false`
	)

Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an affine map of the remaining variables (dimensional and symbolic).

Computes the lower and upper bounds of the first 'num' dimensional variables (starting at 'offset') as affine maps of the remaining variables (dimensional and symbolic variables).

This method is able to detect variables as floordiv's and mod's of affine expressions of other variables with respect to (positive) constants. Sets bound map to a null AffineMap if such a bound can't be found (or yet unimplemented).

By default the returned lower bounds are closed and upper bounds are open. If closedUb is true, the upper bound is closed.

Local variables are themselves explicitly computed as affine functions of other variables in this process if needed.

Definition at line 537 of file FlatLinearValueConstraints.cpp.

References detectAsFloorDiv(), detectAsMod(), mlir::AffineMap::dump(), mlir::AffineMap::get(), mlir::getAffineConstantExpr(), mlir::getAffineDimExpr(), mlir::getAffineSymbolExpr(), mlir::AffineMap::getNumResults(), mlir::presburger::LB, mlir::simplifyAffineExpr(), and mlir::presburger::UB.

Referenced by mlir::ValueBoundsConstraintSet::computeBound(), mlir::affine::computeSliceUnion(), mlir::affine::getComputationSliceState(), and mlir::affine::simplifyConstrainedMinMaxOp().

◆ insertDimVar()

unsigned mlir::FlatLinearConstraints::insertDimVar	(	unsigned	pos,
		unsigned	num = `1`
	)

inline

Insert 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. vals are the Values corresponding to the variables. Values should not be used with VarKind::Local since values can only be attached to non-local variables. Return the absolute column position (i.e., not relative to the kind of variable) of the first added variable.

Note: Empty Values are allowed in vals.

Definition at line 170 of file FlatLinearValueConstraints.h.

References mlir::presburger::IntegerPolyhedron::insertVar().