MLIR  20.0.0git
Public Member Functions | Static Public Member Functions | Protected Attributes | List of all members
mlir::affine::FlatAffineRelation Class Reference

A FlatAffineRelation represents a set of ordered pairs (domain -> range) where "domain" and "range" are tuples of variables. More...

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

+ Inheritance diagram for mlir::affine::FlatAffineRelation:

Public Member Functions

 FlatAffineRelation (unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDomainDims, unsigned numRangeDims, unsigned numSymbols, unsigned numLocals, ArrayRef< std::optional< Value >> valArgs={})
 
 FlatAffineRelation (unsigned numDomainDims=0, unsigned numRangeDims=0, unsigned numSymbols=0, unsigned numLocals=0)
 
 FlatAffineRelation (unsigned numDomainDims, unsigned numRangeDims, FlatAffineValueConstraints &fac)
 
 FlatAffineRelation (unsigned numDomainDims, unsigned numRangeDims, IntegerPolyhedron &fac)
 
Kind getKind () const override
 Return the kind of this object. More...
 
FlatAffineValueConstraints getDomainSet () const
 Returns a set corresponding to the domain/range of the affine relation. More...
 
FlatAffineValueConstraints getRangeSet () const
 
unsigned getNumDomainDims () const
 Returns the number of variables corresponding to domain/range of relation. More...
 
unsigned getNumRangeDims () const
 
void compose (const FlatAffineRelation &other)
 Given affine relation other: (domainOther -> rangeOther), this operation takes the composition of other on this: (domainThis -> rangeThis). More...
 
void inverse ()
 Swap domain and range of the relation. More...
 
void insertDomainVar (unsigned pos, unsigned num=1)
 Insert num variables of the specified kind after the pos variable of that kind. More...
 
void insertRangeVar (unsigned pos, unsigned num=1)
 
void appendDomainVar (unsigned num=1)
 Append num variables of the specified kind after the last variable of that kind. More...
 
void appendRangeVar (unsigned num=1)
 
void removeVarRange (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...
 
- Public Member Functions inherited from mlir::affine::FlatAffineValueConstraints
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 (presburger::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 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...
 
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...
 
void convertLoopIVSymbolsToDims ()
 Changes all symbol variables which are loop IVs to dim variables. 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 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...
 
 FlatLinearValueConstraints (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...
 
 FlatLinearValueConstraints (unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< Value > valArgs)
 Constructs a constraint system reserving memory for the specified number of constraints and variables. More...
 
 FlatLinearValueConstraints (unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< std::optional< Value >> valArgs)
 Constructs a constraint system with the specified number of dimensions and symbols. More...
 
 FlatLinearValueConstraints (unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0, ArrayRef< Value > valArgs={})
 Constructs a constraint system with the specified number of dimensions and symbols. More...
 
 FlatLinearValueConstraints (const IntegerPolyhedron &fac, ArrayRef< std::optional< Value >> valArgs={})
 
 FlatLinearValueConstraints (IntegerSet set, ValueRange operands={})
 Creates an affine constraint system from an IntegerSet. More...
 
void addBound (presburger::BoundType type, Value val, int64_t value)
 Adds a constant bound for the variable associated with the given Value. 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...
 
- Public Member Functions inherited from mlir::FlatLinearValueConstraints
 FlatLinearValueConstraints (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...
 
 FlatLinearValueConstraints (unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< Value > valArgs)
 Constructs a constraint system reserving memory for the specified number of constraints and variables. More...
 
 FlatLinearValueConstraints (unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< std::optional< Value >> valArgs)
 Constructs a constraint system with the specified number of dimensions and symbols. More...
 
 FlatLinearValueConstraints (unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0, ArrayRef< Value > valArgs={})
 Constructs a constraint system with the specified number of dimensions and symbols. More...
 
 FlatLinearValueConstraints (const IntegerPolyhedron &fac, ArrayRef< std::optional< Value >> valArgs={})
 
 FlatLinearValueConstraints (IntegerSet set, ValueRange operands={})
 Creates an affine constraint system from an IntegerSet. More...
 
void addBound (presburger::BoundType type, Value val, int64_t value)
 Adds a constant bound for the variable associated with the given Value. More...
 
Value getValue (unsigned pos) const
 Returns the Value associated with the pos^th variable. More...
 
void getValues (unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
 Returns the Values associated with variables in range [start, end). More...
 
SmallVector< std::optional< Value > > getMaybeValues () const
 
SmallVector< std::optional< Value > > getMaybeValues (presburger::VarKind kind) const
 
bool hasValue (unsigned pos) const
 Returns true if the pos^th variable has an associated Value. More...
 
unsigned appendDimVar (ValueRange vals)
 
unsigned appendSymbolVar (ValueRange vals)
 
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)
 
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...
 
bool findVar (Value val, unsigned *pos, unsigned offset=0) const
 Looks up the position of the variable with the specified Value starting with variables at offset offset. More...
 
bool containsVar (Value val) const
 Returns true if a variable with the specified Value exists, false otherwise. More...
 
void projectOut (Value val)
 Projects out the variable that is associate with Value. More...
 
void printSpace (raw_ostream &os) const override
 Prints the number of constraints, dimensions, symbols and locals in the FlatAffineValueConstraints. More...
 
AffineMap computeAlignedMap (AffineMap map, ValueRange operands) const
 Align map with this constraint system based on operands. More...
 
void mergeAndAlignVarsWithOther (unsigned offset, FlatLinearValueConstraints *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...
 
void mergeSymbolVars (FlatLinearValueConstraints &other)
 Merge and align symbols of this and other such that both get union of of symbols that are unique. More...
 
bool areVarsAlignedWithOther (const FlatLinearConstraints &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...
 
LogicalResult unionBoundingBox (const FlatLinearValueConstraints &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...
 
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...
 
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 insertDimVar (unsigned pos, unsigned num=1)
 Insert variables of the specified kind at position pos. More...
 
unsigned insertSymbolVar (unsigned pos, unsigned num=1)
 
- Public Member Functions inherited from mlir::FlatLinearConstraints
 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)
 
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, AffineMapgetLowerAndUpperBound (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). 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...
 
std::unique_ptr< IntegerPolyhedronclone () const
 
unsigned insertVar (VarKind kind, unsigned pos, unsigned num=1) override
 Insert num variables of the specified kind at position pos. More...
 
IntegerPolyhedron intersect (const IntegerPolyhedron &other) const
 Return the intersection of the two relations. More...
 
PresburgerSet subtract (const PresburgerSet &other) const
 Return the set difference of this set and the given set, i.e., return this \ set. More...
 
- Public Member Functions inherited from mlir::presburger::IntegerRelation
 IntegerRelation (unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, const PresburgerSpace &space)
 Constructs a relation reserving memory for the specified number of constraints and variables. More...
 
 IntegerRelation (const PresburgerSpace &space)
 Constructs a relation with the specified number of dimensions and symbols. More...
 
virtual ~IntegerRelation ()=default
 
std::unique_ptr< IntegerRelationclone () const
 
const PresburgerSpacegetSpace () const
 Returns a reference to the underlying space. More...
 
void setSpace (const PresburgerSpace &oSpace)
 Set the space to oSpace, which should have the same number of ids as the current space. More...
 
void setSpaceExceptLocals (const PresburgerSpace &oSpace)
 Set the space to oSpace, which should not have any local ids. More...
 
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< IdentifiergetIds (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...
 
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 pos to the specified values and removes them. More...
 
void setAndEliminate (unsigned pos, ArrayRef< int64_t > values)
 
virtual void clearAndCopyFrom (const IntegerRelation &other)
 Replaces the contents of this IntegerRelation with other. More...
 
void getLowerAndUpperBoundIndices (unsigned pos, SmallVectorImpl< unsigned > *lbIndices, SmallVectorImpl< unsigned > *ubIndices, SmallVectorImpl< unsigned > *eqIndices=nullptr, unsigned offset=0, unsigned num=0) const
 Gather positions of all lower and upper bounds of the variable at pos, and optionally any equalities on it. More...
 
bool isEmpty () const
 Checks for emptiness by performing variable elimination on all variables, running the GCD test on each equality constraint, and checking for invalid constraints. More...
 
bool 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
 

Static Public Member Functions

static bool classof (const IntegerRelation *cst)
 
- Static Public Member Functions inherited from mlir::affine::FlatAffineValueConstraints
static bool classof (const IntegerRelation *cst)
 
- Static Public Member Functions inherited from mlir::FlatLinearValueConstraints
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 IntegerRelation getEmpty (const PresburgerSpace &space)
 Return an empty system containing an invalid equation 0 = 1. More...
 
static bool classof (const IntegerRelation *cst)
 

Protected Attributes

unsigned numDomainDims
 
unsigned numRangeDims
 
- 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...
 

Additional Inherited Members

- Public Types inherited from mlir::FlatLinearValueConstraints
using Identifier = presburger::Identifier
 The SSA Values attached to each non-local variable are stored as identifiers in the constraint system's space. More...
 
- Public Types inherited from mlir::FlatLinearConstraints
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...
 
- Protected Types inherited from mlir::FlatLinearConstraints
using VarKind = presburger::VarKind
 
- Protected Member Functions inherited from mlir::FlatLinearConstraints
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...
 
- 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...
 
- 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

A FlatAffineRelation represents a set of ordered pairs (domain -> range) where "domain" and "range" are tuples of variables.

The relation is represented as a FlatAffineValueConstraints with separation of dimension variables into domain and range. The variables are stored as: [domainVars, rangeVars, symbolVars, localVars, constant].

Deprecated: use IntegerRelation and store SSA Values in the PresburgerSpace of the relation using PresburgerSpace::identifiers. Note that FlatAffineRelation::numDomainDims and FlatAffineRelation::numRangeDims are independent of numDomain and numRange of the relation's space. In particular, operations such as FlatAffineRelation::compose do not ensure consistency between numDomainDims/numRangeDims and numDomain/numRange which may lead to unexpected behaviour.

Definition at line 164 of file AffineStructures.h.

Constructor & Destructor Documentation

◆ FlatAffineRelation() [1/4]

mlir::affine::FlatAffineRelation::FlatAffineRelation ( unsigned  numReservedInequalities,
unsigned  numReservedEqualities,
unsigned  numReservedCols,
unsigned  numDomainDims,
unsigned  numRangeDims,
unsigned  numSymbols,
unsigned  numLocals,
ArrayRef< std::optional< Value >>  valArgs = {} 
)
inline

Definition at line 166 of file AffineStructures.h.

◆ FlatAffineRelation() [2/4]

mlir::affine::FlatAffineRelation::FlatAffineRelation ( unsigned  numDomainDims = 0,
unsigned  numRangeDims = 0,
unsigned  numSymbols = 0,
unsigned  numLocals = 0 
)
inline

Definition at line 176 of file AffineStructures.h.

◆ FlatAffineRelation() [3/4]

mlir::affine::FlatAffineRelation::FlatAffineRelation ( unsigned  numDomainDims,
unsigned  numRangeDims,
FlatAffineValueConstraints fac 
)
inline

Definition at line 182 of file AffineStructures.h.

◆ FlatAffineRelation() [4/4]

mlir::affine::FlatAffineRelation::FlatAffineRelation ( unsigned  numDomainDims,
unsigned  numRangeDims,
IntegerPolyhedron fac 
)
inline

Definition at line 187 of file AffineStructures.h.

Member Function Documentation

◆ appendDomainVar()

void FlatAffineRelation::appendDomainVar ( unsigned  num = 1)

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

The coefficient columns corresponding to the added variables are initialized to zero.

Definition at line 457 of file AffineStructures.cpp.

◆ appendRangeVar()

void FlatAffineRelation::appendRangeVar ( unsigned  num = 1)

Definition at line 462 of file AffineStructures.cpp.

Referenced by compose().

◆ classof()

static bool mlir::affine::FlatAffineRelation::classof ( const IntegerRelation cst)
inlinestatic

◆ compose()

void FlatAffineRelation::compose ( const FlatAffineRelation other)

◆ getDomainSet()

FlatAffineValueConstraints FlatAffineRelation::getDomainSet ( ) const

Returns a set corresponding to the domain/range of the affine relation.

Definition at line 357 of file AffineStructures.cpp.

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

◆ getKind()

Kind mlir::affine::FlatAffineRelation::getKind ( ) const
inlineoverridevirtual

Return the kind of this object.

Reimplemented from mlir::affine::FlatAffineValueConstraints.

Definition at line 193 of file AffineStructures.h.

References mlir::presburger::IntegerRelation::FlatAffineRelation.

◆ getNumDomainDims()

unsigned mlir::affine::FlatAffineRelation::getNumDomainDims ( ) const
inline

Returns the number of variables corresponding to domain/range of relation.

Definition at line 205 of file AffineStructures.h.

References numDomainDims.

Referenced by compose().

◆ getNumRangeDims()

unsigned mlir::affine::FlatAffineRelation::getNumRangeDims ( ) const
inline

Definition at line 206 of file AffineStructures.h.

References numRangeDims.

Referenced by compose().

◆ getRangeSet()

FlatAffineValueConstraints FlatAffineRelation::getRangeSet ( ) const

◆ insertDomainVar()

void FlatAffineRelation::insertDomainVar ( unsigned  pos,
unsigned  num = 1 
)

Insert num variables of the specified kind after the pos variable of that kind.

The coefficient columns corresponding to the added variables are initialized to zero.

Definition at line 443 of file AffineStructures.cpp.

◆ insertRangeVar()

void FlatAffineRelation::insertRangeVar ( unsigned  pos,
unsigned  num = 1 
)

Definition at line 450 of file AffineStructures.cpp.

◆ inverse()

void FlatAffineRelation::inverse ( )

Swap domain and range of the relation.

(domain -> range) is converted to (range -> domain).

Definition at line 428 of file AffineStructures.cpp.

◆ removeVarRange()

void FlatAffineRelation::removeVarRange ( 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::FlatLinearValueConstraints.

Definition at line 467 of file AffineStructures.cpp.

Member Data Documentation

◆ numDomainDims

unsigned mlir::affine::FlatAffineRelation::numDomainDims
protected

Definition at line 239 of file AffineStructures.h.

Referenced by getNumDomainDims().

◆ numRangeDims

unsigned mlir::affine::FlatAffineRelation::numRangeDims
protected

Definition at line 242 of file AffineStructures.h.

Referenced by getNumRangeDims().


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