Check in the first big step of rewriting DAGISelEmitter to

produce a table based matcher instead of gobs of C++ Code.

Though it's not done yet, the shrinkage seems promising,
the table for the X86 ISel is 75K and still has a lot of 
optimization to come (compare to the ~1.5M of .o generated
the old way, much of which will go away).

The code is currently disabled by default (the #if 0 in
DAGISelEmitter.cpp).  When enabled it generates a dead
SelectCode2 function in the DAGISel Header which will
eventually replace SelectCode.

There is still a lot of stuff left to do, which are
documented with a trail of FIXMEs.



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

7 files changed, 1265 insertions, 2 deletions

diff --git a/include/llvm/CodeGen/DAGISelHeader.h b/include/llvm/CodeGen/DAGISelHeader.h
index 4d50879a15..f9490a77ca 100644
--- a/include/llvm/CodeGen/DAGISelHeader.h
+++ b/include/llvm/CodeGen/DAGISelHeader.h
@@ -132,4 +132,268 @@ void SelectRoot(SelectionDAG &DAG) {
   CurDAG->setRoot(Dummy.getValue());
 }
 
+
+/// CheckInteger - Return true if the specified node is not a ConstantSDNode or
+/// if it doesn't have the specified value.
+static bool CheckInteger(SDValue V, int64_t Val) {
+  ConstantSDNode *C = dyn_cast<ConstantSDNode>(V);
+  return C == 0 || C->getSExtValue() != Val;
+}
+
+/// CheckAndImmediate - Check to see if the specified node is an and with an
+/// immediate returning true on failure.
+///
+/// FIXME: Inline this gunk into CheckAndMask.
+bool CheckAndImmediate(SDValue V, int64_t Val) {
+  if (V->getOpcode() == ISD::AND)
+    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(V->getOperand(1)))
+      if (CheckAndMask(V.getOperand(0), C, Val))
+        return false;
+  return true;
+}
+
+/// CheckOrImmediate - Check to see if the specified node is an or with an
+/// immediate returning true on failure.
+///
+/// FIXME: Inline this gunk into CheckOrMask.
+bool CheckOrImmediate(SDValue V, int64_t Val) {
+  if (V->getOpcode() == ISD::OR)
+    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(V->getOperand(1)))
+      if (CheckOrMask(V.getOperand(0), C, Val))
+        return false;
+  return true;
+}
+
+static int8_t GetInt1(const unsigned char *MatcherTable, unsigned &Idx) {
+  return MatcherTable[Idx++];
+}
+
+static int16_t GetInt2(const unsigned char *MatcherTable, unsigned &Idx) {
+  int16_t Val = GetInt1(MatcherTable, Idx);
+  Val |= int16_t(GetInt1(MatcherTable, Idx)) << 8;
+  return Val;
+}
+
+static int32_t GetInt4(const unsigned char *MatcherTable, unsigned &Idx) {
+  int32_t Val = GetInt2(MatcherTable, Idx);
+  Val |= int32_t(GetInt2(MatcherTable, Idx)) << 16;
+  return Val;
+}
+
+static int64_t GetInt8(const unsigned char *MatcherTable, unsigned &Idx) {
+  int64_t Val = GetInt4(MatcherTable, Idx);
+  Val |= int64_t(GetInt4(MatcherTable, Idx)) << 32;
+  return Val;
+}
+
+enum BuiltinOpcodes {
+  OPC_Emit,
+  OPC_Push,
+  OPC_Record,
+  OPC_MoveChild,
+  OPC_MoveParent,
+  OPC_CheckSame,
+  OPC_CheckPatternPredicate,
+  OPC_CheckPredicate,
+  OPC_CheckOpcode,
+  OPC_CheckType,
+  OPC_CheckInteger1, OPC_CheckInteger2, OPC_CheckInteger4, OPC_CheckInteger8,
+  OPC_CheckCondCode,
+  OPC_CheckValueType,
+  OPC_CheckComplexPat,
+  OPC_CheckAndImm1, OPC_CheckAndImm2, OPC_CheckAndImm4, OPC_CheckAndImm8,
+  OPC_CheckOrImm1, OPC_CheckOrImm2, OPC_CheckOrImm4, OPC_CheckOrImm8
+};
+
+struct MatchScope {
+  /// FailIndex - If this match fails, this is the index to continue with.
+  unsigned FailIndex;
+  
+  /// NodeStackSize - The size of the node stack when the scope was formed.
+  unsigned NodeStackSize;
+  
+  /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
+  unsigned NumRecordedNodes;
+};
+
+SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
+                         unsigned TableSize) {
+  switch (NodeToMatch->getOpcode()) {
+  default:
+    break;
+  case ISD::EntryToken:       // These nodes remain the same.
+  case ISD::BasicBlock:
+  case ISD::Register:
+  case ISD::HANDLENODE:
+  case ISD::TargetConstant:
+  case ISD::TargetConstantFP:
+  case ISD::TargetConstantPool:
+  case ISD::TargetFrameIndex:
+  case ISD::TargetExternalSymbol:
+  case ISD::TargetBlockAddress:
+  case ISD::TargetJumpTable:
+  case ISD::TargetGlobalTLSAddress:
+  case ISD::TargetGlobalAddress:
+  case ISD::TokenFactor:
+  case ISD::CopyFromReg:
+  case ISD::CopyToReg:
+    return 0;
+  case ISD::AssertSext:
+  case ISD::AssertZext:
+    ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
+    return 0;
+  case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch);
+  case ISD::EH_LABEL:  return Select_EH_LABEL(NodeToMatch);
+  case ISD::UNDEF:     return Select_UNDEF(NodeToMatch);
+  }
+  
+  assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
+  
+  SmallVector<MatchScope, 8> MatchScopes;
+  
+  // RecordedNodes - This is the set of nodes that have been recorded by the
+  // state machine.
+  SmallVector<SDValue, 8> RecordedNodes;
+  
+  // Set up the node stack with NodeToMatch as the only node on the stack.
+  SmallVector<SDValue, 8> NodeStack;
+  SDValue N = SDValue(NodeToMatch, 0);
+  NodeStack.push_back(N);
+  
+  // Interpreter starts at opcode #0.
+  unsigned MatcherIndex = 0;
+  while (1) {
+    assert(MatcherIndex < TableSize && "Invalid index");
+    switch ((BuiltinOpcodes)MatcherTable[MatcherIndex++]) {
+    case OPC_Emit: {
+      errs() << "EMIT NODE\n";
+      return 0;
+    }
+    case OPC_Push: {
+      unsigned NumToSkip = MatcherTable[MatcherIndex++];
+      MatchScope NewEntry;
+      NewEntry.FailIndex = MatcherIndex+NumToSkip;
+      NewEntry.NodeStackSize = NodeStack.size();
+      NewEntry.NumRecordedNodes = RecordedNodes.size();
+      MatchScopes.push_back(NewEntry);
+      continue;
+    }
+    case OPC_Record:
+      // Remember this node, it may end up being an operand in the pattern.
+      RecordedNodes.push_back(N);
+      continue;
+        
+    case OPC_MoveChild: {
+      unsigned Child = MatcherTable[MatcherIndex++];
+      if (Child >= N.getNumOperands())
+        break;  // Match fails if out of range child #.
+      N = N.getOperand(Child);
+      NodeStack.push_back(N);
+      continue;
+    }
+        
+    case OPC_MoveParent:
+      // Pop the current node off the NodeStack.
+      NodeStack.pop_back();
+      assert(!NodeStack.empty() && "Node stack imbalance!");
+      N = NodeStack.back();  
+      continue;
+     
+    case OPC_CheckSame: {
+      // Accept if it is exactly the same as a previously recorded node.
+      unsigned RecNo = MatcherTable[MatcherIndex++];
+      assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
+      if (N != RecordedNodes[RecNo]) break;
+      continue;
+    }
+    case OPC_CheckPatternPredicate: {
+      unsigned PredNo = MatcherTable[MatcherIndex++];
+      (void)PredNo;
+      // FIXME: CHECK IT.
+      continue;
+    }
+    case OPC_CheckPredicate: {
+      unsigned PredNo = MatcherTable[MatcherIndex++];
+      (void)PredNo;
+      // FIXME: CHECK IT.
+      continue;
+    }
+    case OPC_CheckComplexPat: {
+      unsigned PatNo = MatcherTable[MatcherIndex++];
+      (void)PatNo;
+      // FIXME: CHECK IT.
+      continue;
+    }
+        
+    case OPC_CheckOpcode:
+      if (N->getOpcode() != MatcherTable[MatcherIndex++]) break;
+      continue;
+    case OPC_CheckType:
+      if (N.getValueType() !=
+          (MVT::SimpleValueType)MatcherTable[MatcherIndex++]) break;
+      continue;
+    case OPC_CheckCondCode:
+      if (cast<CondCodeSDNode>(N)->get() !=
+          (ISD::CondCode)MatcherTable[MatcherIndex++]) break;
+      continue;
+    case OPC_CheckValueType:
+      if (cast<VTSDNode>(N)->getVT() !=
+          (MVT::SimpleValueType)MatcherTable[MatcherIndex++]) break;
+      continue;
+
+    case OPC_CheckInteger1:
+      if (CheckInteger(N, GetInt1(MatcherTable, MatcherIndex))) break;
+      continue;
+    case OPC_CheckInteger2:
+      if (CheckInteger(N, GetInt2(MatcherTable, MatcherIndex))) break;
+      continue;
+    case OPC_CheckInteger4:
+      if (CheckInteger(N, GetInt4(MatcherTable, MatcherIndex))) break;
+      continue;
+    case OPC_CheckInteger8:
+      if (CheckInteger(N, GetInt8(MatcherTable, MatcherIndex))) break;
+      continue;
+        
+    case OPC_CheckAndImm1:
+      if (CheckAndImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
+      continue;
+    case OPC_CheckAndImm2:
+      if (CheckAndImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
+      continue;
+    case OPC_CheckAndImm4:
+      if (CheckAndImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
+      continue;
+    case OPC_CheckAndImm8:
+      if (CheckAndImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
+      continue;
+
+    case OPC_CheckOrImm1:
+      if (CheckOrImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
+      continue;
+    case OPC_CheckOrImm2:
+      if (CheckOrImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
+      continue;
+    case OPC_CheckOrImm4:
+      if (CheckOrImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
+      continue;
+    case OPC_CheckOrImm8:
+      if (CheckOrImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
+      continue;
+    }
+    
+    // If the code reached this point, then the match failed pop out to the next
+    // match scope.
+    if (MatchScopes.empty()) {
+      CannotYetSelect(NodeToMatch);
+      return 0;
+    }
+    
+    RecordedNodes.resize(MatchScopes.back().NumRecordedNodes);
+    NodeStack.resize(MatchScopes.back().NodeStackSize);
+    MatcherIndex = MatchScopes.back().FailIndex;
+    MatchScopes.pop_back();
+  }
+}
+    
+
 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */
diff --git a/utils/TableGen/CMakeLists.txt b/utils/TableGen/CMakeLists.txt
index f344b28842..a2678a29f7 100644
--- a/utils/TableGen/CMakeLists.txt
+++ b/utils/TableGen/CMakeLists.txt
@@ -9,6 +9,9 @@ add_executable(tblgen
   CodeGenInstruction.cpp
   CodeGenTarget.cpp
   DAGISelEmitter.cpp
+  DAGISelMatcherEmitter.cpp
+  DAGISelMatcherGen.cpp
+  DAGISelMatcher.cpp
   DisassemblerEmitter.cpp
   EDEmitter.cpp
   FastISelEmitter.cpp
diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp
index e8aa164302..0eb06bb541 100644
--- a/utils/TableGen/DAGISelEmitter.cpp
+++ b/utils/TableGen/DAGISelEmitter.cpp
@@ -12,6 +12,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "DAGISelEmitter.h"
+#include "DAGISelMatcher.h"
 #include "Record.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/CommandLine.h"
@@ -1609,7 +1610,7 @@ static std::string getLegalCName(std::string OpName) {
 
 void DAGISelEmitter::EmitInstructionSelector(raw_ostream &OS) {
   const CodeGenTarget &Target = CGP.getTargetInfo();
-  
+
   // Get the namespace to insert instructions into.
   std::string InstNS = Target.getInstNamespace();
   if (!InstNS.empty()) InstNS += "::";
@@ -1621,7 +1622,6 @@ void DAGISelEmitter::EmitInstructionSelector(raw_ostream &OS) {
   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
        E = CGP.ptm_end(); I != E; ++I) {
     const PatternToMatch &Pattern = *I;
-    
     TreePatternNode *Node = Pattern.getSrcPattern();
     if (!Node->isLeaf()) {
       PatternsByOpcode[getOpcodeName(Node->getOperator(), CGP)].
@@ -2011,4 +2011,26 @@ void DAGISelEmitter::run(raw_ostream &OS) {
   // definitions.  Emit the resultant instruction selector.
   EmitInstructionSelector(OS);  
   
+#if 0
+  MatcherNode *Matcher = 0;
+  // Walk the patterns backwards, building a matcher for each and adding it to
+  // the matcher for the whole target.
+  for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
+       E = CGP.ptm_end(); I != E;) {
+    const PatternToMatch &Pattern = *--E;
+    MatcherNode *N = ConvertPatternToMatcher(Pattern, CGP);
+    
+    if (Matcher == 0)
+      Matcher = N;
+    else
+      Matcher = new PushMatcherNode(N, Matcher);
+  }
+  
+  
+  EmitMatcherTable(Matcher, OS);
+  
+  
+  //Matcher->dump();
+  delete Matcher;
+#endif
 }
diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp
new file mode 100644
index 0000000000..1363aa3e81
--- /dev/null
+++ b/utils/TableGen/DAGISelMatcher.cpp
@@ -0,0 +1,108 @@
+//===- DAGISelMatcher.cpp - Representation of DAG pattern matcher ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "DAGISelMatcher.h"
+#include "CodeGenDAGPatterns.h"
+#include "CodeGenTarget.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+void MatcherNode::dump() const {
+  print(errs());
+}
+
+void EmitNodeMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "EmitNode: Src = " << *Pattern.getSrcPattern() << "\n";
+  OS.indent(indent) << "EmitNode: Dst = " << *Pattern.getDstPattern() << "\n";
+}
+
+void MatcherNodeWithChild::printChild(raw_ostream &OS, unsigned indent) const {
+  if (Child)
+    return Child->print(OS, indent);
+  OS.indent(indent) << "<null child>\n";
+}
+
+
+void PushMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "Push\n";
+  printChild(OS, indent+2);
+  Failure->print(OS, indent);
+}
+
+void RecordMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "Record\n";
+  printChild(OS, indent);
+}
+
+void MoveChildMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "MoveChild " << ChildNo << '\n';
+  printChild(OS, indent);
+}
+
+void MoveParentMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "MoveParent\n";
+  printChild(OS, indent);
+}
+
+void CheckSameMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckSame " << MatchNumber << '\n';
+  printChild(OS, indent);
+}
+
+void CheckPatternPredicateMatcherNode::
+print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n';
+  printChild(OS, indent);
+}
+
+void CheckPredicateMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckPredicate " << PredName << '\n';
+  printChild(OS, indent);
+}
+
+void CheckOpcodeMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckOpcode " << OpcodeName << '\n';
+  printChild(OS, indent);
+}
+
+void CheckTypeMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckType " << getEnumName(Type) << '\n';
+  printChild(OS, indent);
+}
+
+void CheckIntegerMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckInteger " << Value << '\n';
+  printChild(OS, indent);
+}
+
+void CheckCondCodeMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n';
+  printChild(OS, indent);
+}
+
+void CheckValueTypeMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n';
+  printChild(OS, indent);
+}
+
+void CheckComplexPatMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n';
+  printChild(OS, indent);
+}
+
+void CheckAndImmMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckAndImm " << Value << '\n';
+  printChild(OS, indent);
+}
+
+void CheckOrImmMatcherNode::print(raw_ostream &OS, unsigned indent) const {
+  OS.indent(indent) << "CheckOrImm " << Value << '\n';
+  printChild(OS, indent);
+}
+
diff --git a/utils/TableGen/DAGISelMatcher.h b/utils/TableGen/DAGISelMatcher.h
new file mode 100644
index 0000000000..72bdb7bf27
--- /dev/null
+++ b/utils/TableGen/DAGISelMatcher.h
@@ -0,0 +1,362 @@
+//===- DAGISelMatcher.h - Representation of DAG pattern matcher -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef TBLGEN_DAGISELMATCHER_H
+#define TBLGEN_DAGISELMATCHER_H
+
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/CodeGen/ValueTypes.h"
+
+namespace llvm {
+  class CodeGenDAGPatterns;
+  class MatcherNode;
+  class PatternToMatch;
+  class raw_ostream;
+  class ComplexPattern;
+
+MatcherNode *ConvertPatternToMatcher(const PatternToMatch &Pattern,
+                                     const CodeGenDAGPatterns &CGP);
+
+void EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &OS);
+
+  
+/// MatcherNode - Base class for all the the DAG ISel Matcher representation
+/// nodes.
+class MatcherNode {
+public:
+  enum KindTy {
+    EmitNode,
+    Push,           // [Push, Dest0, Dest1, Dest2, Dest3]
+    Record,         // [Record]
+    MoveChild,      // [MoveChild, Child#]
+    MoveParent,     // [MoveParent]
+    
+    CheckSame,      // [CheckSame, N]         Fail if not same as prev match.
+    CheckPatternPredicate,
+    CheckPredicate, // [CheckPredicate, P]    Fail if predicate fails.
+    CheckOpcode,    // [CheckOpcode, Opcode]  Fail if not opcode.
+    CheckType,      // [CheckType, MVT]       Fail if not correct type.
+    CheckInteger,   // [CheckInteger, int0,int1,int2,...int7] Fail if wrong val.
+    CheckCondCode,  // [CheckCondCode, CondCode] Fail if not condcode.
+    CheckValueType,
+    CheckComplexPat,
+    CheckAndImm,
+    CheckOrImm
+  };
+  const KindTy Kind;
+  
+protected:
+  MatcherNode(KindTy K) : Kind(K) {}
+public:
+  virtual ~MatcherNode() {}
+  
+  KindTy getKind() const { return Kind; }
+  
+  
+  static inline bool classof(const MatcherNode *) { return true; }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const = 0;
+  void dump() const;
+};
+  
+/// EmitNodeMatcherNode - This signals a successful match and generates a node.
+class EmitNodeMatcherNode : public MatcherNode {
+  const PatternToMatch &Pattern;
+public:
+  EmitNodeMatcherNode(const PatternToMatch &pattern)
+    : MatcherNode(EmitNode), Pattern(pattern) {}
+
+  const PatternToMatch &getPattern() const { return Pattern; }
+
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == EmitNode;
+  }
+
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// MatcherNodeWithChild - Every node accept the final accept state has a child
+/// that is executed after the node runs.  This class captures this commonality.
+class MatcherNodeWithChild : public MatcherNode {
+  OwningPtr<MatcherNode> Child;
+public:
+  MatcherNodeWithChild(KindTy K) : MatcherNode(K) {}
+  
+  MatcherNode *getChild() { return Child.get(); }
+  const MatcherNode *getChild() const { return Child.get(); }
+  void setChild(MatcherNode *C) { Child.reset(C); }
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() != EmitNode;
+  }
+  
+protected:
+  void printChild(raw_ostream &OS, unsigned indent) const;
+};
+
+/// PushMatcherNode - This pushes a failure scope on the stack and evaluates
+/// 'child'.  If 'child' fails to match, it pops its scope and attempts to
+/// match 'Failure'.
+class PushMatcherNode : public MatcherNodeWithChild {
+  OwningPtr<MatcherNode> Failure;
+public:
+  PushMatcherNode(MatcherNode *child = 0, MatcherNode *failure = 0)
+    : MatcherNodeWithChild(Push), Failure(failure) {
+    setChild(child);
+  }
+  
+  MatcherNode *getFailure() { return Failure.get(); }
+  const MatcherNode *getFailure() const { return Failure.get(); }
+  void setFailure(MatcherNode *N) { Failure.reset(N); }
+
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == Push;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// RecordMatcherNode - Save the current node in the operand list.
+class RecordMatcherNode : public MatcherNodeWithChild {
+public:
+  RecordMatcherNode() : MatcherNodeWithChild(Record) {}
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == Record;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+/// MoveChildMatcherNode - This tells the interpreter to move into the
+/// specified child node.
+class MoveChildMatcherNode : public MatcherNodeWithChild {
+  unsigned ChildNo;
+public:
+  MoveChildMatcherNode(unsigned childNo)
+  : MatcherNodeWithChild(MoveChild), ChildNo(childNo) {}
+  
+  unsigned getChildNo() const { return ChildNo; }
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == MoveChild;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+/// MoveParentMatcherNode - This tells the interpreter to move to the parent
+/// of the current node.
+class MoveParentMatcherNode : public MatcherNodeWithChild {
+public:
+  MoveParentMatcherNode()
+  : MatcherNodeWithChild(MoveParent) {}
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == MoveParent;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckSameMatcherNode - This checks to see if this node is exactly the same
+/// node as the specified match that was recorded with 'Record'.  This is used
+/// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'.
+class CheckSameMatcherNode : public MatcherNodeWithChild {
+  unsigned MatchNumber;
+public:
+  CheckSameMatcherNode(unsigned matchnumber)
+  : MatcherNodeWithChild(CheckSame), MatchNumber(matchnumber) {}
+  
+  unsigned getMatchNumber() const { return MatchNumber; }
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckSame;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+/// CheckPatternPredicateMatcherNode - This checks the target-specific predicate
+/// to see if the entire pattern is capable of matching.  This predicate does
+/// not take a node as input.  This is used for subtarget feature checks etc.
+class CheckPatternPredicateMatcherNode : public MatcherNodeWithChild {
+  std::string Predicate;
+public:
+  CheckPatternPredicateMatcherNode(StringRef predicate)
+  : MatcherNodeWithChild(CheckPatternPredicate), Predicate(predicate) {}
+  
+  StringRef getPredicate() const { return Predicate; }
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckPatternPredicate;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+/// CheckPredicateMatcherNode - This checks the target-specific predicate to
+/// see if the node is acceptable.
+class CheckPredicateMatcherNode : public MatcherNodeWithChild {
+  StringRef PredName;
+public:
+  CheckPredicateMatcherNode(StringRef predname)
+    : MatcherNodeWithChild(CheckPredicate), PredName(predname) {}
+  
+  StringRef getPredicateName() const { return PredName; }
+
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckPredicate;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+  
+/// CheckOpcodeMatcherNode - This checks to see if the current node has the
+/// specified opcode, if not it fails to match.
+class CheckOpcodeMatcherNode : public MatcherNodeWithChild {
+  StringRef OpcodeName;
+public:
+  CheckOpcodeMatcherNode(StringRef opcodename)
+    : MatcherNodeWithChild(CheckOpcode), OpcodeName(opcodename) {}
+  
+  StringRef getOpcodeName() const { return OpcodeName; }
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckOpcode;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+/// CheckTypeMatcherNode - This checks to see if the current node has the
+/// specified type, if not it fails to match.
+class CheckTypeMatcherNode : public MatcherNodeWithChild {
+  MVT::SimpleValueType Type;
+public:
+  CheckTypeMatcherNode(MVT::SimpleValueType type)
+    : MatcherNodeWithChild(CheckType), Type(type) {}
+  
+  MVT::SimpleValueType getType() const { return Type; }
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckType;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckIntegerMatcherNode - This checks to see if the current node is a
+/// ConstantSDNode with the specified integer value, if not it fails to match.
+class CheckIntegerMatcherNode : public MatcherNodeWithChild {
+  int64_t Value;
+public:
+  CheckIntegerMatcherNode(int64_t value)
+    : MatcherNodeWithChild(CheckInteger), Value(value) {}
+  
+  int64_t getValue() const { return Value; }
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckInteger;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+/// CheckCondCodeMatcherNode - This checks to see if the current node is a
+/// CondCodeSDNode with the specified condition, if not it fails to match.
+class CheckCondCodeMatcherNode : public MatcherNodeWithChild {
+  StringRef CondCodeName;
+public:
+  CheckCondCodeMatcherNode(StringRef condcodename)
+  : MatcherNodeWithChild(CheckCondCode), CondCodeName(condcodename) {}
+  
+  StringRef getCondCodeName() const { return CondCodeName; }
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckCondCode;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+/// CheckValueTypeMatcherNode - This checks to see if the current node is a
+/// VTSDNode with the specified type, if not it fails to match.
+class CheckValueTypeMatcherNode : public MatcherNodeWithChild {
+  StringRef TypeName;
+public:
+  CheckValueTypeMatcherNode(StringRef type_name)
+  : MatcherNodeWithChild(CheckValueType), TypeName(type_name) {}
+  
+  StringRef getTypeName() const { return TypeName; }
+
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckValueType;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+  
+  
+/// CheckComplexPatMatcherNode - This node runs the specified ComplexPattern on
+/// the current node.
+class CheckComplexPatMatcherNode : public MatcherNodeWithChild {
+  const ComplexPattern &Pattern;
+public:
+  CheckComplexPatMatcherNode(const ComplexPattern &pattern)
+  : MatcherNodeWithChild(CheckComplexPat), Pattern(pattern) {}
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckComplexPat;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+/// CheckAndImmMatcherNode - This checks to see if the current node is an 'and'
+/// with something equivalent to the specified immediate.
+class CheckAndImmMatcherNode : public MatcherNodeWithChild {
+  int64_t Value;
+public:
+  CheckAndImmMatcherNode(int64_t value)
+  : MatcherNodeWithChild(CheckAndImm), Value(value) {}
+  
+  int64_t getValue() const { return Value; }
+  
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckAndImm;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+
+/// CheckOrImmMatcherNode - This checks to see if the current node is an 'and'
+/// with something equivalent to the specified immediate.
+class CheckOrImmMatcherNode : public MatcherNodeWithChild {
+  int64_t Value;
+public:
+  CheckOrImmMatcherNode(int64_t value)
+    : MatcherNodeWithChild(CheckOrImm), Value(value) {}
+  
+  int64_t getValue() const { return Value; }
+
+  static inline bool classof(const MatcherNode *N) {
+    return N->getKind() == CheckOrImm;
+  }
+  
+  virtual void print(raw_ostream &OS, unsigned indent = 0) const;
+};
+  
+  
+} // end namespace llvm
+
+#endif
diff --git a/utils/TableGen/DAGISelMatcherEmitter.cpp b/utils/TableGen/DAGISelMatcherEmitter.cpp
new file mode 100644
index 0000000000..1a41713c22
--- /dev/null
+++ b/utils/TableGen/DAGISelMatcherEmitter.cpp
@@ -0,0 +1,217 @@
+//===- DAGISelMatcherEmitter.cpp - Matcher Emitter ------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains code to generate C++ code a matcher.
+//
+//===----------------------------------------------------------------------===//
+
+#include "DAGISelMatcher.h"
+#include "CodeGenDAGPatterns.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/FormattedStream.h"
+using namespace llvm;
+
+namespace {
+enum {
+  CommentIndent = 25
+};
+}
+
+static unsigned EmitMatcherAndChildren(const MatcherNode *N,
+                                       formatted_raw_ostream &FOS,
+                                       unsigned Indent);
+
+/// ClassifyInt - Classify an integer by size, return '1','2','4','8' if this
+/// fits in 1, 2, 4, or 8 sign extended bytes.
+static char ClassifyInt(int64_t Val) {
+  if (Val == int8_t(Val))  return '1';
+  if (Val == int16_t(Val)) return '2';
+  if (Val == int32_t(Val)) return '4';
+  return '8';
+}
+
+/// EmitInt - Emit the specified integer, returning the number of bytes emitted.
+static unsigned EmitInt(int64_t Val, formatted_raw_ostream &OS) {
+  unsigned BytesEmitted = 1;
+  OS << (int)(unsigned char)Val << ", ";
+  if (Val == int8_t(Val)) {
+    OS << "\n";
+    return BytesEmitted;
+  }
+  
+  OS << (int)(unsigned char)(Val >> 8) << ", ";
+  ++BytesEmitted;
+  
+  if (Val != int16_t(Val)) {
+    OS << (int)(unsigned char)(Val >> 16) << ','
+       << (int)(unsigned char)(Val >> 24) << ',';
+    BytesEmitted += 2;
+    
+    if (Val != int32_t(Val)) {
+      OS << (int)(unsigned char)(Val >> 32) << ','
+         << (int)(unsigned char)(Val >> 40) << ','
+         << (int)(unsigned char)(Val >> 48) << ','
+         << (int)(unsigned char)(Val >> 56) << ',';
+      BytesEmitted += 4;
+    }   
+  }
+  
+  OS.PadToColumn(CommentIndent) << "// " << Val << '\n';
+  return BytesEmitted;
+}
+
+/// EmitMatcherOpcodes - Emit bytes for the specified matcher and return
+/// the number of bytes emitted.
+static unsigned EmitMatcher(const MatcherNode *N, formatted_raw_ostream &OS,
+                            unsigned Indent) {
+  OS.PadToColumn(Indent*2);
+  
+  switch (N->getKind()) {
+  case MatcherNode::Push: assert(0 && "Should be handled by caller");
+  case MatcherNode::EmitNode:
+    OS << "OPC_Emit, /*XXX*/";
+    OS.PadToColumn(CommentIndent) << "// Src: "
+      << *cast<EmitNodeMatcherNode>(N)->getPattern().getSrcPattern() << '\n';
+    OS.PadToColumn(CommentIndent) << "// Dst: "
+      << *cast<EmitNodeMatcherNode>(N)->getPattern().getDstPattern() << '\n';
+    return 1;
+  case MatcherNode::Record:
+    OS << "OPC_Record,\n";
+    return 1;
+  case MatcherNode::MoveChild:
+    OS << "OPC_MoveChild, "
+       << cast<MoveChildMatcherNode>(N)->getChildNo() << ",\n";
+    return 2;
+      
+  case MatcherNode::MoveParent:
+    OS << "OPC_MoveParent,\n";
+    return 1;
+      
+  case MatcherNode::CheckSame:
+    OS << "OPC_CheckSame, "
+       << cast<CheckSameMatcherNode>(N)->getMatchNumber() << ",\n";
+    return 2;
+
+  case MatcherNode::CheckPatternPredicate:
+    OS << "OPC_CheckPatternPredicate, /*XXX*/0,";
+    OS.PadToColumn(CommentIndent) << "// "
+      << cast<CheckPatternPredicateMatcherNode>(N)->getPredicate() << '\n';
+    return 2;
+    
+  case MatcherNode::CheckPredicate:
+    OS << "OPC_CheckPredicate, /*XXX*/0,";
+    OS.PadToColumn(CommentIndent) << "// "
+      << cast<CheckPredicateMatcherNode>(N)->getPredicateName() << '\n';
+    return 2;
+      
+  case MatcherNode::CheckOpcode:
+    OS << "OPC_CheckOpcode, "
+       << cast<CheckOpcodeMatcherNode>(N)->getOpcodeName() << ",\n";
+    return 2;
+      
+  case MatcherNode::CheckType:
+    OS << "OPC_CheckType, "
+       << getEnumName(cast<CheckTypeMatcherNode>(N)->getType()) << ",\n";
+    return 2;
+
+  case MatcherNode::CheckInteger: {
+    int64_t Val = cast<CheckIntegerMatcherNode>(N)->getValue();
+    OS << "OPC_CheckInteger" << ClassifyInt(Val) << ", ";
+    return EmitInt(Val, OS)+1;
+  }   
+  case MatcherNode::CheckCondCode:
+    OS << "OPC_CheckCondCode, ISD::"
+       << cast<CheckCondCodeMatcherNode>(N)->getCondCodeName() << ",\n";
+    return 2;
+      
+  case MatcherNode::CheckValueType:
+    OS << "OPC_CheckValueType, MVT::"
+       << cast<CheckValueTypeMatcherNod