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