[TableGen] Cache the vectors of records returned by getAllDerivedDefinitions().

[Paul-C-Anagnostopoulos]

Summary

In RecordKeeper: The vectors of records returned by getAllDerivedDefinitions(). Many backends request the same record vectors multiple times. This includes big ones like the records inheriting from the Instruction class.

My timings indicate that this speeds up most backends by about 2%, for not much effort.

A couple of backends are full of extra phase timers. I will get rid of those before pushing this revision.

[craig.topper]

Can you split this up? The namespace caching change seems quite a bit simpler and easy to approve. The other change makes me think we should return an ArrayRef instead of a vector from getAllDerivedDefinitions. Otherwise we're still making a copy on every call. I also wonder if it should use StringMap instead of std::unordered_map.

Which backends are requesting Instructions multiple times? Don't most backends go through getInstructionsByEnumValue that already caches?

[Paul-C-Anagnostopoulos]

@dblaikie will attest to the fact that I still don't understand the C++ baroque memory management model. It took me awhile to figure out how to use the std::unordered_map.

I presume the extra copy is made each time one of the vectors is returned? Is there an cleverer way to fix this than changing all 221 calls to getAllDerivedDefinitions?

Any backend that works on the instructions and then, in a second step, works with CodeGenTarget, ends up asking for the instruction vector at least twice. One of them, I think InstrInfoEmitter, asks for it three times. getInstructionsByEnumValue helps, but doesn't completely solve the problem. And there are various other subsets of the records, some large, that are requested multiple times: PatFrags, AtomicNoRet, VOP, Commutable_REV.

I should note that timing these changes is rather dicey. The timings vary so much from one run to the next that it's tough to decide whether I'm actually getting anywhere. To convince myself these changes actually helped, I ran various backends at least 30 times each.

[Paul-C-Anagnostopoulos]

I will break out the instruction namespace change, submit a second Phabricator revision, and remove it from this revision. Probably not until Sunday, so let's carry on with this discussion.

[Paul-C-Anagnostopoulos]

It occurs to me that we may have to stick with copying the vector of records each time it is returned. There is nothing stopping backends from modifying the vector. I'll do some research.

I should have realized this earlier.

[Paul-C-Anagnostopoulos]

I removed the namespace caching and submitted a separate revision: https://reviews.llvm.org/D92722

[dblaikie]

llvm/lib/TableGen/Record.cpp

2602

I'd probably write this as std::string ClassNameString = ClassName.str() but could be written as std::string ClassNameString(ClassName); as well, if you prefer, but as-written (std::string ClassNameString = std::string(ClassName);) it's a bit overly verbose/redundant.

2602–2610

This causes a few redundant map lookups on the expensive path-, but probably the overall best solution would be using StringMap for this anyway (no need to do conversions via std::string in that case, for instance)

auto p = m.try_emplace(ClassNameString);
if (p.second) {
  p.first->second = getAllDerivedDefinitions(makeArrayRef(ClassName);
}
return p.first->second;

If this continues to use std::unordered_map, the code should be the same except for the need to call "str()" on the use of ClassNameString: auto p = m.try_emplace(ClassNameString.str());

[Paul-C-Anagnostopoulos]

I will play with this some more on Monday and take your advice, David.

The StringMap sounds interesting.

[Paul-C-Anagnostopoulos]

@dblaikie Are the timings on pages 22 and 23 to be believed?

https://llvm.org/devmtg/2014-04/PDFs/LightningTalks/data_structure_llvm.pdf

[Paul-C-Anagnostopoulos]

I've taken David's advice and now used StringMap. This time I measured and got about a 3% improvement with this caching.

[Paul-C-Anagnostopoulos]

llvm/include/llvm/TableGen/Record.h

37

Remove this include.

llvm/lib/TableGen/Record.cpp

2609

Remove these old lines.

[lattner]

Nice! StringMap is definitely a good way to go here, the timings in that talk don't look right at all.

llvm/lib/TableGen/Record.cpp

2602

Because you're using StringMap you don't need to convert this to an std::string. try_emplace works with StringRef.

[Paul-C-Anagnostopoulos]

Remove the cruft. This is now ready to push.

[lattner]

LGTM thanks paul

[dblaikie]

llvm/lib/TableGen/Record.cpp

2600

Now that the result is cached, perhaps this function could return by const ref instead of by value, to avoid unnecessary copies of the resulting vector?

[Paul-C-Anagnostopoulos]

llvm/lib/TableGen/Record.cpp

2600

The vector must be copied, because there is nothing stopping the caller from modifying it.

Do you think it's worth the effort to establish the rule that it cannot be modified and then investigate every call to see what's going on?

[craig.topper]

llvm/lib/TableGen/Record.cpp

2600

If the caller needs to modify, the caller can make a copy explicitly. I doubt most callers modify it. I think if you just change it to return const std::vector<Record*> & any code that does

std::vector<Record*> Foo = getAllDerivedDefinitions

will still compile. A copy will just be made by the assignment. This should cover most callers I would guess. Then we can through and individually change the callers to use "const std::vector &" to remove the copies.

[Paul-C-Anagnostopoulos]

llvm/lib/TableGen/Record.cpp

2600

That sounds like a good plan.

Some day I will get used to all the copying. I think.

llvm/include/llvm/TableGen/Record.h

 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <map>
 #include <memory>
 #include <string>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
 class ListRecTy;
 struct MultiClass;
 class Record;
 class RecordKeeper;

 class RecordKeeper {
   friend class RecordRecTy;
 
   using RecordMap = std::map<std::string, std::unique_ptr<Record>, std::less<>>;
   using GlobalMap = std::map<std::string, Init *, std::less<>>;
 
   std::string InputFilename;
   RecordMap Classes, Defs;
+  mutable StringMap<std::vector<Record *>> ClassRecordsMap;
   FoldingSet<RecordRecTy> RecordTypePool;
   std::map<std::string, Init *, std::less<>> ExtraGlobals;
   unsigned AnonCounter = 0;
 
   // 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;
public:
   void stopPhaseTiming() {
     if (TimingGroup)
       delete TimingGroup;
   }
 
   //===--------------------------------------------------------------------===//
   // High-level helper methods, useful for tablegen backends.
 
-  /// Get all the concrete records that inherit from all the specified
-  /// classes. The classes must be defined.
-  std::vector<Record *> getAllDerivedDefinitions(
-      const ArrayRef<StringRef> ClassNames) const;
-
   /// 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) const;
 
-    return getAllDerivedDefinitions(makeArrayRef(ClassName));
-  }
+  /// 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;
 
   void dump() const;
 };
 
 /// Sorting predicate to sort record pointers by name.
 struct LessRecord {
   bool operator()(const Record *Rec1, const Record *Rec2) const {
     return StringRef(Rec1->getName()).compare_numeric(Rec2->getName()) < 0;

llvm/lib/TableGen/Record.cpp

void RecordKeeper::stopBackendTimer() {
   if (TimingGroup) {
     if (BackendTimer) {
       stopTimer();
       BackendTimer = false;
     }
   }
 }
 
+// We cache the record vectors for single classes. Many backends request
+// the same vectors multiple times.
 std::vector<Record *> RecordKeeper::getAllDerivedDefinitions(
-    const ArrayRef<StringRef> ClassNames) const {
+    StringRef ClassName) const {
+
+  auto Pair = ClassRecordsMap.try_emplace(ClassName);
+  if (Pair.second)
+    Pair.first->second = getAllDerivedDefinitions(makeArrayRef(ClassName));
+
+  return Pair.first->second;
+}
+
+std::vector<Record *> RecordKeeper::getAllDerivedDefinitions(
+    ArrayRef<StringRef> ClassNames) 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");

llvm/utils/TableGen/InstrInfoEmitter.cpp

void InstrInfoEmitter::run(raw_ostream &OS) {
   const std::string &TargetName = std::string(Target.getName());
   Record *InstrInfo = Target.getInstructionSet();
 
   // Keep track of all of the def lists we have emitted already.
   std::map<std::vector<Record*>, unsigned> EmittedLists;
   unsigned ListNumber = 0;
 
   // Emit all of the instruction's implicit uses and defs.
+  Records.startTimer("Emit uses/defs");
   for (const CodeGenInstruction *II : Target.getInstructionsByEnumValue()) {
     Record *Inst = II->TheDef;
     std::vector<Record*> Uses = Inst->getValueAsListOfDefs("Uses");
     if (!Uses.empty()) {
       unsigned &IL = EmittedLists[Uses];
       if (!IL) PrintDefList(Uses, IL = ++ListNumber, OS);
     }
     std::vector<Record*> Defs = Inst->getValueAsListOfDefs("Defs");
     if (!Defs.empty()) {
       unsigned &IL = EmittedLists[Defs];
       if (!IL) PrintDefList(Defs, IL = ++ListNumber, OS);
     }
   }
 
   OperandInfoMapTy OperandInfoIDs;
 
   // Emit all of the operand info records.
+  Records.startTimer("Emit operand info");
   EmitOperandInfo(OS, OperandInfoIDs);
 
   // Emit all of the MCInstrDesc records in their ENUM ordering.
   //
+  Records.startTimer("Emit InstrDesc records");
   OS << "\nextern const MCInstrDesc " << TargetName << "Insts[] = {\n";
   ArrayRef<const CodeGenInstruction*> NumberedInstructions =
     Target.getInstructionsByEnumValue();
 
   SequenceToOffsetTable<std::string> InstrNames;
   unsigned Num = 0;
   for (const CodeGenInstruction *Inst : NumberedInstructions) {
     // Keep a list of the instruction names.
     InstrNames.add(std::string(Inst->TheDef->getName()));
     // Emit the record into the table.
     emitRecord(*Inst, Num++, InstrInfo, EmittedLists, OperandInfoIDs, OS);
   }
   OS << "};\n\n";
 
   // Emit the array of instruction names.
+  Records.startTimer("Emit instruction names");
   InstrNames.layout();
   InstrNames.emitStringLiteralDef(OS, Twine("extern const char ") + TargetName +
                                           "InstrNameData[]");
 
   OS << "extern const unsigned " << TargetName <<"InstrNameIndices[] = {";
   Num = 0;
   for (const CodeGenInstruction *Inst : NumberedInstructions) {
     // Newline every eight entries.
for (const CodeGenInstruction *Inst : NumberedInstructions) {
       else
         OS << "nullptr, ";
       ++Num;
     }
     OS << "\n};\n\n";
   }
 
   // MCInstrInfo initialization routine.
+  Records.startTimer("Emit initialization routine");
   OS << "static inline void Init" << TargetName
      << "MCInstrInfo(MCInstrInfo *II) {\n";
   OS << "  II->InitMCInstrInfo(" << TargetName << "Insts, " << TargetName
      << "InstrNameIndices, " << TargetName << "InstrNameData, ";
   if (HasDeprecationFeatures)
     OS << TargetName << "InstrDeprecationFeatures, ";
   else
     OS << "nullptr, ";
if (HasComplexDeprecationInfos)
     OS << TargetName << "InstrComplexDeprecationInfos, ";
   else
     OS << "nullptr, ";
   OS << NumberedInstructions.size() << ");\n}\n";
   OS << "} // end namespace llvm\n";
 
   OS << "#endif // GET_INSTRINFO_CTOR_DTOR\n\n";
 
+  Records.startTimer("Emit operand name mappings");
   emitOperandNameMappings(OS, Target, NumberedInstructions);
 
+  Records.startTimer("Emit operand type mappings");
   emitOperandTypeMappings(OS, Target, NumberedInstructions);
 
+  Records.startTimer("Emit helper methods");
   emitMCIIHelperMethods(OS, TargetName);
 }
 
 void InstrInfoEmitter::emitRecord(const CodeGenInstruction &Inst, unsigned Num,
                                   Record *InstrInfo,
                          std::map<std::vector<Record*>, unsigned> &EmittedLists,
                                   const OperandInfoMapTy &OpInfo,
                                   raw_ostream &OS) {
void InstrInfoEmitter::emitEnums(raw_ostream &OS) {
   OS << "} // end namespace llvm\n";
 
   OS << "#endif // GET_INSTRINFO_SCHED_ENUM\n\n";
 }
 
 namespace llvm {
 
 void EmitInstrInfo(RecordKeeper &RK, raw_ostream &OS) {
+  RK.startTimer("Analyze DAG patterns");
   InstrInfoEmitter(RK).run(OS);
+  RK.startTimer("Emit map table");
   EmitMapTable(RK, OS);
 }
 
 } // end namespace llvm