[MLIR][Presburger] Move functionality from IntegerPolyhedron to IntegerRelation

[Groverkss]

Summary

This patch moves all functionality from IntegerPolyhedron to IntegerRelation.
IntegerPolyhedron is now implemented as a relation with no domain. All existing
functionality is extended to work on relations.

This patch does not affect external users like FlatAffineConstraints as they
can still continue to use IntegerPolyhedron abstraction.

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

[arjunp]

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

9–11

Maybe add 1-2 lines to explain what that is.

186–197

Note that domain is minimized, then range.

410

write that it constructs with zero range and with SpaceKind = Set

529

533

what does "between dimensions" mean?

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

64–65

poly -> rel?

mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h

182

We don't support IntegerRelation here right? This should stay as IntegerPolyhedron?

487

Again, do we support IntegerRelation here?

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

56

getNumDimIds() should not be supported on relation spaces, should assert spaceKind == Set in that I feel, and provide a getNumDomainAndRangeIds()

60

ret and rel are a little too similar. Maybe call the return value result

68

also below.

[Groverkss]

• Address Arjun's comments

mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h

182

This is a virtual function used internally in IntegerRelation. So, it is required to be IntegerRelation.

487

Same reasoning as above.

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

56

I prefer getNumDimIds() over this since domain and range identifiers are both dimension identifiers.

[arjunp]

LGTM, please fix minor comments below.

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

9–11

A relation

11

variables

534

Kinds of ids

[arjunp]

Oops, selected the wrong action.

[Groverkss]

• Address Arjun's comments
• Address Arjun's comments

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

-//===- 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.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// 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.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_ANALYSIS_PRESBURGER_INTEGERPOLYHEDRON_H
 #define MLIR_ANALYSIS_PRESBURGER_INTEGERPOLYHEDRON_H
 
 #include "mlir/Analysis/Presburger/Fraction.h"
 #include "mlir/Analysis/Presburger/Matrix.h"

 /// These can be thought of as points in the polyhedron:
 ///         (x, y) : (1 <= x <= 7, x = 2y)
 /// This relation contains the pairs (2, 1), (4, 2), and (6, 3).
 ///
 /// Since IntegerRelation makes a distinction between dimensions, IdKind::Range
 /// 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,
                   unsigned numReservedEqualities, unsigned numReservedCols,
                   unsigned numDomain, unsigned numRange, unsigned numSymbols,
                   unsigned numLocals)
       : PresburgerLocalSpace(numDomain, numRange, numSymbols, numLocals),
         equalities(0, getNumIds() + 1, numReservedEqualities, numReservedCols),
         inequalities(0, getNumIds() + 1, numReservedInequalities,
                      numReservedCols) {
     assert(numReservedCols >= getNumIds() + 1);
   }
 
   /// Constructs a relation with the specified number of dimensions and symbols.
   IntegerRelation(unsigned numDomain = 0, unsigned numRange = 0,
                   unsigned numSymbols = 0, unsigned numLocals = 0)
       : IntegerRelation(/*numReservedInequalities=*/0,
                         /*numReservedEqualities=*/0,
                         /*numReservedCols=*/numDomain + numRange + numSymbols +
                             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,
+    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); }
   inline int64_t &atEq(unsigned i, unsigned j) { return equalities(i, j); }
 
   /// Returns the value at the specified inequality row and column.
   inline int64_t atIneq(unsigned i, unsigned j) const {
     return inequalities(i, j);
public:
 
   void removeEquality(unsigned pos);
   void removeInequality(unsigned pos);
 
   /// Remove the (in)equalities at positions [start, end).
   void removeEqualityRange(unsigned start, unsigned end);
   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.
   virtual void swapId(unsigned posA, unsigned posB);
 
   /// Removes all equalities and inequalities.
   void clearConstraints();
 
   /// Sets the `values.size()` identifiers starting at `po`s to the specified
   /// 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
   /// independent of identifiers in position range [`offset`, `offset` + `num`).
   void
   getLowerAndUpperBoundIndices(unsigned pos,
                                SmallVectorImpl<unsigned> *lbIndices,
                                SmallVectorImpl<unsigned> *ubIndices,
public:
   /// branch and bound algorithm with generalized basis reduction, with some
   /// additional processing using Simplex for unbounded sets.
   ///
   /// Returns an integer sample point if one exists, or an empty Optional
   /// otherwise.
   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;
 
   /// Find equality and pairs of inequality contraints identified by their
   /// position indices, using which an explicit representation for each local
   /// variable can be computed. The indices of the constraints are stored in
   /// `MaybeLocalRepr` struct. If no such pair can be found, the kind attribute
   /// in `MaybeLocalRepr` is set to None.
public:
   ///    other  = {16 <= d0 <= 192},
   ///    output = {0 <= d0 <= 192}
   /// 2) this   = {s0 + 5 <= d0 <= s0 + 20},
   ///    other  = {s0 + 1 <= d0 <= s0 + 9},
   ///    output = {s0 + 1 <= d0 <= s0 + 20}
   /// 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
   /// than or equal to 'exclusive upper bound' - 'lower bound' of the
   /// identifier. This constant bound is guaranteed to be non-negative. Returns
   /// None if it's not a constant. This method employs trivial (low complexity /
   /// cost) checks and detection. Symbolic identifiers are treated specially,
   /// i.e., it looks for constant differences between affine expressions
public:
   /// lie in `this` and `other`. The ordering of the local ids in the
   /// sets may also be changed. After merging, if the `i^th` local variable in
   /// one set has a known division representation, then the `i^th` local
   /// variable in the other set either has the same division representation or
   /// no known division representation.
   ///
   /// 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;
   /// false otherwise.
   bool hasInvalidConstraint() const;
 
   /// Returns the constant lower bound bound if isLower is true, and the upper
   /// bound if isLower is false.
protected:
   bool isColZero(unsigned pos) const;
 
   /// Returns false if the fields corresponding to various identifier counts, or
   /// equality/inequality buffer sizes aren't consistent; true otherwise. This
   /// is meant to be used within an assert internally.
   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
   /// remaining valid data into place, updates member variables, and resizes
   /// arrays as needed.
   void removeIdRange(unsigned idStart, unsigned idLimit) override;
 
   /// 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
   // through a div or mod, an extra pair of bounds gets added. As a limit, we
   // 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
 } // namespace mlir
 
 #endif // MLIR_ANALYSIS_PRESBURGER_INTEGERPOLYHEDRON_H

mlir/include/mlir/Analysis/Presburger/LinearTransform.h

 //===- LinearTransform.h - MLIR LinearTransform 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
 //
 //===----------------------------------------------------------------------===//
 //
-// 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"
 
 namespace mlir {
 namespace presburger {
 
 class LinearTransform {
 public:
   explicit LinearTransform(Matrix &&oMatrix);
   explicit LinearTransform(const Matrix &oMatrix);
 
   // Returns a linear transform T such that MT is M in column echelon form.
   // Also returns the number of non-zero columns in MT.
   //
   // Specifically, T is such that in every column the first non-zero row is
   // strictly below that of the previous column, and all columns which have only
   // zeros are at the end.
   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.
   SmallVector<int64_t, 8> preMultiplyWithRow(ArrayRef<int64_t> rowVec) const {
     return matrix.preMultiplyWithRow(rowVec);
   }
 
   // The given vector is interpreted as a column vector v. Pre-multiply v with

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

 // the value of the function is a tuple of integers, with each value in the
 // 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/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Analysis/Presburger/PresburgerSet.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
public:
 
   MultiAffineFunction(const IntegerPolyhedron &domain, const Matrix &output)
       : IntegerPolyhedron(domain), output(output) {}
   MultiAffineFunction(const Matrix &output, unsigned numDims,
                       unsigned numSymbols = 0, unsigned numLocals = 0)
       : IntegerPolyhedron(numDims, numSymbols, numLocals), output(output) {}
 
   ~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(); }
   unsigned getNumOutputs() const { return output.getNumRows(); }
   bool isConsistent() const {
     return output.getNumColumns() == getNumIds() + 1;
   }
   const IntegerPolyhedron &getDomain() const { return *this; }

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

 //===- Set.h - MLIR PresburgerSet Class -------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // A class to represent unions of IntegerPolyhedrons.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H
 #define MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H
 
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 
 namespace mlir {
 namespace presburger {
 
 /// This class can represent a union of IntegerPolyhedrons, with support for
 /// union, intersection, subtraction and complement operations, as well as
 /// sampling.
 ///

mlir/include/mlir/Analysis/Presburger/Simplex.h

 //===- Simplex.h - MLIR Simplex 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
 //
 //===----------------------------------------------------------------------===//
 //
-// 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.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_ANALYSIS_PRESBURGER_SIMPLEX_H
 #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"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/StringSaver.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace mlir {
 namespace presburger {
 
 class GBRSimplex;
 
 /// The Simplex class implements a version of the Simplex and Generalized Basis
 /// Reduction algorithms, which can perform analysis of integer sets with affine
 /// inequalities and equalities. A Simplex can be constructed
 /// by specifying the dimensionality of the set. It supports adding affine
 /// inequalities and equalities, and can perform emptiness checks, i.e., it can
 /// find a solution to the set of constraints if one exists, or say that the
 /// set is empty if no solution exists. Furthermore, it can find a subset of
 /// 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
 /// functionality for obtaining an integer sample, are based on the paper
 /// "Simplify: A Theorem Prover for Program Checking"
 /// by D. Detlefs, G. Nelson, J. B. Saxe.
 ///
 /// We define variables, constraints, and unknowns. Consider the example of a
public:
 
   /// Get a snapshot of the current state including the basis. When rolling
   /// back, the exact basis will be restored.
   unsigned getSnapshotBasis();
 
   /// 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;
   void dump() const;
 
 protected:
   enum class Orientation { Row, Column };
 

 /// since they are the first non-zero element in each of these columns, so if
 /// (A_k)*y is not zero then we have that A*y is lexicopositive and if not we
 /// ignore more columns; eventually if all these dot products become zero then
 /// A*y is zero and we are done.
 class LexSimplex : public SimplexBase {
 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;
 
   /// Add an inequality to the tableau. If coeffs is c_0, c_1, ... c_n, where n
   /// is the current number of variables, then the corresponding inequality is
   /// c_n + c_0*x_0 + c_1*x_1 + ... + c_{n-1}*x_{n-1} >= 0.
   ///
   /// This just adds the inequality to the tableau and does not try to create a

 /// Finding an integer sample is done with the Generalized Basis Reduction
 /// algorithm. See the documentation for findIntegerSample and reduceBasis.
 class Simplex : public SimplexBase {
 public:
   enum class Direction { Up, Down };
 
   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;
 
   /// Add an inequality to the tableau. If coeffs is c_0, c_1, ... c_n, where n
   /// is the current number of variables, then the corresponding inequality is
   /// c_n + c_0*x_0 + c_1*x_1 + ... + c_{n-1}*x_{n-1} >= 0.
   ///
   /// This also tries to restore the tableau configuration to a consistent
public:
   IneqType findIneqType(ArrayRef<int64_t> coeffs);
 
   /// Check if the specified inequality already holds in the polytope.
   bool isRedundantInequality(ArrayRef<int64_t> coeffs);
 
   /// 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.
   Optional<SmallVector<int64_t, 8>> getSamplePointIfIntegral() const;
 
   /// Returns the current sample point, which may contain non-integer (rational)
   /// coordinates. Returns an empty optional when the tableau is empty.
   Optional<SmallVector<Fraction, 8>> getRationalSample() const;

mlir/include/mlir/Analysis/Presburger/Utils.h

 #define MLIR_ANALYSIS_PRESBURGER_UTILS_H
 
 #include "mlir/Support/LLVM.h"
 #include "llvm/ADT/STLExtras.h"
 
 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
 /// be Empty. If the optimum is unbounded, the kind is Unbounded, and if the
 /// optimum is bounded, the kind will be Bounded and `optimum` holds the optimal
 /// value.
 enum class OptimumKind { Empty, Unbounded, Bounded };
 template <typename T>

 /// function of other identifiers (where the divisor is a positive constant).
 /// `foundRepr` contains a boolean for each identifier indicating if the
 /// explicit representation for that identifier has already been computed.
 /// Returns the `MaybeLocalRepr` struct which contains the indices of the
 /// constraints that can be expressed as a floordiv of an affine function. If
 /// 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);
 
 /// Given dividends of divisions `divs` and denominators `denoms`, detects and
 /// removes duplicate divisions. `localOffset` is the offset in dividend of a
 /// division from where local identifiers start.
 ///
 /// On every possible duplicate division found, `merge(i, j)`, where `i`, `j`
 /// are current index of the duplicate divisions, is called and division at
 /// index `j` is merged into division at index `i`. If `merge(i, j)` returns
 /// `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,
     llvm::function_ref<bool(unsigned i, unsigned j)> merge);
 
 } // namespace presburger
 } // namespace mlir
 
 #endif // MLIR_ANALYSIS_PRESBURGER_UTILS_H

mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h

 //===- AffineStructures.h - MLIR Affine Structures 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Structures for affine/polyhedral analysis of ML functions.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "mlir/Support/LogicalResult.h"
 
 namespace mlir {
 
 class AffineCondition;
public:
 
   FlatAffineConstraints(const MutableAffineMap &map);
 
   ~FlatAffineConstraints() override = default;
 
   /// 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;
   }
 
   /// Clears any existing data and reserves memory for the specified
   /// constraints.
   virtual void reset(unsigned numReservedInequalities,
                      unsigned numReservedEqualities, unsigned numReservedCols,
                      unsigned numDims, unsigned numSymbols,
public:
 
   /// Composes an affine map whose dimensions and symbols match one to one with
   /// the dimensions and symbols of this FlatAffineConstraints. The results of
   /// the map `other` are added as the leading dimensions of this constraint
   /// system. Returns failure if `other` is a semi-affine map.
   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
   /// [symStartPos, getNumDimAndSymbolIds) as symbols, and `pos` lies in
   /// [0, num). The multi-dimensional maps in the returned pair represent the
   /// max and min of potentially multiple affine expressions. The upper bound is
   /// exclusive. `localExprs` holds pre-computed AffineExpr's for all local
   /// identifiers in the system.
public:
   //
   // All dimensions as set as DimId.
   static FlatAffineValueConstraints
   getHyperrectangular(ValueRange ivs, ValueRange lbs, ValueRange ubs);
 
   /// 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;
   }
 
   /// Clears any existing data and reserves memory for the specified
   /// constraints.
   void reset(unsigned numReservedInequalities, unsigned numReservedEqualities,
              unsigned numReservedCols, unsigned numDims, unsigned numSymbols,
              unsigned numLocals = 0) override;
void mergeAndAlignIdsWithOther(unsigned offset,
                                  FlatAffineValueConstraints *other);
 
   /// Returns true if this constraint system and `other` are in the same
   /// space, i.e., if they are associated with the same set of identifiers,
   /// appearing in the same order. Returns false otherwise.
   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.
   inline Value getValue(unsigned pos) const {
     assert(hasValue(pos) && "identifier's Value not set");
     return values[pos].getValue();
   }
 

mlir/lib/Analysis/Presburger/CMakeLists.txt

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

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

-//===- 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.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// 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"
 #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"
 
 using namespace mlir;
 using namespace presburger;
 
 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() +
                            other.getNumInequalities());
   equalities.reserveRows(equalities.getNumRows() + other.getNumEqualities());
 
   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));
   }
 }
 
-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 IntegerPolyhedron::isSubsetOf(const IntegerPolyhedron &other) const {
-  return PresburgerSet(*this).isSubsetOf(PresburgerSet(other));
+bool IntegerRelation::isEqual(const IntegerRelation &other) const {
+  assert(PresburgerLocalSpace::isEqual(other) && "Spaces must be equal.");
+  return PresburgerSet(createSetFromRelation(*this))
+      .isEqual(PresburgerSet(createSetFromRelation(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();
 
   if (!maybeLexMin.isBounded())
     return maybeLexMin;
 
   // The Simplex returns the lexmin over all the variables including locals. But
   // locals are not actually part of the space and should not be returned in the
   // result. Since the locals are placed last in the list of identifiers, they
   // will be minimized last in the lexmin. So simply truncating out the locals
   // from the end of the answer gives the desired lexmin over the dimensions.
   assert(maybeLexMin->size() == getNumIds() &&
          "Incorrect number of vars in lexMin!");
   maybeLexMin->resize(getNumDimAndSymbolIds());
   return maybeLexMin;
 }
 
 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();
 
   if (!maybeLexMin.isBounded())
     return maybeLexMin.getKind();
 
   // The Simplex returns the lexmin over all the variables including locals. But
   // locals are not actually part of the space and should not be returned in the
   // result. Since the locals are placed last in the list of identifiers, they
   // will be minimized last in the lexmin. So simply truncating out the locals
   // from the end of the answer gives the desired lexmin over the dimensions.
   assert(maybeLexMin->size() == getNumIds() &&
          "Incorrect number of vars in lexMin!");
   maybeLexMin->resize(getNumDimAndSymbolIds());
   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);
   inequalities.insertColumns(insertPos, num);
   equalities.insertColumns(insertPos, num);
   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,
   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);
 
   // Remove eliminated identifiers from the constraints..
   equalities.removeColumns(idStart, idLimit - idStart);
   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");
 
   if (posA == posB)
     return;
 
   inequalities.swapColumns(posA, posB);
   equalities.swapColumns(posA, posB);
 }
 
-void IntegerPolyhedron::clearConstraints() {
+void IntegerRelation::clearConstraints() {
   equalities.resizeVertically(0);
   inequalities.resizeVertically(0);
 }
 
 /// 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 {
   assert(pos < getNumIds() && "invalid position");
   assert(offset + num < getNumCols() && "invalid range");
 
   // Checks for a constraint that has a non-zero coeff for the identifiers in
   // the position range [offset, offset + num) while ignoring `pos`.
for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
     if (atEq(r, pos) == 0)
       continue;
     if (containsConstraintDependentOnRange(r, /*isEq=*/true))
       continue;
     eqIndices->push_back(r);
   }
 }
 
-bool IntegerPolyhedron::hasConsistentState() const {
+bool IntegerRelation::hasConsistentState() const {
   if (!inequalities.hasConsistentState())
     return false;
   if (!equalities.hasConsistentState())
     return false;
   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() &&
          "invalid position or too many values");
   // Setting x_j = p in sum_i a_i x_i + c is equivalent to adding p*a_j to the
   // constant term and removing the id x_j. We do this for all the ids
   // pos, pos + 1, ... pos + values.size() - 1.
   unsigned constantColPos = getNumCols() - 1;
   for (unsigned i = 0, numVals = values.size(); i < numVals; ++i)
     inequalities.addToColumn(i + pos, constantColPos, values[i]);
   for (unsigned i = 0, numVals = values.size(); i < numVals; ++i)
     equalities.addToColumn(i + pos, constantColPos, values[i]);
   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,
   assert(colIdx < getNumCols() && "position out of bounds");
   auto at = [&](unsigned rowIdx) -> int64_t {
     return isEq ? atEq(rowIdx, colIdx) : atIneq(rowIdx, colIdx);
   };
   unsigned e = isEq ? getNumEqualities() : getNumInequalities();
   for (*rowIdx = 0; *rowIdx < e; ++(*rowIdx)) {
     if (at(*rowIdx) != 0) {
       return true;
     }
   }
   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();
     unsigned numRows = isEq ? getNumEqualities() : getNumInequalities();
     for (unsigned i = 0, e = numRows; i < e; ++i) {
       unsigned j;
       for (j = 0; j < numCols - 1; ++j) {
         int64_t v = isEq ? atEq(i, j) : atIneq(i, j);
bool IntegerRelation::hasInvalidConstraint() const {
   if (check(/*isEq=*/true))
     return true;
   return check(/*isEq=*/false);
 }
 
 /// 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) {
   // Skip if equality 'rowIdx' if same as 'pivotRow'.
   if (isEq && rowIdx == pivotRow)
     return;
   auto at = [&](unsigned i, unsigned j) -> int64_t {
     return isEq ? constraints->atEq(i, j) : constraints->atIneq(i, j);
static void eliminateFromConstraint(IntegerRelation *constraints,
   }
 }
 
 /// Returns the position of the identifier that has the minimum <number of lower
 /// bounds> times <number of upper bounds> from the specified range of
 /// 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) {
     unsigned numLb = 0;
     unsigned numUb = 0;
     for (unsigned r = 0, e = cst.getNumInequalities(); r < e; r++) {
       if (cst.atIneq(r, pos) > 0) {
         ++numLb;
static unsigned getBestIdToEliminate(const IntegerRelation &cst, unsigned start,
   }
   return minLoc;
 }
 
 // Checks for emptiness of the set by eliminating identifiers successively and
 // 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();
   if (tmpCst.isEmptyByGCDTest() || tmpCst.hasInvalidConstraint())
     return true;
 
   // Eliminate as many identifiers as possible using Gaussian elimination.
   unsigned currentPos = 0;
bool IntegerRelation::isEmpty() const {
 
   // Eliminate the remaining using FM.
   for (unsigned i = 0, e = tmpCst.getNumIds(); i < e; i++) {
     tmpCst.fourierMotzkinEliminate(
         getBestIdToEliminate(tmpCst, 0, tmpCst.getNumIds()));
     // 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");
       return false;
     }
 
     // FM wouldn't have modified the equalities in any way. So no need to again
     // run GCD test. Check for trivial invalid constraints.

 // The equality constraint:
 //
 //  c_1*x_1 + c_2*x_2 + ... + c_n*x_n = c_0
 //
 // has an integer solution iff:
 //
 //  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) {
     uint64_t gcd = std::abs(atEq(i, 0));
     for (unsigned j = 1; j < numCols - 1; ++j) {
       gcd = llvm::GreatestCommonDivisor64(gcd, std::abs(atEq(i, j)));
     }
     int64_t v = std::abs(atEq(i, numCols - 1));
     if (gcd > 0 && (v % gcd != 0)) {
       return true;
     }
   }
   return false;
 }
 
 // Returns a matrix where each row is a vector along which the polytope is
 // bounded. The span of the returned vectors is guaranteed to contain all
 // such vectors. The returned vectors are NOT guaranteed to be linearly
 // independent. This function should not be called on empty sets.
 //
 // 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
   // equalities, are present.
   Simplex simplex(*this);
 
   assert(!simplex.isEmpty() && "It is not meaningful to ask whether a "
                                "direction is bounded in an empty set.");
for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
     for (unsigned col = 0; col < dirsNumCols; ++col)
       dirs(row, col) = atEq(i, col);
     ++row;
   }
 
   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();
 }
 
 /// Let this set be S. If S is bounded then we directly call into the GBR
 /// sampling algorithm. Otherwise, there are some unbounded directions, i.e.,
 /// vectors v such that S extends to infinity along v or -v. In this case we
 /// use an algorithm described in the integer set library (isl) manual and used
 /// by the isl_set_sample function in that library. The algorithm is:

 /// outside the prefix are unbounded in S*T (step 1). Substituting values for
 /// the bounded dimensions cannot make these dimensions bounded, and these are
 /// the only remaining dimensions in C, so C is unbounded along every vector (in
 /// the positive or negative direction, or both). C is hence a full-dimensional
 /// cone and therefore always contains an integer point.
 ///
 /// 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 {};
 
   Simplex simplex(*this);
   if (simplex.isEmpty())
     return {};
 
Optional<SmallVector<int64_t, 8>> IntegerRelation::findIntegerSample() const {
   // In column echelon form, each row of m occupies only the first rank(m)
   // columns and has zeros on the other columns. The transform T that brings S
   // to column echelon form is unimodular as well, so this is a suitable
   // transform to use in step 1 of the algorithm.
   std::pair<unsigned, LinearTransform> result =
       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);
   boundedSet.removeIdRange(numBoundedDims, boundedSet.getNumIds());
 
   // 3) Try to obtain a sample from the bounded set.
   Optional<SmallVector<int64_t, 8>> boundedSample =
       Simplex(boundedSet).findIntegerSample();
   if (!boundedSample)
     return {};
   assert(boundedSet.containsPoint(*boundedSample) &&
          "Simplex returned an invalid sample!");
 
   // 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.
   //
   // We shrink the cone such that for any rational point in the shrunken cone,
   // rounding up each of the point's coordinates produces a point that still
   // lies in the original cone.
   //
   // Rounding up a point x adds a number e_i in [0, 1) to each coordinate x_i.
static int64_t valueAt(ArrayRef<int64_t> expr, ArrayRef<int64_t> point) {
   for (unsigned i = 0; i < point.size(); ++i)
     value += expr[i] * point[i];
   return value;
 }
 
 /// 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;
   }
   for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
     if (valueAt(getInequality(i), point) < 0)
       return false;
   }
   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 {
 
   repr.resize(getNumLocalIds());
   dividends.resize(getNumLocalIds());
   denominators.resize(getNumLocalIds());
 

 /// Tightens inequalities given that we are dealing with integer spaces. This is
 /// analogous to the GCD test but applied to inequalities. The constant term can
 /// be reduced to the preceding multiple of the GCD of the coefficients, i.e.,
 ///  64*i - 100 >= 0  =>  64*i - 128 >= 0 (since 'i' is an integer). This is a
 /// fast method - linear in the number of coefficients.
 // 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.
     uint64_t gcd = inequalities.normalizeRow(i, getNumCols() - 1);
     if (gcd > 1)
       atIneq(i, numCols - 1) = mlir::floorDiv(atIneq(i, numCols - 1), gcd);
   }
 }
 
 // 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,
   // Return if identifier positions to eliminate are out of range.
   assert(posLimit <= getNumIds());
   assert(hasConsistentState());
 
   if (posStart >= posLimit)
     return 0;
 
   gcdTightenInequalities();
unsigned IntegerRelation::gaussianEliminateIds(unsigned posStart,
   posLimit = pivotCol;
   // Remove eliminated columns from all constraints.
   removeIdRange(posStart, posLimit);
   return posLimit - posStart;
 }
 
 // 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);
     tmpCst.atIneq(r, tmpCst.getNumCols() - 1)--;
     if (tmpCst.isEmpty()) {
       redun[r] = true;
       // Zero fill the redundant inequality.
       inequalities.fillRow(r, /*value=*/0);
for (unsigned r = 0, e = getNumInequalities(); r < e; ++r) {
     if (!redun[r])
       inequalities.copyRow(r, pos++);
   }
   inequalities.resizeVertically(pos);
 }
 
 // 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.
   gcdTightenInequalities();
   Simplex simplex(*this);
   simplex.detectRedundant();
 
   unsigned pos = 0;
void IntegerRelation::removeRedundantConstraints() {
   for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
     if (!(simplex.isMarkedRedundant(numIneqs + 2 * r) &&
           simplex.isMarkedRedundant(numIneqs + 2 * r + 1)))
       equalities.copyRow(r, pos++);
   }
   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);
   // If the polytope is rationally empty, there are certainly no integer
   // points.
   if (simplex.isEmpty())
     return 0;
 
   // 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.
   //
   // We also handle the special case where one dimension is unbounded and
   // another dimension can take no integer values. In this case, the volume is
   // zero.
   //
   // If there is no such empty dimension, if any dimension is unbounded we
Optional<uint64_t> IntegerRelation::computeVolume() const {
 
   if (count == 0)
     return 0;
   if (hasUnboundedId)
     return {};
   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");
 
   unsigned localOffset = getIdKindOffset(IdKind::Local);
   posA += localOffset;
   posB += localOffset;
   inequalities.addToColumn(posB, posA, 1);
   equalities.addToColumn(posB, posA, 1);
   removeId(posB);
 }
 
 /// Adds additional local ids to the sets such that they both have the union
 /// of the local ids in each set, without changing the set of points that
 /// lie in `this` and `other`.
 ///
 /// To detect local ids that always take the same in both sets, each local id is
 /// represented as a floordiv with constant denominator in terms of other ids.
 /// After extracting these divisions, local ids with the same division
 /// 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);
   std::copy(denomsB.begin() + initLocals, denomsB.end(),
             denomsA.begin() + initLocals);
 
   // 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;
   };
 
   // Merge all divisions by removing duplicate divisions.
   unsigned localOffset = getIdKindOffset(IdKind::Local);
   removeDuplicateDivs(divsA, denomsA, localOffset, merge);
 }
 
 /// Removes local variables using equalities. Each equality is checked if it
 /// can be reduced to the form: `e = affine-expr`, where `e` is a local
 /// variable and `affine-expr` is an affine expression not containing `e`.
 /// 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)
     equalities.normalizeRow(i);
 
   while (true) {
     unsigned i, e, j, f;
     for (i = 0, e = getNumEqualities(); i < e; ++i) {
for (unsigned k = 0, t = getNumInequalities(); k < t; ++k)
       eliminateFromConstraint(this, k, i, j, j, /*isEq=*/false);
 
     // Remove the ith equality and the found local variable.
     removeId(j);
     removeEquality(i);
   }
 }
 
-void IntegerPolyhedron::convertDimToLocal(unsigned dimStart,
-                                          unsigned dimLimit) {
+void IntegerRelation::convertDimToLocal(unsigned dimStart, unsigned dimLimit) {
   assert(dimLimit <= getNumDimIds() && "Invalid dim pos range");
 
   if (dimStart >= dimLimit)
     return;
 
   // Append new local variables corresponding to the dimensions to be converted.
   unsigned convertCount = dimLimit - dimStart;
   unsigned newLocalIdStart = getNumIds();
   appendId(IdKind::Local, convertCount);
 
   // Swap the new local variables with dimensions.
   for (unsigned i = 0; i < convertCount; ++i)
     swapId(i + dimStart, i + newLocalIdStart);
 
   // Remove dimensions converted to local variables.
   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();
     equalities(row, pos) = 1;
     equalities(row, getNumCols() - 1) = -value;
   } else {
     unsigned row = inequalities.appendExtraRow();
     inequalities(row, pos) = type == BoundType::LB ? 1 : -1;
     inequalities(row, getNumCols() - 1) =
         type == BoundType::LB ? -value : value;
   }
 }
 
-void IntegerPolyhedron::addBound(BoundType type, ArrayRef<int64_t> expr,
-                                 int64_t value) {
+void IntegerRelation::addBound(BoundType type, ArrayRef<int64_t> expr,
   assert(type != BoundType::EQ && "EQ not implemented");
   assert(expr.size() == getNumCols());
   unsigned row = inequalities.appendExtraRow();
   for (unsigned i = 0, e = expr.size(); i < e; ++i)
     inequalities(row, i) = type == BoundType::LB ? expr[i] : -expr[i];
   inequalities(inequalities.getNumRows() - 1, getNumCols() - 1) +=
       type == BoundType::LB ? -value : value;
 }
 
 /// Adds a new local identifier as the floordiv of an affine function of other
 /// identifiers, the coefficients of which are provided in 'dividend' and with
 /// 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,
   assert(dividend.size() == getNumCols() && "incorrect dividend size");
   assert(divisor > 0 && "positive divisor expected");
 
   appendId(IdKind::Local);
 
   // Add two constraints for this new identifier 'q'.
   SmallVector<int64_t, 8> bound(dividend.size() + 1);
 
void IntegerRelation::addLocalFloorDiv(ArrayRef<int64_t> dividend,
   addInequality(bound);
 }
 
 /// Finds an equality that equates the specified identifier to a constant.
 /// Returns the position of the equality row. If 'symbolic' is set to true,
 /// 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++) {
     int64_t v = cst.atEq(r, pos);
     if (v * v != 1)
       continue;
     unsigned c;
     unsigned f = symbolic ? cst.getNumDimIds() : cst.getNumIds();
     // This checks for zeros in all positions other than 'pos' in [0, f)
     for (c = 0; c < f; c++) {
       if (c == pos)
         continue;
       if (cst.atEq(r, c) != 0) {
         // Dependent on another identifier.
         break;
       }
     }
     if (c == f)
       // Equality is free of other identifiers.
       return r;
   }
   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)
     return failure();
 
   // atEq(rowIdx, pos) is either -1 or 1.
   assert(atEq(rowIdx, pos) * atEq(rowIdx, pos) == 1);
   int64_t constVal = -atEq(rowIdx, getNumCols() - 1) / atEq(rowIdx, pos);
   setAndEliminate(pos, constVal);
   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++;
   }
 }
 
 /// Returns a non-negative constant bound on the extent (upper bound - lower
 /// bound) of the specified identifier if it is found to be a constant; returns
 /// None if it's not a constant. This methods treats symbolic identifiers
 /// specially, i.e., it looks for constant differences between affine
 /// expressions involving only the symbolic identifiers. See comments at
 /// function definition for example. 'lb', if provided, is set to the lower
 /// bound associated with the constant difference. Note that 'lb' is purely
 /// symbolic and thus will contain the coefficients of the symbolic identifiers
 /// and the constant coefficient.
 //  Egs: 0 <= i <= 15, return 16.
 //       s0 + 2 <= i <= s0 + 17, returns 16. (s0 has to be a symbol)
 //       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 {
   assert(pos < getNumDimIds() && "Invalid identifier position");
 
   // Find an equality for 'pos'^th identifier that equates it to some function
   // of the symbolic identifiers (+ constant).
   int eqPos = findEqualityToConstant(*this, pos, /*symbolic=*/true);
if (minLbPos)
     *minLbPos = minLbPosition;
   if (minUbPos)
     *minUbPos = minUbPosition;
   return minDiff;
 }
 
 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);
   projectOut(1, getNumIds() - 1);
   // Check if there's an equality equating the '0'^th identifier to a constant.
   int eqRowIdx = findEqualityToConstant(*this, 0, /*symbolic=*/false);
   if (eqRowIdx != -1)
     // atEq(rowIdx, 0) is either -1 or 1.
for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
     } else {
       if (minOrMaxConst == None || boundConst < minOrMaxConst)
         minOrMaxConst = boundConst;
     }
   }
   return minOrMaxConst;
 }
 
-Optional<int64_t> IntegerPolyhedron::getConstantBound(BoundType type,
-                                                      unsigned pos) const {
+Optional<int64_t> IntegerRelation::getConstantBound(BoundType type,
   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++) {
     unsigned sum = 0;
     for (unsigned c = pos; c < pos + num; c++) {
       if (atIneq(r, c) != 0)
         sum++;
     }

 }
 
 /// Removes duplicate constraints, trivially true constraints, and constraints
 /// that can be detected as redundant as a result of differing only in their
 /// constant term part. A constraint of the form <non-negative constant> >= 0 is
 /// 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();
 
   // A map used to detect redundancy stemming from constraints that only differ
   // in their constant term. The value stored is <row position, const term>
   // for a given row.
   SmallDenseMap<ArrayRef<int64_t>, std::pair<unsigned, int64_t>>
       rowsWithoutConstTerm;

 /// rational shadow / integer light shadow:  1 <= j <= 6
 /// dark shadow:                             3 <= j <= 6
 /// exact integer shadow:                    j = 1 \union  3 <= j <= 6
 /// holes/splinters:                         j = 2
 ///
 /// 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,
   LLVM_DEBUG(llvm::dbgs() << "FM input (eliminate pos " << pos << "):\n");
   LLVM_DEBUG(dump());
   assert(pos < getNumIds() && "invalid position");
   assert(hasConsistentState());
 
   // Check if this identifier can be eliminated through a substitution.
   for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
     if (atEq(r, pos) != 0) {
if (atIneq(r, pos) == 0) {
       lbIndices.push_back(r);
     } else {
       // Upper bound.
       ubIndices.push_back(r);
     }
   }
 
   // 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;
 
   // Let x be the variable we are eliminating.
   // For each lower bound, lb <= c_l*x, and each upper bound c_u*x <= ub, (note
   // that c_l, c_u >= 1) we have:
   // lb*lcm(c_l, c_u)/c_l <= lcm(c_l, c_u)*x <= ub*lcm(c_l, c_u)/c_u
   // We thus generate a constraint:
   // lcm(c_l, c_u)/c_l*lb <= lcm(c_l, c_u)/c_u*ub.
   // Note if c_l = c_u = 1, all integer points captured by the resulting
   // constraint correspond to integer points in the original system (i.e., they
   // have integer pre-images). Hence, if the lcm's are all 1, the elimination is
   // integer exact.
   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
       // term being moved to the other size of '>='.
       int64_t ubCoeff = -atIneq(ubPos, pos);
       // TODO: refactor this loop to avoid all branches inside.
       for (unsigned l = 0, e = getNumCols(); l < e; l++) {
         if (l == pos)
           continue;
         assert(lbCoeff >= 1 && ubCoeff >= 1 && "bounds wrongly identified");
         int64_t lcm = mlir::lcm(lbCoeff, ubCoeff);
         ineq.push_back(atIneq(ubPos, l) * (lcm / ubCoeff) +
                        atIneq(lbPos, l) * (lcm / lbCoeff));
         lcmProducts *= lcm;
       }
       if (darkShadow) {
         // The dark shadow is a convex subset of the exact integer shadow. If
         // there is a point here, it proves the existence of a solution.
         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);
     }
   }
 
   LLVM_DEBUG(llvm::dbgs() << "FM isResultIntegerExact: " << (lcmProducts == 1)
                           << "\n");
   if (lcmProducts == 1 && isResultIntegerExact)
     *isResultIntegerExact = true;
 
   // Copy over the constraints not involving this variable.
   for (auto nbPos : nbIndices) {
     SmallVector<int64_t, 4> ineq;
     ineq.reserve(getNumCols() - 1);
     for (unsigned l = 0, e = getNumCols(); l < e; l++) {
       if (l == pos)
         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());
 }
 
 #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;
 
   // 'pos' can be at most getNumCols() - 2 if num > 0.
   assert((getNumCols() < 2 || pos <= getNumCols() - 2) && "invalid position");
   assert(pos + num < getNumCols() && "invalid range");
 
   // Eliminate as many identifiers as possible using Gaussian elimination.
static BoundCmpResult compareBounds(ArrayRef<int64_t> a, ArrayRef<int64_t> b) {
   if (a.back() == b.back())
     return Equal;
 
   return a.back() < b.back() ? Less : Greater;
 }
 } // 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) {
       if (a.getInequality(r) == b.getInequality(s)) {
         c.addInequality(a.getInequality(r));
         break;
       }
     }
   }
   for (unsigned r = 0, e = a.getNumEqualities(); r < e; ++r) {
     for (unsigned s = 0, f = b.getNumEqualities(); s < f; ++s) {
       if (a.getEquality(r) == b.getEquality(s)) {
         c.addEquality(a.getEquality(r));
         break;
       }
     }
   }
 }
 
 // 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;
   std::vector<SmallVector<int64_t, 8>> boundingUbs;
   boundingLbs.reserve(2 * getNumDimIds());
   boundingUbs.reserve(2 * getNumDimIds());
 
   // To hold lower and upper bounds for each dimension.
IntegerRelation::unionBoundingBox(const IntegerRelation &otherCst) {
 
   // TODO: copy over pure symbolic constraints from this and 'other' over to the
   // union (since the above are just the union along dimensions); we shouldn't
   // be discarding any other constraints on the symbols.
 
   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);
 }
 
 /// 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");
   assert(pos + num <= cst.getNumIds() && "invalid limit");
 
   for (unsigned r = 0, e = cst.getNumInequalities(); r < e; r++) {
     // The bounds are to be independent of [offset, offset + num) columns.
     unsigned c;
for (c = pos; c < pos + num; ++c) {
       if (cst.atEq(r, c) != 0)
         break;
     }
     if (c == pos + num)
       nbEqIndices.push_back(r);
   }
 }
 
-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.
   SmallVector<unsigned, 4> nbIneqIndices, nbEqIndices;
   getIndependentConstraints(*this, /*pos=*/0, num, nbIneqIndices, nbEqIndices);
 
   // Iterate in reverse so that indices don't have to be updated.
   // TODO: This method can be made more efficient (because removal of each
   // inequality leads to much shifting/copying in the underlying buffer).
   for (auto nbIndex : llvm::reverse(nbIneqIndices))
     removeInequality(nbIndex);
   for (auto nbIndex : llvm::reverse(nbEqIndices))
     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) {
     for (unsigned j = 0, f = getNumCols(); j < f; ++j) {
       os << atEq(i, j) << " ";
     }
     os << "= 0\n";
   }
   for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
     for (unsigned j = 0, f = getNumCols(); j < f; ++j) {
       os << atIneq(i, j) << " ";
     }
     os << ">= 0\n";
   }
   os << '\n';
 }
 
-void IntegerPolyhedron::dump() const { print(llvm::errs()); }
+void IntegerRelation::dump() const { print(llvm::errs()); }

mlir/lib/Analysis/Presburger/LinearTransform.cpp

 //===- LinearTransform.cpp - MLIR LinearTransform 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/LinearTransform.h"
-#include "mlir/Analysis/Presburger/IntegerPolyhedron.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 
 using namespace mlir;
 using namespace presburger;
 
 LinearTransform::LinearTransform(Matrix &&oMatrix) : matrix(oMatrix) {}
 LinearTransform::LinearTransform(const Matrix &oMatrix) : matrix(oMatrix) {}
 
 // Set M(row, targetCol) to its remainder on division by M(row, sourceCol)
for (unsigned row = 0; row < m.getNumRows(); ++row) {
     }
 
     ++echelonCol;
   }
 
   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();
 
     SmallVector<int64_t, 8> newEq = preMultiplyWithRow(eq.drop_back());
     newEq.push_back(c);
     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();
 
     SmallVector<int64_t, 8> newIneq = preMultiplyWithRow(ineq.drop_back());
     newIneq.push_back(c);
     result.addInequality(newIneq);
   }
 
   return result;
 }

mlir/lib/Analysis/Presburger/PresburgerSet.cpp

for (MaybeLocalRepr &maybeInequality : repr) {
     isDivInequality[ub] = true;
   }
 
   unsigned offset = simplex.getNumConstraints();
   unsigned numLocalsAdded = b.getNumLocalIds() - bInitNumLocals;
   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.
     // We are ignoring level i completely, so we restore the state
     // *before* going to level i + 1.
     restoreState();
     subtractRecursively(b, simplex, s, i + 1, result);
 

mlir/lib/Analysis/Presburger/PresburgerSpace.cpp

 
 PresburgerLocalSpace PresburgerLocalSpace::getSetSpace(unsigned numDims,
                                                        unsigned numSymbols,
                                                        unsigned numLocals) {
   return PresburgerLocalSpace(numDims, numSymbols, numLocals);
 }
 
 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)
     return getNumSymbolIds();
   if (kind == IdKind::Local)
     return numLocals;
   llvm_unreachable("IdKind does not exist!");
 }
 
 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)
     return getNumDimIds();
   if (kind == IdKind::Local)
     return getNumDimAndSymbolIds();
   llvm_unreachable("IdKind does not exist!");
 }

mlir/lib/Analysis/Presburger/Simplex.cpp

for (unsigned i = 0; i < count; ++i) {
     var.emplace_back(Orientation::Column, /*restricted=*/false,
                      /*pos=*/nCol - 1);
     colUnknown.push_back(var.size() - 1);
   }
   tableau.resizeHorizontally(nCol);
   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,
                                                   unsigned row) {
   // Keep trying to find a pivot for the row in the specified direction.
   while (Optional<Pivot> maybePivot = findPivot(row, direction)) {
     // If findPivot returns a pivot involving the row itself, then the optimum
     // is unbounded, so we return None.
for (unsigned col = 0; col < nCol; ++col)
       os << tableau(row, col) << '\t';
     os << '\n';
   }
   os << '\n';
 }
 
 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;
 }
 
 /// Returns the type of the inequality with coefficients `coeffs`.
 /// Possible types are:
 /// Redundant   The inequality is satisfied by all points in the polytope

mlir/lib/Analysis/Presburger/Utils.cpp

 //===- Utils.cpp - General utilities for Presburger library ---------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Utility functions required by the Presburger Library.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 
 using namespace mlir;
 using namespace presburger;
 
 /// Normalize a division's `dividend` and the `divisor` by their GCD. For
 /// example: if the dividend and divisor are [2,0,4] and 4 respectively,

 ///     c <= expr - divisior * id <= divisor - 1, where 0 <= c <= divisor - 1
 /// Rearranging, we have:
 ///     divisor * id - expr + (divisor - 1) >= 0  <-- Lower bound for 'id'
 ///    -divisor * id + expr - c             >= 0  <-- Upper bound for 'id'
 ///
 /// 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) {
 
   assert(pos <= cst.getNumIds() && "Invalid identifier position");
   assert(ubIneq <= cst.getNumInequalities() &&
          "Invalid upper bound inequality position");
   assert(lbIneq <= cst.getNumInequalities() &&

 /// For example:
 ///     32*k == 16*i + j - 31                 <-- `eqInd` for 'k'
 ///     expr = 16*i + j - 31, divisor = 32
 ///     k = (16*i + j - 31) floordiv 32
 ///
 /// 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) {
 
   assert(pos <= cst.getNumIds() && "Invalid identifier position");
   assert(eqInd <= cst.getNumEqualities() && "Invalid equality position");
 
   // Extract divisor, the divisor can be negative and hence its sign information
   // is stored in `signDiv` to reverse the sign of dividend's coefficients.
static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
   expr.back() = signDiv * cst.atEq(eqInd, cst.getNumCols() - 1);
   normalizeDivisionByGCD(expr, divisor);
 
   return success();
 }
 
 // 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) {
   // Exit to avoid circular dependencies between divisions.
   for (unsigned c = 0, e = cst.getNumIds(); c < e; ++c) {
     if (c == pos)
       continue;
 

 /// `foundRepr` contains a boolean for each identifier indicating if the
 /// explicit representation for that identifier has already been computed.
 /// Returns the `MaybeLocalRepr` struct which contains the indices of the
 /// constraints that can be expressed as a floordiv of an affine function. If
 /// 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 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() &&
          "Size of foundRepr does not match total number of variables");
 
   SmallVector<unsigned, 4> lbIndices, ubIndices, eqIndices;
   cst.getLowerAndUpperBoundIndices(pos, &lbIndices, &ubIndices, &eqIndices);
   MaybeLocalRepr repr{};

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

if (auto *valueCstr = dyn_cast<const FlatAffineValueConstraints>(this)) {
         os << "None ";
     } else {
       os << "None ";
     }
   }
   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");
 
   // Note: Assigment operator does not vtable pointer, so kind does not
   // change.
   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)) {
     *this = *otherValueSet;
     return;
   }
 
   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);
 }
 
 void FlatAffineValueConstraints::fourierMotzkinEliminate(
     unsigned pos, bool darkShadow, bool *isResultIntegerExact) {
   SmallVector<Optional<Value>, 8> newVals;

mlir/unittests/Analysis/Presburger/IntegerPolyhedronTest.cpp

 //===- IntegerPolyhedron.cpp - Tests for IntegerPolyhedron 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/IntegerPolyhedron.h"
 #include "./Utils.h"
+#include "mlir/Analysis/Presburger/IntegerRelation.h"
 #include "mlir/Analysis/Presburger/Simplex.h"
 #include "mlir/IR/MLIRContext.h"
 
 #include <gmock/gmock.h>
 #include <gtest/gtest.h>
 
 #include <numeric>
 

mlir/unittests/Analysis/Presburger/Utils.h

 //===- Utils.h - Utils for Presburger 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 defines helper functions for Presburger unittests.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_UNITTESTS_ANALYSIS_PRESBURGER_UTILS_H
 #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"
 
 #include <gtest/gtest.h>
 
 namespace mlir {
 namespace presburger {