14 using namespace presburger;
16 void MultiAffineFunction::assertIsConsistent()
const {
19 "Inconsistent number of output columns");
22 "Inconsistent number of non-division variables in divs");
24 "Inconsistent number of output rows");
26 "Inconsistent number of divisions.");
27 assert(divs.
hasAllReprs() &&
"All divisions should have a representation");
35 assert(vecA.size() == vecB.size() &&
36 "Cannot subtract vectors of differing lengths!");
38 result.reserve(vecA.size());
39 for (
unsigned i = 0, e = vecA.size(); i < e; ++i)
40 result.push_back(vecA[i] - vecB[i]);
46 for (
const Piece &piece : pieces)
53 os <<
"Division Representation:\n";
62 "Point has incorrect dimensionality!");
69 pointHomogenous.reserve(pointHomogenous.size() + divValues.size());
70 for (
const std::optional<MPInt> &divVal : divValues)
71 pointHomogenous.push_back(*divVal);
77 pointHomogenous.emplace_back(1);
85 "Spaces should be compatible for equality check.");
92 "Spaces should be compatible for equality check.");
99 return restrictedThis.
isEqual(restrictedOther);
105 "Spaces should be compatible for equality check.");
108 return isEqual(other, IntegerPolyhedron(disjunct));
123 assert(space.
isCompatible(other.space) &&
"Functions should be compatible");
131 for (
unsigned i = 0; i < nDivs; ++i) {
133 std::fill(div.begin(), div.end(), 0);
145 auto merge = [&](
unsigned i,
unsigned j) {
157 other.output.
addToColumn(divOffset + i, divOffset +
j, 1);
164 unsigned newDivs = other.divs.
getNumDivs() - nDivs;
171 assertIsConsistent();
172 other.assertIsConsistent();
179 "Output space of funcs should be compatible");
213 for (
unsigned i = 0, e = funcA.
getNumDivs(); i < e; ++i) {
222 for (
unsigned level = 0; level < funcA.
getNumOutputs(); ++level) {
247 assert(
false &&
"Not implemented case");
275 return llvm::all_of(this->pieces, [&other](
const Piece &pieceA) {
276 return llvm::all_of(other.pieces, [&pieceA](
const Piece &pieceB) {
277 PresburgerSet commonDomain = pieceA.domain.intersect(pieceB.domain);
278 return pieceA.output.isEqual(pieceB.output, commonDomain);
284 assert(piece.
isConsistent() &&
"Piece should be consistent");
286 "Piece should be disjoint from the function");
287 pieces.push_back(piece);
293 for (
const Piece &piece : pieces) {
294 os <<
"Domain of piece:\n";
295 piece.domain.print(os);
296 os <<
"Output of piece\n";
297 piece.output.print(os);
307 "Ranges of functions should be same.");
309 "Space is not compatible.");
323 for (
const Piece &pieceA : pieces) {
325 for (
const Piece &pieceB : func.pieces) {
330 result.addPiece({better, pieceB.output});
331 dom = dom.subtract(better);
343 result.addPiece({dom, pieceA.output});
348 for (
const Piece &pieceB : func.pieces)
349 result.addPiece({pieceB.domain.subtract(dom), pieceB.output});
357 template <OrderingKind comp>
367 return unionFunction(func, tiebreakLex</*comp=*/OrderingKind::LT>);
371 return unionFunction(func, tiebreakLex</*comp=*/OrderingKind::GT>);
376 "Spaces should be compatible for subtraction.");
384 assertIsConsistent();
393 "All divisions in divs should have a representation");
395 "Relation and divs should have the same number of vars");
397 "Relation and divs should have the same number of local vars");
399 for (
unsigned i = 0, e = divs.
getNumDivs(); i < e; ++i) {
450 for (
Piece &piece : pieces)
451 piece.output.removeOutputs(start, end);
454 std::optional<SmallVector<MPInt, 8>>
458 for (
const Piece &piece : pieces)
459 if (piece.domain.containsPoint(point))
460 return piece.output.valueAt(point);
static void copy(Location loc, Value dst, Value src, Value size, OpBuilder &builder)
Copies the given number of bytes from src to dst pointers.
static PresburgerSet tiebreakLex(const PWMAFunction::Piece &pieceA, const PWMAFunction::Piece &pieceB)
A tiebreak function which breaks ties by comparing the outputs lexicographically based on the given c...
static void addDivisionConstraints(IntegerRelation &rel, const DivisionRepr &divs)
Adds division constraints corresponding to local variables, given a relation and division representat...
static SmallVector< MPInt, 8 > subtractExprs(ArrayRef< MPInt > vecA, ArrayRef< MPInt > vecB)
Class storing division representation of local variables of a constraint system.
void removeDuplicateDivs(llvm::function_ref< bool(unsigned i, unsigned j)> merge)
Removes duplicate divisions.
MPInt & getDenom(unsigned i)
unsigned getNumNonDivs() const
unsigned getNumVars() const
SmallVector< std::optional< MPInt >, 4 > divValuesAt(ArrayRef< MPInt > point) const
unsigned getDivOffset() const
void print(raw_ostream &os) const
unsigned getNumDivs() const
void insertDiv(unsigned pos, ArrayRef< MPInt > dividend, const MPInt &divisor)
void setDiv(unsigned i, ArrayRef< MPInt > dividend, const MPInt &divisor)
MutableArrayRef< MPInt > getDividend(unsigned i)
An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affin...
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
unsigned getVarKindEnd(VarKind kind) const
Return the index at Which the specified kind of vars ends.
void addInequality(ArrayRef< MPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
void addEquality(ArrayRef< MPInt > eq)
Adds an equality from the coefficients specified in eq.
virtual unsigned insertVar(VarKind kind, unsigned pos, unsigned num=1)
Insert num variables of the specified kind at position pos.
unsigned getNumVars() const
void intersectDomain(const IntegerPolyhedron &poly)
Intersect the given poly with the domain in-place.
bool isEqual(const IntegerRelation &other) const
Return whether this and other are equal.
unsigned getNumLocalVars() const
unsigned getNumCols() const
Returns the number of columns in the constraint system.
void removeInequality(unsigned pos)
void addBound(BoundType type, unsigned pos, const MPInt &value)
Adds a constant bound for the specified variable.
unsigned getNumInequalities() const
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of vars starts.
This class provides support for multi-precision arithmetic.
unsigned getNumRows() const
void removeColumn(unsigned pos)
void addToColumn(unsigned sourceColumn, unsigned targetColumn, const T &scale)
Add scale multiples of the source column to the target column.
void print(raw_ostream &os) const
Print the matrix.
void insertColumns(unsigned pos, unsigned count)
Insert columns having positions pos, pos + 1, ...
unsigned getNumColumns() const
SmallVector< T, 8 > postMultiplyWithColumn(ArrayRef< T > colVec) const
The given vector is interpreted as a column vector v.
void addToRow(unsigned sourceRow, unsigned targetRow, const T &scale)
Add scale multiples of the source row to the target row.
void removeRows(unsigned pos, unsigned count)
Remove the rows having positions pos, pos + 1, ...
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain...
void subtract(const MultiAffineFunction &other)
void removeOutputs(unsigned start, unsigned end)
Remove the specified range of outputs.
void print(raw_ostream &os) const
unsigned getNumDivs() const
ArrayRef< MPInt > getOutputExpr(unsigned i) const
Get the i^th output expression.
const PresburgerSpace & getSpace() const
Get the space of this function.
PresburgerSpace getDomainSpace() const
Get the domain/output space of the function.
PresburgerSet getLexSet(OrderingKind comp, const MultiAffineFunction &other) const
Return the set of domain points where the output of this and other are ordered lexicographically acco...
SmallVector< MPInt, 8 > valueAt(ArrayRef< MPInt > point) const
unsigned getNumOutputs() const
unsigned getNumDomainVars() const
void mergeDivs(MultiAffineFunction &other)
Given a MAF other, merges division variables such that both functions have the union of the division ...
unsigned getNumSymbolVars() const
IntegerRelation getAsRelation() const
Get this function as a relation.
bool isEqual(const MultiAffineFunction &other) const
Return whether the this and other are equal when the domain is restricted to domain.
This class represents a piece-wise MultiAffineFunction.
const PresburgerSpace & getSpace() const
void addPiece(const Piece &piece)
unsigned getNumDomainVars() const
void print(raw_ostream &os) const
PWMAFunction unionLexMax(const PWMAFunction &func)
std::optional< SmallVector< MPInt, 8 > > valueAt(ArrayRef< MPInt > point) const
Return the output of the function at the given point.
unsigned getNumPieces() const
void removeOutputs(unsigned start, unsigned end)
Remove the specified range of outputs.
unsigned getNumOutputs() const
PWMAFunction unionLexMin(const PWMAFunction &func)
Return a function defined on the union of the domains of this and func, such that when only one of th...
PresburgerSet getDomain() const
Return the domain of this piece-wise MultiAffineFunction.
PresburgerSpace getDomainSpace() const
Get the domain/output space of the function.
unsigned getNumSymbolVars() const
bool isEqual(const PWMAFunction &other) const
Return whether this and other are equal as PWMAFunctions, i.e.
void unionInPlace(const IntegerRelation &disjunct)
Mutate this set, turning it into the union of this set and the given disjunct.
ArrayRef< IntegerRelation > getAllDisjuncts() const
Return a reference to the list of disjuncts.
PresburgerSet intersect(const PresburgerRelation &set) const
static PresburgerSet getEmpty(const PresburgerSpace &space)
Return an empty set of the specified type that contains no points.
PresburgerSpace is the space of all possible values of a tuple of integer valued variables/variables.
unsigned getNumRangeVars() const
unsigned getNumSymbolVars() const
void removeVarRange(VarKind kind, unsigned varStart, unsigned varLimit)
Removes variables of the specified kind in the column range [varStart, varLimit).
unsigned getNumVars() const
unsigned getNumLocalVars() const
unsigned getNumDomainVars() const
bool isCompatible(const PresburgerSpace &other) const
Returns true if both the spaces are compatible i.e.
void print(llvm::raw_ostream &os) const
PresburgerSpace getSpaceWithoutLocals() const
Get the space without local variables.
static PresburgerSpace getRelationSpace(unsigned numDomain=0, unsigned numRange=0, unsigned numSymbols=0, unsigned numLocals=0)
unsigned insertVar(VarKind kind, unsigned pos, unsigned num=1)
Insert num variables of the specified kind at position pos.
SmallVector< MPInt, 8 > getDivLowerBound(ArrayRef< MPInt > dividend, const MPInt &divisor, unsigned localVarIdx)
OrderingKind
Enum representing a binary comparison operator: equal, not equal, less than, less than or equal,...
SmallVector< MPInt, 8 > getDivUpperBound(ArrayRef< MPInt > dividend, const MPInt &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 ...
This header declares functions that assist transformations in the MemRef dialect.
MultiAffineFunction output
bool isConsistent() const
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.