[Experimental] getAllDerivedDefinitions() returns unsorted Records by default

[chapuni]

Summary

• None: Registration order (by default)
• Numeric: Use StringRef::compare_numeric
• Char: Character order

[chapuni]

This is an experiment to D145874.
RK::Defs2 holds Defs by registration order including anonymous defs.

I have checked only with check-llvm. Bootstrapping is not tested.

llvm/utils/TableGen/Attributes.cpp

68

Enum should be sorted since it would affect the internal order.

118

I guess it should be the same order as Enum.

llvm/utils/TableGen/CodeGenRegisters.cpp

1178

This is the only place that relies on char sort.
I guess it wouldn't affect actual behavior changes.

llvm/utils/TableGen/GlobalISelEmitter.cpp

5555

Possible bug, capturing address of temporary object.

llvm/include/llvm/TableGen/Record.h

 //===- llvm/TableGen/Record.h - Classes for Table Records -------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
public:
   void addClass(std::unique_ptr<Record> R) {
     bool Ins = Classes.insert(std::make_pair(std::string(R->getName()),
                                              std::move(R))).second;
     (void)Ins;
     assert(Ins && "Class already exists");
   }
 
   void addDef(std::unique_ptr<Record> R) {
-    bool Ins = Defs.insert(std::make_pair(std::string(R->getName()),
-                                          std::move(R))).second;
+    Defs2.push_back(R.get());
+
+    bool Ins =
+        Defs.insert(std::make_pair(std::string(R->getName()), std::move(R)))
+            .second;
     (void)Ins;
     assert(Ins && "Record already exists");
   }
 
   void addExtraGlobal(StringRef Name, Init *I) {
     bool Ins = ExtraGlobals.insert(std::make_pair(std::string(Name), I)).second;
     (void)Ins;
     assert(!getDef(Name));
public:
   void stopPhaseTiming() {
     if (TimingGroup)
       delete TimingGroup;
   }
 
   //===--------------------------------------------------------------------===//
   // High-level helper methods, useful for tablegen backends.
 
+  enum SortOrder {
+    None = 0, // Registration order
+    Numeric,
+    Char,
+  };
+
   /// Get all the concrete records that inherit from the one specified
   /// class. The class must be defined.
-  std::vector<Record *> getAllDerivedDefinitions(StringRef ClassName) const;
+  std::vector<Record *> getAllDerivedDefinitions(StringRef ClassName,
+                                                 SortOrder Order = None) const;
 
   /// Get all the concrete records that inherit from all the specified
   /// classes. The classes must be defined.
-  std::vector<Record *> getAllDerivedDefinitions(
-      ArrayRef<StringRef> ClassNames) const;
+  std::vector<Record *> getAllDerivedDefinitions(ArrayRef<StringRef> ClassNames,
+                                                 SortOrder Order = None) const;
 
   /// Get all the concrete records that inherit from specified class, if the
   /// class is defined. Returns an empty vector if the class is not defined.
   std::vector<Record *>
-  getAllDerivedDefinitionsIfDefined(StringRef ClassName) const;
+  getAllDerivedDefinitionsIfDefined(StringRef ClassName,
+                                    SortOrder Order = None) const;
 
   void dump() const;
 
 private:
   RecordKeeper(RecordKeeper &&) = delete;
   RecordKeeper(const RecordKeeper &) = delete;
   RecordKeeper &operator=(RecordKeeper &&) = delete;
   RecordKeeper &operator=(const RecordKeeper &) = delete;
 
   std::string InputFilename;
   RecordMap Classes, Defs;
-  mutable StringMap<std::vector<Record *>> ClassRecordsMap;
+  std::vector<Record *> Defs2;
+  mutable std::array<StringMap<std::vector<Record *>>, 3> ClassRecordsMap;
   GlobalMap ExtraGlobals;
 
   // These members are for the phase timing feature. We need a timer group,
   // the last timer started, and a flag to say whether the last timer
   // is the special "backend overall timer."
   TimerGroup *TimingGroup = nullptr;
   Timer *LastTimer = nullptr;
   bool BackendTimer = false;

llvm/lib/TableGen/Record.cpp

 //===- Record.cpp - Record implementation ---------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
if (TimingGroup) {
     if (BackendTimer) {
       stopTimer();
       BackendTimer = false;
     }
   }
 }
 
 std::vector<Record *>
-RecordKeeper::getAllDerivedDefinitions(StringRef ClassName) const {
+RecordKeeper::getAllDerivedDefinitions(StringRef ClassName,
+                                       SortOrder Order) const {
   // We cache the record vectors for single classes. Many backends request
   // the same vectors multiple times.
-  auto Pair = ClassRecordsMap.try_emplace(ClassName);
+  auto Pair = ClassRecordsMap[int(Order)].try_emplace(ClassName);
   if (Pair.second)
-    Pair.first->second = getAllDerivedDefinitions(ArrayRef(ClassName));
+    Pair.first->second = getAllDerivedDefinitions(ArrayRef(ClassName), Order);
 
   return Pair.first->second;
 }
 
-std::vector<Record *> RecordKeeper::getAllDerivedDefinitions(
-    ArrayRef<StringRef> ClassNames) const {
+std::vector<Record *>
+RecordKeeper::getAllDerivedDefinitions(ArrayRef<StringRef> ClassNames,
+                                       SortOrder Order) const {
   SmallVector<Record *, 2> ClassRecs;
   std::vector<Record *> Defs;
 
   assert(ClassNames.size() > 0 && "At least one class must be passed.");
   for (const auto &ClassName : ClassNames) {
     Record *Class = getClass(ClassName);
     if (!Class)
       PrintFatalError("The class '" + ClassName + "' is not defined\n");
     ClassRecs.push_back(Class);
   }
 
-  for (const auto &OneDef : getDefs()) {
+  for (auto *OneDef : Defs2) {
     if (all_of(ClassRecs, [&OneDef](const Record *Class) {
-                            return OneDef.second->isSubClassOf(Class);
-                          }))
-      Defs.push_back(OneDef.second.get());
+          return OneDef->isSubClassOf(Class);
+      Defs.push_back(OneDef);
+  }
+
+  switch (Order) {
+  case None:
+    break;
+  case Numeric:
+    llvm::sort(Defs, [](Record *LHS, Record *RHS) {
+      return LHS->getName().compare_numeric(RHS->getName()) < 0;
+    });
+    break;
+  case Char:
+    llvm::sort(Defs, [](Record *LHS, Record *RHS) {
+      return LHS->getName() < RHS->getName();
+    });
+    break;
   }
 
   return Defs;
 }
 
 std::vector<Record *>
-RecordKeeper::getAllDerivedDefinitionsIfDefined(StringRef ClassName) const {
-  return getClass(ClassName) ? getAllDerivedDefinitions(ClassName)
+RecordKeeper::getAllDerivedDefinitionsIfDefined(StringRef ClassName,
+                                                SortOrder Order) const {
+  return getClass(ClassName) ? getAllDerivedDefinitions(ClassName, Order)
                              : std::vector<Record *>();
 }
 
 Init *MapResolver::resolve(Init *VarName) {
   auto It = Map.find(VarName);
   if (It == Map.end())
     return nullptr;
 

llvm/utils/TableGen/Attributes.cpp

 //===- Attributes.cpp - Generate attributes -------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
void Attributes::emitTargetIndependentNames(raw_ostream &OS) {
   OS << "#undef ATTRIBUTE_ALL\n";
   OS << "#endif\n\n";
 
   OS << "#ifdef GET_ATTR_ENUM\n";
   OS << "#undef GET_ATTR_ENUM\n";
   unsigned Value = 1; // Leave zero for AttrKind::None.
   for (StringRef KindName : {"EnumAttr", "TypeAttr", "IntAttr"}) {
     OS << "First" << KindName << " = " << Value << ",\n";
-    for (auto *A : Records.getAllDerivedDefinitions(KindName)) {
+    for (auto *A :
+         Records.getAllDerivedDefinitions(KindName, RecordKeeper::Numeric)) {
       OS << A->getName() << " = " << Value << ",\n";
       Value++;
     }
     OS << "Last" << KindName << " = " << (Value - 1) << ",\n";
   }
   OS << "#endif\n\n";
 }
 
void Attributes::emitFnAttrCompatCheck(raw_ostream &OS, bool IsStringAttr) {
   OS << "#endif\n";
 }
 
 void Attributes::emitAttributeProperties(raw_ostream &OS) {
   OS << "#ifdef GET_ATTR_PROP_TABLE\n";
   OS << "#undef GET_ATTR_PROP_TABLE\n";
   OS << "static const uint8_t AttrPropTable[] = {\n";
   for (StringRef KindName : {"EnumAttr", "TypeAttr", "IntAttr"}) {
-    for (auto *A : Records.getAllDerivedDefinitions(KindName)) {
+    for (auto *A :
+         Records.getAllDerivedDefinitions(KindName, RecordKeeper::Numeric)) {
       OS << "0";
       for (Init *P : *A->getValueAsListInit("Properties"))
         OS << " | AttributeProperty::" << cast<DefInit>(P)->getDef()->getName();
       OS << ",\n";
     }
   }
   OS << "};\n";
   OS << "#endif\n";

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

 //===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //

 
 
 /// ParsePatternFragments - Parse all of the PatFrag definitions in the .td
 /// file, building up the PatternFragments map.  After we've collected them all,
 /// inline fragments together as necessary, so that there are no references left
 /// inside a pattern fragment to a pattern fragment.
 ///
 void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) {
-  std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrags");
+  std::vector<Record *> Fragments =
+      Records.getAllDerivedDefinitions("PatFrags", RecordKeeper::Numeric);
 
   // First step, parse all of the fragments.
   for (Record *Frag : Fragments) {
     if (OutFrags != Frag->isSubClassOf("OutPatFrag"))
       continue;
 
     ListInit *LI = Frag->getValueAsListInit("Fragments");
     TreePattern *P =

llvm/utils/TableGen/CodeGenRegisters.cpp

 //===- CodeGenRegisters.cpp - Register and RegisterClass Info -------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records,
   // Read in the register definitions.
   std::vector<Record*> Regs = Records.getAllDerivedDefinitions("Register");
   llvm::sort(Regs, LessRecordRegister());
   // Assign the enumeration values.
   for (unsigned i = 0, e = Regs.size(); i != e; ++i)
     getReg(Regs[i]);
 
   // Expand tuples and number the new registers.
-  std::vector<Record*> Tups =
-    Records.getAllDerivedDefinitions("RegisterTuples");
+  std::vector<Record *> Tups =
+      Records.getAllDerivedDefinitions("RegisterTuples", RecordKeeper::Char);
 
   for (Record *R : Tups) {
     std::vector<Record *> TupRegs = *Sets.expand(R);
     llvm::sort(TupRegs, LessRecordRegister());
     for (Record *RC : TupRegs)
       getReg(RC);
   }
 
for (auto &Reg : Registers) {
     }
   }
 
   // Native register units are associated with a leaf register. They've all been
   // discovered now.
   NumNativeRegUnits = RegUnits.size();
 
   // Read in register class definitions.
-  std::vector<Record*> RCs = Records.getAllDerivedDefinitions("RegisterClass");
+  std::vector<Record *> RCs =
+      Records.getAllDerivedDefinitions("RegisterClass", RecordKeeper::Numeric);
   if (RCs.empty())
     PrintFatalError("No 'RegisterClass' subclasses defined!");
 
   // Allocate user-defined register classes.
   for (auto *R : RCs) {
     RegClasses.emplace_back(*this, R);
     CodeGenRegisterClass &RC = RegClasses.back();
     if (!RC.Artificial)

llvm/utils/TableGen/CodeGenSchedule.cpp

 //===- CodeGenSchedule.cpp - Scheduling MachineModels ---------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
for (unsigned j = i+1; j < e; ++j) {
         }
       }
     }
   }
 }
 
 // Collect all the RegisterFile definitions available in this target.
 void CodeGenSchedModels::collectRegisterFiles() {
-  RecVec RegisterFileDefs = Records.getAllDerivedDefinitions("RegisterFile");
+  RecVec RegisterFileDefs =
+      Records.getAllDerivedDefinitions("RegisterFile", RecordKeeper::Numeric);
 
   // RegisterFiles is the vector of CodeGenRegisterFile.
   for (Record *RF : RegisterFileDefs) {
     // For each register file definition, construct a CodeGenRegisterFile object
     // and add it to the appropriate scheduling model.
     CodeGenProcModel &PM = getProcModel(RF->getValueAsDef("SchedModel"));
     PM.RegisterFiles.emplace_back(CodeGenRegisterFile(RF->getName(),RF));
     CodeGenRegisterFile &CGRF = PM.RegisterFiles.back();

llvm/utils/TableGen/GlobalISelEmitter.cpp

 //===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //

 // The 'Predicate_' part of the name is redundant but eliminating it is more
 // trouble than it's worth.
 void GlobalISelEmitter::emitCxxPredicateFns(
     raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
     StringRef ArgType, StringRef ArgName, StringRef AdditionalArgs,
     StringRef AdditionalDeclarations,
     std::function<bool(const Record *R)> Filter) {
   std::vector<const Record *> MatchedRecords;
-  const auto &Defs = RK.getAllDerivedDefinitions("PatFrags");
+  auto Defs = RK.getAllDerivedDefinitions("PatFrags", RecordKeeper::Numeric);
   std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
                [&](Record *Record) {
                  return !Record->getValueAsString(CodeFieldName).empty() &&
                         Filter(Record);
                });
 
   if (!MatchedRecords.empty()) {
     OS << "// PatFrag predicates.\n"

llvm/utils/TableGen/RegisterBankEmitter.cpp

 //===- RegisterBankEmitter.cpp - Generate a Register Bank Desc. -*- 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
 //
 //===----------------------------------------------------------------------===//
 //

 }
 
 void RegisterBankEmitter::run(raw_ostream &OS) {
   StringRef TargetName = Target.getName();
   const CodeGenRegBank &RegisterClassHierarchy = Target.getRegBank();
 
   Records.startTimer("Analyze records");
   std::vector<RegisterBank> Banks;
-  for (const auto &V : Records.getAllDerivedDefinitions("RegisterBank")) {
+  for (const auto &V : Records.getAllDerivedDefinitions(
+           "RegisterBank", RecordKeeper::Numeric)) {
     SmallPtrSet<const CodeGenRegisterClass *, 8> VisitedRCs;
     RegisterBank Bank(*V);
 
     for (const CodeGenRegisterClass *RC :
          Bank.getExplicitlySpecifiedRegisterClasses(RegisterClassHierarchy)) {
       visitRegisterBankClasses(
           RegisterClassHierarchy, RC, "explicit",
           [&Bank](const CodeGenRegisterClass *RC, StringRef Kind) {

llvm/utils/TableGen/SubtargetFeatureInfo.cpp

 //===- SubtargetFeatureInfo.cpp - Helpers for subtarget features ----------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
LLVM_DUMP_METHOD void SubtargetFeatureInfo::dump() const {
   errs() << getEnumName() << " " << Index << "\n" << *TheDef;
 }
 #endif
 
 std::vector<std::pair<Record *, SubtargetFeatureInfo>>
 SubtargetFeatureInfo::getAll(const RecordKeeper &Records) {
   std::vector<std::pair<Record *, SubtargetFeatureInfo>> SubtargetFeatures;
   std::vector<Record *> AllPredicates =
-      Records.getAllDerivedDefinitions("Predicate");
+      Records.getAllDerivedDefinitions("Predicate", RecordKeeper::Numeric);
   for (Record *Pred : AllPredicates) {
     // Ignore predicates that are not intended for the assembler.
     //
     // The "AssemblerMatcherPredicate" string should be promoted to an argument
     // if we re-use the machinery for non-assembler purposes in future.
     if (!Pred->getValueAsBit("AssemblerMatcherPredicate"))
       continue;