MLIR  16.0.0git
Utils.cpp
Go to the documentation of this file.
1 //===- Utils.cpp - General utilities for Presburger library ---------------===//
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 //
9 // Utility functions required by the Presburger Library.
10 //
11 //===----------------------------------------------------------------------===//
12 
18 #include <numeric>
19 
20 #include <numeric>
21 
22 using namespace mlir;
23 using namespace presburger;
24 
25 /// Normalize a division's `dividend` and the `divisor` by their GCD. For
26 /// example: if the dividend and divisor are [2,0,4] and 4 respectively,
27 /// they get normalized to [1,0,2] and 2. The divisor must be non-negative;
28 /// it is allowed for the divisor to be zero, but nothing is done in this case.
30  MPInt &divisor) {
31  assert(divisor > 0 && "divisor must be non-negative!");
32  if (divisor == 0 || dividend.empty())
33  return;
34  // We take the absolute value of dividend's coefficients to make sure that
35  // `gcd` is positive.
36  MPInt gcd = presburger::gcd(abs(dividend.front()), divisor);
37 
38  // The reason for ignoring the constant term is as follows.
39  // For a division:
40  // floor((a + m.f(x))/(m.d))
41  // It can be replaced by:
42  // floor((floor(a/m) + f(x))/d)
43  // Since `{a/m}/d` in the dividend satisfies 0 <= {a/m}/d < 1/d, it will not
44  // influence the result of the floor division and thus, can be ignored.
45  for (size_t i = 1, m = dividend.size() - 1; i < m; i++) {
46  gcd = presburger::gcd(abs(dividend[i]), gcd);
47  if (gcd == 1)
48  return;
49  }
50 
51  // Normalize the dividend and the denominator.
52  std::transform(dividend.begin(), dividend.end(), dividend.begin(),
53  [gcd](MPInt &n) { return floorDiv(n, gcd); });
54  divisor /= gcd;
55 }
56 
57 /// Check if the pos^th variable can be represented as a division using upper
58 /// bound inequality at position `ubIneq` and lower bound inequality at position
59 /// `lbIneq`.
60 ///
61 /// Let `var` be the pos^th variable, then `var` is equivalent to
62 /// `expr floordiv divisor` if there are constraints of the form:
63 /// 0 <= expr - divisor * var <= divisor - 1
64 /// Rearranging, we have:
65 /// divisor * var - expr + (divisor - 1) >= 0 <-- Lower bound for 'var'
66 /// -divisor * var + expr >= 0 <-- Upper bound for 'var'
67 ///
68 /// For example:
69 /// 32*k >= 16*i + j - 31 <-- Lower bound for 'k'
70 /// 32*k <= 16*i + j <-- Upper bound for 'k'
71 /// expr = 16*i + j, divisor = 32
72 /// k = ( 16*i + j ) floordiv 32
73 ///
74 /// 4q >= i + j - 2 <-- Lower bound for 'q'
75 /// 4q <= i + j + 1 <-- Upper bound for 'q'
76 /// expr = i + j + 1, divisor = 4
77 /// q = (i + j + 1) floordiv 4
78 //
79 /// This function also supports detecting divisions from bounds that are
80 /// strictly tighter than the division bounds described above, since tighter
81 /// bounds imply the division bounds. For example:
82 /// 4q - i - j + 2 >= 0 <-- Lower bound for 'q'
83 /// -4q + i + j >= 0 <-- Tight upper bound for 'q'
84 ///
85 /// To extract floor divisions with tighter bounds, we assume that that the
86 /// constraints are of the form:
87 /// c <= expr - divisior * var <= divisor - 1, where 0 <= c <= divisor - 1
88 /// Rearranging, we have:
89 /// divisor * var - expr + (divisor - 1) >= 0 <-- Lower bound for 'var'
90 /// -divisor * var + expr - c >= 0 <-- Upper bound for 'var'
91 ///
92 /// If successful, `expr` is set to dividend of the division and `divisor` is
93 /// set to the denominator of the division, which will be positive.
94 /// The final division expression is normalized by GCD.
95 static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
96  unsigned ubIneq, unsigned lbIneq,
97  MutableArrayRef<MPInt> expr, MPInt &divisor) {
98 
99  assert(pos <= cst.getNumVars() && "Invalid variable position");
100  assert(ubIneq <= cst.getNumInequalities() &&
101  "Invalid upper bound inequality position");
102  assert(lbIneq <= cst.getNumInequalities() &&
103  "Invalid upper bound inequality position");
104  assert(expr.size() == cst.getNumCols() && "Invalid expression size");
105  assert(cst.atIneq(lbIneq, pos) > 0 && "lbIneq is not a lower bound!");
106  assert(cst.atIneq(ubIneq, pos) < 0 && "ubIneq is not an upper bound!");
107 
108  // Extract divisor from the lower bound.
109  divisor = cst.atIneq(lbIneq, pos);
110 
111  // First, check if the constraints are opposite of each other except the
112  // constant term.
113  unsigned i = 0, e = 0;
114  for (i = 0, e = cst.getNumVars(); i < e; ++i)
115  if (cst.atIneq(ubIneq, i) != -cst.atIneq(lbIneq, i))
116  break;
117 
118  if (i < e)
119  return failure();
120 
121  // Then, check if the constant term is of the proper form.
122  // Due to the form of the upper/lower bound inequalities, the sum of their
123  // constants is `divisor - 1 - c`. From this, we can extract c:
124  MPInt constantSum = cst.atIneq(lbIneq, cst.getNumCols() - 1) +
125  cst.atIneq(ubIneq, cst.getNumCols() - 1);
126  MPInt c = divisor - 1 - constantSum;
127 
128  // Check if `c` satisfies the condition `0 <= c <= divisor - 1`.
129  // This also implictly checks that `divisor` is positive.
130  if (!(0 <= c && c <= divisor - 1)) // NOLINT
131  return failure();
132 
133  // The inequality pair can be used to extract the division.
134  // Set `expr` to the dividend of the division except the constant term, which
135  // is set below.
136  for (i = 0, e = cst.getNumVars(); i < e; ++i)
137  if (i != pos)
138  expr[i] = cst.atIneq(ubIneq, i);
139 
140  // From the upper bound inequality's form, its constant term is equal to the
141  // constant term of `expr`, minus `c`. From this,
142  // constant term of `expr` = constant term of upper bound + `c`.
143  expr.back() = cst.atIneq(ubIneq, cst.getNumCols() - 1) + c;
144  normalizeDivisionByGCD(expr, divisor);
145 
146  return success();
147 }
148 
149 /// Check if the pos^th variable can be represented as a division using
150 /// equality at position `eqInd`.
151 ///
152 /// For example:
153 /// 32*k == 16*i + j - 31 <-- `eqInd` for 'k'
154 /// expr = 16*i + j - 31, divisor = 32
155 /// k = (16*i + j - 31) floordiv 32
156 ///
157 /// If successful, `expr` is set to dividend of the division and `divisor` is
158 /// set to the denominator of the division. The final division expression is
159 /// normalized by GCD.
160 static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
161  unsigned eqInd, MutableArrayRef<MPInt> expr,
162  MPInt &divisor) {
163 
164  assert(pos <= cst.getNumVars() && "Invalid variable position");
165  assert(eqInd <= cst.getNumEqualities() && "Invalid equality position");
166  assert(expr.size() == cst.getNumCols() && "Invalid expression size");
167 
168  // Extract divisor, the divisor can be negative and hence its sign information
169  // is stored in `signDiv` to reverse the sign of dividend's coefficients.
170  // Equality must involve the pos-th variable and hence `tempDiv` != 0.
171  MPInt tempDiv = cst.atEq(eqInd, pos);
172  if (tempDiv == 0)
173  return failure();
174  int signDiv = tempDiv < 0 ? -1 : 1;
175 
176  // The divisor is always a positive integer.
177  divisor = tempDiv * signDiv;
178 
179  for (unsigned i = 0, e = cst.getNumVars(); i < e; ++i)
180  if (i != pos)
181  expr[i] = -signDiv * cst.atEq(eqInd, i);
182 
183  expr.back() = -signDiv * cst.atEq(eqInd, cst.getNumCols() - 1);
184  normalizeDivisionByGCD(expr, divisor);
185 
186  return success();
187 }
188 
189 // Returns `false` if the constraints depends on a variable for which an
190 // explicit representation has not been found yet, otherwise returns `true`.
192  ArrayRef<bool> foundRepr,
193  ArrayRef<MPInt> dividend,
194  unsigned pos) {
195  // Exit to avoid circular dependencies between divisions.
196  for (unsigned c = 0, e = cst.getNumVars(); c < e; ++c) {
197  if (c == pos)
198  continue;
199 
200  if (!foundRepr[c] && dividend[c] != 0) {
201  // Expression can't be constructed as it depends on a yet unknown
202  // variable.
203  //
204  // TODO: Visit/compute the variables in an order so that this doesn't
205  // happen. More complex but much more efficient.
206  return false;
207  }
208  }
209 
210  return true;
211 }
212 
213 /// Check if the pos^th variable can be expressed as a floordiv of an affine
214 /// function of other variables (where the divisor is a positive constant).
215 /// `foundRepr` contains a boolean for each variable indicating if the
216 /// explicit representation for that variable has already been computed.
217 /// Returns the `MaybeLocalRepr` struct which contains the indices of the
218 /// constraints that can be expressed as a floordiv of an affine function. If
219 /// the representation could be computed, `dividend` and `denominator` are set.
220 /// If the representation could not be computed, the kind attribute in
221 /// `MaybeLocalRepr` is set to None.
223  ArrayRef<bool> foundRepr,
224  unsigned pos,
225  MutableArrayRef<MPInt> dividend,
226  MPInt &divisor) {
227  assert(pos < cst.getNumVars() && "invalid position");
228  assert(foundRepr.size() == cst.getNumVars() &&
229  "Size of foundRepr does not match total number of variables");
230  assert(dividend.size() == cst.getNumCols() && "Invalid dividend size");
231 
232  SmallVector<unsigned, 4> lbIndices, ubIndices, eqIndices;
233  cst.getLowerAndUpperBoundIndices(pos, &lbIndices, &ubIndices, &eqIndices);
234  MaybeLocalRepr repr{};
235 
236  for (unsigned ubPos : ubIndices) {
237  for (unsigned lbPos : lbIndices) {
238  // Attempt to get divison representation from ubPos, lbPos.
239  if (failed(getDivRepr(cst, pos, ubPos, lbPos, dividend, divisor)))
240  continue;
241 
242  if (!checkExplicitRepresentation(cst, foundRepr, dividend, pos))
243  continue;
244 
245  repr.kind = ReprKind::Inequality;
246  repr.repr.inequalityPair = {ubPos, lbPos};
247  return repr;
248  }
249  }
250  for (unsigned eqPos : eqIndices) {
251  // Attempt to get divison representation from eqPos.
252  if (failed(getDivRepr(cst, pos, eqPos, dividend, divisor)))
253  continue;
254 
255  if (!checkExplicitRepresentation(cst, foundRepr, dividend, pos))
256  continue;
257 
258  repr.kind = ReprKind::Equality;
259  repr.repr.equalityIdx = eqPos;
260  return repr;
261  }
262  return repr;
263 }
264 
266  const IntegerRelation &cst, ArrayRef<bool> foundRepr, unsigned pos,
267  SmallVector<int64_t, 8> &dividend, unsigned &divisor) {
268  SmallVector<MPInt, 8> dividendMPInt(cst.getNumCols());
269  MPInt divisorMPInt;
270  MaybeLocalRepr result =
271  computeSingleVarRepr(cst, foundRepr, pos, dividendMPInt, divisorMPInt);
272  dividend = getInt64Vec(dividendMPInt);
273  divisor = unsigned(int64_t(divisorMPInt));
274  return result;
275 }
276 
277 llvm::SmallBitVector presburger::getSubrangeBitVector(unsigned len,
278  unsigned setOffset,
279  unsigned numSet) {
280  llvm::SmallBitVector vec(len, false);
281  vec.set(setOffset, setOffset + numSet);
282  return vec;
283 }
284 
286  IntegerRelation &relA, IntegerRelation &relB,
287  llvm::function_ref<bool(unsigned i, unsigned j)> merge) {
288  assert(relA.getSpace().isCompatible(relB.getSpace()) &&
289  "Spaces should be compatible.");
290 
291  // Merge local vars of relA and relB without using division information,
292  // i.e. append local vars of `relB` to `relA` and insert local vars of `relA`
293  // to `relB` at start of its local vars.
294  unsigned initLocals = relA.getNumLocalVars();
296  relB.getNumLocalVars());
297  relB.insertVar(VarKind::Local, 0, initLocals);
298 
299  // Get division representations from each rel.
300  DivisionRepr divsA = relA.getLocalReprs();
301  DivisionRepr divsB = relB.getLocalReprs();
302 
303  for (unsigned i = initLocals, e = divsB.getNumDivs(); i < e; ++i)
304  divsA.setDiv(i, divsB.getDividend(i), divsB.getDenom(i));
305 
306  // Remove duplicate divisions from divsA. The removing duplicate divisions
307  // call, calls `merge` to effectively merge divisions in relA and relB.
308  divsA.removeDuplicateDivs(merge);
309 }
310 
312  const MPInt &divisor,
313  unsigned localVarIdx) {
314  assert(divisor > 0 && "divisor must be positive!");
315  assert(dividend[localVarIdx] == 0 &&
316  "Local to be set to division must have zero coeff!");
317  SmallVector<MPInt, 8> ineq(dividend.begin(), dividend.end());
318  ineq[localVarIdx] = -divisor;
319  return ineq;
320 }
321 
323  const MPInt &divisor,
324  unsigned localVarIdx) {
325  assert(divisor > 0 && "divisor must be positive!");
326  assert(dividend[localVarIdx] == 0 &&
327  "Local to be set to division must have zero coeff!");
328  SmallVector<MPInt, 8> ineq(dividend.size());
329  std::transform(dividend.begin(), dividend.end(), ineq.begin(),
330  std::negate<MPInt>());
331  ineq[localVarIdx] = divisor;
332  ineq.back() += divisor - 1;
333  return ineq;
334 }
335 
337  MPInt gcd(0);
338  for (const MPInt &elem : range) {
339  gcd = presburger::gcd(gcd, abs(elem));
340  if (gcd == 1)
341  return gcd;
342  }
343  return gcd;
344 }
345 
347  MPInt gcd = gcdRange(range);
348  if ((gcd == 0) || (gcd == 1))
349  return gcd;
350  for (MPInt &elem : range)
351  elem /= gcd;
352  return gcd;
353 }
354 
356  assert(denom > 0 && "denom must be positive!");
357  MPInt gcd = presburger::gcd(gcdRange(num), denom);
358  for (MPInt &coeff : num)
359  coeff /= gcd;
360  denom /= gcd;
361 }
362 
364  SmallVector<MPInt, 8> negatedCoeffs;
365  negatedCoeffs.reserve(coeffs.size());
366  for (const MPInt &coeff : coeffs)
367  negatedCoeffs.emplace_back(-coeff);
368  return negatedCoeffs;
369 }
370 
372  SmallVector<MPInt, 8> coeffs;
373  coeffs.reserve(ineq.size());
374  for (const MPInt &coeff : ineq)
375  coeffs.emplace_back(-coeff);
376  --coeffs.back();
377  return coeffs;
378 }
379 
382  assert(point.size() == getNumNonDivs() && "Incorrect point size");
383 
384  SmallVector<Optional<MPInt>, 4> divValues(getNumDivs(), std::nullopt);
385  bool changed = true;
386  while (changed) {
387  changed = false;
388  for (unsigned i = 0, e = getNumDivs(); i < e; ++i) {
389  // If division value is found, continue;
390  if (divValues[i])
391  continue;
392 
393  ArrayRef<MPInt> dividend = getDividend(i);
394  MPInt divVal(0);
395 
396  // Check if we have all the division values required for this division.
397  unsigned j, f;
398  for (j = 0, f = getNumDivs(); j < f; ++j) {
399  if (dividend[getDivOffset() + j] == 0)
400  continue;
401  // Division value required, but not found yet.
402  if (!divValues[j])
403  break;
404  divVal += dividend[getDivOffset() + j] * divValues[j].value();
405  }
406 
407  // We have some division values that are still not found, but are required
408  // to find the value of this division.
409  if (j < f)
410  continue;
411 
412  // Fill remaining values.
413  divVal = std::inner_product(point.begin(), point.end(), dividend.begin(),
414  divVal);
415  // Add constant.
416  divVal += dividend.back();
417  // Take floor division with denominator.
418  divVal = floorDiv(divVal, denoms[i]);
419 
420  // Set div value and continue.
421  divValues[i] = divVal;
422  changed = true;
423  }
424  }
425 
426  return divValues;
427 }
428 
430  llvm::function_ref<bool(unsigned i, unsigned j)> merge) {
431 
432  // Find and merge duplicate divisions.
433  // TODO: Add division normalization to support divisions that differ by
434  // a constant.
435  // TODO: Add division ordering such that a division representation for local
436  // variable at position `i` only depends on local variables at position <
437  // `i`. This would make sure that all divisions depending on other local
438  // variables that can be merged, are merged.
439  for (unsigned i = 0; i < getNumDivs(); ++i) {
440  // Check if a division representation exists for the `i^th` local var.
441  if (denoms[i] == 0)
442  continue;
443  // Check if a division exists which is a duplicate of the division at `i`.
444  for (unsigned j = i + 1; j < getNumDivs(); ++j) {
445  // Check if a division representation exists for the `j^th` local var.
446  if (denoms[j] == 0)
447  continue;
448  // Check if the denominators match.
449  if (denoms[i] != denoms[j])
450  continue;
451  // Check if the representations are equal.
452  if (dividends.getRow(i) != dividends.getRow(j))
453  continue;
454 
455  // Merge divisions at position `j` into division at position `i`. If
456  // merge fails, do not merge these divs.
457  bool mergeResult = merge(i, j);
458  if (!mergeResult)
459  continue;
460 
461  // Update division information to reflect merging.
462  unsigned divOffset = getDivOffset();
463  dividends.addToColumn(divOffset + j, divOffset + i, /*scale=*/1);
464  dividends.removeColumn(divOffset + j);
465  dividends.removeRow(j);
466  denoms.erase(denoms.begin() + j);
467 
468  // Since `j` can never be zero, we do not need to worry about overflows.
469  --j;
470  }
471  }
472 }
473 
474 void DivisionRepr::insertDiv(unsigned pos, ArrayRef<MPInt> dividend,
475  const MPInt &divisor) {
476  assert(pos <= getNumDivs() && "Invalid insertion position");
477  assert(dividend.size() == getNumVars() + 1 && "Incorrect dividend size");
478 
479  dividends.appendExtraRow(dividend);
480  denoms.insert(denoms.begin() + pos, divisor);
481  dividends.insertColumn(getDivOffset() + pos);
482 }
483 
484 void DivisionRepr::insertDiv(unsigned pos, unsigned num) {
485  assert(pos <= getNumDivs() && "Invalid insertion position");
486  dividends.insertColumns(getDivOffset() + pos, num);
487  dividends.insertRows(pos, num);
488  denoms.insert(denoms.begin() + pos, num, MPInt(0));
489 }
490 
491 void DivisionRepr::print(raw_ostream &os) const {
492  os << "Dividends:\n";
493  dividends.print(os);
494  os << "Denominators\n";
495  for (unsigned i = 0, e = denoms.size(); i < e; ++i)
496  os << denoms[i] << " ";
497  os << "\n";
498 }
499 
500 void DivisionRepr::dump() const { print(llvm::errs()); }
501 
503  SmallVector<MPInt, 8> result(range.size());
504  std::transform(range.begin(), range.end(), result.begin(), mpintFromInt64);
505  return result;
506 }
507 
509  SmallVector<int64_t, 8> result(range.size());
510  std::transform(range.begin(), range.end(), result.begin(), int64FromMPInt);
511  return result;
512 }
static void normalizeDivisionByGCD(MutableArrayRef< MPInt > dividend, MPInt &divisor)
Normalize a division's dividend and the divisor by their GCD.
Definition: Utils.cpp:29
static bool checkExplicitRepresentation(const IntegerRelation &cst, ArrayRef< bool > foundRepr, ArrayRef< MPInt > dividend, unsigned pos)
Definition: Utils.cpp:191
static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos, unsigned ubIneq, unsigned lbIneq, MutableArrayRef< MPInt > expr, MPInt &divisor)
Check if the pos^th variable can be represented as a division using upper bound inequality at positio...
Definition: Utils.cpp:95
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:429
SmallVector< Optional< MPInt >, 4 > divValuesAt(ArrayRef< MPInt > point) const
Definition: Utils.cpp:381
MPInt & getDenom(unsigned i)
Definition: Utils.h:148
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:491
unsigned getNumDivs() const
Definition: Utils.h:125
void insertDiv(unsigned pos, ArrayRef< MPInt > dividend, const MPInt &divisor)
Definition: Utils.cpp:474
void setDiv(unsigned i, ArrayRef< MPInt > dividend, const MPInt &divisor)
Definition: Utils.h:153
MutableArrayRef< MPInt > getDividend(unsigned i)
Definition: Utils.h:139
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
MPInt atEq(unsigned i, unsigned j) const
Returns the value at the specified equality row and column.
virtual unsigned insertVar(VarKind kind, unsigned pos, unsigned num=1)
Insert num variables of the specified kind at position pos.
MPInt atIneq(unsigned i, unsigned j) const
Returns the value at the specified inequality row and column.
unsigned getNumCols() const
Returns the number of columns in the constraint system.
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 ...
DivisionRepr getLocalReprs(std::vector< MaybeLocalRepr > *repr=nullptr) const
Returns a DivisonRepr representing the division representation of local variables in the constraint s...
const PresburgerSpace & getSpace() const
Returns a reference to the underlying space.
This class provides support for multi-precision arithmetic.
Definition: MPInt.h:87
void insertRows(unsigned pos, unsigned count)
Insert rows having positions pos, pos + 1, ...
Definition: Matrix.cpp:159
void removeColumn(unsigned pos)
Definition: Matrix.cpp:144
unsigned appendExtraRow()
Add an extra row at the bottom of the matrix and return its position.
Definition: Matrix.cpp:39
void print(raw_ostream &os) const
Print the matrix.
Definition: Matrix.cpp:355
void insertColumn(unsigned pos)
Definition: Matrix.cpp:102
void insertColumns(unsigned pos, unsigned count)
Insert columns having positions pos, pos + 1, ...
Definition: Matrix.cpp:103
void removeRow(unsigned pos)
Definition: Matrix.cpp:172
void addToColumn(unsigned sourceColumn, unsigned targetColumn, const MPInt &scale)
Add scale multiples of the source column to the target column.
Definition: Matrix.cpp:207
MutableArrayRef< MPInt > getRow(unsigned row)
Get a [Mutable]ArrayRef corresponding to the specified row.
Definition: Matrix.cpp:87
bool isCompatible(const PresburgerSpace &other) const
Returns true if both the spaces are compatible i.e.
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt gcd(const MPInt &a, const MPInt &b)
Definition: MPInt.h:399
SmallVector< MPInt, 8 > getDivLowerBound(ArrayRef< MPInt > dividend, const MPInt &divisor, unsigned localVarIdx)
Definition: Utils.cpp:322
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:311
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 ...
Definition: Utils.cpp:285
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt abs(const MPInt &x)
Definition: MPInt.h:370
static int64_t int64FromMPInt(const MPInt &x)
This just calls through to the operator int64_t, but it's useful when a function pointer is required.
Definition: MPInt.h:261
MPInt gcdRange(ArrayRef< MPInt > range)
Compute the gcd of the range.
Definition: Utils.cpp:336
void normalizeDiv(MutableArrayRef< MPInt > num, MPInt &denom)
Normalize the given (numerator, denominator) pair by dividing out the common factors between them.
Definition: Utils.cpp:355
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt mpintFromInt64(int64_t x)
Definition: MPInt.h:262
MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst, ArrayRef< bool > foundRepr, unsigned pos, MutableArrayRef< MPInt > dividend, MPInt &divisor)
Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed...
Definition: Utils.cpp:222
SmallVector< MPInt, 8 > getMPIntVec(ArrayRef< int64_t > range)
Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables ...
Definition: Utils.cpp:502
SmallVector< MPInt, 8 > getNegatedCoeffs(ArrayRef< MPInt > coeffs)
Return coeffs with all the elements negated.
Definition: Utils.cpp:363
MPInt normalizeRange(MutableArrayRef< MPInt > range)
Divide the range by its gcd and return the gcd.
Definition: Utils.cpp:346
SmallVector< int64_t, 8 > getInt64Vec(ArrayRef< MPInt > range)
Return the given array as an array of int64_t.
Definition: Utils.cpp:508
llvm::SmallBitVector getSubrangeBitVector(unsigned len, unsigned setOffset, unsigned numSet)
Definition: Utils.cpp:277
SmallVector< MPInt, 8 > getComplementIneq(ArrayRef< MPInt > ineq)
Return the complement of the given inequality.
Definition: Utils.cpp:371
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt floorDiv(const MPInt &lhs, const MPInt &rhs)
Definition: MPInt.h:382
Include the generated interface declarations.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:72
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
MaybeLocalRepr contains the indices of the constraints that can be expressed as a floordiv of an affi...
Definition: Utils.h:97
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.