diff --git a/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h b/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h --- a/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h +++ b/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h @@ -111,6 +111,8 @@ void dump() const; private: + friend class SetCoalescer; + /// Construct an empty PresburgerSet with the specified number of dimension /// and symbols. PresburgerSet(unsigned numDims = 0, unsigned numSymbols = 0) 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 @@ -380,16 +380,151 @@ return result; } -/// Given an IntegerPolyhedron `p` and one of its inequalities `ineq`, check -/// that all inequalities of `cuttingIneqs` are redundant for the facet of `p` -/// where `ineq` holds as an equality. `simp` must be the Simplex constructed -/// from `p`. -static bool isFacetContained(ArrayRef ineq, Simplex &simp, - IntegerPolyhedron &p, - ArrayRef> cuttingIneqs) { +/// The SetCoalescer class contains all functionality concerning the coalesce +/// heuristic. It is built from a `PresburgerSet` and has the `coalesce()` +/// function as its main API. The coalesce heuristic simplifies the +/// representation of a PresburgerSet. In particular, it removes all polyhedrons +/// which are subsets of other polyhedrons in the union and it combines sets +/// that overlap and can be combined in a convex way. +class presburger::SetCoalescer { + +public: + /// Simplifies the representation of a PresburgerSet. + PresburgerSet coalesce(); + + /// Construct a SetCoalescer from a PresburgerSet. + SetCoalescer(const PresburgerSet &s) { + + set = s; + polyhedrons = set.integerPolyhedrons; + + simplices.reserve(set.getNumPolys()); + // Note that polyhedrons.size() changes during the loop. + for (unsigned i = 0; i < polyhedrons.size();) { + Simplex simp(polyhedrons[i]); + if (simp.isEmpty()) { + polyhedrons[i] = polyhedrons[polyhedrons.size() - 1]; + polyhedrons.pop_back(); + continue; + } + ++i; + simplices.push_back(simp); + } + } + +private: + PresburgerSet set; + + SmallVector polyhedrons; + SmallVector simplices; + + SmallVector, 2> negEqs; + + SmallVector, 2> redundantIneqsA; + SmallVector, 2> cuttingIneqsA; + + SmallVector, 2> redundantIneqsB; + SmallVector, 2> cuttingIneqsB; + + /// Given an IntegerPolyhedron `p` and one of its inequalities `ineq`, check + /// that all inequalities of `cuttingIneqs` are redundant for the facet of + /// `p` where `ineq` holds as an equality. `simp` must be the Simplex + /// constructed from `p`. + bool isFacetContained(ArrayRef ineq, Simplex &simp, + IntegerPolyhedron &p); + + /// Adds `poly` to `polyhedrons` and removes the polyhedrons at position `i` + /// and `j`. Updates `simplices` to reflect the changes. `i` and `j` cannot + /// be equal. + void addCoalescedPolyhedron(unsigned i, unsigned j, + const IntegerPolyhedron &poly); + + /// Given two polyhedra `a` and `b` at positions `i` and `j` in + /// `polyhedrons` and `redundantIneqsA` being the inequalities of `a` that + /// are redundant for `b` (similarly for `cuttingIneqsA`, `redundantIneqsB`, + /// and `cuttingIneqsB`), checks whether the facets of all cutting + /// inequalites of `a` are contained in `b`. If so, a new polyhedron + /// consisting of all redundant inequalites of `a` and `b` and all + /// equalities of both is created. + /// + /// An example of this case: + /// ___________ ___________ + /// / / | / / / + /// \ \ | / ==> \ / + /// \ \ | / \ / + /// \___\|/ \_____/ + /// + /// + LogicalResult coalescePairCutCase(unsigned i, unsigned j); + + /// Types the inequality `ineq` according to its `IneqType` for `simp` into + /// `redundantIneqsB` and `cuttingIneqsB`. Returns success, if no separate + /// inequalities were encountered. Otherwise, returns failure. + LogicalResult typeInequality(ArrayRef ineq, Simplex &simp); + + /// Types the equality `eq`, i.e. for `eq` == 0, types both `eq` >= 0 and + /// -`eq` >= 0 according to their `IneqType` for `simp` into + /// `redundantIneqsB` and `cuttingIneqsB`. Returns success, if no separate + /// inequalities were encountered. Otherwise, returns failure. + LogicalResult typeEquality(ArrayRef eq, Simplex &simp); + + /// Replaces the element at position `i` with the last element and erases + /// the last element for both `polyhedrons` and `simplices`. + void erasePolyhedron(unsigned i); + + /// 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`. At this point, there are no empty + /// polyhedrons in `polyhedrons` left. + LogicalResult coalescePair(unsigned i, unsigned j); +}; + +/// Simplifies the representation of a PresburgerSet. +PresburgerSet SetCoalescer::coalesce() { + // For all tuples of IntegerPolyhedrons, check whether they can be + // coalesced. When coalescing is successful, the contained IntegerPolyhedron + // is swapped with the last element of `polyhedrons` and subsequently erased + // and similarly for simplices. + for (unsigned i = 0; i < polyhedrons.size();) { + + // TODO: This does some comparisons two times (index 0 with 1 and index 1 + // with 0). + bool broken = false; + for (unsigned j = 0, e = polyhedrons.size(); j < e; ++j) { + negEqs.clear(); + redundantIneqsA.clear(); + redundantIneqsB.clear(); + cuttingIneqsA.clear(); + cuttingIneqsB.clear(); + if (i == j) + continue; + if (coalescePair(i, j).succeeded()) { + 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 + // now at position i is not compared. + if (!broken) + ++i; + } + + PresburgerSet newSet = + PresburgerSet::getEmptySet(set.getNumDimIds(), set.getNumSymbolIds()); + for (unsigned i = 0, e = polyhedrons.size(); i < e; ++i) + newSet.unionInPlace(polyhedrons[i]); + + return newSet; +} + +bool SetCoalescer::isFacetContained(ArrayRef ineq, Simplex &simp, + IntegerPolyhedron &p) { unsigned snapshot = simp.getSnapshot(); simp.addEquality(ineq); - if (llvm::any_of(cuttingIneqs, [&simp](ArrayRef curr) { + if (llvm::any_of(cuttingIneqsB, [&simp](ArrayRef curr) { return !simp.isRedundantInequality(curr); })) { simp.rollback(snapshot); @@ -399,20 +534,14 @@ return true; } -/// Adds `poly` to `polyhedrons` and removes the polyhedrons at position `i` and -/// `j`. Updates `simplices` to reflect the changes. `i` and `j` cannot be -/// equal. -static void -addCoalescedPolyhedron(SmallVectorImpl &polyhedrons, - unsigned i, unsigned j, const IntegerPolyhedron &poly, - SmallVectorImpl &simplices) { +void SetCoalescer::addCoalescedPolyhedron(unsigned i, unsigned j, + const IntegerPolyhedron &poly) { assert(i != j && "The indices must refer to different polyhedra"); - unsigned n = polyhedrons.size(); if (j == n - 1) { - // This case needs special handling since position `n` - 1 is removed from - // the vector, hence the `IntegerPolyhedron` at position `n` - 2 is lost - // otherwise. + // This case needs special handling since position `n` - 1 is removed + // from the vector, hence the `IntegerPolyhedron` at position `n` - 2 is + // lost otherwise. polyhedrons[i] = polyhedrons[n - 2]; polyhedrons.pop_back(); polyhedrons[n - 2] = poly; @@ -422,10 +551,11 @@ simplices[n - 2] = Simplex(poly); } else { - // Other possible edge cases are correct since for `j` or `i` == `n` - 2, - // the `IntegerPolyhedron` at position `n` - 2 should be lost. The case - // `i` == `n` - 1 makes the first following statement a noop. Hence, in this - // case the same thing is done as above, but with `j` rather than `i`. + // Other possible edge cases are correct since for `j` or `i` == `n` - + // 2, the `IntegerPolyhedron` at position `n` - 2 should be lost. The + // case `i` == `n` - 1 makes the first following statement a noop. + // Hence, in this case the same thing is done as above, but with `j` + // rather than `i`. polyhedrons[i] = polyhedrons[n - 1]; polyhedrons[j] = polyhedrons[n - 2]; polyhedrons.pop_back(); @@ -438,36 +568,14 @@ } } -/// Given two polyhedra `a` and `b` at positions `i` and `j` in `polyhedrons` -/// and `redundantIneqsA` being the inequalities of `a` that are redundant for -/// `b` (similarly for `cuttingIneqsA`, `redundantIneqsB`, and `cuttingIneqsB`), -/// checks whether the facets of all cutting inequalites of `a` are contained in -/// `b`. If so, a new polyhedron consisting of all redundant inequalites of `a` -/// and `b` and all equalities of both is created. -/// -/// An example of this case: -/// ___________ ___________ -/// / / | / / / -/// \ \ | / ==> \ / -/// \ \ | / \ / -/// \___\|/ \_____/ -/// -/// -static LogicalResult -coalescePairCutCase(SmallVectorImpl &polyhedrons, - SmallVectorImpl &simplices, unsigned i, unsigned j, - ArrayRef> redundantIneqsA, - ArrayRef> cuttingIneqsA, - ArrayRef> redundantIneqsB, - ArrayRef> cuttingIneqsB) { +LogicalResult SetCoalescer::coalescePairCutCase(unsigned i, unsigned j) { /// All inequalities of `b` need to be redundant. We already know that the /// redundant ones are, so only the cutting ones remain to be checked. Simplex &simp = simplices[i]; IntegerPolyhedron &poly = polyhedrons[i]; - if (llvm::any_of(cuttingIneqsA, - [&simp, &poly, &cuttingIneqsB](ArrayRef curr) { - return !isFacetContained(curr, simp, poly, cuttingIneqsB); - })) + if (llvm::any_of(cuttingIneqsA, [this, &simp, &poly](ArrayRef curr) { + return !isFacetContained(curr, simp, poly); + })) return failure(); IntegerPolyhedron newSet(poly.getNumDimIds(), poly.getNumSymbolIds(), poly.getNumLocalIds()); @@ -478,50 +586,33 @@ for (ArrayRef curr : redundantIneqsB) newSet.addInequality(curr); - addCoalescedPolyhedron(polyhedrons, i, j, newSet, simplices); + addCoalescedPolyhedron(i, j, newSet); return success(); } -/// Types the inequality `ineq` according to its `IneqType` for `simp` into -/// `redundantIneqs` and `cuttingIneqs`. Returns success, if no separate -/// inequalities were encountered. Otherwise, returns failure. -static LogicalResult -typeInequality(ArrayRef ineq, Simplex &simp, - SmallVectorImpl> &redundantIneqs, - SmallVectorImpl> &cuttingIneqs) { +LogicalResult SetCoalescer::typeInequality(ArrayRef ineq, + Simplex &simp) { Simplex::IneqType type = simp.findIneqType(ineq); if (type == Simplex::IneqType::Redundant) - redundantIneqs.push_back(ineq); + redundantIneqsB.push_back(ineq); else if (type == Simplex::IneqType::Cut) - cuttingIneqs.push_back(ineq); + cuttingIneqsB.push_back(ineq); else return failure(); return success(); } -/// Types the equality `eq`, i.e. for `eq` == 0, types both `eq` >= 0 and -`eq` -/// >= 0 according to their `IneqType` for `simp` into `redundantIneqs` and -/// `cuttingIneqs`. Returns success, if no separate inequalities were -/// encountered. Otherwise, returns failure. -static LogicalResult -typeEquality(ArrayRef eq, Simplex &simp, - SmallVectorImpl> &redundantIneqs, - SmallVectorImpl> &cuttingIneqs, - SmallVectorImpl> &negEqs) { - if (typeInequality(eq, simp, redundantIneqs, cuttingIneqs).failed()) +LogicalResult SetCoalescer::typeEquality(ArrayRef eq, Simplex &simp) { + if (typeInequality(eq, simp).failed()) return failure(); negEqs.push_back(getNegatedCoeffs(eq)); ArrayRef inv(negEqs.back()); - if (typeInequality(inv, simp, redundantIneqs, cuttingIneqs).failed()) + if (typeInequality(inv, simp).failed()) return failure(); return success(); } -/// Replaces the element at position `i` with the last element and erases the -/// last element for both `polyhedrons` and `simplices`. -static void erasePolyhedron(unsigned i, - SmallVectorImpl &polyhedrons, - SmallVectorImpl &simplices) { +void SetCoalescer::erasePolyhedron(unsigned i) { assert(simplices.size() == polyhedrons.size() && "simplices and polyhedrons must be equally as long"); polyhedrons[i] = polyhedrons.back(); @@ -530,134 +621,69 @@ simplices.pop_back(); } -/// 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`. At this point, there are no empty polyhedrons in -/// `polyhedrons` left. -static LogicalResult -coalescePair(unsigned i, unsigned j, - SmallVectorImpl &polyhedrons, - SmallVectorImpl &simplices) { +LogicalResult SetCoalescer::coalescePair(unsigned i, unsigned j) { IntegerPolyhedron &a = polyhedrons[i]; IntegerPolyhedron &b = polyhedrons[j]; - /// Handling of local ids is not yet implemented, so these cases are skipped. + /// Handling of local ids is not yet implemented, so these cases are + /// skipped. /// TODO: implement local id support. if (a.getNumLocalIds() != 0 || b.getNumLocalIds() != 0) return failure(); Simplex &simpA = simplices[i]; Simplex &simpB = simplices[j]; - SmallVector, 2> redundantIneqsA; - SmallVector, 2> cuttingIneqsA; - SmallVector, 2> negEqs; - - // Organize all inequalities and equalities 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. + // Organize all inequalities and equalities 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. for (int k = 0, e = a.getNumInequalities(); k < e; ++k) - if (typeInequality(a.getInequality(k), simpB, redundantIneqsA, - cuttingIneqsA) - .failed()) + if (typeInequality(a.getInequality(k), simpB).failed()) return failure(); for (int k = 0, e = a.getNumEqualities(); k < e; ++k) - if (typeEquality(a.getEquality(k), simpB, redundantIneqsA, cuttingIneqsA, - negEqs) - .failed()) + if (typeEquality(a.getEquality(k), simpB).failed()) return failure(); - SmallVector, 2> redundantIneqsB; - SmallVector, 2> cuttingIneqsB; + std::swap(redundantIneqsA, redundantIneqsB); + std::swap(cuttingIneqsA, cuttingIneqsB); + for (int k = 0, e = b.getNumInequalities(); k < e; ++k) - if (typeInequality(b.getInequality(k), simpA, redundantIneqsB, - cuttingIneqsB) - .failed()) + if (typeInequality(b.getInequality(k), simpA).failed()) return failure(); for (int k = 0, e = b.getNumEqualities(); k < e; ++k) - if (typeEquality(b.getEquality(k), simpA, redundantIneqsB, cuttingIneqsB, - negEqs) - .failed()) + if (typeEquality(b.getEquality(k), simpA).failed()) return failure(); // If there are no cutting inequalities of `a`, `b` is contained // within `a` (and vice versa for `b`). if (cuttingIneqsA.empty()) { - erasePolyhedron(j, polyhedrons, simplices); + erasePolyhedron(j); return success(); } - if (cuttingIneqsB.empty()) { - erasePolyhedron(i, polyhedrons, simplices); + // Try to apply the cut case + if (coalescePairCutCase(i, j).succeeded()) return success(); - } - // Try to apply the cut case - if (coalescePairCutCase(polyhedrons, simplices, i, j, redundantIneqsA, - cuttingIneqsA, redundantIneqsB, cuttingIneqsB) - .succeeded()) + std::swap(redundantIneqsA, redundantIneqsB); + std::swap(cuttingIneqsA, cuttingIneqsB); + + if (cuttingIneqsA.empty()) { + erasePolyhedron(i); return success(); + } - if (coalescePairCutCase(polyhedrons, simplices, j, i, redundantIneqsB, - cuttingIneqsB, redundantIneqsA, cuttingIneqsA) - .succeeded()) + if (coalescePairCutCase(j, i).succeeded()) return success(); return failure(); } PresburgerSet PresburgerSet::coalesce() const { - PresburgerSet newSet = - PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds()); - SmallVector polyhedrons = integerPolyhedrons; - SmallVector simplices; - - simplices.reserve(getNumPolys()); - // Note that polyhedrons.size() changes during the loop. - for (unsigned i = 0; i < polyhedrons.size();) { - Simplex simp(polyhedrons[i]); - if (simp.isEmpty()) { - polyhedrons[i] = polyhedrons[polyhedrons.size() - 1]; - polyhedrons.pop_back(); - continue; - } - ++i; - simplices.push_back(simp); - } - - // For all tuples of IntegerPolyhedrons, check whether they can be coalesced. - // When coalescing is successful, the contained IntegerPolyhedron is swapped - // with the last element of `polyhedrons` and subsequently erased and - // similarly for simplices. - for (unsigned i = 0; i < polyhedrons.size();) { - - // TODO: This does some comparisons two times (index 0 with 1 and index 1 - // with 0). - bool broken = false; - for (unsigned j = 0, e = polyhedrons.size(); j < e; ++j) { - if (i == j) - continue; - if (coalescePair(i, j, polyhedrons, simplices).succeeded()) { - 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 - // now at position i is not compared. - if (!broken) - ++i; - } - - for (unsigned i = 0, e = polyhedrons.size(); i < e; ++i) - newSet.unionInPlace(polyhedrons[i]); - - return newSet; + return SetCoalescer(*this).coalesce(); } void PresburgerSet::print(raw_ostream &os) const {