FlatAffineValueConstraints represents an extension of IntegerPolyhedron where each non-local variable can have an SSA Value attached to it. More...

#include "mlir/Dialect/Affine/Analysis/AffineStructures.h"

Inheritance diagram for mlir::FlatAffineValueConstraints:

Collaboration diagram for mlir::FlatAffineValueConstraints:

Public Member Functions
	FlatAffineValueConstraints (unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< std::optional< Value >> valArgs={})
	Constructs a constraint system reserving memory for the specified number of constraints and variables. More...

	FlatAffineValueConstraints (unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0, ArrayRef< std::optional< Value >> valArgs={})
	Constructs a constraint system with the specified number of dimensions and symbols. More...

	FlatAffineValueConstraints (const IntegerPolyhedron &fac, ArrayRef< std::optional< Value >> valArgs={})

	FlatAffineValueConstraints (const AffineValueMap &avm)
	Create a flat affine constraint system from an AffineValueMap or a list of these. More...

	FlatAffineValueConstraints (ArrayRef< const AffineValueMap * > avmRef)

	FlatAffineValueConstraints (IntegerSet set, ValueRange operands={})
	Creates an affine constraint system from an IntegerSet. More...

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

void	reset (unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals=0)
	Clears any existing data and reserves memory for the specified constraints. More...

void	reset (unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)

void	reset (unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< Value > valArgs)

void	reset (unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< Value > valArgs)

std::unique_ptr< FlatAffineValueConstraints >	clone () const
	Clones this object. More...

LogicalResult	addAffineForOpDomain (AffineForOp forOp)
	Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR information stored in its bound maps. More...

LogicalResult	addAffineParallelOpDomain (AffineParallelOp parallelOp)
	Add constraints (lower and upper bounds) for the specified 'affine.parallel' operation's Value using IR information stored in its bound maps. More...

LogicalResult	addDomainFromSliceMaps (ArrayRef< AffineMap > lbMaps, ArrayRef< AffineMap > ubMaps, ArrayRef< Value > operands)
	Adds constraints (lower and upper bounds) for each loop in the loop nest described by the bound maps `lbMaps` and `ubMaps` of a computation slice. More...

void	addAffineIfOpDomain (AffineIfOp ifOp)
	Adds constraints imposed by the `affine.if` operation. More...

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

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

LogicalResult	addBound (BoundType type, unsigned pos, AffineMap boundMap, ValueRange operands)
	Adds a bound for the variable at the specified position with constraints being drawn from the specified bound map and operands. More...

void	addBound (BoundType type, Value val, int64_t value)
	Adds a constant bound for the variable associated with the given Value. 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 getClosedUB=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 FlatAffineConstraints. More...

std::pair< AffineMap, AffineMap >	getLowerAndUpperBound (unsigned pos, unsigned offset, unsigned num, unsigned symStartPos, ArrayRef< AffineExpr > localExprs, MLIRContext *context) 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...

void	getIneqAsAffineValueMap (unsigned pos, unsigned ineqPos, AffineValueMap &vmap, MLIRContext *context) const
	Returns the bound for the variable at `pos` from the inequality at `ineqPos` as a 1-d affine value map (affine map + operands). More...

LogicalResult	addSliceBounds (ArrayRef< Value > values, ArrayRef< AffineMap > lbMaps, ArrayRef< AffineMap > ubMaps, ArrayRef< Value > operands)
	Adds slice lower bounds represented by lower bounds in `lbMaps` and upper bounds in `ubMaps` to each variable in the constraint system which has a value in `values`. More...

bool	findVar (Value val, unsigned *pos) const
	Looks up the position of the variable with the specified Value. More...

bool	containsVar (Value val) const
	Returns true if an variable with the specified Value exists, false otherwise. More...

void	swapVar (unsigned posA, unsigned posB) override
	Swap the posA^th variable with the posB^th variable. 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	insertDimVar (unsigned pos, ValueRange vals)

unsigned	insertSymbolVar (unsigned pos, ValueRange vals)

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

unsigned	insertVar (presburger::VarKind kind, unsigned pos, ValueRange vals)

unsigned	appendDimVar (ValueRange vals)
	Append variables of the specified kind after the last variable of that kind. More...

unsigned	appendSymbolVar (ValueRange vals)

unsigned	appendDimVar (unsigned num=1)

unsigned	appendSymbolVar (unsigned num=1)

unsigned	appendLocalVar (unsigned num=1)

void	removeVarRange (presburger::VarKind kind, unsigned varStart, unsigned varLimit) override
	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	addInductionVarOrTerminalSymbol (Value val)
	Add the specified values as a dim or symbol var depending on its nature, if it already doesn't exist in the system. More...

AffineMap	computeAlignedMap (AffineMap map, ValueRange operands) const
	Align `map` with this constraint system based on `operands`. More...

LogicalResult	composeMap (const AffineValueMap *vMap)
	Composes the affine value map with this FlatAffineValueConstrains, adding the results of the map as dimensions at the front [0, vMap->getNumResults()) and with the dimensions set to the equalities specified by the value map. More...

void	projectOut (Value val)
	Projects out the variable that is associate with Value. More...

void	convertLoopIVSymbolsToDims ()
	Changes all symbol variables which are loop IVs to dim variables. More...

LogicalResult	unionBoundingBox (const FlatAffineValueConstraints &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...

void	mergeAndAlignVarsWithOther (unsigned offset, FlatAffineValueConstraints *other)
	Merge and align the variables of `this` and `other` starting at `offset`, so that both constraint systems get the union of the contained variables that is dimension-wise and symbol-wise unique; both constraint systems are updated so that they have the union of all variables, with `this`'s original variables appearing first followed by any of `other`'s variables that didn't appear in `this`. More...

bool	areVarsAlignedWithOther (const FlatAffineValueConstraints &other)
	Returns true if this constraint system and `other` are in the same space, i.e., if they are associated with the same set of variables, appearing in the same order. More...

void	clearAndCopyFrom (const IntegerRelation &other) override
	Replaces the contents of this FlatAffineValueConstraints with `other`. More...

Value	getValue (unsigned pos) const
	Returns the Value associated with the pos^th variable. More...

bool	hasValue (unsigned pos) const
	Returns true if the pos^th variable has an associated Value. More...

bool	hasValues () const
	Returns true if at least one variable has an associated Value. More...

void	getValues (unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
	Returns the Values associated with variables in range [start, end). More...

void	getAllValues (SmallVectorImpl< Value > *values) const

ArrayRef< std::optional< Value > >	getMaybeValues () const

ArrayRef< std::optional< Value > >	getMaybeValues (presburger::VarKind kind) const

void	setValue (unsigned pos, Value val)
	Sets the Value associated with the pos^th variable. More...

void	setValues (unsigned start, unsigned end, ArrayRef< Value > values)
	Sets the Values associated with the variables in the range [start, end). More...

void	mergeSymbolVars (FlatAffineValueConstraints &other)
	Merge and align symbols of `this` and `other` such that both get union of of symbols that are unique. More...

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

std::unique_ptr< IntegerPolyhedron >	clone () const

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

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

MPInt &	atEq (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...

MPInt &	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< MPInt >	getEquality (unsigned idx) const

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

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

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

void	clearConstraints ()
	Removes all equalities and inequalities. More...

void	setAndEliminate (unsigned pos, ArrayRef< MPInt > 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	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< MPInt >	computeVolume () 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< MPInt >	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. 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< MPInt >	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	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 FlatAffineValueConstraints	getHyperrectangular (ValueRange ivs, ValueRange lbs, ValueRange ubs)

static bool	classof (const IntegerRelation *cst)

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 bool	classof (const IntegerRelation *cst)

Protected Types
using	VarKind = presburger::VarKind

Protected Member Functions
bool	hasConsistentState () const override
	Returns false if the fields corresponding to various variable counts, or equality/inequality buffer sizes aren't consistent; true otherwise. More...

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

void	fourierMotzkinEliminate (unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr) override
	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	printSpace (raw_ostream &os) const override
	Prints the number of constraints, dimensions, symbols and locals in the FlatAffineConstraints. 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< MPInt >	computeConstantLowerOrUpperBound (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...

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

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
SmallVector< std::optional< Value >, 8 >	values
	Values corresponding to the (column) non-local variables of this constraint system appearing in the order the variables correspond to columns. 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...

Additional Inherited Members
Public Types inherited from mlir::presburger::IntegerRelation
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...

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

FlatAffineValueConstraints represents an extension of IntegerPolyhedron where each non-local variable can have an SSA Value attached to it.

Definition at line 43 of file AffineStructures.h.

Member Typedef Documentation

◆ VarKind

using mlir::FlatAffineValueConstraints::VarKind = presburger::VarKind

protected

Definition at line 475 of file AffineStructures.h.

Constructor & Destructor Documentation

◆ FlatAffineValueConstraints() [1/6]

mlir::FlatAffineValueConstraints::FlatAffineValueConstraints	(	unsigned	numReservedInequalities,
		unsigned	numReservedEqualities,
		unsigned	numReservedCols,
		unsigned	numDims,
		unsigned	numSymbols,
		unsigned	numLocals,
		ArrayRef< std::optional< Value >>	valArgs = `{}`
	)

inline

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

Definition at line 47 of file AffineStructures.h.

Referenced by getSliceBounds(), and reset().

◆ FlatAffineValueConstraints() [2/6]

mlir::FlatAffineValueConstraints::FlatAffineValueConstraints	(	unsigned	numDims = `0`,
		unsigned	numSymbols = `0`,
		unsigned	numLocals = `0`,
		ArrayRef< std::optional< Value >>	valArgs = `{}`
	)

inline

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

Definition at line 67 of file AffineStructures.h.

◆ FlatAffineValueConstraints() [3/6]

mlir::FlatAffineValueConstraints::FlatAffineValueConstraints	(	const IntegerPolyhedron &	fac,
		ArrayRef< std::optional< Value >>	valArgs = `{}`
	)

inline

Definition at line 76 of file AffineStructures.h.

◆ FlatAffineValueConstraints() [4/6]

mlir::FlatAffineValueConstraints::FlatAffineValueConstraints ( const AffineValueMap & avm )

explicit

Create a flat affine constraint system from an AffineValueMap or a list of these.

The constructed system will only include equalities.

◆ FlatAffineValueConstraints() [5/6]

mlir::FlatAffineValueConstraints::FlatAffineValueConstraints ( ArrayRef< const AffineValueMap * > avmRef )

explicit

◆ FlatAffineValueConstraints() [6/6]

FlatAffineValueConstraints::FlatAffineValueConstraints	(	IntegerSet	set,
		ValueRange	operands = `{}`
	)

explicit

Creates an affine constraint system from an IntegerSet.

Definition at line 153 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::addEquality(), mlir::presburger::IntegerRelation::addInequality(), mlir::presburger::IntegerRelation::append(), mlir::failed(), mlir::IntegerSet::getEqFlags(), mlir::getFlattenedAffineExprs(), mlir::presburger::IntegerRelation::getNumCols(), mlir::IntegerSet::getNumConstraints(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::IntegerSet::getNumInputs(), mlir::presburger::IntegerRelation::getNumLocalVars(), mlir::presburger::IntegerRelation::getNumVarKind(), insertVar(), and values.

Member Function Documentation

◆ addAffineForOpDomain()

LogicalResult FlatAffineValueConstraints::addAffineForOpDomain ( AffineForOp forOp )

Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR information stored in its bound maps.

The right variable is first looked up using forOp's Value. Asserts if the Value corresponding to the 'affine.for' operation isn't found in the constraint system. Returns failure for the yet unimplemented/unsupported cases. Any new variables that are found in the bound operands of the 'affine.for' operation are added as trailing variables (either dimensional or symbolic depending on whether the operand is a valid symbol).

Definition at line 597 of file AffineStructures.cpp.

References addBound(), mlir::presburger::IntegerRelation::addEquality(), mlir::presburger::IntegerRelation::addLocalFloorDiv(), mlir::failed(), mlir::failure(), findVar(), mlir::presburger::IntegerRelation::getNumCols(), and mlir::success().

Referenced by addDomainFromSliceMaps(), addInductionVarOrTerminalSymbol(), addMissingLoopIVBounds(), addSliceBounds(), mlir::ComputationSliceState::getAsConstraints(), mlir::getIndexSet(), mlir::ComputationSliceState::getSourceAsConstraints(), and mlir::ComputationSliceState::isMaximal().

◆ addAffineIfOpDomain()

void FlatAffineValueConstraints::addAffineIfOpDomain ( AffineIfOp ifOp )

Adds constraints imposed by the affine.if operation.

These constraints are collected from the IntegerSet attached to the given affine.if instance argument (ifOp). It is asserted that: 1) The IntegerSet of the given affine.if instance should not contain semi-affine expressions, 2) The columns of the constraint system created from ifOp should match the columns in the current one regarding numbers and values.

Definition at line 725 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::append(), mlir::canonicalizeSetAndOperands(), and mergeAndAlignVarsWithOther().

Referenced by mlir::getIndexSet().

◆ addAffineParallelOpDomain()

LogicalResult FlatAffineValueConstraints::addAffineParallelOpDomain ( AffineParallelOp parallelOp )

Add constraints (lower and upper bounds) for the specified 'affine.parallel' operation's Value using IR information stored in its bound maps.

Returns failure for the yet unimplemented/unsupported cases. Asserts if the Value corresponding to the 'affine.parallel' operation isn't found in the constraint system.

Definition at line 648 of file AffineStructures.cpp.

References addBound(), mlir::failed(), mlir::failure(), findVar(), mlir::AffineMap::getSingleConstantResult(), mlir::AffineMap::isConstant(), and mlir::success().

Referenced by mlir::getIndexSet().

◆ addBound() [1/4]

LogicalResult FlatAffineValueConstraints::addBound	(	BoundType	type,
		unsigned	pos,
		AffineMap	boundMap
	)

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. Note: The dimensions/symbols of this FlatAffineConstraints 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 1255 of file AffineStructures.cpp.

References addBound().

◆ addBound() [2/4]

LogicalResult FlatAffineValueConstraints::addBound	(	BoundType	type,
		unsigned	pos,
		AffineMap	boundMap,
		bool	isClosedBound
	)

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.

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

Definition at line 1203 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::addEquality(), mlir::presburger::IntegerRelation::addInequality(), mlir::failed(), mlir::failure(), flattenAlignedMapAndMergeLocals(), mlir::presburger::IntegerRelation::getNumCols(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::AffineMap::getNumDims(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::AffineMap::getNumInputs(), mlir::AffineMap::getNumResults(), mlir::AffineMap::getNumSymbols(), mlir::presburger::IntegerRelation::getNumSymbolVars(), and mlir::success().

Referenced by addAffineForOpDomain(), addAffineParallelOpDomain(), addBound(), addDomainFromSliceMaps(), addInductionVarOrTerminalSymbol(), addLoopRangeConstraints(), addSliceBounds(), alignAndAddBound(), mlir::ComputationSliceState::getAsConstraints(), mlir::MemRefRegion::getConstantBoundingSizeAndShape(), getHyperrectangular(), mlir::linalg::getUpperBoundForIndex(), mlir::normalizeMemRefType(), mlir::scf::rewritePeeledMinMaxOp(), and mlir::simplifyConstrainedMinMaxOp().

◆ addBound() [3/4]

LogicalResult FlatAffineValueConstraints::addBound	(	BoundType	type,
		unsigned	pos,
		AffineMap	boundMap,
		ValueRange	operands
	)

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

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.

Definition at line 1293 of file AffineStructures.cpp.

References addBound(), addInductionVarOrTerminalSymbol(), mlir::canonicalizeMapAndOperands(), computeAlignedMap(), mlir::fullyComposeAffineMapAndOperands(), and mlir::simplifyAffineMap().

◆ addBound() [4/4]

void FlatAffineValueConstraints::addBound	(	BoundType	type,
		Value	val,
		int64_t	value
	)

Adds a constant bound for the variable associated with the given Value.

Definition at line 1394 of file AffineStructures.cpp.

References addBound(), and findVar().

◆ addDomainFromSliceMaps()

LogicalResult FlatAffineValueConstraints::addDomainFromSliceMaps	(	ArrayRef< AffineMap >	lbMaps,
		ArrayRef< AffineMap >	ubMaps,
		ArrayRef< Value >	operands
	)

Adds constraints (lower and upper bounds) for each loop in the loop nest described by the bound maps lbMaps and ubMaps of a computation slice.

Every pair (lbMaps[i], ubMaps[i]) describes the bounds of a loop in the nest, sorted outer-to-inner. operands contains the bound operands for a single bound map. All the bound maps will use the same bound operands. Note that some loops described by a computation slice might not exist yet in the IR so the Value attached to those dimension variables might be empty. For that reason, this method doesn't perform Value look-ups to retrieve the dimension variable positions. Instead, it assumes the position of the dim variables in the constraint system is the same as the position of the loop in the loop nest.

Definition at line 676 of file AffineStructures.cpp.

References addAffineForOpDomain(), addBound(), mlir::AffineExpr::dyn_cast(), mlir::failed(), mlir::failure(), mlir::getForInductionVarOwner(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::AffineMap::getNumInputs(), mlir::AffineMap::getNumResults(), mlir::AffineDimExpr::getPosition(), mlir::AffineMap::getResult(), mlir::AffineExpr::isa(), and mlir::success().

Referenced by mlir::ComputationSliceState::isMaximal().

◆ addInductionVarOrTerminalSymbol()

void FlatAffineValueConstraints::addInductionVarOrTerminalSymbol ( Value val )

Add the specified values as a dim or symbol var depending on its nature, if it already doesn't exist in the system.

val has to be either a terminal symbol or a loop IV, i.e., it cannot be the result affine.apply of any symbols or loop IVs. The variable is added to the end of the existing dims or symbols. Additional information on the variable is extracted from the IR and added to the constraint system.

Definition at line 574 of file AffineStructures.cpp.

References addAffineForOpDomain(), addBound(), appendDimVar(), appendSymbolVar(), containsVar(), mlir::failed(), mlir::Value::getDefiningOp(), mlir::getForInductionVarOwner(), mlir::isAffineForInductionVar(), and mlir::isTopLevelValue().

Referenced by addBound().

◆ addSliceBounds()

LogicalResult FlatAffineValueConstraints::addSliceBounds	(	ArrayRef< Value >	values,
		ArrayRef< AffineMap >	lbMaps,
		ArrayRef< AffineMap >	ubMaps,
		ArrayRef< Value >	operands
	)

Adds slice lower bounds represented by lower bounds in lbMaps and upper bounds in ubMaps to each variable in the constraint system which has a value in values.

Note that both lower/upper bounds share the same operand list operands. This function assumes values.size == lbMaps.size == ubMaps.size. Note that both lower/upper bounds use operands from operands.

Definition at line 1317 of file AffineStructures.cpp.

References addAffineForOpDomain(), addBound(), mlir::failed(), mlir::failure(), findVar(), mlir::getForInductionVarOwner(), mlir::AffineMap::getNumInputs(), mlir::AffineMap::getNumResults(), mlir::AffineMap::getResult(), mlir::success(), and values.

Referenced by mlir::ComputationSliceState::getAsConstraints().

◆ appendDimVar() [1/2]

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

inline

Definition at line 317 of file AffineStructures.h.

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

◆ appendDimVar() [2/2]

unsigned FlatAffineValueConstraints::appendDimVar ( ValueRange vals )

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 278 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::getNumDimVars(), and insertVar().

Referenced by addInductionVarOrTerminalSymbol(), addLoopRangeConstraints(), getHyperrectangular(), mlir::getRelationFromMap(), mlir::linalg::getUpperBoundForIndex(), mergeAndAlignVars(), mlir::scf::rewritePeeledMinMaxOp(), and mlir::simplifyConstrainedMinMaxOp().

◆ appendLocalVar()

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

inline

Definition at line 323 of file AffineStructures.h.

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

Referenced by flattenAlignedMapAndMergeLocals().

◆ appendSymbolVar() [1/2]

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

inline

Definition at line 320 of file AffineStructures.h.

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

◆ appendSymbolVar() [2/2]

unsigned FlatAffineValueConstraints::appendSymbolVar ( ValueRange vals )

Definition at line 283 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::getNumSymbolVars(), and insertVar().

Referenced by addInductionVarOrTerminalSymbol(), addLoopRangeConstraints(), alignAndAddBound(), and mlir::scf::rewritePeeledMinMaxOp().

◆ areVarsAlignedWithOther()

bool FlatAffineValueConstraints::areVarsAlignedWithOther ( const FlatAffineValueConstraints & other )

Returns true if this constraint system and other are in the same space, i.e., if they are associated with the same set of variables, appearing in the same order.

Calls areVarsAligned to check if two constraint systems have the same set of variables in the same order.

Returns false otherwise.

Definition at line 344 of file AffineStructures.cpp.

References areVarsAligned().

Referenced by mlir::computeSliceUnion().

◆ classof()

static bool mlir::FlatAffineValueConstraints::classof ( const IntegerRelation * cst )

inlinestatic

Definition at line 111 of file AffineStructures.h.

References mlir::presburger::IntegerRelation::FlatAffineValueConstraints.

◆ clearAndCopyFrom()

void FlatAffineValueConstraints::clearAndCopyFrom ( const IntegerRelation & other )

override

Replaces the contents of this FlatAffineValueConstraints with other.

Definition at line 1419 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), and values.

Referenced by getFlattenedAffineExprs().

◆ clone()

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

Clones this object.

Definition at line 148 of file AffineStructures.cpp.

◆ composeMap()

LogicalResult FlatAffineValueConstraints::composeMap ( const AffineValueMap * vMap )

Composes the affine value map with this FlatAffineValueConstrains, adding the results of the map as dimensions at the front [0, vMap->getNumResults()) and with the dimensions set to the equalities specified by the value map.

Returns failure if the composition fails (when vMap is a semi-affine map). The vMap's operand Value's are used to look up the right positions in the FlatAffineConstraints with which to associate. Every operand of vMap should have a matching dim/symbol column in this constraint system (with the same associated Value).

Definition at line 455 of file AffineStructures.cpp.

References composeMatchingMap(), computeAlignedMap(), mlir::AffineValueMap::getAffineMap(), and mlir::AffineValueMap::getOperands().

◆ composeMatchingMap()

LogicalResult FlatAffineValueConstraints::composeMatchingMap ( AffineMap other )

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

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 463 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::addEquality(), mlir::failed(), mlir::failure(), flattenAlignedMapAndMergeLocals(), mlir::presburger::IntegerRelation::getNumCols(), mlir::AffineMap::getNumDims(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::AffineMap::getNumInputs(), mlir::AffineMap::getNumResults(), mlir::AffineMap::getNumSymbols(), mlir::presburger::IntegerRelation::getNumSymbolVars(), insertDimVar(), and mlir::success().

Referenced by composeMap(), and mlir::normalizeMemRefType().

◆ computeAlignedMap()

AffineMap FlatAffineValueConstraints::computeAlignedMap	(	AffineMap	map,
		ValueRange	operands
	)		const

Align map with this constraint system based on operands.

Each operand must already have a corresponding dim/symbol in this constraint system.

Definition at line 1261 of file AffineStructures.cpp.

References mlir::alignAffineMapWithValues(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::AffineMap::getNumInputs(), mlir::presburger::IntegerRelation::getNumSymbolVars(), mlir::presburger::IntegerRelation::getVarKindEnd(), mlir::presburger::IntegerRelation::getVarKindOffset(), and values.

Referenced by addBound(), composeMap(), and mlir::linalg::getUpperBoundForIndex().

◆ containsVar()

bool FlatAffineValueConstraints::containsVar ( Value val ) const

Returns true if an variable with the specified Value exists, false otherwise.

Definition at line 1372 of file AffineStructures.cpp.

References values.

Referenced by addInductionVarOrTerminalSymbol(), mlir::ComputationSliceState::getAsConstraints(), and mlir::linalg::getUpperBoundForIndex().

◆ convertLoopIVSymbolsToDims()

void FlatAffineValueConstraints::convertLoopIVSymbolsToDims ( )

Changes all symbol variables which are loop IVs to dim variables.

Definition at line 561 of file AffineStructures.cpp.

References mlir::getForInductionVarOwner(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::presburger::IntegerRelation::getNumDimVars(), getValue(), hasValue(), and turnSymbolIntoDim().

Referenced by mlir::computeSliceUnion().

◆ findVar()

bool FlatAffineValueConstraints::findVar	(	Value	val,
		unsigned *	pos
	)		const

Looks up the position of the variable with the specified Value.

Returns true if found (false otherwise). pos is set to the (column) position of the variable.

Definition at line 1360 of file AffineStructures.cpp.

References values.

Referenced by addAffineForOpDomain(), addAffineParallelOpDomain(), addBound(), addSliceBounds(), mlir::MemRefAccess::getAccessRelation(), mlir::linalg::getUpperBoundForIndex(), mergeAndAlignVars(), mergeSymbolVars(), projectOut(), and turnSymbolIntoDim().

◆ flattenAlignedMapAndMergeLocals()

LogicalResult FlatAffineValueConstraints::flattenAlignedMapAndMergeLocals	(	AffineMap	map,
		std::vector< SmallVector< int64_t, 8 >> *	flattenedExprs
	)

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 1179 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::append(), appendLocalVar(), mlir::failed(), mlir::failure(), mlir::getFlattenedAffineExprs(), mlir::presburger::IntegerRelation::getNumLocalVars(), insertLocalVar(), and mlir::success().

Referenced by addBound(), and composeMatchingMap().

◆ fourierMotzkinEliminate()

void FlatAffineValueConstraints::fourierMotzkinEliminate	(	unsigned	pos,
		bool	darkShadow = `false`,
		bool *	isResultIntegerExact = `nullptr`
	)

overrideprotectedvirtual

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.

Reimplemented from mlir::presburger::IntegerRelation.

Definition at line 1432 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::presburger::IntegerRelation::getVarKindAt(), and values.

Referenced by projectOut().

◆ getAllValues()

void mlir::FlatAffineValueConstraints::getAllValues ( SmallVectorImpl< Value > * values ) const

inline

Definition at line 436 of file AffineStructures.h.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), getValues(), and values.

Referenced by mlir::linalg::getUpperBoundForIndex().

◆ getAsIntegerSet()

IntegerSet FlatAffineValueConstraints::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 1551 of file AffineStructures.cpp.

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

◆ getHyperrectangular()

FlatAffineValueConstraints FlatAffineValueConstraints::getHyperrectangular	(	ValueRange	ivs,
		ValueRange	lbs,
		ValueRange	ubs
	)

static

Definition at line 204 of file AffineStructures.cpp.

References addBound(), appendDimVar(), mlir::failed(), mlir::AffineMap::get(), and mlir::getAffineDimExpr().

◆ getIneqAsAffineValueMap()

void FlatAffineValueConstraints::getIneqAsAffineValueMap	(	unsigned	pos,
		unsigned	ineqPos,
		AffineValueMap &	vmap,
		MLIRContext *	context
	)		const

Returns the bound for the variable at pos from the inequality at ineqPos as a 1-d affine value map (affine map + operands).

The returned affine value map can either be a lower bound or an upper bound depending on the sign of atIneq(ineqPos, pos). Asserts if the row at ineqPos does not involve the posth variable.

Definition at line 1505 of file AffineStructures.cpp.

Referenced by createFullTiles().

◆ getKind()

Kind mlir::FlatAffineValueConstraints::getKind ( ) const

inlineoverridevirtual

Return the kind of this FlatAffineConstraints.

Reimplemented from mlir::presburger::IntegerPolyhedron.

Definition at line 109 of file AffineStructures.h.

References mlir::presburger::IntegerRelation::FlatAffineValueConstraints.

◆ getLowerAndUpperBound()

std::pair< AffineMap, AffineMap > FlatAffineValueConstraints::getLowerAndUpperBound	(	unsigned	pos,
		unsigned	offset,
		unsigned	num,
		unsigned	symStartPos,
		ArrayRef< AffineExpr >	localExprs,
		MLIRContext *	context
	)		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. The upper bound is exclusive. localExprs holds pre-computed AffineExpr's for all local variables in the system.

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

Definition at line 920 of file AffineStructures.cpp.

References mlir::presburger::abs(), mlir::floorDiv(), mlir::AffineMap::get(), mlir::getAffineExprFromFlatForm(), mlir::presburger::IntegerRelation::getEquality64(), mlir::presburger::IntegerRelation::getInequality64(), mlir::presburger::IntegerRelation::getLowerAndUpperBoundIndices(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::presburger::IntegerRelation::getNumDimVars(), and mlir::presburger::IntegerRelation::getNumLocalVars().

◆ getMaybeValues() [1/2]

ArrayRef<std::optional<Value> > mlir::FlatAffineValueConstraints::getMaybeValues ( ) const

inline

Definition at line 440 of file AffineStructures.h.

References values.

Referenced by alignAndAddBound(), areVarsAligned(), areVarsUnique(), mlir::FlatAffineRelation::compose(), mergeAndAlignVars(), mlir::simplifyConstrainedMinMaxOp(), and unionBoundingBox().

◆ getMaybeValues() [2/2]

ArrayRef<std::optional<Value> > mlir::FlatAffineValueConstraints::getMaybeValues ( presburger::VarKind kind ) const

inline

Definition at line 445 of file AffineStructures.h.

References mlir::presburger::IntegerRelation::getNumVarKind(), mlir::presburger::IntegerRelation::getVarKindOffset(), and values.

◆ getSliceBounds()

void FlatAffineValueConstraints::getSliceBounds	(	unsigned	offset,
		unsigned	num,
		MLIRContext *	context,
		SmallVectorImpl< AffineMap > *	lbMaps,
		SmallVectorImpl< AffineMap > *	ubMaps,
		bool	getClosedUB = `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. This can be changed by getClosedUB.

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

Definition at line 1008 of file AffineStructures.cpp.

Referenced by mlir::computeSliceUnion(), mlir::getComputationSliceState(), mlir::linalg::getUpperBoundForIndex(), and mlir::simplifyConstrainedMinMaxOp().

◆ getValue()

Value mlir::FlatAffineValueConstraints::getValue ( unsigned pos ) const

inline

Returns the Value associated with the pos^th variable.

Asserts if no Value variable was associated.

Definition at line 410 of file AffineStructures.h.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), hasValue(), and values.

Referenced by addMissingLoopIVBounds(), mlir::computeSliceUnion(), convertLoopIVSymbolsToDims(), mlir::MemRefAccess::getAccessRelation(), mlir::getComputationSliceState(), getNumCommonLoops(), getValues(), mergeAndAlignVars(), and mergeSymbolVars().

◆ getValues()

void mlir::FlatAffineValueConstraints::getValues	(	unsigned	start,
		unsigned	end,
		SmallVectorImpl< Value > *	values
	)		const

inline

Returns the Values associated with variables in range [start, end).

Asserts if no Value was associated with one of these variables.

Definition at line 427 of file AffineStructures.h.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), getValue(), and values.

Referenced by mlir::computeSliceUnion(), createPrivateMemRef(), createSeparationCondition(), generateCopy(), getAllValues(), mlir::getComputationSliceState(), getIneqAsAffineValueMap(), mergeAndAlignVars(), and mergeSymbolVars().

◆ hasConsistentState()

bool FlatAffineValueConstraints::hasConsistentState ( ) const

overrideprotectedvirtual

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 from mlir::presburger::IntegerRelation.

Definition at line 742 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), and values.

◆ hasValue()

bool mlir::FlatAffineValueConstraints::hasValue ( unsigned pos ) const

inline

Returns true if the pos^th variable has an associated Value.

Definition at line 417 of file AffineStructures.h.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), and values.

Referenced by convertLoopIVSymbolsToDims(), getValue(), and printSpace().

◆ hasValues()

bool FlatAffineValueConstraints::hasValues ( ) const

Returns true if at least one variable has an associated Value.

Definition at line 327 of file AffineStructures.cpp.

References values.

◆ insertDimVar() [1/2]

unsigned mlir::FlatAffineValueConstraints::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 293 of file AffineStructures.h.

References insertVar().

Referenced by mlir::FlatAffineRelation::appendDomainVar(), mlir::FlatAffineRelation::appendRangeVar(), composeMatchingMap(), computeDirectionVector(), mlir::FlatAffineRelation::insertDomainVar(), mlir::FlatAffineRelation::insertRangeVar(), and mergeAndAlignVars().

◆ insertDimVar() [2/2]

unsigned FlatAffineValueConstraints::insertDimVar	(	unsigned	pos,
		ValueRange	vals
	)

Definition at line 288 of file AffineStructures.cpp.

References insertVar().

◆ insertLocalVar()

unsigned mlir::FlatAffineValueConstraints::insertLocalVar	(	unsigned	pos,
		unsigned	num = `1`
	)

inline

Definition at line 299 of file AffineStructures.h.

References insertVar().

Referenced by flattenAlignedMapAndMergeLocals().

◆ insertSymbolVar() [1/2]

unsigned mlir::FlatAffineValueConstraints::insertSymbolVar	(	unsigned	pos,
		unsigned	num = `1`
	)

inline

Definition at line 296 of file AffineStructures.h.

References insertVar().

Referenced by mergeSymbolVars().

◆ insertSymbolVar() [2/2]

unsigned FlatAffineValueConstraints::insertSymbolVar	(	unsigned	pos,
		ValueRange	vals
	)

Definition at line 293 of file AffineStructures.cpp.

References insertVar().

◆ insertVar() [1/2]

unsigned FlatAffineValueConstraints::insertVar	(	presburger::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::IntegerPolyhedron.

Definition at line 298 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), and values.

Referenced by appendDimVar(), appendSymbolVar(), FlatAffineValueConstraints(), insertDimVar(), insertLocalVar(), and insertSymbolVar().

◆ insertVar() [2/2]

unsigned FlatAffineValueConstraints::insertVar	(	presburger::VarKind	kind,
		unsigned	pos,
		ValueRange	vals
	)

Definition at line 310 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), and values.

◆ mergeAndAlignVarsWithOther()

void FlatAffineValueConstraints::mergeAndAlignVarsWithOther	(	unsigned	offset,
		FlatAffineValueConstraints *	other
	)

Merge and align the variables of this and other starting at offset, so that both constraint systems get the union of the contained variables that is dimension-wise and symbol-wise unique; both constraint systems are updated so that they have the union of all variables, with this's original variables appearing first followed by any of other's variables that didn't appear in this.

Local variables in other that have the same division representation as local variables in this are merged into one.

Definition at line 449 of file AffineStructures.cpp.

References mergeAndAlignVars().

Referenced by addAffineIfOpDomain(), and mlir::computeSliceUnion().

◆ mergeSymbolVars()

void FlatAffineValueConstraints::mergeSymbolVars ( FlatAffineValueConstraints & other )

Merge and align symbols of this and other such that both get union of of symbols that are unique.

Symbols in this and other should be unique. Symbols with Value as None are considered to be inequal to all other symbols.

Definition at line 525 of file AffineStructures.cpp.

References areVarsUnique(), findVar(), mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::presburger::IntegerRelation::getNumSymbolVars(), getValue(), getValues(), insertSymbolVar(), and swapVar().

Referenced by mlir::FlatAffineRelation::compose(), mlir::MemRefAccess::getAccessRelation(), and mergeAndAlignVars().

◆ printSpace()

void FlatAffineValueConstraints::printSpace ( raw_ostream & os ) const

overrideprotectedvirtual

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

Also, prints for each variable whether there is an SSA Value attached to it.

Reimplemented from mlir::presburger::IntegerRelation.

Definition at line 1403 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), mlir::presburger::IntegerRelation::getVarKindEnd(), mlir::presburger::IntegerRelation::getVarKindOffset(), hasValue(), and impl::printSpace().

◆ projectOut()

void FlatAffineValueConstraints::projectOut ( Value val )

Projects out the variable that is associate with Value.

Definition at line 1444 of file AffineStructures.cpp.

References findVar(), and fourierMotzkinEliminate().

Referenced by computeDirectionVector(), mlir::getComputationSliceState(), mlir::ComputationSliceState::isSliceValid(), and mlir::normalizeMemRefType().

◆ removeVarRange()

void FlatAffineValueConstraints::removeVarRange	(	presburger::VarKind	kind,
		unsigned	varStart,
		unsigned	varLimit
	)

overridevirtual

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

Reimplemented from mlir::presburger::IntegerRelation.

Reimplemented in mlir::FlatAffineRelation.

Definition at line 747 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::getVarKindOffset(), and values.

Referenced by mlir::FlatAffineRelation::removeVarRange().

◆ reset() [1/4]

void FlatAffineValueConstraints::reset	(	unsigned	numDims,
		unsigned	numSymbols,
		unsigned	numLocals,
		ArrayRef< Value >	valArgs
	)

Definition at line 270 of file AffineStructures.cpp.

References reset().

◆ reset() [2/4]

void FlatAffineValueConstraints::reset	(	unsigned	numDims = `0`,
		unsigned	numSymbols = `0`,
		unsigned	numLocals = `0`
	)

Definition at line 247 of file AffineStructures.cpp.

References reset().

◆ reset() [3/4]

void FlatAffineValueConstraints::reset	(	unsigned	numReservedInequalities,
		unsigned	numReservedEqualities,
		unsigned	numReservedCols,
		unsigned	numDims,
		unsigned	numSymbols,
		unsigned	numLocals,
		ArrayRef< Value >	valArgs
	)

Definition at line 255 of file AffineStructures.cpp.

References FlatAffineValueConstraints().

◆ reset() [4/4]

void FlatAffineValueConstraints::reset	(	unsigned	numReservedInequalities,
		unsigned	numReservedEqualities,
		unsigned	numReservedCols,
		unsigned	numDims,
		unsigned	numSymbols,
		unsigned	numLocals = `0`
	)

Clears any existing data and reserves memory for the specified constraints.

Definition at line 234 of file AffineStructures.cpp.

References FlatAffineValueConstraints().

Referenced by checkTilingLegalityImpl(), mlir::ComputationSliceState::getAsConstraints(), mlir::getFlattenedAffineExprs(), getFlattenedAffineExprs(), mlir::getIndexSet(), mlir::ComputationSliceState::getSourceAsConstraints(), mlir::ComputationSliceState::isMaximal(), and reset().

◆ setValue()

void mlir::FlatAffineValueConstraints::setValue	(	unsigned	pos,
		Value	val
	)

inline

Sets the Value associated with the pos^th variable.

Definition at line 452 of file AffineStructures.h.

References mlir::presburger::IntegerRelation::getNumDimAndSymbolVars(), and values.

Referenced by mlir::FlatAffineRelation::compose(), mlir::MemRefAccess::getAccessRelation(), mlir::getRelationFromMap(), and setValues().

◆ setValues()

void mlir::FlatAffineValueConstraints::setValues	(	unsigned	start,
		unsigned	end,
		ArrayRef< Value >	values
	)

inline

Sets the Values associated with the variables in the range [start, end).

The range must contain only dim and symbol variables.

Definition at line 459 of file AffineStructures.h.

References mlir::presburger::IntegerRelation::getNumVars(), setValue(), and values.

◆ swapVar()

void FlatAffineValueConstraints::swapVar	(	unsigned	posA,
		unsigned	posB
	)

overridevirtual

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

Reimplemented from mlir::presburger::IntegerRelation.

Definition at line 1378 of file AffineStructures.cpp.

References mlir::presburger::IntegerRelation::getVarKindAt(), and values.

Referenced by mlir::MemRefAccess::getAccessRelation(), mlir::FlatAffineRelation::inverse(), mergeAndAlignVars(), mergeSymbolVars(), and turnSymbolIntoDim().

◆ unionBoundingBox()

LogicalResult FlatAffineValueConstraints::unionBoundingBox ( const FlatAffineValueConstraints & 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 1452 of file AffineStructures.cpp.

References areVarsAligned(), getMaybeValues(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::presburger::IntegerRelation::getNumLocalVars(), and mergeAndAlignVars().

Referenced by mlir::computeSliceUnion().

Member Data Documentation

◆ values

SmallVector<std::optional<Value>, 8> mlir::FlatAffineValueConstraints::values

protected

Values corresponding to the (column) non-local variables of this constraint system appearing in the order the variables correspond to columns.

Variables that aren't associated with any Value are set to None.

Definition at line 514 of file AffineStructures.h.

Referenced by addSliceBounds(), clearAndCopyFrom(), mlir::FlatAffineRelation::compose(), computeAlignedMap(), containsVar(), findVar(), FlatAffineValueConstraints(), fourierMotzkinEliminate(), getAllValues(), getMaybeValues(), getValue(), getValues(), hasConsistentState(), hasValue(), hasValues(), insertVar(), removeVarRange(), setValue(), setValues(), and swapVar().

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

include/mlir/Dialect/Affine/Analysis/AffineStructures.h
lib/Dialect/Affine/Analysis/AffineStructures.cpp

Public Member Functions

Static Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ VarKind

Constructor & Destructor Documentation

◆ FlatAffineValueConstraints() [1/6]

◆ FlatAffineValueConstraints() [2/6]

◆ FlatAffineValueConstraints() [3/6]

◆ FlatAffineValueConstraints() [4/6]

◆ FlatAffineValueConstraints() [5/6]

◆ FlatAffineValueConstraints() [6/6]

Member Function Documentation

◆ addAffineForOpDomain()

◆ addAffineIfOpDomain()

◆ addAffineParallelOpDomain()

◆ addBound() [1/4]

◆ addBound() [2/4]

◆ addBound() [3/4]

◆ addBound() [4/4]

◆ addDomainFromSliceMaps()

◆ addInductionVarOrTerminalSymbol()

◆ addSliceBounds()

◆ appendDimVar() [1/2]

◆ appendDimVar() [2/2]

◆ appendLocalVar()

◆ appendSymbolVar() [1/2]

◆ appendSymbolVar() [2/2]

◆ areVarsAlignedWithOther()

◆ classof()

◆ clearAndCopyFrom()

◆ clone()

◆ composeMap()

◆ composeMatchingMap()

◆ computeAlignedMap()

◆ containsVar()

◆ convertLoopIVSymbolsToDims()

◆ findVar()

◆ flattenAlignedMapAndMergeLocals()

◆ fourierMotzkinEliminate()

◆ getAllValues()

◆ getAsIntegerSet()

◆ getHyperrectangular()

◆ getIneqAsAffineValueMap()

◆ getKind()

◆ getLowerAndUpperBound()

◆ getMaybeValues() [1/2]

◆ getMaybeValues() [2/2]

◆ getSliceBounds()

◆ getValue()

◆ getValues()

◆ hasConsistentState()

◆ hasValue()

◆ hasValues()

◆ insertDimVar() [1/2]

◆ insertDimVar() [2/2]

◆ insertLocalVar()

◆ insertSymbolVar() [1/2]

◆ insertSymbolVar() [2/2]

◆ insertVar() [1/2]

◆ insertVar() [2/2]

◆ mergeAndAlignVarsWithOther()

◆ mergeSymbolVars()

◆ printSpace()

◆ projectOut()

◆ removeVarRange()

◆ reset() [1/4]

◆ reset() [2/4]

◆ reset() [3/4]

◆ reset() [4/4]

◆ setValue()

◆ setValues()

◆ swapVar()

◆ unionBoundingBox()

Member Data Documentation

◆ values