introduce a new SwitchTypeMatcher node (which is analogous to

SwitchOpcodeMatcher) and have DAGISelMatcherOpt form it.  This
speeds up selection, particularly for X86 which has lots of 
variants of instructions with only type differences.


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

4 files changed, 111 insertions, 21 deletions

diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp
index a2603e9683..c4f1cbfcf0 100644
--- a/utils/TableGen/DAGISelMatcher.cpp
+++ b/utils/TableGen/DAGISelMatcher.cpp
@@ -102,6 +102,15 @@ void CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
   OS.indent(indent) << "CheckType " << getEnumName(Type) << '\n';
 }
 
+void SwitchTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "SwitchType: {\n";
+  for (unsigned i = 0, e = Cases.size(); i != e; ++i) {
+    OS.indent(indent) << "case " << getEnumName(Cases[i].first) << ":\n";
+    Cases[i].second->print(OS, indent+2);
+  }
+  OS.indent(indent) << "}\n";
+}
+
 void CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const {
   OS.indent(indent) << "CheckChildType " << ChildNo << " "
     << getEnumName(Type) << '\n';
diff --git a/utils/TableGen/DAGISelMatcher.h b/utils/TableGen/DAGISelMatcher.h
index 3eb6755674..c2e81711e0 100644
--- a/utils/TableGen/DAGISelMatcher.h
+++ b/utils/TableGen/DAGISelMatcher.h
@@ -56,6 +56,7 @@ public:
     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.
     CheckCondCode,        // Fail if not condcode.
@@ -472,6 +473,34 @@ private:
   virtual bool isContradictoryImpl(const Matcher *M) const;
 };
   
+/// SwitchTypeMatcher - Switch based on the current node's type, dispatching
+/// to one matcher per case.  If the type doesn't match any of the cases,
+/// then the match fails.  This is semantically equivalent to a Scope node where
+/// every child does a CheckType, but is much faster.
+class SwitchTypeMatcher : public Matcher {
+  SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases;
+public:
+  SwitchTypeMatcher(const std::pair<MVT::SimpleValueType, Matcher*> *cases,
+                    unsigned numcases)
+  : Matcher(SwitchType), Cases(cases, cases+numcases) {}
+  
+  static inline bool classof(const Matcher *N) {
+    return N->getKind() == SwitchType;
+  }
+  
+  unsigned getNumCases() const { return Cases.size(); }
+  
+  MVT::SimpleValueType getCaseType(unsigned i) const { return Cases[i].first; }
+  Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; }
+  const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; }
+  
+private:
+  virtual void printImpl(raw_ostream &OS, unsigned indent) const;
+  virtual bool isEqualImpl(const Matcher *M) const { return false; }
+  virtual unsigned getHashImpl() const { return 4123; }
+};
+  
+  
 /// CheckChildTypeMatcher - This checks to see if a child node has the
 /// specified type, if not it fails to match.
 class CheckChildTypeMatcher : public Matcher {
diff --git a/utils/TableGen/DAGISelMatcherEmitter.cpp b/utils/TableGen/DAGISelMatcherEmitter.cpp
index 2e3e58d173..1f0405038c 100644
--- a/utils/TableGen/DAGISelMatcherEmitter.cpp
+++ b/utils/TableGen/DAGISelMatcherEmitter.cpp
@@ -261,17 +261,32 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
        << cast<CheckOpcodeMatcher>(N)->getOpcode().getEnumName() << ",\n";
     return 2;
       
-  case Matcher::SwitchOpcode: {
+  case Matcher::SwitchOpcode:
+  case Matcher::SwitchType: {
     unsigned StartIdx = CurrentIdx;
-    const SwitchOpcodeMatcher *SOM = cast<SwitchOpcodeMatcher>(N);
-    OS << "OPC_SwitchOpcode ";
+    
+    unsigned NumCases;
+    if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) {
+      OS << "OPC_SwitchOpcode ";
+      NumCases = SOM->getNumCases();
+    } else {
+      OS << "OPC_SwitchType ";
+      NumCases = cast<SwitchTypeMatcher>(N)->getNumCases();
+    }
+
     if (!OmitComments)
-      OS << "/*" << SOM->getNumCases() << " cases */";
+      OS << "/*" << NumCases << " cases */";
     OS << ", ";
     ++CurrentIdx;
     
     // For each case we emit the size, then the opcode, then the matcher.
-    for (unsigned i = 0, e = SOM->getNumCases(); i != e; ++i) {
+    for (unsigned i = 0, e = NumCases; i != e; ++i) {
+      const Matcher *Child;
+      if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N))
+        Child = SOM->getCaseMatcher(i);
+      else
+        Child = cast<SwitchTypeMatcher>(N)->getCaseMatcher(i);
+      
       // 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
@@ -286,8 +301,7 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
         TmpBuf.clear();
         raw_svector_ostream OS(TmpBuf);
         formatted_raw_ostream FOS(OS);
-        ChildSize = EmitMatcherList(SOM->getCaseMatcher(i),
-                                    Indent+1, CurrentIdx+VBRSize+1, FOS);
+        ChildSize = EmitMatcherList(Child, Indent+1, CurrentIdx+VBRSize+1, FOS);
       } while (GetVBRSize(ChildSize) != VBRSize);
       
       assert(ChildSize != 0 && "Should not have a zero-sized child!");
@@ -295,13 +309,20 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
       if (i != 0) {
         OS.PadToColumn(Indent*2);
         if (!OmitComments)
-         OS << "/*SwitchOpcode*/ ";
+        OS << (isa<SwitchOpcodeMatcher>(N) ?
+                   "/*SwitchOpcode*/ " : "/*SwitchType*/ ");
       }
       
       // Emit the VBR.
       CurrentIdx += EmitVBRValue(ChildSize, OS);
       
-      OS << " " << SOM->getCaseOpcode(i).getEnumName() << ",";
+      OS << ' ';
+      if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N))
+        OS << SOM->getCaseOpcode(i).getEnumName();
+      else
+        OS << getEnumName(cast<SwitchTypeMatcher>(N)->getCaseType(i));
+      OS << ',';
+      
       if (!OmitComments)
         OS << "// ->" << CurrentIdx+ChildSize+1;
       OS << '\n';
@@ -313,7 +334,9 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
     // Emit the final zero to terminate the switch.
     OS.PadToColumn(Indent*2) << "0, ";
     if (!OmitComments)
-      OS << "// EndSwitchOpcode";
+      OS << (isa<SwitchOpcodeMatcher>(N) ?
+             "// EndSwitchOpcode" : "// EndSwitchType");
+
     OS << '\n';
     ++CurrentIdx;
     return CurrentIdx-StartIdx;
@@ -323,6 +346,7 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
     OS << "OPC_CheckType, "
        << getEnumName(cast<CheckTypeMatcher>(N)->getType()) << ",\n";
     return 2;
+      
   case Matcher::CheckChildType:
     OS << "OPC_CheckChild"
        << cast<CheckChildTypeMatcher>(N)->getChildNo() << "Type, "
@@ -673,6 +697,7 @@ void MatcherTableEmitter::EmitHistogram(formatted_raw_ostream &OS) {
     case Matcher::CheckOpcode: OS << "OPC_CheckOpcode"; break;
     case Matcher::SwitchOpcode: OS << "OPC_SwitchOpcode"; break;
     case Matcher::CheckType: OS << "OPC_CheckType"; break;
+    case Matcher::SwitchType: OS << "OPC_SwitchType"; break;
     case Matcher::CheckChildType: OS << "OPC_CheckChildType"; break;
     case Matcher::CheckInteger: OS << "OPC_CheckInteger"; break;
     case Matcher::CheckCondCode: OS << "OPC_CheckCondCode"; break;
diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp
index a625fa85d4..dc077a9909 100644
--- a/utils/TableGen/DAGISelMatcherOpt.cpp
+++ b/utils/TableGen/DAGISelMatcherOpt.cpp
@@ -14,7 +14,7 @@
 #define DEBUG_TYPE "isel-opt"
 #include "DAGISelMatcher.h"
 #include "CodeGenDAGPatterns.h"
-#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
@@ -361,27 +361,39 @@ static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
   
   // Check to see if all of the leading entries are now opcode checks.  If so,
   // we can convert this Scope to be a OpcodeSwitch instead.
-  bool AllOpcodeChecks = true;
+  bool AllOpcodeChecks = true, AllTypeChecks = true;
   for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
-    if (isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) continue;
-   
+    if (!isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) {
 #if 0
-    if (i > 3) {
-      errs() << "FAILING OPC #" << i << "\n";
-      NewOptionsToMatch[i]->dump();
+      if (i > 3 && AllOpcodeChecks) {
+        errs() << "FAILING OPC #" << i << "\n";
+        NewOptionsToMatch[i]->dump();
+      }
+#endif
+      AllOpcodeChecks = false;
     }
+
+    if (!isa<CheckTypeMatcher>(NewOptionsToMatch[i]) ||
+        // iPTR checks could alias any other case without us knowing, don't
+        // bother with them.
+        cast<CheckTypeMatcher>(NewOptionsToMatch[i])->getType() == MVT::iPTR) {
+#if 0
+      if (i > 3 && AllTypeChecks) {
+        errs() << "FAILING TYPE #" << i << "\n";
+        NewOptionsToMatch[i]->dump();
+      }
 #endif
-    
-    AllOpcodeChecks = false;
-    break;
+      AllTypeChecks = false;
+    }
   }
+  // TODO: Can also do CheckChildNType.
   
   // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot.
   if (AllOpcodeChecks) {
     StringSet<> Opcodes;
     SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases;
     for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
-      CheckOpcodeMatcher *COM =cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]);
+      CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]);
       assert(Opcodes.insert(COM->getOpcode().getEnumName()) &&
              "Duplicate opcodes not factored?");
       Cases.push_back(std::make_pair(&COM->getOpcode(), COM->getNext()));
@@ -391,6 +403,21 @@ static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
     return;
   }
   
+  // If all the options are CheckType's, we can form the SwitchType, woot.
+  if (AllTypeChecks) {
+    DenseSet<unsigned> Types;
+    SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases;
+    for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
+      CheckTypeMatcher *CTM = cast<CheckTypeMatcher>(NewOptionsToMatch[i]);
+      assert(Types.insert(CTM->getType()).second &&
+             "Duplicate types not factored?");
+      Cases.push_back(std::make_pair(CTM->getType(), CTM->getNext()));
+    }
+    
+    MatcherPtr.reset(new SwitchTypeMatcher(&Cases[0], Cases.size()));
+    return;
+  }
+  
 
   // Reassemble the Scope node with the adjusted children.
   Scope->setNumChildren(NewOptionsToMatch.size());