implement a simple proof-of-concept optimization for

the new isel: fold movechild+record+moveparent into a
single recordchild N node.  This shrinks the X86 table
from 125443 to 117502 bytes.

llvm-svn: 97031

5 files changed, 73 insertions, 4 deletions

diff --git a/llvm/utils/TableGen/DAGISelEmitter.cpp b/llvm/utils/TableGen/DAGISelEmitter.cpp
index 2d2ab3e707e..7a01caab85d 100644
--- a/llvm/utils/TableGen/DAGISelEmitter.cpp
+++ b/llvm/utils/TableGen/DAGISelEmitter.cpp
@@ -1983,7 +1983,7 @@ void DAGISelEmitter::run(raw_ostream &OS) {
       Matcher = new PushMatcherNode(N, Matcher);
   }
 
-  OptimizeMatcher(Matcher);
+  Matcher = OptimizeMatcher(Matcher);
   //Matcher->dump();
   EmitMatcherTable(Matcher, OS);
   delete Matcher;
diff --git a/llvm/utils/TableGen/DAGISelMatcher.cpp b/llvm/utils/TableGen/DAGISelMatcher.cpp
index 6fb417cf965..9bb8fd51502 100644
--- a/llvm/utils/TableGen/DAGISelMatcher.cpp
+++ b/llvm/utils/TableGen/DAGISelMatcher.cpp
@@ -35,6 +35,11 @@ void RecordMatcherNode::print(raw_ostream &OS, unsigned indent) const {
   printNext(OS, indent);
 }
 
+void RecordChildMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "RecordChild: " << ChildNo << '\n';
+  printNext(OS, indent);
+}
+
 void RecordMemRefMatcherNode::print(raw_ostream &OS, unsigned indent) const {
   OS.indent(indent) << "RecordMemRef\n";
   printNext(OS, indent);
diff --git a/llvm/utils/TableGen/DAGISelMatcher.h b/llvm/utils/TableGen/DAGISelMatcher.h
index 4dcbc8f55fc..ab84168bd8b 100644
--- a/llvm/utils/TableGen/DAGISelMatcher.h
+++ b/llvm/utils/TableGen/DAGISelMatcher.h
@@ -26,7 +26,7 @@ namespace llvm {
 
 MatcherNode *ConvertPatternToMatcher(const PatternToMatch &Pattern,
                                      const CodeGenDAGPatterns &CGP);
-void OptimizeMatcher(const MatcherNode *Matcher);
+MatcherNode *OptimizeMatcher(MatcherNode *Matcher);
 void EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &OS);
 
   
@@ -41,6 +41,7 @@ public:
     // Matcher state manipulation.
     Push,                 // 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.
     CaptureFlagInput,     // If the current node has an input flag, save it.
     MoveChild,            // Move current node to specified child.
@@ -86,6 +87,9 @@ public:
   MatcherNode *getNext() { return Next.get(); }
   const MatcherNode *getNext() const { return Next.get(); }
   void setNext(MatcherNode *C) { Next.reset(C); }
+  MatcherNode *takeNext() { return Next.take(); }
+
+  OwningPtr<MatcherNode> &getNextPtr() { return Next; }
   
   static inline bool classof(const MatcherNode *) { return true; }
   
@@ -109,6 +113,7 @@ public:
   MatcherNode *getFailure() { return Failure.get(); }
   const MatcherNode *getFailure() const { return Failure.get(); }
   void setFailure(MatcherNode *N) { Failure.reset(N); }
+  OwningPtr<MatcherNode> &getFailurePtr() { return Failure; }
 
   static inline bool classof(const MatcherNode *N) {
     return N->getKind() == Push;
@@ -135,6 +140,29 @@ public:
   virtual void print(raw_ostream &OS, unsigned indent = 0) const;
 };
   
+/// RecordChildMatcherNode - Save a numbered child of the current node, or fail
+/// the match if it doesn't exist.  This is logically equivalent to:
+///    MoveChild N + RecordNode + MoveParent.
+class RecordChildMatcherNode : public MatcherNode {
+  unsigned ChildNo;
+  
+  /// WhatFor - This is a string indicating why we're recording this.  This
+  /// should only be used for comment generation not anything semantic.
+  std::string WhatFor;
+public:
+  RecordChildMatcherNode(unsigned childno, const std::string &whatfor)
+  : MatcherNode(RecordChild), ChildNo(childno), WhatFor(whatfor) {}
+  
+  unsigned getChildNo() const { return ChildNo; }
+  const std::string &getWhatFor() const { return WhatFor; }
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == RecordChild;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
 /// RecordMemRefMatcherNode - Save the current node's memref.
 class RecordMemRefMatcherNode : public MatcherNode {
 public:
diff --git a/llvm/utils/TableGen/DAGISelMatcherEmitter.cpp b/llvm/utils/TableGen/DAGISelMatcherEmitter.cpp
index ecc75c8c4c6..e78be79119d 100644
--- a/llvm/utils/TableGen/DAGISelMatcherEmitter.cpp
+++ b/llvm/utils/TableGen/DAGISelMatcherEmitter.cpp
@@ -159,6 +159,13 @@ EmitMatcher(const MatcherNode *N, unsigned Indent, formatted_raw_ostream &OS) {
     OS.PadToColumn(CommentIndent) << "// "
        << cast<RecordMatcherNode>(N)->getWhatFor() << '\n';
     return 1;
+
+  case MatcherNode::RecordChild:
+    OS << "OPC_RecordChild" << cast<RecordChildMatcherNode>(N)->getChildNo()
+       << ',';
+    OS.PadToColumn(CommentIndent) << "// "
+      << cast<RecordChildMatcherNode>(N)->getWhatFor() << '\n';
+    return 1;
       
   case MatcherNode::RecordMemRef:
     OS << "OPC_RecordMemRef,\n";
diff --git a/llvm/utils/TableGen/DAGISelMatcherOpt.cpp b/llvm/utils/TableGen/DAGISelMatcherOpt.cpp
index 7859f36eef6..d3658202a66 100644
--- a/llvm/utils/TableGen/DAGISelMatcherOpt.cpp
+++ b/llvm/utils/TableGen/DAGISelMatcherOpt.cpp
@@ -14,6 +14,35 @@
 #include "DAGISelMatcher.h"
 using namespace llvm;
 
-void llvm::OptimizeMatcher(const MatcherNode *Matcher) {
-  // Nothing yet.
+
+static void FormRecordChildNodes(OwningPtr<MatcherNode> &Matcher) {
+  // If we reached the end of the chain, we're done.
+  MatcherNode *N = Matcher.get();
+  if (N == 0) return;
+  
+  // If we have a push node, walk down both edges.
+  if (PushMatcherNode *Push = dyn_cast<PushMatcherNode>(N))
+    FormRecordChildNodes(Push->getFailurePtr());
+  
+  // If we found a movechild node, check to see if our pattern matches.
+  if (MoveChildMatcherNode *MC = dyn_cast<MoveChildMatcherNode>(N)) {
+    if (RecordMatcherNode *RM = dyn_cast<RecordMatcherNode>(MC->getNext()))
+      if (MoveParentMatcherNode *MP = 
+                 dyn_cast<MoveParentMatcherNode>(RM->getNext())) {
+        MatcherNode *New
+          = new RecordChildMatcherNode(MC->getChildNo(), RM->getWhatFor());
+        New->setNext(MP->takeNext());
+        Matcher.reset(New);
+        return FormRecordChildNodes(Matcher);
+      }
+  }
+
+  FormRecordChildNodes(N->getNextPtr());
+}
+
+
+MatcherNode *llvm::OptimizeMatcher(MatcherNode *Matcher) {
+  OwningPtr<MatcherNode> MatcherPtr(Matcher);
+  FormRecordChildNodes(MatcherPtr);
+  return MatcherPtr.take();
 }