[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

370

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

139

[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

-//===- Set.h - MLIR PresburgerSet Class -------------------------*- C++ -*-===//
+//===- 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 IntegerPolyhedrons.
+// A class to represent unions of IntegerRelation.
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H
-#define MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H
+#ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_H
+#define MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_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.
+/// 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 IntegerPolyhedrons (polyhedrons) are stored in a vector, and the set
+/// The IntegerRelations (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 {
+/// other than that they are all in the same PresburgerSpace. For example, the
+/// polyhedrons may overlap each other.
+class PresburgerRelation : public PresburgerSpace {
 public:
   /// Return a universe set of the specified type that contains all points.
-  static PresburgerSet getUniverse(unsigned numDims = 0,
-                                   unsigned numSymbols = 0);
+  static PresburgerRelation getUniverse(unsigned numDomain, unsigned numRange,
+                                        unsigned numSymbols);
+
   /// Return an empty set of the specified type that contains no points.
-  static PresburgerSet getEmptySet(unsigned numDims = 0,
-                                   unsigned numSymbols = 0);
+  static PresburgerRelation getEmptyRel(unsigned numDomain, unsigned numRange,
+                                        unsigned numSymbols);
 
-  explicit PresburgerSet(const IntegerPolyhedron &poly);
+  explicit PresburgerRelation(const IntegerRelation &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 a reference to the list of IntegerRelations.
+  ArrayRef<IntegerRelation> getAllPolys() const;
 
-  /// Return the IntegerPolyhedron at the specified index.
-  const IntegerPolyhedron &getPoly(unsigned index) const;
+  /// Return the IntegerRelation at the specified index.
+  const IntegerRelation &getPoly(unsigned index) const;
 
   /// Mutate this set, turning it into the union of this set and the given
-  /// IntegerPolyhedron.
-  void unionInPlace(const IntegerPolyhedron &poly);
+  /// IntegerRelation.
+  void unionInPlace(const IntegerRelation &poly);
 
   /// Mutate this set, turning it into the union of this set and the given set.
-  void unionInPlace(const PresburgerSet &set);
+  void unionInPlace(const PresburgerRelation &set);
 
   /// Return the union of this set and the given set.
-  PresburgerSet unionSet(const PresburgerSet &set) const;
+  PresburgerRelation unionSet(const PresburgerRelation &set) const;
 
   /// Return the intersection of this set and the given set.
-  PresburgerSet intersect(const PresburgerSet &set) const;
+  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.
-  PresburgerSet complement() const;
+  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.
-  PresburgerSet subtract(const PresburgerSet &set) const;
+  PresburgerRelation subtract(const PresburgerRelation &set) const;
 
   /// Return true if this set is a subset of the given set, and false otherwise.
-  bool isSubsetOf(const PresburgerSet &set) const;
+  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 PresburgerSet &set) const;
+  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 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.
+  /// Simplifies the representation of a PresburgerRelation.
   ///
   /// In particular, removes all polyhedrons which are subsets of other
   /// polyhedrons in the union.
-  PresburgerSet coalesce() const;
+  PresburgerRelation 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) {}
+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 polyhedrons that this set is the union of.
-  SmallVector<IntegerPolyhedron, 2> integerPolyhedrons;
+  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 getEmptySet(unsigned numDims = 0,
+                                   unsigned numSymbols = 0);
+
+  explicit PresburgerSet(const IntegerPolyhedron &poly);
+
+  explicit PresburgerSet(const PresburgerRelation &set);
+
+  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_PRESBURGERSET_H
+#endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERRELATION_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/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)
+PresburgerRelation::PresburgerRelation(const IntegerRelation &poly)
     : PresburgerSpace(poly) {
   unionInPlace(poly);
 }
 
-unsigned PresburgerSet::getNumPolys() const {
-  return integerPolyhedrons.size();
+unsigned PresburgerRelation::getNumPolys() const {
+  return integerRelations.size();
 }
 
-ArrayRef<IntegerPolyhedron> PresburgerSet::getAllPolys() const {
-  return integerPolyhedrons;
+ArrayRef<IntegerRelation> PresburgerRelation::getAllPolys() const {
+  return integerRelations;
 }
 
-const IntegerPolyhedron &PresburgerSet::getPoly(unsigned index) const {
-  assert(index < integerPolyhedrons.size() && "index out of bounds!");
-  return integerPolyhedrons[index];
+const IntegerRelation &PresburgerRelation::getPoly(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) {
+/// IntegerRelation.
+void PresburgerRelation::unionInPlace(const IntegerRelation &poly) {
   assert(PresburgerSpace::isEqual(poly) && "Spaces should match");
-  integerPolyhedrons.push_back(poly);
+  integerRelations.push_back(poly);
 }
 
 /// 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
 /// 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)
+  for (const IntegerRelation &poly : set.integerRelations)
     unionInPlace(poly);
 }
 
 /// 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) {
+bool PresburgerRelation::containsPoint(ArrayRef<int64_t> point) const {
+  return llvm::any_of(integerRelations, [&](const IntegerRelation &poly) {
     return (poly.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::getEmptyRel(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

 /// 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
 /// 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) {
+static void subtractRecursively(IntegerRelation &b, Simplex &simplex,
+                                const PresburgerRelation &s, unsigned i,
+                                PresburgerRelation &result) {
   if (i == s.getNumPolys()) {
     result.unionInPlace(b);
     return;
   }
-  IntegerPolyhedron sI = s.getPoly(i);
+  IntegerRelation sI = s.getPoly(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();
static void subtractRecursively(IntegerRelation &b, Simplex &simplex,
   }
 }
 
 /// Return the set difference poly \ set.
 ///
 /// The polyhedron 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) {
+static PresburgerRelation getSetDifference(IntegerRelation poly,
+                                           const PresburgerRelation &set) {
   assert(poly.PresburgerSpace::isEqual(set) && "Spaces should match");
   if (poly.isEmptyByGCDTest())
-    return PresburgerSet::getEmptySet(poly.getNumDimIds(),
-                                      poly.getNumSymbolIds());
+    return PresburgerRelation::getEmptyRel(
+        poly.getNumDomainIds(), poly.getNumRangeIds(), poly.getNumSymbolIds());
 
-  PresburgerSet result =
-      PresburgerSet::getEmptySet(poly.getNumDimIds(), poly.getNumSymbolIds());
+  PresburgerRelation result = PresburgerRelation::getEmptyRel(
+      poly.getNumDomainIds(), poly.getNumRangeIds(), poly.getNumSymbolIds());
   Simplex simplex(poly);
   subtractRecursively(poly, 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)
+  for (const IntegerRelation &poly : integerRelations)
     result.unionInPlace(getSetDifference(poly, 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(); });
+      integerRelations.begin(), integerRelations.end(),
+      [](const IntegerRelation &poly) { return poly.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) {
+  for (const IntegerRelation &poly : integerRelations) {
     if (Optional<SmallVector<int64_t, 8>> opt = poly.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) {
+  for (const IntegerRelation &poly : integerRelations) {
     Optional<uint64_t> volume = poly.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
 /// `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,
+addCoalescedPolyhedron(SmallVectorImpl<IntegerRelation> &polyhedrons,
+                       unsigned i, unsigned j, const IntegerRelation &poly,
                        SmallVectorImpl<Simplex> &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
+    // the vector, hence the `IntegerRelation` 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
+    // 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;
 
     simplices[i] = simplices[n - 1];

 ///    ___________        ___________
 ///   /   /  |   /       /          /
 ///   \   \  |  /   ==>  \         /
 ///    \   \ | /          \       /
 ///     \___\|/            \_____/
 ///
 ///
 static LogicalResult
-coalescePairCutCase(SmallVectorImpl<IntegerPolyhedron> &polyhedrons,
+coalescePairCutCase(SmallVectorImpl<IntegerRelation> &polyhedrons,
                     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];
+  IntegerRelation &poly = polyhedrons[i];
   if (llvm::any_of(cuttingIneqsA,
                    [&simp, &poly, &cuttingIneqsB](ArrayRef<int64_t> curr) {
                      return !isFacetContained(curr, simp, poly, cuttingIneqsB);
                    }))
     return failure();
-  IntegerPolyhedron newSet(poly.getNumDimIds(), poly.getNumSymbolIds(),
-                           poly.getNumLocalIds());
+  IntegerRelation newSet(poly.getNumDomainIds(), poly.getNumRangeIds(),
+                         poly.getNumSymbolIds(), poly.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);
typeEquality(ArrayRef<int64_t> eq, Simplex &simp,
   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<IntegerRelation> &polyhedrons,
                             SmallVectorImpl<Simplex> &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();
 }
 
-/// Attempts to coalesce the two IntegerPolyhedrons at position `i` and `j` in
+/// Attempts to coalesce the two IntegerRelations 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<IntegerPolyhedron> &polyhedrons,
+static LogicalResult coalescePair(unsigned i, unsigned j,
+                                  SmallVectorImpl<IntegerRelation> &polyhedrons,
                                   SmallVectorImpl<Simplex> &simplices) {
 
-  IntegerPolyhedron &a = polyhedrons[i];
-  IntegerPolyhedron &b = polyhedrons[j];
+  IntegerRelation &a = polyhedrons[i];
+  IntegerRelation &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<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)
static LogicalResult coalescePair(unsigned i, unsigned j,
   if (coalescePairCutCase(polyhedrons, 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::getEmptyRel(
+      getNumDomainIds(), getNumRangeIds(), getNumSymbolIds());
+  SmallVector<IntegerRelation, 2> polyhedrons = 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]);
     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
+  // 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 `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
+    // 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]);
 
   return newSet;
 }
 
-void PresburgerSet::print(raw_ostream &os) const {
+void PresburgerRelation::print(raw_ostream &os) const {
   os << "Number of Polyhedrons: " << getNumPolys() << "\n";
-  for (const IntegerPolyhedron &poly : integerPolyhedrons) {
+  for (const IntegerRelation &poly : integerRelations) {
     poly.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::getEmptySet(unsigned numDims,
+                                         unsigned numSymbols) {
+  return PresburgerSet(numDims, numSymbols);
+}
+
+PresburgerSet::PresburgerSet(const IntegerPolyhedron &poly)
+    : PresburgerRelation(poly) {}
+
+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;
 

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.