diff --git a/mlir/include/mlir/Analysis/Presburger/Simplex.h b/mlir/include/mlir/Analysis/Presburger/Simplex.h --- a/mlir/include/mlir/Analysis/Presburger/Simplex.h +++ b/mlir/include/mlir/Analysis/Presburger/Simplex.h @@ -308,7 +308,7 @@ unsigned getNumFixedCols() const { return usingBigM ? 3u : 2u; } /// Stores whether or not a big M column is present in the tableau. - const bool usingBigM; + bool usingBigM; /// The number of rows in the tableau. unsigned nRow; diff --git a/mlir/lib/Analysis/Presburger/PresburgerSet.cpp b/mlir/lib/Analysis/Presburger/PresburgerSet.cpp --- a/mlir/lib/Analysis/Presburger/PresburgerSet.cpp +++ b/mlir/lib/Analysis/Presburger/PresburgerSet.cpp @@ -401,39 +401,182 @@ return result; } -PresburgerSet PresburgerSet::coalesce() const { - PresburgerSet newSet = - PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds()); - llvm::SmallBitVector isRedundant(getNumPolys()); - - for (unsigned i = 0, e = integerPolyhedrons.size(); i < e; ++i) { - if (isRedundant[i]) - continue; - Simplex simplex(integerPolyhedrons[i]); +/// Replaces the elements of `polyhedrons` at position `i` and `j` with the ones +/// at the end and replaces the second to last element with `poly`. Updates +/// `simplices` accordingly. +void addCoalescedPolyhedron(SmallVectorImpl &polyhedrons, + unsigned i, unsigned j, + const IntegerPolyhedron &poly, + SmallVectorImpl &simplices) { + IntegerPolyhedron newSet(poly.getNumDimIds(), poly.getNumSymbolIds()); + + for (unsigned k = 0, e = poly.getNumEqualities(); k < e; ++k) + newSet.addEquality(poly.getEquality(k)); + + for (unsigned k = 0, e = poly.getNumInequalities(); k < e; ++k) + newSet.addInequality(poly.getInequality(k)); + + polyhedrons[i] = polyhedrons[polyhedrons.size() - 1]; + polyhedrons[j] = polyhedrons[polyhedrons.size() - 2]; + polyhedrons[polyhedrons.size() - 2] = newSet; + + simplices[i] = simplices[simplices.size() - 1]; + simplices[j] = simplices[simplices.size() - 2]; + simplices[simplices.size() - 2] = Simplex(newSet); +} - // Check whether the polytope of `simplex` is empty. If so, it is trivially - // redundant. - if (simplex.isEmpty()) { - isRedundant[i] = true; - continue; +/// Types the inequalities of `p` according to their `IneqType` for `simp` into +/// `redundantIneqs` and `cuttingIneqs`. Returns true, if no separate +/// inequalities were encountered. Otherwise, returns false. +LogicalResult +typeInequalities(const IntegerPolyhedron &p, Simplex &simp, + SmallVectorImpl> &redundantIneqs, + SmallVectorImpl> &cuttingIneqs) { + for (unsigned i = 0, e = p.getNumInequalities(); i < e; ++i) { + Simplex::IneqType type = simp.findIneqType(p.getInequality(i)); + if (type == Simplex::IneqType::Redundant) { + redundantIneqs.push_back(p.getInequality(i)); + } else if (type == Simplex::IneqType::Cut) { + cuttingIneqs.push_back(p.getInequality(i)); + } else { + return failure(); } + } + return success(); +} - // Check whether `IntegerPolyhedron[i]` is contained in any Poly, that is - // different from itself and not yet marked as redundant. - for (unsigned j = 0, e = integerPolyhedrons.size(); j < e; ++j) { - if (j == i || isRedundant[j]) - continue; +/// Attempts to coalesce the two IntegerPolyhedrons at position `i` and `j` in +/// `polyhedrons` in-place. Returns whether the polyhedrons were successfully +/// coalesced. The simplices in `simplices` need to be the ones constructed from +/// `polyhedrons`. +bool coalescePair(unsigned i, unsigned j, + SmallVectorImpl &polyhedrons, + SmallVectorImpl &simplices) { + + IntegerPolyhedron &a = polyhedrons[i]; + IntegerPolyhedron &b = polyhedrons[j]; + Simplex &simpA = simplices[i]; + Simplex &simpB = simplices[j]; + + /// If A is empty, it is trivially contained in B (and vice versa). + if (simpA.isEmpty()) { + polyhedrons[i] = polyhedrons[polyhedrons.size() - 1]; + simplices[i] = simplices[simplices.size() - 1]; + return true; + } + + if (simpB.isEmpty()) { + polyhedrons[j] = polyhedrons[polyhedrons.size() - 1]; + simplices[j] = simplices[simplices.size() - 1]; + return true; + } - if (simplex.isRationalSubsetOf(integerPolyhedrons[j])) { - isRedundant[i] = true; + /// Check that all equalities are redundant in a (and in b). + bool onlyRedundantEqsA = true; + for (unsigned k = 0, e = a.getNumEqualities(); k < e && onlyRedundantEqsA; + ++k) + onlyRedundantEqsA &= simpB.isRedundantEquality(a.getEquality(k)); + + bool onlyRedundantEqsB = true; + for (unsigned k = 0, e = b.getNumEqualities(); k < e && onlyRedundantEqsB; + ++k) + onlyRedundantEqsB &= simpA.isRedundantEquality(b.getEquality(k)); + + /// If there are non-redundant equalities for both, exit early. + if (!onlyRedundantEqsB && !onlyRedundantEqsA) + return false; + + SmallVector, 2> redundantIneqsA; + SmallVector, 2> cuttingIneqsA; + + /// Organize all inequalities of `a` according to their type for `b` into + /// `redundantIneqsA` and `cuttingIneqsA` (and vice versa for all inequalities + /// of `b` according to their type in `a`). If a separate inequality is + /// encountered during typing, the two IntegerPolyhedrons cannot be coalesced. + if (typeInequalities(a, simpB, redundantIneqsA, cuttingIneqsA).failed()) { + return false; + } + + SmallVector, 2> redundantIneqsB; + SmallVector, 2> cuttingIneqsB; + + if (typeInequalities(b, simpA, redundantIneqsB, cuttingIneqsB).failed()) { + return false; + } + + /// If there are no cutting inequalities of `a` and all equalities of `a` are + /// redundant, then all constraints of `a` are redundant making `b` contained + /// within a (and vice versa for `b`). + if (cuttingIneqsA.size() == 0 && onlyRedundantEqsA) { + addCoalescedPolyhedron(polyhedrons, i, j, a, simplices); + return true; + } + + if (cuttingIneqsB.size() == 0 && onlyRedundantEqsB) { + addCoalescedPolyhedron(polyhedrons, i, j, b, simplices); + return true; + } + + return false; +} + +PresburgerSet PresburgerSet::coalesce() const { + PresburgerSet newSet = + PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds()); + SmallVector polyhedrons = integerPolyhedrons; + SmallVector simplices; + + unsigned n = getNumPolys(); + + simplices.reserve(n); + for (unsigned i = 0; i < n; ++i) + simplices.push_back(Simplex(polyhedrons[i])); + + unsigned coalescings = 0; + /// For all tuples of IntegerPolyhedrons, check whether they can be coalesced. + /// When coalescing is successfull, the coalesced IntegerPolyhedrons are + /// swapped with the last two elements of `polyhedrons` and the second to last + /// element is replaced with the new IntegerPolyhedron. + for (unsigned i = 0; i < n - coalescings;) { + + unsigned j = 0; + /// If `i` < `n` - 2 * `coalescings`, the current IntegerPolyhedron is one + /// of the initial ones, so the comparisons with the ones with smaller index + /// were handled in earlier iterations. Otherwise, the current + /// IntegerPolyhedron is a coalesced one, hence it needs to be compared to + /// all others. + if (i < n - 2 * coalescings) + j = i + 1; + + bool broken = false; + for (; j < n - coalescings; ++j) { + if (i == j) + continue; + if (coalescePair(i, j, polyhedrons, simplices)) { + coalescings++; + broken = true; break; } } + + /// Only if the inner loop was not broken, i is incremented. This is + /// required as otherwise, if a coalescing occurs, the IntegerPolyhedron + /// newly at position i is not compared. + if (!broken) + ++i; + } + + /// If there is exactly one IntegerPolyhedron remaining and it is empty, the + /// set is empty. There cannot be multiple empty IntegerPolyhedron remaining + /// as they would have been removed as subsets of each other. + if (n - coalescings == 1) { + if (simplices[0].isEmpty()) { + return newSet; + } } - for (unsigned i = 0, e = integerPolyhedrons.size(); i < e; ++i) - if (!isRedundant[i]) - newSet.unionPolyInPlace(integerPolyhedrons[i]); + for (unsigned i = 0; i < n - coalescings; ++i) + newSet.unionPolyInPlace(polyhedrons[i]); return newSet; }