[MLIR][Presburger] Add support for PresburgerRelation

[Groverkss]

Summary

This patch adds supports for union of relations (PresburgerRelation). Along
with this, support for PresburgerSet is also maintained.

This patch is part of a series of patches to add support for relations in
Presburger library.

[arjunp]

mlir/include/mlir/Analysis/Presburger/PresburgerRelation.h

9

25

31

39

Since the call will be PresburgerRelation::getEmpty() I think it's clear enough what it is

134–146

Maybe just write a common doc that says these operations are the same as on Relations, they just forward the argument and return the result as a set. And you can drop the blank lines in between IMO

mlir/lib/Analysis/Presburger/PresburgerRelation.cpp

372–373

Please change these everywhere

[Groverkss]

• Address Arjun's comments

[Groverkss]

mlir/include/mlir/Analysis/Presburger/PresburgerRelation.h

25

I replaced this with "relations" as I think the "polyhedrons" name was only for doc.

[arjunp]

mlir/include/mlir/Analysis/Presburger/PresburgerRelation.h

140

[Groverkss]

• Address Arjun's comment

mlir/include/mlir/Analysis/Presburger/PWMAFunction.h

 // tuple being an affine expression in the ids of the IntegerPolyhedron.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_ANALYSIS_PRESBURGER_PWMAFUNCTION_H
 #define MLIR_ANALYSIS_PRESBURGER_PWMAFUNCTION_H
 
 #include "mlir/Analysis/Presburger/IntegerRelation.h"
-#include "mlir/Analysis/Presburger/PresburgerSet.h"
+#include "mlir/Analysis/Presburger/PresburgerRelation.h"
 
 namespace mlir {
 namespace presburger {
 
 /// This class represents a multi-affine function whose domain is given by an
 /// IntegerPolyhedron. This can be thought of as an IntegerPolyhedron with a
 /// tuple of integer values attached to every point in the polyhedron, with the
 /// value of each element of the tuple given by an affine expression in the ids

mlir/include/mlir/Analysis/Presburger/PresburgerRelation.h

+//===- PresburgerRelation.h - MLIR PresburgerRelation Class -----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// A class to represent unions of IntegerRelations.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_H
+#define MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_H
+
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
+
+namespace mlir {
+namespace presburger {
+
+/// A PresburgerRelation represents a union of IntegerRelations that live in
+/// the same PresburgerSpace with support for union, intersection, subtraction,
+/// and complement operations, as well as sampling.
+///
+/// The IntegerRelations (relations) are stored in a vector, and the set
+/// represents the union of these relations. An empty list corresponds to
+/// the empty set.
+///
+/// Note that there are no invariants guaranteed on the list of relations
+/// other than that they are all in the same PresburgerSpace. For example, the
+/// relations may overlap with each other.
+class PresburgerRelation : public PresburgerSpace {
+public:
+  /// Return a universe set of the specified type that contains all points.
+  static PresburgerRelation getUniverse(unsigned numDomain, unsigned numRange,
+                                        unsigned numSymbols);
+
+  /// Return an empty set of the specified type that contains no points.
+  static PresburgerRelation getEmpty(unsigned numDomain = 0,
+                                     unsigned numRange = 0,
+                                     unsigned numSymbols = 0);
+
+  explicit PresburgerRelation(const IntegerRelation &disjunct);
+
+  /// Return the number of Disjuncts in the union.
+  unsigned getNumDisjuncts() const;
+
+  /// Return a reference to the list of IntegerRelations.
+  ArrayRef<IntegerRelation> getAllDisjuncts() const;
+
+  /// Return the IntegerRelation at the specified index.
+  const IntegerRelation &getDisjunct(unsigned index) const;
+
+  /// Mutate this set, turning it into the union of this set and the given
+  /// IntegerRelation.
+  void unionInPlace(const IntegerRelation &disjunct);
+
+  /// Mutate this set, turning it into the union of this set and the given set.
+  void unionInPlace(const PresburgerRelation &set);
+
+  /// Return the union of this set and the given set.
+  PresburgerRelation unionSet(const PresburgerRelation &set) const;
+
+  /// Return the intersection of this set and the given set.
+  PresburgerRelation intersect(const PresburgerRelation &set) const;
+
+  /// Return true if the set contains the given point, and false otherwise.
+  bool containsPoint(ArrayRef<int64_t> point) const;
+
+  /// Return the complement of this set. All local variables in the set must
+  /// correspond to floor divisions.
+  PresburgerRelation complement() const;
+
+  /// Return the set difference of this set and the given set, i.e.,
+  /// return `this \ set`. All local variables in `set` must correspond
+  /// to floor divisions, but local variables in `this` need not correspond to
+  /// divisions.
+  PresburgerRelation subtract(const PresburgerRelation &set) const;
+
+  /// Return true if this set is a subset of the given set, and false otherwise.
+  bool isSubsetOf(const PresburgerRelation &set) const;
+
+  /// Return true if this set is equal to the given set, and false otherwise.
+  /// All local variables in both sets must correspond to floor divisions.
+  bool isEqual(const PresburgerRelation &set) const;
+
+  /// Return true if all the sets in the union are known to be integer empty
+  /// false otherwise.
+  bool isIntegerEmpty() const;
+
+  /// Find an integer sample from the given set. This should not be called if
+  /// any of the disjuncts in the union are unbounded.
+  bool findIntegerSample(SmallVectorImpl<int64_t> &sample);
+
+  /// Compute an overapproximation of the number of integer points in the
+  /// disjunct. Symbol ids are currently not supported. If the computed
+  /// overapproximation is infinite, an empty optional is returned.
+  ///
+  /// This currently just sums up the overapproximations of the volumes of the
+  /// disjuncts, so the approximation might be far from the true volume in the
+  /// case when there is a lot of overlap between disjuncts.
+  Optional<uint64_t> computeVolume() const;
+
+  /// Simplifies the representation of a PresburgerRelation.
+  ///
+  /// In particular, removes all disjuncts which are subsets of other
+  /// disjuncts in the union.
+  PresburgerRelation coalesce() const;
+
+  /// Print the set's internal state.
+  void print(raw_ostream &os) const;
+  void dump() const;
+
+protected:
+  /// Construct an empty PresburgerRelation with the specified number of
+  /// dimension and symbols.
+  PresburgerRelation(unsigned numDomain = 0, unsigned numRange = 0,
+                     unsigned numSymbols = 0)
+      : PresburgerSpace(numDomain, numRange, numSymbols) {}
+
+  /// The list of disjuncts that this set is the union of.
+  SmallVector<IntegerRelation, 2> integerRelations;
+};
+
+class PresburgerSet : public PresburgerRelation {
+public:
+  /// Return a universe set of the specified type that contains all points.
+  static PresburgerSet getUniverse(unsigned numDims = 0,
+                                   unsigned numSymbols = 0);
+
+  /// Return an empty set of the specified type that contains no points.
+  static PresburgerSet getEmpty(unsigned numDims = 0, unsigned numSymbols = 0);
+
+  /// Create a set from a relation.
+  explicit PresburgerSet(const IntegerPolyhedron &disjunct);
+  explicit PresburgerSet(const PresburgerRelation &set);
+
+  /// These operations are the same as the ones in PresburgeRelation, they just
+  /// forward the arguement and return the result as a set instead of a
+  /// relation.
+  PresburgerSet unionSet(const PresburgerRelation &set) const;
+  PresburgerSet intersect(const PresburgerRelation &set) const;
+  PresburgerSet complement() const;
+  PresburgerSet subtract(const PresburgerRelation &set) const;
+  PresburgerSet coalesce() const;
+
+protected:
+  /// Construct an empty PresburgerRelation with the specified number of
+  /// dimension and symbols.
+  PresburgerSet(unsigned numDims = 0, unsigned numSymbols = 0)
+      : PresburgerRelation(/*numDomain=*/0, numDims, numSymbols) {}
+};
+
+} // namespace presburger
+} // namespace mlir
+
+#endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_H

mlir/include/mlir/Analysis/Presburger/PresburgerSet.h

-//===- Set.h - MLIR PresburgerSet Class -------------------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// A class to represent unions of IntegerPolyhedrons.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H
-#define MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H
-
-#include "mlir/Analysis/Presburger/IntegerRelation.h"
-
-namespace mlir {
-namespace presburger {
-
-/// A PresburgerSet represents a union of IntegerPolyhedrons that live in the
-/// same PresburgerSpace with support for union, intersection, subtraction, and
-/// complement operations, as well as sampling.
-///
-/// The IntegerPolyhedrons (polyhedrons) are stored in a vector, and the set
-/// represents the union of these polyhedrons. An empty list corresponds to the
-/// empty set.
-///
-/// Note that there are no invariants guaranteed on the list of polyhedrons
-/// other than that they are all in the same PresburgerSpace, i.e., they all
-/// have the same number of dimensions and symbols. For example, the polyhedrons
-/// may overlap each other.
-class PresburgerSet : public PresburgerSpace {
-public:
-  /// Return a universe set of the specified type that contains all points.
-  static PresburgerSet getUniverse(unsigned numDims = 0,
-                                   unsigned numSymbols = 0);
-  /// Return an empty set of the specified type that contains no points.
-  static PresburgerSet getEmptySet(unsigned numDims = 0,
-                                   unsigned numSymbols = 0);
-
-  explicit PresburgerSet(const IntegerPolyhedron &poly);
-
-  /// Return the number of Polys in the union.
-  unsigned getNumPolys() const;
-
-  /// Return a reference to the list of IntegerPolyhedrons.
-  ArrayRef<IntegerPolyhedron> getAllPolys() const;
-
-  /// Return the IntegerPolyhedron at the specified index.
-  const IntegerPolyhedron &getPoly(unsigned index) const;
-
-  /// Mutate this set, turning it into the union of this set and the given
-  /// IntegerPolyhedron.
-  void unionInPlace(const IntegerPolyhedron &poly);
-
-  /// Mutate this set, turning it into the union of this set and the given set.
-  void unionInPlace(const PresburgerSet &set);
-
-  /// Return the union of this set and the given set.
-  PresburgerSet unionSet(const PresburgerSet &set) const;
-
-  /// Return the intersection of this set and the given set.
-  PresburgerSet intersect(const PresburgerSet &set) const;
-
-  /// Return true if the set contains the given point, and false otherwise.
-  bool containsPoint(ArrayRef<int64_t> point) const;
-
-  /// Return the complement of this set. All local variables in the set must
-  /// correspond to floor divisions.
-  PresburgerSet complement() const;
-
-  /// Return the set difference of this set and the given set, i.e.,
-  /// return `this \ set`. All local variables in `set` must correspond
-  /// to floor divisions, but local variables in `this` need not correspond to
-  /// divisions.
-  PresburgerSet subtract(const PresburgerSet &set) const;
-
-  /// Return true if this set is a subset of the given set, and false otherwise.
-  bool isSubsetOf(const PresburgerSet &set) const;
-
-  /// Return true if this set is equal to the given set, and false otherwise.
-  /// All local variables in both sets must correspond to floor divisions.
-  bool isEqual(const PresburgerSet &set) const;
-
-  /// Return true if all the sets in the union are known to be integer empty
-  /// false otherwise.
-  bool isIntegerEmpty() const;
-
-  /// Find an integer sample from the given set. This should not be called if
-  /// any of the polyhedrons in the union are unbounded.
-  bool findIntegerSample(SmallVectorImpl<int64_t> &sample);
-
-  /// Compute an overapproximation of the number of integer points in the
-  /// polyhedron. Symbol ids are currently not supported. If the computed
-  /// overapproximation is infinite, an empty optional is returned.
-  ///
-  /// This currently just sums up the overapproximations of the volumes of the
-  /// disjuncts, so the approximation might be far from the true volume in the
-  /// case when there is a lot of overlap between disjuncts.
-  Optional<uint64_t> computeVolume() const;
-
-  /// Simplifies the representation of a PresburgerSet.
-  ///
-  /// In particular, removes all polyhedrons which are subsets of other
-  /// polyhedrons in the union.
-  PresburgerSet coalesce() const;
-
-  /// Print the set's internal state.
-  void print(raw_ostream &os) const;
-  void dump() const;
-
-private:
-  /// Construct an empty PresburgerSet with the specified number of dimension
-  /// and symbols.
-  PresburgerSet(unsigned numDims = 0, unsigned numSymbols = 0)
-      : PresburgerSpace(/*numDomain=*/0, /*numRange=*/numDims, numSymbols) {}
-
-  /// The list of polyhedrons that this set is the union of.
-  SmallVector<IntegerPolyhedron, 2> integerPolyhedrons;
-};
-
-} // namespace presburger
-} // namespace mlir
-
-#endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H

mlir/lib/Analysis/Presburger/CMakeLists.txt

 add_mlir_library(MLIRPresburger
   IntegerRelation.cpp
   LinearTransform.cpp
   Matrix.cpp
-  PresburgerSet.cpp
+  PresburgerRelation.cpp
   PresburgerSpace.cpp
   PWMAFunction.cpp
   Simplex.cpp
   Utils.cpp
 
   LINK_LIBS PUBLIC
   MLIRSupport
   )

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

 //===- IntegerRelation.cpp - MLIR IntegerRelation Class ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // A class to represent an relation over integer tuples. A relation is
 // represented as a constraint system over a space of tuples of integer valued
 // varaiables supporting symbolic identifiers and existential quantification.
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Analysis/Presburger/LinearTransform.h"
-#include "mlir/Analysis/Presburger/PresburgerSet.h"
+#include "mlir/Analysis/Presburger/PresburgerRelation.h"
 #include "mlir/Analysis/Presburger/Simplex.h"
 #include "mlir/Analysis/Presburger/Utils.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "presburger"
 
void IntegerRelation::append(const IntegerRelation &other) {
   for (unsigned r = 0, e = other.getNumInequalities(); r < e; r++) {
     addInequality(other.getInequality(r));
   }
   for (unsigned r = 0, e = other.getNumEqualities(); r < e; r++) {
     addEquality(other.getEquality(r));
   }
 }
 
-static IntegerPolyhedron createSetFromRelation(const IntegerRelation &rel) {
-  IntegerPolyhedron result(rel.getNumDimIds(), rel.getNumSymbolIds(),
-                           rel.getNumLocalIds());
-
-  for (unsigned i = 0, e = rel.getNumInequalities(); i < e; ++i)
-    result.addInequality(rel.getInequality(i));
-  for (unsigned i = 0, e = rel.getNumEqualities(); i < e; ++i)
-    result.addEquality(rel.getEquality(i));
-
-  return result;
-}
-
 bool IntegerRelation::isEqual(const IntegerRelation &other) const {
   assert(PresburgerLocalSpace::isEqual(other) && "Spaces must be equal.");
-  return PresburgerSet(createSetFromRelation(*this))
-      .isEqual(PresburgerSet(createSetFromRelation(other)));
+  return PresburgerRelation(*this).isEqual(PresburgerRelation(other));
 }
 
 bool IntegerRelation::isSubsetOf(const IntegerRelation &other) const {
   assert(PresburgerLocalSpace::isEqual(other) && "Spaces must be equal.");
-  return PresburgerSet(createSetFromRelation(*this))
-      .isSubsetOf(PresburgerSet(createSetFromRelation(other)));
+  return PresburgerRelation(*this).isSubsetOf(PresburgerRelation(other));
 }
 
 MaybeOptimum<SmallVector<Fraction, 8>>
 IntegerRelation::findRationalLexMin() const {
   assert(getNumSymbolIds() == 0 && "Symbols are not supported!");
   MaybeOptimum<SmallVector<Fraction, 8>> maybeLexMin =
       LexSimplex(*this).findRationalLexMin();
 

mlir/lib/Analysis/Presburger/PWMAFunction.cpp

static SmallVector<int64_t, 8> subtract(ArrayRef<int64_t> vecA,
   result.reserve(vecA.size());
   for (unsigned i = 0, e = vecA.size(); i < e; ++i)
     result.push_back(vecA[i] - vecB[i]);
   return result;
 }
 
 PresburgerSet PWMAFunction::getDomain() const {
   PresburgerSet domain =
-      PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds());
+      PresburgerSet::getEmpty(getNumDimIds(), getNumSymbolIds());
   for (const MultiAffineFunction &piece : pieces)
     domain.unionInPlace(piece.getDomain());
   return domain;
 }
 
 Optional<SmallVector<int64_t, 8>>
 MultiAffineFunction::valueAt(ArrayRef<int64_t> point) const {
   assert(getNumLocalIds() == 0 && "Local ids are not yet supported!");

mlir/lib/Analysis/Presburger/PresburgerRelation.cpp

-//===- Set.cpp - MLIR PresburgerSet Class ---------------------------------===//
+//===- PresburgerRelation.cpp - MLIR PresburgerRelation Class -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
-#include "mlir/Analysis/Presburger/PresburgerSet.h"
+#include "mlir/Analysis/Presburger/PresburgerRelation.h"
 #include "mlir/Analysis/Presburger/Simplex.h"
 #include "mlir/Analysis/Presburger/Utils.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallBitVector.h"
 
 using namespace mlir;
 using namespace presburger;
 
-PresburgerSet::PresburgerSet(const IntegerPolyhedron &poly)
-    : PresburgerSpace(poly) {
-  unionInPlace(poly);
+PresburgerRelation::PresburgerRelation(const IntegerRelation &disjunct)
+    : PresburgerSpace(disjunct) {
+  unionInPlace(disjunct);
 }
 
-unsigned PresburgerSet::getNumPolys() const {
-  return integerPolyhedrons.size();
+unsigned PresburgerRelation::getNumDisjuncts() const {
+  return integerRelations.size();
 }
 
-ArrayRef<IntegerPolyhedron> PresburgerSet::getAllPolys() const {
-  return integerPolyhedrons;
+ArrayRef<IntegerRelation> PresburgerRelation::getAllDisjuncts() const {
+  return integerRelations;
 }
 
-const IntegerPolyhedron &PresburgerSet::getPoly(unsigned index) const {
-  assert(index < integerPolyhedrons.size() && "index out of bounds!");
-  return integerPolyhedrons[index];
+const IntegerRelation &PresburgerRelation::getDisjunct(unsigned index) const {
+  assert(index < integerRelations.size() && "index out of bounds!");
+  return integerRelations[index];
 }
 
 /// Mutate this set, turning it into the union of this set and the given
-/// IntegerPolyhedron.
-void PresburgerSet::unionInPlace(const IntegerPolyhedron &poly) {
-  assert(PresburgerSpace::isEqual(poly) && "Spaces should match");
-  integerPolyhedrons.push_back(poly);
+/// IntegerRelation.
+void PresburgerRelation::unionInPlace(const IntegerRelation &disjunct) {
+  assert(PresburgerSpace::isEqual(disjunct) && "Spaces should match");
+  integerRelations.push_back(disjunct);
 }
 
 /// Mutate this set, turning it into the union of this set and the given set.
 ///
-/// This is accomplished by simply adding all the polyhedrons of the given set
+/// This is accomplished by simply adding all the disjuncts of the given set
 /// to this set.
-void PresburgerSet::unionInPlace(const PresburgerSet &set) {
+void PresburgerRelation::unionInPlace(const PresburgerRelation &set) {
   assert(PresburgerSpace::isEqual(set) && "Spaces should match");
-  for (const IntegerPolyhedron &poly : set.integerPolyhedrons)
-    unionInPlace(poly);
+  for (const IntegerRelation &disjunct : set.integerRelations)
+    unionInPlace(disjunct);
 }
 
 /// Return the union of this set and the given set.
-PresburgerSet PresburgerSet::unionSet(const PresburgerSet &set) const {
+PresburgerRelation
+PresburgerRelation::unionSet(const PresburgerRelation &set) const {
   assert(PresburgerSpace::isEqual(set) && "Spaces should match");
-  PresburgerSet result = *this;
+  PresburgerRelation result = *this;
   result.unionInPlace(set);
   return result;
 }
 
 /// A point is contained in the union iff any of the parts contain the point.
-bool PresburgerSet::containsPoint(ArrayRef<int64_t> point) const {
-  return llvm::any_of(integerPolyhedrons, [&](const IntegerPolyhedron &poly) {
-    return (poly.containsPoint(point));
+bool PresburgerRelation::containsPoint(ArrayRef<int64_t> point) const {
+  return llvm::any_of(integerRelations, [&](const IntegerRelation &disjunct) {
+    return (disjunct.containsPoint(point));
   });
 }
 
-PresburgerSet PresburgerSet::getUniverse(unsigned numDims,
+PresburgerRelation PresburgerRelation::getUniverse(unsigned numDomain,
+                                                   unsigned numRange,
                                                    unsigned numSymbols) {
-  PresburgerSet result(numDims, numSymbols);
-  result.unionInPlace(IntegerPolyhedron::getUniverse(numDims, numSymbols));
+  PresburgerRelation result(numDomain, numRange, numSymbols);
+  result.unionInPlace(
+      IntegerRelation::getUniverse(numDomain, numRange, numSymbols));
   return result;
 }
 
-PresburgerSet PresburgerSet::getEmptySet(unsigned numDims,
+PresburgerRelation PresburgerRelation::getEmpty(unsigned numDomain,
+                                                unsigned numRange,
                                                 unsigned numSymbols) {
-  return PresburgerSet(numDims, numSymbols);
+  return PresburgerRelation(numDomain, numRange, numSymbols);
 }
 
 // Return the intersection of this set with the given set.
 //
 // We directly compute (S_1 or S_2 ...) and (T_1 or T_2 ...)
 // as (S_1 and T_1) or (S_1 and T_2) or ...
 //
 // If S_i or T_j have local variables, then S_i and T_j contains the local
 // variables of both.
-PresburgerSet PresburgerSet::intersect(const PresburgerSet &set) const {
+PresburgerRelation
+PresburgerRelation::intersect(const PresburgerRelation &set) const {
   assert(PresburgerSpace::isEqual(set) && "Spaces should match");
 
-  PresburgerSet result(getNumDimIds(), getNumSymbolIds());
-  for (const IntegerPolyhedron &csA : integerPolyhedrons) {
-    for (const IntegerPolyhedron &csB : set.integerPolyhedrons) {
-      IntegerPolyhedron csACopy = csA, csBCopy = csB;
+  PresburgerRelation result(getNumDomainIds(), getNumRangeIds(),
+                            getNumSymbolIds());
+  for (const IntegerRelation &csA : integerRelations) {
+    for (const IntegerRelation &csB : set.integerRelations) {
+      IntegerRelation csACopy = csA, csBCopy = csB;
       csACopy.mergeLocalIds(csBCopy);
       csACopy.append(csBCopy);
       if (!csACopy.isEmpty())
         result.unionInPlace(csACopy);
     }
   }
   return result;
 }
static SmallVector<int64_t, 8> getComplementIneq(ArrayRef<int64_t> ineq) {
   return coeffs;
 }
 
 /// Return the set difference b \ s and accumulate the result into `result`.
 /// `simplex` must correspond to b.
 ///
 /// In the following, U denotes union, ^ denotes intersection, \ denotes set
 /// difference and ~ denotes complement.
-/// Let b be the IntegerPolyhedron and s = (U_i s_i) be the set. We want
+/// Let b be the IntegerRelation and s = (U_i s_i) be the set. We want
 /// b \ (U_i s_i).
 ///
 /// Let s_i = ^_j s_ij, where each s_ij is a single inequality. To compute
 /// b \ s_i = b ^ ~s_i, we partition s_i based on the first violated inequality:
 /// ~s_i = (~s_i1) U (s_i1 ^ ~s_i2) U (s_i1 ^ s_i2 ^ ~s_i3) U ...
 /// And the required result is (b ^ ~s_i1) U (b ^ s_i1 ^ ~s_i2) U ...
 /// We recurse by subtracting U_{j > i} S_j from each of these parts and
 /// returning the union of the results. Each equality is handled as a
 /// conjunction of two inequalities.
 ///
 /// Note that the same approach works even if an inequality involves a floor
 /// division. For example, the complement of x <= 7*floor(x/7) is still
 /// x > 7*floor(x/7). Since b \ s_i contains the inequalities of both b and s_i
 /// (or the complements of those inequalities), b \ s_i may contain the
 /// divisions present in both b and s_i. Therefore, we need to add the local
 /// division variables of both b and s_i to each part in the result. This means
 /// adding the local variables of both b and s_i, as well as the corresponding
 /// division inequalities to each part. Since the division inequalities are
 /// added to each part, we can skip the parts where the complement of any
 /// division inequality is added, as these parts will become empty anyway.
 ///
 /// As a heuristic, we try adding all the constraints and check if simplex
 /// says that the intersection is empty. If it is, then subtracting this
-/// polyhedrons is a no-op and we just skip it. Also, in the process we find out
+/// disjuncts is a no-op and we just skip it. Also, in the process we find out
 /// that some constraints are redundant. These redundant constraints are
 /// ignored.
 ///
 /// b and simplex are callee saved, i.e., their values on return are
 /// semantically equivalent to their values when the function is called.
-static void subtractRecursively(IntegerPolyhedron &b, Simplex &simplex,
-                                const PresburgerSet &s, unsigned i,
-                                PresburgerSet &result) {
-  if (i == s.getNumPolys()) {
+static void subtractRecursively(IntegerRelation &b, Simplex &simplex,
+                                const PresburgerRelation &s, unsigned i,
+                                PresburgerRelation &result) {
+  if (i == s.getNumDisjuncts()) {
     result.unionInPlace(b);
     return;
   }
-  IntegerPolyhedron sI = s.getPoly(i);
+  IntegerRelation sI = s.getDisjunct(i);
 
   // Below, we append some additional constraints and ids to b. We want to
   // rollback b to its initial state before returning, which we will do by
   // removing all constraints beyond the original number of inequalities
   // and equalities, so we store these counts first.
   const unsigned bInitNumIneqs = b.getNumInequalities();
   const unsigned bInitNumEqs = b.getNumEqualities();
   const unsigned bInitNumLocals = b.getNumLocalIds();
for (unsigned j = 0, e = sI.getNumEqualities(); j < e; ++j) {
     // check for division inequalities here.
     if (!isMarkedRedundant[offset + 2 * j])
       processInequality(coeffs);
     if (!isMarkedRedundant[offset + 2 * j + 1])
       processInequality(getNegatedCoeffs(coeffs));
   }
 }
 
-/// Return the set difference poly \ set.
+/// Return the set difference disjunct \ set.
 ///
-/// The polyhedron here is modified in subtractRecursively, so it cannot be a
+/// The disjunct here is modified in subtractRecursively, so it cannot be a
 /// const reference even though it is restored to its original state before
 /// returning from that function.
-static PresburgerSet getSetDifference(IntegerPolyhedron poly,
-                                      const PresburgerSet &set) {
-  assert(poly.PresburgerSpace::isEqual(set) && "Spaces should match");
-  if (poly.isEmptyByGCDTest())
-    return PresburgerSet::getEmptySet(poly.getNumDimIds(),
-                                      poly.getNumSymbolIds());
-
-  PresburgerSet result =
-      PresburgerSet::getEmptySet(poly.getNumDimIds(), poly.getNumSymbolIds());
-  Simplex simplex(poly);
-  subtractRecursively(poly, simplex, set, 0, result);
+static PresburgerRelation getSetDifference(IntegerRelation disjunct,
+                                           const PresburgerRelation &set) {
+  assert(disjunct.PresburgerSpace::isEqual(set) && "Spaces should match");
+  if (disjunct.isEmptyByGCDTest())
+    return PresburgerRelation::getEmpty(disjunct.getNumDomainIds(),
+                                        disjunct.getNumRangeIds(),
+                                        disjunct.getNumSymbolIds());
+
+  PresburgerRelation result = PresburgerRelation::getEmpty(
+      disjunct.getNumDomainIds(), disjunct.getNumRangeIds(),
+      disjunct.getNumSymbolIds());
+  Simplex simplex(disjunct);
+  subtractRecursively(disjunct, simplex, set, 0, result);
   return result;
 }
 
 /// Return the complement of this set.
-PresburgerSet PresburgerSet::complement() const {
-  return getSetDifference(
-      IntegerPolyhedron::getUniverse(getNumDimIds(), getNumSymbolIds()), *this);
+PresburgerRelation PresburgerRelation::complement() const {
+  return getSetDifference(IntegerRelation::getUniverse(getNumDomainIds(),
+                                                       getNumRangeIds(),
+                                                       getNumSymbolIds()),
+                          *this);
 }
 
 /// Return the result of subtract the given set from this set, i.e.,
 /// return `this \ set`.
-PresburgerSet PresburgerSet::subtract(const PresburgerSet &set) const {
+PresburgerRelation
+PresburgerRelation::subtract(const PresburgerRelation &set) const {
   assert(PresburgerSpace::isEqual(set) && "Spaces should match");
-  PresburgerSet result(getNumDimIds(), getNumSymbolIds());
+  PresburgerRelation result(getNumDomainIds(), getNumRangeIds(),
+                            getNumSymbolIds());
   // We compute (U_i t_i) \ (U_i set_i) as U_i (t_i \ V_i set_i).
-  for (const IntegerPolyhedron &poly : integerPolyhedrons)
-    result.unionInPlace(getSetDifference(poly, set));
+  for (const IntegerRelation &disjunct : integerRelations)
+    result.unionInPlace(getSetDifference(disjunct, set));
   return result;
 }
 
 /// T is a subset of S iff T \ S is empty, since if T \ S contains a
 /// point then this is a point that is contained in T but not S, and
 /// if T contains a point that is not in S, this also lies in T \ S.
-bool PresburgerSet::isSubsetOf(const PresburgerSet &set) const {
+bool PresburgerRelation::isSubsetOf(const PresburgerRelation &set) const {
   return this->subtract(set).isIntegerEmpty();
 }
 
 /// Two sets are equal iff they are subsets of each other.
-bool PresburgerSet::isEqual(const PresburgerSet &set) const {
+bool PresburgerRelation::isEqual(const PresburgerRelation &set) const {
   assert(PresburgerSpace::isEqual(set) && "Spaces should match");
   return this->isSubsetOf(set) && set.isSubsetOf(*this);
 }
 
 /// Return true if all the sets in the union are known to be integer empty,
 /// false otherwise.
-bool PresburgerSet::isIntegerEmpty() const {
+bool PresburgerRelation::isIntegerEmpty() const {
   // The set is empty iff all of the disjuncts are empty.
-  return std::all_of(
-      integerPolyhedrons.begin(), integerPolyhedrons.end(),
-      [](const IntegerPolyhedron &poly) { return poly.isIntegerEmpty(); });
+  return std::all_of(integerRelations.begin(), integerRelations.end(),
+                     [](const IntegerRelation &disjunct) {
+                       return disjunct.isIntegerEmpty();
+                     });
 }
 
-bool PresburgerSet::findIntegerSample(SmallVectorImpl<int64_t> &sample) {
+bool PresburgerRelation::findIntegerSample(SmallVectorImpl<int64_t> &sample) {
   // A sample exists iff any of the disjuncts contains a sample.
-  for (const IntegerPolyhedron &poly : integerPolyhedrons) {
-    if (Optional<SmallVector<int64_t, 8>> opt = poly.findIntegerSample()) {
+  for (const IntegerRelation &disjunct : integerRelations) {
+    if (Optional<SmallVector<int64_t, 8>> opt = disjunct.findIntegerSample()) {
       sample = std::move(*opt);
       return true;
     }
   }
   return false;
 }
 
-Optional<uint64_t> PresburgerSet::computeVolume() const {
+Optional<uint64_t> PresburgerRelation::computeVolume() const {
   assert(getNumSymbolIds() == 0 && "Symbols are not yet supported!");
   // The sum of the volumes of the disjuncts is a valid overapproximation of the
   // volume of their union, even if they overlap.
   uint64_t result = 0;
-  for (const IntegerPolyhedron &poly : integerPolyhedrons) {
-    Optional<uint64_t> volume = poly.computeVolume();
+  for (const IntegerRelation &disjunct : integerRelations) {
+    Optional<uint64_t> volume = disjunct.computeVolume();
     if (!volume)
       return {};
     result += *volume;
   }
   return result;
 }
 
-/// Given an IntegerPolyhedron `p` and one of its inequalities `ineq`, check
+/// Given an IntegerRelation `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<int64_t> ineq, Simplex &simp,
-                             IntegerPolyhedron &p,
+                             IntegerRelation &p,
                              ArrayRef<ArrayRef<int64_t>> cuttingIneqs) {
   unsigned snapshot = simp.getSnapshot();
   simp.addEquality(ineq);
   if (llvm::any_of(cuttingIneqs, [&simp](ArrayRef<int64_t> 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
+/// Adds `disjunct` to `disjuncts` and removes the disjuncts at position `i` and
 /// `j`. Updates `simplices` to reflect the changes. `i` and `j` cannot be
 /// equal.
-static void
-addCoalescedPolyhedron(SmallVectorImpl<IntegerPolyhedron> &polyhedrons,
-                       unsigned i, unsigned j, const IntegerPolyhedron &poly,
+static void addCoalescedDisjunct(SmallVectorImpl<IntegerRelation> &disjuncts,
+                                 unsigned i, unsigned j,
+                                 const IntegerRelation &disjunct,
                                  SmallVectorImpl<Simplex> &simplices) {
-  assert(i != j && "The indices must refer to different polyhedra");
+  assert(i != j && "The indices must refer to different disjuncts");
 
-  unsigned n = polyhedrons.size();
+  unsigned n = disjuncts.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
+    // the vector, hence the `IntegerRelation` at position `n` - 2 is lost
     // otherwise.
-    polyhedrons[i] = polyhedrons[n - 2];
-    polyhedrons.pop_back();
-    polyhedrons[n - 2] = poly;
+    disjuncts[i] = disjuncts[n - 2];
+    disjuncts.pop_back();
+    disjuncts[n - 2] = disjunct;
 
     simplices[i] = simplices[n - 2];
     simplices.pop_back();
-    simplices[n - 2] = Simplex(poly);
+    simplices[n - 2] = Simplex(disjunct);
 
   } 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
+    // the `IntegerRelation` 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;
+    disjuncts[i] = disjuncts[n - 1];
+    disjuncts[j] = disjuncts[n - 2];
+    disjuncts.pop_back();
+    disjuncts[n - 2] = disjunct;
 
     simplices[i] = simplices[n - 1];
     simplices[j] = simplices[n - 2];
     simplices.pop_back();
-    simplices[n - 2] = Simplex(poly);
+    simplices[n - 2] = Simplex(disjunct);
   }
 }
 
-/// Given two polyhedra `a` and `b` at positions `i` and `j` in `polyhedrons`
+/// Given two disjuncts `a` and `b` at positions `i` and `j` in `disjuncts`
 /// 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`
+/// `b`. If so, a new disjunct 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<IntegerPolyhedron> &polyhedrons,
+coalescePairCutCase(SmallVectorImpl<IntegerRelation> &disjuncts,
                     SmallVectorImpl<Simplex> &simplices, unsigned i, unsigned j,
                     ArrayRef<ArrayRef<int64_t>> redundantIneqsA,
                     ArrayRef<ArrayRef<int64_t>> cuttingIneqsA,
                     ArrayRef<ArrayRef<int64_t>> redundantIneqsB,
                     ArrayRef<ArrayRef<int64_t>> 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<int64_t> curr) {
-                     return !isFacetContained(curr, simp, poly, cuttingIneqsB);
-                   }))
+  IntegerRelation &disjunct = disjuncts[i];
+  if (llvm::any_of(cuttingIneqsA, [&simp, &disjunct,
+                                   &cuttingIneqsB](ArrayRef<int64_t> curr) {
+        return !isFacetContained(curr, simp, disjunct, cuttingIneqsB);
     return failure();
-  IntegerPolyhedron newSet(poly.getNumDimIds(), poly.getNumSymbolIds(),
-                           poly.getNumLocalIds());
+  IntegerRelation newSet(disjunct.getNumDomainIds(), disjunct.getNumRangeIds(),
+                         disjunct.getNumSymbolIds(), disjunct.getNumLocalIds());
 
   for (ArrayRef<int64_t> curr : redundantIneqsA)
     newSet.addInequality(curr);
 
   for (ArrayRef<int64_t> curr : redundantIneqsB)
     newSet.addInequality(curr);
 
-  addCoalescedPolyhedron(polyhedrons, i, j, newSet, simplices);
+  addCoalescedDisjunct(disjuncts, i, j, newSet, simplices);
   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<int64_t> ineq, Simplex &simp,
typeEquality(ArrayRef<int64_t> eq, Simplex &simp,
   negEqs.push_back(getNegatedCoeffs(eq));
   ArrayRef<int64_t> inv(negEqs.back());
   if (typeInequality(inv, simp, redundantIneqs, cuttingIneqs).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<IntegerPolyhedron> &polyhedrons,
-                            SmallVectorImpl<Simplex> &simplices) {
-  assert(simplices.size() == polyhedrons.size() &&
-         "simplices and polyhedrons must be equally as long");
-  polyhedrons[i] = polyhedrons.back();
-  polyhedrons.pop_back();
+/// last element for both `disjuncts` and `simplices`.
+static void eraseDisjunct(unsigned i,
+                          SmallVectorImpl<IntegerRelation> &disjuncts,
+  assert(simplices.size() == disjuncts.size() &&
+         "simplices and disjuncts must be equally as long");
+  disjuncts[i] = disjuncts.back();
+  disjuncts.pop_back();
   simplices[i] = simplices.back();
   simplices.pop_back();
 }
 
-/// Attempts to coalesce the two IntegerPolyhedrons at position `i` and `j` in
-/// `polyhedrons` in-place. Returns whether the polyhedrons were successfully
+/// Attempts to coalesce the two IntegerRelations at position `i` and `j` in
+/// `disjuncts` in-place. Returns whether the disjuncts 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<IntegerPolyhedron> &polyhedrons,
+/// `disjuncts`. At this point, there are no empty disjuncts in
+/// `disjuncts` left.
+static LogicalResult coalescePair(unsigned i, unsigned j,
+                                  SmallVectorImpl<IntegerRelation> &disjuncts,
                                   SmallVectorImpl<Simplex> &simplices) {
 
-  IntegerPolyhedron &a = polyhedrons[i];
-  IntegerPolyhedron &b = polyhedrons[j];
+  IntegerRelation &a = disjuncts[i];
+  IntegerRelation &b = disjuncts[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<ArrayRef<int64_t>, 2> redundantIneqsA;
   SmallVector<ArrayRef<int64_t>, 2> cuttingIneqsA;
   SmallVector<SmallVector<int64_t, 2>, 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
+  // inequality is encountered during typing, the two IntegerRelations 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)
for (int k = 0, e = b.getNumEqualities(); k < e; ++k)
     if (typeEquality(b.getEquality(k), simpA, redundantIneqsB, cuttingIneqsB,
                      negEqs)
             .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);
+    eraseDisjunct(j, disjuncts, simplices);
     return success();
   }
 
   if (cuttingIneqsB.empty()) {
-    erasePolyhedron(i, polyhedrons, simplices);
+    eraseDisjunct(i, disjuncts, simplices);
     return success();
   }
 
   // Try to apply the cut case
-  if (coalescePairCutCase(polyhedrons, simplices, i, j, redundantIneqsA,
+  if (coalescePairCutCase(disjuncts, simplices, i, j, redundantIneqsA,
                           cuttingIneqsA, redundantIneqsB, cuttingIneqsB)
           .succeeded())
     return success();
 
-  if (coalescePairCutCase(polyhedrons, simplices, j, i, redundantIneqsB,
+  if (coalescePairCutCase(disjuncts, simplices, j, i, redundantIneqsB,
                           cuttingIneqsB, redundantIneqsA, cuttingIneqsA)
           .succeeded())
     return success();
 
   return failure();
 }
 
-PresburgerSet PresburgerSet::coalesce() const {
-  PresburgerSet newSet =
-      PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds());
-  SmallVector<IntegerPolyhedron, 2> polyhedrons = integerPolyhedrons;
+PresburgerRelation PresburgerRelation::coalesce() const {
+  PresburgerRelation newSet = PresburgerRelation::getEmpty(
+      getNumDomainIds(), getNumRangeIds(), getNumSymbolIds());
+  SmallVector<IntegerRelation, 2> disjuncts = integerRelations;
   SmallVector<Simplex, 2> simplices;
 
-  simplices.reserve(getNumPolys());
-  // Note that polyhedrons.size() changes during the loop.
-  for (unsigned i = 0; i < polyhedrons.size();) {
-    Simplex simp(polyhedrons[i]);
+  simplices.reserve(getNumDisjuncts());
+  // Note that disjuncts.size() changes during the loop.
+  for (unsigned i = 0; i < disjuncts.size();) {
+    Simplex simp(disjuncts[i]);
     if (simp.isEmpty()) {
-      polyhedrons[i] = polyhedrons[polyhedrons.size() - 1];
-      polyhedrons.pop_back();
+      disjuncts[i] = disjuncts[disjuncts.size() - 1];
+      disjuncts.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
+  // For all tuples of IntegerRelations, check whether they can be coalesced.
+  // When coalescing is successful, the contained IntegerRelation is swapped
+  // with the last element of `disjuncts` and subsequently erased and
   // similarly for simplices.
-  for (unsigned i = 0; i < polyhedrons.size();) {
+  for (unsigned i = 0; i < disjuncts.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) {
+    for (unsigned j = 0, e = disjuncts.size(); j < e; ++j) {
       if (i == j)
         continue;
-      if (coalescePair(i, j, polyhedrons, simplices).succeeded()) {
+      if (coalescePair(i, j, disjuncts, 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
+    // required as otherwise, if a coalescing occurs, the IntegerRelation
     // now at position i is not compared.
     if (!broken)
       ++i;
   }
 
-  for (unsigned i = 0, e = polyhedrons.size(); i < e; ++i)
-    newSet.unionInPlace(polyhedrons[i]);
+  for (unsigned i = 0, e = disjuncts.size(); i < e; ++i)
+    newSet.unionInPlace(disjuncts[i]);
 
   return newSet;
 }
 
-void PresburgerSet::print(raw_ostream &os) const {
-  os << "Number of Polyhedrons: " << getNumPolys() << "\n";
-  for (const IntegerPolyhedron &poly : integerPolyhedrons) {
-    poly.print(os);
+void PresburgerRelation::print(raw_ostream &os) const {
+  os << "Number of Disjuncts: " << getNumDisjuncts() << "\n";
+  for (const IntegerRelation &disjunct : integerRelations) {
+    disjunct.print(os);
     os << '\n';
   }
 }
 
-void PresburgerSet::dump() const { print(llvm::errs()); }
+void PresburgerRelation::dump() const { print(llvm::errs()); }
+
+PresburgerSet PresburgerSet::getUniverse(unsigned numDims,
+                                         unsigned numSymbols) {
+  PresburgerSet result(numDims, numSymbols);
+  result.unionInPlace(IntegerPolyhedron::getUniverse(numDims, numSymbols));
+  return result;
+}
+
+PresburgerSet PresburgerSet::getEmpty(unsigned numDims, unsigned numSymbols) {
+  return PresburgerSet(numDims, numSymbols);
+}
+
+PresburgerSet::PresburgerSet(const IntegerPolyhedron &disjunct)
+    : PresburgerRelation(disjunct) {}
+
+PresburgerSet::PresburgerSet(const PresburgerRelation &set)
+    : PresburgerRelation(set) {}
+
+PresburgerSet PresburgerSet::unionSet(const PresburgerRelation &set) const {
+  return PresburgerSet(PresburgerRelation::unionSet(set));
+}
+
+PresburgerSet PresburgerSet::intersect(const PresburgerRelation &set) const {
+  return PresburgerSet(PresburgerRelation::intersect(set));
+}
+
+PresburgerSet PresburgerSet::complement() const {
+  return PresburgerSet(PresburgerRelation::complement());
+}
+
+PresburgerSet PresburgerSet::subtract(const PresburgerRelation &set) const {
+  return PresburgerSet(PresburgerRelation::subtract(set));
+}
+
+PresburgerSet PresburgerSet::coalesce() const {
+  return PresburgerSet(PresburgerRelation::coalesce());
+}

mlir/lib/Dialect/Affine/Analysis/Utils.cpp

 //===- Utils.cpp ---- Misc utilities for analysis -------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements miscellaneous analysis routines for non-loop IR
 // structures.
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Dialect/Affine/Analysis/Utils.h"
-#include "mlir/Analysis/Presburger/PresburgerSet.h"
+#include "mlir/Analysis/Presburger/PresburgerRelation.h"
 #include "mlir/Dialect/Affine/Analysis/AffineAnalysis.h"
 #include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h"
 #include "mlir/Dialect/Affine/IR/AffineOps.h"
 #include "mlir/Dialect/Affine/IR/AffineValueMap.h"
 #include "mlir/Dialect/Arithmetic/IR/Arithmetic.h"
 #include "mlir/IR/IntegerSet.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Debug.h"

mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp

 //===- PWMAFunctionTest.cpp - Tests for PWMAFunction ----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains tests for PWMAFunction.
 //
 //===----------------------------------------------------------------------===//
 
 #include "./Utils.h"
 
 #include "mlir/Analysis/Presburger/PWMAFunction.h"
-#include "mlir/Analysis/Presburger/PresburgerSet.h"
+#include "mlir/Analysis/Presburger/PresburgerRelation.h"
 #include "mlir/IR/MLIRContext.h"
 
 #include <gmock/gmock.h>
 #include <gtest/gtest.h>
 
 using namespace mlir;
 using namespace presburger;
 

mlir/unittests/Analysis/Presburger/PresburgerSetTest.cpp

 //===- SetTest.cpp - Tests for PresburgerSet ------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains tests for PresburgerSet. The tests for union,
 // intersection, subtract, and complement work by computing the operation on
 // two sets and checking, for a set of points, that the resulting set contains
 // the point iff the result is supposed to contain it. The test for isEqual just
 // checks if the result for two sets matches the expected result.
 //
 //===----------------------------------------------------------------------===//
 
-#include "mlir/Analysis/Presburger/PresburgerSet.h"
 #include "./Utils.h"
+#include "mlir/Analysis/Presburger/PresburgerRelation.h"
 #include "mlir/IR/MLIRContext.h"
 
 #include <gmock/gmock.h>
 #include <gtest/gtest.h>
 
 using namespace mlir;
 using namespace presburger;
 
 /// Parse a list of StringRefs to IntegerPolyhedron and combine them into a
 /// PresburgerSet be using the union operation. It is expected that the strings
 /// are all valid IntegerSet representation and that all of them have the same
 /// number of dimensions as is specified by the numDims argument.
 static PresburgerSet
 parsePresburgerSetFromPolyStrings(unsigned numDims, ArrayRef<StringRef> strs) {
-  PresburgerSet set = PresburgerSet::getEmptySet(numDims);
+  PresburgerSet set = PresburgerSet::getEmpty(numDims);
   for (StringRef str : strs)
     set.unionInPlace(parsePoly(str));
   return set;
 }
 
 /// Compute the union of s and t, and check that each of the given points
 /// belongs to the union iff it belongs to at least one of s and t.
 static void testUnionAtPoints(const PresburgerSet &s, const PresburgerSet &t,

 }
 
 /// Construct a PresburgerSet having `numDims` dimensions and no symbols from
 /// the given list of IntegerPolyhedron. Each Poly in `polys` should also have
 /// `numDims` dimensions and no symbols, although it can have any number of
 /// local ids.
 static PresburgerSet makeSetFromPoly(unsigned numDims,
                                      ArrayRef<IntegerPolyhedron> polys) {
-  PresburgerSet set = PresburgerSet::getEmptySet(numDims);
+  PresburgerSet set = PresburgerSet::getEmpty(numDims);
   for (const IntegerPolyhedron &poly : polys)
     set.unionInPlace(poly);
   return set;
 }
 
 TEST(SetTest, containsPoint) {
   PresburgerSet setA = parsePresburgerSetFromPolyStrings(
       1,
PresburgerSet set = parsePresburgerSetFromPolyStrings(
       1,
       {"(x) : (x - 2 >= 0, -x + 8 >= 0)", "(x) : (x - 10 >= 0, -x + 20 >= 0)"});
 
   // Universe union set.
   testUnionAtPoints(PresburgerSet::getUniverse(1), set,
                     {{1}, {2}, {8}, {9}, {10}, {20}, {21}});
 
   // empty set union set.
-  testUnionAtPoints(PresburgerSet::getEmptySet(1), set,
+  testUnionAtPoints(PresburgerSet::getEmpty(1), set,
                     {{1}, {2}, {8}, {9}, {10}, {20}, {21}});
 
   // empty set union Universe.
-  testUnionAtPoints(PresburgerSet::getEmptySet(1),
-                    PresburgerSet::getUniverse(1), {{1}, {2}, {0}, {-1}});
+  testUnionAtPoints(PresburgerSet::getEmpty(1), PresburgerSet::getUniverse(1),
+                    {{1}, {2}, {0}, {-1}});
 
   // Universe union empty set.
-  testUnionAtPoints(PresburgerSet::getUniverse(1),
-                    PresburgerSet::getEmptySet(1), {{1}, {2}, {0}, {-1}});
+  testUnionAtPoints(PresburgerSet::getUniverse(1), PresburgerSet::getEmpty(1),
+                    {{1}, {2}, {0}, {-1}});
 
   // empty set union empty set.
-  testUnionAtPoints(PresburgerSet::getEmptySet(1),
-                    PresburgerSet::getEmptySet(1), {{1}, {2}, {0}, {-1}});
+  testUnionAtPoints(PresburgerSet::getEmpty(1), PresburgerSet::getEmpty(1),
+                    {{1}, {2}, {0}, {-1}});
 }
 
 TEST(SetTest, Intersect) {
   PresburgerSet set = parsePresburgerSetFromPolyStrings(
       1,
       {"(x) : (x - 2 >= 0, -x + 8 >= 0)", "(x) : (x - 10 >= 0, -x + 20 >= 0)"});
 
   // Universe intersection set.
   testIntersectAtPoints(PresburgerSet::getUniverse(1), set,
                         {{1}, {2}, {8}, {9}, {10}, {20}, {21}});
 
   // empty set intersection set.
-  testIntersectAtPoints(PresburgerSet::getEmptySet(1), set,
+  testIntersectAtPoints(PresburgerSet::getEmpty(1), set,
                         {{1}, {2}, {8}, {9}, {10}, {20}, {21}});
 
   // empty set intersection Universe.
-  testIntersectAtPoints(PresburgerSet::getEmptySet(1),
+  testIntersectAtPoints(PresburgerSet::getEmpty(1),
                         PresburgerSet::getUniverse(1), {{1}, {2}, {0}, {-1}});
 
   // Universe intersection empty set.
   testIntersectAtPoints(PresburgerSet::getUniverse(1),
-                        PresburgerSet::getEmptySet(1), {{1}, {2}, {0}, {-1}});
+                        PresburgerSet::getEmpty(1), {{1}, {2}, {0}, {-1}});
 
   // Universe intersection Universe.
   testIntersectAtPoints(PresburgerSet::getUniverse(1),
                         PresburgerSet::getUniverse(1), {{1}, {2}, {0}, {-1}});
 }
 
 TEST(SetTest, Subtract) {
   // The interval [2, 8] minus the interval [10, 20].

 TEST(SetTest, Complement) {
   // Complement of universe.
   testComplementAtPoints(
       PresburgerSet::getUniverse(1),
       {{-1}, {-2}, {-8}, {1}, {2}, {8}, {9}, {10}, {20}, {21}});
 
   // Complement of empty set.
   testComplementAtPoints(
-      PresburgerSet::getEmptySet(1),
+      PresburgerSet::getEmpty(1),
       {{-1}, {-2}, {-8}, {1}, {2}, {8}, {9}, {10}, {20}, {21}});
 
   testComplementAtPoints(
       parsePresburgerSetFromPolyStrings(2, {"(x,y) : (x - 2 >= 0, y - 2 >= 0, "
                                             "-x + 10 >= 0, -y + 10 >= 0)"}),
       {{1, 1},
        {2, 1},
        {1, 2},
        {2, 2},
        {2, 3},
        {3, 2},
        {10, 10},
        {10, 11},
        {11, 10},
        {2, 10},
        {2, 11},
        {1, 10}});
 }
 
 TEST(SetTest, isEqual) {
   // set = [2, 8] U [10, 20].
   PresburgerSet universe = PresburgerSet::getUniverse(1);
-  PresburgerSet emptySet = PresburgerSet::getEmptySet(1);
+  PresburgerSet emptySet = PresburgerSet::getEmpty(1);
   PresburgerSet set = parsePresburgerSetFromPolyStrings(
       1,
       {"(x) : (x - 2 >= 0, -x + 8 >= 0)", "(x) : (x - 10 >= 0, -x + 20 >= 0)"});
 
   // universe != emptySet.
   EXPECT_FALSE(universe.isEqual(emptySet));
   // emptySet != universe.
   EXPECT_FALSE(emptySet.isEqual(universe));

 }
 
 /// Coalesce `set` and check that the `newSet` is equal to `set and that
 /// `expectedNumPoly` matches the number of Poly in the coalesced set.
 /// If one of the two
 void expectCoalesce(size_t expectedNumPoly, const PresburgerSet &set) {
   PresburgerSet newSet = set.coalesce();
   EXPECT_TRUE(set.isEqual(newSet));
-  EXPECT_TRUE(expectedNumPoly == newSet.getNumPolys());
+  EXPECT_TRUE(expectedNumPoly == newSet.getNumDisjuncts());
 }
 
 TEST(SetTest, coalesceNoPoly) {
   PresburgerSet set = makeSetFromPoly(0, {});
   expectCoalesce(0, set);
 }
 
 TEST(SetTest, coalesceContainedOneDim) {

mlir/unittests/Analysis/Presburger/Utils.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_UNITTESTS_ANALYSIS_PRESBURGER_UTILS_H
 #define MLIR_UNITTESTS_ANALYSIS_PRESBURGER_UTILS_H
 
 #include "../../Dialect/Affine/Analysis/AffineStructuresParser.h"
 #include "mlir/Analysis/Presburger/IntegerRelation.h"
-#include "mlir/Analysis/Presburger/PresburgerSet.h"
+#include "mlir/Analysis/Presburger/PresburgerRelation.h"
 #include "mlir/IR/MLIRContext.h"
 
 #include <gtest/gtest.h>
 
 namespace mlir {
 namespace presburger {
 
 /// Parses a IntegerPolyhedron from a StringRef. It is expected that the

mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParserTest.cpp

 //===- AffineStructuresParserTest.cpp - FAC parsing unit tests --*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains tests for parsing IntegerSets to FlatAffineConstraints.
 // The tests with invalid input check that the parser only accepts well-formed
 // IntegerSets. The tests with well-formed input compare the returned FACs to
 // manually constructed FACs with a PresburgerSet equality check.
 //
 //===----------------------------------------------------------------------===//
 
 #include "./AffineStructuresParser.h"
-#include "mlir/Analysis/Presburger/PresburgerSet.h"
+#include "mlir/Analysis/Presburger/PresburgerRelation.h"
 
 #include <gtest/gtest.h>
 
 using namespace mlir;
 using namespace presburger;
 
 /// Construct a FlatAffineConstraints from a set of inequality, equality, and
 /// division onstraints.