[MLIR][Affine][Analysis] Merge FAC and FACV

[Groverkss]

Summary

With the introduction of IntegerPolyhedron and IntegerRelation in Presburger
directory, the purpose of FlatAffineConstraints becomes redundant. For users
requiring Presburger arithmetic without IR information, Presburger library can
directly be used. For users requiring IR information,
FlatAffineValueConstraints can be used.

This patch merges FAC and FACV to remove redundancy of FAC.

[arjunp]

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

36

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

40–46

I think these should be IntegerPolyhedron

[Groverkss]

• Address Arjun's comments

[bondhugula]

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

37–58

Is this information being deleted already captured/subsumed elsewhere or is this being lost?

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

296–297

Looks like there is an API behavior difference here. An insertId for a 0 count should be valid and supported for completeness and to be intuitive. We shouldn't be using an extra check (for num == 0) at the user site. Can you update the insertId on IntegerPolyhedron to drop this check. (It's valid to say you are insert 0 things at pos -- so returning an absolute position is valid.)

[Groverkss]

• Rebase
• Address Uday's comments

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

37–58

The information about identifiers is already documented in PresburgerSpace. The information about inequalities and equalities is documented in IntegerPolyhedron. The only information lost is about reservedInequalities, reservedEqualities, reservedCols, which we can add to IntegerPolyhedron if required.

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

296–297

IntegerPolyhedron::insertId already does it. I think I added this for values.insert but it seems to work regardless so removing this if condition.

[bondhugula]

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

37–58

I think reserved constraints size is an internal detail - fine to omit it here.

[bondhugula]

This change is looking good to me - thanks!

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

 class AffineMap;
 class AffineValueMap;
 class IntegerSet;
 class MLIRContext;
 class Value;
 class MemRefType;
 struct MutableAffineMap;
 
-/// A flat list of affine equalities and inequalities in the form.
-/// Inequality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} >= 0
-/// Equality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} == 0
-///
-/// FlatAffineConstraints stores coefficients in a contiguous buffer (one buffer
-/// for equalities and one for inequalities). The size of each buffer is
-/// numReservedCols * number of inequalities (or equalities). The reserved size
-/// is numReservedCols * numReservedInequalities (or numReservedEqualities). A
-/// coefficient (r, c) lives at the location numReservedCols * r + c in the
-/// buffer. The extra space between getNumCols() and numReservedCols exists to
-/// prevent frequent movement of data when adding columns, especially at the
-/// end.
-///
-/// The identifiers x_0, x_1, ... appear in the order: dimensional identifiers,
-/// symbolic identifiers, and local identifiers.  The local identifiers
-/// correspond to local/internal variables created when converting from
-/// AffineExpr's containing mod's and div's; they are thus needed to increase
-/// representational power. Each local identifier is always (by construction) a
-/// floordiv of a pure add/mul affine function of dimensional, symbolic, and
-/// other local identifiers, in a non-mutually recursive way. Hence, every local
-/// identifier can ultimately always be recovered as an affine function of
-/// dimensional and symbolic identifiers (involving floordiv's); note however
-/// that some floordiv combinations are converted to mod's by AffineExpr
-/// construction.
-///
-class FlatAffineConstraints : public presburger::IntegerPolyhedron {
-public:
-  /// Constructs a constraint system reserving memory for the specified number
-  /// of constraints and identifiers.
-  FlatAffineConstraints(unsigned numReservedInequalities,
-                        unsigned numReservedEqualities,
-                        unsigned numReservedCols, unsigned numDims,
-                        unsigned numSymbols, unsigned numLocals)
-      : IntegerPolyhedron(
-            numReservedInequalities, numReservedEqualities, numReservedCols,
-            PresburgerSpace::getSetSpace(numDims, numSymbols, numLocals)) {}
-
-  /// Constructs a constraint system with the specified number of
-  /// dimensions and symbols.
-  FlatAffineConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
-                        unsigned numLocals = 0)
-      : FlatAffineConstraints(/*numReservedInequalities=*/0,
-                              /*numReservedEqualities=*/0,
-                              /*numReservedCols=*/numDims + numSymbols +
-                                  numLocals + 1,
-                              numDims, numSymbols, numLocals) {}
-
-  explicit FlatAffineConstraints(const IntegerPolyhedron &poly)
-      : IntegerPolyhedron(poly) {}
-
-  /// Return a system with no constraints, i.e., one which is satisfied by all
-  /// points.
-  static FlatAffineConstraints getUniverse(unsigned numDims = 0,
-                                           unsigned numSymbols = 0) {
-    return FlatAffineConstraints(numDims, numSymbols);
-  }
-
-  /// Creates an affine constraint system from an IntegerSet.
-  explicit FlatAffineConstraints(IntegerSet set);
-
-  ~FlatAffineConstraints() override = default;
-
-  /// Return the kind of this FlatAffineConstraints.
-  Kind getKind() const override { return Kind::FlatAffineConstraints; }
-
-  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,
-                     unsigned numLocals = 0);
-  void reset(unsigned numDims = 0, unsigned numSymbols = 0,
-             unsigned numLocals = 0);
-
-  // Clones this object.
-  std::unique_ptr<FlatAffineConstraints> clone() const;
-
-  /// Insert `num` identifiers of the specified kind at position `pos`.
-  /// Positions are relative to the kind of identifier. The coefficient columns
-  /// corresponding to the added identifiers are initialized to zero. Return the
-  /// absolute column position (i.e., not relative to the kind of identifier)
-  /// of the first added identifier.
-  unsigned insertDimId(unsigned pos, unsigned num = 1) {
-    return insertId(IdKind::SetDim, pos, num);
-  }
-  unsigned insertSymbolId(unsigned pos, unsigned num = 1) {
-    return insertId(IdKind::Symbol, pos, num);
-  }
-  unsigned insertLocalId(unsigned pos, unsigned num = 1) {
-    return insertId(IdKind::Local, pos, num);
-  }
-
-  /// Append `num` identifiers of the specified kind after the last identifier.
-  /// of that kind. Return the position of the first appended column relative to
-  /// the kind of identifier. The coefficient columns corresponding to the added
-  /// identifiers are initialized to zero.
-  unsigned appendDimId(unsigned num = 1) {
-    return appendId(IdKind::SetDim, num);
-  }
-  unsigned appendSymbolId(unsigned num = 1) {
-    return appendId(IdKind::Symbol, num);
-  }
-  unsigned appendLocalId(unsigned num = 1) {
-    return appendId(IdKind::Local, num);
-  }
-
-  /// Adds a bound for the identifier at the specified position with constraints
-  /// being drawn from the specified bound map. In case of an EQ bound, the
-  /// bound map is expected to have exactly one result. In case of a LB/UB, the
-  /// bound map may have more than one result, for each of which an inequality
-  /// is added.
-  /// Note: The dimensions/symbols of this FlatAffineConstraints must match the
-  /// dimensions/symbols of the affine map.
-  LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap);
-
-  /// The `addBound` overload above hides the inherited overloads by default, so
-  /// we explicitly introduce them here.
-  using IntegerPolyhedron::addBound;
-
-  /// Returns the constraint system as an integer set. Returns a null integer
-  /// set if the system has no constraints, or if an integer set couldn't be
-  /// constructed as a result of a local variable's explicit representation not
-  /// being known and such a local variable appearing in any of the constraints.
-  IntegerSet getAsIntegerSet(MLIRContext *context) const;
-
-  /// Computes the lower and upper bounds of the first `num` dimensional
-  /// identifiers (starting at `offset`) as an affine map of the remaining
-  /// identifiers (dimensional and symbolic). This method is able to detect
-  /// identifiers as floordiv's and mod's of affine expressions of other
-  /// identifiers with respect to (positive) constants. Sets bound map to a
-  /// null AffineMap if such a bound can't be found (or yet unimplemented).
-  void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context,
-                      SmallVectorImpl<AffineMap> *lbMaps,
-                      SmallVectorImpl<AffineMap> *ubMaps);
-
-  /// 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 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.
-  std::pair<AffineMap, AffineMap>
-  getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num,
-                        unsigned symStartPos, ArrayRef<AffineExpr> localExprs,
-                        MLIRContext *context) const;
-
-protected:
-  using IdKind = presburger::IdKind;
-
-  /// Given an affine map that is aligned with this constraint system:
-  /// * Flatten the map.
-  /// * Add newly introduced local columns at the beginning of this constraint
-  ///   system (local column pos 0).
-  /// * Add equalities that define the new local columns to this constraint
-  ///   system.
-  /// * Return the flattened expressions via `flattenedExprs`.
-  ///
-  /// Note: This is a shared helper function of `addLowerOrUpperBound` and
-  ///       `composeMatchingMap`.
-  LogicalResult flattenAlignedMapAndMergeLocals(
-      AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs);
-
-  /// Prints the number of constraints, dimensions, symbols and locals in the
-  /// FlatAffineConstraints. Also, prints for each identifier whether there is
-  /// an SSA Value attached to it.
-  void printSpace(raw_ostream &os) const override;
-};
-
-/// An extension of FlatAffineConstraints in which dimensions and symbols can
-/// optionally be associated with an SSA value.
-class FlatAffineValueConstraints : public FlatAffineConstraints {
+/// FlatAffineValueConstraints represents an extension of IntegerPolyhedron
+/// where each identifier can have an SSA Value attached to it.
+class FlatAffineValueConstraints : public presburger::IntegerPolyhedron {
 public:
   /// Constructs a constraint system reserving memory for the specified number
   /// of constraints and identifiers.
   FlatAffineValueConstraints(unsigned numReservedInequalities,
                              unsigned numReservedEqualities,
                              unsigned numReservedCols, unsigned numDims,
                              unsigned numSymbols, unsigned numLocals,
                              ArrayRef<Optional<Value>> valArgs = {})
-      : FlatAffineConstraints(numReservedInequalities, numReservedEqualities,
-                              numReservedCols, numDims, numSymbols, numLocals) {
+      : IntegerPolyhedron(
+            numReservedInequalities, numReservedEqualities, numReservedCols,
+            PresburgerSpace::getSetSpace(numDims, numSymbols, numLocals)) {
     assert(numReservedCols >= getNumIds() + 1);
     assert(valArgs.empty() || valArgs.size() == getNumIds());
     values.reserve(numReservedCols);
     if (valArgs.empty())
       values.resize(getNumIds(), None);
     else
       values.append(valArgs.begin(), valArgs.end());
   }
 
   /// Constructs a constraint system with the specified number of
   /// dimensions and symbols.
   FlatAffineValueConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
                              unsigned numLocals = 0,
                              ArrayRef<Optional<Value>> valArgs = {})
       : FlatAffineValueConstraints(/*numReservedInequalities=*/0,
                                    /*numReservedEqualities=*/0,
                                    /*numReservedCols=*/numDims + numSymbols +
                                        numLocals + 1,
                                    numDims, numSymbols, numLocals, valArgs) {}
 
-  FlatAffineValueConstraints(const FlatAffineConstraints &fac,
+  FlatAffineValueConstraints(const IntegerPolyhedron &fac,
                              ArrayRef<Optional<Value>> valArgs = {})
-      : FlatAffineConstraints(fac) {
+      : IntegerPolyhedron(fac) {
     assert(valArgs.empty() || valArgs.size() == getNumIds());
     if (valArgs.empty())
       values.resize(getNumIds(), None);
     else
       values.append(valArgs.begin(), valArgs.end());
   }
 
   /// Create a flat affine constraint system from an AffineValueMap or a list of
public:
   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;
+             unsigned numLocals = 0);
+  void reset(unsigned numDims = 0, unsigned numSymbols = 0,
+             unsigned numLocals = 0);
   void reset(unsigned numReservedInequalities, unsigned numReservedEqualities,
              unsigned numReservedCols, unsigned numDims, unsigned numSymbols,
              unsigned numLocals, ArrayRef<Value> valArgs);
   void reset(unsigned numDims, unsigned numSymbols, unsigned numLocals,
              ArrayRef<Value> valArgs);
-  using FlatAffineConstraints::reset;
 
   /// Clones this object.
   std::unique_ptr<FlatAffineValueConstraints> clone() const;
 
   /// Adds constraints (lower and upper bounds) for the specified 'affine.for'
   /// operation's Value using IR information stored in its bound maps. The
   /// right identifier is first looked up using `forOp`'s Value. Asserts if the
   /// Value corresponding to the 'affine.for' operation isn't found in the
public:
   /// instance argument (`ifOp`). It is asserted that:
   /// 1) The IntegerSet of the given `affine.if` instance should not contain
   /// semi-affine expressions,
   /// 2) The columns of the constraint system created from `ifOp` should match
   /// the columns in the current one regarding numbers and values.
   void addAffineIfOpDomain(AffineIfOp ifOp);
 
   /// Adds a bound for the identifier at the specified position with constraints
+  /// being drawn from the specified bound map. In case of an EQ bound, the
+  /// bound map is expected to have exactly one result. In case of a LB/UB, the
+  /// bound map may have more than one result, for each of which an inequality
+  /// is added.
+  /// Note: The dimensions/symbols of this FlatAffineConstraints must match the
+  /// dimensions/symbols of the affine map.
+  LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap);
+
+  /// Adds a bound for the identifier at the specified position with constraints
   /// being drawn from the specified bound map and operands. In case of an
   /// EQ bound, the  bound map is expected to have exactly one result. In case
   /// of a LB/UB, the bound map may have more than one result, for each of which
   /// an inequality is added.
   LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap,
                          ValueRange operands);
 
   /// Adds a constant bound for the identifier associated with the given Value.
   void addBound(BoundType type, Value val, int64_t value);
 
-  using FlatAffineConstraints::addBound;
+  /// The `addBound` overload above hides the inherited overloads by default, so
+  /// we explicitly introduce them here.
+  using IntegerPolyhedron::addBound;
+
+  /// Returns the constraint system as an integer set. Returns a null integer
+  /// set if the system has no constraints, or if an integer set couldn't be
+  /// constructed as a result of a local variable's explicit representation not
+  /// being known and such a local variable appearing in any of the constraints.
+  IntegerSet getAsIntegerSet(MLIRContext *context) const;
+
+  /// Computes the lower and upper bounds of the first `num` dimensional
+  /// identifiers (starting at `offset`) as an affine map of the remaining
+  /// identifiers (dimensional and symbolic). This method is able to detect
+  /// identifiers as floordiv's and mod's of affine expressions of other
+  /// identifiers with respect to (positive) constants. Sets bound map to a
+  /// null AffineMap if such a bound can't be found (or yet unimplemented).
+  void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context,
+                      SmallVectorImpl<AffineMap> *lbMaps,
+                      SmallVectorImpl<AffineMap> *ubMaps);
+
+  /// 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);
+
+  /// 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.
+  std::pair<AffineMap, AffineMap>
+  getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num,
+                        unsigned symStartPos, ArrayRef<AffineExpr> localExprs,
+                        MLIRContext *context) const;
 
   /// Returns the bound for the identifier at `pos` from the inequality at
   /// `ineqPos` as a 1-d affine value map (affine map + operands). The returned
   /// affine value map can either be a lower bound or an upper bound depending
   /// on the sign of atIneq(ineqPos, pos). Asserts if the row at `ineqPos` does
   /// not involve the `pos`th identifier.
   void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos,
                                AffineValueMap &vmap,
public:
   /// Insert identifiers of the specified kind at position `pos`. Positions are
   /// relative to the kind of identifier. The coefficient columns corresponding
   /// to the added identifiers are initialized to zero. `vals` are the Values
   /// corresponding to the identifiers. Return the absolute column position
   /// (i.e., not relative to the kind of identifier) of the first added
   /// identifier.
   ///
   /// Note: Empty Values are allowed in `vals`.
+  unsigned insertDimId(unsigned pos, unsigned num = 1) {
+    return insertId(IdKind::SetDim, pos, num);
+  }
+  unsigned insertSymbolId(unsigned pos, unsigned num = 1) {
+    return insertId(IdKind::Symbol, pos, num);
+  }
+  unsigned insertLocalId(unsigned pos, unsigned num = 1) {
+    return insertId(IdKind::Local, pos, num);
+  }
   unsigned insertDimId(unsigned pos, ValueRange vals);
-  using FlatAffineConstraints::insertDimId;
   unsigned insertSymbolId(unsigned pos, ValueRange vals);
-  using FlatAffineConstraints::insertSymbolId;
-  unsigned insertId(IdKind kind, unsigned pos, unsigned num = 1) override;
-  unsigned insertId(IdKind kind, unsigned pos, ValueRange vals);
+  unsigned insertId(presburger::IdKind kind, unsigned pos,
+                    unsigned num = 1) override;
+  unsigned insertId(presburger::IdKind kind, unsigned pos, ValueRange vals);
 
   /// Append identifiers of the specified kind after the last identifier of that
   /// kind. The coefficient columns corresponding to the added identifiers are
   /// initialized to zero. `vals` are the Values corresponding to the
   /// identifiers. Return the position of the first added column.
   ///
   /// Note: Empty Values are allowed in `vals`.
   unsigned appendDimId(ValueRange vals);
-  using FlatAffineConstraints::appendDimId;
   unsigned appendSymbolId(ValueRange vals);
-  using FlatAffineConstraints::appendSymbolId;
+  unsigned appendDimId(unsigned num = 1) {
+    return appendId(IdKind::SetDim, num);
+  }
+  unsigned appendSymbolId(unsigned num = 1) {
+    return appendId(IdKind::Symbol, num);
+  }
+  unsigned appendLocalId(unsigned num = 1) {
+    return appendId(IdKind::Local, num);
+  }
 
   /// 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(IdKind kind, unsigned idStart, unsigned idLimit) override;
-  using IntegerRelation::removeIdRange;
+  void removeIdRange(presburger::IdKind kind, unsigned idStart,
+                     unsigned idLimit) override;
+  using IntegerPolyhedron::removeIdRange;
 
   /// Add the specified values as a dim or symbol id depending on its nature, if
   /// it already doesn't exist in the system. `val` has to be either a terminal
   /// symbol or a loop IV, i.e., it cannot be the result affine.apply of any
   /// symbols or loop IVs. The identifier is added to the end of the existing
   /// dims or symbols. Additional information on the identifier is extracted
   /// from the IR and added to the constraint system.
   void addInductionVarOrTerminalSymbol(Value val);
public:
   /// The vMap's operand Value's are used to look up the right positions in
   /// the FlatAffineConstraints with which to associate. Every operand of vMap
   /// should have a matching dim/symbol column in this constraint system (with
   /// the same associated Value).
   LogicalResult composeMap(const AffineValueMap *vMap);
 
   /// Projects out the identifier that is associate with Value.
   void projectOut(Value val);
-  using FlatAffineConstraints::projectOut;
+  using IntegerPolyhedron::projectOut;
 
   /// Changes all symbol identifiers which are loop IVs to dim identifiers.
   void convertLoopIVSymbolsToDims();
 
   /// Updates the constraints to be the smallest bounding (enclosing) box that
   /// contains the points of `this` set and that of `other`, with the symbols
   /// being treated specially. For each of the dimensions, the min of the lower
   /// bounds (symbolic) and the max of the upper bounds (symbolic) is computed
   /// to determine such a bounding box. `other` is expected to have the same
   /// dimensional identifiers as this constraint system (in the same order).
   ///
   /// E.g.:
   /// 1) this   = {0 <= d0 <= 127},
   ///    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 FlatAffineValueConstraints &other);
-  using FlatAffineConstraints::unionBoundingBox;
+  using IntegerPolyhedron::unionBoundingBox;
 
   /// Merge and align the identifiers of `this` and `other` starting at
   /// `offset`, so that both constraint systems get the union of the contained
   /// identifiers that is dimension-wise and symbol-wise unique; both
   /// constraint systems are updated so that they have the union of all
   /// identifiers, with `this`'s original identifiers appearing first followed
   /// by any of `other`'s identifiers that didn't appear in `this`. Local
   /// identifiers in `other` that have the same division representation as local
public:
 
   /// Merge and align symbols of `this` and `other` such that both get union of
   /// of symbols that are unique. Symbols in `this` and `other` should be
   /// unique. Symbols with Value as `None` are considered to be inequal to all
   /// other symbols.
   void mergeSymbolIds(FlatAffineValueConstraints &other);
 
 protected:
+  using IdKind = presburger::IdKind;
+
   /// 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.
   bool hasConsistentState() const override;
 
+  /// Given an affine map that is aligned with this constraint system:
+  /// * Flatten the map.
+  /// * Add newly introduced local columns at the beginning of this constraint
+  ///   system (local column pos 0).
+  /// * Add equalities that define the new local columns to this constraint
+  ///   system.
+  /// * Return the flattened expressions via `flattenedExprs`.
+  ///
+  /// Note: This is a shared helper function of `addLowerOrUpperBound` and
+  ///       `composeMatchingMap`.
+  LogicalResult flattenAlignedMapAndMergeLocals(
+      AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs);
+
   /// Eliminates the identifier at the specified position using Fourier-Motzkin
   /// variable elimination, but uses Gaussian elimination if there is an
   /// equality involving that identifier. If the result of the elimination is
   /// integer exact, `*isResultIntegerExact` is set to true. If `darkShadow` is
   /// set to true, a potential under approximation (subset) of the rational
   /// shadow / exact integer shadow is computed.
   // See implementation comments for more details.
   void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false,
                                bool *isResultIntegerExact = nullptr) override;
 
+  /// Prints the number of constraints, dimensions, symbols and locals in the
+  /// FlatAffineConstraints. Also, prints for each identifier whether there is
+  /// an SSA Value attached to it.
+  void printSpace(raw_ostream &os) const override;
+
   /// Values corresponding to the (column) identifiers of this constraint
   /// system appearing in the order the identifiers correspond to columns.
   /// Temporary ones or those that aren't associated with any Value are set to
   /// None.
   SmallVector<Optional<Value>, 8> values;
 };
 
 /// A FlatAffineRelation represents a set of ordered pairs (domain -> range)
FlatAffineRelation(unsigned numDomainDims = 0, unsigned numRangeDims = 0,
         numDomainDims(numDomainDims), numRangeDims(numRangeDims) {}
 
   FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims,
                      FlatAffineValueConstraints &fac)
       : FlatAffineValueConstraints(fac), numDomainDims(numDomainDims),
         numRangeDims(numRangeDims) {}
 
   FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims,
-                     FlatAffineConstraints &fac)
+                     IntegerPolyhedron &fac)
       : FlatAffineValueConstraints(fac), numDomainDims(numDomainDims),
         numRangeDims(numRangeDims) {}
 
   /// Returns a set corresponding to the domain/range of the affine relation.
   FlatAffineValueConstraints getDomainSet() const;
   FlatAffineValueConstraints getRangeSet() const;
 
   /// Returns the number of identifiers corresponding to domain/range of

 /// of dimensions, symbols, and in turn other floor divisions.  Returns failure
 /// if 'expr' could not be flattened (i.e., semi-affine is not yet handled).
 /// 'cst' contains constraints that connect newly introduced local identifiers
 /// to existing dimensional and symbolic identifiers. See documentation for
 /// AffineExprFlattener on how mod's and div's are flattened.
 LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims,
                                      unsigned numSymbols,
                                      SmallVectorImpl<int64_t> *flattenedExpr,
-                                     FlatAffineConstraints *cst = nullptr);
+                                     FlatAffineValueConstraints *cst = nullptr);
 
 /// Flattens the result expressions of the map to their corresponding flattened
 /// forms and set in 'flattenedExprs'. Returns failure if any expression in the
 /// map could not be flattened (i.e., semi-affine is not yet handled). 'cst'
 /// contains constraints that connect newly introduced local identifiers to
 /// existing dimensional and / symbolic identifiers. See documentation for
 /// AffineExprFlattener on how mod's and div's are flattened. For all affine
 /// expressions that share the same operands (like those of an affine map), this
 /// method should be used instead of repeatedly calling getFlattenedAffineExpr
 /// since local variables added to deal with div's and mod's will be reused
 /// across expressions.
 LogicalResult
 getFlattenedAffineExprs(AffineMap map,
                         std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
-                        FlatAffineConstraints *cst = nullptr);
+                        FlatAffineValueConstraints *cst = nullptr);
 LogicalResult
 getFlattenedAffineExprs(IntegerSet set,
                         std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
-                        FlatAffineConstraints *cst = nullptr);
+                        FlatAffineValueConstraints *cst = nullptr);
 
 /// Re-indexes the dimensions and symbols of an affine map with given `operands`
 /// values to align with `dims` and `syms` values.
 ///
 /// Each dimension/symbol of the map, bound to an operand `o`, is replaced with
 /// dimension `i`, where `i` is the position of `o` within `dims`. If `o` is not
 /// in `dims`, replace it with symbol `i`, where `i` is the position of `o`
 /// within `syms`. If `o` is not in `syms` either, replace it with a new symbol.

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

 #include "mlir/Interfaces/ViewLikeInterface.h"
 #include "llvm/ADT/TypeSwitch.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "affine-analysis"
 
 using namespace mlir;
+using namespace presburger;
 
 /// Get the value that is being reduced by `pos`-th reduction in the loop if
 /// such a reduction can be performed by affine parallel loops. This assumes
 /// floating-point operations are commutative. On success, `kind` will be the
 /// reduction kind suitable for use in affine parallel loop builder. If the
 /// reduction is not supported, returns null.
 static Value getSupportedReduction(AffineForOp forOp, unsigned pos,
                                    arith::AtomicRMWKind &kind) {
static void computeDirectionVector(
   // Eliminate all variables other than the direction variables just added.
   dependenceDomain->projectOut(numCommonLoops, numIdsToEliminate);
 
   // Scan each common loop variable column and set direction vectors based
   // on eliminated constraint system.
   dependenceComponents->resize(numCommonLoops);
   for (unsigned j = 0; j < numCommonLoops; ++j) {
     (*dependenceComponents)[j].op = commonLoops[j].getOperation();
-    auto lbConst =
-        dependenceDomain->getConstantBound(FlatAffineConstraints::LB, j);
+    auto lbConst = dependenceDomain->getConstantBound(IntegerPolyhedron::LB, j);
     (*dependenceComponents)[j].lb =
         lbConst.getValueOr(std::numeric_limits<int64_t>::min());
-    auto ubConst =
-        dependenceDomain->getConstantBound(FlatAffineConstraints::UB, j);
+    auto ubConst = dependenceDomain->getConstantBound(IntegerPolyhedron::UB, j);
     (*dependenceComponents)[j].ub =
         ubConst.getValueOr(std::numeric_limits<int64_t>::max());
   }
 }
 
 LogicalResult MemRefAccess::getAccessRelation(FlatAffineRelation &rel) const {
   // Create set corresponding to domain of access.
   FlatAffineValueConstraints domain;

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

 using namespace mlir;
 using namespace presburger;
 
 namespace {
 
 // See comments for SimpleAffineExprFlattener.
 // An AffineExprFlattener extends a SimpleAffineExprFlattener by recording
 // constraint information associated with mod's, floordiv's, and ceildiv's
-// in FlatAffineConstraints 'localVarCst'.
+// in FlatAffineValueConstraints 'localVarCst'.
 struct AffineExprFlattener : public SimpleAffineExprFlattener {
 public:
   // Constraints connecting newly introduced local variables (for mod's and
   // div's) to existing (dimensional and symbolic) ones. These are always
   // inequalities.
-  FlatAffineConstraints localVarCst;
+  IntegerPolyhedron localVarCst;
 
   AffineExprFlattener(unsigned nDims, unsigned nSymbols)
-      : SimpleAffineExprFlattener(nDims, nSymbols) {
-    localVarCst.reset(nDims, nSymbols, /*numLocals=*/0);
-  }
+      : SimpleAffineExprFlattener(nDims, nSymbols),
+        localVarCst(PresburgerSpace::getSetSpace(nDims, nSymbols)) {}
 
 private:
   // Add a local identifier (needed to flatten a mod, floordiv, ceildiv expr).
   // The local identifier added is always a floordiv of a pure add/mul affine
   // function of other identifiers, coefficients of which are specified in
   // `dividend' and with respect to the positive constant `divisor'. localExpr
   // is the simplified tree expression (AffineExpr) corresponding to the
   // quantifier.
   void addLocalFloorDivId(ArrayRef<int64_t> dividend, int64_t divisor,
                           AffineExpr localExpr) override {
     SimpleAffineExprFlattener::addLocalFloorDivId(dividend, divisor, localExpr);
     // Update localVarCst.
     localVarCst.addLocalFloorDiv(dividend, divisor);
   }
 };
 
 } // namespace
 
 // Flattens the expressions in map. Returns failure if 'expr' was unable to be
 // flattened (i.e., semi-affine expressions not handled yet).
 static LogicalResult
 getFlattenedAffineExprs(ArrayRef<AffineExpr> exprs, unsigned numDims,
                         unsigned numSymbols,
                         std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
-                        FlatAffineConstraints *localVarCst) {
+                        FlatAffineValueConstraints *localVarCst) {
   if (exprs.empty()) {
     localVarCst->reset(numDims, numSymbols);
     return success();
   }
 
   AffineExprFlattener flattener(numDims, numSymbols);
   // Use the same flattener to simplify each expression successively. This way
   // local identifiers / expressions are shared.

 }
 
 // Flattens 'expr' into 'flattenedExpr'. Returns failure if 'expr' was unable to
 // be flattened (semi-affine expressions not handled yet).
 LogicalResult
 mlir::getFlattenedAffineExpr(AffineExpr expr, unsigned numDims,
                              unsigned numSymbols,
                              SmallVectorImpl<int64_t> *flattenedExpr,
-                             FlatAffineConstraints *localVarCst) {
+                             FlatAffineValueConstraints *localVarCst) {
   std::vector<SmallVector<int64_t, 8>> flattenedExprs;
   LogicalResult ret = ::getFlattenedAffineExprs({expr}, numDims, numSymbols,
                                                 &flattenedExprs, localVarCst);
   *flattenedExpr = flattenedExprs[0];
   return ret;
 }
 
 /// Flattens the expressions in map. Returns failure if 'expr' was unable to be
 /// flattened (i.e., semi-affine expressions not handled yet).
 LogicalResult mlir::getFlattenedAffineExprs(
     AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
-    FlatAffineConstraints *localVarCst) {
+    FlatAffineValueConstraints *localVarCst) {
   if (map.getNumResults() == 0) {
     localVarCst->reset(map.getNumDims(), map.getNumSymbols());
     return success();
   }
   return ::getFlattenedAffineExprs(map.getResults(), map.getNumDims(),
                                    map.getNumSymbols(), flattenedExprs,
                                    localVarCst);
 }
 
 LogicalResult mlir::getFlattenedAffineExprs(
     IntegerSet set, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
-    FlatAffineConstraints *localVarCst) {
+    FlatAffineValueConstraints *localVarCst) {
   if (set.getNumConstraints() == 0) {
     localVarCst->reset(set.getNumDims(), set.getNumSymbols());
     return success();
   }
   return ::getFlattenedAffineExprs(set.getConstraints(), set.getNumDims(),
                                    set.getNumSymbols(), flattenedExprs,
                                    localVarCst);
 }
 
 //===----------------------------------------------------------------------===//
 // FlatAffineConstraints / FlatAffineValueConstraints.
 //===----------------------------------------------------------------------===//
 
-// Clones this object.
-std::unique_ptr<FlatAffineConstraints> FlatAffineConstraints::clone() const {
-  return std::make_unique<FlatAffineConstraints>(*this);
-}
-
 std::unique_ptr<FlatAffineValueConstraints>
 FlatAffineValueConstraints::clone() const {
   return std::make_unique<FlatAffineValueConstraints>(*this);
 }
 
 // Construct from an IntegerSet.
-FlatAffineConstraints::FlatAffineConstraints(IntegerSet set)
+FlatAffineValueConstraints::FlatAffineValueConstraints(IntegerSet set)
     : IntegerPolyhedron(set.getNumInequalities(), set.getNumEqualities(),
                         set.getNumDims() + set.getNumSymbols() + 1,
                         PresburgerSpace::getSetSpace(set.getNumDims(),
                                                      set.getNumSymbols(),
                                                      /*numLocals=*/0)) {
 
+  // Resize values.
+  values.resize(getNumIds(), None);
+
   // Flatten expressions and add them to the constraint system.
   std::vector<SmallVector<int64_t, 8>> flatExprs;
-  FlatAffineConstraints localVarCst;
+  FlatAffineValueConstraints localVarCst;
   if (failed(getFlattenedAffineExprs(set, &flatExprs, &localVarCst))) {
     assert(false && "flattening unimplemented for semi-affine integer sets");
     return;
   }
   assert(flatExprs.size() == set.getNumConstraints());
-  appendLocalId(/*num=*/localVarCst.getNumLocalIds());
+  insertId(IdKind::Local, getNumIdKind(IdKind::Local),
+           /*num=*/localVarCst.getNumLocalIds());
 
   for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
     const auto &flatExpr = flatExprs[i];
     assert(flatExpr.size() == getNumCols());
     if (set.getEqFlags()[i]) {
       addEquality(flatExpr);
     } else {
       addInequality(flatExpr);
     }
   }
   // Add the other constraints involving local id's from flattening.
   append(localVarCst);
 }
 
-// Construct from an IntegerSet.
-FlatAffineValueConstraints::FlatAffineValueConstraints(IntegerSet set)
-    : FlatAffineConstraints(set) {
-  values.resize(getNumIds(), None);
-}
-
 // Construct a hyperrectangular constraint set from ValueRanges that represent
 // induction variables, lower and upper bounds. `ivs`, `lbs` and `ubs` are
 // expected to match one to one. The order of variables and constraints is:
 //
 // ivs | lbs | ubs | eq/ineq
 // ----+-----+-----+---------
 //   1   -1     0      >= 0
 // ----+-----+-----+---------
for (int ivIdx = 0, e = nIvs; ivIdx < e; ++ivIdx) {
     AffineMap ub = AffineMap::get(/*dimCount=*/3 * nIvs, /*symbolCount=*/0,
                                   getAffineDimExpr(ubsStart + ivIdx, ctx));
     if (failed(res.addBound(BoundType::UB, ivIdx, ub)))
       llvm_unreachable("Unexpected FlatAffineValueConstraints creation error");
   }
   return res;
 }
 
-void FlatAffineConstraints::reset(unsigned numReservedInequalities,
+void FlatAffineValueConstraints::reset(unsigned numReservedInequalities,
                                        unsigned numReservedEqualities,
                                        unsigned newNumReservedCols,
-                                  unsigned newNumDims, unsigned newNumSymbols,
+                                       unsigned newNumDims,
+                                       unsigned newNumSymbols,
                                        unsigned newNumLocals) {
   assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 &&
          "minimum 1 column");
-  *this = FlatAffineConstraints(numReservedInequalities, numReservedEqualities,
-                                newNumReservedCols, newNumDims, newNumSymbols,
-                                newNumLocals);
+  *this = FlatAffineValueConstraints(numReservedInequalities,
+                                     numReservedEqualities, newNumReservedCols,
+                                     newNumDims, newNumSymbols, newNumLocals);
 }
 
-void FlatAffineConstraints::reset(unsigned newNumDims, unsigned newNumSymbols,
+void FlatAffineValueConstraints::reset(unsigned newNumDims,
+                                       unsigned newNumSymbols,
                                        unsigned newNumLocals) {
   reset(/*numReservedInequalities=*/0, /*numReservedEqualities=*/0,
         /*numReservedCols=*/newNumDims + newNumSymbols + newNumLocals + 1,
         newNumDims, newNumSymbols, newNumLocals);
 }
 
-void FlatAffineValueConstraints::reset(unsigned numReservedInequalities,
-                                       unsigned numReservedEqualities,
-                                       unsigned newNumReservedCols,
-                                       unsigned newNumDims,
-                                       unsigned newNumSymbols,
-                                       unsigned newNumLocals) {
-  reset(numReservedInequalities, numReservedEqualities, newNumReservedCols,
-        newNumDims, newNumSymbols, newNumLocals, /*valArgs=*/{});
-}
-
 void FlatAffineValueConstraints::reset(
     unsigned numReservedInequalities, unsigned numReservedEqualities,
     unsigned newNumReservedCols, unsigned newNumDims, unsigned newNumSymbols,
     unsigned newNumLocals, ArrayRef<Value> valArgs) {
   assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 &&
          "minimum 1 column");
   SmallVector<Optional<Value>, 8> newVals;
   if (!valArgs.empty())

 
 unsigned FlatAffineValueConstraints::insertSymbolId(unsigned pos,
                                                     ValueRange vals) {
   return insertId(IdKind::Symbol, pos, vals);
 }
 
 unsigned FlatAffineValueConstraints::insertId(IdKind kind, unsigned pos,
                                               unsigned num) {
-  unsigned absolutePos = FlatAffineConstraints::insertId(kind, pos, num);
+  unsigned absolutePos = IntegerPolyhedron::insertId(kind, pos, num);
   values.insert(values.begin() + absolutePos, num, None);
   assert(values.size() == getNumIds());
   return absolutePos;
 }
 
 unsigned FlatAffineValueConstraints::insertId(IdKind kind, unsigned pos,
                                               ValueRange vals) {
   assert(!vals.empty() && "expected ValueRange with Values");
   unsigned num = vals.size();
-  unsigned absolutePos = FlatAffineConstraints::insertId(kind, pos, num);
+  unsigned absolutePos = IntegerPolyhedron::insertId(kind, pos, num);
 
   // If a Value is provided, insert it; otherwise use None.
   for (unsigned i = 0; i < num; ++i)
     values.insert(values.begin() + absolutePos + i,
                   vals[i] ? Optional<Value>(vals[i]) : None);
 
   assert(values.size() == getNumIds());
   return absolutePos;
for (Optional<Value> val : maybeValues) {
     if (val.hasValue() && !uniqueIds.insert(val.getValue()).second)
       return false;
   }
   return true;
 }
 
 /// Checks if the SSA values associated with `cst`'s identifiers are unique.
 static bool LLVM_ATTRIBUTE_UNUSED
-areIdsUnique(const FlatAffineConstraints &cst) {
+areIdsUnique(const FlatAffineValueConstraints &cst) {
   return areIdsUnique(cst, 0, cst.getNumIds());
 }
 
 /// Checks if the SSA values associated with `cst`'s identifiers of kind `kind`
 /// are unique.
 static bool LLVM_ATTRIBUTE_UNUSED
 areIdsUnique(const FlatAffineValueConstraints &cst, IdKind kind) {
 

 FlatAffineValueConstraints::composeMap(const AffineValueMap *vMap) {
   return composeMatchingMap(
       computeAlignedMap(vMap->getAffineMap(), vMap->getOperands()));
 }
 
 // Similar to `composeMap` except that no Values need be associated with the
 // constraint system nor are they looked at -- the dimensions and symbols of
 // `other` are expected to correspond 1:1 to `this` system.
-LogicalResult FlatAffineConstraints::composeMatchingMap(AffineMap other) {
+LogicalResult FlatAffineValueConstraints::composeMatchingMap(AffineMap other) {
   assert(other.getNumDims() == getNumDimIds() && "dim mismatch");
   assert(other.getNumSymbols() == getNumSymbolIds() && "symbol mismatch");
 
   std::vector<SmallVector<int64_t, 8>> flatExprs;
   if (failed(flattenAlignedMapAndMergeLocals(other, &flatExprs)))
     return failure();
   assert(flatExprs.size() == other.getNumResults());
 
void FlatAffineValueConstraints::addAffineIfOpDomain(AffineIfOp ifOp) {
   // Merge the constraints from ifOp to the current domain. We need first merge
   // and align the IDs from both constraints, and then append the constraints
   // from the ifOp into the current one.
   mergeAndAlignIdsWithOther(0, &cst);
   append(cst);
 }
 
 bool FlatAffineValueConstraints::hasConsistentState() const {
-  return FlatAffineConstraints::hasConsistentState() &&
+  return IntegerPolyhedron::hasConsistentState() &&
          values.size() == getNumIds();
 }
 
 void FlatAffineValueConstraints::removeIdRange(IdKind kind, unsigned idStart,
                                                unsigned idLimit) {
-  FlatAffineConstraints::removeIdRange(kind, idStart, idLimit);
+  IntegerPolyhedron::removeIdRange(kind, idStart, idLimit);
   unsigned offset = getIdKindOffset(kind);
   values.erase(values.begin() + idStart + offset,
                values.begin() + idLimit + offset);
 }
 
 // Determine whether the identifier at 'pos' (say id_r) can be expressed as
 // modulo of another known identifier (say id_n) w.r.t a constant. For example,
 // if the following constraints hold true:

 // Additionally, in a special case of the above constaints where `q_expr` is an
 // identifier itself that is not yet known (say `id_q`), it can be written as a
 // floordiv in the following way:
 //
 // `id_q = id_n floordiv divisor`.
 //
 // Returns true if the above mod or floordiv are detected, updating 'memo' with
 // these new expressions. Returns false otherwise.
-static bool detectAsMod(const FlatAffineConstraints &cst, unsigned pos,
+static bool detectAsMod(const FlatAffineValueConstraints &cst, unsigned pos,
                         int64_t lbConst, int64_t ubConst,
                         SmallVectorImpl<AffineExpr> &memo,
                         MLIRContext *context) {
   assert(pos < cst.getNumIds() && "invalid position");
 
   // Check if a divisor satisfying the condition `0 <= id_r <= divisor - 1` can
   // be determined.
   if (lbConst != 0 || ubConst < 1)
for (unsigned curEquality = 0, numEqualities = cst.getNumEqualities();
     // TODO: Handle AffineSymbolExpr as well. There is no reason to restrict it
     // to dims themselves.
     auto dimExpr = dividendExpr.dyn_cast<AffineDimExpr>();
     if (!dimExpr)
       continue;
 
     // Express `id_r` as `id_n % divisor` and store the expression in `memo`.
     if (quotientCount >= 1) {
-      auto ub = cst.getConstantBound(FlatAffineConstraints::BoundType::UB,
+      auto ub = cst.getConstantBound(FlatAffineValueConstraints::BoundType::UB,
                                      dimExpr.getPosition());
       // If `id_n` has an upperbound that is less than the divisor, mod can be
       // eliminated altogether.
       if (ub.hasValue() && ub.getValue() < divisor)
         memo[pos] = dimExpr;
       else
         memo[pos] = dimExpr % divisor;
       // If a unique quotient `id_q` was seen, it can be expressed as

 
 /// Check if the pos^th identifier can be expressed as a floordiv of an affine
 /// function of other identifiers (where the divisor is a positive constant)
 /// given the initial set of expressions in `exprs`. If it can be, the
 /// corresponding position in `exprs` is set as the detected affine expr. For
 /// eg: 4q <= i + j <= 4q + 3   <=>   q = (i + j) floordiv 4. An equality can
 /// also yield a floordiv: eg.  4q = i + j <=> q = (i + j) floordiv 4. 32q + 28
 /// <= i <= 32q + 31 => q = i floordiv 32.
-static bool detectAsFloorDiv(const FlatAffineConstraints &cst, unsigned pos,
-                             MLIRContext *context,
+static bool detectAsFloorDiv(const FlatAffineValueConstraints &cst,
+                             unsigned pos, MLIRContext *context,
                              SmallVectorImpl<AffineExpr> &exprs) {
   assert(pos < cst.getNumIds() && "invalid position");
 
   // Get upper-lower bound pair for this variable.
   SmallVector<bool, 8> foundRepr(cst.getNumIds(), false);
   for (unsigned i = 0, e = cst.getNumIds(); i < e; ++i)
     if (exprs[i])
       foundRepr[i] = true;
for (unsigned c = 0, f = cst.getNumIds(); c < f; c++)
     if (dividend[c] != 0)
       dividendExpr = dividendExpr + dividend[c] * exprs[c];
 
   // Successfully detected the floordiv.
   exprs[pos] = dividendExpr.floorDiv(divisor);
   return true;
 }
 
-std::pair<AffineMap, AffineMap> FlatAffineConstraints::getLowerAndUpperBound(
+std::pair<AffineMap, AffineMap>
+FlatAffineValueConstraints::getLowerAndUpperBound(
     unsigned pos, unsigned offset, unsigned num, unsigned symStartPos,
     ArrayRef<AffineExpr> localExprs, MLIRContext *context) const {
   assert(pos + offset < getNumDimIds() && "invalid dim start pos");
   assert(symStartPos >= (pos + offset) && "invalid sym start pos");
   assert(getNumLocalIds() == localExprs.size() &&
          "incorrect local exprs count");
 
   SmallVector<unsigned, 4> lbIndices, ubIndices, eqIndices;
FlatAffineValueConstraints::getLowerAndUpperBound(
   return {lbMap, ubMap};
 }
 
 /// Computes the lower and upper bounds of the first 'num' dimensional
 /// identifiers (starting at 'offset') as affine maps of the remaining
 /// identifiers (dimensional and symbolic identifiers). Local identifiers are
 /// themselves explicitly computed as affine functions of other identifiers in
 /// this process if needed.
-void FlatAffineConstraints::getSliceBounds(unsigned offset, unsigned num,
-                                           MLIRContext *context,
-                                           SmallVectorImpl<AffineMap> *lbMaps,
-                                           SmallVectorImpl<AffineMap> *ubMaps) {
+void FlatAffineValueConstraints::getSliceBounds(
+    unsigned offset, unsigned num, MLIRContext *context,
+    SmallVectorImpl<AffineMap> *lbMaps, SmallVectorImpl<AffineMap> *ubMaps) {
   assert(num < getNumDimIds() && "invalid range");
 
   // Basic simplification.
   normalizeConstraintsByGCD();
 
   LLVM_DEBUG(llvm::dbgs() << "getSliceBounds for first " << num
                           << " identifiers\n");
   LLVM_DEBUG(dump());
do {
     // This loop is guaranteed to reach a fixed point - since once an
     // identifier's explicit form is computed (in memo[pos]), it's not updated
     // again.
   } while (changed);
 
   // Set the lower and upper bound maps for all the identifiers that were
   // computed as affine expressions of the rest as the "detected expr" and
   // "detected expr + 1" respectively; set the undetected ones to null.
-  Optional<FlatAffineConstraints> tmpClone;
+  Optional<FlatAffineValueConstraints> tmpClone;
   for (unsigned pos = 0; pos < num; pos++) {
     unsigned numMapDims = getNumDimIds() - num;
     unsigned numMapSymbols = getNumSymbolIds();
     AffineExpr expr = memo[pos + offset];
     if (expr)
       expr = simplifyAffineExpr(expr, numMapDims, numMapSymbols);
 
     AffineMap &lbMap = (*lbMaps)[pos];
     AffineMap &ubMap = (*ubMaps)[pos];
 
     if (expr) {
       lbMap = AffineMap::get(numMapDims, numMapSymbols, expr);
       ubMap = AffineMap::get(numMapDims, numMapSymbols, expr + 1);
     } else {
       // TODO: Whenever there are local identifiers in the dependence
       // constraints, we'll conservatively over-approximate, since we don't
       // always explicitly compute them above (in the while loop).
       if (getNumLocalIds() == 0) {
         // Work on a copy so that we don't update this constraint system.
         if (!tmpClone) {
-          tmpClone.emplace(FlatAffineConstraints(*this));
+          tmpClone.emplace(FlatAffineValueConstraints(*this));
           // Removing redundant inequalities is necessary so that we don't get
           // redundant loop bounds.
           tmpClone->removeRedundantInequalities();
         }
         std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
             pos, offset, num, getNumDimIds(), /*localExprs=*/{}, context);
       }
 
LLVM_DEBUG(llvm::dbgs()
                << "lb map for pos = " << Twine(pos + offset) << ", expr: ");
     LLVM_DEBUG(lbMap.dump(););
     LLVM_DEBUG(llvm::dbgs()
                << "ub map for pos = " << Twine(pos + offset) << ", expr: ");
     LLVM_DEBUG(ubMap.dump(););
   }
 }
 
-LogicalResult FlatAffineConstraints::flattenAlignedMapAndMergeLocals(
+LogicalResult FlatAffineValueConstraints::flattenAlignedMapAndMergeLocals(
     AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs) {
-  FlatAffineConstraints localCst;
+  FlatAffineValueConstraints localCst;
   if (failed(getFlattenedAffineExprs(map, flattenedExprs, &localCst))) {
     LLVM_DEBUG(llvm::dbgs()
                << "composition unimplemented for semi-affine maps\n");
     return failure();
   }
 
   // Add localCst information.
   if (localCst.getNumLocalIds() > 0) {
     unsigned numLocalIds = getNumLocalIds();
     // Insert local dims of localCst at the beginning.
     insertLocalId(/*pos=*/0, /*num=*/localCst.getNumLocalIds());
     // Insert local dims of `this` at the end of localCst.
     localCst.appendLocalId(/*num=*/numLocalIds);
     // Dimensions of localCst and this constraint set match. Append localCst to
     // this constraint set.
     append(localCst);
   }
 
   return success();
 }
 
-LogicalResult FlatAffineConstraints::addBound(BoundType type, unsigned pos,
+LogicalResult FlatAffineValueConstraints::addBound(BoundType type, unsigned pos,
                                                    AffineMap boundMap) {
   assert(boundMap.getNumDims() == getNumDimIds() && "dim mismatch");
   assert(boundMap.getNumSymbols() == getNumSymbolIds() && "symbol mismatch");
   assert(pos < getNumDimAndSymbolIds() && "invalid position");
 
   // Equality follows the logic of lower bound except that we add an equality
   // instead of an inequality.
   assert((type != BoundType::EQ || boundMap.getNumResults() == 1) &&
          "single result expected");

 
 bool FlatAffineValueConstraints::containsId(Value val) const {
   return llvm::any_of(values, [&](const Optional<Value> &mayBeId) {
     return mayBeId.hasValue() && mayBeId.getValue() == val;
   });
 }
 
 void FlatAffineValueConstraints::swapId(unsigned posA, unsigned posB) {
-  FlatAffineConstraints::swapId(posA, posB);
+  IntegerPolyhedron::swapId(posA, posB);
   std::swap(values[posA], values[posB]);
 }
 
 void FlatAffineValueConstraints::addBound(BoundType type, Value val,
                                           int64_t value) {
   unsigned pos;
   if (!findId(val, &pos))
     // This is a pre-condition for this method.
     assert(0 && "id not found");
   addBound(type, pos, value);
 }
 
-void FlatAffineConstraints::printSpace(raw_ostream &os) const {
+void FlatAffineValueConstraints::printSpace(raw_ostream &os) const {
   IntegerPolyhedron::printSpace(os);
   os << "(";
   for (unsigned i = 0, e = getNumIds(); i < e; i++) {
-    if (auto *valueCstr = dyn_cast<const FlatAffineValueConstraints>(this)) {
-      if (valueCstr->hasValue(i))
-        os << "Value ";
-      else
-        os << "None ";
-    } else {
-      os << "None ";
-    }
+    if (hasValue(i))
   }
   os << " const)\n";
 }
 
-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<IntegerRelation *>(this) = other;
-}
-
 void FlatAffineValueConstraints::clearAndCopyFrom(
     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
+  } else {
     *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;
   newVals.reserve(getNumIds() - 1);
   newVals.append(values.begin(), values.begin() + pos);
   newVals.append(values.begin() + pos + 1, values.end());
   // Note: Base implementation discards all associated Values.
-  FlatAffineConstraints::fourierMotzkinEliminate(pos, darkShadow,
-                                                 isResultIntegerExact);
+  IntegerPolyhedron::fourierMotzkinEliminate(pos, darkShadow,
   values = newVals;
   assert(values.size() == getNumIds());
 }
 
 void FlatAffineValueConstraints::projectOut(Value val) {
   unsigned pos;
   bool ret = findId(val, &pos);
   assert(ret);
assert(otherCst.getMaybeValues()
          "dim values mismatch");
   assert(otherCst.getNumLocalIds() == 0 && "local ids not supported here");
   assert(getNumLocalIds() == 0 && "local ids not supported yet here");
 
   // Align `other` to this.
   if (!areIdsAligned(*this, otherCst)) {
     FlatAffineValueConstraints otherCopy(otherCst);
     mergeAndAlignIds(/*offset=*/getNumDimIds(), this, &otherCopy);
-    return FlatAffineConstraints::unionBoundingBox(otherCopy);
+    return IntegerPolyhedron::unionBoundingBox(otherCopy);
   }
 
-  return FlatAffineConstraints::unionBoundingBox(otherCst);
+  return IntegerPolyhedron::unionBoundingBox(otherCst);
 }
 
 /// Compute an explicit representation for local vars. For all systems coming
 /// from MLIR integer sets, maps, or expressions where local vars were
 /// introduced to model floordivs and mods, this always succeeds.
-static LogicalResult computeLocalVars(const FlatAffineConstraints &cst,
+static LogicalResult computeLocalVars(const FlatAffineValueConstraints &cst,
                                       SmallVectorImpl<AffineExpr> &memo,
                                       MLIRContext *context) {
   unsigned numDims = cst.getNumDimIds();
   unsigned numSyms = cst.getNumSymbolIds();
 
   // Initialize dimensional and symbolic identifiers.
   for (unsigned i = 0; i < numDims; i++)
     memo[i] = getAffineDimExpr(i, context);
void FlatAffineValueConstraints::getIneqAsAffineValueMap(
   SmallVector<Value, 4> operands;
   getValues(0, pos, &operands);
   SmallVector<Value, 4> trailingOperands;
   getValues(pos + 1, getNumDimAndSymbolIds(), &trailingOperands);
   operands.append(trailingOperands.begin(), trailingOperands.end());
   vmap.reset(AffineMap::get(numDims - 1, numSyms, boundExpr), operands);
 }
 
-IntegerSet FlatAffineConstraints::getAsIntegerSet(MLIRContext *context) const {
+IntegerSet
+FlatAffineValueConstraints::getAsIntegerSet(MLIRContext *context) const {
   if (getNumConstraints() == 0)
     // Return universal set (always true): 0 == 0.
     return IntegerSet::get(getNumDimIds(), getNumSymbolIds(),
                            getAffineConstantExpr(/*constant=*/0, context),
                            /*eqFlags=*/true);
 
   // Construct local references.
   SmallVector<AffineExpr, 8> memo(getNumIds(), AffineExpr());
void FlatAffineRelation::removeIdRange(IdKind kind, unsigned idStart,
   if (intersectRangeLHS > intersectRangeRHS)
     numRangeDims -= intersectRangeLHS - intersectRangeRHS;
 }
 
 LogicalResult mlir::getRelationFromMap(AffineMap &map,
                                        FlatAffineRelation &rel) {
   // Get flattened affine expressions.
   std::vector<SmallVector<int64_t, 8>> flatExprs;
-  FlatAffineConstraints localVarCst;
+  FlatAffineValueConstraints localVarCst;
   if (failed(getFlattenedAffineExprs(map, &flatExprs, &localVarCst)))
     return failure();
 
   unsigned oldDimNum = localVarCst.getNumDimIds();
   unsigned oldCols = localVarCst.getNumCols();
   unsigned numRangeIds = map.getNumResults();
   unsigned numDomainIds = map.getNumDims();
 

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

ComputationSliceState::getAsConstraints(FlatAffineValueConstraints *cst) {
   // Add loop bound constraints for values which are loop IVs of the destination
   // of fusion and equality constraints for symbols which are constants.
   for (unsigned i = numDims, end = values.size(); i < end; ++i) {
     Value value = values[i];
     assert(cst->containsId(value) && "value expected to be present");
     if (isValidSymbol(value)) {
       // Check if the symbol is a constant.
       if (auto cOp = value.getDefiningOp<arith::ConstantIndexOp>())
-        cst->addBound(FlatAffineConstraints::EQ, value, cOp.value());
+        cst->addBound(FlatAffineValueConstraints::EQ, value, cOp.value());
     } else if (auto loop = getForInductionVarOwner(value)) {
       if (failed(cst->addAffineForOpDomain(loop)))
         return failure();
     }
   }
 
   // Add slices bounds on 'ivs' using maps 'lbs'/'ubs' with 'lbOperands[0]'
   LogicalResult ret = cst->addSliceBounds(ivs, lbs, ubs, lbOperands[0]);
Optional<int64_t> MemRefRegion::getConstantBoundingSizeAndShape(
 
   assert(rank == cst.getNumDimIds() && "inconsistent memref region");
 
   // Use a copy of the region constraints that has upper/lower bounds for each
   // memref dimension with static size added to guard against potential
   // over-approximation from projection or union bounding box. We may not add
   // this on the region itself since they might just be redundant constraints
   // that will need non-trivials means to eliminate.
-  FlatAffineConstraints cstWithShapeBounds(cst);
+  FlatAffineValueConstraints cstWithShapeBounds(cst);
   for (unsigned r = 0; r < rank; r++) {
-    cstWithShapeBounds.addBound(FlatAffineConstraints::LB, r, 0);
+    cstWithShapeBounds.addBound(FlatAffineValueConstraints::LB, r, 0);
     int64_t dimSize = memRefType.getDimSize(r);
     if (ShapedType::isDynamic(dimSize))
       continue;
-    cstWithShapeBounds.addBound(FlatAffineConstraints::UB, r, dimSize - 1);
+    cstWithShapeBounds.addBound(FlatAffineValueConstraints::UB, r, dimSize - 1);
   }
 
   // Find a constant upper bound on the extent of this memref region along each
   // dimension.
   int64_t numElements = 1;
   int64_t diffConstant;
   int64_t lbDivisor;
   for (unsigned d = 0; d < rank; d++) {

 //
 //    affine.for %i = 0 to 32 {
 //      affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
 //        load %A[%ii]
 //      }
 //    }
 //
 // region:  {memref = %A, write = false, {%i <= m0 <= %i + 7} }
-// The last field is a 2-d FlatAffineConstraints symbolic in %i.
+// The last field is a 2-d FlatAffineValueConstraints symbolic in %i.
 //
 // TODO: extend this to any other memref dereferencing ops
 // (dma_start, dma_wait).
 LogicalResult MemRefRegion::compute(Operation *op, unsigned loopDepth,
                                     const ComputationSliceState *sliceState,
                                     bool addMemRefDimBounds) {
   assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
          "affine read/write op expected");
if (auto loop = getForInductionVarOwner(operand)) {
         return failure();
     } else {
       // Has to be a valid symbol.
       auto symbol = operand;
       assert(isValidSymbol(symbol));
       // Check if the symbol is a constant.
       if (auto *op = symbol.getDefiningOp()) {
         if (auto constOp = dyn_cast<arith::ConstantIndexOp>(op)) {
-          cst.addBound(FlatAffineConstraints::EQ, symbol, constOp.value());
+          cst.addBound(FlatAffineValueConstraints::EQ, symbol, constOp.value());
         }
       }
     }
   }
 
   // Add lower/upper bounds on loop IVs using bounds from 'sliceState'.
   if (sliceState != nullptr) {
     // Add dim and symbol slice operands.
LogicalResult MemRefRegion::compute(Operation *op, unsigned loopDepth,
   assert(cst.getNumDimIds() == rank && "unexpected MemRefRegion format");
 
   // Add upper/lower bounds for each memref dimension with static size
   // to guard against potential over-approximation from projection.
   // TODO: Support dynamic memref dimensions.
   if (addMemRefDimBounds) {
     auto memRefType = memref.getType().cast<MemRefType>();
     for (unsigned r = 0; r < rank; r++) {
-      cst.addBound(FlatAffineConstraints::LB, /*pos=*/r, /*value=*/0);
+      cst.addBound(FlatAffineValueConstraints::LB, /*pos=*/r, /*value=*/0);
       if (memRefType.isDynamicDim(r))
         continue;
-      cst.addBound(FlatAffineConstraints::UB, /*pos=*/r,
+      cst.addBound(FlatAffineValueConstraints::UB, /*pos=*/r,
                    memRefType.getDimSize(r) - 1);
     }
   }
   cst.removeTrivialRedundancy();
 
   LLVM_DEBUG(llvm::dbgs() << "Memory region:\n");
   LLVM_DEBUG(cst.dump());
   return success();
LogicalResult mlir::boundCheckLoadOrStoreOp(LoadOrStoreOp loadOrStoreOp,
   LLVM_DEBUG(llvm::dbgs() << "Memory region");
   LLVM_DEBUG(region.getConstraints()->dump());
 
   bool outOfBounds = false;
   unsigned rank = loadOrStoreOp.getMemRefType().getRank();
 
   // For each dimension, check for out of bounds.
   for (unsigned r = 0; r < rank; r++) {
-    FlatAffineConstraints ucst(*region.getConstraints());
+    FlatAffineValueConstraints ucst(*region.getConstraints());
 
     // Intersect memory region with constraint capturing out of bounds (both out
     // of upper and out of lower), and check if the constraint system is
     // feasible. If it is, there is at least one point out of bounds.
     SmallVector<int64_t, 4> ineq(rank + 1, 0);
     int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
     // TODO: handle dynamic dim sizes.
     if (dimSize == -1)
       continue;
 
     // Check for overflow: d_i >= memref dim size.
-    ucst.addBound(FlatAffineConstraints::LB, r, dimSize);
+    ucst.addBound(FlatAffineValueConstraints::LB, r, dimSize);
     outOfBounds = !ucst.isEmpty();
     if (outOfBounds && emitError) {
       loadOrStoreOp.emitOpError()
           << "memref out of upper bound access along dimension #" << (r + 1);
     }
 
     // Check for a negative index.
-    FlatAffineConstraints lcst(*region.getConstraints());
+    FlatAffineValueConstraints lcst(*region.getConstraints());
     std::fill(ineq.begin(), ineq.end(), 0);
     // d_i <= -1;
-    lcst.addBound(FlatAffineConstraints::UB, r, -1);
+    lcst.addBound(FlatAffineValueConstraints::UB, r, -1);
     outOfBounds = !lcst.isEmpty();
     if (outOfBounds && emitError) {
       loadOrStoreOp.emitOpError()
           << "memref out of lower bound access along dimension #" << (r + 1);
     }
   }
   return failure(outOfBounds);
 }
void mlir::getSequentialLoops(AffineForOp forOp,
   forOp->walk([&](Operation *op) {
     if (auto innerFor = dyn_cast<AffineForOp>(op))
       if (!isLoopParallel(innerFor))
         sequentialLoops->insert(innerFor.getInductionVar());
   });
 }
 
 IntegerSet mlir::simplifyIntegerSet(IntegerSet set) {
-  FlatAffineConstraints fac(set);
+  FlatAffineValueConstraints fac(set);
   if (fac.isEmpty())
     return IntegerSet::getEmptySet(set.getNumDims(), set.getNumSymbols(),
                                    set.getContext());
   fac.removeTrivialRedundancy();
 
   auto simplifiedSet = fac.getAsIntegerSet(set.getContext());
   assert(simplifiedSet && "guaranteed to succeed while roundtripping");
   return simplifiedSet;
 }

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

 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "LoopUtils"
 
 using namespace mlir;
+using namespace presburger;
 using llvm::SmallMapVector;
 
 namespace {
 // This structure is to pass and return sets of loop parameters without
 // confusing the order.
 struct LoopParams {
   Value lowerBound;
   Value upperBound;
static bool getFullMemRefAsRegion(Operation *op, unsigned numParamLoopIVs,
   extractForInductionVars(ivs, &symbols);
   regionCst->reset(rank, numParamLoopIVs, 0);
   regionCst->setValues(rank, rank + numParamLoopIVs, symbols);
 
   // Memref dim sizes provide the bounds.
   for (unsigned d = 0; d < rank; d++) {
     auto dimSize = memRefType.getDimSize(d);
     assert(dimSize > 0 && "filtered dynamic shapes above");
-    regionCst->addBound(FlatAffineConstraints::LB, d, 0);
-    regionCst->addBound(FlatAffineConstraints::UB, d, dimSize - 1);
+    regionCst->addBound(IntegerPolyhedron::LB, d, 0);
+    regionCst->addBound(IntegerPolyhedron::UB, d, dimSize - 1);
   }
   return true;
 }
 
 LogicalResult mlir::affineDataCopyGenerate(Block::iterator begin,
                                            Block::iterator end,
                                            const AffineCopyOptions &copyOptions,
                                            Optional<Value> filterMemRef,

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

 #include "mlir/IR/BlockAndValueMapping.h"
 #include "mlir/IR/Dominance.h"
 #include "mlir/IR/IntegerSet.h"
 #include "mlir/Transforms/GreedyPatternRewriteDriver.h"
 
 #define DEBUG_TYPE "affine-utils"
 
 using namespace mlir;
+using namespace presburger;
 
 namespace {
 /// Visit affine expressions recursively and build the sequence of operations
 /// that correspond to it.  Visitation functions return an Value of the
 /// expression subtree they visited or `nullptr` on error.
 class AffineApplyExpander
     : public AffineExprVisitor<AffineApplyExpander, Value> {
 public:
MemRefType mlir::normalizeMemRefType(MemRefType memrefType, OpBuilder b,
   SmallVector<std::tuple<AffineExpr, unsigned, unsigned>> tileSizePos;
   (void)getTileSizePos(layoutMap, tileSizePos);
   if (memrefType.getNumDynamicDims() > 0 && tileSizePos.empty())
     return memrefType;
 
   // We have a single map that is not an identity map. Create a new memref
   // with the right shape and an identity layout map.
   ArrayRef<int64_t> shape = memrefType.getShape();
-  // FlatAffineConstraint may later on use symbolicOperands.
-  FlatAffineConstraints fac(rank, numSymbolicOperands);
+  // FlatAffineValueConstraint may later on use symbolicOperands.
+  FlatAffineValueConstraints fac(rank, numSymbolicOperands);
   SmallVector<unsigned, 4> memrefTypeDynDims;
   for (unsigned d = 0; d < rank; ++d) {
     // Use constraint system only in static dimensions.
     if (shape[d] > 0) {
-      fac.addBound(FlatAffineConstraints::LB, d, 0);
-      fac.addBound(FlatAffineConstraints::UB, d, shape[d] - 1);
+      fac.addBound(IntegerPolyhedron::LB, d, 0);
+      fac.addBound(IntegerPolyhedron::UB, d, shape[d] - 1);
     } else {
       memrefTypeDynDims.emplace_back(d);
     }
   }
   // We compose this map with the original index (logical) space to derive
   // the upper bounds for the new index space.
   unsigned newRank = layoutMap.getNumResults();
   if (failed(fac.composeMatchingMap(layoutMap)))
     return memrefType;
   // TODO: Handle semi-affine maps.
   // Project out the old data dimensions.
   fac.projectOut(newRank, fac.getNumIds() - newRank - fac.getNumLocalIds());
   SmallVector<int64_t, 4> newShape(newRank);
   for (unsigned d = 0; d < newRank; ++d) {
     // Check if each dimension of normalized memrefType is dynamic.
     bool isDynDim = isNormalizedMemRefDynamicDim(
         d, layoutMap, memrefTypeDynDims, b.getContext());
     if (isDynDim) {
       newShape[d] = -1;
     } else {
       // The lower bound for the shape is always zero.
-      auto ubConst = fac.getConstantBound(FlatAffineConstraints::UB, d);
+      auto ubConst = fac.getConstantBound(IntegerPolyhedron::UB, d);
       // For a static memref and an affine map with no symbols, this is
       // always bounded.
       assert(ubConst.hasValue() && "should always have an upper bound");
       if (ubConst.getValue() < 0)
         // This is due to an invalid map that maps to a negative space.
         return memrefType;
       // If dimension of new memrefType is dynamic, the value is -1.
       newShape[d] = ubConst.getValue() + 1;

mlir/lib/Dialect/Linalg/Utils/Utils.cpp

 #include "mlir/IR/OpImplementation.h"
 #include "mlir/Pass/Pass.h"
 #include "llvm/ADT/TypeSwitch.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "linalg-utils"
 
 using namespace mlir;
+using namespace presburger;
 using namespace mlir::linalg;
 using namespace mlir::scf;
 
 static bool isZero(Value v) {
   if (auto cst = v.getDefiningOp<arith::ConstantIndexOp>())
     return cst.value() == 0;
   return false;
 }
if (auto applyOp = dyn_cast<AffineApplyOp>(op)) {
       if (failed(constraints.composeMap(&valueMap)))
         return;
       continue;
     }
     // Add AffineMinOps to the constraints.
     auto minOp = cast<AffineMinOp>(op);
     AffineMap map = constraints.computeAlignedMap(minOp.getAffineMap(),
                                                   minOp.getOperands());
-    if (failed(constraints.addBound(FlatAffineConstraints::UB,
+    if (failed(constraints.addBound(IntegerPolyhedron::UB,
                                     getPosition(minOp.getResult()), map)))
       return;
   }
 
   // Obtain an upper bound for the affine index computation by projecting out
   // all temporary results and expressing the upper bound for `value` in terms
   // of the terminals of the index computation.
   SmallVector<AffineMap> lowerBounds(1), upperBounds(1);

mlir/lib/Dialect/SCF/Utils/AffineCanonicalizationUtils.cpp

 #include "mlir/IR/AffineMap.h"
 #include "mlir/IR/Matchers.h"
 #include "mlir/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "mlir-scf-affine-utils"
 
 using namespace mlir;
+using namespace presburger;
 
 static void unpackOptionalValues(ArrayRef<Optional<Value>> source,
                                  SmallVector<Value> &target) {
   target = llvm::to_vector<4>(llvm::map_range(source, [](Optional<Value> val) {
     return val.hasValue() ? *val : Value();
   }));
 }
 
 /// Bound an identifier `pos` in a given FlatAffineValueConstraints with
 /// constraints drawn from an affine map. Before adding the constraint, the
 /// dimensions/symbols of the affine map are aligned with `constraints`.
 /// `operands` are the SSA Value operands used with the affine map.
 /// Note: This function adds a new symbol column to the `constraints` for each
 /// dimension/symbol that exists in the affine map but not in `constraints`.
 static LogicalResult alignAndAddBound(FlatAffineValueConstraints &constraints,
-                                      FlatAffineConstraints::BoundType type,
+                                      IntegerPolyhedron::BoundType type,
                                       unsigned pos, AffineMap map,
                                       ValueRange operands) {
   SmallVector<Value> dims, syms, newSyms;
   unpackOptionalValues(constraints.getMaybeDimValues(), dims);
   unpackOptionalValues(constraints.getMaybeSymbolValues(), syms);
 
   AffineMap alignedMap =
       alignAffineMapWithValues(map, operands, dims, syms, &newSyms);
canonicalizeMinMaxOp(RewriterBase &rewriter, Operation *op, AffineMap map,
 
   // Add a few extra dimensions.
   unsigned dimOp = constraints.appendDimId();      // `op`
   unsigned dimOpBound = constraints.appendDimId(); // `op` lower/upper bound
   unsigned resultDimStart = constraints.appendDimId(/*num=*/numResults);
 
   // Add an inequality for each result expr_i of map:
   // isMin: op <= expr_i, !isMin: op >= expr_i
-  auto boundType =
-      isMin ? FlatAffineConstraints::UB : FlatAffineConstraints::LB;
+  auto boundType = isMin ? IntegerPolyhedron::UB : IntegerPolyhedron::LB;
   // Upper bounds are exclusive, so add 1. (`affine.min` ops are inclusive.)
   AffineMap mapLbUb = isMin ? addConstToResults(map, 1) : map;
   if (failed(
           alignAndAddBound(constraints, boundType, dimOp, mapLbUb, operands)))
     return failure();
 
   // Try to compute a lower/upper bound for op, expressed in terms of the other
   // `dims` and extra symbols.
   SmallVector<AffineMap> opLb(1), opUb(1);
   constraints.getSliceBounds(dimOp, 1, rewriter.getContext(), &opLb, &opUb);
   AffineMap sliceBound = isMin ? opUb[0] : opLb[0];
   // TODO: `getSliceBounds` may return multiple bounds at the moment. This is
   // a TODO of `getSliceBounds` and not handled here.
   if (!sliceBound || sliceBound.getNumResults() != 1)
     return failure(); // No or multiple bounds found.
   // Recover the inclusive UB in the case of an `affine.min`.
   AffineMap boundMap = isMin ? addConstToResults(sliceBound, -1) : sliceBound;
 
   // Add an equality: Set dimOpBound to computed bound.
   // Add back dimension for op. (Was removed by `getSliceBounds`.)
   AffineMap alignedBoundMap = boundMap.shiftDims(/*shift=*/1, /*offset=*/dimOp);
-  if (failed(constraints.addBound(FlatAffineConstraints::EQ, dimOpBound,
+  if (failed(constraints.addBound(IntegerPolyhedron::EQ, dimOpBound,
                                   alignedBoundMap)))
     return failure();
 
   // If the constraint system is empty, there is an inconsistency. (E.g., this
   // can happen if loop lb > ub.)
   if (constraints.isEmpty())
     return failure();
 
canonicalizeMinMaxOp(RewriterBase &rewriter, Operation *op, AffineMap map,
   // that the constraint set is empty.
   for (unsigned i = resultDimStart; i < resultDimStart + numResults; ++i) {
     FlatAffineValueConstraints newConstr(constraints);
 
     // Add an equality: r_i = expr_i
     // Note: These equalities could have been added earlier and used to express
     // minOp <= expr_i. However, then we run the risk that `getSliceBounds`
     // computes minOpUb in terms of r_i dims, which is not desired.
-    if (failed(alignAndAddBound(newConstr, FlatAffineConstraints::EQ, i,
+    if (failed(alignAndAddBound(newConstr, IntegerPolyhedron::EQ, i,
                                 map.getSubMap({i - resultDimStart}), operands)))
       return failure();
 
     // If `isMin`:  Add inequality: r_i < opBound
     //              equiv.: opBound - r_i - 1 >= 0
     // If `!isMin`: Add inequality: r_i > opBound
     //              equiv.: -opBound + r_i - 1 >= 0
     SmallVector<int64_t> ineq(newConstr.getNumCols(), 0);
canonicalizeMinMaxOp(RewriterBase &rewriter, Operation *op, AffineMap map,
   SmallVector<Value> newOperands;
   unpackOptionalValues(constraints.getMaybeDimAndSymbolValues(), newOperands);
   // If dims/symbols have known constant values, use those in order to simplify
   // the affine map further.
   for (int64_t i = 0, e = constraints.getNumIds(); i < e; ++i) {
     // Skip unused operands and operands that are already constants.
     if (!newOperands[i] || getConstantIntValue(newOperands[i]))
       continue;
-    if (auto bound = constraints.getConstantBound(FlatAffineConstraints::EQ, i))
+    if (auto bound = constraints.getConstantBound(IntegerPolyhedron::EQ, i))
       newOperands[i] =
           rewriter.create<arith::ConstantIndexOp>(op->getLoc(), *bound);
   }
   mlir::canonicalizeMapAndOperands(&newMap, &newOperands);
   rewriter.setInsertionPoint(op);
   rewriter.replaceOpWithNewOp<AffineApplyOp>(op, newMap, newOperands);
   return success();
 }
 
 static LogicalResult
 addLoopRangeConstraints(FlatAffineValueConstraints &constraints, Value iv,
                         Value lb, Value ub, Value step,
                         RewriterBase &rewriter) {
-  // FlatAffineConstraints does not support semi-affine expressions.
+  // IntegerPolyhedron does not support semi-affine expressions.
   // Therefore, only constant step values are supported.
   auto stepInt = getConstantIntValue(step);
   if (!stepInt)
     return failure();
 
   unsigned dimIv = constraints.appendDimId(iv);
   unsigned dimLb = constraints.appendDimId(lb);
   unsigned dimUb = constraints.appendDimId(ub);
 
   // If loop lower/upper bounds are constant: Add EQ constraint.
   Optional<int64_t> lbInt = getConstantIntValue(lb);
   Optional<int64_t> ubInt = getConstantIntValue(ub);
   if (lbInt)
-    constraints.addBound(FlatAffineConstraints::EQ, dimLb, *lbInt);
+    constraints.addBound(IntegerPolyhedron::EQ, dimLb, *lbInt);
   if (ubInt)
-    constraints.addBound(FlatAffineConstraints::EQ, dimUb, *ubInt);
+    constraints.addBound(IntegerPolyhedron::EQ, dimUb, *ubInt);
 
   // Lower bound: iv >= lb (equiv.: iv - lb >= 0)
   SmallVector<int64_t> ineqLb(constraints.getNumCols(), 0);
   ineqLb[dimIv] = 1;
   ineqLb[dimLb] = -1;
   constraints.addInequality(ineqLb);
 
   // Upper bound
if (lbInt && ubInt && (*lbInt + *stepInt >= *ubInt)) {
     AffineExpr exprUb = ubInt ? rewriter.getAffineConstantExpr(*ubInt)
                               : rewriter.getAffineDimExpr(dimUb);
     ivUb = exprLb + 1 + (*stepInt * ((exprUb - exprLb - 1).floorDiv(*stepInt)));
   }
   auto map = AffineMap::get(
       /*dimCount=*/constraints.getNumDimIds(),
       /*symbolCount=*/constraints.getNumSymbolIds(), /*result=*/ivUb);
 
-  return constraints.addBound(FlatAffineConstraints::UB, dimIv, map);
+  return constraints.addBound(IntegerPolyhedron::UB, dimIv, map);
 }
 
 /// Canonicalize min/max operations in the context of for loops with a known
 /// range. Call `canonicalizeMinMaxOp` and add the following constraints to
 /// the constraint system (along with the missing dimensions):
 ///
 /// * iv >= lb
 /// * iv < lb + step * ((ub - lb - 1) floorDiv step) + 1
 ///
-/// Note: Due to limitations of FlatAffineConstraints, only constant step sizes
+/// Note: Due to limitations of IntegerPolyhedron, only constant step sizes
 /// are currently supported.
 LogicalResult scf::canonicalizeMinMaxOpInLoop(RewriterBase &rewriter,
                                               Operation *op, AffineMap map,
                                               ValueRange operands, bool isMin,
                                               LoopMatcherFn loopMatcher) {
   FlatAffineValueConstraints constraints;
   DenseSet<Value> allIvs;
 

 /// parameters, see comment of `canonicalizeMinMaxOpInLoop`.
 LogicalResult scf::rewritePeeledMinMaxOp(RewriterBase &rewriter, Operation *op,
                                          AffineMap map, ValueRange operands,
                                          bool isMin, Value iv, Value ub,
                                          Value step, bool insideLoop) {
   FlatAffineValueConstraints constraints;
   constraints.appendDimId({iv, ub, step});
   if (auto constUb = getConstantIntValue(ub))
-    constraints.addBound(FlatAffineConstraints::EQ, 1, *constUb);
+    constraints.addBound(IntegerPolyhedron::EQ, 1, *constUb);
   if (auto constStep = getConstantIntValue(step))
-    constraints.addBound(FlatAffineConstraints::EQ, 2, *constStep);
+    constraints.addBound(IntegerPolyhedron::EQ, 2, *constStep);
 
   // Add loop peeling invariant. This is the main piece of knowledge that
   // enables AffineMinOp simplification.
   if (insideLoop) {
     // ub - iv >= step (equiv.: -iv + ub - step + 0 >= 0)
     // Intuitively: Inside the peeled loop, every iteration is a "full"
     // iteration, i.e., step divides the iteration space `ub - lb` evenly.
     constraints.addInequality({-1, 1, -1, 0});

mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParser.h

 #define MLIR_UNITTEST_ANALYSIS_AFFINESTRUCTURESPARSER_H
 
 #include "mlir/Dialect/Affine/Analysis/AffineStructures.h"
 #include "mlir/Support/LogicalResult.h"
 
 namespace mlir {
 
 /// This parses a single IntegerSet to an MLIR context and transforms it to
-/// FlatAffineConstraints if it was valid. If not, a failure is returned. If the
+/// IntegerPolyhedron if it was valid. If not, a failure is returned. If the
 /// passed `str` has additional tokens that were not part of the IntegerSet, a
 /// failure is returned. Diagnostics are printed on failure if
 /// `printDiagnosticInfo` is true.
 
-FailureOr<FlatAffineConstraints>
+FailureOr<presburger::IntegerPolyhedron>
 parseIntegerSetToFAC(llvm::StringRef, MLIRContext *context,
                      bool printDiagnosticInfo = true);
 
 } // namespace mlir
 
 #endif // MLIR_UNITTEST_ANALYSIS_AFFINESTRUCTURESPARSER_H

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

 //===- AffineStructuresParser.cpp - Parser for AffineStructures -*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "./AffineStructuresParser.h"
 #include "mlir/IR/IntegerSet.h"
 #include "mlir/Parser/Parser.h"
 
 using namespace mlir;
+using namespace presburger;
 
-FailureOr<FlatAffineConstraints>
+FailureOr<IntegerPolyhedron>
 mlir::parseIntegerSetToFAC(llvm::StringRef str, MLIRContext *context,
                            bool printDiagnosticInfo) {
   IntegerSet set = parseIntegerSet(str, context, printDiagnosticInfo);
 
   if (!set)
     return failure();
 
-  return FlatAffineConstraints(set);
+  return FlatAffineValueConstraints(set);
 }

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

 //===- AffineStructuresParserTest.cpp - FAC parsing unit tests --*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// This file contains tests for parsing IntegerSets to FlatAffineConstraints.
+// This file contains tests for parsing IntegerSets to IntegerPolyhedron.
 // The tests with invalid input check that the parser only accepts well-formed
 // IntegerSets. The tests with well-formed input compare the returned FACs to
 // manually constructed FACs with a PresburgerSet equality check.
 //
 //===----------------------------------------------------------------------===//
 
 #include "./AffineStructuresParser.h"
 #include "mlir/Analysis/Presburger/PresburgerRelation.h"
 
 #include <gtest/gtest.h>
 
 using namespace mlir;
 using namespace presburger;
 
-/// Construct a FlatAffineConstraints from a set of inequality, equality, and
+/// Construct a IntegerPolyhedron from a set of inequality, equality, and
 /// division onstraints.
-static FlatAffineConstraints makeFACFromConstraints(
+static IntegerPolyhedron makeFACFromConstraints(
     unsigned dims, unsigned syms, ArrayRef<SmallVector<int64_t, 4>> ineqs,
     ArrayRef<SmallVector<int64_t, 4>> eqs = {},
     ArrayRef<std::pair<SmallVector<int64_t, 4>, int64_t>> divs = {}) {
-  FlatAffineConstraints fac(ineqs.size(), eqs.size(), dims + syms + 1, dims,
-                            syms, 0);
+  IntegerPolyhedron fac(ineqs.size(), eqs.size(), dims + syms + 1,
+                        PresburgerSpace::getSetSpace(dims, syms, 0));
   for (const auto &div : divs)
     fac.addLocalFloorDiv(div.first, div.second);
   for (const auto &eq : eqs)
     fac.addEquality(eq);
   for (const auto &ineq : ineqs)
     fac.addInequality(ineq);
   return fac;
 }
 
 TEST(ParseFACTest, InvalidInputTest) {
   MLIRContext context;
-  FailureOr<FlatAffineConstraints> fac;
+  FailureOr<IntegerPolyhedron> fac;
 
   fac = parseIntegerSetToFAC("(x)", &context, false);
   EXPECT_TRUE(failed(fac))
       << "should not accept strings with no constraint list";
 
   fac = parseIntegerSetToFAC("(x)[] : ())", &context, false);
   EXPECT_TRUE(failed(fac))
       << "should not accept strings that contain remaining characters";
TEST(ParseFACTest, InvalidInputTest) {
   fac = parseIntegerSetToFAC("(x) : (2 * x + 9223372036854775808 >= 0)",
                              &context, false);
   EXPECT_TRUE(failed(fac)) << "should not accept strings with integer literals "
                               "that do not fit into int64_t";
 }
 
 /// Parses and compares the `str` to the `ex`. The equality check is performed
 /// by using PresburgerSet::isEqual
-static bool parseAndCompare(StringRef str, const FlatAffineConstraints &ex,
+static bool parseAndCompare(StringRef str, const IntegerPolyhedron &ex,
                             MLIRContext *context) {
-  FailureOr<FlatAffineConstraints> fac = parseIntegerSetToFAC(str, context);
+  FailureOr<IntegerPolyhedron> fac = parseIntegerSetToFAC(str, context);
 
   EXPECT_TRUE(succeeded(fac));
 
   return PresburgerSet(*fac).isEqual(PresburgerSet(ex));
 }
 
 TEST(ParseFACTest, ParseAndCompareTest) {
   MLIRContext context;