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
@@ -395,39 +395,144 @@
   return result;
 }
 
-PresburgerSet PresburgerSet::coalesce() const {
-  PresburgerSet newSet =
-      PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds());
-  llvm::SmallBitVector isRedundant(getNumPolys());
+/// Replaces the elements of `polyhedrons` at position `i` and `j` with the
+/// IntegerPolyhedron `poly`.
+void addCoalescedPolyhedron(SmallVectorImpl<IntegerPolyhedron> &polyhedrons,
+                            unsigned i, unsigned j,
+                            const IntegerPolyhedron &poly) {
+  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));
+
+  if (i < j) {
+    polyhedrons.erase(polyhedrons.begin() + j);
+    polyhedrons.erase(polyhedrons.begin() + i);
+  } else {
+    polyhedrons.erase(polyhedrons.begin() + i);
+    polyhedrons.erase(polyhedrons.begin() + j);
+  }
 
-  for (unsigned i = 0, e = integerPolyhedrons.size(); i < e; ++i) {
-    if (isRedundant[i])
-      continue;
-    Simplex simplex(integerPolyhedrons[i]);
+  polyhedrons.push_back(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.
+bool typeInequalities(IntegerPolyhedron &p, Simplex &simp,
+                      SmallVectorImpl<ArrayRef<int64_t>> &redundantIneqs,
+                      SmallVectorImpl<ArrayRef<int64_t>> &cuttingIneqs) {
+  for (unsigned k = 0, e = p.getNumInequalities(); k < e; ++k) {
+    Simplex::IneqType type = simp.findIneqType(p.getInequality(k));
+    if (type == Simplex::IneqType::Redundant) {
+      redundantIneqs.push_back(p.getInequality(k));
+    } else if (type == Simplex::IneqType::Cut) {
+      cuttingIneqs.push_back(p.getInequality(k));
+    } else {
+      return false;
     }
+  }
+  return true;
+}
+
+/// Coalesce the two IntegerPolyhedrons at position `i` and `j` in `polyhedrons`
+/// in-place. Returns whether the polyhedrons were successfully coalesced.
+bool coalescePair(unsigned i, unsigned j,
+                  SmallVectorImpl<IntegerPolyhedron> &polyhedrons) {
+
+  IntegerPolyhedron &a = polyhedrons[i];
+  IntegerPolyhedron &b = polyhedrons[j];
+  Simplex simpA(a);
+  Simplex simpB(b);
+
+  /// If A is empty, it is trivially contained in B (and vice versa).
+  if (simpA.isEmpty()) {
+    addCoalescedPolyhedron(polyhedrons, i, j, b);
+    return true;
+  }
+
+  if (simpB.isEmpty()) {
+    addCoalescedPolyhedron(polyhedrons, i, j, a);
+    return 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<ArrayRef<int64_t>, 2> redundantIneqsA;
+  SmallVector<ArrayRef<int64_t>, 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)) {
+    return false;
+  }
 
-    // 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;
+  SmallVector<ArrayRef<int64_t>, 2> redundantIneqsB;
+  SmallVector<ArrayRef<int64_t>, 2> cuttingIneqsB;
 
-      if (simplex.isRationalSubsetOf(integerPolyhedrons[j])) {
-        isRedundant[i] = true;
+  if (!typeInequalities(b, simpA, redundantIneqsB, cuttingIneqsB)) {
+    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);
+    return true;
+  }
+
+  if (cuttingIneqsB.size() == 0 && onlyRedundantEqsB) {
+    addCoalescedPolyhedron(polyhedrons, i, j, b);
+    return true;
+  }
+
+  return false;
+}
+
+PresburgerSet PresburgerSet::coalesce() const {
+  PresburgerSet newSet =
+      PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds());
+  SmallVector<IntegerPolyhedron, 2> polyhedrons = integerPolyhedrons;
+
+  /// For all tuples of IntegerPolyhedrons, check whether they can be coalesced.
+  for (unsigned i = 0; i < polyhedrons.size(); ++i) {
+    for (unsigned j = i + 1; j < polyhedrons.size(); ++j) {
+      if (coalescePair(i, j, polyhedrons)) {
+        i--;
         break;
       }
     }
   }
 
-  for (unsigned i = 0, e = integerPolyhedrons.size(); i < e; ++i)
-    if (!isRedundant[i])
-      newSet.unionPolyInPlace(integerPolyhedrons[i]);
+  /// If the only remaining IntegerPolyhedron is empty, the set is empty.
+  if (polyhedrons.size() == 1) {
+    Simplex s(polyhedrons[0]);
+    if (s.isEmpty()) {
+      return newSet;
+    }
+  }
+
+  for (unsigned i = 0, e = polyhedrons.size(); i < e; ++i)
+    newSet.unionPolyInPlace(polyhedrons[i]);
 
   return newSet;
 }