|
MLIR
20.0.0git
|
Namespaces | |
| detail | |
Classes | |
| struct | Fraction |
| A class to represent fractions. More... | |
| class | IntegerRelation |
| An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine constraints. More... | |
| class | IntegerPolyhedron |
| An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affine constraints. More... | |
| class | LinearTransform |
| class | Matrix |
| This is a class to represent a resizable matrix. More... | |
| class | IntMatrix |
| class | FracMatrix |
| class | PresburgerRelation |
| A PresburgerRelation represents a union of IntegerRelations that live in the same PresburgerSpace with support for union, intersection, subtraction, and complement operations, as well as sampling. More... | |
| class | PresburgerSet |
| class | Identifier |
| An Identifier stores a pointer to an object, such as a Value or an Operation. More... | |
| class | PresburgerSpace |
| PresburgerSpace is the space of all possible values of a tuple of integer valued variables/variables. More... | |
| class | MultiAffineFunction |
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain variables of the function. More... | |
| class | PWMAFunction |
| This class represents a piece-wise MultiAffineFunction. More... | |
| class | QuasiPolynomial |
| class | SimplexBase |
| The Simplex class implements a version of the Simplex and Generalized Basis Reduction algorithms, which can perform analysis of integer sets with affine inequalities and equalities. More... | |
| class | LexSimplexBase |
| Simplex class using the lexicographic pivot rule. More... | |
| class | LexSimplex |
| A class for lexicographic optimization without any symbols. More... | |
| struct | SymbolicLexOpt |
| Represents the result of a symbolic lexicographic optimization computation. More... | |
| class | SymbolicLexSimplex |
A class to perform symbolic lexicographic optimization, i.e., to find, for every assignment to the symbols the specified symbolDomain, the lexicographically minimum value integer value attained by the non-symbol variables. More... | |
| class | Simplex |
| The Simplex class uses the Normal pivot rule and supports integer emptiness checks as well as detecting redundancies. More... | |
| class | SimplexRollbackScopeExit |
| Takes a snapshot of the simplex state on construction and rolls back to the snapshot on destruction. More... | |
| class | MaybeOptimum |
| struct | MaybeLocalRepr |
MaybeLocalRepr contains the indices of the constraints that can be expressed as a floordiv of an affine function. More... | |
| class | DivisionRepr |
| Class storing division representation of local variables of a constraint system. More... | |
| class | SetCoalescer |
| The SetCoalescer class contains all functionality concerning the coalesce heuristic. More... | |
| class | GBRSimplex |
| Given a simplex for a polytope, construct a new simplex whose variables are identified with a pair of points (x, y) in the original polytope. More... | |
Enumerations | |
| enum class | BoundType { EQ , LB , UB } |
| The type of bound: equal, lower bound or upper bound. More... | |
| enum class | VarKind { Symbol , Local , Domain , Range , SetDim = Range } |
| Kind of variable. More... | |
| enum class | OrderingKind { EQ , NE , LT , LE , GT , GE } |
| Enum representing a binary comparison operator: equal, not equal, less than, less than or equal, greater than, greater than or equal. More... | |
| enum class | OptimumKind { Empty , Unbounded , Bounded } |
| This class represents the result of operations optimizing something subject to some constraints. More... | |
| enum class | ReprKind { Inequality , Equality , None } |
ReprKind enum is used to set the constraint type in MaybeLocalRepr. More... | |
Functions | |
| int | compare (const Fraction &x, const Fraction &y) |
| Three-way comparison between two fractions. More... | |
| DynamicAPInt | floor (const Fraction &f) |
| DynamicAPInt | ceil (const Fraction &f) |
| Fraction | operator- (const Fraction &x) |
| bool | operator< (const Fraction &x, const Fraction &y) |
| bool | operator<= (const Fraction &x, const Fraction &y) |
| bool | operator== (const Fraction &x, const Fraction &y) |
| bool | operator!= (const Fraction &x, const Fraction &y) |
| bool | operator> (const Fraction &x, const Fraction &y) |
| bool | operator>= (const Fraction &x, const Fraction &y) |
| Fraction | abs (const Fraction &f) |
| Fraction | reduce (const Fraction &f) |
| Fraction | operator* (const Fraction &x, const Fraction &y) |
| Fraction | operator/ (const Fraction &x, const Fraction &y) |
| Fraction | operator+ (const Fraction &x, const Fraction &y) |
| Fraction | operator- (const Fraction &x, const Fraction &y) |
| DynamicAPInt | round (const Fraction &f) |
| Fraction & | operator+= (Fraction &x, const Fraction &y) |
| Fraction & | operator-= (Fraction &x, const Fraction &y) |
| Fraction & | operator/= (Fraction &x, const Fraction &y) |
| Fraction & | operator*= (Fraction &x, const Fraction &y) |
| llvm::raw_ostream & | operator<< (llvm::raw_ostream &os, const Fraction &x) |
| SmallVector< DynamicAPInt, 8 > | getDivUpperBound (ArrayRef< DynamicAPInt > dividend, const DynamicAPInt &divisor, unsigned localVarIdx) |
If q is defined to be equal to expr floordiv d, this equivalent to saying that q is an integer and q is subject to the inequalities 0 <= expr - d*q <= c - 1 (quotient remainder theorem). More... | |
| SmallVector< DynamicAPInt, 8 > | getDivLowerBound (ArrayRef< DynamicAPInt > dividend, const DynamicAPInt &divisor, unsigned localVarIdx) |
| llvm::SmallBitVector | getSubrangeBitVector (unsigned len, unsigned setOffset, unsigned numSet) |
| SmallVector< DynamicAPInt, 8 > | getDynamicAPIntVec (ArrayRef< int64_t > range) |
| Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables (where the divisor is a positive constant). More... | |
| SmallVector< int64_t, 8 > | getInt64Vec (ArrayRef< DynamicAPInt > range) |
| Return the given array as an array of int64_t. More... | |
| MaybeLocalRepr | computeSingleVarRepr (const IntegerRelation &cst, ArrayRef< bool > foundRepr, unsigned pos, MutableArrayRef< DynamicAPInt > dividend, DynamicAPInt &divisor) |
Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed as a floordiv of an affine function. More... | |
| MaybeLocalRepr | computeSingleVarRepr (const IntegerRelation &cst, ArrayRef< bool > foundRepr, unsigned pos, SmallVector< int64_t, 8 > ÷nd, unsigned &divisor) |
| The following overload using int64_t is required for a callsite in AffineStructures.h. More... | |
| void | mergeLocalVars (IntegerRelation &relA, IntegerRelation &relB, llvm::function_ref< bool(unsigned i, unsigned j)> merge) |
| Given two relations, A and B, add additional local vars to the sets such that both have the union of the local vars in each set, without changing the set of points that lie in A and B. More... | |
| DynamicAPInt | gcdRange (ArrayRef< DynamicAPInt > range) |
| Compute the gcd of the range. More... | |
| DynamicAPInt | normalizeRange (MutableArrayRef< DynamicAPInt > range) |
| Divide the range by its gcd and return the gcd. More... | |
| void | normalizeDiv (MutableArrayRef< DynamicAPInt > num, DynamicAPInt &denom) |
| Normalize the given (numerator, denominator) pair by dividing out the common factors between them. More... | |
| SmallVector< DynamicAPInt, 8 > | getNegatedCoeffs (ArrayRef< DynamicAPInt > coeffs) |
Return coeffs with all the elements negated. More... | |
| SmallVector< DynamicAPInt, 8 > | getComplementIneq (ArrayRef< DynamicAPInt > ineq) |
| Return the complement of the given inequality. More... | |
| Fraction | dotProduct (ArrayRef< Fraction > a, ArrayRef< Fraction > b) |
| Compute the dot product of two vectors. More... | |
| std::vector< Fraction > | multiplyPolynomials (ArrayRef< Fraction > a, ArrayRef< Fraction > b) |
| Find the product of two polynomials, each given by an array of coefficients. More... | |
| bool | isRangeZero (ArrayRef< Fraction > arr) |
|
strong |
The type of bound: equal, lower bound or upper bound.
| Enumerator | |
|---|---|
| EQ | |
| LB | |
| UB | |
Definition at line 43 of file IntegerRelation.h.
|
strong |
This class represents the result of operations optimizing something subject to some constraints.
If the constraints were not satisfiable the, kind will be Empty. If the optimum is unbounded, the kind is Unbounded, and if the optimum is bounded, the kind will be Bounded and optimum holds the optimal value.
| Enumerator | |
|---|---|
| Empty | |
| Unbounded | |
| Bounded | |
|
strong |
Enum representing a binary comparison operator: equal, not equal, less than, less than or equal, greater than, greater than or equal.
| Enumerator | |
|---|---|
| EQ | |
| NE | |
| LT | |
| LE | |
| GT | |
| GE | |
Definition at line 28 of file PWMAFunction.h.
|
strong |
ReprKind enum is used to set the constraint type in MaybeLocalRepr.
| Enumerator | |
|---|---|
| Inequality | |
| Equality | |
| None | |
|
strong |
Kind of variable.
Implementation wise SetDims are treated as Range vars, and spaces with no distinction between dimension vars are treated as relations with zero domain vars.
| Enumerator | |
|---|---|
| Symbol | |
| Local | |
| Domain | |
| Range | |
| SetDim | |
Definition at line 31 of file PresburgerSpace.h.
Definition at line 106 of file Fraction.h.
References mlir::presburger::Fraction::den, and mlir::presburger::Fraction::num.
Referenced by mlir::presburger::detail::computeNumTerms(), mlir::presburger::detail::computeUnimodularConeGeneratingFunction(), eliminateFromConstraint(), gcdRange(), mlir::AffineExpr::getLargestKnownDivisor(), mlir::FlatLinearConstraints::getLowerAndUpperBound(), getNudgedScaleAndZeroPoint(), mlir::vector::isDisjointTransferIndices(), mlir::presburger::IntegerRelation::isEmptyByGCDTest(), normalizeDivisionByGCD(), reduce(), mlir::presburger::IntegerRelation::removeRedundantLocalVars(), impl::MemRefDataVerifier< T >::verifyRelErrorSmallerThan(), and mlir::SimpleAffineExprFlattener::visitModExpr().
|
inline |
Definition at line 78 of file Fraction.h.
References mlir::presburger::Fraction::den, and mlir::presburger::Fraction::num.
Referenced by mlir::presburger::Simplex::computeIntegerBounds(), and computePaddedShape().
Three-way comparison between two fractions.
Returns +1, 0, and -1 if the first fraction is greater than, equal to, or less than the second fraction, respectively.
Definition at line 67 of file Fraction.h.
References mlir::presburger::Fraction::den, and mlir::presburger::Fraction::num.
Referenced by llvm::cl::OptionValue< mlir::OpPassManager >::compare(), mlir::impl::findAttrSorted(), mlir::getValuesSortedByKey(), matchSelectReduction(), operator!=(), operator<(), operator<=(), operator==(), operator>(), and operator>=().
| MaybeLocalRepr mlir::presburger::computeSingleVarRepr | ( | const IntegerRelation & | cst, |
| ArrayRef< bool > | foundRepr, | ||
| unsigned | pos, | ||
| MutableArrayRef< DynamicAPInt > | dividend, | ||
| DynamicAPInt & | divisor | ||
| ) |
Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed as a floordiv of an affine function.
Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables (where the divisor is a positive constant).
If the representation could be computed, dividend and divisor are set, in which case, denominator will be positive. If the representation could not be computed, the kind attribute in MaybeLocalRepr is set to None.
foundRepr contains a boolean for each variable indicating if the explicit representation for that variable has already been computed. Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed as a floordiv of an affine function. If the representation could be computed, dividend and denominator are set. If the representation could not be computed, the kind attribute in MaybeLocalRepr is set to None.
Definition at line 228 of file Utils.cpp.
References checkExplicitRepresentation(), Equality, getDivRepr(), mlir::presburger::IntegerRelation::getLowerAndUpperBoundIndices(), mlir::presburger::IntegerRelation::getNumCols(), mlir::presburger::IntegerRelation::getNumVars(), Inequality, and mlir::presburger::MaybeLocalRepr::kind.
Referenced by computeSingleVarRepr(), detectAsFloorDiv(), and mlir::presburger::IntegerRelation::getLocalReprs().
| MaybeLocalRepr mlir::presburger::computeSingleVarRepr | ( | const IntegerRelation & | cst, |
| ArrayRef< bool > | foundRepr, | ||
| unsigned | pos, | ||
| SmallVector< int64_t, 8 > & | dividend, | ||
| unsigned & | divisor | ||
| ) |
The following overload using int64_t is required for a callsite in AffineStructures.h.
Definition at line 269 of file Utils.cpp.
References computeSingleVarRepr(), getInt64Vec(), and mlir::presburger::IntegerRelation::getNumCols().
Compute the dot product of two vectors.
The vectors must have the same sizes.
Definition at line 538 of file Utils.cpp.
Referenced by mlir::presburger::detail::getNonOrthogonalVector(), mlir::presburger::FracMatrix::gramSchmidt(), mlir::presburger::FracMatrix::LLL(), and substituteMuInTerm().
|
inline |
Definition at line 76 of file Fraction.h.
References mlir::presburger::Fraction::den, and mlir::presburger::Fraction::num.
Referenced by mlir::presburger::Simplex::computeIntegerBounds(), and mlir::sparse_tensor::genMapBuffers().
| DynamicAPInt mlir::presburger::gcdRange | ( | ArrayRef< DynamicAPInt > | range | ) |
Compute the gcd of the range.
Definition at line 342 of file Utils.cpp.
References abs().
Referenced by normalizeDiv(), and normalizeRange().
| SmallVector< DynamicAPInt, 8 > mlir::presburger::getComplementIneq | ( | ArrayRef< DynamicAPInt > | ineq | ) |
Return the complement of the given inequality.
The complement of a_1 x_1 + ... + a_n x_ + c >= 0 is a_1 x_1 + ... + a_n x_ + c < 0, i.e., -a_1 x_1 - ... - a_n x_ - c - 1 >= 0, since all the variables are constrained to be integers.
Definition at line 382 of file Utils.cpp.
Referenced by mlir::presburger::SymbolicLexSimplex::computeSymbolicIntegerLexMin(), and mlir::presburger::LexSimplex::isRedundantInequality().
| SmallVector< DynamicAPInt, 8 > mlir::presburger::getDivLowerBound | ( | ArrayRef< DynamicAPInt > | dividend, |
| const DynamicAPInt & | divisor, | ||
| unsigned | localVarIdx | ||
| ) |
Definition at line 328 of file Utils.cpp.
Referenced by addDivisionConstraints(), mlir::presburger::IntegerRelation::addLocalFloorDiv(), and mlir::presburger::MultiAffineFunction::getLexSet().
| SmallVector< DynamicAPInt, 8 > mlir::presburger::getDivUpperBound | ( | ArrayRef< DynamicAPInt > | dividend, |
| const DynamicAPInt & | divisor, | ||
| unsigned | localVarIdx | ||
| ) |
If q is defined to be equal to expr floordiv d, this equivalent to saying that q is an integer and q is subject to the inequalities 0 <= expr - d*q <= c - 1 (quotient remainder theorem).
Rearranging, we get the bounds on q: d*q <= expr <= d*q + d - 1.
getDivUpperBound returns d*q <= expr, and getDivLowerBound returns expr <= d*q + d - 1.
The parameter dividend corresponds to expr above, divisor to d, and localVarIdx to the position of q in the coefficient list.
The coefficient of q in dividend must be zero, as it is not allowed for local variable to be a floor division of an expression involving itself. The divisor must be positive.
Definition at line 316 of file Utils.cpp.
Referenced by addDivisionConstraints(), mlir::presburger::IntegerRelation::addLocalFloorDiv(), and mlir::presburger::MultiAffineFunction::getLexSet().
| SmallVector< DynamicAPInt, 8 > mlir::presburger::getDynamicAPIntVec | ( | ArrayRef< int64_t > | range | ) |
Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables (where the divisor is a positive constant).
foundRepr contains a boolean for each variable indicating if the explicit representation for that variable has already been computed. Return the given array as an array of DynamicAPInts.
Definition at line 524 of file Utils.cpp.
Referenced by mlir::presburger::IntegerRelation::addBound(), mlir::presburger::IntegerRelation::addEquality(), mlir::presburger::IntegerRelation::addInequality(), mlir::presburger::IntegerRelation::addLocalFloorDiv(), mlir::presburger::IntegerRelation::containsPoint(), mlir::presburger::PresburgerRelation::containsPoint(), mlir::presburger::IntegerRelation::containsPointNoLocal(), mlir::presburger::IntegerRelation::setAndEliminate(), mlir::presburger::MultiAffineFunction::valueAt(), and mlir::presburger::PWMAFunction::valueAt().
| SmallVector< int64_t, 8 > mlir::presburger::getInt64Vec | ( | ArrayRef< DynamicAPInt > | range | ) |
Return the given array as an array of int64_t.
Definition at line 531 of file Utils.cpp.
Referenced by computeSingleVarRepr(), mlir::presburger::IntegerRelation::getConstantBoundOnDimSize64(), mlir::presburger::IntegerRelation::getEquality64(), and mlir::presburger::IntegerRelation::getInequality64().
| SmallVector< DynamicAPInt, 8 > mlir::presburger::getNegatedCoeffs | ( | ArrayRef< DynamicAPInt > | coeffs | ) |
Return coeffs with all the elements negated.
Definition at line 373 of file Utils.cpp.
Referenced by getIneqCoeffsFromIdx().
| llvm::SmallBitVector mlir::presburger::getSubrangeBitVector | ( | unsigned | len, |
| unsigned | setOffset, | ||
| unsigned | numSet | ||
| ) |
| void mlir::presburger::mergeLocalVars | ( | IntegerRelation & | relA, |
| IntegerRelation & | relB, | ||
| llvm::function_ref< bool(unsigned i, unsigned j)> | merge | ||
| ) |
Given two relations, A and B, add additional local vars to the sets such that both have the union of the local vars in each set, without changing the set of points that lie in A and B.
While taking union, if a local var in any set has a division representation which is a duplicate of division representation, of another local var in any set, it is not added to the final union of local vars and is instead merged.
On every possible merge, merge(i, j) is called. i, j are position of local variables in both sets which are being merged. If merge(i, j) returns true, the divisions are merged, otherwise the divisions are not merged.
Definition at line 289 of file Utils.cpp.
References mlir::presburger::DivisionRepr::getDenom(), mlir::presburger::DivisionRepr::getDividend(), mlir::presburger::IntegerRelation::getLocalReprs(), mlir::presburger::DivisionRepr::getNumDivs(), mlir::presburger::IntegerRelation::getNumLocalVars(), mlir::presburger::IntegerRelation::getSpace(), mlir::presburger::IntegerRelation::insertVar(), mlir::presburger::PresburgerSpace::isCompatible(), Local, mlir::presburger::DivisionRepr::removeDuplicateDivs(), and mlir::presburger::DivisionRepr::setDiv().
Referenced by mlir::affine::FlatAffineRelation::compose(), and mlir::presburger::IntegerRelation::mergeLocalVars().
| void mlir::presburger::normalizeDiv | ( | MutableArrayRef< DynamicAPInt > | num, |
| DynamicAPInt & | denom | ||
| ) |
Normalize the given (numerator, denominator) pair by dividing out the common factors between them.
The numerator here is an affine expression with integer coefficients. The denominator must be positive.
Definition at line 361 of file Utils.cpp.
References gcdRange().
Referenced by mlir::presburger::DivisionRepr::normalizeDivs().
| DynamicAPInt mlir::presburger::normalizeRange | ( | MutableArrayRef< DynamicAPInt > | range | ) |
Divide the range by its gcd and return the gcd.
Definition at line 352 of file Utils.cpp.
References gcdRange().
Referenced by mlir::presburger::SymbolicLexSimplex::computeSymbolicIntegerLexMin(), and mlir::presburger::IntMatrix::normalizeRow().
Definition at line 94 of file Fraction.h.
References compare().
Definition at line 118 of file Fraction.h.
References mlir::presburger::Fraction::den, mlir::presburger::Fraction::num, and reduce().
Definition at line 155 of file Fraction.h.
Definition at line 126 of file Fraction.h.
References mlir::presburger::Fraction::den, mlir::presburger::Fraction::num, and reduce().
Definition at line 140 of file Fraction.h.
Definition at line 80 of file Fraction.h.
References mlir::presburger::Fraction::den, and mlir::presburger::Fraction::num.
Definition at line 130 of file Fraction.h.
References mlir::presburger::Fraction::den, mlir::presburger::Fraction::num, and reduce().
Definition at line 145 of file Fraction.h.
Definition at line 122 of file Fraction.h.
References mlir::presburger::Fraction::den, mlir::presburger::Fraction::num, and reduce().
Definition at line 150 of file Fraction.h.
Definition at line 82 of file Fraction.h.
References compare().
Referenced by mlir::ValueBoundsConstraintSet::BoundBuilder::operator<(), and mlir::ValueBoundsConstraintSet::BoundBuilder::operator<=().
|
inline |
Definition at line 160 of file Fraction.h.
References mlir::presburger::Fraction::print().
Definition at line 86 of file Fraction.h.
References compare().
Referenced by mlir::ValueBoundsConstraintSet::BoundBuilder::operator<=().
Definition at line 90 of file Fraction.h.
References compare().
Definition at line 98 of file Fraction.h.
References compare().
Referenced by mlir::ValueBoundsConstraintSet::BoundBuilder::operator>().
Definition at line 102 of file Fraction.h.
References compare().
Referenced by mlir::ValueBoundsConstraintSet::BoundBuilder::operator>(), and mlir::ValueBoundsConstraintSet::BoundBuilder::operator>=().
Definition at line 111 of file Fraction.h.
References abs(), mlir::presburger::Fraction::den, and mlir::presburger::Fraction::num.
Referenced by operator*(), operator+(), operator-(), and operator/().
|
inline |
Definition at line 135 of file Fraction.h.
References mlir::presburger::Fraction::den, and mlir::presburger::Fraction::num.
Referenced by computeMultiplierAndShiftTosaScale16(), computeMultiplierAndShiftTosaScale32(), getNudgedScaleAndZeroPoint(), mlir::presburger::FracMatrix::LLL(), and mlir::quant::UniformQuantizedValueConverter::~UniformQuantizedValueConverter().
1.9.1