[TableGen] Some simple optimizations to TableGen execution time

[zturner]

Summary

I got sufficiently annoyed with sitting around waiting forever for TableGen to complete during a build, so I profiled it. While there's quite a bit more that can be done, this is the really easy stuff. Tons of string allocations and re-allocations, STL stringstream usage, and STL set container usage.

With this patch, X86GenDAGISel is reduced from ~45 seconds to ~33 seconds on my machine, which is a ~1.3x speedup.

The next biggest bottleneck is the class that indents and formats the output. Given that tablegen output is really only intended to be consumed by a machine, it makes sense to question whether or not it's worth the performance cost. I removed the formatting and my speedup jumps to a 2x speedup (44s -> 22s).

After I get the single-threaded execution time sufficiently fast, I might even try to parallelize it. It seems like a terribly obvious and easy candidate for parallelization given that we now have simple parallel algorithms in Support.

Feel free to add other reviewers if there's someone better.

[zturner]

To be clear, this patch is intended to be NFC. So the formatting changes aren't here. Just throwing it out there for potential commentary. I really have no idea how any of this black magic works, so if there's some obvious reason why people need the output to be formatted I'm happy to be wrong (well not happy necessarily, happy would be an extra 11s of my life back every time I type ninja)

[craig.topper]

llvm/utils/TableGen/CodeGenDAGPatterns.h

81 ↗

(On Diff #115557)

I don't see any usage of the return value of this. Did I miss it?

If I didn't miss it, should this just be a void method called print? I think that would be consistent with other classes in LLVM.

Is the llvm:: namespace qualifier needed on raw_ostream?

[craig.topper]

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

3110 ↗

(On Diff #115557)

llvm:: shouldn't be necessary here.

3800 ↗

(On Diff #115557)

Shouldn't need llvm::

[craig.topper]

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

190 ↗

(On Diff #115557)

Why do you need a reserve here? Isn't the vector already have S.size() elements in it after the constructor?

[zturner]

Updated from suggestions.

Craig, do you have thoughts about the formatting? How important is it that the output be formatted?

[asb]

In my view, disabling formatting is unhelpful when you have to debug a compilation error is generated from tablegen'ed code or when auditing its output. If the build-time improvement is meaningful, I'd suggest disabling formatting only when building LLVM in release mode.

[Note: I haven't reviewed unformatted vs formatted tablegen output, it's plausible that in practice the more correct formatting adds relatively little].

[zturner]

Changed another std::set to a DenseSet, and changed a couple of sets to vectors. This shaves off another couple of seconds, I'm now down from 45s (no patch) -> 26s (with patch), for a 1.73x combined speedup.

[RKSimon]

Thank you for working on this!

llvm/include/llvm/CodeGen/MachineValueType.h

203 ↗

(On Diff #115580)

Is this supposed to equal Metadata?

237 ↗

(On Diff #115580)

Please revert these whitespace changes - if nothing else it pollutes this patch.

[craig.topper]

llvm/utils/TableGen/CodeGenDAGPatterns.h

43 ↗

(On Diff #115580)

I wonder if we could use std::bitset. The MVT enum only contains 255 values.

[craig.topper]

Is it the PadToColumn calls that are slowing down the formatting?

[zturner]

In D37957#873349, @craig.topper wrote:

Is it the PadToColumn calls that are slowing down the formatting?

I think it's the fact that every character of every write must be examined in order to find newlines.

One potential optimization that might still work with formatting is to provide a method on the stream called writeLine, where you don't specify the newline but it puts one for you, and assumes that there are no other newlines in the input. This would allow us to get rid of the character scan.

[kparzysz]

Could you rebase this patch?

[zturner]

Rebased on top of changes.

Original baseline (before any performance regression): 11s
After regression: 38s
+Krzysztof's improvements: 26s
+These additional optimizations: 16s

I think this is close enough to the original baseline that it's within the realm of being tolerable. I do get an assertion failure when I run with my patch in debug build, because it's trying to insert an empty StringRef into a StringSet, which is not allowed. Can you apply this patch Krzysztof and see if you can figure out what the right thing to do is with the empty StringRef?

[kparzysz]

In D37957#875513, @zturner wrote:

Can you apply this patch Krzysztof and see if you can figure out what the right thing to do is with the empty StringRef?

It's because of this pattern that doesn't have any named variables (i.e. all names of leaf values are empty):
(intrinsic_void 5755:{ *:[iPTR] }, ECX:{ *:[i32] }, EAX:{ *:[i32] }, EBX:{ *:[i32] })

It corresponds to this pattern in .td, in case anyone's interested:

let Uses = [ ECX, EAX, EBX ] in {
  def MWAITXrrr : I<0x01, MRM_FB, (outs), (ins), "mwaitx",
                  [(int_x86_mwaitx ECX, EAX, EBX)], IIC_SSE_MWAITX>,
                  TB, Requires<[ HasMWAITX ]>;
}

[kparzysz]

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

180 ↗

(On Diff #115886)

You still need to print the contents of the type set. Something like:

for (unsigned M : Modes) {
  OS << ' ' << getModeName() << ':';
  writeToStream(get(M), OS);
}

3823 ↗

(On Diff #115886)

Make it if (N->hasName() && isa<DefInit>(N->getLeafValue())). This will avoid the assertion.

[zturner]

Fixed suggestions.

[kparzysz]

LGTM with a few nitpicks (inline comments). Also, could you commit the DenseSet/tombstone changes in a separate patch?

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

101 ↗

(On Diff #116025)

Same here---the llvm:: seems unnecessary.

167 ↗

(On Diff #116025)

Same here.

llvm/utils/TableGen/CodeGenDAGPatterns.h

21 ↗

(On Diff #116025)

This should go in the .cpp file (I don't see any uses of DenseSet in the header).

338 ↗

(On Diff #116025)

Is the llvm:: needed here?

[zturner]

llvm/utils/TableGen/CodeGenDAGPatterns.h

21 ↗

(On Diff #116025)

It's needed here in order to specialize the DenseMapInfo

[rnk]

lgtm, just nits

llvm/include/llvm/ADT/DenseSet.h

192 ↗

(On Diff #116025)

What made us need this?

196 ↗

(On Diff #116025)

Is this simpler as:

if (!Other.count(I))
  return false;

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

20 ↗

(On Diff #116025)

You only use StringMap, not StringSet, so include that header.

llvm/utils/TableGen/CodeGenDAGPatterns.h

21 ↗

(On Diff #116025)

Include DenseMapInfo.h directly, then.

[zturner]

llvm/include/llvm/ADT/DenseSet.h

192 ↗

(On Diff #116025)

It was no longer needed after Krzysztof's other changes. I removed this in the version that I committted.

llvm/trunk/utils/TableGen/CodeGenDAGPatterns.h

 #ifndef LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H
 #define LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H
 
 #include "CodeGenHwModes.h"
 #include "CodeGenIntrinsics.h"
 #include "CodeGenTarget.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <array>
 #include <map>
 #include <set>
 #include <vector>
 
struct TypeSetByHwMode : public InfoByHwMode<MachineValueTypeSet> {
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   bool isDefaultOnly() const {
     return Map.size() == 1 && Map.begin()->first == DefaultMode;
   }
 
   bool insert(const ValueTypeByHwMode &VVT);
   bool constrain(const TypeSetByHwMode &VTS);
   template <typename Predicate> bool constrain(Predicate P);
-  template <typename Predicate> bool assign_if(const TypeSetByHwMode &VTS,
-                                               Predicate P);
+  template <typename Predicate>
+  bool assign_if(const TypeSetByHwMode &VTS, Predicate P);
 
-  std::string getAsString() const;
-  static std::string getAsString(const SetType &S);
+  void writeToStream(raw_ostream &OS) const;
+  static void writeToStream(const SetType &S, raw_ostream &OS);
 
   bool operator==(const TypeSetByHwMode &VTS) const;
   bool operator!=(const TypeSetByHwMode &VTS) const { return !(*this == VTS); }
 
   void dump() const;
   void validate() const;
 
 private:
private:
   TypeSetByHwMode getLegalTypes();
 
   /// Cached legal types.
   bool LegalTypesCached = false;
   TypeSetByHwMode::SetType LegalCache = {};
 };
 
 /// Set type used to track multiply used variables in patterns
-typedef std::set<std::string> MultipleUseVarSet;
+typedef StringSet<> MultipleUseVarSet;
 
 /// SDTypeConstraint - This is a discriminated union of constraints,
 /// corresponding to the SDTypeConstraint tablegen class in Target.td.
 struct SDTypeConstraint {
   SDTypeConstraint(Record *R, const CodeGenHwModes &CGH);
 
   unsigned OperandNo;   // The operand # this constraint applies to.
   enum {

llvm/trunk/utils/TableGen/CodeGenDAGPatterns.cpp

 //===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the CodeGenDAGPatterns class, which is used to read and
 // represent the patterns present in a .td file for instructions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenDAGPatterns.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include <algorithm>
 #include <cstdio>
 #include <set>
-#include <sstream>
 using namespace llvm;
 
 #define DEBUG_TYPE "dag-patterns"
 
 static inline bool isIntegerOrPtr(MVT VT) {
   return VT.isInteger() || VT == MVT::iPTR;
 }
 static inline bool isFloatingPoint(MVT VT) {
bool TypeSetByHwMode::isPossible() const {
   for (const auto &I : *this)
     if (!I.second.empty())
       return true;
   return false;
 }
 
 bool TypeSetByHwMode::insert(const ValueTypeByHwMode &VVT) {
   bool Changed = false;
-  std::set<unsigned> Modes;
+  SmallDenseSet<unsigned, 4> Modes;
   for (const auto &P : VVT) {
     unsigned M = P.first;
     Modes.insert(M);
     // Make sure there exists a set for each specific mode from VVT.
     Changed |= getOrCreate(M).insert(P.second).second;
   }
 
   // If VVT has a default mode, add the corresponding type to all
   // modes in "this" that do not exist in VVT.
   if (Modes.count(DefaultMode)) {
     MVT DT = VVT.getType(DefaultMode);
     for (auto &I : *this)
       if (!Modes.count(I.first))
         Changed |= I.second.insert(DT).second;
   }
-
   return Changed;
 }
 
 // Constrain the type set to be the intersection with VTS.
 bool TypeSetByHwMode::constrain(const TypeSetByHwMode &VTS) {
   bool Changed = false;
   if (hasDefault()) {
     for (const auto &I : VTS) {
for (const auto &I : VTS) {
     SetType &S = getOrCreate(I.first);
     for (auto J : I.second)
       if (P(J))
         S.insert(J);
   }
   return !empty();
 }
 
-std::string TypeSetByHwMode::getAsString() const {
-  std::stringstream str;
-  std::vector<unsigned> Modes;
+void TypeSetByHwMode::writeToStream(raw_ostream &OS) const {
+  SmallVector<unsigned, 4> Modes;
+  Modes.reserve(Map.size());
 
   for (const auto &I : *this)
     Modes.push_back(I.first);
-  if (Modes.empty())
-    return "{}";
+  if (Modes.empty()) {
+    OS << "{}";
+    return;
+  }
   array_pod_sort(Modes.begin(), Modes.end());
 
-  str << '{';
+  OS << '{';
   for (unsigned M : Modes) {
-    const SetType &S = get(M);
-    str << ' ' << getModeName(M) << ':' << getAsString(S);
+    OS << ' ' << getModeName(M) << ':';
+    writeToStream(get(M), OS);
   }
-  str << " }";
-  return str.str();
+  OS << " }";
 }
 
-std::string TypeSetByHwMode::getAsString(const SetType &S) {
-  std::vector<MVT> Types;
-  for (MVT T : S)
-    Types.push_back(T);
+void TypeSetByHwMode::writeToStream(const SetType &S, raw_ostream &OS) {
+  SmallVector<MVT, 4> Types(S.begin(), S.end());
   array_pod_sort(Types.begin(), Types.end());
 
-  std::stringstream str;
-  str << '[';
+  OS << '[';
   for (unsigned i = 0, e = Types.size(); i != e; ++i) {
-    str << ValueTypeByHwMode::getMVTName(Types[i]);
+    OS << ValueTypeByHwMode::getMVTName(Types[i]);
     if (i != e-1)
-      str << ' ';
+      OS << ' ';
   }
-  str << ']';
-  return str.str();
+  OS << ']';
 }
 
 bool TypeSetByHwMode::operator==(const TypeSetByHwMode &VTS) const {
   bool HaveDefault = hasDefault();
   if (HaveDefault != VTS.hasDefault())
     return false;
 
   if (isSimple()) {
     if (VTS.isSimple())
       return *begin() == *VTS.begin();
     return false;
   }
 
-  std::set<unsigned> Modes;
+  SmallDenseSet<unsigned, 4> Modes;
   for (auto &I : *this)
     Modes.insert(I.first);
   for (const auto &I : VTS)
     Modes.insert(I.first);
 
   if (HaveDefault) {
     // Both sets have default mode.
     for (unsigned M : Modes) {
if (HaveDefault) {
     }
   }
 
   return true;
 }
 
 LLVM_DUMP_METHOD
 void TypeSetByHwMode::dump() const {
-  dbgs() << getAsString() << '\n';
+  writeToStream(dbgs());
+  dbgs() << '\n';
 }
 
 bool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) {
   bool OutP = Out.count(MVT::iPTR), InP = In.count(MVT::iPTR);
   auto Int = [&In](MVT T) -> bool { return !In.count(T); };
 
   if (OutP == InP)
     return berase_if(Out, Int);

 }
 
 void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out,
                                 const TypeSetByHwMode::SetType &Legal) {
   std::set<MVT> Ovs;
   for (MVT T : Out) {
     if (!T.isOverloaded())
       continue;
+
     Ovs.insert(T);
     // MachineValueTypeSet allows iteration and erasing.
     Out.erase(T);
   }
 
   for (MVT Ov : Ovs) {
     switch (Ov.SimpleTy) {
       case MVT::iPTRAny:

 }
 
 void TreePatternNode::print(raw_ostream &OS) const {
   if (isLeaf())
     OS << *getLeafValue();
   else
     OS << '(' << getOperator()->getName();
 
-  for (unsigned i = 0, e = Types.size(); i != e; ++i)
-    OS << ':' << getExtType(i).getAsString();
+  for (unsigned i = 0, e = Types.size(); i != e; ++i) {
+    OS << ':';
+    getExtType(i).writeToStream(OS);
+  }
 
   if (!isLeaf()) {
     if (getNumChildren() != 0) {
       OS << " ";
       getChild(0)->print(OS);
       for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
         OS << ", ";
         getChild(i)->print(OS);
for (Record *Frag : Fragments) {
     DagInit *Tree = Frag->getValueAsDag("Fragment");
     TreePattern *P =
         (PatternFragments[Frag] = llvm::make_unique<TreePattern>(
              Frag, Tree, !Frag->isSubClassOf("OutPatFrag"),
              *this)).get();
 
     // Validate the argument list, converting it to set, to discard duplicates.
     std::vector<std::string> &Args = P->getArgList();
-    std::set<std::string> OperandsSet(Args.begin(), Args.end());
+    // Copy the args so we can take StringRefs to them.
+    auto ArgsCopy = Args;
+    SmallDenseSet<StringRef, 4> OperandsSet;
+    OperandsSet.insert(ArgsCopy.begin(), ArgsCopy.end());
 
     if (OperandsSet.count(""))
       P->error("Cannot have unnamed 'node' values in pattern fragment!");
 
     // Parse the operands list.
     DagInit *OpsList = Frag->getValueAsDag("Operands");
     DefInit *OpsOp = dyn_cast<DefInit>(OpsList->getOperator());
     // Special cases: ops == outs == ins. Different names are used to
const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern(
   // InstResults - Keep track of all the virtual registers that are 'set'
   // in the instruction, including what reg class they are.
   std::map<std::string, TreePatternNode*> InstResults;
 
   std::vector<Record*> InstImpResults;
 
   // Verify that the top-level forms in the instruction are of void type, and
   // fill in the InstResults map.
+  SmallString<32> TypesString;
   for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) {
+    TypesString.clear();
     TreePatternNode *Pat = I->getTree(j);
     if (Pat->getNumTypes() != 0) {
-      std::string Types;
+      raw_svector_ostream OS(TypesString);
       for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) {
         if (k > 0)
-          Types += ", ";
-        Types += Pat->getExtType(k).getAsString();
+          OS << ", ";
+        Pat->getExtType(k).writeToStream(OS);
       }
       I->error("Top-level forms in instruction pattern should have"
-               " void types, has types " + Types);
+               " void types, has types " +
+               OS.str());
     }
 
     // Find inputs and outputs, and verify the structure of the uses/defs.
     FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults,
                                 InstImpResults);
   }
 
   // Now that we have inputs and outputs of the pattern, inspect the operands
for (PatternToMatch &P : Copy) {
 
     bool HasDefault = Modes.count(DefaultMode);
     if (HasDefault)
       AppendPattern(P, DefaultMode);
   }
 }
 
 /// Dependent variable map for CodeGenDAGPattern variant generation
-typedef std::map<std::string, int> DepVarMap;
+typedef StringMap<int> DepVarMap;
 
 static void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) {
   if (N->isLeaf()) {
-    if (isa<DefInit>(N->getLeafValue()))
+    if (N->hasName() && isa<DefInit>(N->getLeafValue()))
       DepMap[N->getName()]++;
   } else {
     for (size_t i = 0, e = N->getNumChildren(); i != e; ++i)
       FindDepVarsOf(N->getChild(i), DepMap);
   }
 }
 
 /// Find dependent variables within child patterns
 static void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) {
   DepVarMap depcounts;
   FindDepVarsOf(N, depcounts);
-  for (const std::pair<std::string, int> &Pair : depcounts) {
-    if (Pair.second > 1)
-      DepVars.insert(Pair.first);
+  for (const auto &Pair : depcounts) {
+    if (Pair.getValue() > 1)
+      DepVars.insert(Pair.getKey());
   }
 }
 
 #ifndef NDEBUG
 /// Dump the dependent variable set:
 static void DumpDepVars(MultipleUseVarSet &DepVars) {
   if (DepVars.empty()) {
     DEBUG(errs() << "<empty set>");
   } else {
     DEBUG(errs() << "[ ");
-    for (const std::string &DepVar : DepVars) {
-      DEBUG(errs() << DepVar << " ");
+    for (const auto &DepVar : DepVars) {
+      DEBUG(errs() << DepVar.getKey() << " ");
     }
     DEBUG(errs() << "]");
   }
 }
 #endif
 
 
 /// CombineChildVariants - Given a bunch of permutations of each child of the