diff --git a/mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h b/mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
rename from mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h
rename to mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
--- a/mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h
+++ b/mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
@@ -1,4 +1,4 @@
-//===- IntegerPolyhedron.h - MLIR IntegerPolyhedron Class -----*- C++ -*---===//
+//===- IntegerRelation.h - MLIR IntegerRelation 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.
@@ -6,7 +6,9 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// A class to represent an integer polyhedron.
+// A class to represent a relation over integer tuples. A relation is
+// represented as a constraint system over a space of tuples of integer valued
+// variables supporting symbolic identifiers and existential quantification.
 //
 //===----------------------------------------------------------------------===//
 
@@ -42,6 +44,15 @@
 /// and IdKind::Domain should be used to refer to dimension identifiers.
 class IntegerRelation : public PresburgerLocalSpace {
 public:
+  /// All derived classes of IntegerRelation.
+  enum class Kind {
+    FlatAffineConstraints,
+    FlatAffineValueConstraints,
+    MultiAffineFunction,
+    IntegerRelation,
+    IntegerPolyhedron,
+  };
+
   /// Constructs a relation reserving memory for the specified number
   /// of constraints and identifiers.
   IntegerRelation(unsigned numReservedInequalities,
@@ -64,99 +75,35 @@
                             numLocals + 1,
                         numDomain, numRange, numSymbols, numLocals) {}
 
-protected:
-  /// Constructs a set reserving memory for the specified number
-  /// of constraints and identifiers.  This constructor should not be used
-  /// directly to create a relation and should only be used to create Sets.
-  IntegerRelation(unsigned numReservedInequalities,
-                  unsigned numReservedEqualities, unsigned numReservedCols,
-                  unsigned numDims, unsigned numSymbols, unsigned numLocals)
-      : PresburgerLocalSpace(numDims, numSymbols, numLocals),
-        equalities(0, getNumIds() + 1, numReservedEqualities, numReservedCols),
-        inequalities(0, getNumIds() + 1, numReservedInequalities,
-                     numReservedCols) {
-    assert(numReservedCols >= getNumIds() + 1);
-  }
-
-  /// Coefficients of affine equalities (in == 0 form).
-  Matrix equalities;
-
-  /// Coefficients of affine inequalities (in >= 0 form).
-  Matrix inequalities;
-};
-
-/// An IntegerPolyhedron is a PresburgerLocalSpace subject to affine
-/// constraints. Affine constraints can be inequalities or equalities in the
-/// form:
-///
-/// Inequality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} + c_n >= 0
-/// Equality  : c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} + c_n == 0
-///
-/// where c_0, c_1, ..., c_n are integers and n is the total number of
-/// identifiers in the space.
-///
-/// An IntegerPolyhedron is similar to a IntegerRelation but it does not make a
-/// distinction between Domain and Range identifiers. Internally,
-/// IntegerPolyhedron is implemented as a IntegerRelation with zero domain ids.
-///
-/// Since IntegerPolyhedron does not make a distinction between dimensions,
-/// IdKind::SetDim should be used to refer to dimension identifiers.
-class IntegerPolyhedron : public IntegerRelation {
-public:
-  /// All derived classes of IntegerPolyhedron.
-  enum class Kind {
-    FlatAffineConstraints,
-    FlatAffineValueConstraints,
-    MultiAffineFunction,
-    IntegerPolyhedron
-  };
-
-  /// Constructs a constraint system reserving memory for the specified number
-  /// of constraints and identifiers.
-  IntegerPolyhedron(unsigned numReservedInequalities,
-                    unsigned numReservedEqualities, unsigned numReservedCols,
-                    unsigned numDims, unsigned numSymbols, unsigned numLocals)
-      : IntegerRelation(numReservedInequalities, numReservedEqualities,
-                        numReservedCols, numDims, numSymbols, numLocals) {}
-
-  /// Constructs a constraint system with the specified number of
-  /// dimensions and symbols.
-  IntegerPolyhedron(unsigned numDims = 0, unsigned numSymbols = 0,
-                    unsigned numLocals = 0)
-      : IntegerPolyhedron(/*numReservedInequalities=*/0,
-                          /*numReservedEqualities=*/0,
-                          /*numReservedCols=*/numDims + numSymbols + numLocals +
-                              1,
-                          numDims, numSymbols, numLocals) {}
-
   /// Return a system with no constraints, i.e., one which is satisfied by all
   /// points.
-  static IntegerPolyhedron getUniverse(unsigned numDims = 0,
-                                       unsigned numSymbols = 0) {
-    return IntegerPolyhedron(numDims, numSymbols);
+  static IntegerRelation getUniverse(unsigned numDomain = 0,
+                                     unsigned numRange = 0,
+                                     unsigned numSymbols = 0) {
+    return IntegerRelation(numDomain, numRange, numSymbols);
   }
 
-  /// Return the kind of this IntegerPolyhedron.
-  virtual Kind getKind() const { return Kind::IntegerPolyhedron; }
+  /// Return the kind of this IntegerRelation.
+  virtual Kind getKind() const { return Kind::IntegerRelation; }
 
-  static bool classof(const IntegerPolyhedron *cst) { return true; }
+  static bool classof(const IntegerRelation *cst) { return true; }
 
   // Clones this object.
-  std::unique_ptr<IntegerPolyhedron> clone() const;
+  std::unique_ptr<IntegerRelation> clone() const;
 
   /// Appends constraints from `other` into `this`. This is equivalent to an
   /// intersection with no simplification of any sort attempted.
-  void append(const IntegerPolyhedron &other);
+  void append(const IntegerRelation &other);
 
   /// Return whether `this` and `other` are equal. This is integer-exact
   /// and somewhat expensive, since it uses the integer emptiness check
-  /// (see IntegerPolyhedron::findIntegerSample()).
-  bool isEqual(const IntegerPolyhedron &other) const;
+  /// (see IntegerRelation::findIntegerSample()).
+  bool isEqual(const IntegerRelation &other) const;
 
-  /// Return whether this is a subset of the given IntegerPolyhedron. This is
+  /// Return whether this is a subset of the given IntegerRelation. This is
   /// integer-exact and somewhat expensive, since it uses the integer emptiness
-  /// check (see IntegerPolyhedron::findIntegerSample()).
-  bool isSubsetOf(const IntegerPolyhedron &other) const;
+  /// check (see IntegerRelation::findIntegerSample()).
+  bool isSubsetOf(const IntegerRelation &other) const;
 
   /// Returns the value at the specified equality row and column.
   inline int64_t atEq(unsigned i, unsigned j) const { return equalities(i, j); }
@@ -237,15 +184,16 @@
   void removeInequalityRange(unsigned start, unsigned end);
 
   /// Get the lexicographically minimum rational point satisfying the
-  /// constraints. Returns an empty optional if the polyhedron is empty or if
+  /// constraints. Returns an empty optional if the relation is empty or if
   /// the lexmin is unbounded. Symbols are not supported and will result in
-  /// assert-failure.
+  /// assert-failure. Note that Domain is minimized first, then range.
   MaybeOptimum<SmallVector<Fraction, 8>> findRationalLexMin() const;
 
   /// Same as above, but returns lexicographically minimal integer point.
   /// Note: this should be used only when the lexmin is really required.
   /// For a generic integer sampling operation, findIntegerSample is more
-  /// robust and should be preferred.
+  /// robust and should be preferred. Note that Domain is minimized first, then
+  /// range.
   MaybeOptimum<SmallVector<int64_t, 8>> findIntegerLexMin() const;
 
   /// Swap the posA^th identifier with the posB^th identifier.
@@ -258,8 +206,8 @@
   /// values and removes them.
   void setAndEliminate(unsigned pos, ArrayRef<int64_t> values);
 
-  /// Replaces the contents of this IntegerPolyhedron with `other`.
-  virtual void clearAndCopyFrom(const IntegerPolyhedron &other);
+  /// Replaces the contents of this IntegerRelation with `other`.
+  virtual void clearAndCopyFrom(const IntegerRelation &other);
 
   /// Gather positions of all lower and upper bounds of the identifier at `pos`,
   /// and optionally any equalities on it. In addition, the bounds are to be
@@ -304,14 +252,14 @@
   Optional<SmallVector<int64_t, 8>> findIntegerSample() const;
 
   /// Compute an overapproximation of the number of integer points in the
-  /// polyhedron. Symbol ids are currently not supported. If the computed
+  /// relation. Symbol ids are currently not supported. If the computed
   /// overapproximation is infinite, an empty optional is returned.
   Optional<uint64_t> computeVolume() const;
 
   /// Returns true if the given point satisfies the constraints, or false
   /// otherwise.
   ///
-  /// Note: currently, if the polyhedron contains local ids, the values of
+  /// Note: currently, if the relation contains local ids, the values of
   /// the local ids must also be provided.
   bool containsPoint(ArrayRef<int64_t> point) const;
 
@@ -383,7 +331,7 @@
   /// 3) this   = {0 <= d0 <= 5, 1 <= d1 <= 9}
   ///    other  = {2 <= d0 <= 6, 5 <= d1 <= 15},
   ///    output = {0 <= d0 <= 6, 1 <= d1 <= 15}
-  LogicalResult unionBoundingBox(const IntegerPolyhedron &other);
+  LogicalResult unionBoundingBox(const IntegerRelation &other);
 
   /// Returns the smallest known constant bound for the extent of the specified
   /// identifier (pos^th), i.e., the smallest known constant that is greater
@@ -452,12 +400,27 @@
   ///
   /// The number of dimensions and symbol ids in `this` and `other` should
   /// match.
-  void mergeLocalIds(IntegerPolyhedron &other);
+  void mergeLocalIds(IntegerRelation &other);
 
   void print(raw_ostream &os) const;
   void dump() const;
 
 protected:
+  /// Constructs a set reserving memory for the specified number
+  /// of constraints and identifiers. This constructor should not be used
+  /// directly to create a relation and should only be used to create Sets.
+  /// Internally this constructs a relation with with no domain and a
+  /// space with no distinction between domain and range identifiers.
+  IntegerRelation(unsigned numReservedInequalities,
+                  unsigned numReservedEqualities, unsigned numReservedCols,
+                  unsigned numDims, unsigned numSymbols, unsigned numLocals)
+      : PresburgerLocalSpace(numDims, numSymbols, numLocals),
+        equalities(0, getNumIds() + 1, numReservedEqualities, numReservedCols),
+        inequalities(0, getNumIds() + 1, numReservedInequalities,
+                     numReservedCols) {
+    assert(numReservedCols >= getNumIds() + 1);
+  }
+
   /// Checks all rows of equality/inequality constraints for trivial
   /// contradictions (for example: 1 == 0, 0 >= 1), which may have surfaced
   /// after elimination. Returns true if an invalid constraint is found;
@@ -526,7 +489,7 @@
   virtual bool hasConsistentState() const;
 
   /// Prints the number of constraints, dimensions, symbols and locals in the
-  /// IntegerPolyhedron.
+  /// IntegerRelation.
   virtual void printSpace(raw_ostream &os) const;
 
   /// Removes identifiers in the column range [idStart, idLimit), and copies any
@@ -537,7 +500,7 @@
   /// A parameter that controls detection of an unrealistic number of
   /// constraints. If the number of constraints is this many times the number of
   /// variables, we consider such a system out of line with the intended use
-  /// case of IntegerPolyhedron.
+  /// case of IntegerRelation.
   // The rationale for 32 is that in the typical simplest of cases, an
   // identifier is expected to have one lower bound and one upper bound
   // constraint. With a level of tiling or a connection to another identifier
@@ -545,6 +508,65 @@
   // don't expect an identifier to have more than 32 lower/upper/equality
   // constraints. This is conservatively set low and can be raised if needed.
   constexpr static unsigned kExplosionFactor = 32;
+
+  /// Coefficients of affine equalities (in == 0 form).
+  Matrix equalities;
+
+  /// Coefficients of affine inequalities (in >= 0 form).
+  Matrix inequalities;
+};
+
+/// An IntegerPolyhedron is a PresburgerLocalSpace subject to affine
+/// constraints. Affine constraints can be inequalities or equalities in the
+/// form:
+///
+/// Inequality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} + c_n >= 0
+/// Equality  : c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} + c_n == 0
+///
+/// where c_0, c_1, ..., c_n are integers and n is the total number of
+/// identifiers in the space.
+///
+/// An IntegerPolyhedron is similar to an IntegerRelation but it does not make a
+/// distinction between Domain and Range identifiers. Internally,
+/// IntegerPolyhedron is implemented as a IntegerRelation with zero domain ids.
+///
+/// Since IntegerPolyhedron does not make a distinction between kinds of
+/// dimensions, IdKind::SetDim should be used to refer to dimension identifiers.
+class IntegerPolyhedron : public IntegerRelation {
+public:
+  /// Constructs a set reserving memory for the specified number
+  /// of constraints and identifiers.
+  IntegerPolyhedron(unsigned numReservedInequalities,
+                    unsigned numReservedEqualities, unsigned numReservedCols,
+                    unsigned numDims, unsigned numSymbols, unsigned numLocals)
+      : IntegerRelation(numReservedInequalities, numReservedEqualities,
+                        numReservedCols, numDims, numSymbols, numLocals) {}
+
+  /// Constructs a relation with the specified number of dimensions and symbols.
+  IntegerPolyhedron(unsigned numDims = 0, unsigned numSymbols = 0,
+                    unsigned numLocals = 0)
+      : IntegerPolyhedron(/*numReservedInequalities=*/0,
+                          /*numReservedEqualities=*/0,
+                          /*numReservedCols=*/numDims + numSymbols + numLocals +
+                              1,
+                          numDims, numSymbols, numLocals) {}
+
+  /// Return a system with no constraints, i.e., one which is satisfied by all
+  /// points.
+  static IntegerPolyhedron getUniverse(unsigned numDims = 0,
+                                       unsigned numSymbols = 0) {
+    return IntegerPolyhedron(numDims, numSymbols);
+  }
+
+  /// Return the kind of this IntegerRelation.
+  Kind getKind() const override { return Kind::IntegerPolyhedron; }
+
+  static bool classof(const IntegerRelation *cst) {
+    return cst->getKind() == Kind::IntegerPolyhedron;
+  }
+
+  // Clones this object.
+  std::unique_ptr<IntegerPolyhedron> clone() const;
 };
 
 } // namespace presburger
diff --git a/mlir/include/mlir/Analysis/Presburger/LinearTransform.h b/mlir/include/mlir/Analysis/Presburger/LinearTransform.h
--- a/mlir/include/mlir/Analysis/Presburger/LinearTransform.h
+++ b/mlir/include/mlir/Analysis/Presburger/LinearTransform.h
@@ -6,14 +6,14 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// Support for linear transforms and applying them to an IntegerPolyhedron.
+// Support for linear transforms and applying them to an IntegerRelation.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_ANALYSIS_PRESBURGER_LINEARTRANSFORM_H
 #define MLIR_ANALYSIS_PRESBURGER_LINEARTRANSFORM_H
 
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Analysis/Presburger/Matrix.h"
 #include "llvm/ADT/SmallVector.h"
 
@@ -34,9 +34,9 @@
   static std::pair<unsigned, LinearTransform>
   makeTransformToColumnEchelon(Matrix m);
 
-  // Returns an IntegerPolyhedron having a constraint vector vT for every
-  // constraint vector v in poly, where T is this transform.
-  IntegerPolyhedron applyTo(const IntegerPolyhedron &poly) const;
+  // Returns an IntegerRelation having a constraint vector vT for every
+  // constraint vector v in rel, where T is this transform.
+  IntegerRelation applyTo(const IntegerRelation &rel) const;
 
   // The given vector is interpreted as a row vector v. Post-multiply v with
   // this transform, say T, and return vT.
diff --git a/mlir/include/mlir/Analysis/Presburger/PWMAFunction.h b/mlir/include/mlir/Analysis/Presburger/PWMAFunction.h
--- a/mlir/include/mlir/Analysis/Presburger/PWMAFunction.h
+++ b/mlir/include/mlir/Analysis/Presburger/PWMAFunction.h
@@ -16,7 +16,7 @@
 #ifndef MLIR_ANALYSIS_PRESBURGER_PWMAFUNCTION_H
 #define MLIR_ANALYSIS_PRESBURGER_PWMAFUNCTION_H
 
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Analysis/Presburger/PresburgerSet.h"
 
 namespace mlir {
@@ -62,8 +62,8 @@
 
   ~MultiAffineFunction() override = default;
   Kind getKind() const override { return Kind::MultiAffineFunction; }
-  bool classof(const IntegerPolyhedron *poly) const {
-    return poly->getKind() == Kind::MultiAffineFunction;
+  bool classof(const IntegerRelation *rel) const {
+    return rel->getKind() == Kind::MultiAffineFunction;
   }
 
   unsigned getNumInputs() const { return getNumDimAndSymbolIds(); }
diff --git a/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h b/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h
--- a/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h
+++ b/mlir/include/mlir/Analysis/Presburger/PresburgerSet.h
@@ -13,7 +13,7 @@
 #ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H
 #define MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H
 
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 
 namespace mlir {
 namespace presburger {
diff --git a/mlir/include/mlir/Analysis/Presburger/Simplex.h b/mlir/include/mlir/Analysis/Presburger/Simplex.h
--- a/mlir/include/mlir/Analysis/Presburger/Simplex.h
+++ b/mlir/include/mlir/Analysis/Presburger/Simplex.h
@@ -6,7 +6,7 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// Functionality to perform analysis on an IntegerPolyhedron. In particular,
+// Functionality to perform analysis on an IntegerRelation. In particular,
 // support for performing emptiness checks, redundancy checks and obtaining the
 // lexicographically minimum rational element in a set.
 //
@@ -16,7 +16,7 @@
 #define MLIR_ANALYSIS_PRESBURGER_SIMPLEX_H
 
 #include "mlir/Analysis/Presburger/Fraction.h"
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Analysis/Presburger/Matrix.h"
 #include "mlir/Analysis/Presburger/Utils.h"
 #include "mlir/Support/LogicalResult.h"
@@ -41,8 +41,8 @@
 /// these constraints that are redundant, i.e. a subset of constraints that
 /// doesn't constrain the affine set further after adding the non-redundant
 /// constraints. The LexSimplex class provides support for computing the
-/// lexicographical minimum of an IntegerPolyhedron. Both these classes can be
-/// constructed from an IntegerPolyhedron, and both inherit common
+/// lexicographical minimum of an IntegerRelation. Both these classes can be
+/// constructed from an IntegerRelation, and both inherit common
 /// functionality from SimplexBase.
 ///
 /// The implementations of the Simplex and SimplexBase classes, other than the
@@ -201,8 +201,8 @@
   /// Rollback to a snapshot. This invalidates all later snapshots.
   void rollback(unsigned snapshot);
 
-  /// Add all the constraints from the given IntegerPolyhedron.
-  void intersectIntegerPolyhedron(const IntegerPolyhedron &poly);
+  /// Add all the constraints from the given IntegerRelation.
+  void intersectIntegerRelation(const IntegerRelation &rel);
 
   /// Print the tableau's internal state.
   void print(raw_ostream &os) const;
@@ -419,9 +419,9 @@
 public:
   explicit LexSimplex(unsigned nVar)
       : SimplexBase(nVar, /*mustUseBigM=*/true) {}
-  explicit LexSimplex(const IntegerPolyhedron &constraints)
+  explicit LexSimplex(const IntegerRelation &constraints)
       : LexSimplex(constraints.getNumIds()) {
-    intersectIntegerPolyhedron(constraints);
+    intersectIntegerRelation(constraints);
   }
   ~LexSimplex() override = default;
 
@@ -515,9 +515,9 @@
 
   Simplex() = delete;
   explicit Simplex(unsigned nVar) : SimplexBase(nVar, /*mustUseBigM=*/false) {}
-  explicit Simplex(const IntegerPolyhedron &constraints)
+  explicit Simplex(const IntegerRelation &constraints)
       : Simplex(constraints.getNumIds()) {
-    intersectIntegerPolyhedron(constraints);
+    intersectIntegerRelation(constraints);
   }
   ~Simplex() override = default;
 
@@ -595,9 +595,9 @@
   /// Check if the specified equality already holds in the polytope.
   bool isRedundantEquality(ArrayRef<int64_t> coeffs);
 
-  /// Returns true if this Simplex's polytope is a rational subset of `poly`.
+  /// Returns true if this Simplex's polytope is a rational subset of `rel`.
   /// Otherwise, returns false.
-  bool isRationalSubsetOf(const IntegerPolyhedron &poly);
+  bool isRationalSubsetOf(const IntegerRelation &rel);
 
   /// Returns the current sample point if it is integral. Otherwise, returns
   /// None.
diff --git a/mlir/include/mlir/Analysis/Presburger/Utils.h b/mlir/include/mlir/Analysis/Presburger/Utils.h
--- a/mlir/include/mlir/Analysis/Presburger/Utils.h
+++ b/mlir/include/mlir/Analysis/Presburger/Utils.h
@@ -19,7 +19,7 @@
 namespace mlir {
 namespace presburger {
 
-class IntegerPolyhedron;
+class IntegerRelation;
 
 /// This class represents the result of operations optimizing something subject
 /// to some constraints. If the constraints were not satisfiable the, kind will
@@ -109,7 +109,7 @@
 /// the representation could be computed, `dividend` and `denominator` are set.
 /// If the representation could not be computed, the kind attribute in
 /// `MaybeLocalRepr` is set to None.
-MaybeLocalRepr computeSingleVarRepr(const IntegerPolyhedron &cst,
+MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst,
                                     ArrayRef<bool> foundRepr, unsigned pos,
                                     SmallVector<int64_t, 8> &dividend,
                                     unsigned &divisor);
@@ -124,7 +124,7 @@
 /// `true`, the divisions are merged i.e. `j^th` division gets eliminated and
 /// it's each instance is replaced by `i^th` division. If it returns `false`,
 /// the divisions are not merged. `merge` can also do side effects, For example
-/// it can merge the local identifiers in IntegerPolyhedron.
+/// it can merge the local identifiers in IntegerRelation.
 void removeDuplicateDivs(
     std::vector<SmallVector<int64_t, 8>> &divs,
     SmallVectorImpl<unsigned> &denoms, unsigned localOffset,
diff --git a/mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h b/mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h
--- a/mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h
+++ b/mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h
@@ -13,7 +13,7 @@
 #ifndef MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H
 #define MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H
 
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Analysis/Presburger/Matrix.h"
 #include "mlir/IR/AffineExpr.h"
 #include "mlir/IR/OpDefinition.h"
@@ -98,7 +98,7 @@
   /// Return the kind of this FlatAffineConstraints.
   Kind getKind() const override { return Kind::FlatAffineConstraints; }
 
-  static bool classof(const IntegerPolyhedron *cst) {
+  static bool classof(const IntegerRelation *cst) {
     return cst->getKind() == Kind::FlatAffineConstraints;
   }
 
@@ -179,7 +179,7 @@
   LogicalResult composeMatchingMap(AffineMap other);
 
   /// Replaces the contents of this FlatAffineConstraints with `other`.
-  void clearAndCopyFrom(const IntegerPolyhedron &other) override;
+  void clearAndCopyFrom(const IntegerRelation &other) override;
 
   /// Gets the lower and upper bound of the `offset` + `pos`th identifier
   /// treating [0, offset) U [offset + num, symStartPos) as dimensions and
@@ -286,7 +286,7 @@
   /// Return the kind of this FlatAffineConstraints.
   Kind getKind() const override { return Kind::FlatAffineValueConstraints; }
 
-  static bool classof(const IntegerPolyhedron *cst) {
+  static bool classof(const IntegerRelation *cst) {
     return cst->getKind() == Kind::FlatAffineValueConstraints;
   }
 
@@ -484,7 +484,7 @@
   bool areIdsAlignedWithOther(const FlatAffineValueConstraints &other);
 
   /// Replaces the contents of this FlatAffineValueConstraints with `other`.
-  void clearAndCopyFrom(const IntegerPolyhedron &other) override;
+  void clearAndCopyFrom(const IntegerRelation &other) override;
 
   /// Returns the Value associated with the pos^th identifier. Asserts if
   /// no Value identifier was associated.
diff --git a/mlir/lib/Analysis/Presburger/CMakeLists.txt b/mlir/lib/Analysis/Presburger/CMakeLists.txt
--- a/mlir/lib/Analysis/Presburger/CMakeLists.txt
+++ b/mlir/lib/Analysis/Presburger/CMakeLists.txt
@@ -1,5 +1,5 @@
 add_mlir_library(MLIRPresburger
-  IntegerPolyhedron.cpp
+  IntegerRelation.cpp
   LinearTransform.cpp
   Matrix.cpp
   PresburgerSet.cpp
diff --git a/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp b/mlir/lib/Analysis/Presburger/IntegerRelation.cpp
rename from mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp
rename to mlir/lib/Analysis/Presburger/IntegerRelation.cpp
--- a/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp
+++ b/mlir/lib/Analysis/Presburger/IntegerRelation.cpp
@@ -1,4 +1,4 @@
-//===- IntegerPolyhedron.cpp - MLIR IntegerPolyhedron Class ---------------===//
+//===- 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.
@@ -6,11 +6,13 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// A class to represent an integer polyhedron.
+// 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/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Analysis/Presburger/LinearTransform.h"
 #include "mlir/Analysis/Presburger/PresburgerSet.h"
 #include "mlir/Analysis/Presburger/Simplex.h"
@@ -27,11 +29,15 @@
 using llvm::SmallDenseMap;
 using llvm::SmallDenseSet;
 
+std::unique_ptr<IntegerRelation> IntegerRelation::clone() const {
+  return std::make_unique<IntegerRelation>(*this);
+}
+
 std::unique_ptr<IntegerPolyhedron> IntegerPolyhedron::clone() const {
   return std::make_unique<IntegerPolyhedron>(*this);
 }
 
-void IntegerPolyhedron::append(const IntegerPolyhedron &other) {
+void IntegerRelation::append(const IntegerRelation &other) {
   assert(PresburgerLocalSpace::isEqual(other) && "Spaces must be equal.");
 
   inequalities.reserveRows(inequalities.getNumRows() +
@@ -46,16 +52,32 @@
   }
 }
 
-bool IntegerPolyhedron::isEqual(const IntegerPolyhedron &other) const {
-  return PresburgerSet(*this).isEqual(PresburgerSet(other));
+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)));
 }
 
-bool IntegerPolyhedron::isSubsetOf(const IntegerPolyhedron &other) const {
-  return PresburgerSet(*this).isSubsetOf(PresburgerSet(other));
+bool IntegerRelation::isSubsetOf(const IntegerRelation &other) const {
+  assert(PresburgerLocalSpace::isEqual(other) && "Spaces must be equal.");
+  return PresburgerSet(createSetFromRelation(*this))
+      .isSubsetOf(PresburgerSet(createSetFromRelation(other)));
 }
 
 MaybeOptimum<SmallVector<Fraction, 8>>
-IntegerPolyhedron::findRationalLexMin() const {
+IntegerRelation::findRationalLexMin() const {
   assert(getNumSymbolIds() == 0 && "Symbols are not supported!");
   MaybeOptimum<SmallVector<Fraction, 8>> maybeLexMin =
       LexSimplex(*this).findRationalLexMin();
@@ -75,7 +97,7 @@
 }
 
 MaybeOptimum<SmallVector<int64_t, 8>>
-IntegerPolyhedron::findIntegerLexMin() const {
+IntegerRelation::findIntegerLexMin() const {
   assert(getNumSymbolIds() == 0 && "Symbols are not supported!");
   MaybeOptimum<SmallVector<int64_t, 8>> maybeLexMin =
       LexSimplex(*this).findIntegerLexMin();
@@ -94,7 +116,7 @@
   return maybeLexMin;
 }
 
-unsigned IntegerPolyhedron::insertId(IdKind kind, unsigned pos, unsigned num) {
+unsigned IntegerRelation::insertId(IdKind kind, unsigned pos, unsigned num) {
   assert(pos <= getNumIdKind(kind));
 
   unsigned insertPos = PresburgerLocalSpace::insertId(kind, pos, num);
@@ -103,39 +125,39 @@
   return insertPos;
 }
 
-unsigned IntegerPolyhedron::appendId(IdKind kind, unsigned num) {
+unsigned IntegerRelation::appendId(IdKind kind, unsigned num) {
   unsigned pos = getNumIdKind(kind);
   return insertId(kind, pos, num);
 }
 
-void IntegerPolyhedron::addEquality(ArrayRef<int64_t> eq) {
+void IntegerRelation::addEquality(ArrayRef<int64_t> eq) {
   assert(eq.size() == getNumCols());
   unsigned row = equalities.appendExtraRow();
   for (unsigned i = 0, e = eq.size(); i < e; ++i)
     equalities(row, i) = eq[i];
 }
 
-void IntegerPolyhedron::addInequality(ArrayRef<int64_t> inEq) {
+void IntegerRelation::addInequality(ArrayRef<int64_t> inEq) {
   assert(inEq.size() == getNumCols());
   unsigned row = inequalities.appendExtraRow();
   for (unsigned i = 0, e = inEq.size(); i < e; ++i)
     inequalities(row, i) = inEq[i];
 }
 
-void IntegerPolyhedron::removeId(IdKind kind, unsigned pos) {
+void IntegerRelation::removeId(IdKind kind, unsigned pos) {
   removeIdRange(kind, pos, pos + 1);
 }
 
-void IntegerPolyhedron::removeId(unsigned pos) { removeIdRange(pos, pos + 1); }
+void IntegerRelation::removeId(unsigned pos) { removeIdRange(pos, pos + 1); }
 
-void IntegerPolyhedron::removeIdRange(IdKind kind, unsigned idStart,
-                                      unsigned idLimit) {
+void IntegerRelation::removeIdRange(IdKind kind, unsigned idStart,
+                                    unsigned idLimit) {
   assert(idLimit <= getNumIdKind(kind));
   removeIdRange(getIdKindOffset(kind) + idStart,
                 getIdKindOffset(kind) + idLimit);
 }
 
-void IntegerPolyhedron::removeIdRange(unsigned idStart, unsigned idLimit) {
+void IntegerRelation::removeIdRange(unsigned idStart, unsigned idLimit) {
   // Update space paramaters.
   PresburgerLocalSpace::removeIdRange(idStart, idLimit);
 
@@ -144,27 +166,27 @@
   inequalities.removeColumns(idStart, idLimit - idStart);
 }
 
-void IntegerPolyhedron::removeEquality(unsigned pos) {
+void IntegerRelation::removeEquality(unsigned pos) {
   equalities.removeRow(pos);
 }
 
-void IntegerPolyhedron::removeInequality(unsigned pos) {
+void IntegerRelation::removeInequality(unsigned pos) {
   inequalities.removeRow(pos);
 }
 
-void IntegerPolyhedron::removeEqualityRange(unsigned start, unsigned end) {
+void IntegerRelation::removeEqualityRange(unsigned start, unsigned end) {
   if (start >= end)
     return;
   equalities.removeRows(start, end - start);
 }
 
-void IntegerPolyhedron::removeInequalityRange(unsigned start, unsigned end) {
+void IntegerRelation::removeInequalityRange(unsigned start, unsigned end) {
   if (start >= end)
     return;
   inequalities.removeRows(start, end - start);
 }
 
-void IntegerPolyhedron::swapId(unsigned posA, unsigned posB) {
+void IntegerRelation::swapId(unsigned posA, unsigned posB) {
   assert(posA < getNumIds() && "invalid position A");
   assert(posB < getNumIds() && "invalid position B");
 
@@ -175,7 +197,7 @@
   equalities.swapColumns(posA, posB);
 }
 
-void IntegerPolyhedron::clearConstraints() {
+void IntegerRelation::clearConstraints() {
   equalities.resizeVertically(0);
   inequalities.resizeVertically(0);
 }
@@ -183,7 +205,7 @@
 /// Gather all lower and upper bounds of the identifier at `pos`, and
 /// optionally any equalities on it. In addition, the bounds are to be
 /// independent of identifiers in position range [`offset`, `offset` + `num`).
-void IntegerPolyhedron::getLowerAndUpperBoundIndices(
+void IntegerRelation::getLowerAndUpperBoundIndices(
     unsigned pos, SmallVectorImpl<unsigned> *lbIndices,
     SmallVectorImpl<unsigned> *ubIndices, SmallVectorImpl<unsigned> *eqIndices,
     unsigned offset, unsigned num) const {
@@ -234,7 +256,7 @@
   }
 }
 
-bool IntegerPolyhedron::hasConsistentState() const {
+bool IntegerRelation::hasConsistentState() const {
   if (!inequalities.hasConsistentState())
     return false;
   if (!equalities.hasConsistentState())
@@ -242,8 +264,7 @@
   return true;
 }
 
-void IntegerPolyhedron::setAndEliminate(unsigned pos,
-                                        ArrayRef<int64_t> values) {
+void IntegerRelation::setAndEliminate(unsigned pos, ArrayRef<int64_t> values) {
   if (values.empty())
     return;
   assert(pos + values.size() <= getNumIds() &&
@@ -259,15 +280,15 @@
   removeIdRange(pos, pos + values.size());
 }
 
-void IntegerPolyhedron::clearAndCopyFrom(const IntegerPolyhedron &other) {
+void IntegerRelation::clearAndCopyFrom(const IntegerRelation &other) {
   *this = other;
 }
 
 // Searches for a constraint with a non-zero coefficient at `colIdx` in
 // equality (isEq=true) or inequality (isEq=false) constraints.
 // Returns true and sets row found in search in `rowIdx`, false otherwise.
-bool IntegerPolyhedron::findConstraintWithNonZeroAt(unsigned colIdx, bool isEq,
-                                                    unsigned *rowIdx) const {
+bool IntegerRelation::findConstraintWithNonZeroAt(unsigned colIdx, bool isEq,
+                                                  unsigned *rowIdx) const {
   assert(colIdx < getNumCols() && "position out of bounds");
   auto at = [&](unsigned rowIdx) -> int64_t {
     return isEq ? atEq(rowIdx, colIdx) : atIneq(rowIdx, colIdx);
@@ -281,14 +302,14 @@
   return false;
 }
 
-void IntegerPolyhedron::normalizeConstraintsByGCD() {
+void IntegerRelation::normalizeConstraintsByGCD() {
   for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
     equalities.normalizeRow(i);
   for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
     inequalities.normalizeRow(i);
 }
 
-bool IntegerPolyhedron::hasInvalidConstraint() const {
+bool IntegerRelation::hasInvalidConstraint() const {
   assert(hasConsistentState());
   auto check = [&](bool isEq) -> bool {
     unsigned numCols = getNumCols();
@@ -321,7 +342,7 @@
 /// Eliminate identifier from constraint at `rowIdx` based on coefficient at
 /// pivotRow, pivotCol. Columns in range [elimColStart, pivotCol) will not be
 /// updated as they have already been eliminated.
-static void eliminateFromConstraint(IntegerPolyhedron *constraints,
+static void eliminateFromConstraint(IntegerRelation *constraints,
                                     unsigned rowIdx, unsigned pivotRow,
                                     unsigned pivotCol, unsigned elimColStart,
                                     bool isEq) {
@@ -358,8 +379,8 @@
 /// identifiers [start, end). It is often best to eliminate in the increasing
 /// order of these counts when doing Fourier-Motzkin elimination since FM adds
 /// that many new constraints.
-static unsigned getBestIdToEliminate(const IntegerPolyhedron &cst,
-                                     unsigned start, unsigned end) {
+static unsigned getBestIdToEliminate(const IntegerRelation &cst, unsigned start,
+                                     unsigned end) {
   assert(start < cst.getNumIds() && end < cst.getNumIds() + 1);
 
   auto getProductOfNumLowerUpperBounds = [&](unsigned pos) {
@@ -391,11 +412,11 @@
 // using the GCD test (on all equality constraints) and checking for trivially
 // invalid constraints. Returns 'true' if the constraint system is found to be
 // empty; false otherwise.
-bool IntegerPolyhedron::isEmpty() const {
+bool IntegerRelation::isEmpty() const {
   if (isEmptyByGCDTest() || hasInvalidConstraint())
     return true;
 
-  IntegerPolyhedron tmpCst(*this);
+  IntegerRelation tmpCst(*this);
 
   // First, eliminate as many local variables as possible using equalities.
   tmpCst.removeRedundantLocalVars();
@@ -422,7 +443,7 @@
     // Check for a constraint explosion. This rarely happens in practice, but
     // this check exists as a safeguard against improperly constructed
     // constraint systems or artificially created arbitrarily complex systems
-    // that aren't the intended use case for IntegerPolyhedron. This is
+    // that aren't the intended use case for IntegerRelation. This is
     // needed since FM has a worst case exponential complexity in theory.
     if (tmpCst.getNumConstraints() >= kExplosionFactor * getNumIds()) {
       LLVM_DEBUG(llvm::dbgs() << "FM constraint explosion detected\n");
@@ -452,7 +473,7 @@
 //
 //  GCD of c_1, c_2, ..., c_n divides c_0.
 //
-bool IntegerPolyhedron::isEmptyByGCDTest() const {
+bool IntegerRelation::isEmptyByGCDTest() const {
   assert(hasConsistentState());
   unsigned numCols = getNumCols();
   for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
@@ -475,7 +496,7 @@
 //
 // It is sufficient to check the perpendiculars of the constraints, as the set
 // of perpendiculars which are bounded must span all bounded directions.
-Matrix IntegerPolyhedron::getBoundedDirections() const {
+Matrix IntegerRelation::getBoundedDirections() const {
   // Note that it is necessary to add the equalities too (which the constructor
   // does) even though we don't need to check if they are bounded; whether an
   // inequality is bounded or not depends on what other constraints, including
@@ -516,34 +537,34 @@
   return dirs;
 }
 
-bool eqInvolvesSuffixDims(const IntegerPolyhedron &poly, unsigned eqIndex,
+bool eqInvolvesSuffixDims(const IntegerRelation &rel, unsigned eqIndex,
                           unsigned numDims) {
-  for (unsigned e = poly.getNumIds(), j = e - numDims; j < e; ++j)
-    if (poly.atEq(eqIndex, j) != 0)
+  for (unsigned e = rel.getNumIds(), j = e - numDims; j < e; ++j)
+    if (rel.atEq(eqIndex, j) != 0)
       return true;
   return false;
 }
-bool ineqInvolvesSuffixDims(const IntegerPolyhedron &poly, unsigned ineqIndex,
+bool ineqInvolvesSuffixDims(const IntegerRelation &rel, unsigned ineqIndex,
                             unsigned numDims) {
-  for (unsigned e = poly.getNumIds(), j = e - numDims; j < e; ++j)
-    if (poly.atIneq(ineqIndex, j) != 0)
+  for (unsigned e = rel.getNumIds(), j = e - numDims; j < e; ++j)
+    if (rel.atIneq(ineqIndex, j) != 0)
       return true;
   return false;
 }
 
-void removeConstraintsInvolvingSuffixDims(IntegerPolyhedron &poly,
+void removeConstraintsInvolvingSuffixDims(IntegerRelation &rel,
                                           unsigned unboundedDims) {
   // We iterate backwards so that whether we remove constraint i - 1 or not, the
   // next constraint to be tested is always i - 2.
-  for (unsigned i = poly.getNumEqualities(); i > 0; i--)
-    if (eqInvolvesSuffixDims(poly, i - 1, unboundedDims))
-      poly.removeEquality(i - 1);
-  for (unsigned i = poly.getNumInequalities(); i > 0; i--)
-    if (ineqInvolvesSuffixDims(poly, i - 1, unboundedDims))
-      poly.removeInequality(i - 1);
+  for (unsigned i = rel.getNumEqualities(); i > 0; i--)
+    if (eqInvolvesSuffixDims(rel, i - 1, unboundedDims))
+      rel.removeEquality(i - 1);
+  for (unsigned i = rel.getNumInequalities(); i > 0; i--)
+    if (ineqInvolvesSuffixDims(rel, i - 1, unboundedDims))
+      rel.removeInequality(i - 1);
 }
 
-bool IntegerPolyhedron::isIntegerEmpty() const {
+bool IntegerRelation::isIntegerEmpty() const {
   return !findIntegerSample().hasValue();
 }
 
@@ -592,7 +613,7 @@
 ///
 /// Concatenating the samples from B and C gives a sample v in S*T, so the
 /// returned sample T*v is a sample in S.
-Optional<SmallVector<int64_t, 8>> IntegerPolyhedron::findIntegerSample() const {
+Optional<SmallVector<int64_t, 8>> IntegerRelation::findIntegerSample() const {
   // First, try the GCD test heuristic.
   if (isEmptyByGCDTest())
     return {};
@@ -619,11 +640,11 @@
       LinearTransform::makeTransformToColumnEchelon(std::move(m));
   const LinearTransform &transform = result.second;
   // 1) Apply T to S to obtain S*T.
-  IntegerPolyhedron transformedSet = transform.applyTo(*this);
+  IntegerRelation transformedSet = transform.applyTo(*this);
 
   // 2) Remove the unbounded dimensions and constraints involving them to
   // obtain a bounded set.
-  IntegerPolyhedron boundedSet(transformedSet);
+  IntegerRelation boundedSet(transformedSet);
   unsigned numBoundedDims = result.first;
   unsigned numUnboundedDims = getNumIds() - numBoundedDims;
   removeConstraintsInvolvingSuffixDims(boundedSet, numUnboundedDims);
@@ -640,7 +661,7 @@
   // 4) Substitute the values of the bounded dimensions into S*T to obtain a
   // full-dimensional cone, which necessarily contains an integer sample.
   transformedSet.setAndEliminate(0, *boundedSample);
-  IntegerPolyhedron &cone = transformedSet;
+  IntegerRelation &cone = transformedSet;
 
   // 5) Obtain an integer sample from the cone.
   //
@@ -709,7 +730,7 @@
 /// A point satisfies an equality iff the value of the equality at the
 /// expression is zero, and it satisfies an inequality iff the value of the
 /// inequality at that point is non-negative.
-bool IntegerPolyhedron::containsPoint(ArrayRef<int64_t> point) const {
+bool IntegerRelation::containsPoint(ArrayRef<int64_t> point) const {
   for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
     if (valueAt(getEquality(i), point) != 0)
       return false;
@@ -721,20 +742,20 @@
   return true;
 }
 
-void IntegerPolyhedron::getLocalReprs(std::vector<MaybeLocalRepr> &repr) const {
+void IntegerRelation::getLocalReprs(std::vector<MaybeLocalRepr> &repr) const {
   std::vector<SmallVector<int64_t, 8>> dividends(getNumLocalIds());
   SmallVector<unsigned, 4> denominators(getNumLocalIds());
   getLocalReprs(dividends, denominators, repr);
 }
 
-void IntegerPolyhedron::getLocalReprs(
+void IntegerRelation::getLocalReprs(
     std::vector<SmallVector<int64_t, 8>> &dividends,
     SmallVector<unsigned, 4> &denominators) const {
   std::vector<MaybeLocalRepr> repr(getNumLocalIds());
   getLocalReprs(dividends, denominators, repr);
 }
 
-void IntegerPolyhedron::getLocalReprs(
+void IntegerRelation::getLocalReprs(
     std::vector<SmallVector<int64_t, 8>> &dividends,
     SmallVector<unsigned, 4> &denominators,
     std::vector<MaybeLocalRepr> &repr) const {
@@ -781,7 +802,7 @@
 // Example on how this affects practical cases: consider the scenario:
 // 64*i >= 100, j = 64*i; without a tightening, elimination of i would yield
 // j >= 100 instead of the tighter (exact) j >= 128.
-void IntegerPolyhedron::gcdTightenInequalities() {
+void IntegerRelation::gcdTightenInequalities() {
   unsigned numCols = getNumCols();
   for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
     // Normalize the constraint and tighten the constant term by the GCD.
@@ -793,8 +814,8 @@
 
 // Eliminates all identifier variables in column range [posStart, posLimit).
 // Returns the number of variables eliminated.
-unsigned IntegerPolyhedron::gaussianEliminateIds(unsigned posStart,
-                                                 unsigned posLimit) {
+unsigned IntegerRelation::gaussianEliminateIds(unsigned posStart,
+                                               unsigned posLimit) {
   // Return if identifier positions to eliminate are out of range.
   assert(posLimit <= getNumIds());
   assert(hasConsistentState());
@@ -843,12 +864,12 @@
 
 // A more complex check to eliminate redundant inequalities. Uses FourierMotzkin
 // to check if a constraint is redundant.
-void IntegerPolyhedron::removeRedundantInequalities() {
+void IntegerRelation::removeRedundantInequalities() {
   SmallVector<bool, 32> redun(getNumInequalities(), false);
   // To check if an inequality is redundant, we replace the inequality by its
   // complement (for eg., i - 1 >= 0 by i <= 0), and check if the resulting
   // system is empty. If it is, the inequality is redundant.
-  IntegerPolyhedron tmpCst(*this);
+  IntegerRelation tmpCst(*this);
   for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
     // Change the inequality to its complement.
     tmpCst.inequalities.negateRow(r);
@@ -875,7 +896,7 @@
 
 // A more complex check to eliminate redundant inequalities and equalities. Uses
 // Simplex to check if a constraint is redundant.
-void IntegerPolyhedron::removeRedundantConstraints() {
+void IntegerRelation::removeRedundantConstraints() {
   // First, we run gcdTightenInequalities. This allows us to catch some
   // constraints which are not redundant when considering rational solutions
   // but are redundant in terms of integer solutions.
@@ -906,7 +927,7 @@
   equalities.resizeVertically(pos);
 }
 
-Optional<uint64_t> IntegerPolyhedron::computeVolume() const {
+Optional<uint64_t> IntegerRelation::computeVolume() const {
   assert(getNumSymbolIds() == 0 && "Symbols are not yet supported!");
 
   Simplex simplex(*this);
@@ -918,8 +939,8 @@
   // Just find the maximum and minimum integer value of each non-local id
   // separately, thus finding the number of integer values each such id can
   // take. Multiplying these together gives a valid overapproximation of the
-  // number of integer points in the polyhedron. The result this gives is
-  // equivalent to projecting (rationally) the polyhedron onto its non-local ids
+  // number of integer points in the relation. The result this gives is
+  // equivalent to projecting (rationally) the relation onto its non-local ids
   // and returning the number of integer points in a minimal axis-parallel
   // hyperrectangular overapproximation of that.
   //
@@ -963,8 +984,7 @@
   return count;
 }
 
-void IntegerPolyhedron::eliminateRedundantLocalId(unsigned posA,
-                                                  unsigned posB) {
+void IntegerRelation::eliminateRedundantLocalId(unsigned posA, unsigned posB) {
   assert(posA < getNumLocalIds() && "Invalid local id position");
   assert(posB < getNumLocalIds() && "Invalid local id position");
 
@@ -986,28 +1006,28 @@
 /// representation are considered duplicate and are merged. It is possible that
 /// division representation for some local id cannot be obtained, and thus these
 /// local ids are not considered for detecting duplicates.
-void IntegerPolyhedron::mergeLocalIds(IntegerPolyhedron &other) {
+void IntegerRelation::mergeLocalIds(IntegerRelation &other) {
   assert(PresburgerSpace::isEqual(other) && "Spaces should match.");
 
-  IntegerPolyhedron &polyA = *this;
-  IntegerPolyhedron &polyB = other;
+  IntegerRelation &relA = *this;
+  IntegerRelation &relB = other;
 
-  // Merge local ids of polyA and polyB without using division information,
-  // i.e. append local ids of `polyB` to `polyA` and insert local ids of `polyA`
-  // to `polyB` at start of its local ids.
-  unsigned initLocals = polyA.getNumLocalIds();
-  insertId(IdKind::Local, polyA.getNumLocalIds(), polyB.getNumLocalIds());
-  polyB.insertId(IdKind::Local, 0, initLocals);
+  // Merge local ids of relA and relB without using division information,
+  // i.e. append local ids of `relB` to `relA` and insert local ids of `relA`
+  // to `relB` at start of its local ids.
+  unsigned initLocals = relA.getNumLocalIds();
+  insertId(IdKind::Local, relA.getNumLocalIds(), relB.getNumLocalIds());
+  relB.insertId(IdKind::Local, 0, initLocals);
 
-  // Get division representations from each poly.
+  // Get division representations from each rel.
   std::vector<SmallVector<int64_t, 8>> divsA, divsB;
   SmallVector<unsigned, 4> denomsA, denomsB;
-  polyA.getLocalReprs(divsA, denomsA);
-  polyB.getLocalReprs(divsB, denomsB);
+  relA.getLocalReprs(divsA, denomsA);
+  relB.getLocalReprs(divsB, denomsB);
 
-  // Copy division information for polyB into `divsA` and `denomsA`, so that
-  // these have the combined division information of both polys. Since newly
-  // added local variables in polyA and polyB have no constraints, they will not
+  // Copy division information for relB into `divsA` and `denomsA`, so that
+  // these have the combined division information of both rels. Since newly
+  // added local variables in relA and relB have no constraints, they will not
   // have any division representation.
   std::copy(divsB.begin() + initLocals, divsB.end(),
             divsA.begin() + initLocals);
@@ -1016,9 +1036,9 @@
 
   // Merge function that merges the local variables in both sets by treating
   // them as the same identifier.
-  auto merge = [&polyA, &polyB](unsigned i, unsigned j) -> bool {
-    polyA.eliminateRedundantLocalId(i, j);
-    polyB.eliminateRedundantLocalId(i, j);
+  auto merge = [&relA, &relB](unsigned i, unsigned j) -> bool {
+    relA.eliminateRedundantLocalId(i, j);
+    relB.eliminateRedundantLocalId(i, j);
     return true;
   };
 
@@ -1033,7 +1053,7 @@
 /// If an equality satisfies this form, the local variable is replaced in
 /// each constraint and then removed. The equality used to replace this local
 /// variable is also removed.
-void IntegerPolyhedron::removeRedundantLocalVars() {
+void IntegerRelation::removeRedundantLocalVars() {
   // Normalize the equality constraints to reduce coefficients of local
   // variables to 1 wherever possible.
   for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
@@ -1075,8 +1095,7 @@
   }
 }
 
-void IntegerPolyhedron::convertDimToLocal(unsigned dimStart,
-                                          unsigned dimLimit) {
+void IntegerRelation::convertDimToLocal(unsigned dimStart, unsigned dimLimit) {
   assert(dimLimit <= getNumDimIds() && "Invalid dim pos range");
 
   if (dimStart >= dimLimit)
@@ -1095,7 +1114,7 @@
   removeIdRange(dimStart, dimLimit);
 }
 
-void IntegerPolyhedron::addBound(BoundType type, unsigned pos, int64_t value) {
+void IntegerRelation::addBound(BoundType type, unsigned pos, int64_t value) {
   assert(pos < getNumCols());
   if (type == BoundType::EQ) {
     unsigned row = equalities.appendExtraRow();
@@ -1109,8 +1128,8 @@
   }
 }
 
-void IntegerPolyhedron::addBound(BoundType type, ArrayRef<int64_t> expr,
-                                 int64_t value) {
+void IntegerRelation::addBound(BoundType type, ArrayRef<int64_t> expr,
+                               int64_t value) {
   assert(type != BoundType::EQ && "EQ not implemented");
   assert(expr.size() == getNumCols());
   unsigned row = inequalities.appendExtraRow();
@@ -1125,8 +1144,8 @@
 /// respect to a positive constant 'divisor'. Two constraints are added to the
 /// system to capture equivalence with the floordiv.
 ///      q = expr floordiv c    <=>   c*q <= expr <= c*q + c - 1.
-void IntegerPolyhedron::addLocalFloorDiv(ArrayRef<int64_t> dividend,
-                                         int64_t divisor) {
+void IntegerRelation::addLocalFloorDiv(ArrayRef<int64_t> dividend,
+                                       int64_t divisor) {
   assert(dividend.size() == getNumCols() && "incorrect dividend size");
   assert(divisor > 0 && "positive divisor expected");
 
@@ -1154,7 +1173,7 @@
 /// symbols are also treated like a constant, i.e., an affine function of the
 /// symbols is also treated like a constant. Returns -1 if such an equality
 /// could not be found.
-static int findEqualityToConstant(const IntegerPolyhedron &cst, unsigned pos,
+static int findEqualityToConstant(const IntegerRelation &cst, unsigned pos,
                                   bool symbolic = false) {
   assert(pos < cst.getNumIds() && "invalid position");
   for (unsigned r = 0, e = cst.getNumEqualities(); r < e; r++) {
@@ -1179,7 +1198,7 @@
   return -1;
 }
 
-LogicalResult IntegerPolyhedron::constantFoldId(unsigned pos) {
+LogicalResult IntegerRelation::constantFoldId(unsigned pos) {
   assert(pos < getNumIds() && "invalid position");
   int rowIdx;
   if ((rowIdx = findEqualityToConstant(*this, pos)) == -1)
@@ -1192,7 +1211,7 @@
   return success();
 }
 
-void IntegerPolyhedron::constantFoldIdRange(unsigned pos, unsigned num) {
+void IntegerRelation::constantFoldIdRange(unsigned pos, unsigned num) {
   for (unsigned s = pos, t = pos, e = pos + num; s < e; s++) {
     if (failed(constantFoldId(t)))
       t++;
@@ -1213,7 +1232,7 @@
 //       s0 + s1 + 16 <= d0 <= s0 + s1 + 31, returns 16.
 //       s0 - 7 <= 8*j <= s0 returns 1 with lb = s0, lbDivisor = 8 (since lb =
 //       ceil(s0 - 7 / 8) = floor(s0 / 8)).
-Optional<int64_t> IntegerPolyhedron::getConstantBoundOnDimSize(
+Optional<int64_t> IntegerRelation::getConstantBoundOnDimSize(
     unsigned pos, SmallVectorImpl<int64_t> *lb, int64_t *boundFloorDivisor,
     SmallVectorImpl<int64_t> *ub, unsigned *minLbPos,
     unsigned *minUbPos) const {
@@ -1341,7 +1360,7 @@
 
 template <bool isLower>
 Optional<int64_t>
-IntegerPolyhedron::computeConstantLowerOrUpperBound(unsigned pos) {
+IntegerRelation::computeConstantLowerOrUpperBound(unsigned pos) {
   assert(pos < getNumIds() && "invalid position");
   // Project to 'pos'.
   projectOut(0, pos);
@@ -1397,27 +1416,27 @@
   return minOrMaxConst;
 }
 
-Optional<int64_t> IntegerPolyhedron::getConstantBound(BoundType type,
-                                                      unsigned pos) const {
+Optional<int64_t> IntegerRelation::getConstantBound(BoundType type,
+                                                    unsigned pos) const {
   if (type == BoundType::LB)
-    return IntegerPolyhedron(*this)
+    return IntegerRelation(*this)
         .computeConstantLowerOrUpperBound</*isLower=*/true>(pos);
   if (type == BoundType::UB)
-    return IntegerPolyhedron(*this)
+    return IntegerRelation(*this)
         .computeConstantLowerOrUpperBound</*isLower=*/false>(pos);
 
   assert(type == BoundType::EQ && "expected EQ");
   Optional<int64_t> lb =
-      IntegerPolyhedron(*this)
-          .computeConstantLowerOrUpperBound</*isLower=*/true>(pos);
+      IntegerRelation(*this).computeConstantLowerOrUpperBound</*isLower=*/true>(
+          pos);
   Optional<int64_t> ub =
-      IntegerPolyhedron(*this)
+      IntegerRelation(*this)
           .computeConstantLowerOrUpperBound</*isLower=*/false>(pos);
   return (lb && ub && *lb == *ub) ? Optional<int64_t>(*ub) : None;
 }
 
 // A simple (naive and conservative) check for hyper-rectangularity.
-bool IntegerPolyhedron::isHyperRectangular(unsigned pos, unsigned num) const {
+bool IntegerRelation::isHyperRectangular(unsigned pos, unsigned num) const {
   assert(pos < getNumCols() - 1);
   // Check for two non-zero coefficients in the range [pos, pos + sum).
   for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
@@ -1447,7 +1466,7 @@
 /// considered trivially true.
 //  Uses a DenseSet to hash and detect duplicates followed by a linear scan to
 //  remove duplicates in place.
-void IntegerPolyhedron::removeTrivialRedundancy() {
+void IntegerRelation::removeTrivialRedundancy() {
   gcdTightenInequalities();
   normalizeConstraintsByGCD();
 
@@ -1558,8 +1577,8 @@
 /// darkShadow = false, isResultIntegerExact = nullptr are default values.
 // TODO: a slight modification to yield dark shadow version of FM (tightened),
 // which can prove the existence of a solution if there is one.
-void IntegerPolyhedron::fourierMotzkinEliminate(unsigned pos, bool darkShadow,
-                                                bool *isResultIntegerExact) {
+void IntegerRelation::fourierMotzkinEliminate(unsigned pos, bool darkShadow,
+                                              bool *isResultIntegerExact) {
   LLVM_DEBUG(llvm::dbgs() << "FM input (eliminate pos " << pos << "):\n");
   LLVM_DEBUG(dump());
   assert(pos < getNumIds() && "invalid position");
@@ -1616,18 +1635,19 @@
   }
 
   // Set the number of dimensions, symbols, locals in the resulting system.
-  unsigned newNumDims =
-      getNumDimIds() - getIdKindOverlap(IdKind::SetDim, pos, pos + 1);
+  unsigned newNumDomain =
+      getNumDomainIds() - getIdKindOverlap(IdKind::Domain, pos, pos + 1);
+  unsigned newNumRange =
+      getNumRangeIds() - getIdKindOverlap(IdKind::Range, pos, pos + 1);
   unsigned newNumSymbols =
       getNumSymbolIds() - getIdKindOverlap(IdKind::Symbol, pos, pos + 1);
   unsigned newNumLocals =
       getNumLocalIds() - getIdKindOverlap(IdKind::Local, pos, pos + 1);
 
   /// Create the new system which has one identifier less.
-  IntegerPolyhedron newPoly(lbIndices.size() * ubIndices.size() +
-                                nbIndices.size(),
-                            getNumEqualities(), getNumCols() - 1, newNumDims,
-                            newNumSymbols, newNumLocals);
+  IntegerRelation newRel(lbIndices.size() * ubIndices.size() + nbIndices.size(),
+                         getNumEqualities(), getNumCols() - 1, newNumDomain,
+                         newNumRange, newNumSymbols, newNumLocals);
 
   // This will be used to check if the elimination was integer exact.
   unsigned lcmProducts = 1;
@@ -1645,7 +1665,7 @@
   for (auto ubPos : ubIndices) {
     for (auto lbPos : lbIndices) {
       SmallVector<int64_t, 4> ineq;
-      ineq.reserve(newPoly.getNumCols());
+      ineq.reserve(newRel.getNumCols());
       int64_t lbCoeff = atIneq(lbPos, pos);
       // Note that in the comments above, ubCoeff is the negation of the
       // coefficient in the canonical form as the view taken here is that of the
@@ -1667,8 +1687,8 @@
         ineq[ineq.size() - 1] += lbCoeff * ubCoeff - lbCoeff - ubCoeff + 1;
       }
       // TODO: we need to have a way to add inequalities in-place in
-      // IntegerPolyhedron instead of creating and copying over.
-      newPoly.addInequality(ineq);
+      // IntegerRelation instead of creating and copying over.
+      newRel.addInequality(ineq);
     }
   }
 
@@ -1686,30 +1706,30 @@
         continue;
       ineq.push_back(atIneq(nbPos, l));
     }
-    newPoly.addInequality(ineq);
+    newRel.addInequality(ineq);
   }
 
-  assert(newPoly.getNumConstraints() ==
+  assert(newRel.getNumConstraints() ==
          lbIndices.size() * ubIndices.size() + nbIndices.size());
 
   // Copy over the equalities.
   for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
     SmallVector<int64_t, 4> eq;
-    eq.reserve(newPoly.getNumCols());
+    eq.reserve(newRel.getNumCols());
     for (unsigned l = 0, e = getNumCols(); l < e; l++) {
       if (l == pos)
         continue;
       eq.push_back(atEq(r, l));
     }
-    newPoly.addEquality(eq);
+    newRel.addEquality(eq);
   }
 
   // GCD tightening and normalization allows detection of more trivially
   // redundant constraints.
-  newPoly.gcdTightenInequalities();
-  newPoly.normalizeConstraintsByGCD();
-  newPoly.removeTrivialRedundancy();
-  clearAndCopyFrom(newPoly);
+  newRel.gcdTightenInequalities();
+  newRel.normalizeConstraintsByGCD();
+  newRel.removeTrivialRedundancy();
+  clearAndCopyFrom(newRel);
   LLVM_DEBUG(llvm::dbgs() << "FM output:\n");
   LLVM_DEBUG(dump());
 }
@@ -1717,7 +1737,7 @@
 #undef DEBUG_TYPE
 #define DEBUG_TYPE "presburger"
 
-void IntegerPolyhedron::projectOut(unsigned pos, unsigned num) {
+void IntegerRelation::projectOut(unsigned pos, unsigned num) {
   if (num == 0)
     return;
 
@@ -1776,11 +1796,10 @@
 } // namespace
 
 // Returns constraints that are common to both A & B.
-static void getCommonConstraints(const IntegerPolyhedron &a,
-                                 const IntegerPolyhedron &b,
-                                 IntegerPolyhedron &c) {
-  c = IntegerPolyhedron(a.getNumDimIds(), a.getNumSymbolIds(),
-                        a.getNumLocalIds());
+static void getCommonConstraints(const IntegerRelation &a,
+                                 const IntegerRelation &b, IntegerRelation &c) {
+  c = IntegerRelation(a.getNumDomainIds(), a.getNumRangeIds(),
+                      a.getNumSymbolIds(), a.getNumLocalIds());
   // a naive O(n^2) check should be enough here given the input sizes.
   for (unsigned r = 0, e = a.getNumInequalities(); r < e; ++r) {
     for (unsigned s = 0, f = b.getNumInequalities(); s < f; ++s) {
@@ -1803,13 +1822,13 @@
 // Computes the bounding box with respect to 'other' by finding the min of the
 // lower bounds and the max of the upper bounds along each of the dimensions.
 LogicalResult
-IntegerPolyhedron::unionBoundingBox(const IntegerPolyhedron &otherCst) {
+IntegerRelation::unionBoundingBox(const IntegerRelation &otherCst) {
   assert(PresburgerLocalSpace::isEqual(otherCst) && "Spaces should match.");
   assert(getNumLocalIds() == 0 && "local ids not supported yet here");
 
   // Get the constraints common to both systems; these will be added as is to
   // the union.
-  IntegerPolyhedron commonCst;
+  IntegerRelation commonCst;
   getCommonConstraints(*this, otherCst, commonCst);
 
   std::vector<SmallVector<int64_t, 8>> boundingLbs;
@@ -1913,7 +1932,7 @@
   return success();
 }
 
-bool IntegerPolyhedron::isColZero(unsigned pos) const {
+bool IntegerRelation::isColZero(unsigned pos) const {
   unsigned rowPos;
   return !findConstraintWithNonZeroAt(pos, /*isEq=*/false, &rowPos) &&
          !findConstraintWithNonZeroAt(pos, /*isEq=*/true, &rowPos);
@@ -1921,8 +1940,8 @@
 
 /// Find positions of inequalities and equalities that do not have a coefficient
 /// for [pos, pos + num) identifiers.
-static void getIndependentConstraints(const IntegerPolyhedron &cst,
-                                      unsigned pos, unsigned num,
+static void getIndependentConstraints(const IntegerRelation &cst, unsigned pos,
+                                      unsigned num,
                                       SmallVectorImpl<unsigned> &nbIneqIndices,
                                       SmallVectorImpl<unsigned> &nbEqIndices) {
   assert(pos < cst.getNumIds() && "invalid start position");
@@ -1951,8 +1970,7 @@
   }
 }
 
-void IntegerPolyhedron::removeIndependentConstraints(unsigned pos,
-                                                     unsigned num) {
+void IntegerRelation::removeIndependentConstraints(unsigned pos, unsigned num) {
   assert(pos + num <= getNumIds() && "invalid range");
 
   // Remove constraints that are independent of these identifiers.
@@ -1968,13 +1986,12 @@
     removeEquality(nbIndex);
 }
 
-void IntegerPolyhedron::printSpace(raw_ostream &os) const {
-  os << "\nConstraints (" << getNumDimIds() << " dims, " << getNumSymbolIds()
-     << " symbols, " << getNumLocalIds() << " locals), (" << getNumConstraints()
-     << " constraints)\n";
+void IntegerRelation::printSpace(raw_ostream &os) const {
+  PresburgerLocalSpace::print(os);
+  os << getNumConstraints() << " constraints\n";
 }
 
-void IntegerPolyhedron::print(raw_ostream &os) const {
+void IntegerRelation::print(raw_ostream &os) const {
   assert(hasConsistentState());
   printSpace(os);
   for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
@@ -1992,4 +2009,4 @@
   os << '\n';
 }
 
-void IntegerPolyhedron::dump() const { print(llvm::errs()); }
+void IntegerRelation::dump() const { print(llvm::errs()); }
diff --git a/mlir/lib/Analysis/Presburger/LinearTransform.cpp b/mlir/lib/Analysis/Presburger/LinearTransform.cpp
--- a/mlir/lib/Analysis/Presburger/LinearTransform.cpp
+++ b/mlir/lib/Analysis/Presburger/LinearTransform.cpp
@@ -7,7 +7,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Analysis/Presburger/LinearTransform.h"
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 
 using namespace mlir;
 using namespace presburger;
@@ -112,12 +112,11 @@
   return {echelonCol, LinearTransform(std::move(resultMatrix))};
 }
 
-IntegerPolyhedron
-LinearTransform::applyTo(const IntegerPolyhedron &poly) const {
-  IntegerPolyhedron result(poly.getNumIds());
+IntegerRelation LinearTransform::applyTo(const IntegerRelation &rel) const {
+  IntegerRelation result(rel.getNumIds());
 
-  for (unsigned i = 0, e = poly.getNumEqualities(); i < e; ++i) {
-    ArrayRef<int64_t> eq = poly.getEquality(i);
+  for (unsigned i = 0, e = rel.getNumEqualities(); i < e; ++i) {
+    ArrayRef<int64_t> eq = rel.getEquality(i);
 
     int64_t c = eq.back();
 
@@ -126,8 +125,8 @@
     result.addEquality(newEq);
   }
 
-  for (unsigned i = 0, e = poly.getNumInequalities(); i < e; ++i) {
-    ArrayRef<int64_t> ineq = poly.getInequality(i);
+  for (unsigned i = 0, e = rel.getNumInequalities(); i < e; ++i) {
+    ArrayRef<int64_t> ineq = rel.getInequality(i);
 
     int64_t c = ineq.back();
 
diff --git a/mlir/lib/Analysis/Presburger/PresburgerSet.cpp b/mlir/lib/Analysis/Presburger/PresburgerSet.cpp
--- a/mlir/lib/Analysis/Presburger/PresburgerSet.cpp
+++ b/mlir/lib/Analysis/Presburger/PresburgerSet.cpp
@@ -221,7 +221,7 @@
   simplex.appendVariable(numLocalsAdded);
 
   unsigned snapshotBeforeIntersect = simplex.getSnapshot();
-  simplex.intersectIntegerPolyhedron(sI);
+  simplex.intersectIntegerRelation(sI);
 
   if (simplex.isEmpty()) {
     // b ^ s_i is empty, so b \ s_i = b. We move directly to i + 1.
diff --git a/mlir/lib/Analysis/Presburger/PresburgerSpace.cpp b/mlir/lib/Analysis/Presburger/PresburgerSpace.cpp
--- a/mlir/lib/Analysis/Presburger/PresburgerSpace.cpp
+++ b/mlir/lib/Analysis/Presburger/PresburgerSpace.cpp
@@ -38,10 +38,8 @@
 }
 
 unsigned PresburgerSpace::getNumIdKind(IdKind kind) const {
-  if (kind == IdKind::Domain) {
-    assert(spaceKind == Relation && "IdKind::Domain is not supported in Set.");
+  if (kind == IdKind::Domain)
     return getNumDomainIds();
-  }
   if (kind == IdKind::Range)
     return getNumRangeIds();
   if (kind == IdKind::Symbol)
@@ -52,10 +50,8 @@
 }
 
 unsigned PresburgerSpace::getIdKindOffset(IdKind kind) const {
-  if (kind == IdKind::Domain) {
-    assert(spaceKind == Relation && "IdKind::Domain is not supported in Set.");
+  if (kind == IdKind::Domain)
     return 0;
-  }
   if (kind == IdKind::Range)
     return getNumDomainIds();
   if (kind == IdKind::Symbol)
diff --git a/mlir/lib/Analysis/Presburger/Simplex.cpp b/mlir/lib/Analysis/Presburger/Simplex.cpp
--- a/mlir/lib/Analysis/Presburger/Simplex.cpp
+++ b/mlir/lib/Analysis/Presburger/Simplex.cpp
@@ -833,14 +833,14 @@
   undoLog.insert(undoLog.end(), count, UndoLogEntry::RemoveLastVariable);
 }
 
-/// Add all the constraints from the given IntegerPolyhedron.
-void SimplexBase::intersectIntegerPolyhedron(const IntegerPolyhedron &poly) {
-  assert(poly.getNumIds() == getNumVariables() &&
-         "IntegerPolyhedron must have same dimensionality as simplex");
-  for (unsigned i = 0, e = poly.getNumInequalities(); i < e; ++i)
-    addInequality(poly.getInequality(i));
-  for (unsigned i = 0, e = poly.getNumEqualities(); i < e; ++i)
-    addEquality(poly.getEquality(i));
+/// Add all the constraints from the given IntegerRelation.
+void SimplexBase::intersectIntegerRelation(const IntegerRelation &rel) {
+  assert(rel.getNumIds() == getNumVariables() &&
+         "IntegerRelation must have same dimensionality as simplex");
+  for (unsigned i = 0, e = rel.getNumInequalities(); i < e; ++i)
+    addInequality(rel.getInequality(i));
+  for (unsigned i = 0, e = rel.getNumEqualities(); i < e; ++i)
+    addEquality(rel.getEquality(i));
 }
 
 MaybeOptimum<Fraction> Simplex::computeRowOptimum(Direction direction,
@@ -1655,16 +1655,16 @@
 
 void SimplexBase::dump() const { print(llvm::errs()); }
 
-bool Simplex::isRationalSubsetOf(const IntegerPolyhedron &poly) {
+bool Simplex::isRationalSubsetOf(const IntegerRelation &rel) {
   if (isEmpty())
     return true;
 
-  for (unsigned i = 0, e = poly.getNumInequalities(); i < e; ++i)
-    if (findIneqType(poly.getInequality(i)) != IneqType::Redundant)
+  for (unsigned i = 0, e = rel.getNumInequalities(); i < e; ++i)
+    if (findIneqType(rel.getInequality(i)) != IneqType::Redundant)
       return false;
 
-  for (unsigned i = 0, e = poly.getNumEqualities(); i < e; ++i)
-    if (!isRedundantEquality(poly.getEquality(i)))
+  for (unsigned i = 0, e = rel.getNumEqualities(); i < e; ++i)
+    if (!isRedundantEquality(rel.getEquality(i)))
       return false;
 
   return true;
diff --git a/mlir/lib/Analysis/Presburger/Utils.cpp b/mlir/lib/Analysis/Presburger/Utils.cpp
--- a/mlir/lib/Analysis/Presburger/Utils.cpp
+++ b/mlir/lib/Analysis/Presburger/Utils.cpp
@@ -11,7 +11,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Analysis/Presburger/Utils.h"
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Support/LogicalResult.h"
 #include "mlir/Support/MathExtras.h"
 
@@ -87,7 +87,7 @@
 /// If successful, `expr` is set to dividend of the division and `divisor` is
 /// set to the denominator of the division. The final division expression is
 /// normalized by GCD.
-static LogicalResult getDivRepr(const IntegerPolyhedron &cst, unsigned pos,
+static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
                                 unsigned ubIneq, unsigned lbIneq,
                                 SmallVector<int64_t, 8> &expr,
                                 unsigned &divisor) {
@@ -151,7 +151,7 @@
 /// If successful, `expr` is set to dividend of the division and `divisor` is
 /// set to the denominator of the division. The final division expression is
 /// normalized by GCD.
-static LogicalResult getDivRepr(const IntegerPolyhedron &cst, unsigned pos,
+static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
                                 unsigned eqInd, SmallVector<int64_t, 8> &expr,
                                 unsigned &divisor) {
 
@@ -182,7 +182,7 @@
 
 // Returns `false` if the constraints depends on a variable for which an
 // explicit representation has not been found yet, otherwise returns `true`.
-static bool checkExplicitRepresentation(const IntegerPolyhedron &cst,
+static bool checkExplicitRepresentation(const IntegerRelation &cst,
                                         ArrayRef<bool> foundRepr,
                                         ArrayRef<int64_t> dividend,
                                         unsigned pos) {
@@ -214,7 +214,7 @@
 /// If the representation could not be computed, the kind attribute in
 /// `MaybeLocalRepr` is set to None.
 MaybeLocalRepr presburger::computeSingleVarRepr(
-    const IntegerPolyhedron &cst, ArrayRef<bool> foundRepr, unsigned pos,
+    const IntegerRelation &cst, ArrayRef<bool> foundRepr, unsigned pos,
     SmallVector<int64_t, 8> &dividend, unsigned &divisor) {
   assert(pos < cst.getNumIds() && "invalid position");
   assert(foundRepr.size() == cst.getNumIds() &&
diff --git a/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp b/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp
--- a/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp
+++ b/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp
@@ -1365,7 +1365,7 @@
   os << " const)\n";
 }
 
-void FlatAffineConstraints::clearAndCopyFrom(const IntegerPolyhedron &other) {
+void FlatAffineConstraints::clearAndCopyFrom(const IntegerRelation &other) {
   if (auto *otherValueSet = dyn_cast<const FlatAffineValueConstraints>(&other))
     assert(!otherValueSet->hasValues() &&
            "cannot copy associated Values into FlatAffineConstraints");
@@ -1375,11 +1375,11 @@
   if (auto *otherValueSet = dyn_cast<const FlatAffineConstraints>(&other))
     *this = *otherValueSet;
   else
-    *static_cast<IntegerPolyhedron *>(this) = other;
+    *static_cast<IntegerRelation *>(this) = other;
 }
 
 void FlatAffineValueConstraints::clearAndCopyFrom(
-    const IntegerPolyhedron &other) {
+    const IntegerRelation &other) {
 
   if (auto *otherValueSet =
           dyn_cast<const FlatAffineValueConstraints>(&other)) {
@@ -1390,7 +1390,7 @@
   if (auto *otherValueSet = dyn_cast<const FlatAffineValueConstraints>(&other))
     *static_cast<FlatAffineConstraints *>(this) = *otherValueSet;
   else
-    *static_cast<IntegerPolyhedron *>(this) = other;
+    *static_cast<IntegerRelation *>(this) = other;
 
   values.clear();
   values.resize(getNumIds(), None);
diff --git a/mlir/unittests/Analysis/Presburger/IntegerPolyhedronTest.cpp b/mlir/unittests/Analysis/Presburger/IntegerPolyhedronTest.cpp
--- a/mlir/unittests/Analysis/Presburger/IntegerPolyhedronTest.cpp
+++ b/mlir/unittests/Analysis/Presburger/IntegerPolyhedronTest.cpp
@@ -6,8 +6,8 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
 #include "./Utils.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Analysis/Presburger/Simplex.h"
 #include "mlir/IR/MLIRContext.h"
 
diff --git a/mlir/unittests/Analysis/Presburger/Utils.h b/mlir/unittests/Analysis/Presburger/Utils.h
--- a/mlir/unittests/Analysis/Presburger/Utils.h
+++ b/mlir/unittests/Analysis/Presburger/Utils.h
@@ -14,7 +14,7 @@
 #define MLIR_UNITTESTS_ANALYSIS_PRESBURGER_UTILS_H
 
 #include "../../Dialect/Affine/Analysis/AffineStructuresParser.h"
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Analysis/Presburger/PresburgerSet.h"
 #include "mlir/IR/MLIRContext.h"