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