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 @@ -118,6 +118,8 @@ /// The list of polyhedrons that this set is the union of. SmallVector integerPolyhedrons; + + friend class SetCoalescer; }; } // namespace presburger 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,284 +380,283 @@ 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) { - unsigned snapshot = simp.getSnapshot(); - simp.addEquality(ineq); - if (llvm::any_of(cuttingIneqs, [&simp](ArrayRef curr) { - return !simp.isRedundantInequality(curr); - })) { - simp.rollback(snapshot); - return false; - } - simp.rollback(snapshot); - return true; -} +class presburger::SetCoalescer { -/// 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) { - 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. - polyhedrons[i] = polyhedrons[n - 2]; - polyhedrons.pop_back(); - polyhedrons[n - 2] = poly; +public: + SetCoalescer(PresburgerSet s) { - simplices[i] = simplices[n - 2]; - simplices.pop_back(); - 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`. - polyhedrons[i] = polyhedrons[n - 1]; - polyhedrons[j] = polyhedrons[n - 2]; - polyhedrons.pop_back(); - polyhedrons[n - 2] = poly; + set = s; + polyhedrons = set.integerPolyhedrons; - simplices[i] = simplices[n - 1]; - simplices[j] = simplices[n - 2]; - simplices.pop_back(); - simplices[n - 2] = Simplex(poly); + 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); + } } -} -/// 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) { - /// 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); - })) - return failure(); - IntegerPolyhedron newSet(poly.getNumDimIds(), poly.getNumSymbolIds(), - poly.getNumLocalIds()); - - for (ArrayRef curr : redundantIneqsA) - newSet.addInequality(curr); + PresburgerSet 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; + } + } - for (ArrayRef curr : redundantIneqsB) - newSet.addInequality(curr); + // 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; + } - addCoalescedPolyhedron(polyhedrons, i, j, newSet, simplices); - return success(); -} + PresburgerSet newSet = + PresburgerSet::getEmptySet(set.getNumDimIds(), set.getNumSymbolIds()); + for (unsigned i = 0, e = polyhedrons.size(); i < e; ++i) + newSet.unionInPlace(polyhedrons[i]); -/// 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) { - Simplex::IneqType type = simp.findIneqType(ineq); - if (type == Simplex::IneqType::Redundant) - redundantIneqs.push_back(ineq); - else if (type == Simplex::IneqType::Cut) - cuttingIneqs.push_back(ineq); - else - return failure(); - return success(); -} + return newSet; + } -/// 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()) - return failure(); - negEqs.push_back(getNegatedCoeffs(eq)); - ArrayRef inv(negEqs.back()); - if (typeInequality(inv, simp, redundantIneqs, cuttingIneqs).failed()) - return failure(); - return success(); -} +private: + PresburgerSet set; -/// 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) { - assert(simplices.size() == polyhedrons.size() && - "simplices and polyhedrons must be equally as long"); - polyhedrons[i] = polyhedrons.back(); - polyhedrons.pop_back(); - simplices[i] = simplices.back(); - simplices.pop_back(); -} + SmallVector polyhedrons; + SmallVector simplices; -/// 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) { - - IntegerPolyhedron &a = polyhedrons[i]; - IntegerPolyhedron &b = polyhedrons[j]; - /// 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> negEqs; 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. - for (int k = 0, e = a.getNumInequalities(); k < e; ++k) - if (typeInequality(a.getInequality(k), simpB, redundantIneqsA, - cuttingIneqsA) - .failed()) - return failure(); - - for (int k = 0, e = a.getNumEqualities(); k < e; ++k) - if (typeEquality(a.getEquality(k), simpB, redundantIneqsA, cuttingIneqsA, - negEqs) - .failed()) - return failure(); SmallVector, 2> redundantIneqsB; SmallVector, 2> cuttingIneqsB; - for (int k = 0, e = b.getNumInequalities(); k < e; ++k) - if (typeInequality(b.getInequality(k), simpA, redundantIneqsB, - cuttingIneqsB) - .failed()) - return failure(); - for (int k = 0, e = b.getNumEqualities(); k < e; ++k) - if (typeEquality(b.getEquality(k), simpA, redundantIneqsB, cuttingIneqsB, - negEqs) - .failed()) + /// 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) { + unsigned snapshot = simp.getSnapshot(); + simp.addEquality(ineq); + if (llvm::any_of(cuttingIneqsB, [&simp](ArrayRef curr) { + return !simp.isRedundantInequality(curr); + })) { + simp.rollback(snapshot); + return false; + } + simp.rollback(snapshot); + 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. + void 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. + polyhedrons[i] = polyhedrons[n - 2]; + polyhedrons.pop_back(); + polyhedrons[n - 2] = poly; + + simplices[i] = simplices[n - 2]; + simplices.pop_back(); + 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`. + polyhedrons[i] = polyhedrons[n - 1]; + polyhedrons[j] = polyhedrons[n - 2]; + polyhedrons.pop_back(); + polyhedrons[n - 2] = poly; + + simplices[i] = simplices[n - 1]; + simplices[j] = simplices[n - 2]; + simplices.pop_back(); + simplices[n - 2] = Simplex(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) { + /// 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, + [this, &simp, &poly](ArrayRef curr) { + return !isFacetContained(curr, simp, poly); + })) return failure(); + IntegerPolyhedron newSet(poly.getNumDimIds(), poly.getNumSymbolIds(), + poly.getNumLocalIds()); + + for (ArrayRef curr : redundantIneqsA) + newSet.addInequality(curr); + + for (ArrayRef curr : redundantIneqsB) + newSet.addInequality(curr); - // 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); + addCoalescedPolyhedron(i, j, newSet); return success(); } - if (cuttingIneqsB.empty()) { - erasePolyhedron(i, polyhedrons, simplices); + /// 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) { + Simplex::IneqType type = simp.findIneqType(ineq); + if (type == Simplex::IneqType::Redundant) + redundantIneqsB.push_back(ineq); + else if (type == Simplex::IneqType::Cut) + cuttingIneqsB.push_back(ineq); + else + return failure(); return success(); } - // Try to apply the cut case - if (coalescePairCutCase(polyhedrons, simplices, i, j, redundantIneqsA, - cuttingIneqsA, redundantIneqsB, cuttingIneqsB) - .succeeded()) + /// 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) { + if (typeInequality(eq, simp).failed()) + return failure(); + negEqs.push_back(getNegatedCoeffs(eq)); + ArrayRef inv(negEqs.back()); + if (typeInequality(inv, simp).failed()) + return failure(); return success(); + } - if (coalescePairCutCase(polyhedrons, simplices, j, i, redundantIneqsB, - cuttingIneqsB, redundantIneqsA, cuttingIneqsA) - .succeeded()) - return success(); + /// Replaces the element at position `i` with the last element and erases + /// the last element for both `polyhedrons` and `simplices`. + void erasePolyhedron(unsigned i) { + assert(simplices.size() == polyhedrons.size() && + "simplices and polyhedrons must be equally as long"); + polyhedrons[i] = polyhedrons.back(); + polyhedrons.pop_back(); + simplices[i] = simplices.back(); + simplices.pop_back(); + } - return failure(); -} + /// 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) { + + IntegerPolyhedron &a = polyhedrons[i]; + IntegerPolyhedron &b = polyhedrons[j]; + /// 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]; + + // 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).failed()) + return failure(); + + for (int k = 0, e = a.getNumEqualities(); k < e; ++k) + if (typeEquality(a.getEquality(k), simpB).failed()) + return failure(); + + std::swap(redundantIneqsA, redundantIneqsB); + std::swap(cuttingIneqsA, cuttingIneqsB); + + for (int k = 0, e = b.getNumInequalities(); k < e; ++k) + 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).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); + return success(); + } -PresburgerSet PresburgerSet::coalesce() const { - PresburgerSet newSet = - PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds()); - SmallVector polyhedrons = integerPolyhedrons; - SmallVector simplices; + // Try to apply the cut case + if (coalescePairCutCase(i, j).succeeded()) + return success(); - 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); - } + std::swap(redundantIneqsA, redundantIneqsB); + std::swap(cuttingIneqsA, cuttingIneqsB); - // 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; - } + if (cuttingIneqsA.empty()) { + erasePolyhedron(i); + return success(); } - // 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; - } + if (coalescePairCutCase(j, i).succeeded()) + return success(); - for (unsigned i = 0, e = polyhedrons.size(); i < e; ++i) - newSet.unionInPlace(polyhedrons[i]); + return failure(); + } +}; - return newSet; +PresburgerSet PresburgerSet::coalesce() const { + return SetCoalescer(*this).coalesce(); } void PresburgerSet::print(raw_ostream &os) const {