[TableGen] [ISel Matcher Emitter] Rework with two passes: one to size, one to emit

[Paul-C-Anagnostopoulos]

Summary

This patch reworks DAGISelMatcherEmitter.cpp in order to speed it up. It now makes two passes over the matcher tree: one to size the matchers and one to emit them. This eliminates the relaxation method that was used to size the matchers previously. The emitter produces exactly the same output as before.

For the AMDGPU target, the emitting phase took 88.5% of the TableGen run; now it takes 3.5% of the time. On my machine the run went from 751 seconds to 89 seconds.

[foad]

Looks good to me. I'm looking forward to the improved build times.

llvm/utils/TableGen/DAGISelMatcherEmitter.cpp

51

Did you mean to include this in this patch? It seems unrelated.

978

Seems unrelated?

[arsenm]

llvm/utils/TableGen/DAGISelMatcher.h

44

Probably should be size_t

[Paul-C-Anagnostopoulos]

I'll get this in as soon as there is some more review *and* I manage to reinstate my building ability. I just updated Visual Studio and can't build anything. Sigh.

llvm/utils/TableGen/DAGISelMatcherEmitter.cpp

51

This part of the update eliminates the extra pass over the matcher tree just to count the matcher kinds for the histogram. The counting was merged into the new first pass for sizing.

978

This part of the update eliminates the extra pass over the matcher tree just to count the matcher kinds for the histogram. The counting was merged into the new first pass for sizing.

[Paul-C-Anagnostopoulos]

llvm/utils/TableGen/DAGISelMatcher.h

44

Yes, I will fix this.

[foad]

llvm/utils/TableGen/DAGISelMatcherEmitter.cpp

51

Fair enough, sounds good!

[Paul-C-Anagnostopoulos]

Changed the child size to a size_t. And changed the VBR size to match.

[Paul-C-Anagnostopoulos]

I will auto-LGTM this revision on Friday.

[RKSimon]

llvm/utils/TableGen/DAGISelMatcher.h

92

We seem to mainly use this as "HighestKind + 1" - wouldn't a NumOfKinds / KindCount value be better (and wouldn't need the assignment to the previous enum value).

MorphNodeTo, // Build a node, finish a match and update results.
KindCount        // Total number of kind types.

[Paul-C-Anagnostopoulos]

llvm/utils/TableGen/DAGISelMatcher.h

92

I had that originally but changed my mind. Why? . . . Ah, because then the compiler complains when it isn't included in a switch on the kind. Is there a trick I don't know? Using default: just seems confusing.

[RKSimon]

llvm/utils/TableGen/DAGISelMatcher.h

92

OK - no worries for now then

[RKSimon]

LGTM - thank you for working on this!

[RKSimon]

llvm/utils/TableGen/DAGISelMatcherEmitter.cpp

1124

@Paul-C-Anagnostopoulos scan-build is warning that TotalSize is initialized but never read - is there anything useful we can do with TotalSize here?

https://llvm.org/reports/scan-build/report-DAGISelMatcherEmitter.cpp-EmitMatcherTable-39-50bd0b.html#EndPath

[foad]

llvm/utils/TableGen/DAGISelMatcherEmitter.cpp

1124

In a debug build I think it would make sense to assert that it matches the size calculated on line 1134.

llvm/utils/TableGen/DAGISelMatcher.h

namespace llvm {
   class SDNodeInfo;
   class TreePredicateFn;
   class TreePattern;
 
 Matcher *ConvertPatternToMatcher(const PatternToMatch &Pattern,unsigned Variant,
                                  const CodeGenDAGPatterns &CGP);
 void OptimizeMatcher(std::unique_ptr<Matcher> &Matcher,
                      const CodeGenDAGPatterns &CGP);
-void EmitMatcherTable(const Matcher *Matcher, const CodeGenDAGPatterns &CGP,
+void EmitMatcherTable(Matcher *Matcher, const CodeGenDAGPatterns &CGP,
                       raw_ostream &OS);
 
 
 /// Matcher - Base class for all the DAG ISel Matcher representation
 /// nodes.
 class Matcher {
   // The next matcher node that is executed after this one.  Null if this is the
   // last stage of a match.
   std::unique_ptr<Matcher> Next;
+  unsigned Size; // Size in bytes of matcher and all its children (if any).
   virtual void anchor();
 public:
   enum KindTy {
     // Matcher state manipulation.
     Scope,                // Push a checking scope.
     RecordNode,           // Record the current node.
     RecordChild,          // Record a child of the current node.
     RecordMemRef,         // Record the memref in the current node.
     CaptureGlueInput,     // If the current node has an input glue, save it.
     MoveChild,            // Move current node to specified child.
     MoveParent,           // Move current node to parent.
 
     // Predicate checking.
     CheckSame,            // Fail if not same as prev match.
     CheckChildSame,       // Fail if child not same as prev match.
     CheckPatternPredicate,
     CheckPredicate,       // Fail if node predicate fails.
     CheckOpcode,          // Fail if not opcode.
     SwitchOpcode,         // Dispatch based on opcode.
     CheckType,            // Fail if not correct type.
     SwitchType,           // Dispatch based on type.
     CheckChildType,       // Fail if child has wrong type.
     CheckInteger,         // Fail if wrong val.
     CheckChildInteger,    // Fail if child is wrong val.
     CheckCondCode,        // Fail if not condcode.
enum KindTy {
     EmitStringInteger,    // Create a TargetConstant from a string.
     EmitRegister,         // Create a register.
     EmitConvertToTarget,  // Convert a imm/fpimm to target imm/fpimm
     EmitMergeInputChains, // Merge together a chains for an input.
     EmitCopyToReg,        // Emit a copytoreg into a physreg.
     EmitNode,             // Create a DAG node
     EmitNodeXForm,        // Run a SDNodeXForm
     CompleteMatch,        // Finish a match and update the results.
-    MorphNodeTo           // Build a node, finish a match and update results.
+    MorphNodeTo,          // Build a node, finish a match and update results.
+
+    // Highest enum value; watch out when adding more.
+    HighestKind = MorphNodeTo
   };
   const KindTy Kind;
 
 protected:
   Matcher(KindTy K) : Kind(K) {}
 public:
   virtual ~Matcher() {}
 
+  unsigned getSize() const { return Size; }
+  void setSize(unsigned sz) { Size = sz; }
   KindTy getKind() const { return Kind; }
 
   Matcher *getNext() { return Next.get(); }
   const Matcher *getNext() const { return Next.get(); }
   void setNext(Matcher *C) { Next.reset(C); }
   Matcher *takeNext() { return Next.release(); }
 
   std::unique_ptr<Matcher> &getNextPtr() { return Next; }

llvm/utils/TableGen/DAGISelMatcherEmitter.cpp

 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
+
 using namespace llvm;
 
 enum {
   IndexWidth = 6,
   FullIndexWidth = IndexWidth + 4,
   HistOpcWidth = 40,
 };
 
 cl::OptionCategory DAGISelCat("Options for -gen-dag-isel");
 
 // To reduce generated source code size.
 static cl::opt<bool> OmitComments("omit-comments",
                                   cl::desc("Do not generate comments"),
                                   cl::init(false), cl::cat(DAGISelCat));
 
 static cl::opt<bool> InstrumentCoverage(
     "instrument-coverage",
     cl::desc("Generates tables to help identify patterns matched"),
     cl::init(false), cl::cat(DAGISelCat));
 
 namespace {
 class MatcherTableEmitter {
   const CodeGenDAGPatterns &CGP;
 
+  SmallVector<unsigned, Matcher::HighestKind+1> OpcodeCounts;
+
   DenseMap<TreePattern *, unsigned> NodePredicateMap;
   std::vector<TreePredicateFn> NodePredicates;
   std::vector<TreePredicateFn> NodePredicatesWithOperands;
 
   // We de-duplicate the predicates by code string, and use this map to track
   // all the patterns with "identical" predicates.
   StringMap<TinyPtrVector<TreePattern *>> NodePredicatesByCodeToRun;
 
if (It == VecPatterns.end()) {
       VecPatterns.insert(make_pair(std::move(P), VecPatterns.size()));
       VecIncludeStrings.push_back(std::move(include_loc));
       return VecIncludeStrings.size() - 1;
     }
     return It->second;
   }
 
 public:
-  MatcherTableEmitter(const CodeGenDAGPatterns &cgp)
-    : CGP(cgp) {}
+  MatcherTableEmitter(const CodeGenDAGPatterns &cgp) : CGP(cgp) {
+    OpcodeCounts.assign(Matcher::HighestKind+1, 0);
+  }
 
-  unsigned EmitMatcherList(const Matcher *N, unsigned Indent,
+  unsigned EmitMatcherList(const Matcher *N, const unsigned Indent,
                            unsigned StartIdx, raw_ostream &OS);
 
+  unsigned SizeMatcherList(Matcher *N, raw_ostream &OS);
+
   void EmitPredicateFunctions(raw_ostream &OS);
 
   void EmitHistogram(const Matcher *N, raw_ostream &OS);
 
   void EmitPatternMatchTable(raw_ostream &OS);
 
 private:
   void EmitNodePredicatesFunction(const std::vector<TreePredicateFn> &Preds,
                                   StringRef Decl, raw_ostream &OS);
 
-  unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
+  unsigned SizeMatcher(Matcher *N, raw_ostream &OS);
+
+  unsigned EmitMatcher(const Matcher *N, const unsigned Indent, unsigned CurrentIdx,
                        raw_ostream &OS);
 
   unsigned getNodePredicate(TreePredicateFn Pred) {
     TreePattern *TP = Pred.getOrigPatFragRecord();
     unsigned &Entry = NodePredicateMap[TP];
     if (Entry == 0) {
       TinyPtrVector<TreePattern *> &SameCodePreds =
           NodePredicatesByCodeToRun[Pred.getCodeToRunOnSDNode()];
static std::string getIncludePath(const Record *R) {
   assert(CurBuf && "Invalid or unspecified location!");
 
   Stream << SrcMgr.getBufferInfo(CurBuf).Buffer->getBufferIdentifier() << ":"
          << SrcMgr.FindLineNumber(L, CurBuf);
   Stream.str();
   return str;
 }
 
+/// This function traverses the matcher tree and sizes all the nodes
+/// that are children of the three kinds of nodes that have them.
+unsigned MatcherTableEmitter::
+SizeMatcherList(Matcher *N, raw_ostream &OS) {
+  unsigned Size = 0;
+  while (N) {
+    Size += SizeMatcher(N, OS);
+    N = N->getNext();
+  }
+  return Size;
+}
+
+/// This function sizes the children of the three kinds of nodes that
+/// have them. It does so by using special cases for those three
+/// nodes, but sharing the code in EmitMatcher() for the other kinds.
+unsigned MatcherTableEmitter::
+SizeMatcher(Matcher *N, raw_ostream &OS) {
+  unsigned Idx = 0;
+
+  ++OpcodeCounts[N->getKind()];
+  switch (N->getKind()) {
+  // The Scope matcher has its kind, a series of child size + child,
+  // and a trailing zero.
+  case Matcher::Scope: {
+    ScopeMatcher *SM = cast<ScopeMatcher>(N);
+    assert(SM->getNext() == nullptr && "Scope matcher should not have next");
+    unsigned Size = 1; // Count the kind.
+    for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) {
+      const unsigned ChildSize = SizeMatcherList(SM->getChild(i), OS);
+      assert(ChildSize != 0 && "Matcher cannot have child of size 0");
+      SM->getChild(i)->setSize(ChildSize);
+      Size += GetVBRSize(ChildSize) + ChildSize; // Count VBR and child size.
+    }
+    ++Size; // Count the zero sentinel.
+    return Size;
+  }
+
+  // SwitchOpcode and SwitchType have their kind, a series of child size +
+  // opcode/type + child, and a trailing zero.
+  case Matcher::SwitchOpcode:
+  case Matcher::SwitchType: {
+    unsigned Size = 1; // Count the kind.
+    unsigned NumCases;
+    if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N))
+      NumCases = SOM->getNumCases();
+    else
+      NumCases = cast<SwitchTypeMatcher>(N)->getNumCases();
+    for (unsigned i = 0, e = NumCases; i != e; ++i) {
+      Matcher *Child;
+      if (SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) {
+        Child = SOM->getCaseMatcher(i);
+        Size += 2; // Count the child's opcode.
+      } else {
+        Child = cast<SwitchTypeMatcher>(N)->getCaseMatcher(i);
+        ++Size; // Count the child's type.
+      }
+      const unsigned ChildSize = SizeMatcherList(Child, OS);
+      assert(ChildSize != 0 && "Matcher cannot have child of size 0");
+      Child->setSize(ChildSize);
+      Size += GetVBRSize(ChildSize) + ChildSize; // Count VBR and child size.
+    }
+    ++Size; // Count the zero sentinel.
+    return Size;
+  }
+
+  default:
+    // Employ the matcher emitter to size other matchers.
+    return EmitMatcher(N, 0, Idx, OS);
+  }
+  llvm_unreachable("Unreachable");
+}
+
 static void BeginEmitFunction(raw_ostream &OS, StringRef RetType,
                               StringRef Decl, bool AddOverride) {
   OS << "#ifdef GET_DAGISEL_DECL\n";
   OS << RetType << ' ' << Decl;
   if (AddOverride)
     OS << " override";
   OS << ";\n"
         "#endif\n"
void MatcherTableEmitter::EmitPatternMatchTable(raw_ostream &OS) {
   OS << "\n};";
   OS << "\nreturn StringRef(INCLUDE_PATH_TABLE[Index]);";
   OS << "\n}\n";
   EndEmitFunction(OS);
 }
 
 /// EmitMatcher - Emit bytes for the specified matcher and return
 /// the number of bytes emitted.
 unsigned MatcherTableEmitter::
-EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
+EmitMatcher(const Matcher *N, const unsigned Indent, unsigned CurrentIdx,
             raw_ostream &OS) {
   OS.indent(Indent);
 
   switch (N->getKind()) {
   case Matcher::Scope: {
     const ScopeMatcher *SM = cast<ScopeMatcher>(N);
-    assert(SM->getNext() == nullptr && "Shouldn't have next after scope");
-
     unsigned StartIdx = CurrentIdx;
 
     // Emit all of the children.
-    SmallString<128> TmpBuf;
     for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) {
       if (i == 0) {
         OS << "OPC_Scope, ";
         ++CurrentIdx;
       } else  {
         if (!OmitComments) {
           OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/";
           OS.indent(Indent) << "/*Scope*/ ";
         } else
           OS.indent(Indent);
       }
 
-      // We need to encode the child and the offset of the failure code before
-      // emitting either of them.  Handle this by buffering the output into a
-      // string while we get the size.  Unfortunately, the offset of the
-      // children depends on the VBR size of the child, so for large children we
-      // have to iterate a bit.
-      unsigned ChildSize = 0;
-      unsigned VBRSize = 0;
-      do {
-        VBRSize = GetVBRSize(ChildSize);
-
-        TmpBuf.clear();
-        raw_svector_ostream OS(TmpBuf);
-        ChildSize = EmitMatcherList(SM->getChild(i), Indent+1,
-                                    CurrentIdx+VBRSize, OS);
-      } while (GetVBRSize(ChildSize) != VBRSize);
-
-      assert(ChildSize != 0 && "Should not have a zero-sized child!");
-
-      CurrentIdx += EmitVBRValue(ChildSize, OS);
+      unsigned ChildSize = SM->getChild(i)->getSize();
+      unsigned VBRSize = GetVBRSize(ChildSize);
+      EmitVBRValue(ChildSize, OS);
       if (!OmitComments) {
-        OS << "/*->" << CurrentIdx+ChildSize << "*/";
-
+        OS << "/*->" << CurrentIdx + VBRSize + ChildSize << "*/";
         if (i == 0)
           OS << " // " << SM->getNumChildren() << " children in Scope";
       }
+      OS << '\n';
 
-      OS << '\n' << TmpBuf;
-      CurrentIdx += ChildSize;
+      ChildSize = EmitMatcherList(SM->getChild(i), Indent+1,
+                                  CurrentIdx + VBRSize, OS);
+      assert(ChildSize == SM->getChild(i)->getSize() &&
+             "Emitted child size does not match calculated size");
+      CurrentIdx += VBRSize + ChildSize;
     }
 
     // Emit a zero as a sentinel indicating end of 'Scope'.
     if (!OmitComments)
       OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/";
     OS.indent(Indent) << "0, ";
     if (!OmitComments)
       OS << "/*End of Scope*/";
case Matcher::SwitchType: {
     }
 
     if (!OmitComments)
       OS << "/*" << NumCases << " cases */";
     OS << ", ";
     ++CurrentIdx;
 
     // For each case we emit the size, then the opcode, then the matcher.
-    SmallString<128> TmpBuf;
     for (unsigned i = 0, e = NumCases; i != e; ++i) {
       const Matcher *Child;
       unsigned IdxSize;
       if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) {
         Child = SOM->getCaseMatcher(i);
         IdxSize = 2;  // size of opcode in table is 2 bytes.
       } else {
         Child = cast<SwitchTypeMatcher>(N)->getCaseMatcher(i);
         IdxSize = 1;  // size of type in table is 1 byte.
       }
 
-      // We need to encode the opcode and the offset of the case code before
-      // emitting the case code.  Handle this by buffering the output into a
-      // string while we get the size.  Unfortunately, the offset of the
-      // children depends on the VBR size of the child, so for large children we
-      // have to iterate a bit.
-      unsigned ChildSize = 0;
-      unsigned VBRSize = 0;
-      do {
-        VBRSize = GetVBRSize(ChildSize);
-
-        TmpBuf.clear();
-        raw_svector_ostream OS(TmpBuf);
-        ChildSize = EmitMatcherList(Child, Indent+1, CurrentIdx+VBRSize+IdxSize,
-                                    OS);
-      } while (GetVBRSize(ChildSize) != VBRSize);
-
-      assert(ChildSize != 0 && "Should not have a zero-sized child!");
-
       if (i != 0) {
         if (!OmitComments)
           OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/";
         OS.indent(Indent);
         if (!OmitComments)
           OS << (isa<SwitchOpcodeMatcher>(N) ?
                      "/*SwitchOpcode*/ " : "/*SwitchType*/ ");
       }
 
-      // Emit the VBR.
-      CurrentIdx += EmitVBRValue(ChildSize, OS);
-
+      unsigned ChildSize = Child->getSize();
+      CurrentIdx += EmitVBRValue(ChildSize, OS) + IdxSize;
       if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N))
         OS << "TARGET_VAL(" << SOM->getCaseOpcode(i).getEnumName() << "),";
       else
         OS << getEnumName(cast<SwitchTypeMatcher>(N)->getCaseType(i)) << ',';
-
-      CurrentIdx += IdxSize;
-
       if (!OmitComments)
-        OS << "// ->" << CurrentIdx+ChildSize;
+        OS << "// ->" << CurrentIdx + ChildSize;
       OS << '\n';
-      OS << TmpBuf;
+
+      ChildSize = EmitMatcherList(Child, Indent+1, CurrentIdx, OS);
+      assert(ChildSize == Child->getSize() &&
+             "Emitted child size does not match calculated size");
       CurrentIdx += ChildSize;
     }
 
     // Emit the final zero to terminate the switch.
     if (!OmitComments)
       OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/";
     OS.indent(Indent) << "0,";
     if (!OmitComments)
       OS << (isa<SwitchOpcodeMatcher>(N) ?
              " // EndSwitchOpcode" : " // EndSwitchType");
 
     OS << '\n';
-    ++CurrentIdx;
-    return CurrentIdx-StartIdx;
+    return CurrentIdx - StartIdx + 1;
   }
 
  case Matcher::CheckType:
     if (cast<CheckTypeMatcher>(N)->getResNo() == 0) {
       OS << "OPC_CheckType, "
          << getEnumName(cast<CheckTypeMatcher>(N)->getType()) << ",\n";
       return 2;
     }
case Matcher::CompleteMatch: {
     }
     OS << '\n';
     return 2 + NumResultBytes + NumCoveredBytes;
   }
   }
   llvm_unreachable("Unreachable");
 }
 
-/// EmitMatcherList - Emit the bytes for the specified matcher subtree.
+/// This function traverses the matcher tree and emits all the nodes.
+/// The nodes have already been sized.
 unsigned MatcherTableEmitter::
-EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
+EmitMatcherList(const Matcher *N, const unsigned Indent, unsigned CurrentIdx,
                 raw_ostream &OS) {
   unsigned Size = 0;
   while (N) {
     if (!OmitComments)
       OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/";
     unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS);
     Size += MatcherSize;
     CurrentIdx += MatcherSize;
if (Preds.empty())
     return;
 
   BeginEmitFunction(OS, "bool", Decl, true/*AddOverride*/);
   OS << "{\n";
   OS << "  switch (PredNo) {\n";
   OS << "  default: llvm_unreachable(\"Invalid predicate in table?\");\n";
   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
     // Emit the predicate code corresponding to this pattern.
-    TreePredicateFn PredFn = Preds[i];
+    const TreePredicateFn PredFn = Preds[i];
 
     assert(!PredFn.isAlwaysTrue() && "No code in this predicate");
     OS << "  case " << i << ": {\n";
     for (auto *SimilarPred :
              NodePredicatesByCodeToRun[PredFn.getCodeToRunOnSDNode()])
       OS << "    // " << TreePredicateFn(SimilarPred).getFnName() <<'\n';
 
     OS << PredFn.getCodeToRunOnSDNode() << "\n  }\n";
   }
   OS << "  }\n";
   OS << "}\n";
   EndEmitFunction(OS);
 }
for (unsigned i = 0, e = NodeXForms.size(); i != e; ++i) {
       OS << Code << "\n  }\n";
     }
     OS << "  }\n";
     OS << "}\n";
     EndEmitFunction(OS);
   }
 }
 
-static void BuildHistogram(const Matcher *M, std::vector<unsigned> &OpcodeFreq){
-  for (; M != nullptr; M = M->getNext()) {
-    // Count this node.
-    if (unsigned(M->getKind()) >= OpcodeFreq.size())
-      OpcodeFreq.resize(M->getKind()+1);
-    OpcodeFreq[M->getKind()]++;
-
-    // Handle recursive nodes.
-    if (const ScopeMatcher *SM = dyn_cast<ScopeMatcher>(M)) {
-      for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i)
-        BuildHistogram(SM->getChild(i), OpcodeFreq);
-    } else if (const SwitchOpcodeMatcher *SOM =
-                 dyn_cast<SwitchOpcodeMatcher>(M)) {
-      for (unsigned i = 0, e = SOM->getNumCases(); i != e; ++i)
-        BuildHistogram(SOM->getCaseMatcher(i), OpcodeFreq);
-    } else if (const SwitchTypeMatcher *STM = dyn_cast<SwitchTypeMatcher>(M)) {
-      for (unsigned i = 0, e = STM->getNumCases(); i != e; ++i)
-        BuildHistogram(STM->getCaseMatcher(i), OpcodeFreq);
-    }
-  }
-}
-
 static StringRef getOpcodeString(Matcher::KindTy Kind) {
   switch (Kind) {
   case Matcher::Scope: return "OPC_Scope"; break;
   case Matcher::RecordNode: return "OPC_RecordNode"; break;
   case Matcher::RecordChild: return "OPC_RecordChild"; break;
   case Matcher::RecordMemRef: return "OPC_RecordMemRef"; break;
   case Matcher::CaptureGlueInput: return "OPC_CaptureGlueInput"; break;
   case Matcher::MoveChild: return "OPC_MoveChild"; break;
static StringRef getOpcodeString(Matcher::KindTy Kind) {
   llvm_unreachable("Unhandled opcode?");
 }
 
 void MatcherTableEmitter::EmitHistogram(const Matcher *M,
                                         raw_ostream &OS) {
   if (OmitComments)
     return;
 
-  std::vector<unsigned> OpcodeFreq;
-  BuildHistogram(M, OpcodeFreq);
-
   OS << "  // Opcode Histogram:\n";
-  for (unsigned i = 0, e = OpcodeFreq.size(); i != e; ++i) {
+  for (unsigned i = 0, e = OpcodeCounts.size(); i != e; ++i) {
     OS << "  // #"
        << left_justify(getOpcodeString((Matcher::KindTy)i), HistOpcWidth)
-       << " = " << OpcodeFreq[i] << '\n';
+       << " = " << OpcodeCounts[i] << '\n';
   }
   OS << '\n';
 }
 
 
-void llvm::EmitMatcherTable(const Matcher *TheMatcher,
+void llvm::EmitMatcherTable(Matcher *TheMatcher,
                             const CodeGenDAGPatterns &CGP,
                             raw_ostream &OS) {
   OS << "#if defined(GET_DAGISEL_DECL) && defined(GET_DAGISEL_BODY)\n";
   OS << "#error GET_DAGISEL_DECL and GET_DAGISEL_BODY cannot be both defined, ";
   OS << "undef both for inline definitions\n";
   OS << "#endif\n\n";
 
   // Emit a check for omitted class name.
void llvm::EmitMatcherTable(Matcher *TheMatcher,
   OS << "#define DAGISEL_CLASS_COLONCOLON GET_DAGISEL_BODY ::\n";
   OS << "#else\n";
   OS << "#define DAGISEL_CLASS_COLONCOLON\n";
   OS << "#endif\n\n";
 
   BeginEmitFunction(OS, "void", "SelectCode(SDNode *N)", false/*AddOverride*/);
   MatcherTableEmitter MatcherEmitter(CGP);
 
+  // First we size all the children of the three kinds of matchers that have
+  // them. This is done by sharing the code in EmitMatcher(). but we don't
+  // want to emit anything, so we turn off comments and use a null stream.
+  bool SaveOmitComments = OmitComments;
+  OmitComments = true;
+  raw_null_ostream NullOS;
+  unsigned TotalSize = MatcherEmitter.SizeMatcherList(TheMatcher, NullOS);
+  OmitComments = SaveOmitComments;
+
+  // Now that the matchers are sized, we can emit the code for them to the
+  // final stream.
   OS << "{\n";
   OS << "  // Some target values are emitted as 2 bytes, TARGET_VAL handles\n";
   OS << "  // this.\n";
   OS << "  #define TARGET_VAL(X) X & 255, unsigned(X) >> 8\n";
   OS << "  static const unsigned char MatcherTable[] = {\n";
-  unsigned TotalSize = MatcherEmitter.EmitMatcherList(TheMatcher, 1, 0, OS);
+  TotalSize = MatcherEmitter.EmitMatcherList(TheMatcher, 1, 0, OS);
   OS << "    0\n  }; // Total Array size is " << (TotalSize+1) << " bytes\n\n";
 
   MatcherEmitter.EmitHistogram(TheMatcher, OS);
 
   OS << "  #undef TARGET_VAL\n";
   OS << "  SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n";
   OS << "}\n";
   EndEmitFunction(OS);