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,158 @@ return result; } +/// Types the inequalities of `p` according to their `IneqType` for `simp` into +/// `redundantIneqs` and `cuttingIneqs`. Returns success, if no separate +/// inequalities were encountered. Otherwise, returns failure. +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(); +} + +/// 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`. `currLength` is the actual length of `polyhedrons` (without +/// the coalesced IntegerPolyhedrons at the end). +LogicalResult coalescePair(unsigned i, unsigned j, unsigned currLength, + 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[currLength - 1]; + simplices[i] = simplices[currLength - 1]; + return success(); + } + + if (simpB.isEmpty()) { + polyhedrons[j] = polyhedrons[currLength - 1]; + simplices[j] = simplices[currLength - 1]; + return success(); + } + + /// Check that all equalities are redundant in a (and in b). + bool onlyRedundantEqsA = true; + for (unsigned k = 0, e = a.getNumEqualities(); k < e; ++k) + if (!simpB.isRedundantEquality(a.getEquality(k))) { + onlyRedundantEqsA = false; + break; + } + + bool onlyRedundantEqsB = true; + for (unsigned k = 0, e = b.getNumEqualities(); k < e; ++k) + if (!simpA.isRedundantEquality(b.getEquality(k))) { + onlyRedundantEqsB = false; + break; + } + + /// If there are non-redundant equalities for both, exit early. + if (!onlyRedundantEqsB && !onlyRedundantEqsA) + return failure(); + + 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 failure(); + } + + SmallVector, 2> redundantIneqsB; + SmallVector, 2> cuttingIneqsB; + + if (typeInequalities(b, simpA, redundantIneqsB, cuttingIneqsB).failed()) { + return failure(); + } + + /// 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) { + polyhedrons[j] = polyhedrons[currLength - 1]; + simplices[j] = simplices[currLength - 1]; + return success(); + } + + if (cuttingIneqsB.size() == 0 && onlyRedundantEqsB) { + polyhedrons[i] = polyhedrons[currLength - 1]; + simplices[i] = simplices[currLength - 1]; + return success(); + } + + return failure(); +} + 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]); - - // Check whether the polytope of `simplex` is empty. If so, it is trivially - // redundant. - if (simplex.isEmpty()) { - isRedundant[i] = true; + SmallVector polyhedrons = integerPolyhedrons; + SmallVector simplices; + + unsigned n = getNumPolys(); + + unsigned coalescings = 0; + simplices.reserve(n); + for (unsigned i = 0; i < n - coalescings;) { + Simplex simp(polyhedrons[i]); + if (simp.isEmpty()) { + polyhedrons[i] = polyhedrons[n - coalescings - 1]; + coalescings++; continue; } + i++; + simplices.push_back(simp); + } - // 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]) + /// For all tuples of IntegerPolyhedrons, check whether they can be coalesced. + /// When coalescing is successful, the coalesced IntegerPolyhedrons are + /// swapped with the last two elements of `polyhedrons` and the second to last + /// element is replaced with the new coalesced IntegerPolyhedron. + for (unsigned i = 0; i < n - coalescings;) { + + /// TODO: This does some comparisons two times (index 0 with 1 and index 1 + /// with 0). + bool broken = false; + for (unsigned j = 0, e = n - coalescings; j < e; ++j) { + if (i == j) continue; - - if (simplex.isRationalSubsetOf(integerPolyhedrons[j])) { - isRedundant[i] = true; + if (coalescePair(i, j, n - coalescings, polyhedrons, simplices) + .succeeded()) { + 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; } - 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; }