[TableGen][GlobalISel] Guarantee stable iteration order for stop-after-parse

[Pierre-vh]

Summary

Builds on top of 6de2735c2428 to fix remaining issues with iteration order in the MatchTable Combiner backend.
See D155789 as well.

[MaskRay]

thank you!

[DavidSpickett]

FYI, I get this warning building a release llvm-tblgen:

/home/davspi01/work/open_source/llvm-project/llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp:672:6: warning: ‘void {anonymous}::CombineRuleBuilder::verify() const’ defined but not used [-Wunused-function]
  672 | void CombineRuleBuilder::verify() const {
      |      ^~~~~~~~~~~~~~~~~~

Presumably because it's called like this:

bool CombineRuleBuilder::parseAll() {
  if (!parseDefs(*RuleDef.getValueAsDag("Defs")))
    return false;
  if (!parseMatch(*RuleDef.getValueAsDag("Match")))
    return false;
  if (!parseApply(*RuleDef.getValueAsDag("Apply")))
    return false;
  if (!buildOperandsTable())
    return false;
  if (!findRoots())
    return false;
  LLVM_DEBUG(verify());
  return true;
}

If you could figure out a way to mark it used in release builds that would be great, as something called verify being unused is always worrying.

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td

def InstTest0 : GICombineRule<
   (match (MOV $a, $b):$d),
   (apply [{ APPLY }])>;
 
 // CHECK:      (CombineRule name:InstTest1 id:3 root:d
 // CHECK-NEXT:   (MatchDatas
 // CHECK-NEXT:      (MatchDataInfo pattern_symbol:r0 type:'Register' var_name:MDInfo0)
 // CHECK-NEXT:   )
 // CHECK-NEXT:   (MatchPats
-// CHECK-NEXT:     __anon_pat_match_3_0:(InstructionPattern inst:ZEXT operands:[<def>x, a])
 // CHECK-NEXT:     <root>d:(InstructionPattern inst:MOV operands:[<def>a, b])
+// CHECK-NEXT:     __anon_pat_match_3_0:(InstructionPattern inst:ZEXT operands:[<def>x, a])
 // CHECK-NEXT:   )
 // CHECK-NEXT:   (ApplyPats
 // CHECK-NEXT:     __anon_pat_apply_3_1:(CXXPattern apply code:"APPLY")
 // CHECK-NEXT:   )
 // CHECK-NEXT:   (OperandTable
-// CHECK-NEXT:     [x match_pat:__anon_pat_match_3_0]
 // CHECK-NEXT:     [a match_pat:d]
 // CHECK-NEXT:     [b live-in]
+// CHECK-NEXT:     [x match_pat:__anon_pat_match_3_0]
 // CHECK-NEXT:   )
 // CHECK-NEXT: )
 let Predicates = [HasAnswerToEverything] in
 def InstTest1 : GICombineRule<
   (defs root:$d, reg_matchinfo:$r0),
   (match (MOV $a, $b):$d,
          (ZEXT $x, $a)),
   (apply [{ APPLY }])>;
 
 def MyCombiner: GICombinerHelper<"GenMyCombiner", [
   WipOpcodeTest0,
   WipOpcodeTest1,
   InstTest0,
   InstTest1
 ]>;

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp

Pattern(unsigned Kind, StringRef Name) : Kind(Kind), Name(Name.str()) {
     assert(!Name.empty() && "unnamed pattern!");
   }
 
   void printImpl(raw_ostream &OS, bool PrintName,
                  function_ref<void()> ContentPrinter) const;
 
 private:
   unsigned Kind;
+
+  // Note: if this ever changes to a StringRef (e.g. allocated in a pool or
+  // something), CombineRuleBuilder::verify() needs to be updated as well.
+  // It currently checks that the StringRef in the PatternMap references this.
   std::string Name;
 };
 
 const char *Pattern::getKindName() const {
   switch (Kind) {
   case K_AnyOpcode:
     return "AnyOpcodePattern";
   case K_Inst:

 /// patterns together and emit RuleMatchers to match them. This may emit more
 /// than one RuleMatcher, e.g. for `wip_match_opcode`.
 ///
 /// Memory management for `Pattern` objects is done through `std::unique_ptr`.
 /// In most cases, there are two stages to a pattern's lifetime:
 ///   - Creation in a `parse` function
 ///     - The unique_ptr is stored in a variable, and may be destroyed if the
 ///       pattern is found to be semantically invalid.
-///   - Ownership transfer into a `PatternStringMap`
+///   - Ownership transfer into a `PatternMap`
 ///     - Once a pattern is moved into either the map of Match or Apply
 ///       patterns, it is known to be valid and it never moves back.
 class CombineRuleBuilder {
 public:
-  using PatternStringMap = StringMap<std::unique_ptr<Pattern>>;
+  using PatternMap = MapVector<StringRef, std::unique_ptr<Pattern>>;
 
   CombineRuleBuilder(const CodeGenTarget &CGT,
                      SubtargetFeatureInfoMap &SubtargetFeatures,
                      Record &RuleDef, unsigned ID,
                      std::vector<RuleMatcher> &OutRMs)
       : CGT(CGT), SubtargetFeatures(SubtargetFeatures), RuleDef(RuleDef),
         RuleID(ID), OutRMs(OutRMs) {}
 
private:
   // For InstructionMatcher::addOperand
   unsigned AllocatedTemporariesBaseID = 0;
 
   /// The root of the pattern.
   StringRef RootName;
 
   /// These maps have ownership of the actual Pattern objects.
   /// They both map a Pattern's name to the Pattern instance.
-  PatternStringMap MatchPats;
-  PatternStringMap ApplyPats;
+  PatternMap MatchPats;
+  PatternMap ApplyPats;
 
   /// Set by findRoots.
   Pattern *MatchRoot = nullptr;
 
   MapVector<StringRef, OperandTableEntry> OperandTable;
   SmallVector<MatchDataInfo, 2> MatchDatas;
 };
 
else {
     for (const auto &MD : MatchDatas) {
       OS << "    ";
       MD.print(OS);
       OS << "\n";
     }
     OS << "  )\n";
   }
 
-  const auto DumpPats = [&](StringRef Name, const PatternStringMap &Pats) {
+  const auto DumpPats = [&](StringRef Name, const PatternMap &Pats) {
     OS << "  (" << Name << " ";
     if (Pats.empty()) {
       OS << "<empty>)\n";
       return;
     }
 
     OS << "\n";
-    for (const auto &P : Pats) {
+    for (const auto &[Name, Pat] : Pats) {
       OS << "    ";
-      if (P.getValue().get() == MatchRoot)
+      if (Pat.get() == MatchRoot)
         OS << "<root>";
-      OS << P.getKey() << ":";
-      P.getValue()->print(OS, /*PrintName=*/false);
+      OS << Name << ":";
+      Pat->print(OS, /*PrintName=*/false);
       OS << "\n";
     }
     OS << "  )\n";
   };
 
   DumpPats("MatchPats", MatchPats);
   DumpPats("ApplyPats", ApplyPats);
 
else {
     }
     OS << "  )\n";
   }
 
   OS << ")\n";
 }
 
 void CombineRuleBuilder::verify() const {
-  const auto VerifyPats = [&](const PatternStringMap &Pats) {
-    for (const auto &Entry : Pats) {
-      if (!Entry.getValue())
+  const auto VerifyPats = [&](const PatternMap &Pats) {
+    for (const auto &[Name, Pat] : Pats) {
+      if (!Pat)
         PrintFatalError("null pattern in pattern map!");
 
-      if (Entry.getKey() != Entry.getValue()->getName()) {
-        Entry.getValue()->dump();
-        PrintFatalError("Pattern name mismatch! Map name: " + Entry.getKey() +
-                        ", Pat name: " + Entry.getValue()->getName());
+      if (Name != Pat->getName()) {
+        Pat->dump();
+        PrintFatalError("Pattern name mismatch! Map name: " + Name +
+                        ", Pat name: " + Pat->getName());
+      }
+
+      // As an optimization, the PatternMaps don't re-allocate the PatternName
+      // string. They simply reference the std::string inside Pattern. Ensure
+      // this is the case to avoid memory issues.
+      if (Name.data() != Pat->getName().data()) {
+        dbgs() << "Map StringRef: '" << Name << "' @ " << (void *)Name.data()
+               << "\n";
+        dbgs() << "Pat String: '" << Pat->getName() << "' @ "
+               << (void *)Pat->getName().data() << "\n";
+        PrintFatalError("StringRef stored in the PatternMap is not referencing "
+                        "the same string as its Pattern!");
       }
     }
   };
 
   VerifyPats(MatchPats);
   VerifyPats(ApplyPats);
 
   for (const auto &[Name, Op] : OperandTable) {
RM.addAction<DebugCommentAction>(
       (AdditionalCommentStr.empty() ? "" : "; " + AdditionalCommentStr));
   return RM;
 }
 
 bool CombineRuleBuilder::findRoots() {
   // Look by pattern name, e.g.
   //    (G_FNEG $x, $y):$root
   if (auto It = MatchPats.find(RootName); It != MatchPats.end()) {
-    MatchRoot = MatchPats[RootName].get();
+    MatchRoot = It->second.get();
     return true;
   }
 
   // Look by def:
   //    (G_FNEG $root, $y)
   auto It = OperandTable.find(RootName);
   if (It == OperandTable.end()) {
     PrintError("Cannot find root '" + RootName + "' in match patterns!");
     return false;
   }
 
   if (!It->second.MatchPat) {
     PrintError("Cannot use live-in operand '" + RootName +
                "' as match pattern root!");
     return false;
   }
 
   MatchRoot = It->second.MatchPat;
   return true;
 }
 
 bool CombineRuleBuilder::buildOperandsTable() {
   // Walk each instruction pattern
-  for (auto &P : MatchPats) {
-    auto *IP = dyn_cast<InstructionPattern>(P.getValue().get());
+  for (auto &[_, P] : MatchPats) {
+    auto *IP = dyn_cast<InstructionPattern>(P.get());
     if (!IP)
       continue;
     for (const auto &Operand : IP->operands()) {
       // Create an entry, no matter if it's a use or a def.
       auto &Entry = OperandTable[Operand.Name];
 
       // We only need to do additional checking on defs, though.
       if (!Operand.IsDef)
         continue;
 
       if (Entry.MatchPat) {
         PrintError("Operand '" + Operand.Name +
                    "' is defined multiple times in the 'match' patterns");
         return false;
       }
       Entry.MatchPat = IP;
     }
   }
 
-  for (auto &P : ApplyPats) {
-    auto *IP = dyn_cast<InstructionPattern>(P.getValue().get());
+  for (auto &[_, P] : ApplyPats) {
+    auto *IP = dyn_cast<InstructionPattern>(P.get());
     if (!IP)
       continue;
     for (const auto &Operand : IP->operands()) {
       // Create an entry, no matter if it's a use or a def.
       auto &Entry = OperandTable[Operand.Name];
 
       // We only need to do additional checking on defs, though.
       if (!Operand.IsDef)
for (unsigned I = 0; I < Match.getNumArgs(); ++I) {
     // Parse arbitrary C++ code
     if (const auto *StringI = dyn_cast<StringInit>(Arg)) {
       auto CXXPat =
           std::make_unique<CXXPattern>(*StringI, Name, /*IsApply*/ false);
       if (!CXXPat->getRawCode().contains("return ")) {
         PrintWarning(RuleDef.getLoc(),
                      "'match' C++ code does not seem to return!");
       }
-      MatchPats[Name] = std::move(CXXPat);
+      MatchPats[CXXPat->getName()] = std::move(CXXPat);
       continue;
     }
 
     // TODO: don't print this on, e.g. bad operand count in inst pat
     PrintError("Expected a subclass of GIMatchKind or a sub-dag whose "
                "operator is either of a GIMatchKindWithArgs or Instruction");
     PrintNote("Pattern was `" + Arg->getAsString() + "'");
     return false;
bool CombineRuleBuilder::parseApply(DagInit &Apply) {
   }
 
   if (Apply.getNumArgs() != 1) {
     PrintError("Expected exactly 1 argument in 'apply'");
     return false;
   }
 
   const StringInit *Code = dyn_cast<StringInit>(Apply.getArg(0));
-  const auto PatName = makeAnonPatName("apply");
-  ApplyPats[PatName] =
-      std::make_unique<CXXPattern>(*Code, PatName, /*IsApply*/ true);
+  auto Pat = std::make_unique<CXXPattern>(*Code, makeAnonPatName("apply"),
+                                          /*IsApply*/ true);
+  ApplyPats[Pat->getName()] = std::move(Pat);
   return true;
 }
 
 std::unique_ptr<Pattern>
 CombineRuleBuilder::parseInstructionMatcher(const Init &Arg, StringRef Name) {
   const DagInit *Matcher = getDagWithOperatorOfSubClass(Arg, "Instruction");
   if (!Matcher)
     return nullptr;
bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
   InstructionMatcher &IM = M.addInstructionMatcher("root");
   declareInstExpansion(CE, IM, IP.getName());
 
   DenseSet<const Pattern *> SeenPats;
   if (!emitInstructionMatchPattern(CE, M, IM, IP, SeenPats))
     return false;
 
   // Emit remaining patterns
-  for (auto &Entry : MatchPats) {
-    Pattern *CurPat = Entry.getValue().get();
-    if (SeenPats.contains(CurPat))
+  for (auto &[_, Pat] : MatchPats) {
+    if (SeenPats.contains(Pat.get()))
       continue;
 
-    switch (CurPat->getKind()) {
+    switch (Pat->getKind()) {
     case Pattern::K_AnyOpcode:
       PrintError("wip_match_opcode can not be used with instruction patterns!");
       return false;
     case Pattern::K_Inst:
-      cast<InstructionPattern>(CurPat)->reportUnreachable(RuleDef.getLoc());
+      cast<InstructionPattern>(Pat.get())->reportUnreachable(RuleDef.getLoc());
       return false;
     case Pattern::K_CXX: {
-      addCXXPredicate(IM, CE, *cast<CXXPattern>(CurPat));
+      addCXXPredicate(IM, CE, *cast<CXXPattern>(Pat.get()));
       continue;
     }
     default:
       llvm_unreachable("unknown pattern kind!");
     }
   }
 
   return emitApplyPatterns(CE, M);
for (const CodeGenInstruction *CGI : AOP.insts()) {
     declareInstExpansion(CE, IM, AOP.getName());
     // declareInstExpansion needs to be identical, otherwise we need to create a
     // CodeExpansions object here instead.
     assert(IM.getInsnVarID() == 0);
 
     IM.addPredicate<InstructionOpcodeMatcher>(CGI);
 
     // Emit remaining patterns.
-    for (auto &Entry : MatchPats) {
-      Pattern *CurPat = Entry.getValue().get();
-      if (CurPat == &AOP)
+    for (auto &[_, Pat] : MatchPats) {
+      if (Pat.get() == &AOP)
         continue;
 
-      switch (CurPat->getKind()) {
+      switch (Pat->getKind()) {
       case Pattern::K_AnyOpcode:
         PrintError("wip_match_opcode can only be present once!");
         return false;
       case Pattern::K_Inst:
-        cast<InstructionPattern>(CurPat)->reportUnreachable(RuleDef.getLoc());
+        cast<InstructionPattern>(Pat.get())->reportUnreachable(
+            RuleDef.getLoc());
         return false;
       case Pattern::K_CXX: {
-        addCXXPredicate(IM, CE, *cast<CXXPattern>(CurPat));
+        addCXXPredicate(IM, CE, *cast<CXXPattern>(Pat.get()));
         break;
       }
       default:
         llvm_unreachable("unknown pattern kind!");
       }
     }
 
     if (!emitApplyPatterns(CE, M))
       return false;
   }
 
   return true;
 }
 
 bool CombineRuleBuilder::emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M) {
-  for (auto &Entry : ApplyPats) {
-    Pattern *CurPat = Entry.getValue().get();
-    switch (CurPat->getKind()) {
+  for (auto &[_, Pat] : ApplyPats) {
+    switch (Pat->getKind()) {
     case Pattern::K_AnyOpcode:
     case Pattern::K_Inst:
       llvm_unreachable("Unsupported pattern kind in output pattern!");
     case Pattern::K_CXX: {
-      CXXPattern *CXXPat = cast<CXXPattern>(CurPat);
+      CXXPattern *CXXPat = cast<CXXPattern>(Pat.get());
       const auto &ExpandedCode = CXXPat->expandCode(CE, RuleDef.getLoc());
       M.addAction<CustomCXXAction>(
           ExpandedCode.getEnumNameWithPrefix(CXXApplyPrefix));
       continue;
     }
     default:
       llvm_unreachable("Unknown pattern kind!");
     }