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
13#include "mlir/Analysis/Presburger/Utils.h"
14#include "mlir/Analysis/Presburger/IntegerRelation.h"
15#include "mlir/Analysis/Presburger/PresburgerSpace.h"
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
24using namespace mlir;
25using namespace presburger;
26using 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.
32static void normalizeDivisionByGCD(MutableArrayRef<DynamicAPInt> dividend,
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(A: abs(X: dividend.front()), B: 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(A: abs(X: dividend[i]), B: gcd);
50 if (gcd == 1)
51 return;
52 }
53
54 // Normalize the dividend and the denominator.
55 std::transform(first: dividend.begin(), last: dividend.end(), result: dividend.begin(),
56 unary_op: [gcd](DynamicAPInt &n) { return floorDiv(LHS: n, RHS: 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.
98static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
99 unsigned ubIneq, unsigned lbIneq,
100 MutableArrayRef<DynamicAPInt> expr,
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(i: lbIneq, j: 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(i: ubIneq, j: i) != -cst.atIneq(i: lbIneq, j: 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(i: lbIneq, j: cst.getNumCols() - 1) +
129 cst.atIneq(i: ubIneq, j: 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(i: ubIneq, j: 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(i: ubIneq, j: cst.getNumCols() - 1) + c;
148 normalizeDivisionByGCD(dividend: 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.
164static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
165 unsigned eqInd,
166 MutableArrayRef<DynamicAPInt> expr,
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(i: eqInd, j: 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(i: eqInd, j: i);
187
188 expr.back() = -signDiv * cst.atEq(i: eqInd, j: cst.getNumCols() - 1);
189 normalizeDivisionByGCD(dividend: 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`.
196static bool checkExplicitRepresentation(const IntegerRelation &cst,
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.
227MaybeLocalRepr presburger::computeSingleVarRepr(
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: &lbIndices, ubIndices: &ubIndices, eqIndices: &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, ubIneq: ubPos, lbIneq: lbPos, expr: 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 = {.lowerBoundIdx: ubPos, .upperBoundIdx: lbPos};
250 return repr;
251 }
252 }
253 for (unsigned eqPos : eqIndices) {
254 // Attempt to get divison representation from eqPos.
255 if (getDivRepr(cst, pos, eqInd: eqPos, expr: 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
268MaybeLocalRepr presburger::computeSingleVarRepr(
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;
273 MaybeLocalRepr result = computeSingleVarRepr(
274 cst, foundRepr, pos, dividend: dividendDynamicAPInt, divisor&: divisorDynamicAPInt);
275 dividend = getInt64Vec(range: dividendDynamicAPInt);
276 divisor = unsigned(int64_t(divisorDynamicAPInt));
277 return result;
278}
279
280llvm::SmallBitVector presburger::getSubrangeBitVector(unsigned len,
281 unsigned setOffset,
282 unsigned numSet) {
283 llvm::SmallBitVector vec(len, false);
284 vec.set(I: setOffset, E: setOffset + numSet);
285 return vec;
286}
287
288void presburger::mergeLocalVars(
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();
298 relA.insertVar(kind: VarKind::Local, pos: relA.getNumLocalVars(),
299 num: relB.getNumLocalVars());
300 relB.insertVar(kind: VarKind::Local, pos: 0, num: 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, dividend: divsB.getDividend(i), divisor: 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
314SmallVector<DynamicAPInt, 8>
315presburger::getDivUpperBound(ArrayRef<DynamicAPInt> dividend,
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
326SmallVector<DynamicAPInt, 8>
327presburger::getDivLowerBound(ArrayRef<DynamicAPInt> dividend,
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(first: dividend.begin(), last: dividend.end(), result: ineq.begin(),
335 unary_op: std::negate<DynamicAPInt>());
336 ineq[localVarIdx] = divisor;
337 ineq.back() += divisor - 1;
338 return ineq;
339}
340
341DynamicAPInt presburger::gcdRange(ArrayRef<DynamicAPInt> range) {
342 DynamicAPInt gcd(0);
343 for (const DynamicAPInt &elem : range) {
344 gcd = llvm::gcd(A: gcd, B: abs(X: elem));
345 if (gcd == 1)
346 return gcd;
347 }
348 return gcd;
349}
350
351DynamicAPInt presburger::normalizeRange(MutableArrayRef<DynamicAPInt> range) {
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
360void presburger::normalizeDiv(MutableArrayRef<DynamicAPInt> num,
361 DynamicAPInt &denom) {
362 assert(denom > 0 && "denom must be positive!");
363 DynamicAPInt gcd = llvm::gcd(A: gcdRange(range: num), B: denom);
364 if (gcd == 1)
365 return;
366 for (DynamicAPInt &coeff : num)
367 coeff /= gcd;
368 denom /= gcd;
369}
370
371SmallVector<DynamicAPInt, 8>
372presburger::getNegatedCoeffs(ArrayRef<DynamicAPInt> coeffs) {
373 SmallVector<DynamicAPInt, 8> negatedCoeffs;
374 negatedCoeffs.reserve(N: coeffs.size());
375 for (const DynamicAPInt &coeff : coeffs)
376 negatedCoeffs.emplace_back(Args: -coeff);
377 return negatedCoeffs;
378}
379
380SmallVector<DynamicAPInt, 8>
381presburger::getComplementIneq(ArrayRef<DynamicAPInt> ineq) {
382 SmallVector<DynamicAPInt, 8> coeffs;
383 coeffs.reserve(N: ineq.size());
384 for (const DynamicAPInt &coeff : ineq)
385 coeffs.emplace_back(Args: -coeff);
386 --coeffs.back();
387 return coeffs;
388}
389
390SmallVector<std::optional<DynamicAPInt>, 4>
391DivisionRepr::divValuesAt(ArrayRef<DynamicAPInt> point) const {
392 assert(point.size() == getNumNonDivs() && "Incorrect point size");
393
394 SmallVector<std::optional<DynamicAPInt>, 4> divValues(getNumDivs(),
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(first1: point.begin(), last1: point.end(), first2: dividend.begin(),
425 init: divVal);
426 // Add constant.
427 divVal += dividend.back();
428 // Take floor division with denominator.
429 divVal = floorDiv(LHS: divVal, RHS: denoms[i]);
430
431 // Set div value and continue.
432 divValues[i] = divVal;
433 changed = true;
434 }
435 }
436
437 return divValues;
438}
439
440void DivisionRepr::removeDuplicateDivs(
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(row: i) != dividends.getRow(row: 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(sourceColumn: divOffset + j, targetColumn: divOffset + i, /*scale=*/1);
476 dividends.removeColumn(pos: divOffset + j);
477 dividends.removeRow(pos: j);
478 denoms.erase(CI: 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
486void DivisionRepr::normalizeDivs() {
487 for (unsigned i = 0, e = getNumDivs(); i < e; ++i) {
488 if (getDenom(i) == 0 || getDividend(i).empty())
489 continue;
490 normalizeDiv(num: getDividend(i), denom&: getDenom(i));
491 }
492}
493
494void DivisionRepr::insertDiv(unsigned pos, ArrayRef<DynamicAPInt> dividend,
495 const DynamicAPInt &divisor) {
496 assert(pos <= getNumDivs() && "Invalid insertion position");
497 assert(dividend.size() == getNumVars() + 1 && "Incorrect dividend size");
498
499 dividends.appendExtraRow(elems: dividend);
500 denoms.insert(I: denoms.begin() + pos, Elt: divisor);
501 dividends.insertColumn(pos: getDivOffset() + pos);
502}
503
504void DivisionRepr::insertDiv(unsigned pos, unsigned num) {
505 assert(pos <= getNumDivs() && "Invalid insertion position");
506 dividends.insertColumns(pos: getDivOffset() + pos, count: num);
507 dividends.insertRows(pos, count: num);
508 denoms.insert(I: denoms.begin() + pos, NumToInsert: num, Elt: DynamicAPInt(0));
509}
510
511void 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
520void DivisionRepr::dump() const { print(os&: llvm::errs()); }
521
522SmallVector<DynamicAPInt, 8>
523presburger::getDynamicAPIntVec(ArrayRef<int64_t> range) {
524 SmallVector<DynamicAPInt, 8> result(range.size());
525 std::transform(first: range.begin(), last: range.end(), result: result.begin(),
526 unary_op: dynamicAPIntFromInt64);
527 return result;
528}
529
530SmallVector<int64_t, 8> presburger::getInt64Vec(ArrayRef<DynamicAPInt> range) {
531 SmallVector<int64_t, 8> result(range.size());
532 std::transform(first: range.begin(), last: range.end(), result: result.begin(),
533 unary_op: int64fromDynamicAPInt);
534 return result;
535}
536
537Fraction presburger::dotProduct(ArrayRef<Fraction> a, ArrayRef<Fraction> b) {
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.
548std::vector<Fraction> presburger::multiplyPolynomials(ArrayRef<Fraction> a,
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(n: 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(args&: sum);
568 }
569 return convolution;
570}
571
572bool presburger::isRangeZero(ArrayRef<Fraction> arr) {
573 return llvm::all_of(Range&: arr, P: [](const Fraction &f) { return f == 0; });
574}
575

source code of mlir/lib/Analysis/Presburger/Utils.cpp