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