[mlir][Analysis][NFC] Split FlatAffineConstraints class

[springerm]

Summary

• Extract "value" functionality of FlatAffineConstraints into a new derived FlatAffineValueConstraints class. Current users of FlatAffineConstraints can use FlatAffineValueConstraints without additional code changes, thus NFC.
• FlatAffineConstraints no longer associates dimensions with SSA Values. All functionality that requires this, is moved to FlatAffineValueConstraints.
• FlatAffineConstraints no longer makes assumptions about where Values associated with dimensions are coming from.

Depends On: D107814

[springerm]

mlir/include/mlir/Analysis/AffineStructures.h

665–671

I changed this comment a bit. Is it correct?

mlir/lib/Analysis/AffineStructures.cpp

2647–2666

Is this good?

[ftynse]

Generally looks good, two high-level comments:

1. Keeping the notion of "id" or "identifier" in the (new) FlatAffineConstraints class sounds misleading, "id" is a Value and the base class should be free of this concern. For naming purposes, I suppose we can call the generalization of "dimension" and "symbol" a variable, so we have a system of constraints on variables which can be dimensions, symbols or local variables. Since we know it's a flat list of constraints, we can also use "column" to refer to coefficients for each variable in all constraints.
2. We shouldn't use RTTI / dynamic_cast. Thinking about this more, now that you looked at all the users of FlatAffineConstraints, do you think we actually need inheritance? That is, do we have a lot of functions that take a pointer/reference to FlatAffineConstraints and are expected to work transparently on FlatAffineValueConstraints? If not, we may also consider FlatAffineValueConstraints to contain FlatValueConstraints instead of deriving it. The former can expose a const reference accessors to constraints if necessary. This is the approach AffineValueMap uses, by the way, so it can also have the consistency argument.

mlir/include/mlir/Analysis/AffineStructures.h

246–247

I was surprised that we still have something with "Id" in the name at the FlatAffineConstraints level since it is not supposed to have IDs anymore. Actually, this just swaps the coefficients associated with dimensions or symbols identified by their (absolute) position. Maybe we can rename this to swapColumns or something similar?

247–250

Ideally, we would drop the notion of "Id" from this class entirely, it will only create confusion otherwise. addDim and addSymbol are fine, addId can become addColumn.

665

mlir/lib/Analysis/AffineStructures.cpp

281–282

The "dimensional identifier" part looks incorrect on a generic addId, it's not necessarily a dimension but a column of the specified kind.

2647–2666

Nope. LLVM must build without RTTI. If necessary, we can set this up to use LLVM's dyn_cast mechanism - https://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html - but with MLIR-style TypeID instead of fixed enum.

[springerm]

In D107725#2934613, @ftynse wrote:

Thinking about this more, now that you looked at all the users of FlatAffineConstraints, do you think we actually need inheritance? That is, do we have a lot of functions that take a pointer/reference to FlatAffineConstraints and are expected to work transparently on FlatAffineValueConstraints?

There is one that comes to mind: getFlattenedAffineExprs. E.g., it takes a FlatAffineConstraints in FlatAffineConstraints::composeMatchingMap and a FlatAffineValueConstraints in FlatAffineValueConstraints::addLowerOrUpperBound and FlatAffineValueConstraints::composeMap. But I think I can reimplement composeMap in terms of composeMatchingMap, similar to addLowerOrUpperBound in D107729, so that getFlattenedAffineExprs is always called with FlatAffineConstraints. Anyway, these are all "internal" users, so there should always be a way to refactor it. External users always use either FlatAffineConstraints or FlatAffineValueConstraints.

The former can expose a const reference accessors to constraints if necessary.

Requires a few more code changes, but should be possible. FlatAffineConstraints::fourierMotzkinEliminate etc. (everything that removes/adds columns) must be adapted when called through FlatAffineValueConstraints to ensure that the Value is also removed. (In the current revision, I just have a virtual removeId function.)

I'll give it a try!

[springerm]

rebase

[ftynse]

In D107725#2935973, @springerm wrote:

There is one that comes to mind: getFlattenedAffineExprs.

Hmm, I would have expected this to work without ids. AffineExprs don't know about those. The reason why it may be needing ids is some additional simplification of the map before/after the flattening. It should be possible to do this simplification in a separate call.

E.g., it takes a FlatAffineConstraints in FlatAffineConstraints::composeMatchingMap and a FlatAffineValueConstraints in FlatAffineValueConstraints::addLowerOrUpperBound and FlatAffineValueConstraints::composeMap. But I think I can reimplement composeMap in terms of composeMatchingMap, similar to addLowerOrUpperBound in D107729, so that getFlattenedAffineExprs is always called with FlatAffineConstraints. Anyway, these are all "internal" users, so there should always be a way to refactor it. External users always use either FlatAffineConstraints or FlatAffineValueConstraints.

Sounds good! Internal uses can also be function templates as long as the member functions they call have identical signatures. This will remove the need for virtual dispatch.

Requires a few more code changes, but should be possible. FlatAffineConstraints::fourierMotzkinEliminate etc. (everything that removes/adds columns) must be adapted when called through FlatAffineValueConstraints to ensure that the Value is also removed. (In the current revision, I just have a virtual removeId function.)

I'll give it a try!

Same idea as above. If we have removeColumn and template <MapTy> void fmEliminateImpl(...) that uses MapTy::removeColumn, we should be good to go.

[springerm]

I ran into an inconvenience with the "composition" approach.

In the composition design, there are two classes:

class FlatAffineConstraints { /* ... */ };

class FlatAffineValueConstraints {
public:
  /* ... */
  const FlatAffineConstraints &getConstraints() const { return fac; }

private:
  FlatAffineConstraints fac;
  SmallVector<Optional<Value>, 8> ids;
};

FlatAffineValueConstraints contains the functions that require Value association (i.e., access to ids). All other functions can be called through obj.getConstraints().someFunc(). getConstraints returns a const reference, so users cannot call obj.getConstraints().addDimId(...). This would bring the state of fac and the FlatAffineValueConstraints object out of sync. Columns must be added/removed/swapped/... through the same functions defined on FlatAffineValueConstraints, which calls the fac implementation and ensures ids is updates correctly. So far so good.

The problem is, a large number of functions of FlatAffineConstraints is non-const. They may not even add/remove columns but just modify the constraints. Such functions cannot be called through getConstraints(). Instead, I need a wrapper function on FlatAffineValueConstraints that sometimes just calls the fac implementation and does nothing more. I'm mostly done with this refactoring and I found myself reimplementing/forwarding a quite big part of the API of FlatAffineConstraints.

For reference, these are functions that must be defined on FlatAffineValueConstraints, either with added functionality or as pure wrappers to get around the constness issue:

reset (2 overloads), append, &atEq, &atIneq, addAffineForOpDomain, addDomainFromSliceMaps, addAffineIfOpDomain, addLowerOrUpperBound (2 overloads), getSliceBounds, addSliceBounds, addInequality, addEquality, addConstantLowerBound (2 overloads), addConstantUpperBound (2 overloads), addLocalFloorDiv, setIdToConstant (2 overloads), swapId, addDimId, addSymbolId, addLocalId, addId, addInductionVarOrTerminalSymbol, composeMap, composeMatchingMap, getIneqAsAffineValueMap, projectOut (2 overloads), removeId, removeEquality, removeInequality, setDimSymbolSeparation, convertLoopIVSymbolsToDims, setAndEliminate, constantFoldId, constantFoldIdRange, unionBoundingBox, areIdsAlignedWithOther, mergeAndAlignIdsWithOther, getIds (2 overloads), getId (2 overloads), getIdValue, getIdValues, getAllIdValues, setIdValue, setIdValues, clearAndCopyFrom, removeIndependentConstraints, removeTrivialRedundancy, removeTrivialInequalities, removeRedundantConstraints, clearConstraints

E.g., functions such as addConstantLowerBound or removeTrivialRedundancy should not be part of the API of FlatAffineValueConstraints IMO.

And these are the functions that would have to be added to FlatAffineValueConstraints if we go for the "derived class" design, either as overridden functions or as completely new functions:

reset (3 overloads), addAffineForOpDomain, addDomainFromSliceMaps, addAffineIfOpDomain, addLowerOrUpperBound, getIneqAsAffineValueMap, addSliceBounds, setIdToConstant, findId, containsId, swapId, addDimId, addSymbolId, addId (2 overloads), addInductionVarOrTerminalSymbol, composeMap, projectOut, convertLoopIVSymbolsToDims, unionBoundingBox, unionBoundingBox, areIdsAlignedWithOther, clearAndCopyFrom, getIds (2 overloads), getId (2 overloads), getIdValue, hasIdValue, hasIdValues, getIdValues, getAllIdValues, setIdValue, setIdValues

The above functions are only the public ones. Maybe some of them could be made private, which solve the constness issue. But in the derived class design, even private functions remain a bit simpler IMO because I can just call a virtual function instead of extracting the function impl into a static function with a function template, as you suggested above. (Also, functions such as removeId are sometimes not called directly but via another function, so maybe I would have to forward the template etc...)

Another concern I have is with code maintenance. There is an implicit assumptions that every call to addDim etc. (everything that modifies the set of columns) must go through FlatAffineValueConstraints. If someone makes a change to FlatAffineConstraints which modifies columns, but does not update FlatAffineValueConstraints, there's a chance that the ids go out of sync. This should be prevented by the fact that getConstraints() returns a const reference. So this is mainly a problem in case of changes to functions that I had to split into two parts as part of this refactoring: E.g., unionBoundingBox is split into two parts: It computes the union in FlatAffineConstraints, whereas the FlatAffineValueConstraints aligns the columns, then calls the fac implementation. But then, nothing prevents other people from making changes to columns in FlatAffineConstraints::unionBoundingBox.

Overall, I think the derived class design would be better here. What do you think?

[springerm]

rebase

[springerm]

mlir/include/mlir/Analysis/AffineStructures.h

246–247

"id" seems to be used quite a lot in here, e.g.: addDimId, addLocalId, swapId, etc.

I think whenever "id" refers to a value, it should be renamed. E.g.: containsId --> containsValue or findId --> findValue. This would be a rather small change.

We could also rename all the other uses of "id", e.g.: swapId --> swapColumn. But to be consistent, we should then also rename stuff such as addDimId --> addDimColumn or areIdsAligned --> areColumnsAligned.

I'll prepare a new (dependent) commit that renames id to value where appropriate. (I think it should be a separate commit to make the review easier, because right now code is simply copied/moved around, which is easy to review.)

Not sure what to do with id --> column. Is it worth it? Either one is fine with me.

[springerm]

mlir/include/mlir/Analysis/AffineStructures.h

246–247

There is a actually a difference between "ids" and "columns".

numCols = numIds + 1

There is one column for the constant value, which is not an "identifier" (or whatever you may call it). So "column" may not be the right word in general. But I think in many places the "id" part can simply be dropped.

[ftynse]

Overall, I think the derived class design would be better here. What do you think?

Generally, whatever requires the least non-trivial code. Overrides are fine as long as we don't need RTTI, the cost of a virtual call is neglectable when we compute things like Fourier-Motzkin.

[ftynse]

mlir/include/mlir/Analysis/AffineStructures.h

246–247

Not sure what to do with id --> column. Is it worth it? Either one is fine with me.

I don't feel strongly about this, just want to avoid potential confusion.

There is one column for the constant value, which is not an "identifier" (or whatever you may call it). So "column" may not be the right word in general. But I think in many places the "id" part can simply be dropped.

"Variable" is another alternative that generalizes "dimension" and "symbol" and clearly excludes constants. Anything that makes it easy to differentiate whether the method touches Value parts or not sounds helpful here. At the same time, the smaller the API change, the better.

[springerm]

In D107725#2940357, @ftynse wrote:

Overall, I think the derived class design would be better here. What do you think?

Generally, whatever requires the least non-trivial code. Overrides are fine as long as we don't need RTTI, the cost of a virtual call is neglectable when we compute things like Fourier-Motzkin.

OK, then this commit is ready as it.

mlir/include/mlir/Analysis/AffineStructures.h

246–247

I decided to leave the term identifier. I think this is OK and well documented in the class comment of FlatAffineConstraints.

I renamed id to value when it refers to an associated SSA value.

The changes are in a separate commit, so that this commit doesn't get any longer (D107947).

[springerm]

mlir/lib/Analysis/AffineStructures.cpp

281–282

Removed the comment entirely. (There's already a header file comment.)

[springerm]

update

[springerm]

rebase

[bondhugula]

mlir/include/mlir/Analysis/AffineStructures.h

61

I'd just avoid mentioning RTTI (although this is custom RTTI) -- it's confusing and unnecessary. This comment can instead be replaced with a line actually documenting the sub-class kinds.

62

Doc comment on the kind or the enum class mentioning about the specialization.

104

Triple /// comments. I know some of the other methods below missed it.

507

Nit: No need of the comma in between I think.

551

Triple /// comment.

[springerm]

address comments

[nicolasvasilache]

Great, thanks for refactoring for better reuse, LGTM!
Do you plan on further separating APIs that require particular dim/sym interpretation?

mlir/include/mlir/Analysis/AffineStructures.h

704

Nit: I'd add some newlines and align the left braces.

[springerm]

Do you plan on further separating APIs that require particular dim/sym interpretation?

No further plans at the moment. Is there a particular refactoring that you have in mind?

mlir/include/mlir/Analysis/AffineStructures.h

704

Updating as part of D107947.

mlir/include/mlir/Analysis/AffineAnalysis.h

 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 
 namespace mlir {
 
 class AffineApplyOp;
 class AffineForOp;
 class AffineValueMap;
-class FlatAffineConstraints;
+class FlatAffineValueConstraints;
 class Operation;
 
 /// A description of a (parallelizable) reduction in an affine loop.
 struct LoopReduction {
   /// Reduction kind.
   AtomicRMWKind kind;
 
   /// Position of the iteration argument that acts as accumulator.

 /// the loop IVs of the forOps and AffineIfOp's operands appearing in
 /// that order. Bounds of the loop are used to add appropriate inequalities.
 /// Constraints from the index sets of AffineIfOp are also added. Any symbols
 /// founds in the bound operands are added as symbols in the system. Returns
 /// failure for the yet unimplemented cases. `ops` accepts both AffineForOp and
 /// AffineIfOp.
 //  TODO: handle non-unit strides.
 LogicalResult getIndexSet(MutableArrayRef<Operation *> ops,
-                          FlatAffineConstraints *domain);
+                          FlatAffineValueConstraints *domain);
 
 /// Encapsulates a memref load or store access information.
 struct MemRefAccess {
   Value memref;
   Operation *opInst;
   SmallVector<Value, 4> indices;
 
   /// Constructs a MemRefAccess from a load or store operation.
enum ResultEnum {
     NoDependence,  // No dependence exists between 'srcAccess' and 'dstAccess'.
     Failure,       // Dependence check failed due to unsupported cases.
   } value;
   DependenceResult(ResultEnum v) : value(v) {}
 };
 
 DependenceResult checkMemrefAccessDependence(
     const MemRefAccess &srcAccess, const MemRefAccess &dstAccess,
-    unsigned loopDepth, FlatAffineConstraints *dependenceConstraints,
+    unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints,
     SmallVector<DependenceComponent, 2> *dependenceComponents,
     bool allowRAR = false);
 
 /// Utility function that returns true if the provided DependenceResult
 /// corresponds to a dependence result.
 inline bool hasDependence(DependenceResult result) {
   return result.value == DependenceResult::HasDependence;
 }

mlir/include/mlir/Analysis/AffineStructures.h

 /// 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:
+  /// All derived classes of FlatAffineConstraints.
+  enum class Kind { FlatAffineConstraints, FlatAffineValueConstraints };
+
+  /// Kind of identifier (column).
   enum IdKind { Dimension, Symbol, Local };
 
   /// Constructs a constraint system reserving memory for the specified number
-  /// of constraints and identifiers..
+  /// of constraints and identifiers.
   FlatAffineConstraints(unsigned numReservedInequalities,
                         unsigned numReservedEqualities,
                         unsigned numReservedCols, unsigned numDims,
-                        unsigned numSymbols, unsigned numLocals,
-                        ArrayRef<Optional<Value>> idArgs = {})
+                        unsigned numSymbols, unsigned numLocals)
       : numIds(numDims + numSymbols + numLocals), numDims(numDims),
         numSymbols(numSymbols),
         equalities(0, numIds + 1, numReservedEqualities, numReservedCols),
         inequalities(0, numIds + 1, numReservedInequalities, numReservedCols) {
     assert(numReservedCols >= numIds + 1);
-    assert(idArgs.empty() || idArgs.size() == numIds);
-    ids.reserve(numReservedCols);
-    if (idArgs.empty())
-      ids.resize(numIds, None);
-    else
-      ids.append(idArgs.begin(), idArgs.end());
   }
 
   /// Constructs a constraint system with the specified number of
   /// dimensions and symbols.
   FlatAffineConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
-                        unsigned numLocals = 0,
-                        ArrayRef<Optional<Value>> idArgs = {})
+                        unsigned numLocals = 0)
       : FlatAffineConstraints(/*numReservedInequalities=*/0,
                               /*numReservedEqualities=*/0,
                               /*numReservedCols=*/numDims + numSymbols +
                                   numLocals + 1,
-                              numDims, numSymbols, numLocals, idArgs) {}
+                              numDims, numSymbols, numLocals) {}
 
   /// 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);
   }
 
-  /// Create a flat affine constraint system from an AffineValueMap or a list of
-  /// these. The constructed system will only include equalities.
-  explicit FlatAffineConstraints(const AffineValueMap &avm);
-  explicit FlatAffineConstraints(ArrayRef<const AffineValueMap *> avmRef);
-
   /// Creates an affine constraint system from an IntegerSet.
   explicit FlatAffineConstraints(IntegerSet set);
 
-  FlatAffineConstraints(ArrayRef<const AffineValueMap *> avmRef,
-                        IntegerSet set);
-
   FlatAffineConstraints(const MutableAffineMap &map);
 
-  ~FlatAffineConstraints() {}
+  virtual ~FlatAffineConstraints() = default;
 
-  // 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, ArrayRef<Value> idArgs = {});
+  /// Return the kind of this FlatAffineConstraints.
+  virtual Kind getKind() const { return Kind::FlatAffineConstraints; }
+
+  static bool classof(const FlatAffineConstraints *cst) { return true; }
+
+  /// 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, ArrayRef<Value> idArgs = {});
+             unsigned numLocals = 0);
 
   /// Appends constraints from 'other' into this. This is equivalent to an
   /// intersection with no simplification of any sort attempted.
   void append(const FlatAffineConstraints &other);
 
   /// Checks for emptiness by performing variable elimination on all
   /// identifiers, running the GCD test on each equality constraint, and
   /// checking for invalid constraints. Returns true if the GCD test fails for
   /// any equality, or if any invalid constraints are discovered on any row.
   /// Returns false otherwise.
   bool isEmpty() const;
 
   /// Runs the GCD test on all equality constraints. Returns 'true' if this test
   /// fails on any equality. Returns 'false' otherwise.
   /// This test can be used to disprove the existence of a solution. If it
   /// returns true, no integer solution to the equality constraints can exist.
   bool isEmptyByGCDTest() const;
 
   /// Returns true if the set of constraints is found to have no solution,
   /// false if a solution exists. Uses the same algorithm as findIntegerSample.
   bool isIntegerEmpty() const;
 
-  // 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.
+  /// 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.
   Matrix getBoundedDirections() const;
 
   /// Find an integer sample point satisfying the constraints using a
   /// 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;
 
   /// Returns true if the given point satisfies the constraints, or false
   /// otherwise.
   bool containsPoint(ArrayRef<int64_t> point) const;
 
-  // Clones this object.
+  /// Clones this object.
   std::unique_ptr<FlatAffineConstraints> clone() 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); }
 
   inline int64_t atIneq(unsigned i, unsigned j) const {
     return inequalities(i, j);
public:
   inline ArrayRef<int64_t> getEquality(unsigned idx) const {
     return equalities.getRow(idx);
   }
 
   inline ArrayRef<int64_t> getInequality(unsigned idx) const {
     return inequalities.getRow(idx);
   }
 
-  /// 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
-  /// constraint system. Returns failure for the yet unimplemented/unsupported
-  /// cases.  Any new identifiers that are found in the bound operands of the
-  /// 'affine.for' operation are added as trailing identifiers (either
-  /// dimensional or symbolic depending on whether the operand is a valid
-  /// symbol).
-  //  TODO: add support for non-unit strides.
-  LogicalResult addAffineForOpDomain(AffineForOp forOp);
-
-  /// Adds constraints (lower and upper bounds) for each loop in the loop nest
-  /// described by the bound maps 'lbMaps' and 'ubMaps' of a computation slice.
-  /// Every pair ('lbMaps[i]', 'ubMaps[i]') describes the bounds of a loop in
-  /// the nest, sorted outer-to-inner. 'operands' contains the bound operands
-  /// for a single bound map. All the bound maps will use the same bound
-  /// operands. Note that some loops described by a computation slice might not
-  /// exist yet in the IR so the Value attached to those dimension identifiers
-  /// might be empty. For that reason, this method doesn't perform Value
-  /// look-ups to retrieve the dimension identifier positions. Instead, it
-  /// assumes the position of the dim identifiers in the constraint system is
-  /// the same as the position of the loop in the loop nest.
-  LogicalResult addDomainFromSliceMaps(ArrayRef<AffineMap> lbMaps,
-                                       ArrayRef<AffineMap> ubMaps,
-                                       ArrayRef<Value> operands);
-
-  /// Adds constraints imposed by the `affine.if` operation. These constraints
-  /// are collected from the IntegerSet attached to the given `affine.if`
-  /// 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 lower or an upper bound for the identifier at the specified
   /// position with constraints being drawn from the specified bound map. If
   /// `eq` is true, add a single equality equal to the bound map's first result
   /// expr.
   /// Note: The dimensions/symbols of this FlatAffineConstraints must match the
   /// dimensions/symbols of the affine map.
   LogicalResult addLowerOrUpperBound(unsigned pos, AffineMap boundMap, bool eq,
                                      bool lower = true);
 
-  /// Adds a lower or an upper bound for the identifier at the specified
-  /// position with constraints being drawn from the specified bound map and
-  /// operands. If `eq` is true, add a single equality equal to the bound map's
-  /// first result expr.
-  LogicalResult addLowerOrUpperBound(unsigned pos, AffineMap boundMap,
-                                     ValueRange operands, bool eq,
-                                     bool lower = true);
-
-  /// 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,
-                               MLIRContext *context) const;
-
   /// 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);
 
-  /// Adds slice lower bounds represented by lower bounds in 'lbMaps' and upper
-  /// bounds in 'ubMaps' to each identifier in the constraint system which has
-  /// a value in 'values'. Note that both lower/upper bounds share the same
-  /// operand list 'operands'.
-  /// This function assumes 'values.size' == 'lbMaps.size' == 'ubMaps.size'.
-  /// Note that both lower/upper bounds use operands from 'operands'.
-  LogicalResult addSliceBounds(ArrayRef<Value> values,
-                               ArrayRef<AffineMap> lbMaps,
-                               ArrayRef<AffineMap> ubMaps,
-                               ArrayRef<Value> operands);
-
-  // Adds an inequality (>= 0) from the coefficients specified in inEq.
+  /// Adds an inequality (>= 0) from the coefficients specified in inEq.
   void addInequality(ArrayRef<int64_t> inEq);
-  // Adds an equality from the coefficients specified in eq.
+  /// Adds an equality from the coefficients specified in eq.
   void addEquality(ArrayRef<int64_t> eq);
 
   /// Adds a constant lower bound constraint for the specified identifier.
   void addConstantLowerBound(unsigned pos, int64_t lb);
   /// Adds a constant upper bound constraint for the specified identifier.
   void addConstantUpperBound(unsigned pos, int64_t ub);
 
   /// 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 = dividend floordiv c    <=>   c*q <= dividend <= c*q + c - 1.
   void addLocalFloorDiv(ArrayRef<int64_t> dividend, int64_t divisor);
 
   /// Adds a constant lower bound constraint for the specified expression.
   void addConstantLowerBound(ArrayRef<int64_t> expr, int64_t lb);
   /// Adds a constant upper bound constraint for the specified expression.
   void addConstantUpperBound(ArrayRef<int64_t> expr, int64_t ub);
 
   /// Sets the identifier at the specified position to a constant.
   void setIdToConstant(unsigned pos, int64_t val);
 
-  /// Sets the identifier corresponding to the specified Value id to a
-  /// constant. Asserts if the 'id' is not found.
-  void setIdToConstant(Value id, int64_t val);
-
-  /// Looks up the position of the identifier with the specified Value. Returns
-  /// true if found (false otherwise). `pos' is set to the (column) position of
-  /// the identifier.
-  bool findId(Value id, unsigned *pos) const;
-
-  /// Returns true if an identifier with the specified Value exists, false
-  /// otherwise.
-  bool containsId(Value id) const;
-
   /// Swap the posA^th identifier with the posB^th identifier.
-  void swapId(unsigned posA, unsigned posB);
+  virtual void swapId(unsigned posA, unsigned posB);
 
-  // Add identifiers of the specified kind - specified positions are relative to
-  // the kind of identifier. The coefficient column corresponding to the added
-  // identifier is initialized to zero. 'id' is the Value corresponding to the
-  // identifier that can optionally be provided.
-  void addDimId(unsigned pos, Value id = nullptr);
-  void addSymbolId(unsigned pos, Value id = nullptr);
+  /// Add identifiers of the specified kind - specified positions are relative
+  /// to the kind of identifier. The coefficient column corresponding to the
+  /// added identifier is initialized to zero.
+  void addDimId(unsigned pos);
+  void addSymbolId(unsigned pos);
   void addLocalId(unsigned pos);
-  void addId(IdKind kind, unsigned pos, Value id = nullptr);
-
-  /// Add the specified values as a dim or symbol id depending on its nature, if
-  /// it already doesn't exist in the system. `id' 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 id);
-
-  /// Composes the affine value map with this FlatAffineConstrains, adding the
-  /// results of the map as dimensions at the front [0, vMap->getNumResults())
-  /// and with the dimensions set to the equalities specified by the value map.
-  /// Returns failure if the composition fails (when vMap is a semi-affine map).
-  /// 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);
+  virtual unsigned addId(IdKind kind, unsigned pos);
 
   /// 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);
 
   /// Projects out (aka eliminates) 'num' identifiers starting at position
   /// 'pos'. The resulting constraint system is the shadow along the dimensions
   /// that still exist. This method may not always be integer exact.
   // TODO: deal with integer exactness when necessary - can return a value to
   // mark exactness for example.
   void projectOut(unsigned pos, unsigned num);
   inline void projectOut(unsigned pos) { return projectOut(pos, 1); }
 
-  /// Projects out the identifier that is associate with Value .
-  void projectOut(Value id);
-
   /// Removes the specified identifier from the system.
   void removeId(unsigned pos);
 
   void removeEquality(unsigned pos);
   void removeInequality(unsigned pos);
 
+  /// Sets the values.size() identifiers starting at pos to the specified values
+  /// and removes them.
+  void setAndEliminate(unsigned pos, ArrayRef<int64_t> values);
+
   /// Changes the partition between dimensions and symbols. Depending on the new
   /// symbol count, either a chunk of trailing dimensional identifiers becomes
   /// symbols, or some of the leading symbols become dimensions.
   void setDimSymbolSeparation(unsigned newSymbolCount);
 
-  /// Changes all symbol identifiers which are loop IVs to dim identifiers.
-  void convertLoopIVSymbolsToDims();
-
-  /// Sets the values.size() identifiers starting at pos to the specified values
-  /// and removes them.
-  void setAndEliminate(unsigned pos, ArrayRef<int64_t> values);
-
   /// Tries to fold the specified identifier to a constant using a trivial
   /// equality detection; if successful, the constant is substituted for the
   /// identifier everywhere in the constraint system and then removed from the
   /// system.
   LogicalResult constantFoldId(unsigned pos);
 
   /// This method calls constantFoldId for the specified range of identifiers,
   /// 'num' identifiers starting at position 'pos'.
public:
   /// Eg: if 'this' is {0 <= d0 <= 127}, 'other' is {16 <= d0 <= 192}, the
   ///      output is {0 <= d0 <= 192}.
   /// 2) 'this' = {s0 + 5 <= d0 <= s0 + 20}, 'other' is {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 FlatAffineConstraints &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 FlatAffineConstraints &other);
-
-  /// 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 of each system are by design separate/local and are placed
-  /// one after other (this's followed by other's).
-  //  Eg: Input: 'this'  has ((%i %j) [%M %N])
-  //             'other' has (%k, %j) [%P, %N, %M])
-  //      Output: both 'this', 'other' have (%i, %j, %k) [%M, %N, %P]
-  //
-  void mergeAndAlignIdsWithOther(unsigned offset, FlatAffineConstraints *other);
-
   unsigned getNumConstraints() const {
     return getNumInequalities() + getNumEqualities();
   }
   inline unsigned getNumIds() const { return numIds; }
   inline unsigned getNumDimIds() const { return numDims; }
   inline unsigned getNumSymbolIds() const { return numSymbols; }
   inline unsigned getNumDimAndSymbolIds() const { return numDims + numSymbols; }
   inline unsigned getNumLocalIds() const {
     return numIds - numDims - numSymbols;
   }
 
-  inline ArrayRef<Optional<Value>> getIds() const {
-    return {ids.data(), ids.size()};
-  }
-  inline MutableArrayRef<Optional<Value>> getIds() {
-    return {ids.data(), ids.size()};
-  }
-
-  /// Returns the optional Value corresponding to the pos^th identifier.
-  inline Optional<Value> getId(unsigned pos) const { return ids[pos]; }
-  inline Optional<Value> &getId(unsigned pos) { return ids[pos]; }
-
-  /// Returns the Value associated with the pos^th identifier. Asserts if
-  /// no Value identifier was associated.
-  inline Value getIdValue(unsigned pos) const {
-    assert(ids[pos].hasValue() && "identifier's Value not set");
-    return ids[pos].getValue();
-  }
-
-  /// Returns the Values associated with identifiers in range [start, end).
-  /// Asserts if no Value was associated with one of these identifiers.
-  void getIdValues(unsigned start, unsigned end,
-                   SmallVectorImpl<Value> *values) const {
-    assert((start < numIds || start == end) && "invalid start position");
-    assert(end <= numIds && "invalid end position");
-    values->clear();
-    values->reserve(end - start);
-    for (unsigned i = start; i < end; i++) {
-      values->push_back(getIdValue(i));
-    }
-  }
-  inline void getAllIdValues(SmallVectorImpl<Value> *values) const {
-    getIdValues(0, numIds, values);
-  }
-
-  /// Sets Value associated with the pos^th identifier.
-  inline void setIdValue(unsigned pos, Value val) {
-    assert(pos < numIds && "invalid id position");
-    ids[pos] = val;
-  }
-  /// Sets Values associated with identifiers in the range [start, end).
-  void setIdValues(unsigned start, unsigned end, ArrayRef<Value> values) {
-    assert((start < numIds || end == start) && "invalid start position");
-    assert(end <= numIds && "invalid end position");
-    assert(values.size() == end - start);
-    for (unsigned i = start; i < end; ++i)
-      ids[i] = values[i - start];
-  }
-
-  /// Clears this list of constraints and copies other into it.
-  void clearAndCopyFrom(const FlatAffineConstraints &other);
+  /// Replaces the contents of this FlatAffineConstraints with `other`.
+  virtual void clearAndCopyFrom(const FlatAffineConstraints &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:
 
   /// Removes redundant constraints using Simplex. Although the algorithm can
   /// theoretically take exponential time in the worst case (rare), it is known
   /// to perform much better in the average case. If V is the number of vertices
   /// in the polytope and C is the number of constraints, the algorithm takes
   /// O(VC) time.
   void removeRedundantConstraints();
 
-  // Removes all equalities and inequalities.
+  /// Removes all equalities and inequalities.
   void clearConstraints();
 
   void print(raw_ostream &os) const;
   void dump() const;
 
-private:
+protected:
   /// 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;
+  virtual bool hasConsistentState() const;
 
   /// 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.
   template <bool isLower>
   Optional<int64_t> computeConstantLowerOrUpperBound(unsigned pos);
 
-  /// Align `map` with this constraint system based on `operands`. Each operand
-  /// must already have a corresponding dim/symbol in this constraint system.
-  AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const;
-
   /// 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 a single identifier at 'position' from equality and inequality
-  // constraints. Returns 'success' if the identifier was eliminated, and
-  // 'failure' otherwise.
+  /// Eliminates a single identifier at 'position' from equality and inequality
+  /// constraints. Returns 'success' if the identifier was eliminated, and
+  /// 'failure' otherwise.
   inline LogicalResult gaussianEliminateId(unsigned position) {
     return success(gaussianEliminateIds(position, position + 1) == 1);
   }
 
-  // Eliminates identifiers from equality and inequality constraints
-  // in column range [posStart, posLimit).
-  // Returns the number of variables eliminated.
+  /// Eliminates identifiers from equality and inequality constraints
+  /// in column range [posStart, posLimit).
+  /// Returns the number of variables eliminated.
   unsigned gaussianEliminateIds(unsigned posStart, unsigned posLimit);
 
   /// Eliminates 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,
+  virtual void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false,
                                        bool *isResultIntegerExact = nullptr);
 
   /// Tightens inequalities given that we are dealing with integer spaces. This
   /// is similar 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).
   void gcdTightenInequalities();
 
   /// Normalized each constraints by the GCD of its coefficients.
   void normalizeConstraintsByGCD();
 
   /// 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);
+  virtual void removeIdRange(unsigned idStart, unsigned idLimit);
 
   /// Total number of identifiers.
   unsigned numIds;
 
   /// Number of identifiers corresponding to real dimensions.
   unsigned numDims;
 
   /// Number of identifiers corresponding to symbols (unknown but constant for
   /// analysis).
   unsigned numSymbols;
 
   /// Coefficients of affine equalities (in == 0 form).
   Matrix equalities;
 
   /// Coefficients of affine inequalities (in >= 0 form).
   Matrix inequalities;
 
-  /// 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 to any Value are set to
-  /// None.
-  SmallVector<Optional<Value>, 8> ids;
-
   /// 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 FlatAffineConstraints.
   // 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;
 };
 
+/// An extension of FlatAffineConstraints in which dimensions and symbols can
+/// optionally be associated with an SSA value.
+class FlatAffineValueConstraints : public FlatAffineConstraints {
+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>> idArgs = {})
+      : FlatAffineConstraints(numReservedInequalities, numReservedEqualities,
+                              numReservedCols, numDims, numSymbols, numLocals) {
+    assert(numReservedCols >= numIds + 1);
+    assert(idArgs.empty() || idArgs.size() == numIds);
+    ids.reserve(numReservedCols);
+    if (idArgs.empty())
+      ids.resize(numIds, None);
+    else
+      ids.append(idArgs.begin(), idArgs.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>> idArgs = {})
+      : FlatAffineValueConstraints(/*numReservedInequalities=*/0,
+                                   /*numReservedEqualities=*/0,
+                                   /*numReservedCols=*/numDims + numSymbols +
+                                       numLocals + 1,
+                                   numDims, numSymbols, numLocals, idArgs) {}
+
+  /// Create a flat affine constraint system from an AffineValueMap or a list of
+  /// these. The constructed system will only include equalities.
+  explicit FlatAffineValueConstraints(const AffineValueMap &avm);
+  explicit FlatAffineValueConstraints(ArrayRef<const AffineValueMap *> avmRef);
+
+  /// Creates an affine constraint system from an IntegerSet.
+  explicit FlatAffineValueConstraints(IntegerSet set);
+
+  FlatAffineValueConstraints(ArrayRef<const AffineValueMap *> avmRef,
+                             IntegerSet set);
+
+  /// Return the kind of this FlatAffineConstraints.
+  Kind getKind() const override { return Kind::FlatAffineValueConstraints; }
+
+  static bool classof(const FlatAffineConstraints *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 reset(unsigned numReservedInequalities, unsigned numReservedEqualities,
+             unsigned numReservedCols, unsigned numDims, unsigned numSymbols,
+             unsigned numLocals, ArrayRef<Value> idArgs);
+  void reset(unsigned numDims, unsigned numSymbols, unsigned numLocals,
+             ArrayRef<Value> idArgs);
+  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
+  /// constraint system. Returns failure for the yet unimplemented/unsupported
+  /// cases.  Any new identifiers that are found in the bound operands of the
+  /// 'affine.for' operation are added as trailing identifiers (either
+  /// dimensional or symbolic depending on whether the operand is a valid
+  /// symbol).
+  //  TODO: add support for non-unit strides.
+  LogicalResult addAffineForOpDomain(AffineForOp forOp);
+
+  /// Adds constraints (lower and upper bounds) for each loop in the loop nest
+  /// described by the bound maps 'lbMaps' and 'ubMaps' of a computation slice.
+  /// Every pair ('lbMaps[i]', 'ubMaps[i]') describes the bounds of a loop in
+  /// the nest, sorted outer-to-inner. 'operands' contains the bound operands
+  /// for a single bound map. All the bound maps will use the same bound
+  /// operands. Note that some loops described by a computation slice might not
+  /// exist yet in the IR so the Value attached to those dimension identifiers
+  /// might be empty. For that reason, this method doesn't perform Value
+  /// look-ups to retrieve the dimension identifier positions. Instead, it
+  /// assumes the position of the dim identifiers in the constraint system is
+  /// the same as the position of the loop in the loop nest.
+  LogicalResult addDomainFromSliceMaps(ArrayRef<AffineMap> lbMaps,
+                                       ArrayRef<AffineMap> ubMaps,
+                                       ArrayRef<Value> operands);
+
+  /// Adds constraints imposed by the `affine.if` operation. These constraints
+  /// are collected from the IntegerSet attached to the given `affine.if`
+  /// 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 lower or an upper bound for the identifier at the specified
+  /// position with constraints being drawn from the specified bound map and
+  /// operands. If `eq` is true, add a single equality equal to the bound map's
+  /// first result expr.
+  LogicalResult addLowerOrUpperBound(unsigned pos, AffineMap boundMap,
+                                     ValueRange operands, bool eq,
+                                     bool lower = true);
+  using FlatAffineConstraints::addLowerOrUpperBound;
+
+  /// 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,
+                               MLIRContext *context) const;
+
+  /// Adds slice lower bounds represented by lower bounds in 'lbMaps' and upper
+  /// bounds in 'ubMaps' to each identifier in the constraint system which has
+  /// a value in 'values'. Note that both lower/upper bounds share the same
+  /// operand list 'operands'.
+  /// This function assumes 'values.size' == 'lbMaps.size' == 'ubMaps.size'.
+  /// Note that both lower/upper bounds use operands from 'operands'.
+  LogicalResult addSliceBounds(ArrayRef<Value> values,
+                               ArrayRef<AffineMap> lbMaps,
+                               ArrayRef<AffineMap> ubMaps,
+                               ArrayRef<Value> operands);
+
+  /// Sets the identifier corresponding to the specified Value id to a
+  /// constant. Asserts if the 'id' is not found.
+  void setIdToConstant(Value id, int64_t val);
+  using FlatAffineConstraints::setIdToConstant;
+
+  /// Looks up the position of the identifier with the specified Value. Returns
+  /// true if found (false otherwise). `pos' is set to the (column) position of
+  /// the identifier.
+  bool findId(Value id, unsigned *pos) const;
+
+  /// Returns true if an identifier with the specified Value exists, false
+  /// otherwise.
+  bool containsId(Value id) const;
+
+  /// Swap the posA^th identifier with the posB^th identifier.
+  void swapId(unsigned posA, unsigned posB) override;
+
+  /// Add identifiers of the specified kind - specified positions are relative
+  /// to the kind of identifier. The coefficient column corresponding to the
+  /// added identifier is initialized to zero. 'id' is the Value corresponding
+  /// to the identifier that can optionally be provided.
+  void addDimId(unsigned pos, Value id);
+  using FlatAffineConstraints::addDimId;
+  void addSymbolId(unsigned pos, Value id);
+  using FlatAffineConstraints::addSymbolId;
+  unsigned addId(IdKind kind, unsigned pos) override;
+  unsigned addId(IdKind kind, unsigned pos, Value id);
+
+  /// Add the specified values as a dim or symbol id depending on its nature, if
+  /// it already doesn't exist in the system. `id' 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 id);
+
+  /// Align `map` with this constraint system based on `operands`. Each operand
+  /// must already have a corresponding dim/symbol in this constraint system.
+  AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const;
+
+  /// Composes the affine value map with this FlatAffineValueConstrains, adding
+  /// the results of the map as dimensions at the front
+  /// [0, vMap->getNumResults()) and with the dimensions set to the equalities
+  /// specified by the value map.
+  ///
+  /// Returns failure if the composition fails (when vMap is a semi-affine map).
+  /// 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 id);
+  using FlatAffineConstraints::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).
+  ///
+  /// Eg: if 'this' is {0 <= d0 <= 127}, 'other' is {16 <= d0 <= 192}, the
+  ///      output is {0 <= d0 <= 192}.
+  /// 2) 'this' = {s0 + 5 <= d0 <= s0 + 20}, 'other' is {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;
+
+  /// 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 of each system are by design separate/local and are placed
+  /// one after other (this's followed by other's).
+  //  Eg: Input: 'this'  has ((%i %j) [%M %N])
+  //             'other' has (%k, %j) [%P, %N, %M])
+  //      Output: both 'this', 'other' have (%i, %j, %k) [%M, %N, %P]
+  //
+  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 FlatAffineConstraints &other) override;
+
+  inline ArrayRef<Optional<Value>> getIds() const {
+    return {ids.data(), ids.size()};
+  }
+  inline MutableArrayRef<Optional<Value>> getIds() {
+    return {ids.data(), ids.size()};
+  }
+
+  /// Returns the optional Value corresponding to the pos^th identifier.
+  inline Optional<Value> getId(unsigned pos) const { return ids[pos]; }
+  inline Optional<Value> &getId(unsigned pos) { return ids[pos]; }
+
+  /// Returns the Value associated with the pos^th identifier. Asserts if
+  /// no Value identifier was associated.
+  inline Value getIdValue(unsigned pos) const {
+    assert(hasIdValue(pos) && "identifier's Value not set");
+    return ids[pos].getValue();
+  }
+
+  /// Returns true if the pos^th identifier has an associated Value.
+  inline bool hasIdValue(unsigned pos) const { return ids[pos].hasValue(); }
+
+  /// Returns true if at least one identifier has an associated Value.
+  bool hasIdValues() const;
+
+  /// Returns the Values associated with identifiers in range [start, end).
+  /// Asserts if no Value was associated with one of these identifiers.
+  void getIdValues(unsigned start, unsigned end,
+                   SmallVectorImpl<Value> *values) const {
+    assert((start < numIds || start == end) && "invalid start position");
+    assert(end <= numIds && "invalid end position");
+    values->clear();
+    values->reserve(end - start);
+    for (unsigned i = start; i < end; i++) {
+      values->push_back(getIdValue(i));
+    }
+  }
+  inline void getAllIdValues(SmallVectorImpl<Value> *values) const {
+    getIdValues(0, numIds, values);
+  }
+
+  /// Sets Value associated with the pos^th identifier.
+  inline void setIdValue(unsigned pos, Value val) {
+    assert(pos < numIds && "invalid id position");
+    ids[pos] = val;
+  }
+
+  /// Sets Values associated with identifiers in the range [start, end).
+  void setIdValues(unsigned start, unsigned end, ArrayRef<Value> values) {
+    assert((start < numIds || end == start) && "invalid start position");
+    assert(end <= numIds && "invalid end position");
+    assert(values.size() == end - start);
+    for (unsigned i = start; i < end; ++i)
+      ids[i] = values[i - start];
+  }
+
+protected:
+  /// 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;
+
+  /// 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;
+
+  /// Eliminates 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;
+
+  /// 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 to any Value are set to
+  /// None.
+  SmallVector<Optional<Value>, 8> ids;
+};
+
 /// Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the
 /// dimensions, symbols, and additional variables that represent floor divisions
 /// 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,

mlir/include/mlir/Analysis/Utils.h

 #include "mlir/Support/LLVM.h"
 #include "llvm/ADT/SmallVector.h"
 #include <memory>
 
 namespace mlir {
 
 class AffineForOp;
 class Block;
-class FlatAffineConstraints;
 class Location;
 struct MemRefAccess;
 class Operation;
 class Value;
 
 /// Populates 'loops' with IVs of the loops surrounding 'op' ordered from
 /// the outermost 'affine.for' operation to the innermost one.
 //  TODO: handle 'affine.if' ops.
struct ComputationSliceState {
   // Slice loop nest insertion point in target loop nest.
   Block::iterator insertPoint;
   // Adds to 'cst' with constraints which represent the slice bounds on 'ivs'
   // in 'this'. Specifically, the values in 'ivs' are added to 'cst' as dim
   // identifiers and the values in 'lb/ubOperands' are added as symbols.
   // Constraints are added for all loop IV bounds (dim or symbol), and
   // constraints are added for slice bounds in 'lbs'/'ubs'.
   // Returns failure if we cannot add loop bounds because of unsupported cases.
-  LogicalResult getAsConstraints(FlatAffineConstraints *cst);
+  LogicalResult getAsConstraints(FlatAffineValueConstraints *cst);
 
   /// Adds to 'cst' constraints which represent the original loop bounds on
   /// 'ivs' in 'this'. This corresponds to the original domain of the loop nest
   /// from which the slice is being computed. Returns failure if we cannot add
   /// loop bounds because of unsupported cases.
-  LogicalResult getSourceAsConstraints(FlatAffineConstraints &cst);
+  LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst);
 
   // Clears all bounds and operands in slice state.
   void clearBounds();
 
   /// Returns true if the computation slice is empty.
   bool isEmpty() const { return ivs.empty(); }
 
   /// Returns true if the computation slice encloses all the iterations of the

 //    }
 //
 //    // Forward computation slice of loop nest '%i1'.
 //    affine.for %i1 = (d0) -> (d0)(%i0) to (d0) -> (d0 + 1)(%i0) {
 //      %v = affine.load %0[%i1] : memref<100xf32>    // 'depSinkAccess'
 //    }
 //
 void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp,
-                              FlatAffineConstraints *dependenceConstraints,
+                              FlatAffineValueConstraints *dependenceConstraints,
                               unsigned loopDepth, bool isBackwardSlice,
                               ComputationSliceState *sliceState);
 
 /// Return the number of iterations for the `slicetripCountMap` provided.
 uint64_t getSliceIterationCount(
     const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap);
 
 /// Builds a map 'tripCountMap' from AffineForOp to constant trip count for

 //
 //    affine.for %i = 0 to 32 {
 //      affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
 //        affine.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.
 //
 struct MemRefRegion {
   explicit MemRefRegion(Location loc) : loc(loc) {}
 
   /// Computes the memory region accessed by this memref with the region
   /// represented as constraints symbolic/parametric in 'loopDepth' loops
   /// surrounding opInst. The computed region's 'cst' field has exactly as many
   /// dimensional identifiers as the rank of the memref, and *potentially*
struct MemRefRegion {
   ///
   ///    affine.for %i = 0 to 32 {
   ///      affine.for %ii = %i to (d0) -> (d0 + 8) (%i) {
   ///        load %A[%ii]
   ///      }
   ///    }
   ///
   ///   {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.
   ///
   LogicalResult compute(Operation *op, unsigned loopDepth,
                         const ComputationSliceState *sliceState = nullptr,
                         bool addMemRefDimBounds = true);
 
-  FlatAffineConstraints *getConstraints() { return &cst; }
-  const FlatAffineConstraints *getConstraints() const { return &cst; }
+  FlatAffineValueConstraints *getConstraints() { return &cst; }
+  const FlatAffineValueConstraints *getConstraints() const { return &cst; }
   bool isWrite() const { return write; }
   void setWrite(bool flag) { write = flag; }
 
   /// Returns a constant upper bound on the number of elements in this region if
   /// bounded by a known constant (always possible for static shapes), None
   /// otherwise. Note that the symbols of the region are treated specially,
   /// i.e., the returned bounding constant holds for *any given* value of the
   /// symbol identifiers. The 'shape' vector is set to the corresponding
   /// dimension-wise bounds major to minor. The number of elements and all the
   /// dimension-wise bounds are guaranteed to be non-negative. We use int64_t
   /// instead of uint64_t since index types can be at most int64_t. `lbs` are
   /// set to the lower bounds for each of the rank dimensions, and lbDivisors
   /// contains the corresponding denominators for floorDivs.
   Optional<int64_t> getConstantBoundingSizeAndShape(
       SmallVectorImpl<int64_t> *shape = nullptr,
       std::vector<SmallVector<int64_t, 4>> *lbs = nullptr,
       SmallVectorImpl<int64_t> *lbDivisors = nullptr) const;
 
   /// Gets the lower and upper bound map for the dimensional identifier at
   /// `pos`.
   void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap,
                              AffineMap &ubMap) const;
 
-  /// A wrapper around FlatAffineConstraints::getConstantBoundOnDimSize(). 'pos'
-  /// corresponds to the position of the memref shape's dimension (major to
-  /// minor) which matches 1:1 with the dimensional identifier positions in
-  //'cst'.
+  /// A wrapper around FlatAffineValueConstraints::getConstantBoundOnDimSize().
+  /// 'pos' corresponds to the position of the memref shape's dimension (major
+  /// to minor) which matches 1:1 with the dimensional identifier positions in
+  /// 'cst'.
   Optional<int64_t>
   getConstantBoundOnDimSize(unsigned pos,
                             SmallVectorImpl<int64_t> *lb = nullptr,
                             int64_t *lbFloorDivisor = nullptr) const {
     assert(pos < getRank() && "invalid position");
     return cst.getConstantBoundOnDimSize(pos, lb);
   }
 
   /// Returns the size of this MemRefRegion in bytes.
   Optional<int64_t> getRegionSize();
 
-  // Wrapper around FlatAffineConstraints::unionBoundingBox.
+  // Wrapper around FlatAffineValueConstraints::unionBoundingBox.
   LogicalResult unionBoundingBox(const MemRefRegion &other);
 
   /// Returns the rank of the memref that this region corresponds to.
   unsigned getRank() const;
 
   /// Memref that this region corresponds to.
   Value memref;
 
   /// Read or write.
   bool write;
 
   /// If there is more than one load/store op associated with the region, the
   /// location information would correspond to one of those op's.
   Location loc;
 
   /// Region (data space) of the memref accessed. This set will thus have at
   /// least as many dimensional identifiers as the shape dimensionality of the
   /// memref, and these are the leading dimensions of the set appearing in that
   /// order (major to minor / outermost to innermost). There may be additional
   /// identifiers since getMemRefRegion() is called with a specific loop depth,
   /// and thus the region is symbolic in the outer surrounding loops at that
   /// depth.
   // TODO: Replace this to exploit HyperRectangularSet.
-  FlatAffineConstraints cst;
+  FlatAffineValueConstraints cst;
 };
 
 /// Returns the size of memref data in bytes if it's statically shaped, None
 /// otherwise.
 Optional<uint64_t> getMemRefSizeInBytes(MemRefType memRefType);
 
 /// Checks a load or store op for an out of bound access; returns failure if the
 /// access is out of bounds along any of the dimensions, success otherwise.

mlir/include/mlir/Dialect/Linalg/Analysis/ConstraintsSet.h

-//===- ConstraintsSet.h - Extensions for FlatAffineConstraints --*- C++ -*-===//
+//===- ConstraintsSet.h - Ext. for FlatAffineValueConstraints ---*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Linalg-specific constraints set extensions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_DIALECT_LINALG_ANALYSIS_CONSTRAINTS_SET_H_
 #define MLIR_DIALECT_LINALG_ANALYSIS_CONSTRAINTS_SET_H_
 
 #include "mlir/Analysis/AffineStructures.h"
 #include "mlir/IR/AffineMap.h"
 
 namespace mlir {
 class ValueRange;
 
 /// Linalg-specific constraints set extensions.
-class ConstraintsSet : public FlatAffineConstraints {
+class ConstraintsSet : public FlatAffineValueConstraints {
 public:
-  ConstraintsSet() : FlatAffineConstraints() {}
+  ConstraintsSet() : FlatAffineValueConstraints() {}
 
   /// Assuming `val` is defined by `val = affine.min map (operands)`, introduce
   /// all the constraints `val <= expr_i(operands)`, where expr_i are all the
   /// results of `map`.
   // This API avoids taking a dependence on the AffineMinOp definition.
   LogicalResult composeMin(Value val, AffineMap map, ValueRange operands) {
     return composeMinOrMaxMapAndOperands(val, map, operands, /*min=*/true);
   }

mlir/lib/Analysis/AffineAnalysis.cpp

bool mlir::isLoopMemoryParallel(AffineForOp forOp) {
   // Dep check depth would be number of enclosing loops + 1.
   unsigned depth = getNestingDepth(forOp) + 1;
 
   // Check dependences between all pairs of ops in 'loadAndStoreOps'.
   for (auto *srcOp : loadAndStoreOps) {
     MemRefAccess srcAccess(srcOp);
     for (auto *dstOp : loadAndStoreOps) {
       MemRefAccess dstAccess(dstOp);
-      FlatAffineConstraints dependenceConstraints;
+      FlatAffineValueConstraints dependenceConstraints;
       DependenceResult result = checkMemrefAccessDependence(
           srcAccess, dstAccess, depth, &dependenceConstraints,
           /*dependenceComponents=*/nullptr);
       if (result.value != DependenceResult::NoDependence)
         return false;
     }
   }
   return true;
void mlir::getReachableAffineApplyOps(
   }
 }
 
 // Builds a system of constraints with dimensional identifiers corresponding to
 // the loop IVs of the forOps appearing in that order. Any symbols founds in
 // the bound operands are added as symbols in the system. Returns failure for
 // the yet unimplemented cases.
 // TODO: Handle non-unit steps through local variables or stride information in
-// FlatAffineConstraints. (For eg., by using iv - lb % step = 0 and/or by
-// introducing a method in FlatAffineConstraints setExprStride(ArrayRef<int64_t>
-// expr, int64_t stride)
+// FlatAffineValueConstraints. (For eg., by using iv - lb % step = 0 and/or by
+// introducing a method in FlatAffineValueConstraints
+// setExprStride(ArrayRef<int64_t> expr, int64_t stride)
 LogicalResult mlir::getIndexSet(MutableArrayRef<Operation *> ops,
-                                FlatAffineConstraints *domain) {
+                                FlatAffineValueConstraints *domain) {
   SmallVector<Value, 4> indices;
   SmallVector<AffineForOp, 8> forOps;
 
   for (Operation *op : ops) {
     assert((isa<AffineForOp, AffineIfOp>(op)) &&
            "ops should have either AffineForOp or AffineIfOp");
     if (AffineForOp forOp = dyn_cast<AffineForOp>(op))
       forOps.push_back(forOp);

 }
 
 /// Computes the iteration domain for 'op' and populates 'indexSet', which
 /// encapsulates the constraints involving loops surrounding 'op' and
 /// potentially involving any Function symbols. The dimensional identifiers in
 /// 'indexSet' correspond to the loops surrounding 'op' from outermost to
 /// innermost.
 static LogicalResult getOpIndexSet(Operation *op,
-                                   FlatAffineConstraints *indexSet) {
+                                   FlatAffineValueConstraints *indexSet) {
   SmallVector<Operation *, 4> ops;
   getEnclosingAffineForAndIfOps(*op, &ops);
   return getIndexSet(ops, indexSet);
 }
 
 namespace {
 // ValuePositionMap manages the mapping from Values which represent dimension
 // and symbol identifiers from 'src' and 'dst' access functions to positions

 // iteration domains, the format of which is as follows:
 //
 //   [src-dim-identifiers, dst-dim-identifiers, symbol-identifiers, const_term]
 //
 // This method populates 'valuePosMap' with mappings from operand Values in
 // 'srcAccessMap'/'dstAccessMap' (as well as those in 'srcDomain'/'dstDomain')
 // to the position of these values in the merged list.
 static void buildDimAndSymbolPositionMaps(
-    const FlatAffineConstraints &srcDomain,
-    const FlatAffineConstraints &dstDomain, const AffineValueMap &srcAccessMap,
-    const AffineValueMap &dstAccessMap, ValuePositionMap *valuePosMap,
-    FlatAffineConstraints *dependenceConstraints) {
+    const FlatAffineValueConstraints &srcDomain,
+    const FlatAffineValueConstraints &dstDomain,
+    const AffineValueMap &srcAccessMap, const AffineValueMap &dstAccessMap,
+    ValuePositionMap *valuePosMap,
+    FlatAffineValueConstraints *dependenceConstraints) {
 
   // IsDimState is a tri-state boolean. It is used to distinguish three
   // different cases of the values passed to updateValuePosMap.
   // - When it is TRUE, we are certain that all values are dim values.
   // - When it is FALSE, we are certain that all values are symbol values.
   // - When it is UNKNOWN, we need to further check whether the value is from a
   // loop IV to determine its type (dim or symbol).
 
updateValuePosMap(srcAccessMap.getOperands(), /*isSrc=*/true,
                     /*isDim=*/UNKNOWN);
   // Update value position map with identifiers from dst access function.
   updateValuePosMap(dstAccessMap.getOperands(), /*isSrc=*/false,
                     /*isDim=*/UNKNOWN);
 }
 
 // Sets up dependence constraints columns appropriately, in the format:
 // [src-dim-ids, dst-dim-ids, symbol-ids, local-ids, const_term]
-static void initDependenceConstraints(
-    const FlatAffineConstraints &srcDomain,
-    const FlatAffineConstraints &dstDomain, const AffineValueMap &srcAccessMap,
-    const AffineValueMap &dstAccessMap, const ValuePositionMap &valuePosMap,
-    FlatAffineConstraints *dependenceConstraints) {
+static void
+initDependenceConstraints(const FlatAffineValueConstraints &srcDomain,
+                          const FlatAffineValueConstraints &dstDomain,
+                          const AffineValueMap &srcAccessMap,
+                          const AffineValueMap &dstAccessMap,
+                          const ValuePositionMap &valuePosMap,
+                          FlatAffineValueConstraints *dependenceConstraints) {
   // Calculate number of equalities/inequalities and columns required to
-  // initialize FlatAffineConstraints for 'dependenceDomain'.
+  // initialize FlatAffineValueConstraints for 'dependenceDomain'.
   unsigned numIneq =
       srcDomain.getNumInequalities() + dstDomain.getNumInequalities();
   AffineMap srcMap = srcAccessMap.getAffineMap();
   assert(srcMap.getNumResults() == dstAccessMap.getAffineMap().getNumResults());
   unsigned numEq = srcMap.getNumResults();
   unsigned numDims = srcDomain.getNumDimIds() + dstDomain.getNumDimIds();
   unsigned numSymbols = valuePosMap.getNumSymbols();
   unsigned numLocals = srcDomain.getNumLocalIds() + dstDomain.getNumLocalIds();
for (unsigned i = 0, e = dependenceConstraints->getNumDimAndSymbolIds();
        i < e; i++)
     assert(dependenceConstraints->getIds()[i].hasValue());
 }
 
 // Adds iteration domain constraints from 'srcDomain' and 'dstDomain' into
 // 'dependenceDomain'.
 // Uses 'valuePosMap' to determine the position in 'dependenceDomain' to which a
 // srcDomain/dstDomain Value maps.
-static void addDomainConstraints(const FlatAffineConstraints &srcDomain,
-                                 const FlatAffineConstraints &dstDomain,
+static void addDomainConstraints(const FlatAffineValueConstraints &srcDomain,
+                                 const FlatAffineValueConstraints &dstDomain,
                                  const ValuePositionMap &valuePosMap,
-                                 FlatAffineConstraints *dependenceDomain) {
+                                 FlatAffineValueConstraints *dependenceDomain) {
   unsigned depNumDimsAndSymbolIds = dependenceDomain->getNumDimAndSymbolIds();
 
   SmallVector<int64_t, 4> cst(dependenceDomain->getNumCols());
 
   auto addDomain = [&](bool isSrc, bool isEq, unsigned localOffset) {
-    const FlatAffineConstraints &domain = isSrc ? srcDomain : dstDomain;
+    const FlatAffineValueConstraints &domain = isSrc ? srcDomain : dstDomain;
     unsigned numCsts =
         isEq ? domain.getNumEqualities() : domain.getNumInequalities();
     unsigned numDimAndSymbolIds = domain.getNumDimAndSymbolIds();
     auto at = [&](unsigned i, unsigned j) -> int64_t {
       return isEq ? domain.atEq(i, j) : domain.atIneq(i, j);
     };
     auto map = [&](unsigned i) -> int64_t {
       return isSrc ? valuePosMap.getSrcDimOrSymPos(domain.getIdValue(i))

 //   b0     -f0      (b1 - f1)  (b2 - f2) = 0
 //
 // Returns failure if any AffineExpr cannot be flattened (due to it being
 // semi-affine). Returns success otherwise.
 static LogicalResult
 addMemRefAccessConstraints(const AffineValueMap &srcAccessMap,
                            const AffineValueMap &dstAccessMap,
                            const ValuePositionMap &valuePosMap,
-                           FlatAffineConstraints *dependenceDomain) {
+                           FlatAffineValueConstraints *dependenceDomain) {
   AffineMap srcMap = srcAccessMap.getAffineMap();
   AffineMap dstMap = dstAccessMap.getAffineMap();
   assert(srcMap.getNumResults() == dstMap.getNumResults());
   unsigned numResults = srcMap.getNumResults();
 
   unsigned srcNumIds = srcMap.getNumDims() + srcMap.getNumSymbols();
   ArrayRef<Value> srcOperands = srcAccessMap.getOperands();
 
   unsigned dstNumIds = dstMap.getNumDims() + dstMap.getNumSymbols();
   ArrayRef<Value> dstOperands = dstAccessMap.getOperands();
 
   std::vector<SmallVector<int64_t, 8>> srcFlatExprs;
   std::vector<SmallVector<int64_t, 8>> destFlatExprs;
-  FlatAffineConstraints srcLocalVarCst, destLocalVarCst;
+  FlatAffineValueConstraints srcLocalVarCst, destLocalVarCst;
   // Get flattened expressions for the source destination maps.
   if (failed(getFlattenedAffineExprs(srcMap, &srcFlatExprs, &srcLocalVarCst)) ||
       failed(getFlattenedAffineExprs(dstMap, &destFlatExprs, &destLocalVarCst)))
     return failure();
 
   unsigned domNumLocalIds = dependenceDomain->getNumLocalIds();
   unsigned srcNumLocalIds = srcLocalVarCst.getNumLocalIds();
   unsigned dstNumLocalIds = destLocalVarCst.getNumLocalIds();
for (unsigned r = 0, e = destLocalVarCst.getNumInequalities(); r < e; r++) {
     dependenceDomain->addInequality(ineq);
   }
   return success();
 }
 
 // Returns the number of outer loop common to 'src/dstDomain'.
 // Loops common to 'src/dst' domains are added to 'commonLoops' if non-null.
 static unsigned
-getNumCommonLoops(const FlatAffineConstraints &srcDomain,
-                  const FlatAffineConstraints &dstDomain,
+getNumCommonLoops(const FlatAffineValueConstraints &srcDomain,
+                  const FlatAffineValueConstraints &dstDomain,
                   SmallVectorImpl<AffineForOp> *commonLoops = nullptr) {
   // Find the number of common loops shared by src and dst accesses.
   unsigned minNumLoops =
       std::min(srcDomain.getNumDimIds(), dstDomain.getNumDimIds());
   unsigned numCommonLoops = 0;
   for (unsigned i = 0; i < minNumLoops; ++i) {
     if (!isForInductionVar(srcDomain.getIdValue(i)) ||
         !isForInductionVar(dstDomain.getIdValue(i)) ||
         srcDomain.getIdValue(i) != dstDomain.getIdValue(i))
       break;
     if (commonLoops != nullptr)
       commonLoops->push_back(getForInductionVarOwner(srcDomain.getIdValue(i)));
     ++numCommonLoops;
   }
   if (commonLoops != nullptr)
     assert(commonLoops->size() == numCommonLoops);
   return numCommonLoops;
 }
 
 /// Returns Block common to 'srcAccess.opInst' and 'dstAccess.opInst'.
 static Block *getCommonBlock(const MemRefAccess &srcAccess,
                              const MemRefAccess &dstAccess,
-                             const FlatAffineConstraints &srcDomain,
+                             const FlatAffineValueConstraints &srcDomain,
                              unsigned numCommonLoops) {
   // Get the chain of ancestor blocks to the given `MemRefAccess` instance. The
   // search terminates when either an op with the `AffineScope` trait or
   // `endBlock` is reached.
   auto getChainOfAncestorBlocks = [&](const MemRefAccess &access,
                                       SmallVector<Block *, 4> &ancestorBlocks,
                                       Block *endBlock = nullptr) {
     Block *currBlock = access.opInst->getBlock();

 // Returns true if the ancestor operation of 'srcAccess' appears before the
 // ancestor operation of 'dstAccess' in the common ancestral block. Returns
 // false otherwise.
 // Note that because 'srcAccess' or 'dstAccess' may be nested in conditionals,
 // the function is named 'srcAppearsBeforeDstInCommonBlock'. Note that
 // 'numCommonLoops' is the number of contiguous surrounding outer loops.
 static bool srcAppearsBeforeDstInAncestralBlock(
     const MemRefAccess &srcAccess, const MemRefAccess &dstAccess,
-    const FlatAffineConstraints &srcDomain, unsigned numCommonLoops) {
+    const FlatAffineValueConstraints &srcDomain, unsigned numCommonLoops) {
   // Get Block common to 'srcAccess.opInst' and 'dstAccess.opInst'.
   auto *commonBlock =
       getCommonBlock(srcAccess, dstAccess, srcDomain, numCommonLoops);
   // Check the dominance relationship between the respective ancestors of the
   // src and dst in the Block of the innermost among the common loops.
   auto *srcInst = commonBlock->findAncestorOpInBlock(*srcAccess.opInst);
   assert(srcInst != nullptr);
   auto *dstInst = commonBlock->findAncestorOpInBlock(*dstAccess.opInst);
   assert(dstInst != nullptr);
 
   // Determine whether dstInst comes after srcInst.
   return srcInst->isBeforeInBlock(dstInst);
 }
 
 // Adds ordering constraints to 'dependenceDomain' based on number of loops
 // common to 'src/dstDomain' and requested 'loopDepth'.
 // Note that 'loopDepth' cannot exceed the number of common loops plus one.
 // EX: Given a loop nest of depth 2 with IVs 'i' and 'j':
 // *) If 'loopDepth == 1' then one constraint is added: i' >= i + 1
 // *) If 'loopDepth == 2' then two constraints are added: i == i' and j' > j + 1
 // *) If 'loopDepth == 3' then two constraints are added: i == i' and j == j'
-static void addOrderingConstraints(const FlatAffineConstraints &srcDomain,
-                                   const FlatAffineConstraints &dstDomain,
-                                   unsigned loopDepth,
-                                   FlatAffineConstraints *dependenceDomain) {
+static void
+addOrderingConstraints(const FlatAffineValueConstraints &srcDomain,
+                       const FlatAffineValueConstraints &dstDomain,
+                       FlatAffineValueConstraints *dependenceDomain) {
   unsigned numCols = dependenceDomain->getNumCols();
   SmallVector<int64_t, 4> eq(numCols);
   unsigned numSrcDims = srcDomain.getNumDimIds();
   unsigned numCommonLoops = getNumCommonLoops(srcDomain, dstDomain);
   unsigned numCommonLoopConstraints = std::min(numCommonLoops, loopDepth);
   for (unsigned i = 0; i < numCommonLoopConstraints; ++i) {
     std::fill(eq.begin(), eq.end(), 0);
     eq[i] = -1;
     eq[i + numSrcDims] = 1;
     if (i == loopDepth - 1) {
       eq[numCols - 1] = -1;
       dependenceDomain->addInequality(eq);
     } else {
       dependenceDomain->addEquality(eq);
     }
   }
 }
 
 // Computes distance and direction vectors in 'dependences', by adding
 // variables to 'dependenceDomain' which represent the difference of the IVs,
 // eliminating all other variables, and reading off distance vectors from
 // equality constraints (if possible), and direction vectors from inequalities.
 static void computeDirectionVector(
-    const FlatAffineConstraints &srcDomain,
-    const FlatAffineConstraints &dstDomain, unsigned loopDepth,
-    FlatAffineConstraints *dependenceDomain,
+    const FlatAffineValueConstraints &srcDomain,
+    const FlatAffineValueConstraints &dstDomain, unsigned loopDepth,
+    FlatAffineValueConstraints *dependenceDomain,
     SmallVector<DependenceComponent, 2> *dependenceComponents) {
   // Find the number of common loops shared by src and dst accesses.
   SmallVector<AffineForOp, 4> commonLoops;
   unsigned numCommonLoops =
       getNumCommonLoops(srcDomain, dstDomain, &commonLoops);
   if (numCommonLoops == 0)
     return;
   // Compute direction vectors for requested loop depth.

 //       0         0        -1         0        0     0     0     100  >= 0
 //       0         0         0         1        0     0     0     0    >= 0
 //       0         0         0        -1        0     0     0     50   >= 0
 //
 //
 // TODO: Support AffineExprs mod/floordiv/ceildiv.
 DependenceResult mlir::checkMemrefAccessDependence(
     const MemRefAccess &srcAccess, const MemRefAccess &dstAccess,
-    unsigned loopDepth, FlatAffineConstraints *dependenceConstraints,
+    unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints,
     SmallVector<DependenceComponent, 2> *dependenceComponents, bool allowRAR) {
   LLVM_DEBUG(llvm::dbgs() << "Checking for dependence at depth: "
                           << Twine(loopDepth) << " between:\n";);
   LLVM_DEBUG(srcAccess.opInst->dump(););
   LLVM_DEBUG(dstAccess.opInst->dump(););
 
   // Return 'NoDependence' if these accesses do not access the same memref.
   if (srcAccess.memref != dstAccess.memref)
DependenceResult mlir::checkMemrefAccessDependence(
   AffineValueMap srcAccessMap;
   srcAccess.getAccessMap(&srcAccessMap);
 
   // Get composed access function for 'dstAccess'.
   AffineValueMap dstAccessMap;
   dstAccess.getAccessMap(&dstAccessMap);
 
   // Get iteration domain for the 'srcAccess' operation.
-  FlatAffineConstraints srcDomain;
+  FlatAffineValueConstraints srcDomain;
   if (failed(getOpIndexSet(srcAccess.opInst, &srcDomain)))
     return DependenceResult::Failure;
 
   // Get iteration domain for 'dstAccess' operation.
-  FlatAffineConstraints dstDomain;
+  FlatAffineValueConstraints dstDomain;
   if (failed(getOpIndexSet(dstAccess.opInst, &dstDomain)))
     return DependenceResult::Failure;
 
   // Return 'NoDependence' if loopDepth > numCommonLoops and if the ancestor
   // operation of 'srcAccess' does not properly dominate the ancestor
   // operation of 'dstAccess' in the same common operation block.
   // Note: this check is skipped if 'allowRAR' is true, because because RAR
   // deps can exist irrespective of lexicographic ordering b/w src and dst.
void mlir::getDependenceComponents(
   for (unsigned d = 1; d <= maxLoopDepth; ++d) {
     for (unsigned i = 0; i < numOps; ++i) {
       auto *srcOp = loadAndStoreOps[i];
       MemRefAccess srcAccess(srcOp);
       for (unsigned j = 0; j < numOps; ++j) {
         auto *dstOp = loadAndStoreOps[j];
         MemRefAccess dstAccess(dstOp);
 
-        FlatAffineConstraints dependenceConstraints;
+        FlatAffineValueConstraints dependenceConstraints;
         SmallVector<DependenceComponent, 2> depComps;
         // TODO: Explore whether it would be profitable to pre-compute and store
         // deps instead of repeatedly checking.
         DependenceResult result = checkMemrefAccessDependence(
             srcAccess, dstAccess, d, &dependenceConstraints, &depComps);
         if (hasDependence(result))
           depCompsVec->push_back(depComps);
       }
     }
   }
 }

mlir/lib/Analysis/AffineStructures.cpp

if (set.getNumConstraints() == 0) {
     return success();
   }
   return ::getFlattenedAffineExprs(set.getConstraints(), set.getNumDims(),
                                    set.getNumSymbols(), flattenedExprs,
                                    localVarCst);
 }
 
 //===----------------------------------------------------------------------===//
-// FlatAffineConstraints.
+// 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)
     : numIds(set.getNumDims() + set.getNumSymbols()), numDims(set.getNumDims()),
       numSymbols(set.getNumSymbols()),
       equalities(0, numIds + 1, set.getNumEqualities(), numIds + 1),
       inequalities(0, numIds + 1, set.getNumInequalities(), numIds + 1) {
-  ids.resize(numIds, None);
-
   // Flatten expressions and add them to the constraint system.
   std::vector<SmallVector<int64_t, 8>> flatExprs;
   FlatAffineConstraints localVarCst;
   if (failed(getFlattenedAffineExprs(set, &flatExprs, &localVarCst))) {
     assert(false && "flattening unimplemented for semi-affine integer sets");
     return;
   }
   assert(flatExprs.size() == set.getNumConstraints());
for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
     } 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) {
+  ids.resize(numIds, None);
+}
+
 void FlatAffineConstraints::reset(unsigned numReservedInequalities,
                                   unsigned numReservedEqualities,
                                   unsigned newNumReservedCols,
                                   unsigned newNumDims, unsigned newNumSymbols,
-                                  unsigned newNumLocals,
-                                  ArrayRef<Value> idArgs) {
+                                  unsigned newNumLocals) {
+  assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 &&
+         "minimum 1 column");
+  *this = FlatAffineConstraints(numReservedInequalities, numReservedEqualities,
+                                newNumReservedCols, 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, /*idArgs=*/{});
+}
+
+void FlatAffineValueConstraints::reset(
+    unsigned numReservedInequalities, unsigned numReservedEqualities,
+    unsigned newNumReservedCols, unsigned newNumDims, unsigned newNumSymbols,
+    unsigned newNumLocals, ArrayRef<Value> idArgs) {
   assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 &&
          "minimum 1 column");
   SmallVector<Optional<Value>, 8> newIds;
   if (!idArgs.empty())
     newIds.assign(idArgs.begin(), idArgs.end());
 
-  *this = FlatAffineConstraints(numReservedInequalities, numReservedEqualities,
-                                newNumReservedCols, newNumDims, newNumSymbols,
-                                newNumLocals, newIds);
+  *this = FlatAffineValueConstraints(
+      numReservedInequalities, numReservedEqualities, newNumReservedCols,
+      newNumDims, newNumSymbols, newNumLocals, newIds);
 }
 
 void FlatAffineConstraints::reset(unsigned newNumDims, unsigned newNumSymbols,
+                                  unsigned newNumLocals) {
+  reset(0, 0, newNumDims + newNumSymbols + newNumLocals + 1, newNumDims,
+        newNumSymbols, newNumLocals);
+}
+
+void FlatAffineValueConstraints::reset(unsigned newNumDims,
+                                       unsigned newNumSymbols,
                                        unsigned newNumLocals,
                                        ArrayRef<Value> idArgs) {
   reset(0, 0, newNumDims + newNumSymbols + newNumLocals + 1, newNumDims,
         newNumSymbols, newNumLocals, idArgs);
 }
 
 void FlatAffineConstraints::append(const FlatAffineConstraints &other) {
   assert(other.getNumCols() == getNumCols());
   assert(other.getNumDimIds() == getNumDimIds());
   assert(other.getNumSymbolIds() == getNumSymbolIds());
for (unsigned r = 0, e = other.getNumEqualities(); r < e; r++) {
     addEquality(other.getEquality(r));
   }
 }
 
 void FlatAffineConstraints::addLocalId(unsigned pos) {
   addId(IdKind::Local, pos);
 }
 
-void FlatAffineConstraints::addDimId(unsigned pos, Value id) {
+void FlatAffineConstraints::addDimId(unsigned pos) {
+  addId(IdKind::Dimension, pos);
+}
+
+void FlatAffineValueConstraints::addDimId(unsigned pos, Value id) {
   addId(IdKind::Dimension, pos, id);
 }
 
-void FlatAffineConstraints::addSymbolId(unsigned pos, Value id) {
+void FlatAffineConstraints::addSymbolId(unsigned pos) {
+  addId(IdKind::Symbol, pos);
+}
+
+void FlatAffineValueConstraints::addSymbolId(unsigned pos, Value id) {
   addId(IdKind::Symbol, pos, id);
 }
 
-/// Adds a dimensional identifier. The added column is initialized to
-/// zero.
-void FlatAffineConstraints::addId(IdKind kind, unsigned pos, Value id) {
+unsigned FlatAffineConstraints::addId(IdKind kind, unsigned pos) {
   if (kind == IdKind::Dimension)
     assert(pos <= getNumDimIds());
   else if (kind == IdKind::Symbol)
     assert(pos <= getNumSymbolIds());
   else
     assert(pos <= getNumLocalIds());
 
-  int absolutePos;
+  unsigned absolutePos;
   if (kind == IdKind::Dimension) {
     absolutePos = pos;
     numDims++;
   } else if (kind == IdKind::Symbol) {
     absolutePos = pos + getNumDimIds();
     numSymbols++;
   } else {
     absolutePos = pos + getNumDimIds() + getNumSymbolIds();
   }
   numIds++;
 
   inequalities.insertColumn(absolutePos);
   equalities.insertColumn(absolutePos);
 
+  return absolutePos;
+}
+
+unsigned FlatAffineValueConstraints::addId(IdKind kind, unsigned pos) {
+  return addId(kind, pos, /*id=*/{});
+}
+
+unsigned FlatAffineValueConstraints::addId(IdKind kind, unsigned pos,
+                                           Value id) {
+  unsigned absolutePos = FlatAffineConstraints::addId(kind, pos);
+
   // If an 'id' is provided, insert it; otherwise use None.
   if (id)
     ids.insert(ids.begin() + absolutePos, id);
   else
     ids.insert(ids.begin() + absolutePos, None);
   assert(ids.size() == getNumIds());
+
+  return absolutePos;
+}
+
+bool FlatAffineValueConstraints::hasIdValues() const {
+  return llvm::find_if(ids, [](Optional<Value> id) { return id.hasValue(); }) !=
+         ids.end();
 }
 
 /// Checks if two constraint systems are in the same space, i.e., if they are
 /// associated with the same set of identifiers, appearing in the same order.
-static bool areIdsAligned(const FlatAffineConstraints &a,
-                          const FlatAffineConstraints &b) {
+static bool areIdsAligned(const FlatAffineValueConstraints &a,
+                          const FlatAffineValueConstraints &b) {
   return a.getNumDimIds() == b.getNumDimIds() &&
          a.getNumSymbolIds() == b.getNumSymbolIds() &&
          a.getNumIds() == b.getNumIds() && a.getIds().equals(b.getIds());
 }
 
 /// Calls areIdsAligned to check if two constraint systems have the same set
 /// of identifiers in the same order.
-bool FlatAffineConstraints::areIdsAlignedWithOther(
-    const FlatAffineConstraints &other) {
+bool FlatAffineValueConstraints::areIdsAlignedWithOther(
+    const FlatAffineValueConstraints &other) {
   return areIdsAligned(*this, other);
 }
 
 /// 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) {
   SmallPtrSet<Value, 8> uniqueIds;
   for (auto id : cst.getIds()) {
     if (id.hasValue() && !uniqueIds.insert(id.getValue()).second)
       return false;
   }
   return true;
 }
 
 /// Merge and align the identifiers of A and B 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 A's original
 /// identifiers appearing first followed by any of B's identifiers that didn't
 /// appear in A. Local identifiers of each system are by design separate/local
 /// and are placed one after other (A's followed by B's).
 //  Eg: Input: A has ((%i %j) [%M %N]) and B has (%k, %j) [%P, %N, %M])
 //      Output: both A, B have (%i, %j, %k) [%M, %N, %P]
-//
-static void mergeAndAlignIds(unsigned offset, FlatAffineConstraints *a,
-                             FlatAffineConstraints *b) {
+static void mergeAndAlignIds(unsigned offset, FlatAffineValueConstraints *a,
+                             FlatAffineValueConstraints *b) {
   assert(offset <= a->getNumDimIds() && offset <= b->getNumDimIds());
   // A merge/align isn't meaningful if a cst's ids aren't distinct.
   assert(areIdsUnique(*a) && "A's id values aren't unique");
   assert(areIdsUnique(*b) && "B's id values aren't unique");
 
   assert(std::all_of(a->getIds().begin() + offset,
                      a->getIds().begin() + a->getNumDimAndSymbolIds(),
                      [](Optional<Value> id) { return id.hasValue(); }));
for (unsigned t = a->getNumDimAndSymbolIds(),
       a->addSymbolId(a->getNumSymbolIds());
       a->setIdValue(a->getNumDimAndSymbolIds() - 1, b->getIdValue(t));
     }
   }
   assert(areIdsAligned(*a, *b) && "IDs expected to be aligned");
 }
 
 // Call 'mergeAndAlignIds' to align constraint systems of 'this' and 'other'.
-void FlatAffineConstraints::mergeAndAlignIdsWithOther(
-    unsigned offset, FlatAffineConstraints *other) {
+void FlatAffineValueConstraints::mergeAndAlignIdsWithOther(
+    unsigned offset, FlatAffineValueConstraints *other) {
   mergeAndAlignIds(offset, this, other);
 }
 
-LogicalResult FlatAffineConstraints::composeMap(const AffineValueMap *vMap) {
+LogicalResult
+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) {
for (unsigned r = 0, e = flatExprs.size(); r < e; r++) {
     // Add the equality connecting the result of the map to this constraint set.
     addEquality(eqToAdd);
   }
 
   return success();
 }
 
 // Turn a symbol into a dimension.
-static void turnSymbolIntoDim(FlatAffineConstraints *cst, Value id) {
+static void turnSymbolIntoDim(FlatAffineValueConstraints *cst, Value id) {
   unsigned pos;
   if (cst->findId(id, &pos) && pos >= cst->getNumDimIds() &&
       pos < cst->getNumDimAndSymbolIds()) {
     cst->swapId(pos, cst->getNumDimIds());
     cst->setDimSymbolSeparation(cst->getNumSymbolIds() - 1);
   }
 }
 
 // Changes all symbol identifiers which are loop IVs to dim identifiers.
-void FlatAffineConstraints::convertLoopIVSymbolsToDims() {
+void FlatAffineValueConstraints::convertLoopIVSymbolsToDims() {
   // Gather all symbols which are loop IVs.
   SmallVector<Value, 4> loopIVs;
   for (unsigned i = getNumDimIds(), e = getNumDimAndSymbolIds(); i < e; i++) {
     if (ids[i].hasValue() && getForInductionVarOwner(ids[i].getValue()))
       loopIVs.push_back(ids[i].getValue());
   }
   // Turn each symbol in 'loopIVs' into a dim identifier.
   for (auto iv : loopIVs) {
     turnSymbolIntoDim(this, iv);
   }
 }
 
-void FlatAffineConstraints::addInductionVarOrTerminalSymbol(Value id) {
+void FlatAffineValueConstraints::addInductionVarOrTerminalSymbol(Value id) {
   if (containsId(id))
     return;
 
   // Caller is expected to fully compose map/operands if necessary.
   assert((isTopLevelValue(id) || isForInductionVar(id)) &&
          "non-terminal symbol / loop IV expected");
   // Outer loop IVs could be used in forOp's bounds.
   if (auto loop = getForInductionVarOwner(id)) {
     addDimId(getNumDimIds(), id);
     if (failed(this->addAffineForOpDomain(loop)))
       LLVM_DEBUG(
           loop.emitWarning("failed to add domain info to constraint system"));
     return;
   }
   // Add top level symbol.
   addSymbolId(getNumSymbolIds(), id);
   // Check if the symbol is a constant.
   if (auto constOp = id.getDefiningOp<ConstantIndexOp>())
     setIdToConstant(id, constOp.getValue());
 }
 
-LogicalResult FlatAffineConstraints::addAffineForOpDomain(AffineForOp forOp) {
+LogicalResult
+FlatAffineValueConstraints::addAffineForOpDomain(AffineForOp forOp) {
   unsigned pos;
   // Pre-condition for this method.
   if (!findId(forOp.getInductionVar(), &pos)) {
     assert(false && "Value not found");
     return failure();
   }
 
   int64_t step = forOp.getStep();

 /// for a single bound map. All the bound maps will use the same bound
 /// operands. Note that some loops described by a computation slice might not
 /// exist yet in the IR so the Value attached to those dimension identifiers
 /// might be empty. For that reason, this method doesn't perform Value
 /// look-ups to retrieve the dimension identifier positions. Instead, it
 /// assumes the position of the dim identifiers in the constraint system is
 /// the same as the position of the loop in the loop nest.
 LogicalResult
-FlatAffineConstraints::addDomainFromSliceMaps(ArrayRef<AffineMap> lbMaps,
+FlatAffineValueConstraints::addDomainFromSliceMaps(ArrayRef<AffineMap> lbMaps,
                                                    ArrayRef<AffineMap> ubMaps,
                                                    ArrayRef<Value> operands) {
   assert(lbMaps.size() == ubMaps.size());
   assert(lbMaps.size() <= getNumDimIds());
 
   for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
     AffineMap lbMap = lbMaps[i];
     AffineMap ubMap = ubMaps[i];
     assert(!lbMap || lbMap.getNumInputs() == operands.size());
     assert(!ubMap || ubMap.getNumInputs() == operands.size());
for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
 
     if (ubMap && failed(addLowerOrUpperBound(i, ubMap, operands, /*eq=*/false,
                                              /*lower=*/false)))
       return failure();
   }
   return success();
 }
 
-void FlatAffineConstraints::addAffineIfOpDomain(AffineIfOp ifOp) {
+void FlatAffineValueConstraints::addAffineIfOpDomain(AffineIfOp ifOp) {
   // Create the base constraints from the integer set attached to ifOp.
-  FlatAffineConstraints cst(ifOp.getIntegerSet());
+  FlatAffineValueConstraints cst(ifOp.getIntegerSet());
 
   // Bind ids in the constraints to ifOp operands.
   SmallVector<Value, 4> operands = ifOp.getOperands();
   cst.setIdValues(0, cst.getNumDimAndSymbolIds(), operands);
 
   // 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.
void FlatAffineConstraints::normalizeConstraintsByGCD() {
   }
 }
 
 bool FlatAffineConstraints::hasConsistentState() const {
   if (!inequalities.hasConsistentState())
     return false;
   if (!equalities.hasConsistentState())
     return false;
-  if (ids.size() != getNumIds())
-    return false;
 
   // Catches errors where numDims, numSymbols, numIds aren't consistent.
   if (numDims > numIds || numSymbols > numIds || numDims + numSymbols > numIds)
     return false;
 
   return true;
 }
 
+bool FlatAffineValueConstraints::hasConsistentState() const {
+  return FlatAffineConstraints::hasConsistentState() &&
+         ids.size() == getNumIds();
+}
+
 /// 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 FlatAffineConstraints::hasInvalidConstraint() const {
   assert(hasConsistentState());
   auto check = [&](bool isEq) -> bool {
     unsigned numCols = getNumCols();
numLocalsEliminated = std::min(
         idLimit - std::max(idStart, numDims + numSymbols), getNumLocalIds());
   }
   unsigned numSymbolsEliminated =
       numColsEliminated - numDimsEliminated - numLocalsEliminated;
 
   numDims -= numDimsEliminated;
   numSymbols -= numSymbolsEliminated;
   numIds = numIds - numColsEliminated;
+}
 
+void FlatAffineValueConstraints::removeIdRange(unsigned idStart,
+                                               unsigned idLimit) {
+  FlatAffineConstraints::removeIdRange(idStart, idLimit);
   ids.erase(ids.begin() + idStart, ids.begin() + idLimit);
 }
 
 /// 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.
ineq[getNumCols() - 1] =
               // Upper bound in flattenedExpr is an exclusive one.
               : flatExpr[flatExpr.size() - 1] - 1;
     eq ? addEquality(ineq) : addInequality(ineq);
   }
 
   return success();
 }
 
-AffineMap FlatAffineConstraints::computeAlignedMap(AffineMap map,
-                                                   ValueRange operands) const {
+AffineMap
+FlatAffineValueConstraints::computeAlignedMap(AffineMap map,
   assert(map.getNumInputs() == operands.size() && "number of inputs mismatch");
 
   SmallVector<Value> dims, syms;
 #ifndef NDEBUG
   SmallVector<Value> newSyms;
   SmallVector<Value> *newSymsPtr = &newSyms;
 #else
   SmallVector<Value> *newSymsPtr = nullptr;
AffineMap alignedMap =
       alignAffineMapWithValues(map, operands, dims, syms, newSymsPtr);
   // All symbols are already part of this FlatAffineConstraints.
   assert(syms.size() == newSymsPtr->size() && "unexpected new/missing symbols");
   assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
          "unexpected new/missing symbols");
   return alignedMap;
 }
 
-LogicalResult
-FlatAffineConstraints::addLowerOrUpperBound(unsigned pos, AffineMap boundMap,
-                                            ValueRange boundOperands, bool eq,
-                                            bool lower) {
+LogicalResult FlatAffineValueConstraints::addLowerOrUpperBound(
+    unsigned pos, AffineMap boundMap, ValueRange boundOperands, bool eq,
   // Fully compose map and operands; canonicalize and simplify so that we
   // transitively get to terminal symbols or loop IVs.
   auto map = boundMap;
   SmallVector<Value, 4> operands(boundOperands.begin(), boundOperands.end());
   fullyComposeAffineMapAndOperands(&map, &operands);
   map = simplifyAffineMap(map);
   canonicalizeMapAndOperands(&map, &operands);
   for (auto operand : operands)
     addInductionVarOrTerminalSymbol(operand);
   return addLowerOrUpperBound(pos, computeAlignedMap(map, operands), eq, lower);
 }
 
 // Adds slice lower bounds represented by lower bounds in 'lbMaps' and upper
 // bounds in 'ubMaps' to each value in `values' that appears in the constraint
 // system. Note that both lower/upper bounds share the same operand list
 // 'operands'.
 // This function assumes 'values.size' == 'lbMaps.size' == 'ubMaps.size', and
 // skips any null AffineMaps in 'lbMaps' or 'ubMaps'.
 // Note that both lower/upper bounds use operands from 'operands'.
 // Returns failure for unimplemented cases such as semi-affine expressions or
 // expressions with mod/floordiv.
-LogicalResult FlatAffineConstraints::addSliceBounds(ArrayRef<Value> values,
-                                                    ArrayRef<AffineMap> lbMaps,
-                                                    ArrayRef<AffineMap> ubMaps,
-                                                    ArrayRef<Value> operands) {
+LogicalResult FlatAffineValueConstraints::addSliceBounds(
+    ArrayRef<Value> values, ArrayRef<AffineMap> lbMaps,
+    ArrayRef<AffineMap> ubMaps, ArrayRef<Value> operands) {
   assert(values.size() == lbMaps.size());
   assert(lbMaps.size() == ubMaps.size());
 
   for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
     unsigned pos;
     if (!findId(values[i], &pos))
       continue;
 
void FlatAffineConstraints::addLocalFloorDiv(ArrayRef<int64_t> dividend,
 
   // -dividend +qdivisor * q + divisor - 1 >= 0
   std::transform(bound.begin(), bound.end(), bound.begin(),
                  std::negate<int64_t>());
   bound[bound.size() - 1] += divisor - 1;
   addInequality(bound);
 }
 
-bool FlatAffineConstraints::findId(Value id, unsigned *pos) const {
+bool FlatAffineValueConstraints::findId(Value id, unsigned *pos) const {
   unsigned i = 0;
   for (const auto &mayBeId : ids) {
     if (mayBeId.hasValue() && mayBeId.getValue() == id) {
       *pos = i;
       return true;
     }
     i++;
   }
   return false;
 }
 
-bool FlatAffineConstraints::containsId(Value id) const {
+bool FlatAffineValueConstraints::containsId(Value id) const {
   return llvm::any_of(ids, [&](const Optional<Value> &mayBeId) {
     return mayBeId.hasValue() && mayBeId.getValue() == id;
   });
 }
 
 void FlatAffineConstraints::swapId(unsigned posA, unsigned posB) {
   assert(posA < getNumIds() && "invalid position A");
   assert(posB < getNumIds() && "invalid position B");
 
   if (posA == posB)
     return;
 
   for (unsigned r = 0, e = getNumInequalities(); r < e; r++)
     std::swap(atIneq(r, posA), atIneq(r, posB));
   for (unsigned r = 0, e = getNumEqualities(); r < e; r++)
     std::swap(atEq(r, posA), atEq(r, posB));
+}
+
+void FlatAffineValueConstraints::swapId(unsigned posA, unsigned posB) {
+  FlatAffineConstraints::swapId(posA, posB);
   std::swap(getId(posA), getId(posB));
 }
 
 void FlatAffineConstraints::setDimSymbolSeparation(unsigned newSymbolCount) {
   assert(newSymbolCount <= numDims + numSymbols &&
          "invalid separation position");
   numDims = numDims + numSymbols - newSymbolCount;
   numSymbols = newSymbolCount;
 }
 
 /// Sets the specified identifier to a constant value.
 void FlatAffineConstraints::setIdToConstant(unsigned pos, int64_t val) {
   equalities.resizeVertically(equalities.getNumRows() + 1);
   unsigned row = equalities.getNumRows() - 1;
   equalities(row, pos) = 1;
   equalities(row, getNumCols() - 1) = -val;
 }
 
 /// Sets the specified identifier to a constant value; asserts if the id is not
 /// found.
-void FlatAffineConstraints::setIdToConstant(Value id, int64_t val) {
+void FlatAffineValueConstraints::setIdToConstant(Value id, int64_t val) {
   unsigned pos;
   if (!findId(id, &pos))
     // This is a pre-condition for this method.
     assert(0 && "id not found");
   setIdToConstant(pos, val);
 }
 
 void FlatAffineConstraints::removeEquality(unsigned pos) {

 
 void FlatAffineConstraints::print(raw_ostream &os) const {
   assert(hasConsistentState());
   os << "\nConstraints (" << getNumDimIds() << " dims, " << getNumSymbolIds()
      << " symbols, " << getNumLocalIds() << " locals), (" << getNumConstraints()
      << " constraints)\n";
   os << "(";
   for (unsigned i = 0, e = getNumIds(); i < e; i++) {
-    if (ids[i] == None)
-      os << "None ";
-    else
+    if (auto *valueCstr = dyn_cast<const FlatAffineValueConstraints>(this)) {
+      if (valueCstr->hasIdValue(i))
         os << "Value ";
+      else
+        os << "None ";
+    } else {
+      os << "None ";
+    }
   }
   os << " const)\n";
   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";
   }
if (!redunIneq[r])
       inequalities.copyRow(r, pos++);
 
   inequalities.resizeVertically(pos);
 
   // TODO: consider doing this for equalities as well, but probably not worth
   // the savings.
 }
 
 void FlatAffineConstraints::clearAndCopyFrom(
     const FlatAffineConstraints &other) {
-  FlatAffineConstraints copy(other);
-  std::swap(*this, copy);
-  assert(copy.getNumIds() == copy.getIds().size());
+  if (auto *otherValueSet = dyn_cast<const FlatAffineValueConstraints>(&other))
+    assert(!otherValueSet->hasIdValues() &&
+           "cannot copy associated Values into FlatAffineConstraints");
+  // Note: Assigment operator does not vtable pointer, so kind does not change.
+  *this = other;
+}
+
+void FlatAffineValueConstraints::clearAndCopyFrom(
+    const FlatAffineConstraints &other) {
+  if (auto *otherValueSet =
+          dyn_cast<const FlatAffineValueConstraints>(&other)) {
+    *this = *otherValueSet;
+  } else {
+    *static_cast<FlatAffineConstraints *>(this) = other;
+    ids.clear();
+    ids.resize(numIds, None);
+  }
 }
 
 void FlatAffineConstraints::removeId(unsigned pos) {
   removeIdRange(pos, pos + 1);
 }
 
 static std::pair<unsigned, unsigned>
 getNewNumDimsSymbols(unsigned pos, const FlatAffineConstraints &cst) {
   unsigned numDims = cst.getNumDimIds();
for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
     }
   }
 
   // Set the number of dimensions, symbols in the resulting system.
   const auto &dimsSymbols = getNewNumDimsSymbols(pos, *this);
   unsigned newNumDims = dimsSymbols.first;
   unsigned newNumSymbols = dimsSymbols.second;
 
-  SmallVector<Optional<Value>, 8> newIds;
-  newIds.reserve(numIds - 1);
-  newIds.append(ids.begin(), ids.begin() + pos);
-  newIds.append(ids.begin() + pos + 1, ids.end());
-
   /// Create the new system which has one identifier less.
   FlatAffineConstraints newFac(
       lbIndices.size() * ubIndices.size() + nbIndices.size(),
       getNumEqualities(), getNumCols() - 1, newNumDims, newNumSymbols,
-      /*numLocals=*/getNumIds() - 1 - newNumDims - newNumSymbols, newIds);
-
-  assert(newFac.getIds().size() == newFac.getNumIds());
+      /*numLocals=*/getNumIds() - 1 - newNumDims - newNumSymbols);
 
   // 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
void FlatAffineConstraints::fourierMotzkinEliminate(
   clearAndCopyFrom(newFac);
   LLVM_DEBUG(llvm::dbgs() << "FM output:\n");
   LLVM_DEBUG(dump());
 }
 
 #undef DEBUG_TYPE
 #define DEBUG_TYPE "affine-structures"
 
+void FlatAffineValueConstraints::fourierMotzkinEliminate(
+    unsigned pos, bool darkShadow, bool *isResultIntegerExact) {
+  SmallVector<Optional<Value>, 8> newIds;
+  newIds.reserve(numIds - 1);
+  newIds.append(ids.begin(), ids.begin() + pos);
+  newIds.append(ids.begin() + pos + 1, ids.end());
+  // Note: Base implementation discards all associated Values.
+  FlatAffineConstraints::fourierMotzkinEliminate(pos, darkShadow,
+                                                 isResultIntegerExact);
+  ids = newIds;
+  assert(getIds().size() == getNumIds());
+}
+
 void FlatAffineConstraints::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");
 
void FlatAffineConstraints::projectOut(unsigned pos, unsigned num) {
 
   // Fast/trivial simplifications.
   gcdTightenInequalities();
   // Normalize constraints after tightening since the latter impacts this, but
   // not the other way round.
   normalizeConstraintsByGCD();
 }
 
-void FlatAffineConstraints::projectOut(Value id) {
+void FlatAffineValueConstraints::projectOut(Value id) {
   unsigned pos;
   bool ret = findId(id, &pos);
   assert(ret);
   (void)ret;
   fourierMotzkinEliminate(pos);
 }
 
 void FlatAffineConstraints::clearConstraints() {
static void getCommonConstraints(const FlatAffineConstraints &a,
   }
 }
 
 // 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
 FlatAffineConstraints::unionBoundingBox(const FlatAffineConstraints &otherCst) {
   assert(otherCst.getNumDimIds() == numDims && "dims mismatch");
-  assert(otherCst.getIds()
-             .slice(0, getNumDimIds())
-             .equals(getIds().slice(0, getNumDimIds())) &&
-         "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.
-  Optional<FlatAffineConstraints> otherCopy;
-  if (!areIdsAligned(*this, otherCst)) {
-    otherCopy.emplace(FlatAffineConstraints(otherCst));
-    mergeAndAlignIds(/*offset=*/numDims, this, &otherCopy.getValue());
-  }
-
-  const auto &otherAligned = otherCopy ? *otherCopy : otherCst;
-
   // Get the constraints common to both systems; these will be added as is to
   // the union.
   FlatAffineConstraints commonCst;
-  getCommonConstraints(*this, otherAligned, 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.
   SmallVector<int64_t, 4> lb, otherLb, ub, otherUb;
   // To compute min of lower bounds and max of upper bounds for each dimension.
   SmallVector<int64_t, 4> minLb(getNumSymbolIds() + 1);
   SmallVector<int64_t, 4> maxUb(getNumSymbolIds() + 1);
   // To compute final new lower and upper bounds for the union.
   SmallVector<int64_t, 8> newLb(getNumCols()), newUb(getNumCols());
 
   int64_t lbFloorDivisor, otherLbFloorDivisor;
   for (unsigned d = 0, e = getNumDimIds(); d < e; ++d) {
     auto extent = getConstantBoundOnDimSize(d, &lb, &lbFloorDivisor, &ub);
     if (!extent.hasValue())
       // TODO: symbolic extents when necessary.
       // TODO: handle union if a dimension is unbounded.
       return failure();
 
-    auto otherExtent = otherAligned.getConstantBoundOnDimSize(
+    auto otherExtent = otherCst.getConstantBoundOnDimSize(
         d, &otherLb, &otherLbFloorDivisor, &otherUb);
     if (!otherExtent.hasValue() || lbFloorDivisor != otherLbFloorDivisor)
       // TODO: symbolic extents when necessary.
       return failure();
 
     assert(lbFloorDivisor > 0 && "divisor always expected to be positive");
 
     auto res = compareBounds(lb, otherLb);
     // Identify min.
     if (res == BoundCmpResult::Less || res == BoundCmpResult::Equal) {
       minLb = lb;
       // Since the divisor is for a floordiv, we need to convert to ceildiv,
       // i.e., i >= expr floordiv div <=> i >= (expr - div + 1) ceildiv div <=>
       // div * i >= expr - div + 1.
       minLb.back() -= lbFloorDivisor - 1;
     } else if (res == BoundCmpResult::Greater) {
       minLb = otherLb;
       minLb.back() -= otherLbFloorDivisor - 1;
     } else {
       // Uncomparable - check for constant lower/upper bounds.
       auto constLb = getConstantLowerBound(d);
-      auto constOtherLb = otherAligned.getConstantLowerBound(d);
+      auto constOtherLb = otherCst.getConstantLowerBound(d);
       if (!constLb.hasValue() || !constOtherLb.hasValue())
         return failure();
       std::fill(minLb.begin(), minLb.end(), 0);
       minLb.back() = std::min(constLb.getValue(), constOtherLb.getValue());
     }
 
     // Do the same for ub's but max of upper bounds. Identify max.
     auto uRes = compareBounds(ub, otherUb);
     if (uRes == BoundCmpResult::Greater || uRes == BoundCmpResult::Equal) {
       maxUb = ub;
     } else if (uRes == BoundCmpResult::Less) {
       maxUb = otherUb;
     } else {
       // Uncomparable - check for constant lower/upper bounds.
       auto constUb = getConstantUpperBound(d);
-      auto constOtherUb = otherAligned.getConstantUpperBound(d);
+      auto constOtherUb = otherCst.getConstantUpperBound(d);
       if (!constUb.hasValue() || !constOtherUb.hasValue())
         return failure();
       std::fill(maxUb.begin(), maxUb.end(), 0);
       maxUb.back() = std::max(constUb.getValue(), constOtherUb.getValue());
     }
 
     std::fill(newLb.begin(), newLb.end(), 0);
     std::fill(newUb.begin(), newUb.end(), 0);
FlatAffineConstraints::unionBoundingBox(const FlatAffineConstraints &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();
 }
 
+LogicalResult FlatAffineValueConstraints::unionBoundingBox(
+    const FlatAffineValueConstraints &otherCst) {
+  assert(otherCst.getNumDimIds() == numDims && "dims mismatch");
+  assert(otherCst.getIds()
+             .slice(0, getNumDimIds())
+             .equals(getIds().slice(0, getNumDimIds())) &&
+         "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=*/numDims, this, &otherCopy);
+    return FlatAffineConstraints::unionBoundingBox(otherCopy);
+  }
+
+  return FlatAffineConstraints::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,
                                       SmallVectorImpl<AffineExpr> &memo,
                                       MLIRContext *context) {
   unsigned numDims = cst.getNumDimIds();
   unsigned numSyms = cst.getNumSymbolIds();
static LogicalResult computeLocalVars(const FlatAffineConstraints &cst,
   } while (changed);
 
   ArrayRef<AffineExpr> localExprs =
       ArrayRef<AffineExpr>(memo).take_back(cst.getNumLocalIds());
   return success(
       llvm::all_of(localExprs, [](AffineExpr expr) { return expr; }));
 }
 
-void FlatAffineConstraints::getIneqAsAffineValueMap(
+void FlatAffineValueConstraints::getIneqAsAffineValueMap(
     unsigned pos, unsigned ineqPos, AffineValueMap &vmap,
     MLIRContext *context) const {
   unsigned numDims = getNumDimIds();
   unsigned numSyms = getNumSymbolIds();
 
   assert(pos < numDims && "invalid position");
   assert(ineqPos < getNumInequalities() && "invalid inequality position");
 

mlir/lib/Analysis/Utils.cpp

void mlir::getEnclosingAffineForAndIfOps(Operation &op,
   while (currOp) {
     if (isa<AffineIfOp, AffineForOp>(currOp))
       ops->push_back(currOp);
     currOp = currOp->getParentOp();
   }
   std::reverse(ops->begin(), ops->end());
 }
 
-// Populates 'cst' with FlatAffineConstraints which represent original domain of
-// the loop bounds that define 'ivs'.
+// Populates 'cst' with FlatAffineValueConstraints which represent original
+// domain of the loop bounds that define 'ivs'.
 LogicalResult
-ComputationSliceState::getSourceAsConstraints(FlatAffineConstraints &cst) {
+ComputationSliceState::getSourceAsConstraints(FlatAffineValueConstraints &cst) {
   assert(!ivs.empty() && "Cannot have a slice without its IVs");
   cst.reset(/*numDims=*/ivs.size(), /*numSymbols=*/0, /*numLocals=*/0, ivs);
   for (Value iv : ivs) {
     AffineForOp loop = getForInductionVarOwner(iv);
     assert(loop && "Expected affine for");
     if (failed(cst.addAffineForOpDomain(loop)))
       return failure();
   }
   return success();
 }
 
-// Populates 'cst' with FlatAffineConstraints which represent slice bounds.
+// Populates 'cst' with FlatAffineValueConstraints which represent slice bounds.
 LogicalResult
-ComputationSliceState::getAsConstraints(FlatAffineConstraints *cst) {
+ComputationSliceState::getAsConstraints(FlatAffineValueConstraints *cst) {
   assert(!lbOperands.empty());
   // Adds src 'ivs' as dimension identifiers in 'cst'.
   unsigned numDims = ivs.size();
   // Adds operands (dst ivs and symbols) as symbols in 'cst'.
   unsigned numSymbols = lbOperands[0].size();
 
   SmallVector<Value, 4> values(ivs);
   // Append 'ivs' then 'operands' to 'values'.
Optional<bool> ComputationSliceState::isSliceValid() {
   // expensive analysis.
   // TODO: Store the result of the fast check, as it might be used again in
   // `canRemoveSrcNodeAfterFusion`.
   Optional<bool> isValidFastCheck = isSliceMaximalFastCheck();
   if (isValidFastCheck.hasValue() && isValidFastCheck.getValue())
     return true;
 
   // Create constraints for the source loop nest using which slice is computed.
-  FlatAffineConstraints srcConstraints;
+  FlatAffineValueConstraints srcConstraints;
   // TODO: Store the source's domain to avoid computation at each depth.
   if (failed(getSourceAsConstraints(srcConstraints))) {
     LLVM_DEBUG(llvm::dbgs() << "Unable to compute source's domain\n");
     return llvm::None;
   }
   // As the set difference utility currently cannot handle symbols in its
   // operands, validity of the slice cannot be determined.
   if (srcConstraints.getNumSymbolIds() > 0) {
     LLVM_DEBUG(llvm::dbgs() << "Cannot handle symbols in source domain\n");
     return llvm::None;
   }
   // TODO: Handle local ids in the source domains while using the 'projectOut'
   // utility below. Currently, aligning is not done assuming that there will be
   // no local ids in the source domain.
   if (srcConstraints.getNumLocalIds() != 0) {
     LLVM_DEBUG(llvm::dbgs() << "Cannot handle locals in source domain\n");
     return llvm::None;
   }
 
   // Create constraints for the slice loop nest that would be created if the
   // fusion succeeds.
-  FlatAffineConstraints sliceConstraints;
+  FlatAffineValueConstraints sliceConstraints;
   if (failed(getAsConstraints(&sliceConstraints))) {
     LLVM_DEBUG(llvm::dbgs() << "Unable to compute slice's domain\n");
     return llvm::None;
   }
 
   // Projecting out every dimension other than the 'ivs' to express slice's
   // domain completely in terms of source's IVs.
   sliceConstraints.projectOut(ivs.size(),

 Optional<bool> ComputationSliceState::isMaximal() const {
   // Fast check to determine if the computation slice is maximal. If the result
   // is inconclusive, we proceed with a more expensive analysis.
   Optional<bool> isMaximalFastCheck = isSliceMaximalFastCheck();
   if (isMaximalFastCheck.hasValue())
     return isMaximalFastCheck;
 
   // Create constraints for the src loop nest being sliced.
-  FlatAffineConstraints srcConstraints;
+  FlatAffineValueConstraints srcConstraints;
   srcConstraints.reset(/*numDims=*/ivs.size(), /*numSymbols=*/0,
                        /*numLocals=*/0, ivs);
   for (Value iv : ivs) {
     AffineForOp loop = getForInductionVarOwner(iv);
     assert(loop && "Expected affine for");
     if (failed(srcConstraints.addAffineForOpDomain(loop)))
       return llvm::None;
   }
 
   // Create constraints for the slice using the dst loop nest information. We
   // retrieve existing dst loops from the lbOperands.
   SmallVector<Value, 8> consumerIVs;
   for (Value lbOp : lbOperands[0])
     if (getForInductionVarOwner(lbOp))
       consumerIVs.push_back(lbOp);
 
   // Add empty IV Values for those new loops that are not equalities and,
   // therefore, are not yet materialized in the IR.
   for (int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)
     consumerIVs.push_back(Value());
 
-  FlatAffineConstraints sliceConstraints;
+  FlatAffineValueConstraints sliceConstraints;
   sliceConstraints.reset(/*numDims=*/consumerIVs.size(), /*numSymbols=*/0,
                          /*numLocals=*/0, consumerIVs);
 
   if (failed(sliceConstraints.addDomainFromSliceMaps(lbs, ubs, lbOperands[0])))
     return llvm::None;
 
   if (srcConstraints.getNumDimIds() != sliceConstraints.getNumDimIds())
     // Constraint dims are different. The integer set difference can't be
for (auto &op : *block) {
     }
     return nullptr;
   }
   return nullptr;
 }
 
 // Adds loop IV bounds to 'cst' for loop IVs not found in 'ivs'.
 static LogicalResult addMissingLoopIVBounds(SmallPtrSet<Value, 8> &ivs,
-                                            FlatAffineConstraints *cst) {
+                                            FlatAffineValueConstraints *cst) {
   for (unsigned i = 0, e = cst->getNumDimIds(); i < e; ++i) {
     auto value = cst->getIdValue(i);
     if (ivs.count(value) == 0) {
       assert(isForInductionVar(value));
       auto loop = getForInductionVarOwner(value);
       if (failed(cst->addAffineForOpDomain(loop)))
         return failure();
     }

 /// union was computed correctly, an appropriate failure otherwise.
 SliceComputationResult
 mlir::computeSliceUnion(ArrayRef<Operation *> opsA, ArrayRef<Operation *> opsB,
                         unsigned loopDepth, unsigned numCommonLoops,
                         bool isBackwardSlice,
                         ComputationSliceState *sliceUnion) {
   // Compute the union of slice bounds between all pairs in 'opsA' and
   // 'opsB' in 'sliceUnionCst'.
-  FlatAffineConstraints sliceUnionCst;
+  FlatAffineValueConstraints sliceUnionCst;
   assert(sliceUnionCst.getNumDimAndSymbolIds() == 0);
   std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
   for (unsigned i = 0, numOpsA = opsA.size(); i < numOpsA; ++i) {
     MemRefAccess srcAccess(opsA[i]);
     for (unsigned j = 0, numOpsB = opsB.size(); j < numOpsB; ++j) {
       MemRefAccess dstAccess(opsB[j]);
       if (srcAccess.memref != dstAccess.memref)
         continue;
       // Check if 'loopDepth' exceeds nesting depth of src/dst ops.
       if ((!isBackwardSlice && loopDepth > getNestingDepth(opsA[i])) ||
           (isBackwardSlice && loopDepth > getNestingDepth(opsB[j]))) {
         LLVM_DEBUG(llvm::dbgs() << "Invalid loop depth\n");
         return SliceComputationResult::GenericFailure;
       }
 
       bool readReadAccesses = isa<AffineReadOpInterface>(srcAccess.opInst) &&
                               isa<AffineReadOpInterface>(dstAccess.opInst);
-      FlatAffineConstraints dependenceConstraints;
+      FlatAffineValueConstraints dependenceConstraints;
       // Check dependence between 'srcAccess' and 'dstAccess'.
       DependenceResult result = checkMemrefAccessDependence(
           srcAccess, dstAccess, /*loopDepth=*/numCommonLoops + 1,
           &dependenceConstraints, /*dependenceComponents=*/nullptr,
           /*allowRAR=*/readReadAccesses);
       if (result.value == DependenceResult::Failure) {
         LLVM_DEBUG(llvm::dbgs() << "Dependence check failed\n");
         return SliceComputationResult::GenericFailure;
for (unsigned j = 0, numOpsB = opsB.size(); j < numOpsB; ++j) {
                      << "Unable to compute slice bound constraints\n");
           return SliceComputationResult::GenericFailure;
         }
         assert(sliceUnionCst.getNumDimAndSymbolIds() > 0);
         continue;
       }
 
       // Compute constraints for 'tmpSliceState' in 'tmpSliceCst'.
-      FlatAffineConstraints tmpSliceCst;
+      FlatAffineValueConstraints tmpSliceCst;
       if (failed(tmpSliceState.getAsConstraints(&tmpSliceCst))) {
         LLVM_DEBUG(llvm::dbgs()
                    << "Unable to compute slice bound constraints\n");
         return SliceComputationResult::GenericFailure;
       }
 
       // Align coordinate spaces of 'sliceUnionCst' and 'tmpSliceCst' if needed.
       if (!sliceUnionCst.areIdsAlignedWithOther(tmpSliceCst)) {

 
 const char *const kSliceFusionBarrierAttrName = "slice_fusion_barrier";
 // Computes slice bounds by projecting out any loop IVs from
 // 'dependenceConstraints' at depth greater than 'loopDepth', and computes slice
 // bounds in 'sliceState' which represent the one loop nest's IVs in terms of
 // the other loop nest's IVs, symbols and constants (using 'isBackwardsSlice').
 void mlir::getComputationSliceState(
     Operation *depSourceOp, Operation *depSinkOp,
-    FlatAffineConstraints *dependenceConstraints, unsigned loopDepth,
+    FlatAffineValueConstraints *dependenceConstraints, unsigned loopDepth,
     bool isBackwardSlice, ComputationSliceState *sliceState) {
   // Get loop nest surrounding src operation.
   SmallVector<AffineForOp, 4> srcLoopIVs;
   getLoopIVs(*depSourceOp, &srcLoopIVs);
   unsigned numSrcLoopIVs = srcLoopIVs.size();
 
   // Get loop nest surrounding dst operation.
   SmallVector<AffineForOp, 4> dstLoopIVs;

mlir/lib/Dialect/Affine/Transforms/AffineScalarReplacement.cpp

if (auto memEffect = dyn_cast<MemoryEffectOpInterface>(op)) {
       // If the side effect comes from an affine read or write, try to
       // prove the side effecting `op` cannot reach `memOp`.
       if (isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) {
         MemRefAccess srcAccess(op);
         MemRefAccess destAccess(memOp);
         // Dependence analysis is only correct if both ops operate on the same
         // memref.
         if (srcAccess.memref == destAccess.memref) {
-          FlatAffineConstraints dependenceConstraints;
+          FlatAffineValueConstraints dependenceConstraints;
 
           // Number of loops containing the start op and the ending operation.
           unsigned minSurroundingLoops =
               getNumCommonSurroundingLoops(*start, *memOp);
 
           // Number of loops containing the operation `op` which has the
           // potential memory side effect and can occur on a path between
           // `start` and `memOp`.

mlir/lib/Transforms/LoopFusion.cpp

static Value createPrivateMemRef(AffineForOp forOp, Operation *srcStoreOpInst,
   lbs.reserve(rank);
   // Query 'region' for 'newShape' and lower bounds of MemRefRegion accessed
   // by 'srcStoreOpInst' at depth 'dstLoopDepth'.
   Optional<int64_t> numElements =
       region.getConstantBoundingSizeAndShape(&newShape, &lbs, &lbDivisors);
   assert(numElements.hasValue() &&
          "non-constant number of elts in local buffer");
 
-  const FlatAffineConstraints *cst = region.getConstraints();
+  const FlatAffineValueConstraints *cst = region.getConstraints();
   // 'outerIVs' holds the values that this memory region is symbolic/parametric
   // on; this would correspond to loop IVs surrounding the level at which the
   // slice is being materialized.
   SmallVector<Value, 8> outerIVs;
   cst->getIdValues(rank, cst->getNumIds(), &outerIVs);
 
   // Build 'rank' AffineExprs from MemRefRegion 'lbs'
   SmallVector<AffineExpr, 4> offsets;

mlir/lib/Transforms/Utils/LoopFusionUtils.cpp

for (unsigned i = 0, e = targetDstOps.size(); i < e; ++i) {
     MemRefAccess srcAccess(srcOpInst);
     for (unsigned j = 0; j < e; ++j) {
       auto *dstOpInst = targetDstOps[j];
       MemRefAccess dstAccess(dstOpInst);
 
       unsigned numCommonLoops =
           getNumCommonSurroundingLoops(*srcOpInst, *dstOpInst);
       for (unsigned d = 1; d <= numCommonLoops + 1; ++d) {
-        FlatAffineConstraints dependenceConstraints;
+        FlatAffineValueConstraints dependenceConstraints;
         // TODO: Cache dependence analysis results, check cache here.
         DependenceResult result = checkMemrefAccessDependence(
             srcAccess, dstAccess, d, &dependenceConstraints,
             /*dependenceComponents=*/nullptr);
         if (hasDependence(result)) {
           // Store minimum loop depth and break because we want the min 'd' at
           // which there is a dependence.
           loopDepth = std::min(loopDepth, d - 1);

mlir/lib/Transforms/Utils/LoopUtils.cpp

checkTilingLegalityImpl(MutableArrayRef<mlir::AffineForOp> origLoops) {
   SmallVector<Operation *, 8> loadAndStoreOps;
   origLoops[0]->walk([&](Operation *op) {
     if (isa<AffineReadOpInterface, AffineWriteOpInterface>(op))
       loadAndStoreOps.push_back(op);
   });
 
   unsigned numOps = loadAndStoreOps.size();
   unsigned numLoops = origLoops.size();
-  FlatAffineConstraints dependenceConstraints;
+  FlatAffineValueConstraints dependenceConstraints;
   for (unsigned d = 1; d <= numLoops + 1; ++d) {
     for (unsigned i = 0; i < numOps; ++i) {
       Operation *srcOp = loadAndStoreOps[i];
       MemRefAccess srcAccess(srcOp);
       for (unsigned j = 0; j < numOps; ++j) {
         Operation *dstOp = loadAndStoreOps[j];
         MemRefAccess dstAccess(dstOp);
 
void constructTiledLoopNest(MutableArrayRef<AffineForOp> origLoops,
   // Move the loop body of the original nest to the new one.
   moveLoopBody(origLoops.back(), innermostPointLoop);
 }
 
 /// Checks whether a loop nest is hyper-rectangular or not.
 LogicalResult checkIfHyperRectangular(MutableArrayRef<AffineForOp> input,
                                       AffineForOp rootAffineForOp,
                                       unsigned width) {
-  FlatAffineConstraints cst;
+  FlatAffineValueConstraints cst;
   SmallVector<Operation *, 8> ops(input.begin(), input.end());
   (void)getIndexSet(ops, &cst);
   if (!cst.isHyperRectangular(0, width)) {
     rootAffineForOp.emitError("tiled code generation unimplemented for the "
                               "non-hyperrectangular case");
     return failure();
   }
   return success();
if (numElements.getValue() == 0) {
     *sizeInBytes = 0;
     return success();
   }
 
   SmallVector<AffineMap, 4> lbMaps(rank), ubMaps(rank);
   for (unsigned i = 0; i < rank; ++i)
     region.getLowerAndUpperBound(i, lbMaps[i], ubMaps[i]);
 
-  const FlatAffineConstraints *cst = region.getConstraints();
+  const FlatAffineValueConstraints *cst = region.getConstraints();
   // 'regionSymbols' hold values that this memory region is symbolic/parametric
   // on; these typically include loop IVs surrounding the level at which the
   // copy generation is being done or other valid symbols in MLIR.
   SmallVector<Value, 8> regionSymbols;
   cst->getIdValues(rank, cst->getNumIds(), &regionSymbols);
 
   // Construct the index expressions for the fast memory buffer. The index
   // expression for a particular dimension of the fast buffer is obtained by

 /// insertion point of `b`.
 static AffineIfOp createSeparationCondition(MutableArrayRef<AffineForOp> loops,
                                             OpBuilder b) {
   if (loops.empty())
     return nullptr;
 
   auto *context = loops[0].getContext();
 
-  FlatAffineConstraints cst;
+  FlatAffineValueConstraints cst;
   SmallVector<Operation *, 8> ops;
   ops.reserve(loops.size());
   for (AffineForOp forOp : loops)
     ops.push_back(forOp);
   (void)getIndexSet(ops, &cst);
 
   // Remove constraints that are independent of these loop IVs.
   cst.removeIndependentConstraints(/*pos=*/0, /*num=*/loops.size());

 /// Create the full tile loop nest (along with its body).
 static LogicalResult
 createFullTiles(MutableArrayRef<AffineForOp> inputNest,
                 SmallVectorImpl<AffineForOp> &fullTileLoops, OpBuilder b) {
   fullTileLoops.reserve(inputNest.size());
 
   // For each loop in the original nest identify a lower/upper bound pair such
   // that their difference is a constant.
-  FlatAffineConstraints cst;
+  FlatAffineValueConstraints cst;
   for (auto loop : inputNest) {
     // TODO: straightforward to generalize to a non-unit stride.
     if (loop.getStep() != 1) {
       LLVM_DEBUG(llvm::dbgs()
                  << "[tile separation] non-unit stride not implemented\n");
       return failure();
     }
     SmallVector<Operation *, 1> loopOp{loop.getOperation()};

mlir/test/lib/Analysis/TestMemRefDependenceCheck.cpp

for (unsigned i = 0, e = loadsAndStores.size(); i < e; ++i) {
     MemRefAccess srcAccess(srcOpInst);
     for (unsigned j = 0; j < e; ++j) {
       auto *dstOpInst = loadsAndStores[j];
       MemRefAccess dstAccess(dstOpInst);
 
       unsigned numCommonLoops =
           getNumCommonSurroundingLoops(*srcOpInst, *dstOpInst);
       for (unsigned d = 1; d <= numCommonLoops + 1; ++d) {
-        FlatAffineConstraints dependenceConstraints;
+        FlatAffineValueConstraints dependenceConstraints;
         SmallVector<DependenceComponent, 2> dependenceComponents;
         DependenceResult result = checkMemrefAccessDependence(
             srcAccess, dstAccess, d, &dependenceConstraints,
             &dependenceComponents);
         assert(result.value != DependenceResult::Failure);
         bool ret = hasDependence(result);
         // TODO: Print dependence type (i.e. RAW, etc) and print
         // distance vectors as: ([2, 3], [0, 10]). Also, shorten distance