MLIR  18.0.0git
PWMAFunction.cpp
Go to the documentation of this file.
1 //===- PWMAFunction.cpp - MLIR PWMAFunction Class -------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
11 #include <optional>
12 
13 using namespace mlir;
14 using namespace presburger;
15 
16 void MultiAffineFunction::assertIsConsistent() const {
17  assert(space.getNumVars() - space.getNumRangeVars() + 1 ==
18  output.getNumColumns() &&
19  "Inconsistent number of output columns");
20  assert(space.getNumDomainVars() + space.getNumSymbolVars() ==
21  divs.getNumNonDivs() &&
22  "Inconsistent number of non-division variables in divs");
23  assert(space.getNumRangeVars() == output.getNumRows() &&
24  "Inconsistent number of output rows");
25  assert(space.getNumLocalVars() == divs.getNumDivs() &&
26  "Inconsistent number of divisions.");
27  assert(divs.hasAllReprs() && "All divisions should have a representation");
28 }
29 
30 // Return the result of subtracting the two given vectors pointwise.
31 // The vectors must be of the same size.
32 // e.g., [3, 4, 6] - [2, 5, 1] = [1, -1, 5].
34  ArrayRef<MPInt> vecB) {
35  assert(vecA.size() == vecB.size() &&
36  "Cannot subtract vectors of differing lengths!");
37  SmallVector<MPInt, 8> result;
38  result.reserve(vecA.size());
39  for (unsigned i = 0, e = vecA.size(); i < e; ++i)
40  result.push_back(vecA[i] - vecB[i]);
41  return result;
42 }
43 
46  for (const Piece &piece : pieces)
47  domain.unionInPlace(piece.domain);
48  return domain;
49 }
50 
51 void MultiAffineFunction::print(raw_ostream &os) const {
52  space.print(os);
53  os << "Division Representation:\n";
54  divs.print(os);
55  os << "Output:\n";
56  output.print(os);
57 }
58 
61  assert(point.size() == getNumDomainVars() + getNumSymbolVars() &&
62  "Point has incorrect dimensionality!");
63 
64  SmallVector<MPInt, 8> pointHomogenous{llvm::to_vector(point)};
65  // Get the division values at this point.
66  SmallVector<std::optional<MPInt>, 8> divValues = divs.divValuesAt(point);
67  // The given point didn't include the values of the divs which the output is a
68  // function of; we have computed one possible set of values and use them here.
69  pointHomogenous.reserve(pointHomogenous.size() + divValues.size());
70  for (const std::optional<MPInt> &divVal : divValues)
71  pointHomogenous.push_back(*divVal);
72  // The matrix `output` has an affine expression in the ith row, corresponding
73  // to the expression for the ith value in the output vector. The last column
74  // of the matrix contains the constant term. Let v be the input point with
75  // a 1 appended at the end. We can see that output * v gives the desired
76  // output vector.
77  pointHomogenous.emplace_back(1);
78  SmallVector<MPInt, 8> result = output.postMultiplyWithColumn(pointHomogenous);
79  assert(result.size() == getNumOutputs());
80  return result;
81 }
82 
84  assert(space.isCompatible(other.space) &&
85  "Spaces should be compatible for equality check.");
86  return getAsRelation().isEqual(other.getAsRelation());
87 }
88 
90  const IntegerPolyhedron &domain) const {
91  assert(space.isCompatible(other.space) &&
92  "Spaces should be compatible for equality check.");
93  IntegerRelation restrictedThis = getAsRelation();
94  restrictedThis.intersectDomain(domain);
95 
96  IntegerRelation restrictedOther = other.getAsRelation();
97  restrictedOther.intersectDomain(domain);
98 
99  return restrictedThis.isEqual(restrictedOther);
100 }
101 
103  const PresburgerSet &domain) const {
104  assert(space.isCompatible(other.space) &&
105  "Spaces should be compatible for equality check.");
106  return llvm::all_of(domain.getAllDisjuncts(),
107  [&](const IntegerRelation &disjunct) {
108  return isEqual(other, IntegerPolyhedron(disjunct));
109  });
110 }
111 
112 void MultiAffineFunction::removeOutputs(unsigned start, unsigned end) {
113  assert(end <= getNumOutputs() && "Invalid range");
114 
115  if (start >= end)
116  return;
117 
118  space.removeVarRange(VarKind::Range, start, end);
119  output.removeRows(start, end - start);
120 }
121 
123  assert(space.isCompatible(other.space) && "Functions should be compatible");
124 
125  unsigned nDivs = getNumDivs();
126  unsigned divOffset = divs.getDivOffset();
127 
128  other.divs.insertDiv(0, nDivs);
129 
130  SmallVector<MPInt, 8> div(other.divs.getNumVars() + 1);
131  for (unsigned i = 0; i < nDivs; ++i) {
132  // Zero fill.
133  std::fill(div.begin(), div.end(), 0);
134  // Fill div with dividend from `divs`. Do not fill the constant.
135  std::copy(divs.getDividend(i).begin(), divs.getDividend(i).end() - 1,
136  div.begin());
137  // Fill constant.
138  div.back() = divs.getDividend(i).back();
139  other.divs.setDiv(i, div, divs.getDenom(i));
140  }
141 
142  other.space.insertVar(VarKind::Local, 0, nDivs);
143  other.output.insertColumns(divOffset, nDivs);
144 
145  auto merge = [&](unsigned i, unsigned j) {
146  // We only merge from local at pos j to local at pos i, where j > i.
147  if (i >= j)
148  return false;
149 
150  // If i < nDivs, we are trying to merge duplicate divs in `this`. Since we
151  // do not want to merge duplicates in `this`, we ignore this call.
152  if (j < nDivs)
153  return false;
154 
155  // Merge things in space and output.
156  other.space.removeVarRange(VarKind::Local, j, j + 1);
157  other.output.addToColumn(divOffset + i, divOffset + j, 1);
158  other.output.removeColumn(divOffset + j);
159  return true;
160  };
161 
162  other.divs.removeDuplicateDivs(merge);
163 
164  unsigned newDivs = other.divs.getNumDivs() - nDivs;
165 
166  space.insertVar(VarKind::Local, nDivs, newDivs);
167  output.insertColumns(divOffset + nDivs, newDivs);
168  divs = other.divs;
169 
170  // Check consistency.
171  assertIsConsistent();
172  other.assertIsConsistent();
173 }
174 
177  const MultiAffineFunction &other) const {
178  assert(getSpace().isCompatible(other.getSpace()) &&
179  "Output space of funcs should be compatible");
180 
181  // Create copies of functions and merge their local space.
182  MultiAffineFunction funcA = *this;
183  MultiAffineFunction funcB = other;
184  funcA.mergeDivs(funcB);
185 
186  // We first create the set `result`, corresponding to the set where output
187  // of funcA is lexicographically larger/smaller than funcB. This is done by
188  // creating a PresburgerSet with the following constraints:
189  //
190  // (outA[0] > outB[0]) U
191  // (outA[0] = outB[0], outA[1] > outA[1]) U
192  // (outA[0] = outB[0], outA[1] = outA[1], outA[2] > outA[2]) U
193  // ...
194  // (outA[0] = outB[0], ..., outA[n-2] = outB[n-2], outA[n-1] > outB[n-1])
195  //
196  // where `n` is the number of outputs.
197  // If `lexMin` is set, the complement inequality is used:
198  //
199  // (outA[0] < outB[0]) U
200  // (outA[0] = outB[0], outA[1] < outA[1]) U
201  // (outA[0] = outB[0], outA[1] = outA[1], outA[2] < outA[2]) U
202  // ...
203  // (outA[0] = outB[0], ..., outA[n-2] = outB[n-2], outA[n-1] < outB[n-1])
204  PresburgerSpace resultSpace = funcA.getDomainSpace();
205  PresburgerSet result =
207  IntegerPolyhedron levelSet(
208  /*numReservedInequalities=*/1 + 2 * resultSpace.getNumLocalVars(),
209  /*numReservedEqualities=*/funcA.getNumOutputs(),
210  /*numReservedCols=*/resultSpace.getNumVars() + 1, resultSpace);
211 
212  // Add division inequalities to `levelSet`.
213  for (unsigned i = 0, e = funcA.getNumDivs(); i < e; ++i) {
214  levelSet.addInequality(getDivUpperBound(funcA.divs.getDividend(i),
215  funcA.divs.getDenom(i),
216  funcA.divs.getDivOffset() + i));
217  levelSet.addInequality(getDivLowerBound(funcA.divs.getDividend(i),
218  funcA.divs.getDenom(i),
219  funcA.divs.getDivOffset() + i));
220  }
221 
222  for (unsigned level = 0; level < funcA.getNumOutputs(); ++level) {
223  // Create the expression `outA - outB` for this level.
224  SmallVector<MPInt, 8> subExpr =
225  subtractExprs(funcA.getOutputExpr(level), funcB.getOutputExpr(level));
226 
227  // TODO: Implement all comparison cases.
228  switch (comp) {
229  case OrderingKind::LT:
230  // For less than, we add an upper bound of -1:
231  // outA - outB <= -1
232  // outA <= outB - 1
233  // outA < outB
234  levelSet.addBound(BoundType::UB, subExpr, MPInt(-1));
235  break;
236  case OrderingKind::GT:
237  // For greater than, we add a lower bound of 1:
238  // outA - outB >= 1
239  // outA > outB + 1
240  // outA > outB
241  levelSet.addBound(BoundType::LB, subExpr, MPInt(1));
242  break;
243  case OrderingKind::GE:
244  case OrderingKind::LE:
245  case OrderingKind::EQ:
246  case OrderingKind::NE:
247  assert(false && "Not implemented case");
248  }
249 
250  // Union the set with the result.
251  result.unionInPlace(levelSet);
252  // The last inequality in `levelSet` is the bound we inserted. We remove
253  // that for next iteration.
254  levelSet.removeInequality(levelSet.getNumInequalities() - 1);
255  // Add equality `outA - outB == 0` for this level for next iteration.
256  levelSet.addEquality(subExpr);
257  }
258 
259  return result;
260 }
261 
262 /// Two PWMAFunctions are equal if they have the same dimensionalities,
263 /// the same domain, and take the same value at every point in the domain.
264 bool PWMAFunction::isEqual(const PWMAFunction &other) const {
265  if (!space.isCompatible(other.space))
266  return false;
267 
268  if (!this->getDomain().isEqual(other.getDomain()))
269  return false;
270 
271  // Check if, whenever the domains of a piece of `this` and a piece of `other`
272  // overlap, they take the same output value. If `this` and `other` have the
273  // same domain (checked above), then this check passes iff the two functions
274  // have the same output at every point in the domain.
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);
279  });
280  });
281 }
282 
283 void PWMAFunction::addPiece(const Piece &piece) {
284  assert(piece.isConsistent() && "Piece should be consistent");
285  assert(piece.domain.intersect(getDomain()).isIntegerEmpty() &&
286  "Piece should be disjoint from the function");
287  pieces.push_back(piece);
288 }
289 
290 void PWMAFunction::print(raw_ostream &os) const {
291  space.print(os);
292  os << getNumPieces() << " pieces:\n";
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);
298  }
299 }
300 
301 void PWMAFunction::dump() const { print(llvm::errs()); }
302 
303 PWMAFunction PWMAFunction::unionFunction(
304  const PWMAFunction &func,
305  llvm::function_ref<PresburgerSet(Piece maf1, Piece maf2)> tiebreak) const {
306  assert(getNumOutputs() == func.getNumOutputs() &&
307  "Ranges of functions should be same.");
308  assert(getSpace().isCompatible(func.getSpace()) &&
309  "Space is not compatible.");
310 
311  // The algorithm used here is as follows:
312  // - Add the output of pieceB for the part of the domain where both pieceA and
313  // pieceB are defined, and `tiebreak` chooses the output of pieceB.
314  // - Add the output of pieceA, where pieceB is not defined or `tiebreak`
315  // chooses
316  // pieceA over pieceB.
317  // - Add the output of pieceB, where pieceA is not defined.
318 
319  // Add parts of the common domain where pieceB's output is used. Also
320  // add all the parts where pieceA's output is used, both common and
321  // non-common.
322  PWMAFunction result(getSpace());
323  for (const Piece &pieceA : pieces) {
324  PresburgerSet dom(pieceA.domain);
325  for (const Piece &pieceB : func.pieces) {
326  PresburgerSet better = tiebreak(pieceB, pieceA);
327  // Add the output of pieceB, where it is better than output of pieceA.
328  // The disjuncts in "better" will be disjoint as tiebreak should gurantee
329  // that.
330  result.addPiece({better, pieceB.output});
331  dom = dom.subtract(better);
332  }
333  // Add output of pieceA, where it is better than pieceB, or pieceB is not
334  // defined.
335  //
336  // `dom` here is guranteed to be disjoint from already added pieces
337  // because the pieces added before are either:
338  // - Subsets of the domain of other MAFs in `this`, which are guranteed
339  // to be disjoint from `dom`, or
340  // - They are one of the pieces added for `pieceB`, and we have been
341  // subtracting all such pieces from `dom`, so `dom` is disjoint from those
342  // pieces as well.
343  result.addPiece({dom, pieceA.output});
344  }
345 
346  // Add parts of pieceB which are not shared with pieceA.
347  PresburgerSet dom = getDomain();
348  for (const Piece &pieceB : func.pieces)
349  result.addPiece({pieceB.domain.subtract(dom), pieceB.output});
350 
351  return result;
352 }
353 
354 /// A tiebreak function which breaks ties by comparing the outputs
355 /// lexicographically based on the given comparison operator.
356 /// This is templated since it is passed as a lambda.
357 template <OrderingKind comp>
359  const PWMAFunction::Piece &pieceB) {
360  PresburgerSet result = pieceA.output.getLexSet(comp, pieceB.output);
361  result = result.intersect(pieceA.domain).intersect(pieceB.domain);
362 
363  return result;
364 }
365 
367  return unionFunction(func, tiebreakLex</*comp=*/OrderingKind::LT>);
368 }
369 
371  return unionFunction(func, tiebreakLex</*comp=*/OrderingKind::GT>);
372 }
373 
375  assert(space.isCompatible(other.space) &&
376  "Spaces should be compatible for subtraction.");
377 
378  MultiAffineFunction copyOther = other;
379  mergeDivs(copyOther);
380  for (unsigned i = 0, e = getNumOutputs(); i < e; ++i)
381  output.addToRow(i, copyOther.getOutputExpr(i), MPInt(-1));
382 
383  // Check consistency.
384  assertIsConsistent();
385 }
386 
387 /// Adds division constraints corresponding to local variables, given a
388 /// relation and division representations of the local variables in the
389 /// relation.
391  const DivisionRepr &divs) {
392  assert(divs.hasAllReprs() &&
393  "All divisions in divs should have a representation");
394  assert(rel.getNumVars() == divs.getNumVars() &&
395  "Relation and divs should have the same number of vars");
396  assert(rel.getNumLocalVars() == divs.getNumDivs() &&
397  "Relation and divs should have the same number of local vars");
398 
399  for (unsigned i = 0, e = divs.getNumDivs(); i < e; ++i) {
400  rel.addInequality(getDivUpperBound(divs.getDividend(i), divs.getDenom(i),
401  divs.getDivOffset() + i));
402  rel.addInequality(getDivLowerBound(divs.getDividend(i), divs.getDenom(i),
403  divs.getDivOffset() + i));
404  }
405 }
406 
408  // Create a relation corressponding to the input space plus the divisions
409  // used in outputs.
411  space.getNumDomainVars(), 0, space.getNumSymbolVars(),
412  space.getNumLocalVars()));
413  // Add division constraints corresponding to divisions used in outputs.
414  addDivisionConstraints(result, divs);
415  // The outputs are represented as range variables in the relation. We add
416  // range variables for the outputs.
417  result.insertVar(VarKind::Range, 0, getNumOutputs());
418 
419  // Add equalities such that the i^th range variable is equal to the i^th
420  // output expression.
421  SmallVector<MPInt, 8> eq(result.getNumCols());
422  for (unsigned i = 0, e = getNumOutputs(); i < e; ++i) {
423  // TODO: Add functions to get VarKind offsets in output in MAF and use them
424  // here.
425  // The output expression does not contain range variables, while the
426  // equality does. So, we need to copy all variables and mark all range
427  // variables as 0 in the equality.
428  ArrayRef<MPInt> expr = getOutputExpr(i);
429  // Copy domain variables in `expr` to domain variables in `eq`.
430  std::copy(expr.begin(), expr.begin() + getNumDomainVars(), eq.begin());
431  // Fill the range variables in `eq` as zero.
432  std::fill(eq.begin() + result.getVarKindOffset(VarKind::Range),
433  eq.begin() + result.getVarKindEnd(VarKind::Range), 0);
434  // Copy remaining variables in `expr` to the remaining variables in `eq`.
435  std::copy(expr.begin() + getNumDomainVars(), expr.end(),
436  eq.begin() + result.getVarKindEnd(VarKind::Range));
437 
438  // Set the i^th range var to -1 in `eq` to equate the output expression to
439  // this range var.
440  eq[result.getVarKindOffset(VarKind::Range) + i] = -1;
441  // Add the equality `rangeVar_i = output[i]`.
442  result.addEquality(eq);
443  }
444 
445  return result;
446 }
447 
448 void PWMAFunction::removeOutputs(unsigned start, unsigned end) {
449  space.removeVarRange(VarKind::Range, start, end);
450  for (Piece &piece : pieces)
451  piece.output.removeOutputs(start, end);
452 }
453 
454 std::optional<SmallVector<MPInt, 8>>
456  assert(point.size() == getNumDomainVars() + getNumSymbolVars());
457 
458  for (const Piece &piece : pieces)
459  if (piece.domain.containsPoint(point))
460  return piece.output.valueAt(point);
461  return std::nullopt;
462 }
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.
Definition: Utils.h:118
void removeDuplicateDivs(llvm::function_ref< bool(unsigned i, unsigned j)> merge)
Removes duplicate divisions.
Definition: Utils.cpp:430
MPInt & getDenom(unsigned i)
Definition: Utils.h:149
bool hasAllReprs() const
Definition: Utils.h:134
unsigned getNumNonDivs() const
Definition: Utils.h:127
unsigned getNumVars() const
Definition: Utils.h:125
SmallVector< std::optional< MPInt >, 4 > divValuesAt(ArrayRef< MPInt > point) const
Definition: Utils.cpp:382
unsigned getDivOffset() const
Definition: Utils.h:129
void print(raw_ostream &os) const
Definition: Utils.cpp:501
unsigned getNumDivs() const
Definition: Utils.h:126
void insertDiv(unsigned pos, ArrayRef< MPInt > dividend, const MPInt &divisor)
Definition: Utils.cpp:484
void setDiv(unsigned i, ArrayRef< MPInt > dividend, const MPInt &divisor)
Definition: Utils.h:154
MutableArrayRef< MPInt > getDividend(unsigned i)
Definition: Utils.h:140
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.
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 getNumCols() const
Returns the number of columns in the constraint system.
void addBound(BoundType type, unsigned pos, const MPInt &value)
Adds a constant bound for the specified variable.
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of vars starts.
This class provides support for multi-precision arithmetic.
Definition: MPInt.h:87
unsigned getNumRows() const
Definition: Matrix.h:83
void removeColumn(unsigned pos)
Definition: Matrix.cpp:145
void addToColumn(unsigned sourceColumn, unsigned targetColumn, const T &scale)
Add scale multiples of the source column to the target column.
Definition: Matrix.cpp:208
void print(raw_ostream &os) const
Print the matrix.
Definition: Matrix.cpp:262
void insertColumns(unsigned pos, unsigned count)
Insert columns having positions pos, pos + 1, ...
Definition: Matrix.cpp:104
unsigned getNumColumns() const
Definition: Matrix.h:85
SmallVector< T, 8 > postMultiplyWithColumn(ArrayRef< T > colVec) const
The given vector is interpreted as a column vector v.
Definition: Matrix.cpp:237
void addToRow(unsigned sourceRow, unsigned targetRow, const T &scale)
Add scale multiples of the source row to the target row.
Definition: Matrix.cpp:195
void removeRows(unsigned pos, unsigned count)
Remove the rows having positions pos, pos + 1, ...
Definition: Matrix.cpp:174
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain...
Definition: PWMAFunction.h:41
void subtract(const MultiAffineFunction &other)
void removeOutputs(unsigned start, unsigned end)
Remove the specified range of outputs.
void print(raw_ostream &os) const
ArrayRef< MPInt > getOutputExpr(unsigned i) const
Get the i^th output expression.
Definition: PWMAFunction.h:70
const PresburgerSpace & getSpace() const
Get the space of this function.
Definition: PWMAFunction.h:61
PresburgerSpace getDomainSpace() const
Get the domain/output space of the function.
Definition: PWMAFunction.h:64
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
void mergeDivs(MultiAffineFunction &other)
Given a MAF other, merges division variables such that both functions have the union of the division ...
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.
Definition: PWMAFunction.h:151
const PresburgerSpace & getSpace() const
Definition: PWMAFunction.h:168
void addPiece(const Piece &piece)
unsigned getNumDomainVars() const
Definition: PWMAFunction.h:177
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.
void removeOutputs(unsigned start, unsigned end)
Remove the specified range of outputs.
unsigned getNumOutputs() const
Definition: PWMAFunction.h:178
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.
Definition: PWMAFunction.h:186
unsigned getNumSymbolVars() const
Definition: PWMAFunction.h:179
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.
void removeVarRange(VarKind kind, unsigned varStart, unsigned varLimit)
Removes variables of the specified kind in the column range [varStart, varLimit).
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)
Definition: Utils.cpp:323
OrderingKind
Enum representing a binary comparison operator: equal, not equal, less than, less than or equal,...
Definition: PWMAFunction.h:28
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 ...
Definition: Utils.cpp:312
This header declares functions that assist transformations in the MemRef dialect.
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.