[mlir] Allow merging symbols without attached Values

[ubfx]

Summary

From the comments and my understanding of the use of this function, the mergeSymbolVars function is supposed to treat Symbols without attached Values as unique and replicate them in the other constraint system. In other words, it should treat a Symbol without an attached Value like a Symbol that it didn't find a match for instead of asserting because some Symbols in either System doesn't have a Value.

[ubfx]

To clarify a little more, because I saw that there have been a few changes to these files recently and I'm not entirely sure whether the current behavior of the function might be intentional:

The comment says

• Merge and align symbols of this and other such that both get union of symbols that are unique
• Symbols with Value as None are considered to be inequal to all other symbols

I think being inequal to all other symbols is the same thing as being unique, so all of the None-Valued symbols should automatically be replicated as new symbols in the other constraint system.

IMHO this also makes sense from a usage standpoint: For Domain and Range variables, forcing their comparable-ness makes sense but with Symbols and Locals, it's not critical.

mlir/lib/Analysis/FlatLinearValueConstraints.cpp

1067

getValues asserts when one of the Symbol vars does not have a Value

[ubfx]

@springerm Since you have been working on a restructuring of the FlatAffineValueConstraints / Affine Analysis classes and are working on the ValueBoundsOpInterface, which all seem related, could you comment on this?

[springerm]

This change makes sense to me. It's been a while since I looked at this particular part of the file though. Could you go back in the Github history and also add the original author of this function? (The file was moved around a few times.)

mlir/lib/Analysis/FlatLinearValueConstraints.cpp

1081–1084

nit: indentation is confusing, wrap this in {}

[ubfx]

In D147345#4242641, @springerm wrote:

This change makes sense to me. It's been a while since I looked at this particular part of the file though. Could you go back in the Github history and also add the original author of this function? (The file was moved around a few times.)

Thank you for your feedback.

I think there is another function that is quite similar and related to this:
https://github.com/llvm/llvm-project/blob/main/mlir/lib/Analysis/FlatLinearValueConstraints.cpp#L1001

Citing from the file:

/// Merge and align the variables of A and B starting at 'offset', so that
/// both constraint systems get the union of the contained variables that is
/// dimension-wise and symbol-wise unique; both constraint systems are updated
/// so that they have the union of all variables, with A's original
/// variables appearing first followed by any of B's variables that didn't
/// appear in A. Local variables in B that have the same division
/// representation as local variables in A are merged into one.
//  E.g.: 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 mergeAndAlignVars(unsigned offset, FlatLinearValueConstraints *a,
                              FlatLinearValueConstraints *b) {

This function works on all Variables independent of their type but forces all the Variables starting at offset to have a Value attached. It seems to me like there is a more general need for a function that does something like this:

mergeAndAlignVars(other, varStart, varLimit, treatNoneValueAsUnique)

• other Other relation
• varStart First variable to consider
• varLimit Last variable to consider
• treatNoneValueAsUnique How to treat variables without a Value attached?
  • If true -> treat them as unique and replicate them in the other Relation following the ordering: this first, other after
  • if false -> return failure (meaning the Relations are incompatible) when encountering Variable without Value

It seems like this could replace both the FlatLinearValueConstraints::mergeSymbolVars and the FlatLinearValueConstraints::mergeAndAlignVars function with a better API.

[ubfx]

Add braces for readability

[ubfx]

merge my commits into one

[Groverkss]

I would not recommend treating symbols as having any values attached to them as unique, as this could lead to an explosion in the number of symbols. Presburger operations are generally chained and let's say you do something like:

x = (x)[N] : ()
for i in range(10):
  x = mergeSymbols(x, x)

This could lead to an explosion in the number of symbols. An assertion is better than allowing this to happen, as this could be very hard to trace back.

Generally, Symbols can be identified in 2 ways. Either they have an attached value associated with them, or their position identifies them.

mlir/lib/Analysis/FlatLinearValueConstraints.cpp

 
 // Call 'mergeAndAlignVars' to align constraint systems of 'this' and 'other'.
 void FlatLinearValueConstraints::mergeAndAlignVarsWithOther(
     unsigned offset, FlatLinearValueConstraints *other) {
   mergeAndAlignVars(offset, this, other);
 }
 
 /// Merge and align symbols of `this` and `other` such that both get union of
-/// of symbols that are unique. Symbols in `this` and `other` should be
-/// unique. Symbols with Value as `None` are considered to be inequal to all
-/// other symbols.
+/// symbols that are unique. The symbols will be ordered with the symbols from
+/// `this` appearing first, then the symbols from `other`. Symbols in `this` and
+/// `other` should be unique. Symbols with Value as `None` are considered to be
+/// inequal to all other symbols.
 void FlatLinearValueConstraints::mergeSymbolVars(
     FlatLinearValueConstraints &other) {
 
   assert(areVarsUnique(*this, VarKind::Symbol) && "Symbol vars are not unique");
   assert(areVarsUnique(other, VarKind::Symbol) && "Symbol vars are not unique");
 
-  SmallVector<Value, 4> aSymValues;
-  getValues(getNumDimVars(), getNumDimAndSymbolVars(), &aSymValues);
+  auto maybeSymValues = getMaybeValues(presburger::VarKind::Symbol);
 
   // Merge symbols: merge symbols into `other` first from `this`.
   unsigned s = other.getNumDimVars();
-  for (Value aSymValue : aSymValues) {
+  for (std::optional<Value> maybeValue : maybeSymValues) {
+    if (maybeValue.has_value()) {
       unsigned loc;
       // If the var is a symbol in `other`, then align it, otherwise assume that
       // it is a new symbol
-    if (other.findVar(aSymValue, &loc) && loc >= other.getNumDimVars() &&
+      if (other.findVar(*maybeValue, &loc) && loc >= other.getNumDimVars() &&
           loc < other.getNumDimAndSymbolVars())
         other.swapVar(s, loc);
       else
-      other.insertSymbolVar(s - other.getNumDimVars(), aSymValue);
+        other.insertSymbolVar(s - other.getNumDimVars(), *maybeValue);
+    } else {
+      // if the symbol has no Value attached, we have to add it as a new symbol
+      // to `other`
+      other.insertSymbolVar(s - other.getNumDimVars());
+    }
     s++;
   }
 
   // Symbols that are in other, but not in this, are added at the end.
   for (unsigned t = other.getNumDimVars() + getNumSymbolVars(),
                 e = other.getNumDimAndSymbolVars();
-       t < e; t++)
+       t < e; t++) {
+    if (other.hasValue(t))
       insertSymbolVar(getNumSymbolVars(), other.getValue(t));
+    else
+      insertSymbolVar(getNumSymbolVars());
+  }
 
   assert(getNumSymbolVars() == other.getNumSymbolVars() &&
          "expected same number of symbols");
   assert(areVarsUnique(*this, VarKind::Symbol) && "Symbol vars are not unique");
   assert(areVarsUnique(other, VarKind::Symbol) && "Symbol vars are not unique");
 }
 
 bool FlatLinearValueConstraints::hasConsistentState() const {