1//===- IntegerRelation.cpp - MLIR IntegerRelation Class ---------------===//
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// A class to represent an relation over integer tuples. A relation is
10// represented as a constraint system over a space of tuples of integer valued
11// variables supporting symbolic variables and existential quantification.
12//
13//===----------------------------------------------------------------------===//
14
15#include "mlir/Analysis/Presburger/IntegerRelation.h"
16#include "mlir/Analysis/Presburger/Fraction.h"
17#include "mlir/Analysis/Presburger/LinearTransform.h"
18#include "mlir/Analysis/Presburger/PWMAFunction.h"
19#include "mlir/Analysis/Presburger/PresburgerRelation.h"
20#include "mlir/Analysis/Presburger/PresburgerSpace.h"
21#include "mlir/Analysis/Presburger/Simplex.h"
22#include "mlir/Analysis/Presburger/Utils.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/DenseSet.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/ADT/Sequence.h"
27#include "llvm/ADT/SmallBitVector.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/DebugLog.h"
30#include "llvm/Support/raw_ostream.h"
31#include <algorithm>
32#include <cassert>
33#include <functional>
34#include <memory>
35#include <optional>
36#include <utility>
37#include <vector>
38
39#define DEBUG_TYPE "presburger"
40
41using namespace mlir;
42using namespace presburger;
43
44using llvm::SmallDenseMap;
45
46std::unique_ptr<IntegerRelation> IntegerRelation::clone() const {
47 return std::make_unique<IntegerRelation>(args: *this);
48}
49
50std::unique_ptr<IntegerPolyhedron> IntegerPolyhedron::clone() const {
51 return std::make_unique<IntegerPolyhedron>(args: *this);
52}
53
54void IntegerRelation::setSpace(const PresburgerSpace &oSpace) {
55 assert(space.getNumVars() == oSpace.getNumVars() && "invalid space!");
56 space = oSpace;
57}
58
59void IntegerRelation::setSpaceExceptLocals(const PresburgerSpace &oSpace) {
60 assert(oSpace.getNumLocalVars() == 0 && "no locals should be present!");
61 assert(oSpace.getNumVars() <= getNumVars() && "invalid space!");
62 unsigned newNumLocals = getNumVars() - oSpace.getNumVars();
63 space = oSpace;
64 space.insertVar(kind: VarKind::Local, pos: 0, num: newNumLocals);
65}
66
67void IntegerRelation::setId(VarKind kind, unsigned i, Identifier id) {
68 assert(space.isUsingIds() &&
69 "space must be using identifiers to set an identifier");
70 assert(kind != VarKind::Local && "local variables cannot have identifiers");
71 assert(i < space.getNumVarKind(kind) && "invalid variable index");
72 space.setId(kind, pos: i, id);
73}
74
75ArrayRef<Identifier> IntegerRelation::getIds(VarKind kind) {
76 if (!space.isUsingIds())
77 space.resetIds();
78 return space.getIds(kind);
79}
80
81void IntegerRelation::append(const IntegerRelation &other) {
82 assert(space.isEqual(other.getSpace()) && "Spaces must be equal.");
83
84 inequalities.reserveRows(rows: inequalities.getNumRows() +
85 other.getNumInequalities());
86 equalities.reserveRows(rows: equalities.getNumRows() + other.getNumEqualities());
87
88 for (unsigned r = 0, e = other.getNumInequalities(); r < e; r++) {
89 addInequality(inEq: other.getInequality(idx: r));
90 }
91 for (unsigned r = 0, e = other.getNumEqualities(); r < e; r++) {
92 addEquality(eq: other.getEquality(idx: r));
93 }
94}
95
96IntegerRelation IntegerRelation::intersect(IntegerRelation other) const {
97 IntegerRelation result = *this;
98 result.mergeLocalVars(other);
99 result.append(other);
100 return result;
101}
102
103bool IntegerRelation::isEqual(const IntegerRelation &other) const {
104 assert(space.isCompatible(other.getSpace()) && "Spaces must be compatible.");
105 return PresburgerRelation(*this).isEqual(set: PresburgerRelation(other));
106}
107
108bool IntegerRelation::isObviouslyEqual(const IntegerRelation &other) const {
109 if (!space.isEqual(other: other.getSpace()))
110 return false;
111 if (getNumEqualities() != other.getNumEqualities())
112 return false;
113 if (getNumInequalities() != other.getNumInequalities())
114 return false;
115
116 unsigned cols = getNumCols();
117 for (unsigned i = 0, eqs = getNumEqualities(); i < eqs; ++i) {
118 for (unsigned j = 0; j < cols; ++j) {
119 if (atEq(i, j) != other.atEq(i, j))
120 return false;
121 }
122 }
123 for (unsigned i = 0, ineqs = getNumInequalities(); i < ineqs; ++i) {
124 for (unsigned j = 0; j < cols; ++j) {
125 if (atIneq(i, j) != other.atIneq(i, j))
126 return false;
127 }
128 }
129 return true;
130}
131
132bool IntegerRelation::isSubsetOf(const IntegerRelation &other) const {
133 assert(space.isCompatible(other.getSpace()) && "Spaces must be compatible.");
134 return PresburgerRelation(*this).isSubsetOf(set: PresburgerRelation(other));
135}
136
137MaybeOptimum<SmallVector<Fraction, 8>>
138IntegerRelation::findRationalLexMin() const {
139 assert(getNumSymbolVars() == 0 && "Symbols are not supported!");
140 MaybeOptimum<SmallVector<Fraction, 8>> maybeLexMin =
141 LexSimplex(*this).findRationalLexMin();
142
143 if (!maybeLexMin.isBounded())
144 return maybeLexMin;
145
146 // The Simplex returns the lexmin over all the variables including locals. But
147 // locals are not actually part of the space and should not be returned in the
148 // result. Since the locals are placed last in the list of variables, they
149 // will be minimized last in the lexmin. So simply truncating out the locals
150 // from the end of the answer gives the desired lexmin over the dimensions.
151 assert(maybeLexMin->size() == getNumVars() &&
152 "Incorrect number of vars in lexMin!");
153 maybeLexMin->resize(N: getNumDimAndSymbolVars());
154 return maybeLexMin;
155}
156
157MaybeOptimum<SmallVector<DynamicAPInt, 8>>
158IntegerRelation::findIntegerLexMin() const {
159 assert(getNumSymbolVars() == 0 && "Symbols are not supported!");
160 MaybeOptimum<SmallVector<DynamicAPInt, 8>> maybeLexMin =
161 LexSimplex(*this).findIntegerLexMin();
162
163 if (!maybeLexMin.isBounded())
164 return maybeLexMin.getKind();
165
166 // The Simplex returns the lexmin over all the variables including locals. But
167 // locals are not actually part of the space and should not be returned in the
168 // result. Since the locals are placed last in the list of variables, they
169 // will be minimized last in the lexmin. So simply truncating out the locals
170 // from the end of the answer gives the desired lexmin over the dimensions.
171 assert(maybeLexMin->size() == getNumVars() &&
172 "Incorrect number of vars in lexMin!");
173 maybeLexMin->resize(N: getNumDimAndSymbolVars());
174 return maybeLexMin;
175}
176
177static bool rangeIsZero(ArrayRef<DynamicAPInt> range) {
178 return llvm::all_of(Range&: range, P: [](const DynamicAPInt &x) { return x == 0; });
179}
180
181static void removeConstraintsInvolvingVarRange(IntegerRelation &poly,
182 unsigned begin, unsigned count) {
183 // We loop until i > 0 and index into i - 1 to avoid sign issues.
184 //
185 // We iterate backwards so that whether we remove constraint i - 1 or not, the
186 // next constraint to be tested is always i - 2.
187 for (unsigned i = poly.getNumEqualities(); i > 0; i--)
188 if (!rangeIsZero(range: poly.getEquality(idx: i - 1).slice(N: begin, M: count)))
189 poly.removeEquality(pos: i - 1);
190 for (unsigned i = poly.getNumInequalities(); i > 0; i--)
191 if (!rangeIsZero(range: poly.getInequality(idx: i - 1).slice(N: begin, M: count)))
192 poly.removeInequality(pos: i - 1);
193}
194
195IntegerRelation::CountsSnapshot IntegerRelation::getCounts() const {
196 return {getSpace(), getNumInequalities(), getNumEqualities()};
197}
198
199void IntegerRelation::truncateVarKind(VarKind kind, unsigned num) {
200 unsigned curNum = getNumVarKind(kind);
201 assert(num <= curNum && "Can't truncate to more vars!");
202 removeVarRange(kind, varStart: num, varLimit: curNum);
203}
204
205void IntegerRelation::truncateVarKind(VarKind kind,
206 const CountsSnapshot &counts) {
207 truncateVarKind(kind, num: counts.getSpace().getNumVarKind(kind));
208}
209
210void IntegerRelation::truncate(const CountsSnapshot &counts) {
211 truncateVarKind(kind: VarKind::Domain, counts);
212 truncateVarKind(kind: VarKind::Range, counts);
213 truncateVarKind(kind: VarKind::Symbol, counts);
214 truncateVarKind(kind: VarKind::Local, counts);
215 removeInequalityRange(start: counts.getNumIneqs(), end: getNumInequalities());
216 removeEqualityRange(start: counts.getNumEqs(), end: getNumEqualities());
217}
218
219PresburgerRelation IntegerRelation::computeReprWithOnlyDivLocals() const {
220 // If there are no locals, we're done.
221 if (getNumLocalVars() == 0)
222 return PresburgerRelation(*this);
223
224 // Move all the non-div locals to the end, as the current API to
225 // SymbolicLexOpt requires these to form a contiguous range.
226 //
227 // Take a copy so we can perform mutations.
228 IntegerRelation copy = *this;
229 std::vector<MaybeLocalRepr> reprs(getNumLocalVars());
230 copy.getLocalReprs(repr: &reprs);
231
232 // Iterate through all the locals. The last `numNonDivLocals` are the locals
233 // that have been scanned already and do not have division representations.
234 unsigned numNonDivLocals = 0;
235 unsigned offset = copy.getVarKindOffset(kind: VarKind::Local);
236 for (unsigned i = 0, e = copy.getNumLocalVars(); i < e - numNonDivLocals;) {
237 if (!reprs[i]) {
238 // Whenever we come across a local that does not have a division
239 // representation, we swap it to the `numNonDivLocals`-th last position
240 // and increment `numNonDivLocal`s. `reprs` also needs to be swapped.
241 copy.swapVar(posA: offset + i, posB: offset + e - numNonDivLocals - 1);
242 std::swap(a&: reprs[i], b&: reprs[e - numNonDivLocals - 1]);
243 ++numNonDivLocals;
244 continue;
245 }
246 ++i;
247 }
248
249 // If there are no non-div locals, we're done.
250 if (numNonDivLocals == 0)
251 return PresburgerRelation(*this);
252
253 // We computeSymbolicIntegerLexMin by considering the non-div locals as
254 // "non-symbols" and considering everything else as "symbols". This will
255 // compute a function mapping assignments to "symbols" to the
256 // lexicographically minimal valid assignment of "non-symbols", when a
257 // satisfying assignment exists. It separately returns the set of assignments
258 // to the "symbols" such that a satisfying assignment to the "non-symbols"
259 // exists but the lexmin is unbounded. We basically want to find the set of
260 // values of the "symbols" such that an assignment to the "non-symbols"
261 // exists, which is the union of the domain of the returned lexmin function
262 // and the returned set of assignments to the "symbols" that makes the lexmin
263 // unbounded.
264 SymbolicLexOpt lexminResult =
265 SymbolicLexSimplex(copy, /*symbolOffset*/ 0,
266 IntegerPolyhedron(PresburgerSpace::getSetSpace(
267 /*numDims=*/copy.getNumVars() - numNonDivLocals)))
268 .computeSymbolicIntegerLexMin();
269 PresburgerRelation result =
270 lexminResult.lexopt.getDomain().unionSet(set: lexminResult.unboundedDomain);
271
272 // The result set might lie in the wrong space -- all its ids are dims.
273 // Set it to the desired space and return.
274 PresburgerSpace space = getSpace();
275 space.removeVarRange(kind: VarKind::Local, varStart: 0, varLimit: getNumLocalVars());
276 result.setSpace(space);
277 return result;
278}
279
280SymbolicLexOpt IntegerRelation::findSymbolicIntegerLexMin() const {
281 // Symbol and Domain vars will be used as symbols for symbolic lexmin.
282 // In other words, for every value of the symbols and domain, return the
283 // lexmin value of the (range, locals).
284 llvm::SmallBitVector isSymbol(getNumVars(), false);
285 isSymbol.set(I: getVarKindOffset(kind: VarKind::Symbol),
286 E: getVarKindEnd(kind: VarKind::Symbol));
287 isSymbol.set(I: getVarKindOffset(kind: VarKind::Domain),
288 E: getVarKindEnd(kind: VarKind::Domain));
289 // Compute the symbolic lexmin of the dims and locals, with the symbols being
290 // the actual symbols of this set.
291 // The resultant space of lexmin is the space of the relation itself.
292 SymbolicLexOpt result =
293 SymbolicLexSimplex(*this,
294 IntegerPolyhedron(PresburgerSpace::getSetSpace(
295 /*numDims=*/getNumDomainVars(),
296 /*numSymbols=*/getNumSymbolVars())),
297 isSymbol)
298 .computeSymbolicIntegerLexMin();
299
300 // We want to return only the lexmin over the dims, so strip the locals from
301 // the computed lexmin.
302 result.lexopt.removeOutputs(start: result.lexopt.getNumOutputs() - getNumLocalVars(),
303 end: result.lexopt.getNumOutputs());
304 return result;
305}
306
307/// findSymbolicIntegerLexMax is implemented using findSymbolicIntegerLexMin as
308/// follows:
309/// 1. A new relation is created which is `this` relation with the sign of
310/// each dimension variable in range flipped;
311/// 2. findSymbolicIntegerLexMin is called on the range negated relation to
312/// compute the negated lexmax of `this` relation;
313/// 3. The sign of the negated lexmax is flipped and returned.
314SymbolicLexOpt IntegerRelation::findSymbolicIntegerLexMax() const {
315 IntegerRelation flippedRel = *this;
316 // Flip range sign by flipping the sign of range variables in all constraints.
317 for (unsigned j = getNumDomainVars(),
318 b = getNumDomainVars() + getNumRangeVars();
319 j < b; j++) {
320 for (unsigned i = 0, a = getNumEqualities(); i < a; i++)
321 flippedRel.atEq(i, j) = -1 * atEq(i, j);
322 for (unsigned i = 0, a = getNumInequalities(); i < a; i++)
323 flippedRel.atIneq(i, j) = -1 * atIneq(i, j);
324 }
325 // Compute negated lexmax by computing lexmin.
326 SymbolicLexOpt flippedSymbolicIntegerLexMax =
327 flippedRel.findSymbolicIntegerLexMin(),
328 symbolicIntegerLexMax(
329 flippedSymbolicIntegerLexMax.lexopt.getSpace());
330 // Get lexmax by flipping range sign in the PWMA constraints.
331 for (auto &flippedPiece :
332 flippedSymbolicIntegerLexMax.lexopt.getAllPieces()) {
333 IntMatrix mat = flippedPiece.output.getOutputMatrix();
334 for (unsigned i = 0, e = mat.getNumRows(); i < e; i++)
335 mat.negateRow(row: i);
336 MultiAffineFunction maf(flippedPiece.output.getSpace(), mat);
337 PWMAFunction::Piece piece = {.domain: flippedPiece.domain, .output: maf};
338 symbolicIntegerLexMax.lexopt.addPiece(piece);
339 }
340 symbolicIntegerLexMax.unboundedDomain =
341 flippedSymbolicIntegerLexMax.unboundedDomain;
342 return symbolicIntegerLexMax;
343}
344
345PresburgerRelation
346IntegerRelation::subtract(const PresburgerRelation &set) const {
347 return PresburgerRelation(*this).subtract(set);
348}
349
350unsigned IntegerRelation::insertVar(VarKind kind, unsigned pos, unsigned num) {
351 assert(pos <= getNumVarKind(kind));
352
353 unsigned insertPos = space.insertVar(kind, pos, num);
354 inequalities.insertColumns(pos: insertPos, count: num);
355 equalities.insertColumns(pos: insertPos, count: num);
356 return insertPos;
357}
358
359unsigned IntegerRelation::appendVar(VarKind kind, unsigned num) {
360 unsigned pos = getNumVarKind(kind);
361 return insertVar(kind, pos, num);
362}
363
364void IntegerRelation::addEquality(ArrayRef<DynamicAPInt> eq) {
365 assert(eq.size() == getNumCols());
366 unsigned row = equalities.appendExtraRow();
367 for (unsigned i = 0, e = eq.size(); i < e; ++i)
368 equalities(row, i) = eq[i];
369}
370
371void IntegerRelation::addInequality(ArrayRef<DynamicAPInt> inEq) {
372 assert(inEq.size() == getNumCols());
373 unsigned row = inequalities.appendExtraRow();
374 for (unsigned i = 0, e = inEq.size(); i < e; ++i)
375 inequalities(row, i) = inEq[i];
376}
377
378void IntegerRelation::removeVar(VarKind kind, unsigned pos) {
379 removeVarRange(kind, varStart: pos, varLimit: pos + 1);
380}
381
382void IntegerRelation::removeVar(unsigned pos) { removeVarRange(varStart: pos, varLimit: pos + 1); }
383
384void IntegerRelation::removeVarRange(VarKind kind, unsigned varStart,
385 unsigned varLimit) {
386 assert(varLimit <= getNumVarKind(kind));
387
388 if (varStart >= varLimit)
389 return;
390
391 // Remove eliminated variables from the constraints.
392 unsigned offset = getVarKindOffset(kind);
393 equalities.removeColumns(pos: offset + varStart, count: varLimit - varStart);
394 inequalities.removeColumns(pos: offset + varStart, count: varLimit - varStart);
395
396 // Remove eliminated variables from the space.
397 space.removeVarRange(kind, varStart, varLimit);
398}
399
400void IntegerRelation::removeVarRange(unsigned varStart, unsigned varLimit) {
401 assert(varLimit <= getNumVars());
402
403 if (varStart >= varLimit)
404 return;
405
406 // Helper function to remove vars of the specified kind in the given range
407 // [start, limit), The range is absolute (i.e. it is not relative to the kind
408 // of variable). Also updates `limit` to reflect the deleted variables.
409 auto removeVarKindInRange = [this](VarKind kind, unsigned &start,
410 unsigned &limit) {
411 if (start >= limit)
412 return;
413
414 unsigned offset = getVarKindOffset(kind);
415 unsigned num = getNumVarKind(kind);
416
417 // Get `start`, `limit` relative to the specified kind.
418 unsigned relativeStart =
419 start <= offset ? 0 : std::min(a: num, b: start - offset);
420 unsigned relativeLimit =
421 limit <= offset ? 0 : std::min(a: num, b: limit - offset);
422
423 // Remove vars of the specified kind in the relative range.
424 removeVarRange(kind, varStart: relativeStart, varLimit: relativeLimit);
425
426 // Update `limit` to reflect deleted variables.
427 // `start` does not need to be updated because any variables that are
428 // deleted are after position `start`.
429 limit -= relativeLimit - relativeStart;
430 };
431
432 removeVarKindInRange(VarKind::Domain, varStart, varLimit);
433 removeVarKindInRange(VarKind::Range, varStart, varLimit);
434 removeVarKindInRange(VarKind::Symbol, varStart, varLimit);
435 removeVarKindInRange(VarKind::Local, varStart, varLimit);
436}
437
438void IntegerRelation::removeEquality(unsigned pos) {
439 equalities.removeRow(pos);
440}
441
442void IntegerRelation::removeInequality(unsigned pos) {
443 inequalities.removeRow(pos);
444}
445
446void IntegerRelation::removeConstraint(unsigned pos) {
447 if (pos >= getNumInequalities()) {
448 removeEquality(pos: pos - getNumInequalities());
449 } else {
450 removeInequality(pos);
451 }
452}
453
454void IntegerRelation::removeEqualityRange(unsigned start, unsigned end) {
455 if (start >= end)
456 return;
457 equalities.removeRows(pos: start, count: end - start);
458}
459
460void IntegerRelation::removeInequalityRange(unsigned start, unsigned end) {
461 if (start >= end)
462 return;
463 inequalities.removeRows(pos: start, count: end - start);
464}
465
466void IntegerRelation::swapVar(unsigned posA, unsigned posB) {
467 assert(posA < getNumVars() && "invalid position A");
468 assert(posB < getNumVars() && "invalid position B");
469
470 if (posA == posB)
471 return;
472
473 VarKind kindA = space.getVarKindAt(pos: posA);
474 VarKind kindB = space.getVarKindAt(pos: posB);
475 unsigned relativePosA = posA - getVarKindOffset(kind: kindA);
476 unsigned relativePosB = posB - getVarKindOffset(kind: kindB);
477 space.swapVar(kindA, kindB, posA: relativePosA, posB: relativePosB);
478
479 inequalities.swapColumns(column: posA, otherColumn: posB);
480 equalities.swapColumns(column: posA, otherColumn: posB);
481}
482
483void IntegerRelation::clearConstraints() {
484 equalities.resizeVertically(newNRows: 0);
485 inequalities.resizeVertically(newNRows: 0);
486}
487
488/// Gather all lower and upper bounds of the variable at `pos`, and
489/// optionally any equalities on it. In addition, the bounds are to be
490/// independent of variables in position range [`offset`, `offset` + `num`).
491void IntegerRelation::getLowerAndUpperBoundIndices(
492 unsigned pos, SmallVectorImpl<unsigned> *lbIndices,
493 SmallVectorImpl<unsigned> *ubIndices, SmallVectorImpl<unsigned> *eqIndices,
494 unsigned offset, unsigned num) const {
495 assert(pos < getNumVars() && "invalid position");
496 assert(offset + num < getNumCols() && "invalid range");
497
498 // Checks for a constraint that has a non-zero coeff for the variables in
499 // the position range [offset, offset + num) while ignoring `pos`.
500 auto containsConstraintDependentOnRange = [&](unsigned r, bool isEq) {
501 unsigned c, f;
502 auto cst = isEq ? getEquality(idx: r) : getInequality(idx: r);
503 for (c = offset, f = offset + num; c < f; ++c) {
504 if (c == pos)
505 continue;
506 if (cst[c] != 0)
507 break;
508 }
509 return c < f;
510 };
511
512 // Gather all lower bounds and upper bounds of the variable. Since the
513 // canonical form c_1*x_1 + c_2*x_2 + ... + c_0 >= 0, a constraint is a lower
514 // bound for x_i if c_i >= 1, and an upper bound if c_i <= -1.
515 for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
516 // The bounds are to be independent of [offset, offset + num) columns.
517 if (containsConstraintDependentOnRange(r, /*isEq=*/false))
518 continue;
519 if (atIneq(i: r, j: pos) >= 1) {
520 // Lower bound.
521 lbIndices->emplace_back(Args&: r);
522 } else if (atIneq(i: r, j: pos) <= -1) {
523 // Upper bound.
524 ubIndices->emplace_back(Args&: r);
525 }
526 }
527
528 // An equality is both a lower and upper bound. Record any equalities
529 // involving the pos^th variable.
530 if (!eqIndices)
531 return;
532
533 for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
534 if (atEq(i: r, j: pos) == 0)
535 continue;
536 if (containsConstraintDependentOnRange(r, /*isEq=*/true))
537 continue;
538 eqIndices->emplace_back(Args&: r);
539 }
540}
541
542bool IntegerRelation::hasConsistentState() const {
543 if (!inequalities.hasConsistentState())
544 return false;
545 if (!equalities.hasConsistentState())
546 return false;
547 return true;
548}
549
550void IntegerRelation::setAndEliminate(unsigned pos,
551 ArrayRef<DynamicAPInt> values) {
552 if (values.empty())
553 return;
554 assert(pos + values.size() <= getNumVars() &&
555 "invalid position or too many values");
556 // Setting x_j = p in sum_i a_i x_i + c is equivalent to adding p*a_j to the
557 // constant term and removing the var x_j. We do this for all the vars
558 // pos, pos + 1, ... pos + values.size() - 1.
559 unsigned constantColPos = getNumCols() - 1;
560 for (unsigned i = 0, numVals = values.size(); i < numVals; ++i)
561 inequalities.addToColumn(sourceColumn: i + pos, targetColumn: constantColPos, scale: values[i]);
562 for (unsigned i = 0, numVals = values.size(); i < numVals; ++i)
563 equalities.addToColumn(sourceColumn: i + pos, targetColumn: constantColPos, scale: values[i]);
564 removeVarRange(varStart: pos, varLimit: pos + values.size());
565}
566
567void IntegerRelation::clearAndCopyFrom(const IntegerRelation &other) {
568 *this = other;
569}
570
571std::optional<unsigned>
572IntegerRelation::findConstraintWithNonZeroAt(unsigned colIdx, bool isEq) const {
573 assert(colIdx < getNumCols() && "position out of bounds");
574 auto at = [&](unsigned rowIdx) -> DynamicAPInt {
575 return isEq ? atEq(i: rowIdx, j: colIdx) : atIneq(i: rowIdx, j: colIdx);
576 };
577 unsigned e = isEq ? getNumEqualities() : getNumInequalities();
578 for (unsigned rowIdx = 0; rowIdx < e; ++rowIdx) {
579 if (at(rowIdx) != 0)
580 return rowIdx;
581 }
582 return std::nullopt;
583}
584
585void IntegerRelation::normalizeConstraintsByGCD() {
586 for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
587 equalities.normalizeRow(row: i);
588 for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
589 inequalities.normalizeRow(row: i);
590}
591
592bool IntegerRelation::hasInvalidConstraint() const {
593 assert(hasConsistentState());
594 auto check = [&](bool isEq) -> bool {
595 unsigned numCols = getNumCols();
596 unsigned numRows = isEq ? getNumEqualities() : getNumInequalities();
597 for (unsigned i = 0, e = numRows; i < e; ++i) {
598 unsigned j;
599 for (j = 0; j < numCols - 1; ++j) {
600 DynamicAPInt v = isEq ? atEq(i, j) : atIneq(i, j);
601 // Skip rows with non-zero variable coefficients.
602 if (v != 0)
603 break;
604 }
605 if (j < numCols - 1) {
606 continue;
607 }
608 // Check validity of constant term at 'numCols - 1' w.r.t 'isEq'.
609 // Example invalid constraints include: '1 == 0' or '-1 >= 0'
610 DynamicAPInt v = isEq ? atEq(i, j: numCols - 1) : atIneq(i, j: numCols - 1);
611 if ((isEq && v != 0) || (!isEq && v < 0)) {
612 return true;
613 }
614 }
615 return false;
616 };
617 if (check(/*isEq=*/true))
618 return true;
619 return check(/*isEq=*/false);
620}
621
622/// Eliminate variable from constraint at `rowIdx` based on coefficient at
623/// pivotRow, pivotCol. Columns in range [elimColStart, pivotCol) will not be
624/// updated as they have already been eliminated.
625static void eliminateFromConstraint(IntegerRelation *constraints,
626 unsigned rowIdx, unsigned pivotRow,
627 unsigned pivotCol, unsigned elimColStart,
628 bool isEq) {
629 // Skip if equality 'rowIdx' if same as 'pivotRow'.
630 if (isEq && rowIdx == pivotRow)
631 return;
632 auto at = [&](unsigned i, unsigned j) -> DynamicAPInt {
633 return isEq ? constraints->atEq(i, j) : constraints->atIneq(i, j);
634 };
635 DynamicAPInt leadCoeff = at(rowIdx, pivotCol);
636 // Skip if leading coefficient at 'rowIdx' is already zero.
637 if (leadCoeff == 0)
638 return;
639 DynamicAPInt pivotCoeff = constraints->atEq(i: pivotRow, j: pivotCol);
640 int sign = (leadCoeff * pivotCoeff > 0) ? -1 : 1;
641 DynamicAPInt lcm = llvm::lcm(A: pivotCoeff, B: leadCoeff);
642 DynamicAPInt pivotMultiplier = sign * (lcm / abs(X: pivotCoeff));
643 DynamicAPInt rowMultiplier = lcm / abs(X: leadCoeff);
644
645 unsigned numCols = constraints->getNumCols();
646 for (unsigned j = 0; j < numCols; ++j) {
647 // Skip updating column 'j' if it was just eliminated.
648 if (j >= elimColStart && j < pivotCol)
649 continue;
650 DynamicAPInt v = pivotMultiplier * constraints->atEq(i: pivotRow, j) +
651 rowMultiplier * at(rowIdx, j);
652 isEq ? constraints->atEq(i: rowIdx, j) = v
653 : constraints->atIneq(i: rowIdx, j) = v;
654 }
655}
656
657/// Returns the position of the variable that has the minimum <number of lower
658/// bounds> times <number of upper bounds> from the specified range of
659/// variables [start, end). It is often best to eliminate in the increasing
660/// order of these counts when doing Fourier-Motzkin elimination since FM adds
661/// that many new constraints.
662static unsigned getBestVarToEliminate(const IntegerRelation &cst,
663 unsigned start, unsigned end) {
664 assert(start < cst.getNumVars() && end < cst.getNumVars() + 1);
665
666 auto getProductOfNumLowerUpperBounds = [&](unsigned pos) {
667 unsigned numLb = 0;
668 unsigned numUb = 0;
669 for (unsigned r = 0, e = cst.getNumInequalities(); r < e; r++) {
670 if (cst.atIneq(i: r, j: pos) > 0) {
671 ++numLb;
672 } else if (cst.atIneq(i: r, j: pos) < 0) {
673 ++numUb;
674 }
675 }
676 return numLb * numUb;
677 };
678
679 unsigned minLoc = start;
680 unsigned min = getProductOfNumLowerUpperBounds(start);
681 for (unsigned c = start + 1; c < end; c++) {
682 unsigned numLbUbProduct = getProductOfNumLowerUpperBounds(c);
683 if (numLbUbProduct < min) {
684 min = numLbUbProduct;
685 minLoc = c;
686 }
687 }
688 return minLoc;
689}
690
691// Checks for emptiness of the set by eliminating variables successively and
692// using the GCD test (on all equality constraints) and checking for trivially
693// invalid constraints. Returns 'true' if the constraint system is found to be
694// empty; false otherwise.
695bool IntegerRelation::isEmpty() const {
696 if (isEmptyByGCDTest() || hasInvalidConstraint())
697 return true;
698
699 IntegerRelation tmpCst(*this);
700
701 // First, eliminate as many local variables as possible using equalities.
702 tmpCst.removeRedundantLocalVars();
703 if (tmpCst.isEmptyByGCDTest() || tmpCst.hasInvalidConstraint())
704 return true;
705
706 // Eliminate as many variables as possible using Gaussian elimination.
707 unsigned currentPos = 0;
708 while (currentPos < tmpCst.getNumVars()) {
709 tmpCst.gaussianEliminateVars(posStart: currentPos, posLimit: tmpCst.getNumVars());
710 ++currentPos;
711 // We check emptiness through trivial checks after eliminating each ID to
712 // detect emptiness early. Since the checks isEmptyByGCDTest() and
713 // hasInvalidConstraint() are linear time and single sweep on the constraint
714 // buffer, this appears reasonable - but can optimize in the future.
715 if (tmpCst.hasInvalidConstraint() || tmpCst.isEmptyByGCDTest())
716 return true;
717 }
718
719 // Eliminate the remaining using FM.
720 for (unsigned i = 0, e = tmpCst.getNumVars(); i < e; i++) {
721 tmpCst.fourierMotzkinEliminate(
722 pos: getBestVarToEliminate(cst: tmpCst, start: 0, end: tmpCst.getNumVars()));
723 // Check for a constraint explosion. This rarely happens in practice, but
724 // this check exists as a safeguard against improperly constructed
725 // constraint systems or artificially created arbitrarily complex systems
726 // that aren't the intended use case for IntegerRelation. This is
727 // needed since FM has a worst case exponential complexity in theory.
728 if (tmpCst.getNumConstraints() >= kExplosionFactor * getNumVars()) {
729 LDBG() << "FM constraint explosion detected";
730 return false;
731 }
732
733 // FM wouldn't have modified the equalities in any way. So no need to again
734 // run GCD test. Check for trivial invalid constraints.
735 if (tmpCst.hasInvalidConstraint())
736 return true;
737 }
738 return false;
739}
740
741bool IntegerRelation::isObviouslyEmpty() const {
742 return isEmptyByGCDTest() || hasInvalidConstraint();
743}
744
745// Runs the GCD test on all equality constraints. Returns 'true' if this test
746// fails on any equality. Returns 'false' otherwise.
747// This test can be used to disprove the existence of a solution. If it returns
748// true, no integer solution to the equality constraints can exist.
749//
750// GCD test definition:
751//
752// The equality constraint:
753//
754// c_1*x_1 + c_2*x_2 + ... + c_n*x_n = c_0
755//
756// has an integer solution iff:
757//
758// GCD of c_1, c_2, ..., c_n divides c_0.
759bool IntegerRelation::isEmptyByGCDTest() const {
760 assert(hasConsistentState());
761 unsigned numCols = getNumCols();
762 for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
763 DynamicAPInt gcd = abs(X: atEq(i, j: 0));
764 for (unsigned j = 1; j < numCols - 1; ++j) {
765 gcd = llvm::gcd(A: gcd, B: abs(X: atEq(i, j)));
766 }
767 DynamicAPInt v = abs(X: atEq(i, j: numCols - 1));
768 if (gcd > 0 && (v % gcd != 0)) {
769 return true;
770 }
771 }
772 return false;
773}
774
775// Returns a matrix where each row is a vector along which the polytope is
776// bounded. The span of the returned vectors is guaranteed to contain all
777// such vectors. The returned vectors are NOT guaranteed to be linearly
778// independent. This function should not be called on empty sets.
779//
780// It is sufficient to check the perpendiculars of the constraints, as the set
781// of perpendiculars which are bounded must span all bounded directions.
782IntMatrix IntegerRelation::getBoundedDirections() const {
783 // Note that it is necessary to add the equalities too (which the constructor
784 // does) even though we don't need to check if they are bounded; whether an
785 // inequality is bounded or not depends on what other constraints, including
786 // equalities, are present.
787 Simplex simplex(*this);
788
789 assert(!simplex.isEmpty() && "It is not meaningful to ask whether a "
790 "direction is bounded in an empty set.");
791
792 SmallVector<unsigned, 8> boundedIneqs;
793 // The constructor adds the inequalities to the simplex first, so this
794 // processes all the inequalities.
795 for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
796 if (simplex.isBoundedAlongConstraint(constraintIndex: i))
797 boundedIneqs.emplace_back(Args&: i);
798 }
799
800 // The direction vector is given by the coefficients and does not include the
801 // constant term, so the matrix has one fewer column.
802 unsigned dirsNumCols = getNumCols() - 1;
803 IntMatrix dirs(boundedIneqs.size() + getNumEqualities(), dirsNumCols);
804
805 // Copy the bounded inequalities.
806 unsigned row = 0;
807 for (unsigned i : boundedIneqs) {
808 for (unsigned col = 0; col < dirsNumCols; ++col)
809 dirs(row, col) = atIneq(i, j: col);
810 ++row;
811 }
812
813 // Copy the equalities. All the equalities' perpendiculars are bounded.
814 for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
815 for (unsigned col = 0; col < dirsNumCols; ++col)
816 dirs(row, col) = atEq(i, j: col);
817 ++row;
818 }
819
820 return dirs;
821}
822
823bool IntegerRelation::isIntegerEmpty() const { return !findIntegerSample(); }
824
825/// Let this set be S. If S is bounded then we directly call into the GBR
826/// sampling algorithm. Otherwise, there are some unbounded directions, i.e.,
827/// vectors v such that S extends to infinity along v or -v. In this case we
828/// use an algorithm described in the integer set library (isl) manual and used
829/// by the isl_set_sample function in that library. The algorithm is:
830///
831/// 1) Apply a unimodular transform T to S to obtain S*T, such that all
832/// dimensions in which S*T is bounded lie in the linear span of a prefix of the
833/// dimensions.
834///
835/// 2) Construct a set B by removing all constraints that involve
836/// the unbounded dimensions and then deleting the unbounded dimensions. Note
837/// that B is a Bounded set.
838///
839/// 3) Try to obtain a sample from B using the GBR sampling
840/// algorithm. If no sample is found, return that S is empty.
841///
842/// 4) Otherwise, substitute the obtained sample into S*T to obtain a set
843/// C. C is a full-dimensional Cone and always contains a sample.
844///
845/// 5) Obtain an integer sample from C.
846///
847/// 6) Return T*v, where v is the concatenation of the samples from B and C.
848///
849/// The following is a sketch of a proof that
850/// a) If the algorithm returns empty, then S is empty.
851/// b) If the algorithm returns a sample, it is a valid sample in S.
852///
853/// The algorithm returns empty only if B is empty, in which case S*T is
854/// certainly empty since B was obtained by removing constraints and then
855/// deleting unconstrained dimensions from S*T. Since T is unimodular, a vector
856/// v is in S*T iff T*v is in S. So in this case, since
857/// S*T is empty, S is empty too.
858///
859/// Otherwise, the algorithm substitutes the sample from B into S*T. All the
860/// constraints of S*T that did not involve unbounded dimensions are satisfied
861/// by this substitution. All dimensions in the linear span of the dimensions
862/// outside the prefix are unbounded in S*T (step 1). Substituting values for
863/// the bounded dimensions cannot make these dimensions bounded, and these are
864/// the only remaining dimensions in C, so C is unbounded along every vector (in
865/// the positive or negative direction, or both). C is hence a full-dimensional
866/// cone and therefore always contains an integer point.
867///
868/// Concatenating the samples from B and C gives a sample v in S*T, so the
869/// returned sample T*v is a sample in S.
870std::optional<SmallVector<DynamicAPInt, 8>>
871IntegerRelation::findIntegerSample() const {
872 // First, try the GCD test heuristic.
873 if (isEmptyByGCDTest())
874 return {};
875
876 Simplex simplex(*this);
877 if (simplex.isEmpty())
878 return {};
879
880 // For a bounded set, we directly call into the GBR sampling algorithm.
881 if (!simplex.isUnbounded())
882 return simplex.findIntegerSample();
883
884 // The set is unbounded. We cannot directly use the GBR algorithm.
885 //
886 // m is a matrix containing, in each row, a vector in which S is
887 // bounded, such that the linear span of all these dimensions contains all
888 // bounded dimensions in S.
889 IntMatrix m = getBoundedDirections();
890 // In column echelon form, each row of m occupies only the first rank(m)
891 // columns and has zeros on the other columns. The transform T that brings S
892 // to column echelon form is unimodular as well, so this is a suitable
893 // transform to use in step 1 of the algorithm.
894 std::pair<unsigned, LinearTransform> result =
895 LinearTransform::makeTransformToColumnEchelon(m);
896 const LinearTransform &transform = result.second;
897 // 1) Apply T to S to obtain S*T.
898 IntegerRelation transformedSet = transform.applyTo(rel: *this);
899
900 // 2) Remove the unbounded dimensions and constraints involving them to
901 // obtain a bounded set.
902 IntegerRelation boundedSet(transformedSet);
903 unsigned numBoundedDims = result.first;
904 unsigned numUnboundedDims = getNumVars() - numBoundedDims;
905 removeConstraintsInvolvingVarRange(poly&: boundedSet, begin: numBoundedDims,
906 count: numUnboundedDims);
907 boundedSet.removeVarRange(varStart: numBoundedDims, varLimit: boundedSet.getNumVars());
908
909 // 3) Try to obtain a sample from the bounded set.
910 std::optional<SmallVector<DynamicAPInt, 8>> boundedSample =
911 Simplex(boundedSet).findIntegerSample();
912 if (!boundedSample)
913 return {};
914 assert(boundedSet.containsPoint(*boundedSample) &&
915 "Simplex returned an invalid sample!");
916
917 // 4) Substitute the values of the bounded dimensions into S*T to obtain a
918 // full-dimensional cone, which necessarily contains an integer sample.
919 transformedSet.setAndEliminate(pos: 0, values: *boundedSample);
920 IntegerRelation &cone = transformedSet;
921
922 // 5) Obtain an integer sample from the cone.
923 //
924 // We shrink the cone such that for any rational point in the shrunken cone,
925 // rounding up each of the point's coordinates produces a point that still
926 // lies in the original cone.
927 //
928 // Rounding up a point x adds a number e_i in [0, 1) to each coordinate x_i.
929 // For each inequality sum_i a_i x_i + c >= 0 in the original cone, the
930 // shrunken cone will have the inequality tightened by some amount s, such
931 // that if x satisfies the shrunken cone's tightened inequality, then x + e
932 // satisfies the original inequality, i.e.,
933 //
934 // sum_i a_i x_i + c + s >= 0 implies sum_i a_i (x_i + e_i) + c >= 0
935 //
936 // for any e_i values in [0, 1). In fact, we will handle the slightly more
937 // general case where e_i can be in [0, 1]. For example, consider the
938 // inequality 2x_1 - 3x_2 - 7x_3 - 6 >= 0, and let x = (3, 0, 0). How low
939 // could the LHS go if we added a number in [0, 1] to each coordinate? The LHS
940 // is minimized when we add 1 to the x_i with negative coefficient a_i and
941 // keep the other x_i the same. In the example, we would get x = (3, 1, 1),
942 // changing the value of the LHS by -3 + -7 = -10.
943 //
944 // In general, the value of the LHS can change by at most the sum of the
945 // negative a_i, so we accomodate this by shifting the inequality by this
946 // amount for the shrunken cone.
947 for (unsigned i = 0, e = cone.getNumInequalities(); i < e; ++i) {
948 for (unsigned j = 0; j < cone.getNumVars(); ++j) {
949 DynamicAPInt coeff = cone.atIneq(i, j);
950 if (coeff < 0)
951 cone.atIneq(i, j: cone.getNumVars()) += coeff;
952 }
953 }
954
955 // Obtain an integer sample in the cone by rounding up a rational point from
956 // the shrunken cone. Shrinking the cone amounts to shifting its apex
957 // "inwards" without changing its "shape"; the shrunken cone is still a
958 // full-dimensional cone and is hence non-empty.
959 Simplex shrunkenConeSimplex(cone);
960 assert(!shrunkenConeSimplex.isEmpty() && "Shrunken cone cannot be empty!");
961
962 // The sample will always exist since the shrunken cone is non-empty.
963 SmallVector<Fraction, 8> shrunkenConeSample =
964 *shrunkenConeSimplex.getRationalSample();
965
966 SmallVector<DynamicAPInt, 8> coneSample(
967 llvm::map_range(C&: shrunkenConeSample, F: ceil));
968
969 // 6) Return transform * concat(boundedSample, coneSample).
970 SmallVector<DynamicAPInt, 8> &sample = *boundedSample;
971 sample.append(in_start: coneSample.begin(), in_end: coneSample.end());
972 return transform.postMultiplyWithColumn(colVec: sample);
973}
974
975/// Helper to evaluate an affine expression at a point.
976/// The expression is a list of coefficients for the dimensions followed by the
977/// constant term.
978static DynamicAPInt valueAt(ArrayRef<DynamicAPInt> expr,
979 ArrayRef<DynamicAPInt> point) {
980 assert(expr.size() == 1 + point.size() &&
981 "Dimensionalities of point and expression don't match!");
982 DynamicAPInt value = expr.back();
983 for (unsigned i = 0; i < point.size(); ++i)
984 value += expr[i] * point[i];
985 return value;
986}
987
988/// A point satisfies an equality iff the value of the equality at the
989/// expression is zero, and it satisfies an inequality iff the value of the
990/// inequality at that point is non-negative.
991bool IntegerRelation::containsPoint(ArrayRef<DynamicAPInt> point) const {
992 for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
993 if (valueAt(expr: getEquality(idx: i), point) != 0)
994 return false;
995 }
996 for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
997 if (valueAt(expr: getInequality(idx: i), point) < 0)
998 return false;
999 }
1000 return true;
1001}
1002
1003/// Just substitute the values given and check if an integer sample exists for
1004/// the local vars.
1005///
1006/// TODO: this could be made more efficient by handling divisions separately.
1007/// Instead of finding an integer sample over all the locals, we can first
1008/// compute the values of the locals that have division representations and
1009/// only use the integer emptiness check for the locals that don't have this.
1010/// Handling this correctly requires ordering the divs, though.
1011std::optional<SmallVector<DynamicAPInt, 8>>
1012IntegerRelation::containsPointNoLocal(ArrayRef<DynamicAPInt> point) const {
1013 assert(point.size() == getNumVars() - getNumLocalVars() &&
1014 "Point should contain all vars except locals!");
1015 assert(getVarKindOffset(VarKind::Local) == getNumVars() - getNumLocalVars() &&
1016 "This function depends on locals being stored last!");
1017 IntegerRelation copy = *this;
1018 copy.setAndEliminate(pos: 0, values: point);
1019 return copy.findIntegerSample();
1020}
1021
1022DivisionRepr
1023IntegerRelation::getLocalReprs(std::vector<MaybeLocalRepr> *repr) const {
1024 SmallVector<bool, 8> foundRepr(getNumVars(), false);
1025 for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; ++i)
1026 foundRepr[i] = true;
1027
1028 unsigned localOffset = getVarKindOffset(kind: VarKind::Local);
1029 DivisionRepr divs(getNumVars(), getNumLocalVars());
1030 bool changed;
1031 do {
1032 // Each time changed is true, at end of this iteration, one or more local
1033 // vars have been detected as floor divs.
1034 changed = false;
1035 for (unsigned i = 0, e = getNumLocalVars(); i < e; ++i) {
1036 if (!foundRepr[i + localOffset]) {
1037 MaybeLocalRepr res =
1038 computeSingleVarRepr(cst: *this, foundRepr, pos: localOffset + i,
1039 dividend: divs.getDividend(i), divisor&: divs.getDenom(i));
1040 if (!res) {
1041 // No representation was found, so clear the representation and
1042 // continue.
1043 divs.clearRepr(i);
1044 continue;
1045 }
1046 foundRepr[localOffset + i] = true;
1047 if (repr)
1048 (*repr)[i] = res;
1049 changed = true;
1050 }
1051 }
1052 } while (changed);
1053
1054 return divs;
1055}
1056
1057/// Tightens inequalities given that we are dealing with integer spaces. This is
1058/// analogous to the GCD test but applied to inequalities. The constant term can
1059/// be reduced to the preceding multiple of the GCD of the coefficients, i.e.,
1060/// 64*i - 100 >= 0 => 64*i - 128 >= 0 (since 'i' is an integer). This is a
1061/// fast method - linear in the number of coefficients.
1062// Example on how this affects practical cases: consider the scenario:
1063// 64*i >= 100, j = 64*i; without a tightening, elimination of i would yield
1064// j >= 100 instead of the tighter (exact) j >= 128.
1065void IntegerRelation::gcdTightenInequalities() {
1066 unsigned numCols = getNumCols();
1067 for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
1068 // Normalize the constraint and tighten the constant term by the GCD.
1069 DynamicAPInt gcd = inequalities.normalizeRow(row: i, nCols: getNumCols() - 1);
1070 if (gcd > 1)
1071 atIneq(i, j: numCols - 1) = floorDiv(LHS: atIneq(i, j: numCols - 1), RHS: gcd);
1072 }
1073}
1074
1075// Eliminates all variable variables in column range [posStart, posLimit).
1076// Returns the number of variables eliminated.
1077unsigned IntegerRelation::gaussianEliminateVars(unsigned posStart,
1078 unsigned posLimit) {
1079 // Return if variable positions to eliminate are out of range.
1080 assert(posLimit <= getNumVars());
1081 assert(hasConsistentState());
1082
1083 if (posStart >= posLimit)
1084 return 0;
1085
1086 gcdTightenInequalities();
1087
1088 unsigned pivotCol = 0;
1089 for (pivotCol = posStart; pivotCol < posLimit; ++pivotCol) {
1090 // Find a row which has a non-zero coefficient in column 'j'.
1091 std::optional<unsigned> pivotRow =
1092 findConstraintWithNonZeroAt(colIdx: pivotCol, /*isEq=*/true);
1093 // No pivot row in equalities with non-zero at 'pivotCol'.
1094 if (!pivotRow) {
1095 // If inequalities are also non-zero in 'pivotCol', it can be eliminated.
1096 if ((pivotRow = findConstraintWithNonZeroAt(colIdx: pivotCol, /*isEq=*/false)))
1097 break;
1098 continue;
1099 }
1100
1101 // Eliminate variable at 'pivotCol' from each equality row.
1102 for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
1103 eliminateFromConstraint(constraints: this, rowIdx: i, pivotRow: *pivotRow, pivotCol, elimColStart: posStart,
1104 /*isEq=*/true);
1105 equalities.normalizeRow(row: i);
1106 }
1107
1108 // Eliminate variable at 'pivotCol' from each inequality row.
1109 for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
1110 eliminateFromConstraint(constraints: this, rowIdx: i, pivotRow: *pivotRow, pivotCol, elimColStart: posStart,
1111 /*isEq=*/false);
1112 inequalities.normalizeRow(row: i);
1113 }
1114 removeEquality(pos: *pivotRow);
1115 gcdTightenInequalities();
1116 }
1117 // Update position limit based on number eliminated.
1118 posLimit = pivotCol;
1119 // Remove eliminated columns from all constraints.
1120 removeVarRange(varStart: posStart, varLimit: posLimit);
1121 return posLimit - posStart;
1122}
1123
1124static std::optional<unsigned>
1125findEqualityWithNonZeroAfterRow(IntegerRelation &rel, unsigned fromRow,
1126 unsigned colIdx) {
1127 assert(fromRow < rel.getNumEqualities() && colIdx < rel.getNumCols() &&
1128 "position out of bounds");
1129 for (unsigned rowIdx = fromRow, e = rel.getNumEqualities(); rowIdx < e;
1130 ++rowIdx) {
1131 if (rel.atEq(i: rowIdx, j: colIdx) != 0)
1132 return rowIdx;
1133 }
1134 return std::nullopt;
1135}
1136
1137bool IntegerRelation::gaussianEliminate() {
1138 gcdTightenInequalities();
1139 unsigned firstVar = 0, vars = getNumVars();
1140 unsigned nowDone, eqs;
1141 std::optional<unsigned> pivotRow;
1142 for (nowDone = 0, eqs = getNumEqualities(); nowDone < eqs; ++nowDone) {
1143 // Finds the first non-empty column that we haven't dealt with.
1144 for (; firstVar < vars; ++firstVar) {
1145 if ((pivotRow =
1146 findEqualityWithNonZeroAfterRow(rel&: *this, fromRow: nowDone, colIdx: firstVar)))
1147 break;
1148 }
1149 // The matrix has been normalized to row echelon form.
1150 if (firstVar >= vars)
1151 break;
1152
1153 // The first pivot row found is below where it should currently be placed.
1154 if (*pivotRow > nowDone) {
1155 equalities.swapRows(row: *pivotRow, otherRow: nowDone);
1156 *pivotRow = nowDone;
1157 }
1158
1159 // Normalize all lower equations and all inequalities.
1160 for (unsigned i = nowDone + 1; i < eqs; ++i) {
1161 eliminateFromConstraint(constraints: this, rowIdx: i, pivotRow: *pivotRow, pivotCol: firstVar, elimColStart: 0, isEq: true);
1162 equalities.normalizeRow(row: i);
1163 }
1164 for (unsigned i = 0, ineqs = getNumInequalities(); i < ineqs; ++i) {
1165 eliminateFromConstraint(constraints: this, rowIdx: i, pivotRow: *pivotRow, pivotCol: firstVar, elimColStart: firstVar, isEq: false);
1166 inequalities.normalizeRow(row: i);
1167 }
1168 gcdTightenInequalities();
1169
1170 // The column is finished. Tell the next iteration to start at the next
1171 // column.
1172 firstVar++;
1173 }
1174
1175 // No redundant rows.
1176 if (nowDone == eqs)
1177 return false;
1178
1179 // Check to see if the redundant rows constant is zero, a non-zero value means
1180 // the set is empty.
1181 for (unsigned i = nowDone; i < eqs; ++i) {
1182 if (atEq(i, j: vars) == 0)
1183 continue;
1184
1185 *this = getEmpty(space: getSpace());
1186 return true;
1187 }
1188 // Eliminate rows that are confined to be all zeros.
1189 removeEqualityRange(start: nowDone, end: eqs);
1190 return true;
1191}
1192
1193// A more complex check to eliminate redundant inequalities. Uses FourierMotzkin
1194// to check if a constraint is redundant.
1195void IntegerRelation::removeRedundantInequalities() {
1196 SmallVector<bool, 32> redun(getNumInequalities(), false);
1197 // To check if an inequality is redundant, we replace the inequality by its
1198 // complement (for eg., i - 1 >= 0 by i <= 0), and check if the resulting
1199 // system is empty. If it is, the inequality is redundant.
1200 IntegerRelation tmpCst(*this);
1201 for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
1202 // Change the inequality to its complement.
1203 tmpCst.inequalities.negateRow(row: r);
1204 --tmpCst.atIneq(i: r, j: tmpCst.getNumCols() - 1);
1205 if (tmpCst.isEmpty()) {
1206 redun[r] = true;
1207 // Zero fill the redundant inequality.
1208 inequalities.fillRow(row: r, /*value=*/0);
1209 tmpCst.inequalities.fillRow(row: r, /*value=*/0);
1210 } else {
1211 // Reverse the change (to avoid recreating tmpCst each time).
1212 ++tmpCst.atIneq(i: r, j: tmpCst.getNumCols() - 1);
1213 tmpCst.inequalities.negateRow(row: r);
1214 }
1215 }
1216
1217 unsigned pos = 0;
1218 for (unsigned r = 0, e = getNumInequalities(); r < e; ++r) {
1219 if (!redun[r])
1220 inequalities.copyRow(sourceRow: r, targetRow: pos++);
1221 }
1222 inequalities.resizeVertically(newNRows: pos);
1223}
1224
1225// A more complex check to eliminate redundant inequalities and equalities. Uses
1226// Simplex to check if a constraint is redundant.
1227void IntegerRelation::removeRedundantConstraints() {
1228 // First, we run gcdTightenInequalities. This allows us to catch some
1229 // constraints which are not redundant when considering rational solutions
1230 // but are redundant in terms of integer solutions.
1231 gcdTightenInequalities();
1232 Simplex simplex(*this);
1233 simplex.detectRedundant();
1234 removeRedundantConstraintsFromSimplex(simplex, /*offset=*/0);
1235}
1236
1237void IntegerRelation::removeRedundantConstraintsFromSimplex(
1238 const Simplex &simplex, unsigned offset) {
1239 unsigned numIneqs = getNumInequalities();
1240 assert(offset + numIneqs + 2 * getNumEqualities() <=
1241 simplex.getNumConstraints() &&
1242 "simplex does not contain all constraints of this relation");
1243
1244 unsigned pos = 0;
1245 // Scan to get rid of all inequalities marked redundant, in-place. In Simplex,
1246 // the first constraints added are the inequalities.
1247 for (unsigned r = 0; r < numIneqs; r++) {
1248 if (!simplex.isMarkedRedundant(constraintIndex: offset + r))
1249 inequalities.copyRow(sourceRow: r, targetRow: pos++);
1250 }
1251 inequalities.resizeVertically(newNRows: pos);
1252
1253 // Scan to get rid of all equalities marked redundant, in-place. In Simplex,
1254 // after the inequalities, a pair of constraints for each equality is added.
1255 // An equality is redundant if both the inequalities in its pair are
1256 // redundant.
1257 pos = 0;
1258 for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
1259 if (!(simplex.isMarkedRedundant(constraintIndex: offset + numIneqs + 2 * r) &&
1260 simplex.isMarkedRedundant(constraintIndex: offset + numIneqs + 2 * r + 1)))
1261 equalities.copyRow(sourceRow: r, targetRow: pos++);
1262 }
1263 equalities.resizeVertically(newNRows: pos);
1264}
1265
1266std::optional<DynamicAPInt> IntegerRelation::computeVolume() const {
1267 assert(getNumSymbolVars() == 0 && "Symbols are not yet supported!");
1268
1269 Simplex simplex(*this);
1270 // If the polytope is rationally empty, there are certainly no integer
1271 // points.
1272 if (simplex.isEmpty())
1273 return DynamicAPInt(0);
1274
1275 // Just find the maximum and minimum integer value of each non-local var
1276 // separately, thus finding the number of integer values each such var can
1277 // take. Multiplying these together gives a valid overapproximation of the
1278 // number of integer points in the relation. The result this gives is
1279 // equivalent to projecting (rationally) the relation onto its non-local vars
1280 // and returning the number of integer points in a minimal axis-parallel
1281 // hyperrectangular overapproximation of that.
1282 //
1283 // We also handle the special case where one dimension is unbounded and
1284 // another dimension can take no integer values. In this case, the volume is
1285 // zero.
1286 //
1287 // If there is no such empty dimension, if any dimension is unbounded we
1288 // just return the result as unbounded.
1289 DynamicAPInt count(1);
1290 SmallVector<DynamicAPInt, 8> dim(getNumVars() + 1);
1291 bool hasUnboundedVar = false;
1292 for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; ++i) {
1293 dim[i] = 1;
1294 auto [min, max] = simplex.computeIntegerBounds(coeffs: dim);
1295 dim[i] = 0;
1296
1297 assert((!min.isEmpty() && !max.isEmpty()) &&
1298 "Polytope should be rationally non-empty!");
1299
1300 // One of the dimensions is unbounded. Note this fact. We will return
1301 // unbounded if none of the other dimensions makes the volume zero.
1302 if (min.isUnbounded() || max.isUnbounded()) {
1303 hasUnboundedVar = true;
1304 continue;
1305 }
1306
1307 // In this case there are no valid integer points and the volume is
1308 // definitely zero.
1309 if (min.getBoundedOptimum() > max.getBoundedOptimum())
1310 return DynamicAPInt(0);
1311
1312 count *= (*max - *min + 1);
1313 }
1314
1315 if (count == 0)
1316 return DynamicAPInt(0);
1317 if (hasUnboundedVar)
1318 return {};
1319 return count;
1320}
1321
1322void IntegerRelation::eliminateRedundantLocalVar(unsigned posA, unsigned posB) {
1323 assert(posA < getNumLocalVars() && "Invalid local var position");
1324 assert(posB < getNumLocalVars() && "Invalid local var position");
1325
1326 unsigned localOffset = getVarKindOffset(kind: VarKind::Local);
1327 posA += localOffset;
1328 posB += localOffset;
1329 inequalities.addToColumn(sourceColumn: posB, targetColumn: posA, scale: 1);
1330 equalities.addToColumn(sourceColumn: posB, targetColumn: posA, scale: 1);
1331 removeVar(pos: posB);
1332}
1333
1334/// mergeAndAlignSymbols's implementation can be broken down into two steps:
1335/// 1. Merge and align identifiers into `other` from `this. If an identifier
1336/// from `this` exists in `other` then we align it. Otherwise, we assume it is a
1337/// new identifier and insert it into `other` in the same position as `this`.
1338/// 2. Add identifiers that are in `other` but not `this to `this`.
1339void IntegerRelation::mergeAndAlignSymbols(IntegerRelation &other) {
1340 assert(space.isUsingIds() && other.space.isUsingIds() &&
1341 "both relations need to have identifers to merge and align");
1342
1343 unsigned i = 0;
1344 for (const Identifier identifier : space.getIds(kind: VarKind::Symbol)) {
1345 // Search in `other` starting at position `i` since the left of `i` is
1346 // aligned.
1347 const Identifier *findBegin =
1348 other.space.getIds(kind: VarKind::Symbol).begin() + i;
1349 const Identifier *findEnd = other.space.getIds(kind: VarKind::Symbol).end();
1350 const Identifier *itr = std::find(first: findBegin, last: findEnd, val: identifier);
1351 if (itr != findEnd) {
1352 other.swapVar(posA: other.getVarKindOffset(kind: VarKind::Symbol) + i,
1353 posB: other.getVarKindOffset(kind: VarKind::Symbol) + i +
1354 std::distance(first: findBegin, last: itr));
1355 } else {
1356 other.insertVar(kind: VarKind::Symbol, pos: i);
1357 other.space.setId(kind: VarKind::Symbol, pos: i, id: identifier);
1358 }
1359 ++i;
1360 }
1361
1362 for (unsigned e = other.getNumVarKind(kind: VarKind::Symbol); i < e; ++i) {
1363 insertVar(kind: VarKind::Symbol, pos: i);
1364 space.setId(kind: VarKind::Symbol, pos: i, id: other.space.getId(kind: VarKind::Symbol, pos: i));
1365 }
1366}
1367
1368/// Adds additional local ids to the sets such that they both have the union
1369/// of the local ids in each set, without changing the set of points that
1370/// lie in `this` and `other`.
1371///
1372/// To detect local ids that always take the same value, each local id is
1373/// represented as a floordiv with constant denominator in terms of other ids.
1374/// After extracting these divisions, local ids in `other` with the same
1375/// division representation as some other local id in any set are considered
1376/// duplicate and are merged.
1377///
1378/// It is possible that division representation for some local id cannot be
1379/// obtained, and thus these local ids are not considered for detecting
1380/// duplicates.
1381unsigned IntegerRelation::mergeLocalVars(IntegerRelation &other) {
1382 IntegerRelation &relA = *this;
1383 IntegerRelation &relB = other;
1384
1385 unsigned oldALocals = relA.getNumLocalVars();
1386
1387 // Merge function that merges the local variables in both sets by treating
1388 // them as the same variable.
1389 auto merge = [&relA, &relB, oldALocals](unsigned i, unsigned j) -> bool {
1390 // We only merge from local at pos j to local at pos i, where j > i.
1391 if (i >= j)
1392 return false;
1393
1394 // If i < oldALocals, we are trying to merge duplicate divs. Since we do not
1395 // want to merge duplicates in A, we ignore this call.
1396 if (j < oldALocals)
1397 return false;
1398
1399 // Merge local at pos j into local at position i.
1400 relA.eliminateRedundantLocalVar(posA: i, posB: j);
1401 relB.eliminateRedundantLocalVar(posA: i, posB: j);
1402 return true;
1403 };
1404
1405 presburger::mergeLocalVars(relA&: *this, relB&: other, merge);
1406
1407 // Since we do not remove duplicate divisions in relA, this is guranteed to be
1408 // non-negative.
1409 return relA.getNumLocalVars() - oldALocals;
1410}
1411
1412bool IntegerRelation::hasOnlyDivLocals() const {
1413 return getLocalReprs().hasAllReprs();
1414}
1415
1416void IntegerRelation::removeDuplicateDivs() {
1417 DivisionRepr divs = getLocalReprs();
1418 auto merge = [this](unsigned i, unsigned j) -> bool {
1419 eliminateRedundantLocalVar(posA: i, posB: j);
1420 return true;
1421 };
1422 divs.removeDuplicateDivs(merge);
1423}
1424
1425void IntegerRelation::simplify() {
1426 bool changed = true;
1427 // Repeat until we reach a fixed point.
1428 while (changed) {
1429 if (isObviouslyEmpty())
1430 return;
1431 changed = false;
1432 normalizeConstraintsByGCD();
1433 changed |= gaussianEliminate();
1434 changed |= removeDuplicateConstraints();
1435 }
1436 // Current set is not empty.
1437}
1438
1439/// Removes local variables using equalities. Each equality is checked if it
1440/// can be reduced to the form: `e = affine-expr`, where `e` is a local
1441/// variable and `affine-expr` is an affine expression not containing `e`.
1442/// If an equality satisfies this form, the local variable is replaced in
1443/// each constraint and then removed. The equality used to replace this local
1444/// variable is also removed.
1445void IntegerRelation::removeRedundantLocalVars() {
1446 // Normalize the equality constraints to reduce coefficients of local
1447 // variables to 1 wherever possible.
1448 for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
1449 equalities.normalizeRow(row: i);
1450
1451 while (true) {
1452 unsigned i, e, j, f;
1453 for (i = 0, e = getNumEqualities(); i < e; ++i) {
1454 // Find a local variable to eliminate using ith equality.
1455 for (j = getNumDimAndSymbolVars(), f = getNumVars(); j < f; ++j)
1456 if (abs(X: atEq(i, j)) == 1)
1457 break;
1458
1459 // Local variable can be eliminated using ith equality.
1460 if (j < f)
1461 break;
1462 }
1463
1464 // No equality can be used to eliminate a local variable.
1465 if (i == e)
1466 break;
1467
1468 // Use the ith equality to simplify other equalities. If any changes
1469 // are made to an equality constraint, it is normalized by GCD.
1470 for (unsigned k = 0, t = getNumEqualities(); k < t; ++k) {
1471 if (atEq(i: k, j) != 0) {
1472 eliminateFromConstraint(constraints: this, rowIdx: k, pivotRow: i, pivotCol: j, elimColStart: j, /*isEq=*/true);
1473 equalities.normalizeRow(row: k);
1474 }
1475 }
1476
1477 // Use the ith equality to simplify inequalities.
1478 for (unsigned k = 0, t = getNumInequalities(); k < t; ++k)
1479 eliminateFromConstraint(constraints: this, rowIdx: k, pivotRow: i, pivotCol: j, elimColStart: j, /*isEq=*/false);
1480
1481 // Remove the ith equality and the found local variable.
1482 removeVar(pos: j);
1483 removeEquality(pos: i);
1484 }
1485}
1486
1487void IntegerRelation::convertVarKind(VarKind srcKind, unsigned varStart,
1488 unsigned varLimit, VarKind dstKind,
1489 unsigned pos) {
1490 assert(varLimit <= getNumVarKind(srcKind) && "invalid id range");
1491
1492 if (varStart >= varLimit)
1493 return;
1494
1495 unsigned srcOffset = getVarKindOffset(kind: srcKind);
1496 unsigned dstOffset = getVarKindOffset(kind: dstKind);
1497 unsigned convertCount = varLimit - varStart;
1498 int forwardMoveOffset = dstOffset > srcOffset ? -convertCount : 0;
1499
1500 equalities.moveColumns(srcPos: srcOffset + varStart, num: convertCount,
1501 dstPos: dstOffset + pos + forwardMoveOffset);
1502 inequalities.moveColumns(srcPos: srcOffset + varStart, num: convertCount,
1503 dstPos: dstOffset + pos + forwardMoveOffset);
1504
1505 space.convertVarKind(srcKind, srcPos: varStart, num: varLimit - varStart, dstKind, dstPos: pos);
1506}
1507
1508void IntegerRelation::addBound(BoundType type, unsigned pos,
1509 const DynamicAPInt &value) {
1510 assert(pos < getNumCols());
1511 if (type == BoundType::EQ) {
1512 unsigned row = equalities.appendExtraRow();
1513 equalities(row, pos) = 1;
1514 equalities(row, getNumCols() - 1) = -value;
1515 } else {
1516 unsigned row = inequalities.appendExtraRow();
1517 inequalities(row, pos) = type == BoundType::LB ? 1 : -1;
1518 inequalities(row, getNumCols() - 1) =
1519 type == BoundType::LB ? -value : value;
1520 }
1521}
1522
1523void IntegerRelation::addBound(BoundType type, ArrayRef<DynamicAPInt> expr,
1524 const DynamicAPInt &value) {
1525 assert(type != BoundType::EQ && "EQ not implemented");
1526 assert(expr.size() == getNumCols());
1527 unsigned row = inequalities.appendExtraRow();
1528 for (unsigned i = 0, e = expr.size(); i < e; ++i)
1529 inequalities(row, i) = type == BoundType::LB ? expr[i] : -expr[i];
1530 inequalities(inequalities.getNumRows() - 1, getNumCols() - 1) +=
1531 type == BoundType::LB ? -value : value;
1532}
1533
1534/// Adds a new local variable as the floordiv of an affine function of other
1535/// variables, the coefficients of which are provided in 'dividend' and with
1536/// respect to a positive constant 'divisor'. Two constraints are added to the
1537/// system to capture equivalence with the floordiv.
1538/// q = expr floordiv c <=> c*q <= expr <= c*q + c - 1.
1539/// Returns the column position of the new local variable.
1540unsigned IntegerRelation::addLocalFloorDiv(ArrayRef<DynamicAPInt> dividend,
1541 const DynamicAPInt &divisor) {
1542 assert(dividend.size() == getNumCols() && "incorrect dividend size");
1543 assert(divisor > 0 && "positive divisor expected");
1544
1545 unsigned newVar = appendVar(kind: VarKind::Local);
1546
1547 SmallVector<DynamicAPInt, 8> dividendCopy(dividend);
1548 dividendCopy.insert(I: dividendCopy.end() - 1, Elt: DynamicAPInt(0));
1549 addInequality(
1550 inEq: getDivLowerBound(dividend: dividendCopy, divisor, localVarIdx: dividendCopy.size() - 2));
1551 addInequality(
1552 inEq: getDivUpperBound(dividend: dividendCopy, divisor, localVarIdx: dividendCopy.size() - 2));
1553 return newVar;
1554}
1555
1556unsigned IntegerRelation::addLocalModulo(ArrayRef<DynamicAPInt> exprs,
1557 const DynamicAPInt &modulus) {
1558 assert(exprs.size() == getNumCols() && "incorrect exprs size");
1559 assert(modulus > 0 && "positive modulus expected");
1560
1561 /// Add a local variable for q = expr floordiv modulus
1562 addLocalFloorDiv(dividend: exprs, divisor: modulus);
1563
1564 /// Add a local var to represent the result
1565 auto resultIndex = appendVar(kind: VarKind::Local);
1566
1567 SmallVector<DynamicAPInt, 8> exprsCopy(exprs);
1568 /// Insert the two new locals before the constant
1569 /// Add locals that correspond to `q` and `result` to compute
1570 /// 0 = (expr - modulus * q) - result
1571 exprsCopy.insert(I: exprsCopy.end() - 1,
1572 IL: {DynamicAPInt(-modulus), DynamicAPInt(-1)});
1573 addEquality(eq: exprsCopy);
1574 return resultIndex;
1575}
1576
1577int IntegerRelation::findEqualityToConstant(unsigned pos, bool symbolic) const {
1578 assert(pos < getNumVars() && "invalid position");
1579 for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
1580 DynamicAPInt v = atEq(i: r, j: pos);
1581 if (v * v != 1)
1582 continue;
1583 unsigned c;
1584 unsigned f = symbolic ? getNumDimVars() : getNumVars();
1585 // This checks for zeros in all positions other than 'pos' in [0, f)
1586 for (c = 0; c < f; c++) {
1587 if (c == pos)
1588 continue;
1589 if (atEq(i: r, j: c) != 0) {
1590 // Dependent on another variable.
1591 break;
1592 }
1593 }
1594 if (c == f)
1595 // Equality is free of other variables.
1596 return r;
1597 }
1598 return -1;
1599}
1600
1601LogicalResult IntegerRelation::constantFoldVar(unsigned pos) {
1602 assert(pos < getNumVars() && "invalid position");
1603 int rowIdx;
1604 if ((rowIdx = findEqualityToConstant(pos)) == -1)
1605 return failure();
1606
1607 // atEq(rowIdx, pos) is either -1 or 1.
1608 assert(atEq(rowIdx, pos) * atEq(rowIdx, pos) == 1);
1609 DynamicAPInt constVal = -atEq(i: rowIdx, j: getNumCols() - 1) / atEq(i: rowIdx, j: pos);
1610 setAndEliminate(pos, values: constVal);
1611 return success();
1612}
1613
1614void IntegerRelation::constantFoldVarRange(unsigned pos, unsigned num) {
1615 for (unsigned s = pos, t = pos, e = pos + num; s < e; s++) {
1616 if (constantFoldVar(pos: t).failed())
1617 t++;
1618 }
1619}
1620
1621/// Returns a non-negative constant bound on the extent (upper bound - lower
1622/// bound) of the specified variable if it is found to be a constant; returns
1623/// std::nullopt if it's not a constant. This methods treats symbolic variables
1624/// specially, i.e., it looks for constant differences between affine
1625/// expressions involving only the symbolic variables. See comments at function
1626/// definition for example. 'lb', if provided, is set to the lower bound
1627/// associated with the constant difference. Note that 'lb' is purely symbolic
1628/// and thus will contain the coefficients of the symbolic variables and the
1629/// constant coefficient.
1630// Egs: 0 <= i <= 15, return 16.
1631// s0 + 2 <= i <= s0 + 17, returns 16. (s0 has to be a symbol)
1632// s0 + s1 + 16 <= d0 <= s0 + s1 + 31, returns 16.
1633// s0 - 7 <= 8*j <= s0 returns 1 with lb = s0, lbDivisor = 8 (since lb =
1634// ceil(s0 - 7 / 8) = floor(s0 / 8)).
1635std::optional<DynamicAPInt> IntegerRelation::getConstantBoundOnDimSize(
1636 unsigned pos, SmallVectorImpl<DynamicAPInt> *lb,
1637 DynamicAPInt *boundFloorDivisor, SmallVectorImpl<DynamicAPInt> *ub,
1638 unsigned *minLbPos, unsigned *minUbPos) const {
1639 assert(pos < getNumDimVars() && "Invalid variable position");
1640
1641 // Find an equality for 'pos'^th variable that equates it to some function
1642 // of the symbolic variables (+ constant).
1643 int eqPos = findEqualityToConstant(pos, /*symbolic=*/true);
1644 if (eqPos != -1) {
1645 auto eq = getEquality(idx: eqPos);
1646 // If the equality involves a local var, we do not handle it.
1647 // FlatLinearConstraints can instead be used to detect the local variable as
1648 // an affine function (potentially div/mod) of other variables and use
1649 // affine expressions/maps to represent output.
1650 if (!std::all_of(first: eq.begin() + getNumDimAndSymbolVars(), last: eq.end() - 1,
1651 pred: [](const DynamicAPInt &coeff) { return coeff == 0; }))
1652 return std::nullopt;
1653
1654 // This variable can only take a single value.
1655 if (lb) {
1656 // Set lb to that symbolic value.
1657 lb->resize(N: getNumSymbolVars() + 1);
1658 if (ub)
1659 ub->resize(N: getNumSymbolVars() + 1);
1660 for (unsigned c = 0, f = getNumSymbolVars() + 1; c < f; c++) {
1661 DynamicAPInt v = atEq(i: eqPos, j: pos);
1662 // atEq(eqRow, pos) is either -1 or 1.
1663 assert(v * v == 1);
1664 (*lb)[c] = v < 0 ? atEq(i: eqPos, j: getNumDimVars() + c) / -v
1665 : -atEq(i: eqPos, j: getNumDimVars() + c) / v;
1666 // Since this is an equality, ub = lb.
1667 if (ub)
1668 (*ub)[c] = (*lb)[c];
1669 }
1670 assert(boundFloorDivisor &&
1671 "both lb and divisor or none should be provided");
1672 *boundFloorDivisor = 1;
1673 }
1674 if (minLbPos)
1675 *minLbPos = eqPos;
1676 if (minUbPos)
1677 *minUbPos = eqPos;
1678 return DynamicAPInt(1);
1679 }
1680
1681 // Check if the variable appears at all in any of the inequalities.
1682 unsigned r, e;
1683 for (r = 0, e = getNumInequalities(); r < e; r++) {
1684 if (atIneq(i: r, j: pos) != 0)
1685 break;
1686 }
1687 if (r == e)
1688 // If it doesn't, there isn't a bound on it.
1689 return std::nullopt;
1690
1691 // Positions of constraints that are lower/upper bounds on the variable.
1692 SmallVector<unsigned, 4> lbIndices, ubIndices;
1693
1694 // Gather all symbolic lower bounds and upper bounds of the variable, i.e.,
1695 // the bounds can only involve symbolic (and local) variables. Since the
1696 // canonical form c_1*x_1 + c_2*x_2 + ... + c_0 >= 0, a constraint is a lower
1697 // bound for x_i if c_i >= 1, and an upper bound if c_i <= -1.
1698 getLowerAndUpperBoundIndices(pos, lbIndices: &lbIndices, ubIndices: &ubIndices,
1699 /*eqIndices=*/nullptr, /*offset=*/0,
1700 /*num=*/getNumDimVars());
1701
1702 std::optional<DynamicAPInt> minDiff;
1703 unsigned minLbPosition = 0, minUbPosition = 0;
1704 for (auto ubPos : ubIndices) {
1705 for (auto lbPos : lbIndices) {
1706 // Look for a lower bound and an upper bound that only differ by a
1707 // constant, i.e., pairs of the form 0 <= c_pos - f(c_i's) <= diffConst.
1708 // For example, if ii is the pos^th variable, we are looking for
1709 // constraints like ii >= i, ii <= ii + 50, 50 being the difference. The
1710 // minimum among all such constant differences is kept since that's the
1711 // constant bounding the extent of the pos^th variable.
1712 unsigned j, e;
1713 for (j = 0, e = getNumCols() - 1; j < e; j++)
1714 if (atIneq(i: ubPos, j) != -atIneq(i: lbPos, j)) {
1715 break;
1716 }
1717 if (j < getNumCols() - 1)
1718 continue;
1719 DynamicAPInt diff = ceilDiv(LHS: atIneq(i: ubPos, j: getNumCols() - 1) +
1720 atIneq(i: lbPos, j: getNumCols() - 1) + 1,
1721 RHS: atIneq(i: lbPos, j: pos));
1722 // This bound is non-negative by definition.
1723 diff = std::max<DynamicAPInt>(a: diff, b: DynamicAPInt(0));
1724 if (minDiff == std::nullopt || diff < minDiff) {
1725 minDiff = diff;
1726 minLbPosition = lbPos;
1727 minUbPosition = ubPos;
1728 }
1729 }
1730 }
1731 if (lb && minDiff) {
1732 // Set lb to the symbolic lower bound.
1733 lb->resize(N: getNumSymbolVars() + 1);
1734 if (ub)
1735 ub->resize(N: getNumSymbolVars() + 1);
1736 // The lower bound is the ceildiv of the lb constraint over the coefficient
1737 // of the variable at 'pos'. We express the ceildiv equivalently as a floor
1738 // for uniformity. For eg., if the lower bound constraint was: 32*d0 - N +
1739 // 31 >= 0, the lower bound for d0 is ceil(N - 31, 32), i.e., floor(N, 32).
1740 *boundFloorDivisor = atIneq(i: minLbPosition, j: pos);
1741 assert(*boundFloorDivisor == -atIneq(minUbPosition, pos));
1742 for (unsigned c = 0, e = getNumSymbolVars() + 1; c < e; c++) {
1743 (*lb)[c] = -atIneq(i: minLbPosition, j: getNumDimVars() + c);
1744 }
1745 if (ub) {
1746 for (unsigned c = 0, e = getNumSymbolVars() + 1; c < e; c++)
1747 (*ub)[c] = atIneq(i: minUbPosition, j: getNumDimVars() + c);
1748 }
1749 // The lower bound leads to a ceildiv while the upper bound is a floordiv
1750 // whenever the coefficient at pos != 1. ceildiv (val / d) = floordiv (val +
1751 // d - 1 / d); hence, the addition of 'atIneq(minLbPosition, pos) - 1' to
1752 // the constant term for the lower bound.
1753 (*lb)[getNumSymbolVars()] += atIneq(i: minLbPosition, j: pos) - 1;
1754 }
1755 if (minLbPos)
1756 *minLbPos = minLbPosition;
1757 if (minUbPos)
1758 *minUbPos = minUbPosition;
1759 return minDiff;
1760}
1761
1762void IntegerRelation::pruneOrthogonalConstraints(unsigned pos) {
1763 llvm::DenseSet<unsigned> relatedCols({pos}), relatedRows;
1764
1765 // Early exit if constraints is empty.
1766 unsigned numConstraints = getNumConstraints();
1767 if (numConstraints == 0)
1768 return;
1769
1770 llvm::SmallVector<unsigned> rowStack, colStack({pos});
1771 // The following code performs a graph traversal, starting from the target
1772 // variable, to identify all variables(recorded in relatedCols) and
1773 // constraints (recorded in relatedRows) belonging to the same connected
1774 // component.
1775 while (!rowStack.empty() || !colStack.empty()) {
1776 if (!rowStack.empty()) {
1777 unsigned currentRow = rowStack.pop_back_val();
1778 // Push all variable that accociated to this constraints to relatedCols
1779 // and colStack.
1780 for (unsigned colIndex = 0; colIndex < getNumVars(); ++colIndex) {
1781 if (atConstraint(i: currentRow, j: colIndex) != 0 &&
1782 relatedCols.insert(V: colIndex).second) {
1783 colStack.push_back(Elt: colIndex);
1784 }
1785 }
1786 } else {
1787 unsigned currentCol = colStack.pop_back_val();
1788 // Push all constraints that are associated with this variable to related
1789 // rows and the row stack.
1790 for (unsigned rowIndex = 0; rowIndex < numConstraints; ++rowIndex) {
1791 if (atConstraint(i: rowIndex, j: currentCol) != 0 &&
1792 relatedRows.insert(V: rowIndex).second) {
1793 rowStack.push_back(Elt: rowIndex);
1794 }
1795 }
1796 }
1797 }
1798
1799 // Prune all constraints not related to target variable.
1800 for (int constraintId = numConstraints - 1; constraintId >= 0;
1801 --constraintId) {
1802 if (!relatedRows.contains(V: constraintId))
1803 removeConstraint(pos: (unsigned)constraintId);
1804 }
1805}
1806
1807template <bool isLower>
1808std::optional<DynamicAPInt>
1809IntegerRelation::computeConstantLowerOrUpperBound(unsigned pos) {
1810 assert(pos < getNumVars() && "invalid position");
1811 // Project to 'pos'.
1812 // Prune orthogonal constraints to reduce unnecessary computations and
1813 // accelerate the bound computation.
1814 pruneOrthogonalConstraints(pos);
1815 projectOut(pos: 0, num: pos);
1816
1817 // After projecting out values, more orthogonal constraints may be exposed.
1818 // Prune these orthogonal constraints again.
1819 pruneOrthogonalConstraints(pos: 0);
1820 projectOut(pos: 1, num: getNumVars() - 1);
1821 // Check if there's an equality equating the '0'^th variable to a constant.
1822 int eqRowIdx = findEqualityToConstant(/*pos=*/0, /*symbolic=*/false);
1823 if (eqRowIdx != -1)
1824 // atEq(rowIdx, 0) is either -1 or 1.
1825 return -atEq(i: eqRowIdx, j: getNumCols() - 1) / atEq(i: eqRowIdx, j: 0);
1826
1827 // Check if the variable appears at all in any of the inequalities.
1828 unsigned r, e;
1829 for (r = 0, e = getNumInequalities(); r < e; r++) {
1830 if (atIneq(i: r, j: 0) != 0)
1831 break;
1832 }
1833 if (r == e)
1834 // If it doesn't, there isn't a bound on it.
1835 return std::nullopt;
1836
1837 std::optional<DynamicAPInt> minOrMaxConst;
1838
1839 // Take the max across all const lower bounds (or min across all constant
1840 // upper bounds).
1841 for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
1842 if (isLower) {
1843 if (atIneq(i: r, j: 0) <= 0)
1844 // Not a lower bound.
1845 continue;
1846 } else if (atIneq(i: r, j: 0) >= 0) {
1847 // Not an upper bound.
1848 continue;
1849 }
1850 unsigned c, f;
1851 for (c = 0, f = getNumCols() - 1; c < f; c++)
1852 if (c != 0 && atIneq(i: r, j: c) != 0)
1853 break;
1854 if (c < getNumCols() - 1)
1855 // Not a constant bound.
1856 continue;
1857
1858 DynamicAPInt boundConst =
1859 isLower ? ceilDiv(LHS: -atIneq(i: r, j: getNumCols() - 1), RHS: atIneq(i: r, j: 0))
1860 : floorDiv(LHS: atIneq(i: r, j: getNumCols() - 1), RHS: -atIneq(i: r, j: 0));
1861 if (isLower) {
1862 if (minOrMaxConst == std::nullopt || boundConst > minOrMaxConst)
1863 minOrMaxConst = boundConst;
1864 } else {
1865 if (minOrMaxConst == std::nullopt || boundConst < minOrMaxConst)
1866 minOrMaxConst = boundConst;
1867 }
1868 }
1869 return minOrMaxConst;
1870}
1871
1872std::optional<DynamicAPInt>
1873IntegerRelation::getConstantBound(BoundType type, unsigned pos) const {
1874 if (type == BoundType::LB)
1875 return IntegerRelation(*this)
1876 .computeConstantLowerOrUpperBound</*isLower=*/true>(pos);
1877 if (type == BoundType::UB)
1878 return IntegerRelation(*this)
1879 .computeConstantLowerOrUpperBound</*isLower=*/false>(pos);
1880
1881 assert(type == BoundType::EQ && "expected EQ");
1882 std::optional<DynamicAPInt> lb =
1883 IntegerRelation(*this).computeConstantLowerOrUpperBound</*isLower=*/true>(
1884 pos);
1885 std::optional<DynamicAPInt> ub =
1886 IntegerRelation(*this)
1887 .computeConstantLowerOrUpperBound</*isLower=*/false>(pos);
1888 return (lb && ub && *lb == *ub) ? std::optional<DynamicAPInt>(*ub)
1889 : std::nullopt;
1890}
1891
1892// A simple (naive and conservative) check for hyper-rectangularity.
1893bool IntegerRelation::isHyperRectangular(unsigned pos, unsigned num) const {
1894 assert(pos < getNumCols() - 1);
1895 // Check for two non-zero coefficients in the range [pos, pos + sum).
1896 for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
1897 unsigned sum = 0;
1898 for (unsigned c = pos; c < pos + num; c++) {
1899 if (atIneq(i: r, j: c) != 0)
1900 sum++;
1901 }
1902 if (sum > 1)
1903 return false;
1904 }
1905 for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
1906 unsigned sum = 0;
1907 for (unsigned c = pos; c < pos + num; c++) {
1908 if (atEq(i: r, j: c) != 0)
1909 sum++;
1910 }
1911 if (sum > 1)
1912 return false;
1913 }
1914 return true;
1915}
1916
1917/// Removes duplicate constraints, trivially true constraints, and constraints
1918/// that can be detected as redundant as a result of differing only in their
1919/// constant term part. A constraint of the form <non-negative constant> >= 0 is
1920/// considered trivially true.
1921// Uses a DenseSet to hash and detect duplicates followed by a linear scan to
1922// remove duplicates in place.
1923void IntegerRelation::removeTrivialRedundancy() {
1924 gcdTightenInequalities();
1925 normalizeConstraintsByGCD();
1926
1927 // A map used to detect redundancy stemming from constraints that only differ
1928 // in their constant term. The value stored is <row position, const term>
1929 // for a given row.
1930 SmallDenseMap<ArrayRef<DynamicAPInt>, std::pair<unsigned, DynamicAPInt>>
1931 rowsWithoutConstTerm;
1932
1933 // Check if constraint is of the form <non-negative-constant> >= 0.
1934 auto isTriviallyValid = [&](unsigned r) -> bool {
1935 for (unsigned c = 0, e = getNumCols() - 1; c < e; c++) {
1936 if (atIneq(i: r, j: c) != 0)
1937 return false;
1938 }
1939 return atIneq(i: r, j: getNumCols() - 1) >= 0;
1940 };
1941
1942 // Detect and mark redundant constraints.
1943 SmallVector<bool, 256> redunIneq(getNumInequalities(), false);
1944 for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
1945 DynamicAPInt *rowStart = &inequalities(r, 0);
1946 if (isTriviallyValid(r)) {
1947 redunIneq[r] = true;
1948 continue;
1949 }
1950
1951 // Among constraints that only differ in the constant term part, mark
1952 // everything other than the one with the smallest constant term redundant.
1953 // (eg: among i - 16j - 5 >= 0, i - 16j - 1 >=0, i - 16j - 7 >= 0, the
1954 // former two are redundant).
1955 DynamicAPInt constTerm = atIneq(i: r, j: getNumCols() - 1);
1956 auto rowWithoutConstTerm =
1957 ArrayRef<DynamicAPInt>(rowStart, getNumCols() - 1);
1958 const auto &ret =
1959 rowsWithoutConstTerm.insert(KV: {rowWithoutConstTerm, {r, constTerm}});
1960 if (!ret.second) {
1961 // Check if the other constraint has a higher constant term.
1962 auto &val = ret.first->second;
1963 if (val.second > constTerm) {
1964 // The stored row is redundant. Mark it so, and update with this one.
1965 redunIneq[val.first] = true;
1966 val = {r, constTerm};
1967 } else {
1968 // The one stored makes this one redundant.
1969 redunIneq[r] = true;
1970 }
1971 }
1972 }
1973
1974 // Scan to get rid of all rows marked redundant, in-place.
1975 unsigned pos = 0;
1976 for (unsigned r = 0, e = getNumInequalities(); r < e; r++)
1977 if (!redunIneq[r])
1978 inequalities.copyRow(sourceRow: r, targetRow: pos++);
1979
1980 inequalities.resizeVertically(newNRows: pos);
1981
1982 // TODO: consider doing this for equalities as well, but probably not worth
1983 // the savings.
1984}
1985
1986#undef DEBUG_TYPE
1987#define DEBUG_TYPE "fm"
1988
1989/// Eliminates variable at the specified position using Fourier-Motzkin
1990/// variable elimination. This technique is exact for rational spaces but
1991/// conservative (in "rare" cases) for integer spaces. The operation corresponds
1992/// to a projection operation yielding the (convex) set of integer points
1993/// contained in the rational shadow of the set. An emptiness test that relies
1994/// on this method will guarantee emptiness, i.e., it disproves the existence of
1995/// a solution if it says it's empty.
1996/// If a non-null isResultIntegerExact is passed, it is set to true if the
1997/// result is also integer exact. If it's set to false, the obtained solution
1998/// *may* not be exact, i.e., it may contain integer points that do not have an
1999/// integer pre-image in the original set.
2000///
2001/// Eg:
2002/// j >= 0, j <= i + 1
2003/// i >= 0, i <= N + 1
2004/// Eliminating i yields,
2005/// j >= 0, 0 <= N + 1, j - 1 <= N + 1
2006///
2007/// If darkShadow = true, this method computes the dark shadow on elimination;
2008/// the dark shadow is a convex integer subset of the exact integer shadow. A
2009/// non-empty dark shadow proves the existence of an integer solution. The
2010/// elimination in such a case could however be an under-approximation, and thus
2011/// should not be used for scanning sets or used by itself for dependence
2012/// checking.
2013///
2014/// Eg: 2-d set, * represents grid points, 'o' represents a point in the set.
2015/// ^
2016/// |
2017/// | * * * * o o
2018/// i | * * o o o o
2019/// | o * * * * *
2020/// --------------->
2021/// j ->
2022///
2023/// Eliminating i from this system (projecting on the j dimension):
2024/// rational shadow / integer light shadow: 1 <= j <= 6
2025/// dark shadow: 3 <= j <= 6
2026/// exact integer shadow: j = 1 \union 3 <= j <= 6
2027/// holes/splinters: j = 2
2028///
2029/// darkShadow = false, isResultIntegerExact = nullptr are default values.
2030// TODO: a slight modification to yield dark shadow version of FM (tightened),
2031// which can prove the existence of a solution if there is one.
2032void IntegerRelation::fourierMotzkinEliminate(unsigned pos, bool darkShadow,
2033 bool *isResultIntegerExact) {
2034 LDBG() << "FM input (eliminate pos " << pos << "):";
2035 LLVM_DEBUG(dump());
2036 assert(pos < getNumVars() && "invalid position");
2037 assert(hasConsistentState());
2038
2039 // Check if this variable can be eliminated through a substitution.
2040 for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
2041 if (atEq(i: r, j: pos) != 0) {
2042 // Use Gaussian elimination here (since we have an equality).
2043 LogicalResult ret = gaussianEliminateVar(position: pos);
2044 (void)ret;
2045 assert(ret.succeeded() && "Gaussian elimination guaranteed to succeed");
2046 LDBG() << "FM output (through Gaussian elimination):";
2047 LLVM_DEBUG(dump());
2048 return;
2049 }
2050 }
2051
2052 // A fast linear time tightening.
2053 gcdTightenInequalities();
2054
2055 // Check if the variable appears at all in any of the inequalities.
2056 if (isColZero(pos)) {
2057 // If it doesn't appear, just remove the column and return.
2058 // TODO: refactor removeColumns to use it from here.
2059 removeVar(pos);
2060 LDBG() << "FM output:";
2061 LLVM_DEBUG(dump());
2062 return;
2063 }
2064
2065 // Positions of constraints that are lower bounds on the variable.
2066 SmallVector<unsigned, 4> lbIndices;
2067 // Positions of constraints that are lower bounds on the variable.
2068 SmallVector<unsigned, 4> ubIndices;
2069 // Positions of constraints that do not involve the variable.
2070 std::vector<unsigned> nbIndices;
2071 nbIndices.reserve(n: getNumInequalities());
2072
2073 // Gather all lower bounds and upper bounds of the variable. Since the
2074 // canonical form c_1*x_1 + c_2*x_2 + ... + c_0 >= 0, a constraint is a lower
2075 // bound for x_i if c_i >= 1, and an upper bound if c_i <= -1.
2076 for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
2077 if (atIneq(i: r, j: pos) == 0) {
2078 // Var does not appear in bound.
2079 nbIndices.emplace_back(args&: r);
2080 } else if (atIneq(i: r, j: pos) >= 1) {
2081 // Lower bound.
2082 lbIndices.emplace_back(Args&: r);
2083 } else {
2084 // Upper bound.
2085 ubIndices.emplace_back(Args&: r);
2086 }
2087 }
2088
2089 PresburgerSpace newSpace = getSpace();
2090 VarKind idKindRemove = newSpace.getVarKindAt(pos);
2091 unsigned relativePos = pos - newSpace.getVarKindOffset(kind: idKindRemove);
2092 newSpace.removeVarRange(kind: idKindRemove, varStart: relativePos, varLimit: relativePos + 1);
2093
2094 /// Create the new system which has one variable less.
2095 IntegerRelation newRel(lbIndices.size() * ubIndices.size() + nbIndices.size(),
2096 getNumEqualities(), getNumCols() - 1, newSpace);
2097
2098 // This will be used to check if the elimination was integer exact.
2099 bool allLCMsAreOne = true;
2100
2101 // Let x be the variable we are eliminating.
2102 // For each lower bound, lb <= c_l*x, and each upper bound c_u*x <= ub, (note
2103 // that c_l, c_u >= 1) we have:
2104 // lb*lcm(c_l, c_u)/c_l <= lcm(c_l, c_u)*x <= ub*lcm(c_l, c_u)/c_u
2105 // We thus generate a constraint:
2106 // lcm(c_l, c_u)/c_l*lb <= lcm(c_l, c_u)/c_u*ub.
2107 // Note if c_l = c_u = 1, all integer points captured by the resulting
2108 // constraint correspond to integer points in the original system (i.e., they
2109 // have integer pre-images). Hence, if the lcm's are all 1, the elimination is
2110 // integer exact.
2111 for (auto ubPos : ubIndices) {
2112 for (auto lbPos : lbIndices) {
2113 SmallVector<DynamicAPInt, 4> ineq;
2114 ineq.reserve(N: newRel.getNumCols());
2115 DynamicAPInt lbCoeff = atIneq(i: lbPos, j: pos);
2116 // Note that in the comments above, ubCoeff is the negation of the
2117 // coefficient in the canonical form as the view taken here is that of the
2118 // term being moved to the other size of '>='.
2119 DynamicAPInt ubCoeff = -atIneq(i: ubPos, j: pos);
2120 // TODO: refactor this loop to avoid all branches inside.
2121 for (unsigned l = 0, e = getNumCols(); l < e; l++) {
2122 if (l == pos)
2123 continue;
2124 assert(lbCoeff >= 1 && ubCoeff >= 1 && "bounds wrongly identified");
2125 DynamicAPInt lcm = llvm::lcm(A: lbCoeff, B: ubCoeff);
2126 ineq.emplace_back(Args: atIneq(i: ubPos, j: l) * (lcm / ubCoeff) +
2127 atIneq(i: lbPos, j: l) * (lcm / lbCoeff));
2128 assert(lcm > 0 && "lcm should be positive!");
2129 if (lcm != 1)
2130 allLCMsAreOne = false;
2131 }
2132 if (darkShadow) {
2133 // The dark shadow is a convex subset of the exact integer shadow. If
2134 // there is a point here, it proves the existence of a solution.
2135 ineq[ineq.size() - 1] += lbCoeff * ubCoeff - lbCoeff - ubCoeff + 1;
2136 }
2137 // TODO: we need to have a way to add inequalities in-place in
2138 // IntegerRelation instead of creating and copying over.
2139 newRel.addInequality(inEq: ineq);
2140 }
2141 }
2142
2143 LDBG() << "FM isResultIntegerExact: " << allLCMsAreOne;
2144 if (allLCMsAreOne && isResultIntegerExact)
2145 *isResultIntegerExact = true;
2146
2147 // Copy over the constraints not involving this variable.
2148 for (auto nbPos : nbIndices) {
2149 SmallVector<DynamicAPInt, 4> ineq;
2150 ineq.reserve(N: getNumCols() - 1);
2151 for (unsigned l = 0, e = getNumCols(); l < e; l++) {
2152 if (l == pos)
2153 continue;
2154 ineq.emplace_back(Args&: atIneq(i: nbPos, j: l));
2155 }
2156 newRel.addInequality(inEq: ineq);
2157 }
2158
2159 assert(newRel.getNumConstraints() ==
2160 lbIndices.size() * ubIndices.size() + nbIndices.size());
2161
2162 // Copy over the equalities.
2163 for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
2164 SmallVector<DynamicAPInt, 4> eq;
2165 eq.reserve(N: newRel.getNumCols());
2166 for (unsigned l = 0, e = getNumCols(); l < e; l++) {
2167 if (l == pos)
2168 continue;
2169 eq.emplace_back(Args&: atEq(i: r, j: l));
2170 }
2171 newRel.addEquality(eq);
2172 }
2173
2174 // GCD tightening and normalization allows detection of more trivially
2175 // redundant constraints.
2176 newRel.gcdTightenInequalities();
2177 newRel.normalizeConstraintsByGCD();
2178 newRel.removeTrivialRedundancy();
2179 clearAndCopyFrom(other: newRel);
2180 LDBG() << "FM output:";
2181 LLVM_DEBUG(dump());
2182}
2183
2184#undef DEBUG_TYPE
2185#define DEBUG_TYPE "presburger"
2186
2187void IntegerRelation::projectOut(unsigned pos, unsigned num) {
2188 if (num == 0)
2189 return;
2190
2191 // 'pos' can be at most getNumCols() - 2 if num > 0.
2192 assert((getNumCols() < 2 || pos <= getNumCols() - 2) && "invalid position");
2193 assert(pos + num < getNumCols() && "invalid range");
2194
2195 // Eliminate as many variables as possible using Gaussian elimination.
2196 unsigned currentPos = pos;
2197 unsigned numToEliminate = num;
2198 unsigned numGaussianEliminated = 0;
2199
2200 while (currentPos < getNumVars()) {
2201 unsigned curNumEliminated =
2202 gaussianEliminateVars(posStart: currentPos, posLimit: currentPos + numToEliminate);
2203 ++currentPos;
2204 numToEliminate -= curNumEliminated + 1;
2205 numGaussianEliminated += curNumEliminated;
2206 }
2207
2208 // Eliminate the remaining using Fourier-Motzkin.
2209 for (unsigned i = 0; i < num - numGaussianEliminated; i++) {
2210 unsigned numToEliminate = num - numGaussianEliminated - i;
2211 fourierMotzkinEliminate(
2212 pos: getBestVarToEliminate(cst: *this, start: pos, end: pos + numToEliminate));
2213 }
2214
2215 // Fast/trivial simplifications.
2216 gcdTightenInequalities();
2217 // Normalize constraints after tightening since the latter impacts this, but
2218 // not the other way round.
2219 normalizeConstraintsByGCD();
2220}
2221
2222namespace {
2223
2224enum BoundCmpResult { Greater, Less, Equal, Unknown };
2225
2226/// Compares two affine bounds whose coefficients are provided in 'first' and
2227/// 'second'. The last coefficient is the constant term.
2228static BoundCmpResult compareBounds(ArrayRef<DynamicAPInt> a,
2229 ArrayRef<DynamicAPInt> b) {
2230 assert(a.size() == b.size());
2231
2232 // For the bounds to be comparable, their corresponding variable
2233 // coefficients should be equal; the constant terms are then compared to
2234 // determine less/greater/equal.
2235
2236 if (!std::equal(first1: a.begin(), last1: a.end() - 1, first2: b.begin()))
2237 return Unknown;
2238
2239 if (a.back() == b.back())
2240 return Equal;
2241
2242 return a.back() < b.back() ? Less : Greater;
2243}
2244} // namespace
2245
2246// Returns constraints that are common to both A & B.
2247static void getCommonConstraints(const IntegerRelation &a,
2248 const IntegerRelation &b, IntegerRelation &c) {
2249 c = IntegerRelation(a.getSpace());
2250 // a naive O(n^2) check should be enough here given the input sizes.
2251 for (unsigned r = 0, e = a.getNumInequalities(); r < e; ++r) {
2252 for (unsigned s = 0, f = b.getNumInequalities(); s < f; ++s) {
2253 if (a.getInequality(idx: r) == b.getInequality(idx: s)) {
2254 c.addInequality(inEq: a.getInequality(idx: r));
2255 break;
2256 }
2257 }
2258 }
2259 for (unsigned r = 0, e = a.getNumEqualities(); r < e; ++r) {
2260 for (unsigned s = 0, f = b.getNumEqualities(); s < f; ++s) {
2261 if (a.getEquality(idx: r) == b.getEquality(idx: s)) {
2262 c.addEquality(eq: a.getEquality(idx: r));
2263 break;
2264 }
2265 }
2266 }
2267}
2268
2269// Computes the bounding box with respect to 'other' by finding the min of the
2270// lower bounds and the max of the upper bounds along each of the dimensions.
2271LogicalResult
2272IntegerRelation::unionBoundingBox(const IntegerRelation &otherCst) {
2273 assert(space.isEqual(otherCst.getSpace()) && "Spaces should match.");
2274 assert(getNumLocalVars() == 0 && "local ids not supported yet here");
2275
2276 // Get the constraints common to both systems; these will be added as is to
2277 // the union.
2278 IntegerRelation commonCst(PresburgerSpace::getRelationSpace());
2279 getCommonConstraints(a: *this, b: otherCst, c&: commonCst);
2280
2281 std::vector<SmallVector<DynamicAPInt, 8>> boundingLbs;
2282 std::vector<SmallVector<DynamicAPInt, 8>> boundingUbs;
2283 boundingLbs.reserve(n: 2 * getNumDimVars());
2284 boundingUbs.reserve(n: 2 * getNumDimVars());
2285
2286 // To hold lower and upper bounds for each dimension.
2287 SmallVector<DynamicAPInt, 4> lb, otherLb, ub, otherUb;
2288 // To compute min of lower bounds and max of upper bounds for each dimension.
2289 SmallVector<DynamicAPInt, 4> minLb(getNumSymbolVars() + 1);
2290 SmallVector<DynamicAPInt, 4> maxUb(getNumSymbolVars() + 1);
2291 // To compute final new lower and upper bounds for the union.
2292 SmallVector<DynamicAPInt, 8> newLb(getNumCols()), newUb(getNumCols());
2293
2294 DynamicAPInt lbFloorDivisor, otherLbFloorDivisor;
2295 for (unsigned d = 0, e = getNumDimVars(); d < e; ++d) {
2296 auto extent = getConstantBoundOnDimSize(pos: d, lb: &lb, boundFloorDivisor: &lbFloorDivisor, ub: &ub);
2297 if (!extent.has_value())
2298 // TODO: symbolic extents when necessary.
2299 // TODO: handle union if a dimension is unbounded.
2300 return failure();
2301
2302 auto otherExtent = otherCst.getConstantBoundOnDimSize(
2303 pos: d, lb: &otherLb, boundFloorDivisor: &otherLbFloorDivisor, ub: &otherUb);
2304 if (!otherExtent.has_value() || lbFloorDivisor != otherLbFloorDivisor)
2305 // TODO: symbolic extents when necessary.
2306 return failure();
2307
2308 assert(lbFloorDivisor > 0 && "divisor always expected to be positive");
2309
2310 auto res = compareBounds(a: lb, b: otherLb);
2311 // Identify min.
2312 if (res == BoundCmpResult::Less || res == BoundCmpResult::Equal) {
2313 minLb = lb;
2314 // Since the divisor is for a floordiv, we need to convert to ceildiv,
2315 // i.e., i >= expr floordiv div <=> i >= (expr - div + 1) ceildiv div <=>
2316 // div * i >= expr - div + 1.
2317 minLb.back() -= lbFloorDivisor - 1;
2318 } else if (res == BoundCmpResult::Greater) {
2319 minLb = otherLb;
2320 minLb.back() -= otherLbFloorDivisor - 1;
2321 } else {
2322 // Uncomparable - check for constant lower/upper bounds.
2323 auto constLb = getConstantBound(type: BoundType::LB, pos: d);
2324 auto constOtherLb = otherCst.getConstantBound(type: BoundType::LB, pos: d);
2325 if (!constLb.has_value() || !constOtherLb.has_value())
2326 return failure();
2327 llvm::fill(Range&: minLb, Value: 0);
2328 minLb.back() = std::min(a: *constLb, b: *constOtherLb);
2329 }
2330
2331 // Do the same for ub's but max of upper bounds. Identify max.
2332 auto uRes = compareBounds(a: ub, b: otherUb);
2333 if (uRes == BoundCmpResult::Greater || uRes == BoundCmpResult::Equal) {
2334 maxUb = ub;
2335 } else if (uRes == BoundCmpResult::Less) {
2336 maxUb = otherUb;
2337 } else {
2338 // Uncomparable - check for constant lower/upper bounds.
2339 auto constUb = getConstantBound(type: BoundType::UB, pos: d);
2340 auto constOtherUb = otherCst.getConstantBound(type: BoundType::UB, pos: d);
2341 if (!constUb.has_value() || !constOtherUb.has_value())
2342 return failure();
2343 llvm::fill(Range&: maxUb, Value: 0);
2344 maxUb.back() = std::max(a: *constUb, b: *constOtherUb);
2345 }
2346
2347 llvm::fill(Range&: newLb, Value: 0);
2348 llvm::fill(Range&: newUb, Value: 0);
2349
2350 // The divisor for lb, ub, otherLb, otherUb at this point is lbDivisor,
2351 // and so it's the divisor for newLb and newUb as well.
2352 newLb[d] = lbFloorDivisor;
2353 newUb[d] = -lbFloorDivisor;
2354 // Copy over the symbolic part + constant term.
2355 llvm::copy(Range&: minLb, Out: newLb.begin() + getNumDimVars());
2356 std::transform(first: newLb.begin() + getNumDimVars(), last: newLb.end(),
2357 result: newLb.begin() + getNumDimVars(),
2358 unary_op: std::negate<DynamicAPInt>());
2359 llvm::copy(Range&: maxUb, Out: newUb.begin() + getNumDimVars());
2360
2361 boundingLbs.emplace_back(args&: newLb);
2362 boundingUbs.emplace_back(args&: newUb);
2363 }
2364
2365 // Clear all constraints and add the lower/upper bounds for the bounding box.
2366 clearConstraints();
2367 for (unsigned d = 0, e = getNumDimVars(); d < e; ++d) {
2368 addInequality(inEq: boundingLbs[d]);
2369 addInequality(inEq: boundingUbs[d]);
2370 }
2371
2372 // Add the constraints that were common to both systems.
2373 append(other: commonCst);
2374 removeTrivialRedundancy();
2375
2376 // TODO: copy over pure symbolic constraints from this and 'other' over to the
2377 // union (since the above are just the union along dimensions); we shouldn't
2378 // be discarding any other constraints on the symbols.
2379
2380 return success();
2381}
2382
2383bool IntegerRelation::isColZero(unsigned pos) const {
2384 return !findConstraintWithNonZeroAt(colIdx: pos, /*isEq=*/false) &&
2385 !findConstraintWithNonZeroAt(colIdx: pos, /*isEq=*/true);
2386}
2387
2388/// Find positions of inequalities and equalities that do not have a coefficient
2389/// for [pos, pos + num) variables.
2390static void getIndependentConstraints(const IntegerRelation &cst, unsigned pos,
2391 unsigned num,
2392 SmallVectorImpl<unsigned> &nbIneqIndices,
2393 SmallVectorImpl<unsigned> &nbEqIndices) {
2394 assert(pos < cst.getNumVars() && "invalid start position");
2395 assert(pos + num <= cst.getNumVars() && "invalid limit");
2396
2397 for (unsigned r = 0, e = cst.getNumInequalities(); r < e; r++) {
2398 // The bounds are to be independent of [offset, offset + num) columns.
2399 unsigned c;
2400 for (c = pos; c < pos + num; ++c) {
2401 if (cst.atIneq(i: r, j: c) != 0)
2402 break;
2403 }
2404 if (c == pos + num)
2405 nbIneqIndices.emplace_back(Args&: r);
2406 }
2407
2408 for (unsigned r = 0, e = cst.getNumEqualities(); r < e; r++) {
2409 // The bounds are to be independent of [offset, offset + num) columns.
2410 unsigned c;
2411 for (c = pos; c < pos + num; ++c) {
2412 if (cst.atEq(i: r, j: c) != 0)
2413 break;
2414 }
2415 if (c == pos + num)
2416 nbEqIndices.emplace_back(Args&: r);
2417 }
2418}
2419
2420void IntegerRelation::removeIndependentConstraints(unsigned pos, unsigned num) {
2421 assert(pos + num <= getNumVars() && "invalid range");
2422
2423 // Remove constraints that are independent of these variables.
2424 SmallVector<unsigned, 4> nbIneqIndices, nbEqIndices;
2425 getIndependentConstraints(cst: *this, /*pos=*/0, num, nbIneqIndices, nbEqIndices);
2426
2427 // Iterate in reverse so that indices don't have to be updated.
2428 // TODO: This method can be made more efficient (because removal of each
2429 // inequality leads to much shifting/copying in the underlying buffer).
2430 for (auto nbIndex : llvm::reverse(C&: nbIneqIndices))
2431 removeInequality(pos: nbIndex);
2432 for (auto nbIndex : llvm::reverse(C&: nbEqIndices))
2433 removeEquality(pos: nbIndex);
2434}
2435
2436IntegerPolyhedron IntegerRelation::getDomainSet() const {
2437 IntegerRelation copyRel = *this;
2438
2439 // Convert Range variables to Local variables.
2440 copyRel.convertVarKind(srcKind: VarKind::Range, varStart: 0, varLimit: getNumVarKind(kind: VarKind::Range),
2441 dstKind: VarKind::Local);
2442
2443 // Convert Domain variables to SetDim(Range) variables.
2444 copyRel.convertVarKind(srcKind: VarKind::Domain, varStart: 0, varLimit: getNumVarKind(kind: VarKind::Domain),
2445 dstKind: VarKind::SetDim);
2446
2447 return IntegerPolyhedron(std::move(copyRel));
2448}
2449
2450bool IntegerRelation::removeDuplicateConstraints() {
2451 bool changed = false;
2452 SmallDenseMap<ArrayRef<DynamicAPInt>, unsigned> hashTable;
2453 unsigned ineqs = getNumInequalities(), cols = getNumCols();
2454
2455 if (ineqs <= 1)
2456 return changed;
2457
2458 // Check if the non-constant part of the constraint is the same.
2459 ArrayRef<DynamicAPInt> row = getInequality(idx: 0).drop_back();
2460 hashTable.insert(KV: {row, 0});
2461 for (unsigned k = 1; k < ineqs; ++k) {
2462 row = getInequality(idx: k).drop_back();
2463 if (hashTable.try_emplace(Key: row, Args&: k).second)
2464 continue;
2465
2466 // For identical cases, keep only the smaller part of the constant term.
2467 unsigned l = hashTable[row];
2468 changed = true;
2469 if (atIneq(i: k, j: cols - 1) <= atIneq(i: l, j: cols - 1))
2470 inequalities.swapRows(row: k, otherRow: l);
2471 removeInequality(pos: k);
2472 --k;
2473 --ineqs;
2474 }
2475
2476 // Check the neg form of each inequality, need an extra vector to store it.
2477 SmallVector<DynamicAPInt> negIneq(cols - 1);
2478 for (unsigned k = 0; k < ineqs; ++k) {
2479 row = getInequality(idx: k).drop_back();
2480 negIneq.assign(in_start: row.begin(), in_end: row.end());
2481 for (DynamicAPInt &ele : negIneq)
2482 ele = -ele;
2483 if (!hashTable.contains(Val: negIneq))
2484 continue;
2485
2486 // For cases where the neg is the same as other inequalities, check that the
2487 // sum of their constant terms is positive.
2488 unsigned l = hashTable[row];
2489 auto sum = atIneq(i: l, j: cols - 1) + atIneq(i: k, j: cols - 1);
2490 if (sum > 0 || l == k)
2491 continue;
2492
2493 // A sum of constant terms equal to zero combines two inequalities into one
2494 // equation, less than zero means the set is empty.
2495 changed = true;
2496 if (k < l)
2497 std::swap(a&: l, b&: k);
2498 if (sum == 0) {
2499 addEquality(eq: getInequality(idx: k));
2500 removeInequality(pos: k);
2501 removeInequality(pos: l);
2502 } else {
2503 *this = getEmpty(space: getSpace());
2504 }
2505 break;
2506 }
2507
2508 return changed;
2509}
2510
2511IntegerPolyhedron IntegerRelation::getRangeSet() const {
2512 IntegerRelation copyRel = *this;
2513
2514 // Convert Domain variables to Local variables.
2515 copyRel.convertVarKind(srcKind: VarKind::Domain, varStart: 0, varLimit: getNumVarKind(kind: VarKind::Domain),
2516 dstKind: VarKind::Local);
2517
2518 // We do not need to do anything to Range variables since they are already in
2519 // SetDim position.
2520
2521 return IntegerPolyhedron(std::move(copyRel));
2522}
2523
2524void IntegerRelation::intersectDomain(const IntegerPolyhedron &poly) {
2525 assert(getDomainSet().getSpace().isCompatible(poly.getSpace()) &&
2526 "Domain set is not compatible with poly");
2527
2528 // Treating the poly as a relation, convert it from `0 -> R` to `R -> 0`.
2529 IntegerRelation rel = poly;
2530 rel.inverse();
2531
2532 // Append dummy range variables to make the spaces compatible.
2533 rel.appendVar(kind: VarKind::Range, num: getNumRangeVars());
2534
2535 // Intersect in place.
2536 mergeLocalVars(other&: rel);
2537 append(other: rel);
2538}
2539
2540void IntegerRelation::intersectRange(const IntegerPolyhedron &poly) {
2541 assert(getRangeSet().getSpace().isCompatible(poly.getSpace()) &&
2542 "Range set is not compatible with poly");
2543
2544 IntegerRelation rel = poly;
2545
2546 // Append dummy domain variables to make the spaces compatible.
2547 rel.appendVar(kind: VarKind::Domain, num: getNumDomainVars());
2548
2549 mergeLocalVars(other&: rel);
2550 append(other: rel);
2551}
2552
2553void IntegerRelation::inverse() {
2554 unsigned numRangeVars = getNumVarKind(kind: VarKind::Range);
2555 convertVarKind(srcKind: VarKind::Domain, varStart: 0, varLimit: getVarKindEnd(kind: VarKind::Domain),
2556 dstKind: VarKind::Range);
2557 convertVarKind(srcKind: VarKind::Range, varStart: 0, varLimit: numRangeVars, dstKind: VarKind::Domain);
2558}
2559
2560void IntegerRelation::compose(const IntegerRelation &rel) {
2561 assert(getRangeSet().getSpace().isCompatible(rel.getDomainSet().getSpace()) &&
2562 "Range of `this` should be compatible with Domain of `rel`");
2563
2564 IntegerRelation copyRel = rel;
2565
2566 // Let relation `this` be R1: A -> B, and `rel` be R2: B -> C.
2567 // We convert R1 to A -> (B X C), and R2 to B X C then intersect the range of
2568 // R1 with R2. After this, we get R1: A -> C, by projecting out B.
2569 // TODO: Using nested spaces here would help, since we could directly
2570 // intersect the range with another relation.
2571 unsigned numBVars = getNumRangeVars();
2572
2573 // Convert R1 from A -> B to A -> (B X C).
2574 appendVar(kind: VarKind::Range, num: copyRel.getNumRangeVars());
2575
2576 // Convert R2 to B X C.
2577 copyRel.convertVarKind(srcKind: VarKind::Domain, varStart: 0, varLimit: numBVars, dstKind: VarKind::Range, pos: 0);
2578
2579 // Intersect R2 to range of R1.
2580 intersectRange(poly: IntegerPolyhedron(copyRel));
2581
2582 // Project out B in R1.
2583 convertVarKind(srcKind: VarKind::Range, varStart: 0, varLimit: numBVars, dstKind: VarKind::Local);
2584
2585 // Eliminate local variables
2586 removeRedundantLocalVars();
2587}
2588
2589void IntegerRelation::applyDomain(const IntegerRelation &rel) {
2590 inverse();
2591 compose(rel);
2592 inverse();
2593}
2594
2595void IntegerRelation::applyRange(const IntegerRelation &rel) { compose(rel); }
2596
2597IntegerRelation IntegerRelation::rangeProduct(const IntegerRelation &rel) {
2598 /// R1: (i, j) -> k : f(i, j, k) = 0
2599 /// R2: (i, j) -> l : g(i, j, l) = 0
2600 /// R1.rangeProduct(R2): (i, j) -> (k, l) : f(i, j, k) = 0 and g(i, j, l) = 0
2601 assert(getNumDomainVars() == rel.getNumDomainVars() &&
2602 "Range product is only defined for relations with equal domains");
2603
2604 // explicit copy of `this`
2605 IntegerRelation result = *this;
2606 unsigned relRangeVarStart = rel.getVarKindOffset(kind: VarKind::Range);
2607 unsigned numThisRangeVars = getNumRangeVars();
2608 unsigned numNewSymbolVars = result.getNumSymbolVars() - getNumSymbolVars();
2609
2610 result.appendVar(kind: VarKind::Range, num: rel.getNumRangeVars());
2611
2612 // Copy each equality from `rel` and update the copy to account for range
2613 // variables from `this`. The `rel` equality is a list of coefficients of the
2614 // variables from `rel`, and so the range variables need to be shifted right
2615 // by the number of `this` range variables and symbols.
2616 for (unsigned i = 0; i < rel.getNumEqualities(); ++i) {
2617 SmallVector<DynamicAPInt> copy =
2618 SmallVector<DynamicAPInt>(rel.getEquality(idx: i));
2619 copy.insert(I: copy.begin() + relRangeVarStart,
2620 NumToInsert: numThisRangeVars + numNewSymbolVars, Elt: DynamicAPInt(0));
2621 result.addEquality(eq: copy);
2622 }
2623
2624 for (unsigned i = 0; i < rel.getNumInequalities(); ++i) {
2625 SmallVector<DynamicAPInt> copy =
2626 SmallVector<DynamicAPInt>(rel.getInequality(idx: i));
2627 copy.insert(I: copy.begin() + relRangeVarStart,
2628 NumToInsert: numThisRangeVars + numNewSymbolVars, Elt: DynamicAPInt(0));
2629 result.addInequality(inEq: copy);
2630 }
2631
2632 return result;
2633}
2634
2635void IntegerRelation::printSpace(raw_ostream &os) const {
2636 space.print(os);
2637 os << getNumConstraints() << " constraints\n";
2638}
2639
2640void IntegerRelation::removeTrivialEqualities() {
2641 for (int i = getNumEqualities() - 1; i >= 0; --i)
2642 if (rangeIsZero(range: getEquality(idx: i)))
2643 removeEquality(pos: i);
2644}
2645
2646bool IntegerRelation::isFullDim() {
2647 if (getNumVars() == 0)
2648 return true;
2649 if (isEmpty())
2650 return false;
2651
2652 // If there is a non-trivial equality, the space cannot be full-dimensional.
2653 removeTrivialEqualities();
2654 if (getNumEqualities() > 0)
2655 return false;
2656
2657 // The polytope is full-dimensional iff it is not flat along every
2658 // inequality directions that involve at least one variable.
2659 //
2660 // To check this, we first remove inequalities involving no variables,
2661 // which is done in the following function.
2662 removeTrivialRedundancy();
2663 Simplex simplex(*this);
2664 return llvm::none_of(Range: llvm::seq<int>(Size: getNumInequalities()), P: [&](int i) {
2665 return simplex.isFlatAlong(coeffs: getInequality(idx: i));
2666 });
2667}
2668
2669void IntegerRelation::mergeAndCompose(const IntegerRelation &other) {
2670 assert(getNumDomainVars() == other.getNumRangeVars() &&
2671 "Domain of this and range of other do not match");
2672 // assert(std::equal(values.begin(), values.begin() +
2673 // other.getNumDomainVars(),
2674 // otherValues.begin() + other.getNumDomainVars()) &&
2675 // "Domain of this and range of other do not match");
2676
2677 IntegerRelation result = other;
2678
2679 const unsigned thisDomain = getNumDomainVars();
2680 const unsigned thisRange = getNumRangeVars();
2681 const unsigned otherDomain = other.getNumDomainVars();
2682 const unsigned otherRange = other.getNumRangeVars();
2683
2684 // Add dimension variables temporarily to merge symbol and local vars.
2685 // Convert `this` from
2686 // [thisDomain] -> [thisRange]
2687 // to
2688 // [otherDomain thisDomain] -> [otherRange thisRange].
2689 // and `result` from
2690 // [otherDomain] -> [otherRange]
2691 // to
2692 // [otherDomain thisDomain] -> [otherRange thisRange]
2693 insertVar(kind: VarKind::Domain, pos: 0, num: otherDomain);
2694 insertVar(kind: VarKind::Range, pos: 0, num: otherRange);
2695 result.insertVar(kind: VarKind::Domain, pos: otherDomain, num: thisDomain);
2696 result.insertVar(kind: VarKind::Range, pos: otherRange, num: thisRange);
2697
2698 // Merge symbol and local variables.
2699 mergeAndAlignSymbols(other&: result);
2700 mergeLocalVars(other&: result);
2701
2702 // Convert `result` from [otherDomain thisDomain] -> [otherRange thisRange] to
2703 // [otherDomain] -> [thisRange]
2704 result.removeVarRange(kind: VarKind::Domain, varStart: otherDomain, varLimit: otherDomain + thisDomain);
2705 result.convertToLocal(kind: VarKind::Range, varStart: 0, varLimit: otherRange);
2706 // Convert `this` from [otherDomain thisDomain] -> [otherRange thisRange] to
2707 // [otherDomain] -> [thisRange]
2708 convertToLocal(kind: VarKind::Domain, varStart: otherDomain, varLimit: otherDomain + thisDomain);
2709 removeVarRange(kind: VarKind::Range, varStart: 0, varLimit: otherRange);
2710
2711 // Add and match domain of `result` to domain of `this`.
2712 for (unsigned i = 0, e = result.getNumDomainVars(); i < e; ++i)
2713 if (result.getSpace().getId(kind: VarKind::Domain, pos: i).hasValue())
2714 space.setId(kind: VarKind::Domain, pos: i,
2715 id: result.getSpace().getId(kind: VarKind::Domain, pos: i));
2716 // Add and match range of `this` to range of `result`.
2717 for (unsigned i = 0, e = getNumRangeVars(); i < e; ++i)
2718 if (space.getId(kind: VarKind::Range, pos: i).hasValue())
2719 result.space.setId(kind: VarKind::Range, pos: i, id: space.getId(kind: VarKind::Range, pos: i));
2720
2721 // Append `this` to `result` and simplify constraints.
2722 result.append(other: *this);
2723 result.removeRedundantLocalVars();
2724
2725 *this = result;
2726}
2727
2728void IntegerRelation::print(raw_ostream &os) const {
2729 assert(hasConsistentState());
2730 printSpace(os);
2731 PrintTableMetrics ptm = {.maxPreIndent: 0, .maxPostIndent: 0, .preAlign: "-"};
2732 for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
2733 for (unsigned j = 0, f = getNumCols(); j < f; ++j)
2734 updatePrintMetrics<DynamicAPInt>(val: atEq(i, j), m&: ptm);
2735 for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
2736 for (unsigned j = 0, f = getNumCols(); j < f; ++j)
2737 updatePrintMetrics<DynamicAPInt>(val: atIneq(i, j), m&: ptm);
2738 // Print using PrintMetrics.
2739 constexpr unsigned kMinSpacing = 1;
2740 for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
2741 for (unsigned j = 0, f = getNumCols(); j < f; ++j) {
2742 printWithPrintMetrics<DynamicAPInt>(os, val: atEq(i, j), minSpacing: kMinSpacing, m: ptm);
2743 }
2744 os << " = 0\n";
2745 }
2746 for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
2747 for (unsigned j = 0, f = getNumCols(); j < f; ++j) {
2748 printWithPrintMetrics<DynamicAPInt>(os, val: atIneq(i, j), minSpacing: kMinSpacing, m: ptm);
2749 }
2750 os << " >= 0\n";
2751 }
2752 os << '\n';
2753}
2754
2755#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2756void IntegerRelation::dump() const { print(llvm::errs()); }
2757#endif
2758
2759unsigned IntegerPolyhedron::insertVar(VarKind kind, unsigned pos,
2760 unsigned num) {
2761 assert((kind != VarKind::Domain || num == 0) &&
2762 "Domain has to be zero in a set");
2763 return IntegerRelation::insertVar(kind, pos, num);
2764}
2765IntegerPolyhedron
2766IntegerPolyhedron::intersect(const IntegerPolyhedron &other) const {
2767 return IntegerPolyhedron(IntegerRelation::intersect(other));
2768}
2769
2770PresburgerSet IntegerPolyhedron::subtract(const PresburgerSet &other) const {
2771 return PresburgerSet(IntegerRelation::subtract(set: other));
2772}
2773