[TableGen] Fix sort order of asm operand classes

[olista01]

Summary

This is a fix for https://llvm.org/bugs/show_bug.cgi?id=22796.

The previous implementation of ClassInfo::operator< allowed cycles of classes such that x < y < z < x, meaning that a list of them cannot be correctly sorted, and the sort order could differ with different standard libraries.

The original implementation sorted classes by ValueName if they were otherwise equal. This isn't strictly necessary, but some backends seem to accidentally rely on it. If I reverse this comparison I get 8 test failures spread across the AArch64, Mips and X86 backends, so I have left it in until those backends can be fixed.

There was one case in the X86 backend where the observable behaviour of the assembler is changed by this patch. This was because some of the memory asm operands were not marked as children of X86MemAsmOperand.

This bug caused my patch to add the ARMv8.2 FP16 AArch32 scalar instructions (http://reviews.llvm.org/rL255762) to fail on windows.

[dexonsmith]

Thanks for working on this!

FWIW this fix looks right to me, but I'm not sure I've ever committed
to tablegen. Please track down someone that knows the code better to
chime in.

+ / operator< - Compare two classes. This does not produce a total ordering,
+ / but does guarantee that subclasses are sorted before their parents, and
+ /// that the ordering is transitive.

Since you're changing the comment anyway, can you update the style
(remove the function name at the start of it)?

[olista01]

Updated doxygen comment style.

[dsanders]

If I reverse this comparison I get 8 test failures spread across the AArch64, Mips and X86 backends, so I have left it in until those backends can be fixed.

The Mips failure is that there's a choice of two accurate error messages and changing the order of these matchables changes which one is emitted. Of the two, the current one is preferable (since it slightly exaggerates its expected values to accommodate both possible matches) but ideally we would be able to emit multiple reasons for a failed match (e.g. 'expected either unsigned 5 bit immediate or values 32..63').

The ValueName is the only available tie breaker at the moment. Superclasses could be used to produce the right effect but it seems wrong to declare one a superclass of the other when the accepted values are distinct sets. At the moment, I'm thinking we should just make the priority explicit using something similar to the AddedComplexity field from instruction selection. Do you agree?

[craig.topper]

utils/TableGen/AsmMatcherEmitter.cpp

267 ↗

(On Diff #45233)

Variable names should be capitalized by coding standards.

1596 ↗

(On Diff #45233)

Can we use std::is_sorted here and the location below?

[craig.topper]

utils/TableGen/AsmMatcherEmitter.cpp

319 ↗

(On Diff #45233)

Should this say "name" instead of "kind"?

[olista01]

utils/TableGen/AsmMatcherEmitter.cpp

1596 ↗

(On Diff #45233)

std::is_sorted just checks adjacent elements, and assumes that operator< is well-behaved, so wouldn't have caught this bug before it started causing (windows-only in my case) test failures.

[craig.topper]

LGTM

llvm/trunk/lib/Target/X86/X86InstrInfo.td

 // the index operand of an address, to conform to x86 encoding restrictions.
 def ptr_rc_nosp : PointerLikeRegClass<1>;
 
 // *mem - Operand definitions for the funky X86 addressing mode operands.
 //
 def X86MemAsmOperand : AsmOperandClass {
  let Name = "Mem";
 }
-let RenderMethod = "addMemOperands" in {
+let RenderMethod = "addMemOperands", SuperClasses = [X86MemAsmOperand] in {
   def X86Mem8AsmOperand   : AsmOperandClass { let Name = "Mem8"; }
   def X86Mem16AsmOperand  : AsmOperandClass { let Name = "Mem16"; }
   def X86Mem32AsmOperand  : AsmOperandClass { let Name = "Mem32"; }
   def X86Mem64AsmOperand  : AsmOperandClass { let Name = "Mem64"; }
   def X86Mem80AsmOperand  : AsmOperandClass { let Name = "Mem80"; }
   def X86Mem128AsmOperand : AsmOperandClass { let Name = "Mem128"; }
   def X86Mem256AsmOperand : AsmOperandClass { let Name = "Mem256"; }
   def X86Mem512AsmOperand : AsmOperandClass { let Name = "Mem512"; }

llvm/trunk/utils/TableGen/AsmMatcherEmitter.cpp

bool isSubsetOf(const ClassInfo &RHS) const {
     // ... or if any of its super classes are a subset of RHS.
     for (const ClassInfo *CI : SuperClasses)
       if (CI->isSubsetOf(RHS))
         return true;
 
     return false;
   }
 
-  /// operator< - Compare two classes.
-  // FIXME: This ordering seems to be broken. For example:
-  // u64 < i64, i64 < s8, s8 < u64, forming a cycle
-  // u64 is a subset of i64
-  // i64 and s8 are not subsets of each other, so are ordered by name
-  // s8 and u64 are not subsets of each other, so are ordered by name
+  int getTreeDepth() const {
+    int Depth = 0;
+    const ClassInfo *Root = this;
+    while (!Root->SuperClasses.empty()) {
+      Depth++;
+      Root = Root->SuperClasses.front();
+    }
+    return Depth;
+  }
+
+  const ClassInfo *findRoot() const {
+    const ClassInfo *Root = this;
+    while (!Root->SuperClasses.empty())
+      Root = Root->SuperClasses.front();
+    return Root;
+  }
+
+  /// Compare two classes. This does not produce a total ordering, but does
+  /// guarantee that subclasses are sorted before their parents, and that the
+  /// ordering is transitive.
   bool operator<(const ClassInfo &RHS) const {
     if (this == &RHS)
       return false;
 
-    // Unrelated classes can be ordered by kind.
-    if (!isRelatedTo(RHS))
-      return Kind < RHS.Kind;
-
-    switch (Kind) {
-    case Invalid:
-      llvm_unreachable("Invalid kind!");
+    // First, enforce the ordering between the three different types of class.
+    // Tokens sort before registers, which sort before user classes.
+    if (Kind == Token) {
+      if (RHS.Kind != Token)
+        return true;
+      assert(RHS.Kind == Token);
+    } else if (isRegisterClass()) {
+      if (RHS.Kind == Token)
+        return false;
+      else if (RHS.isUserClass())
+        return true;
+      assert(RHS.isRegisterClass());
+    } else if (isUserClass()) {
+      if (!RHS.isUserClass())
+        return false;
+      assert(RHS.isUserClass());
+    } else {
+      llvm_unreachable("Unknown ClassInfoKind");
+    }
 
-    default:
-      // This class precedes the RHS if it is a proper subset of the RHS.
-      if (isSubsetOf(RHS))
+    if (Kind == Token || isUserClass()) {
+      // Related tokens and user classes get sorted by depth in the inheritence
+      // tree (so that subclasses are before their parents).
+      if (isRelatedTo(RHS)) {
+        if (getTreeDepth() > RHS.getTreeDepth())
           return true;
-      if (RHS.isSubsetOf(*this))
+        if (getTreeDepth() < RHS.getTreeDepth())
           return false;
+      } else {
+        // Unrelated tokens and user classes are ordered by the name of their
+        // root nodes, so that there is a consistent ordering between
+        // unconnected trees.
+        return findRoot()->ValueName < RHS.findRoot()->ValueName;
+      }
+    } else if (isRegisterClass()) {
+      // For register sets, sort by number of registers. This guarantees that
+      // a set will always sort before all of it's strict supersets.
+      if (Registers.size() != RHS.Registers.size())
+        return Registers.size() < RHS.Registers.size();
+    } else {
+      llvm_unreachable("Unknown ClassInfoKind");
+    }
 
-      // Otherwise, order by name to ensure we have a total ordering.
-      return ValueName < RHS.ValueName;
-    }
-  }
+    // FIXME: We should be able to just return false here, as we only need a
+    // partial order (we use stable sorts, so this is deterministic) and the
+    // name of a class shouldn't be significant. However, some of the backends
+    // accidentally rely on this behaviour, so it will have to stay like this
+    // until they are fixed.
 };
 
 class AsmVariantInfo {
 public:
   std::string RegisterPrefix;
   std::string TokenizingCharacters;
   std::string SeparatorCharacters;
   std::string BreakCharacters;
for (Record *Rec : AllTokenAliases) {
     if (FromClass == ToClass)
       PrintFatalError(Rec->getLoc(),
                     "error: Destination value identical to source value.");
     FromClass->SuperClasses.push_back(ToClass);
   }
 
   // Reorder classes so that classes precede super classes.
   Classes.sort();
+
+#ifndef NDEBUG
+  // Verify that the table is now sorted
+  for (auto I = Classes.begin(), E = Classes.end(); I != E; ++I) {
+    for (auto J = I; J != E; ++J) {
+      assert(!(*J < *I));
+      assert(I == J || !J->isSubsetOf(*I));
+    }
+  }
+#endif
 }
 
 /// buildInstructionOperandReference - The specified operand is a reference to a
 /// named operand such as $src.  Resolve the Class and OperandInfo pointers.
 void AsmMatcherInfo::
 buildInstructionOperandReference(MatchableInfo *II,
                                  StringRef OperandName,
                                  unsigned AsmOpIdx) {
void AsmMatcherEmitter::run(raw_ostream &OS) {
   // Sort the instruction table using the partial order on classes. We use
   // stable_sort to ensure that ambiguous instructions are still
   // deterministically ordered.
   std::stable_sort(Info.Matchables.begin(), Info.Matchables.end(),
                    [](const std::unique_ptr<MatchableInfo> &a,
                       const std::unique_ptr<MatchableInfo> &b){
                      return *a < *b;});
 
+#ifndef NDEBUG
+  // Verify that the table is now sorted
+  for (auto I = Info.Matchables.begin(), E = Info.Matchables.end(); I != E;
+       ++I) {
+    for (auto J = I; J != E; ++J) {
+      assert(!(**J < **I));
+    }
+  }
+#endif
+
   DEBUG_WITH_TYPE("instruction_info", {
       for (const auto &MI : Info.Matchables)
         MI->dump();
     });
 
   // Check for ambiguous matchables.
   DEBUG_WITH_TYPE("ambiguous_instrs", {
     unsigned NumAmbiguous = 0;