change the scope node to include a list of children to be checked

instead of to have a chained series of scope nodes.  This makes
the generated table smaller, improves the efficiency of the
interpreter, and make the factoring optimization much more 
reasonable to implement.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97160 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 124 insertions, 94 deletions

diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp
index fbf3f86e08..5e2b07d0d4 100644
--- a/utils/TableGen/DAGISelEmitter.cpp
+++ b/utils/TableGen/DAGISelEmitter.cpp
@@ -1945,8 +1945,6 @@ void DAGISelEmitter::run(raw_ostream &OS) {
   }
   
 #ifdef ENABLE_NEW_ISEL
-  Matcher *TheMatcher = 0;
-
   // Add all the patterns to a temporary list so we can sort them.
   std::vector<const PatternToMatch*> Patterns;
   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end();
@@ -1960,20 +1958,13 @@ void DAGISelEmitter::run(raw_ostream &OS) {
                    PatternSortingPredicate2(CGP));
   
   
-  // Walk the patterns backwards (since we append to the front of the generated
-  // code), building a matcher for each and adding it to the matcher for the
-  // whole target.
-  while (!Patterns.empty()) {
-    const PatternToMatch &Pattern = *Patterns.back();
-    Patterns.pop_back();
-    
-    Matcher *N = ConvertPatternToMatcher(Pattern, CGP);
-    
-    if (TheMatcher == 0)
-      TheMatcher = N;
-    else
-      TheMatcher = new ScopeMatcher(N, TheMatcher);
-  }
+  // Convert each pattern into Matcher's.
+  std::vector<Matcher*> PatternMatchers;
+  for (unsigned i = 0, e = Patterns.size(); i != e; ++i)
+    PatternMatchers.push_back(ConvertPatternToMatcher(*Patterns[i], CGP));
+  
+  Matcher *TheMatcher = new ScopeMatcher(&PatternMatchers[0],
+                                         PatternMatchers.size());
 
   TheMatcher = OptimizeMatcher(TheMatcher);
   //Matcher->dump();
diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp
index e01292801c..561d6127e8 100644
--- a/utils/TableGen/DAGISelMatcher.cpp
+++ b/utils/TableGen/DAGISelMatcher.cpp
@@ -25,9 +25,18 @@ void Matcher::print(raw_ostream &OS, unsigned indent) const {
     return Next->print(OS, indent);
 }
 
+ScopeMatcher::~ScopeMatcher() {
+  for (unsigned i = 0, e = Children.size(); i != e; ++i)
+    delete Children[i];
+}
+
+
+// printImpl methods.
+
 void ScopeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
   OS.indent(indent) << "Scope\n";
-  Check->print(OS, indent+2);
+  for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+    getChild(i)->print(OS, indent+2);
 }
 
 void RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
diff --git a/utils/TableGen/DAGISelMatcher.h b/utils/TableGen/DAGISelMatcher.h
index 0bc44e7473..6599b21e93 100644
--- a/utils/TableGen/DAGISelMatcher.h
+++ b/utils/TableGen/DAGISelMatcher.h
@@ -111,21 +111,32 @@ protected:
   virtual unsigned getHashImpl() const = 0;
 };
   
-/// ScopeMatcher - This pushes a failure scope on the stack and evaluates
-/// 'Check'.  If 'Check' fails to match, it pops its scope and continues on to
-/// 'Next'.
+/// ScopeMatcher - This attempts to match each of its children to find the first
+/// one that successfully matches.  If one child fails, it tries the next child.
+/// If none of the children match then this check fails.  It never has a 'next'.
 class ScopeMatcher : public Matcher {
-  OwningPtr<Matcher> Check;
+  SmallVector<Matcher*, 4> Children;
 public:
-  ScopeMatcher(Matcher *check = 0, Matcher *next = 0)
-    : Matcher(Scope), Check(check) {
-    setNext(next);
+  ScopeMatcher(Matcher *const *children, unsigned numchildren)
+    : Matcher(Scope), Children(children, children+numchildren) {
   }
+  virtual ~ScopeMatcher();
   
-  Matcher *getCheck() { return Check.get(); }
-  const Matcher *getCheck() const { return Check.get(); }
-  void setCheck(Matcher *N) { Check.reset(N); }
-  OwningPtr<Matcher> &getCheckPtr() { return Check; }
+  unsigned getNumChildren() const { return Children.size(); }
+  
+  Matcher *getChild(unsigned i) { return Children[i]; }
+  const Matcher *getChild(unsigned i) const { return Children[i]; }
+  
+  void resetChild(unsigned i, Matcher *N) {
+    delete Children[i];
+    Children[i] = N;
+  }
+
+  Matcher *takeChild(unsigned i) {
+    Matcher *Res = Children[i];
+    Children[i] = 0;
+    return Res;
+  }
 
   static inline bool classof(const Matcher *N) {
     return N->getKind() == Scope;
@@ -134,7 +145,7 @@ public:
 private:
   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
   virtual bool isEqualImpl(const Matcher *M) const { return false; }
-  virtual unsigned getHashImpl() const { return 0; }
+  virtual unsigned getHashImpl() const { return 12312; }
 };
 
 /// RecordMatcher - Save the current node in the operand list.
diff --git a/utils/TableGen/DAGISelMatcherEmitter.cpp b/utils/TableGen/DAGISelMatcherEmitter.cpp
index 93dbf2d162..d2eab2741c 100644
--- a/utils/TableGen/DAGISelMatcherEmitter.cpp
+++ b/utils/TableGen/DAGISelMatcherEmitter.cpp
@@ -88,7 +88,7 @@ public:
   
   void EmitHistogram(formatted_raw_ostream &OS);
 private:
-  unsigned EmitMatcher(const Matcher *N, unsigned Indent,
+  unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
                        formatted_raw_ostream &OS);
   
   unsigned getNodePredicate(StringRef PredName) {
@@ -129,6 +129,17 @@ private:
 };
 } // end anonymous namespace.
 
+static unsigned GetVBRSize(unsigned Val) {
+  if (Val <= 127) return 1;
+  
+  unsigned NumBytes = 0;
+  while (Val >= 128) {
+    Val >>= 7;
+    ++NumBytes;
+  }
+  return NumBytes+1;
+}
+
 /// EmitVBRValue - Emit the specified value as a VBR, returning the number of
 /// bytes emitted.
 static unsigned EmitVBRValue(unsigned Val, raw_ostream &OS) {
@@ -151,11 +162,58 @@ static unsigned EmitVBRValue(unsigned Val, raw_ostream &OS) {
 /// EmitMatcherOpcodes - Emit bytes for the specified matcher and return
 /// the number of bytes emitted.
 unsigned MatcherTableEmitter::
-EmitMatcher(const Matcher *N, unsigned Indent, formatted_raw_ostream &OS) {
+EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
+            formatted_raw_ostream &OS) {
   OS.PadToColumn(Indent*2);
   
   switch (N->getKind()) {
-  case Matcher::Scope: assert(0 && "Should be handled by caller");
+  case Matcher::Scope: {
+    const ScopeMatcher *SM = cast<ScopeMatcher>(N);
+    assert(SM->getNext() == 0 && "Shouldn't have next after scope");
+    
+    unsigned StartIdx = CurrentIdx;
+    
+    // Emit all of the children.
+    for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) {
+      if (i == 0) {
+        OS << "OPC_Scope, ";
+        ++CurrentIdx;
+      } else {
+        OS << "/*" << CurrentIdx << "*/";
+        OS.PadToColumn(Indent*2) << "/*Scope*/ ";
+      }
+
+      // 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.
+      SmallString<128> TmpBuf;
+      unsigned ChildSize = 0;
+      unsigned VBRSize = 0;
+      do {
+        VBRSize = GetVBRSize(ChildSize);
+        
+        TmpBuf.clear();
+        raw_svector_ostream OS(TmpBuf);
+        formatted_raw_ostream FOS(OS);
+        ChildSize = EmitMatcherList(cast<ScopeMatcher>(N)->getChild(i),
+                                   Indent+1, CurrentIdx+VBRSize, FOS);
+      } while (GetVBRSize(ChildSize) != VBRSize);
+      
+      assert(ChildSize != 0 && "Should not have a zero-sized child!");
+    
+      CurrentIdx += EmitVBRValue(ChildSize, OS);
+      OS << '\n' << TmpBuf.str();
+      CurrentIdx += ChildSize;
+    }
+    
+    // Emit a zero as a sentinel indicating end of 'Scope'.
+    OS << "/*" << CurrentIdx << "*/";
+    OS.PadToColumn(Indent*2) << "0, /*End of Scope*/\n";
+    return CurrentIdx - StartIdx + 1;
+  }
+      
   case Matcher::RecordNode:
     OS << "OPC_RecordNode,";
     OS.PadToColumn(CommentIndent) << "// "
@@ -387,52 +445,8 @@ EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
       Histogram.resize(N->getKind()+1);
     Histogram[N->getKind()]++;
     
-    // Scope is a special case since it is binary.
-    if (const ScopeMatcher *SMN = dyn_cast<ScopeMatcher>(N)) {
-      // 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.
-      SmallString<128> TmpBuf;
-      unsigned NextSize;
-      {
-        raw_svector_ostream OS(TmpBuf);
-        formatted_raw_ostream FOS(OS);
-        NextSize = EmitMatcherList(cast<ScopeMatcher>(N)->getCheck(),
-                                   Indent+1, CurrentIdx+2, FOS);
-      }
-
-      // In the unlikely event that we have something too big to emit with a
-      // one byte offset, regenerate it with a two-byte one.
-      if (NextSize > 255) {
-        TmpBuf.clear();
-        raw_svector_ostream OS(TmpBuf);
-        formatted_raw_ostream FOS(OS);
-        NextSize = EmitMatcherList(cast<ScopeMatcher>(N)->getCheck(),
-                                   Indent+1, CurrentIdx+3, FOS);
-        if (NextSize > 65535) {
-          errs() <<
-            "Tblgen internal error: can't handle pattern this complex yet\n";
-          exit(1);
-        }
-      }
-      
-      OS << "/*" << CurrentIdx << "*/";
-      OS.PadToColumn(Indent*2);
-      
-      if (NextSize < 256)
-        OS << "OPC_Scope, " << NextSize << ",\n";
-      else
-        OS << "OPC_Scope2, " << (NextSize&255) << ", " << (NextSize>>8) <<",\n";
-      OS << TmpBuf.str();
-      
-      Size += 2+NextSize;
-      CurrentIdx += 2+NextSize;
-      N = SMN->getNext();
-      continue;
-    }
-  
     OS << "/*" << CurrentIdx << "*/";
-    unsigned MatcherSize = EmitMatcher(N, Indent, OS);
+    unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS);
     Size += MatcherSize;
     CurrentIdx += MatcherSize;
     
diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp
index 002637b47d..9a6edd3b4e 100644
--- a/utils/TableGen/DAGISelMatcherOpt.cpp
+++ b/utils/TableGen/DAGISelMatcherOpt.cpp
@@ -21,9 +21,15 @@ static void ContractNodes(OwningPtr<Matcher> &MatcherPtr) {
   Matcher *N = MatcherPtr.get();
   if (N == 0) return;
   
-  // If we have a scope node, walk down both edges.
-  if (ScopeMatcher *Push = dyn_cast<ScopeMatcher>(N))
-    ContractNodes(Push->getCheckPtr());
+  // If we have a scope node, walk down all of the children.
+  if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
+    for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
+      OwningPtr<Matcher> Child(Scope->takeChild(i));
+      ContractNodes(Child);
+      Scope->resetChild(i, Child.take());
+    }
+    return;
+  }
   
   // If we found a movechild node with a node that comes in a 'foochild' form,
   // transform it.
@@ -61,32 +67,31 @@ static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
   if (N == 0) return;
   
   // If this is not a push node, just scan for one.
-  if (!isa<ScopeMatcher>(N))
+  ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N);
+  if (Scope == 0)
     return FactorNodes(N->getNextPtr());
   
-  // Okay, pull together the series of linear push nodes into a vector so we can
+  // Okay, pull together the children of the scope node into a vector so we can
   // inspect it more easily.  While we're at it, bucket them up by the hash
   // code of their first predicate.
   SmallVector<Matcher*, 32> OptionsToMatch;
   typedef DenseMap<unsigned, std::vector<Matcher*> > HashTableTy;
   HashTableTy MatchersByHash;
   
-  Matcher *CurNode = N;
-  for (; ScopeMatcher *PMN = dyn_cast<ScopeMatcher>(CurNode);
-       CurNode = PMN->getNext()) {
+  for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
     // Factor the subexpression.
-    FactorNodes(PMN->getCheckPtr());
-    if (Matcher *Check = PMN->getCheck()) {
-      OptionsToMatch.push_back(Check);
-      MatchersByHash[Check->getHash()].push_back(Check);
+    OwningPtr<Matcher> Child(Scope->takeChild(i));
+    FactorNodes(Child);
+    
+    // FIXME: Eventually don't pass ownership back to the scope node.
+    Scope->resetChild(i, Child.take());
+    
+    if (Matcher *N = Scope->getChild(i)) {
+      OptionsToMatch.push_back(N);
+      MatchersByHash[N->getHash()].push_back(N);
     }
   }
   
-  if (CurNode) {
-    OptionsToMatch.push_back(CurNode);
-    MatchersByHash[CurNode->getHash()].push_back(CurNode);
-  }
-  
   
   SmallVector<Matcher*, 32> NewOptionsToMatch;