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