Update LLVM to r99115.

1 files changed, 423 insertions, 260 deletions

diff --git a/utils/TableGen/CodeGenDAGPatterns.cpp b/utils/TableGen/CodeGenDAGPatterns.cpp
index 6e894a4..4cc9b79 100644
--- a/utils/TableGen/CodeGenDAGPatterns.cpp
+++ b/utils/TableGen/CodeGenDAGPatterns.cpp
@@ -25,19 +25,18 @@ using namespace llvm;
 //  EEVT::TypeSet Implementation
 //===----------------------------------------------------------------------===//
 
-// FIXME: Remove EEVT::isUnknown!
-
 static inline bool isInteger(MVT::SimpleValueType VT) {
   return EVT(VT).isInteger();
 }
-
 static inline bool isFloatingPoint(MVT::SimpleValueType VT) {
   return EVT(VT).isFloatingPoint();
 }
-
 static inline bool isVector(MVT::SimpleValueType VT) {
   return EVT(VT).isVector();
 }
+static inline bool isScalar(MVT::SimpleValueType VT) {
+  return !EVT(VT).isVector();
+}
 
 EEVT::TypeSet::TypeSet(MVT::SimpleValueType VT, TreePattern &TP) {
   if (VT == MVT::iAny)
@@ -67,6 +66,32 @@ EEVT::TypeSet::TypeSet(const std::vector<MVT::SimpleValueType> &VTList) {
   TypeVec.erase(std::unique(TypeVec.begin(), TypeVec.end()), TypeVec.end());
 }
 
+/// FillWithPossibleTypes - Set to all legal types and return true, only valid
+/// on completely unknown type sets.
+bool EEVT::TypeSet::FillWithPossibleTypes(TreePattern &TP,
+                                          bool (*Pred)(MVT::SimpleValueType),
+                                          const char *PredicateName) {
+  assert(isCompletelyUnknown());
+  const std::vector<MVT::SimpleValueType> &LegalTypes = 
+    TP.getDAGPatterns().getTargetInfo().getLegalValueTypes();
+  
+  for (unsigned i = 0, e = LegalTypes.size(); i != e; ++i)
+    if (Pred == 0 || Pred(LegalTypes[i]))
+      TypeVec.push_back(LegalTypes[i]);
+
+  // If we have nothing that matches the predicate, bail out.
+  if (TypeVec.empty())
+    TP.error("Type inference contradiction found, no " +
+             std::string(PredicateName) + " types found");  
+  // No need to sort with one element.
+  if (TypeVec.size() == 1) return true;
+
+  // Remove duplicates.
+  array_pod_sort(TypeVec.begin(), TypeVec.end());
+  TypeVec.erase(std::unique(TypeVec.begin(), TypeVec.end()), TypeVec.end());
+  
+  return true;
+}
 
 /// hasIntegerTypes - Return true if this TypeSet contains iAny or an
 /// integer value type.
@@ -97,7 +122,7 @@ bool EEVT::TypeSet::hasVectorTypes() const {
 
 
 std::string EEVT::TypeSet::getName() const {
-  if (TypeVec.empty()) return "isUnknown";
+  if (TypeVec.empty()) return "<empty>";
   
   std::string Result;
     
@@ -200,94 +225,84 @@ bool EEVT::TypeSet::MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP){
 
 /// EnforceInteger - Remove all non-integer types from this set.
 bool EEVT::TypeSet::EnforceInteger(TreePattern &TP) {
-  TypeSet InputSet(*this);
-  bool MadeChange = false;
-  
   // If we know nothing, then get the full set.
-  if (TypeVec.empty()) {
-    *this = TP.getDAGPatterns().getTargetInfo().getLegalValueTypes();
-    MadeChange = true;
-  }
-  
+  if (TypeVec.empty())
+    return FillWithPossibleTypes(TP, isInteger, "integer");
   if (!hasFloatingPointTypes())
-    return MadeChange;
+    return false;
+
+  TypeSet InputSet(*this);
   
   // Filter out all the fp types.
   for (unsigned i = 0; i != TypeVec.size(); ++i)
-    if (isFloatingPoint(TypeVec[i]))
+    if (!isInteger(TypeVec[i]))
       TypeVec.erase(TypeVec.begin()+i--);
   
   if (TypeVec.empty())
     TP.error("Type inference contradiction found, '" +
              InputSet.getName() + "' needs to be integer");
-  return MadeChange;
+  return true;
 }
 
 /// EnforceFloatingPoint - Remove all integer types from this set.
 bool EEVT::TypeSet::EnforceFloatingPoint(TreePattern &TP) {
-  TypeSet InputSet(*this);
-  bool MadeChange = false;
-  
   // If we know nothing, then get the full set.
-  if (TypeVec.empty()) {
-    *this = TP.getDAGPatterns().getTargetInfo().getLegalValueTypes();
-    MadeChange = true;
-  }
-  
+  if (TypeVec.empty())
+    return FillWithPossibleTypes(TP, isFloatingPoint, "floating point");
+
   if (!hasIntegerTypes())
-    return MadeChange;
+    return false;
+
+  TypeSet InputSet(*this);
   
   // Filter out all the fp types.
   for (unsigned i = 0; i != TypeVec.size(); ++i)
-    if (isInteger(TypeVec[i]))
+    if (!isFloatingPoint(TypeVec[i]))
       TypeVec.erase(TypeVec.begin()+i--);
   
   if (TypeVec.empty())
     TP.error("Type inference contradiction found, '" +
              InputSet.getName() + "' needs to be floating point");
-  return MadeChange;
+  return true;
 }
 
 /// EnforceScalar - Remove all vector types from this.
 bool EEVT::TypeSet::EnforceScalar(TreePattern &TP) {
-  TypeSet InputSet(*this);
-  bool MadeChange = false;
-  
   // If we know nothing, then get the full set.
-  if (TypeVec.empty()) {
-    *this = TP.getDAGPatterns().getTargetInfo().getLegalValueTypes();
-    MadeChange = true;
-  }
-  
+  if (TypeVec.empty())
+    return FillWithPossibleTypes(TP, isScalar, "scalar");
+
   if (!hasVectorTypes())
-    return MadeChange;
+    return false;
+
+  TypeSet InputSet(*this);
   
   // Filter out all the vector types.
   for (unsigned i = 0; i != TypeVec.size(); ++i)
-    if (isVector(TypeVec[i]))
+    if (!isScalar(TypeVec[i]))
       TypeVec.erase(TypeVec.begin()+i--);
   
   if (TypeVec.empty())
     TP.error("Type inference contradiction found, '" +
              InputSet.getName() + "' needs to be scalar");
-  return MadeChange;
+  return true;
 }
 
 /// EnforceVector - Remove all vector types from this.
 bool EEVT::TypeSet::EnforceVector(TreePattern &TP) {
+  // If we know nothing, then get the full set.
+  if (TypeVec.empty())
+    return FillWithPossibleTypes(TP, isVector, "vector");
+
   TypeSet InputSet(*this);
   bool MadeChange = false;
   
-  // If we know nothing, then get the full set.
-  if (TypeVec.empty()) {
-    *this = TP.getDAGPatterns().getTargetInfo().getLegalValueTypes();
-    MadeChange = true;
-  }
-  
   // Filter out all the scalar types.
   for (unsigned i = 0; i != TypeVec.size(); ++i)
-    if (!isVector(TypeVec[i]))
+    if (!isVector(TypeVec[i])) {
       TypeVec.erase(TypeVec.begin()+i--);
+      MadeChange = true;
+    }
   
   if (TypeVec.empty())
     TP.error("Type inference contradiction found, '" +
@@ -296,72 +311,86 @@ bool EEVT::TypeSet::EnforceVector(TreePattern &TP) {
 }
 
 
+
 /// EnforceSmallerThan - 'this' must be a smaller VT than Other.  Update
 /// this an other based on this information.
 bool EEVT::TypeSet::EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP) {
   // Both operands must be integer or FP, but we don't care which.
   bool MadeChange = false;
   
-  // This code does not currently handle nodes which have multiple types,
-  // where some types are integer, and some are fp.  Assert that this is not
-  // the case.
-  assert(!(hasIntegerTypes() && hasFloatingPointTypes()) &&
-         !(Other.hasIntegerTypes() && Other.hasFloatingPointTypes()) &&
-         "SDTCisOpSmallerThanOp does not handle mixed int/fp types!");
+  if (isCompletelyUnknown())
+    MadeChange = FillWithPossibleTypes(TP);
+
+  if (Other.isCompletelyUnknown())
+    MadeChange = Other.FillWithPossibleTypes(TP);
+    
   // If one side is known to be integer or known to be FP but the other side has
   // no information, get at least the type integrality info in there.
-  if (hasIntegerTypes())
+  if (!hasFloatingPointTypes())
     MadeChange |= Other.EnforceInteger(TP);
-  else if (hasFloatingPointTypes())
+  else if (!hasIntegerTypes())
     MadeChange |= Other.EnforceFloatingPoint(TP);
-  if (Other.hasIntegerTypes())
+  if (!Other.hasFloatingPointTypes())
     MadeChange |= EnforceInteger(TP);
-  else if (Other.hasFloatingPointTypes())
+  else if (!Other.hasIntegerTypes())
     MadeChange |= EnforceFloatingPoint(TP);
   
   assert(!isCompletelyUnknown() && !Other.isCompletelyUnknown() &&
          "Should have a type list now");
   
   // If one contains vectors but the other doesn't pull vectors out.
-  if (!hasVectorTypes() && Other.hasVectorTypes())
+  if (!hasVectorTypes())
     MadeChange |= Other.EnforceScalar(TP);
-  if (hasVectorTypes() && !Other.hasVectorTypes())
+  if (!hasVectorTypes())
     MadeChange |= EnforceScalar(TP);
   
-  // FIXME: This is a bone-headed way to do this.
+  // This code does not currently handle nodes which have multiple types,
+  // where some types are integer, and some are fp.  Assert that this is not
+  // the case.
+  assert(!(hasIntegerTypes() && hasFloatingPointTypes()) &&
+         !(Other.hasIntegerTypes() && Other.hasFloatingPointTypes()) &&
+         "SDTCisOpSmallerThanOp does not handle mixed int/fp types!");
   
-  // Get the set of legal VTs and filter it based on the known integrality.
-  const CodeGenTarget &CGT = TP.getDAGPatterns().getTargetInfo();
-  TypeSet LegalVTs = CGT.getLegalValueTypes();
-
-  // TODO: If one or the other side is known to be a specific VT, we could prune
-  // LegalVTs.
-  if (hasIntegerTypes())
-    LegalVTs.EnforceInteger(TP);
-  else if (hasFloatingPointTypes())
-    LegalVTs.EnforceFloatingPoint(TP);
-  else
-    return MadeChange;
+  // Okay, find the smallest type from the current set and remove it from the
+  // largest set.
+  MVT::SimpleValueType Smallest = TypeVec[0];
+  for (unsigned i = 1, e = TypeVec.size(); i != e; ++i)
+    if (TypeVec[i] < Smallest)
+      Smallest = TypeVec[i];
   
-  switch (LegalVTs.TypeVec.size()) {
-  case 0: assert(0 && "No legal VTs?");
-  default:         // Too many VT's to pick from.
-    // TODO: If the biggest type in LegalVTs is in this set, we could remove it.
-    // If one or the other side is known to be a specific VT, we could prune
-    // LegalVTs.
-    return MadeChange;
-  case 1: 
-    // Only one VT of this flavor.  Cannot ever satisfy the constraints.
-    return MergeInTypeInfo(MVT::Other, TP);  // throw
-  case 2:
-    // If we have exactly two possible types, the little operand must be the
-    // small one, the big operand should be the big one.  This is common with 
-    // float/double for example.
-    assert(LegalVTs.TypeVec[0] < LegalVTs.TypeVec[1] && "Should be sorted!");
-    MadeChange |= MergeInTypeInfo(LegalVTs.TypeVec[0], TP);
-    MadeChange |= Other.MergeInTypeInfo(LegalVTs.TypeVec[1], TP);
-    return MadeChange;
-  }    
+  // If this is the only type in the large set, the constraint can never be
+  // satisfied.
+  if (Other.TypeVec.size() == 1 && Other.TypeVec[0] == Smallest)
+    TP.error("Type inference contradiction found, '" +
+             Other.getName() + "' has nothing larger than '" + getName() +"'!");
+  
+  SmallVector<MVT::SimpleValueType, 2>::iterator TVI =
+    std::find(Other.TypeVec.begin(), Other.TypeVec.end(), Smallest);
+  if (TVI != Other.TypeVec.end()) {
+    Other.TypeVec.erase(TVI);
+    MadeChange = true;
+  }
+  
+  // Okay, find the largest type in the Other set and remove it from the
+  // current set.
+  MVT::SimpleValueType Largest = Other.TypeVec[0];
+  for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i)
+    if (Other.TypeVec[i] > Largest)
+      Largest = Other.TypeVec[i];
+  
+  // If this is the only type in the small set, the constraint can never be
+  // satisfied.
+  if (TypeVec.size() == 1 && TypeVec[0] == Largest)
+    TP.error("Type inference contradiction found, '" +
+             getName() + "' has nothing smaller than '" + Other.getName()+"'!");
+  
+  TVI = std::find(TypeVec.begin(), TypeVec.end(), Largest);
+  if (TVI != TypeVec.end()) {
+    TypeVec.erase(TVI);
+    MadeChange = true;
+  }
+  
+  return MadeChange;
 }
 
 /// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type
@@ -372,10 +401,8 @@ bool EEVT::TypeSet::EnforceVectorEltTypeIs(MVT::SimpleValueType VT,
   bool MadeChange = false;
   
   // If we know nothing, then get the full set.
-  if (TypeVec.empty()) {
-    *this = TP.getDAGPatterns().getTargetInfo().getLegalValueTypes();
-    MadeChange = true;
-  }
+  if (TypeVec.empty())
+    MadeChange = FillWithPossibleTypes(TP, isVector, "vector");
   
   // Filter out all the non-vector types and types which don't have the right
   // element type.
@@ -511,24 +538,27 @@ SDTypeConstraint::SDTypeConstraint(Record *R) {
 }
 
 /// getOperandNum - Return the node corresponding to operand #OpNo in tree
-/// N, which has NumResults results.
-TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo,
-                                                 TreePatternNode *N,
-                                                 unsigned NumResults) const {
-  assert(NumResults <= 1 &&
-         "We only work with nodes with zero or one result so far!");
+/// N, and the result number in ResNo.
+static TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N,
+                                      const SDNodeInfo &NodeInfo,
+                                      unsigned &ResNo) {
+  unsigned NumResults = NodeInfo.getNumResults();
+  if (OpNo < NumResults) {
+    ResNo = OpNo;
+    return N;
+  }
+  
+  OpNo -= NumResults;
   
-  if (OpNo >= (NumResults + N->getNumChildren())) {
-    errs() << "Invalid operand number " << OpNo << " ";
+  if (OpNo >= N->getNumChildren()) {
+    errs() << "Invalid operand number in type constraint " 
+           << (OpNo+NumResults) << " ";
     N->dump();
     errs() << '\n';
     exit(1);
   }
 
-  if (OpNo < NumResults)
-    return N;  // FIXME: need value #
-  else
-    return N->getChild(OpNo-NumResults);
+  return N->getChild(OpNo);
 }
 
 /// ApplyTypeConstraint - Given a node in a pattern, apply this type
@@ -538,10 +568,6 @@ TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo,
 bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N,
                                            const SDNodeInfo &NodeInfo,
                                            TreePattern &TP) const {
-  unsigned NumResults = NodeInfo.getNumResults();
-  assert(NumResults <= 1 &&
-         "We only work with nodes with zero or one result so far!");
-  
   // Check that the number of operands is sane.  Negative operands -> varargs.
   if (NodeInfo.getNumOperands() >= 0) {
     if (N->getNumChildren() != (unsigned)NodeInfo.getNumOperands())
@@ -549,30 +575,32 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N,
                itostr(NodeInfo.getNumOperands()) + " operands!");
   }
 
-  TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NumResults);
+  unsigned ResNo = 0; // The result number being referenced.
+  TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NodeInfo, ResNo);
   
   switch (ConstraintType) {
   default: assert(0 && "Unknown constraint type!");
   case SDTCisVT:
     // Operand must be a particular type.
-    return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP);
+    return NodeToApply->UpdateNodeType(ResNo, x.SDTCisVT_Info.VT, TP);
   case SDTCisPtrTy:
     // Operand must be same as target pointer type.
-    return NodeToApply->UpdateNodeType(MVT::iPTR, TP);
+    return NodeToApply->UpdateNodeType(ResNo, MVT::iPTR, TP);
   case SDTCisInt:
     // Require it to be one of the legal integer VTs.
-    return NodeToApply->getExtType().EnforceInteger(TP);
+    return NodeToApply->getExtType(ResNo).EnforceInteger(TP);
   case SDTCisFP:
     // Require it to be one of the legal fp VTs.
-    return NodeToApply->getExtType().EnforceFloatingPoint(TP);
+    return NodeToApply->getExtType(ResNo).EnforceFloatingPoint(TP);
   case SDTCisVec:
     // Require it to be one of the legal vector VTs.
-    return NodeToApply->getExtType().EnforceVector(TP);
+    return NodeToApply->getExtType(ResNo).EnforceVector(TP);
   case SDTCisSameAs: {
+    unsigned OResNo = 0;
     TreePatternNode *OtherNode =
-      getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NumResults);
-    return NodeToApply->UpdateNodeType(OtherNode->getExtType(), TP) |
-           OtherNode->UpdateNodeType(NodeToApply->getExtType(), TP);
+      getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NodeInfo, OResNo);
+    return NodeToApply->UpdateNodeType(OResNo, OtherNode->getExtType(ResNo),TP)|
+           OtherNode->UpdateNodeType(ResNo,NodeToApply->getExtType(OResNo),TP);
   }
   case SDTCisVTSmallerThanOp: {
     // The NodeToApply must be a leaf node that is a VT.  OtherOperandNum must
@@ -587,40 +615,47 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N,
     if (!isInteger(VT))
       TP.error(N->getOperator()->getName() + " VT operand must be integer!");
     
+    unsigned OResNo = 0;
     TreePatternNode *OtherNode =
-      getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N,NumResults);
+      getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N, NodeInfo,
+                    OResNo);
     
     // It must be integer.
-    bool MadeChange = OtherNode->getExtType().EnforceInteger(TP);
+    bool MadeChange = OtherNode->getExtType(OResNo).EnforceInteger(TP);
 
     // This doesn't try to enforce any information on the OtherNode, it just
     // validates it when information is determined.
-    if (OtherNode->hasTypeSet() && OtherNode->getType() <= VT)
-      OtherNode->UpdateNodeType(MVT::Other, TP);  // Throw an error.
+    if (OtherNode->hasTypeSet(OResNo) && OtherNode->getType(OResNo) <= VT)
+      OtherNode->UpdateNodeType(OResNo, MVT::Other, TP);  // Throw an error.
     return MadeChange;
   }
   case SDTCisOpSmallerThanOp: {
+    unsigned BResNo = 0;
     TreePatternNode *BigOperand =
-      getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NumResults);
-    return NodeToApply->getExtType().
-                  EnforceSmallerThan(BigOperand->getExtType(), TP);
+      getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NodeInfo,
+                    BResNo);
+    return NodeToApply->getExtType(ResNo).
+                  EnforceSmallerThan(BigOperand->getExtType(BResNo), TP);
   }
   case SDTCisEltOfVec: {
+    unsigned VResNo = 0;
     TreePatternNode *VecOperand =
-      getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, N, NumResults);
-    if (VecOperand->hasTypeSet()) {
-      if (!isVector(VecOperand->getType()))
+      getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, N, NodeInfo,
+                    VResNo);
+    if (VecOperand->hasTypeSet(VResNo)) {
+      if (!isVector(VecOperand->getType(VResNo)))
         TP.error(N->getOperator()->getName() + " VT operand must be a vector!");
-      EVT IVT = VecOperand->getType();
+      EVT IVT = VecOperand->getType(VResNo);
       IVT = IVT.getVectorElementType();
-      return NodeToApply->UpdateNodeType(IVT.getSimpleVT().SimpleTy, TP);
+      return NodeToApply->UpdateNodeType(ResNo, IVT.getSimpleVT().SimpleTy, TP);
     }
     
-    if (NodeToApply->hasTypeSet() && VecOperand->getExtType().hasVectorTypes()){
+    if (NodeToApply->hasTypeSet(ResNo) &&
+        VecOperand->getExtType(VResNo).hasVectorTypes()){
       // Filter vector types out of VecOperand that don't have the right element
       // type.
-      return VecOperand->getExtType().
-        EnforceVectorEltTypeIs(NodeToApply->getType(), TP);
+      return VecOperand->getExtType(VResNo).
+        EnforceVectorEltTypeIs(NodeToApply->getType(ResNo), TP);
     }
     return false;
   }
@@ -662,6 +697,8 @@ SDNodeInfo::SDNodeInfo(Record *R) : Def(R) {
       Properties |= 1 << SDNPSideEffect;
     } else if (PropList[i]->getName() == "SDNPMemOperand") {
       Properties |= 1 << SDNPMemOperand;
+    } else if (PropList[i]->getName() == "SDNPVariadic") {
+      Properties |= 1 << SDNPVariadic;
     } else {
       errs() << "Unknown SD Node property '" << PropList[i]->getName()
              << "' on node '" << R->getName() << "'!\n";
@@ -678,8 +715,8 @@ SDNodeInfo::SDNodeInfo(Record *R) : Def(R) {
 
 /// getKnownType - If the type constraints on this node imply a fixed type
 /// (e.g. all stores return void, etc), then return it as an
-/// MVT::SimpleValueType.  Otherwise, return EEVT::isUnknown.
-unsigned SDNodeInfo::getKnownType() const {
+/// MVT::SimpleValueType.  Otherwise, return EEVT::Other.
+MVT::SimpleValueType SDNodeInfo::getKnownType() const {
   unsigned NumResults = getNumResults();
   assert(NumResults <= 1 &&
          "We only work with nodes with zero or one result so far!");
@@ -697,7 +734,7 @@ unsigned SDNodeInfo::getKnownType() const {
       return MVT::iPTR;
     }
   }
-  return EEVT::isUnknown;
+  return MVT::Other;
 }
 
 //===----------------------------------------------------------------------===//
@@ -711,17 +748,73 @@ TreePatternNode::~TreePatternNode() {
 #endif
 }
 
-
+static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) {
+  if (Operator->getName() == "set" ||
+      Operator->getName() == "implicit" ||
+      Operator->getName() == "parallel")
+    return 0;  // All return nothing.
+  
+  if (Operator->isSubClassOf("Intrinsic")) {
+    unsigned NumRes = CDP.getIntrinsic(Operator).IS.RetVTs.size();
+    if (NumRes == 1 && CDP.getIntrinsic(Operator).IS.RetVTs[0] == MVT::isVoid)
+      return 0;
+    return NumRes;
+  }
+  
+  if (Operator->isSubClassOf("SDNode"))
+    return CDP.getSDNodeInfo(Operator).getNumResults();
+  
+  if (Operator->isSubClassOf("PatFrag")) {
+    // If we've already parsed this pattern fragment, get it.  Otherwise, handle
+    // the forward reference case where one pattern fragment references another
+    // before it is processed.
+    if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator))
+      return PFRec->getOnlyTree()->getNumTypes();
+    
+    // Get the result tree.
+    DagInit *Tree = Operator->getValueAsDag("Fragment");
+    Record *Op = 0;
+    if (Tree && dynamic_cast<DefInit*>(Tree->getOperator()))
+      Op = dynamic_cast<DefInit*>(Tree->getOperator())->getDef();
+    assert(Op && "Invalid Fragment");
+    return GetNumNodeResults(Op, CDP);
+  }
+  
+  if (Operator->isSubClassOf("Instruction")) {
+    CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator);
+    
+    // FIXME: Handle implicit defs right.
+    if (InstInfo.NumDefs != 0)
+      return 1;     // FIXME: Handle inst results right!
+    
+    if (!InstInfo.ImplicitDefs.empty()) {
+      // Add on one implicit def if it has a resolvable type.
+      Record *FirstImplicitDef = InstInfo.ImplicitDefs[0];
+      assert(FirstImplicitDef->isSubClassOf("Register"));
+      const std::vector<MVT::SimpleValueType> &RegVTs = 
+      CDP.getTargetInfo().getRegisterVTs(FirstImplicitDef);
+      if (RegVTs.size() == 1)
+        return 1;
+    }
+    return 0;
+  }
+  
+  if (Operator->isSubClassOf("SDNodeXForm"))
+    return 1;  // FIXME: Generalize SDNodeXForm
+  
+  Operator->dump();
+  errs() << "Unhandled node in GetNumNodeResults\n";
+  exit(1);
+}
 
 void TreePatternNode::print(raw_ostream &OS) const {
-  if (isLeaf()) {
+  if (isLeaf())
     OS << *getLeafValue();
-  } else {
+  else
     OS << '(' << getOperator()->getName();
-  }
-  
-  if (!isTypeCompletelyUnknown())
-    OS << ':' << getExtType().getName();
+
+  for (unsigned i = 0, e = Types.size(); i != e; ++i)
+    OS << ':' << getExtType(i).getName();
 
   if (!isLeaf()) {
     if (getNumChildren() != 0) {
@@ -757,7 +850,7 @@ void TreePatternNode::dump() const {
 bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N,
                                      const MultipleUseVarSet &DepVars) const {
   if (N == this) return true;
-  if (N->isLeaf() != isLeaf() || getExtType() != N->getExtType() ||
+  if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() ||
       getPredicateFns() != N->getPredicateFns() ||
       getTransformFn() != N->getTransformFn())
     return false;
@@ -786,16 +879,16 @@ bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N,
 TreePatternNode *TreePatternNode::clone() const {
   TreePatternNode *New;
   if (isLeaf()) {
-    New = new TreePatternNode(getLeafValue());
+    New = new TreePatternNode(getLeafValue(), getNumTypes());
   } else {
     std::vector<TreePatternNode*> CChildren;
     CChildren.reserve(Children.size());
     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
       CChildren.push_back(getChild(i)->clone());
-    New = new TreePatternNode(getOperator(), CChildren);
+    New = new TreePatternNode(getOperator(), CChildren, getNumTypes());
   }
   New->setName(getName());
-  New->setType(getExtType());
+  New->Types = Types;
   New->setPredicateFns(getPredicateFns());
   New->setTransformFn(getTransformFn());
   return New;
@@ -803,7 +896,8 @@ TreePatternNode *TreePatternNode::clone() const {
 
 /// RemoveAllTypes - Recursively strip all the types of this tree.
 void TreePatternNode::RemoveAllTypes() {
-  setType(EEVT::TypeSet());  // Reset to unknown type.
+  for (unsigned i = 0, e = Types.size(); i != e; ++i)
+    Types[i] = EEVT::TypeSet();  // Reset to unknown type.
   if (isLeaf()) return;
   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
     getChild(i)->RemoveAllTypes();
@@ -885,7 +979,8 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) {
   }
   
   FragTree->setName(getName());
-  FragTree->UpdateNodeType(getExtType(), TP);
+  for (unsigned i = 0, e = Types.size(); i != e; ++i)
+    FragTree->UpdateNodeType(i, getExtType(i), TP);
 
   // Transfer in the old predicates.
   for (unsigned i = 0, e = getPredicateFns().size(); i != e; ++i)
@@ -903,8 +998,10 @@ TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) {
 /// type which should be applied to it.  This will infer the type of register
 /// references from the register file information, for example.
 ///
-static EEVT::TypeSet getImplicitType(Record *R, bool NotRegisters,
-                                     TreePattern &TP) {
+static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo,
+                                     bool NotRegisters, TreePattern &TP) {
+  assert(ResNo == 0 && "FIXME: Unhandled result number");
+  
   // Check to see if this is a register or a register class.
   if (R->isSubClassOf("RegisterClass")) {
     if (NotRegisters) 
@@ -1015,17 +1112,23 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
   if (isLeaf()) {
     if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) {
       // If it's a regclass or something else known, include the type.
-      return UpdateNodeType(getImplicitType(DI->getDef(), NotRegisters, TP),TP);
+      bool MadeChange = false;
+      for (unsigned i = 0, e = Types.size(); i != e; ++i)
+        MadeChange |= UpdateNodeType(i, getImplicitType(DI->getDef(), i,
+                                                        NotRegisters, TP), TP);
+      return MadeChange;
     }
     
     if (IntInit *II = dynamic_cast<IntInit*>(getLeafValue())) {
+      assert(Types.size() == 1 && "Invalid IntInit");
+      
       // Int inits are always integers. :)
-      bool MadeChange = Type.EnforceInteger(TP);
+      bool MadeChange = Types[0].EnforceInteger(TP);
       
-      if (!hasTypeSet())
+      if (!Types[0].isConcrete())
         return MadeChange;
       
-      MVT::SimpleValueType VT = getType();
+      MVT::SimpleValueType VT = getType(0);
       if (VT == MVT::iPTR || VT == MVT::iPTRAny)
         return MadeChange;
       
@@ -1046,7 +1149,7 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
         return MadeChange;
       
       TP.error("Integer value '" + itostr(II->getValue())+
-               "' is out of range for type '" + getEnumName(getType()) + "'!");
+               "' is out of range for type '" + getEnumName(getType(0)) + "'!");
       return MadeChange;
     }
     return false;
@@ -1054,27 +1157,31 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
   
   // special handling for set, which isn't really an SDNode.
   if (getOperator()->getName() == "set") {
-    assert (getNumChildren() >= 2 && "Missing RHS of a set?");
+    assert(getNumTypes() == 0 && "Set doesn't produce a value");
+    assert(getNumChildren() >= 2 && "Missing RHS of a set?");
     unsigned NC = getNumChildren();
-    bool MadeChange = false;
+    
+    TreePatternNode *SetVal = getChild(NC-1);
+    bool MadeChange = SetVal->ApplyTypeConstraints(TP, NotRegisters);
+
     for (unsigned i = 0; i < NC-1; ++i) {
-      MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
-      MadeChange |= getChild(NC-1)->ApplyTypeConstraints(TP, NotRegisters);
+      TreePatternNode *Child = getChild(i);
+      MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters);
     
       // Types of operands must match.
-      MadeChange |=getChild(i)->UpdateNodeType(getChild(NC-1)->getExtType(),TP);
-      MadeChange |=getChild(NC-1)->UpdateNodeType(getChild(i)->getExtType(),TP);
-      MadeChange |=UpdateNodeType(MVT::isVoid, TP);
+      MadeChange |= Child->UpdateNodeType(0, SetVal->getExtType(i), TP);
+      MadeChange |= SetVal->UpdateNodeType(i, Child->getExtType(0), TP);
     }
     return MadeChange;
   }
   
   if (getOperator()->getName() == "implicit" ||
       getOperator()->getName() == "parallel") {
+    assert(getNumTypes() == 0 && "Node doesn't produce a value");
+
     bool MadeChange = false;
     for (unsigned i = 0; i < getNumChildren(); ++i)
       MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
-    MadeChange |= UpdateNodeType(MVT::isVoid, TP);
     return MadeChange;
   }
   
@@ -1083,13 +1190,16 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
     MadeChange |= getChild(0)->ApplyTypeConstraints(TP, NotRegisters);
     MadeChange |= getChild(1)->ApplyTypeConstraints(TP, NotRegisters);
     
+    assert(getChild(0)->getNumTypes() == 1 &&
+           getChild(1)->getNumTypes() == 1 && "Unhandled case");
+    
     // child #1 of COPY_TO_REGCLASS should be a register class.  We don't care
     // what type it gets, so if it didn't get a concrete type just give it the
     // first viable type from the reg class.
-    if (!getChild(1)->hasTypeSet() &&
-        !getChild(1)->getExtType().isCompletelyUnknown()) {
-      MVT::SimpleValueType RCVT = getChild(1)->getExtType().getTypeList()[0];
-      MadeChange |= getChild(1)->UpdateNodeType(RCVT, TP);
+    if (!getChild(1)->hasTypeSet(0) &&
+        !getChild(1)->getExtType(0).isCompletelyUnknown()) {
+      MVT::SimpleValueType RCVT = getChild(1)->getExtType(0).getTypeList()[0];
+      MadeChange |= getChild(1)->UpdateNodeType(0, RCVT, TP);
     }
     return MadeChange;
   }
@@ -1100,22 +1210,26 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
     // Apply the result type to the node.
     unsigned NumRetVTs = Int->IS.RetVTs.size();
     unsigned NumParamVTs = Int->IS.ParamVTs.size();
-
+    if (NumRetVTs == 1 && Int->IS.RetVTs[0] == MVT::isVoid)
+      NumRetVTs = 0;
+    
     for (unsigned i = 0, e = NumRetVTs; i != e; ++i)
-      MadeChange |= UpdateNodeType(Int->IS.RetVTs[i], TP);
+      MadeChange |= UpdateNodeType(i, Int->IS.RetVTs[i], TP);
 
-    if (getNumChildren() != NumParamVTs + NumRetVTs)
+    if (getNumChildren() != NumParamVTs + 1)
       TP.error("Intrinsic '" + Int->Name + "' expects " +
-               utostr(NumParamVTs + NumRetVTs - 1) + " operands, not " +
+               utostr(NumParamVTs) + " operands, not " +
                utostr(getNumChildren() - 1) + " operands!");
 
     // Apply type info to the intrinsic ID.
-    MadeChange |= getChild(0)->UpdateNodeType(MVT::iPTR, TP);
+    MadeChange |= getChild(0)->UpdateNodeType(0, MVT::iPTR, TP);
     
-    for (unsigned i = NumRetVTs, e = getNumChildren(); i != e; ++i) {
-      MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i - NumRetVTs];
-      MadeChange |= getChild(i)->UpdateNodeType(OpVT, TP);
-      MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
+    for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) {
+      MadeChange |= getChild(i+1)->ApplyTypeConstraints(TP, NotRegisters);
+      
+      MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i];
+      assert(getChild(i+1)->getNumTypes() == 1 && "Unhandled case");
+      MadeChange |= getChild(i+1)->UpdateNodeType(0, OpVT, TP);
     }
     return MadeChange;
   }
@@ -1126,51 +1240,60 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
     bool MadeChange = NI.ApplyTypeConstraints(this, TP);
     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
       MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
-    // Branch, etc. do not produce results and top-level forms in instr pattern
-    // must have void types.
-    if (NI.getNumResults() == 0)
-      MadeChange |= UpdateNodeType(MVT::isVoid, TP);
-    
-    return MadeChange;  
+    return MadeChange;
   }
   
   if (getOperator()->isSubClassOf("Instruction")) {
     const DAGInstruction &Inst = CDP.getInstruction(getOperator());
-    bool MadeChange = false;
-    unsigned NumResults = Inst.getNumResults();
-    
-    assert(NumResults <= 1 &&
-           "Only supports zero or one result instrs!");
+    unsigned ResNo = 0;
+    assert(Inst.getNumResults() <= 1 &&
+           "FIXME: Only supports zero or one result instrs!");
 
     CodeGenInstruction &InstInfo =
-      CDP.getTargetInfo().getInstruction(getOperator()->getName());
+      CDP.getTargetInfo().getInstruction(getOperator());
+    
+    EEVT::TypeSet ResultType;
+    
     // Apply the result type to the node
-    if (NumResults == 0 || InstInfo.NumDefs == 0) {
-      MadeChange = UpdateNodeType(MVT::isVoid, TP);
-    } else {
+    if (InstInfo.NumDefs != 0) { // # of elements in (outs) list
       Record *ResultNode = Inst.getResult(0);
       
       if (ResultNode->isSubClassOf("PointerLikeRegClass")) {
-        MadeChange = UpdateNodeType(MVT::iPTR, TP);
+        ResultType = EEVT::TypeSet(MVT::iPTR, TP);
       } else if (ResultNode->getName() == "unknown") {
         // Nothing to do.
       } else {
         assert(ResultNode->isSubClassOf("RegisterClass") &&
                "Operands should be register classes!");
-
         const CodeGenRegisterClass &RC = 
           CDP.getTargetInfo().getRegisterClass(ResultNode);
-        MadeChange = UpdateNodeType(RC.getValueTypes(), TP);
+        ResultType = RC.getValueTypes();
       }
+    } else if (!InstInfo.ImplicitDefs.empty()) {
+      // If the instruction has implicit defs, the first one defines the result
+      // type.
+      Record *FirstImplicitDef = InstInfo.ImplicitDefs[0];
+      assert(FirstImplicitDef->isSubClassOf("Register"));
+      const std::vector<MVT::SimpleValueType> &RegVTs = 
+        CDP.getTargetInfo().getRegisterVTs(FirstImplicitDef);
+      if (RegVTs.size() == 1)   // FIXME: Generalize.
+        ResultType = EEVT::TypeSet(RegVTs);
+    } else {
+      // Otherwise, the instruction produces no value result.
     }
     
+    bool MadeChange = false;
+    
+    if (!ResultType.isCompletelyUnknown())
+      MadeChange |= UpdateNodeType(ResNo, ResultType, TP);
+    
     // If this is an INSERT_SUBREG, constrain the source and destination VTs to
     // be the same.
     if (getOperator()->getName() == "INSERT_SUBREG") {
-      MadeChange |= UpdateNodeType(getChild(0)->getExtType(), TP);
-      MadeChange |= getChild(0)->UpdateNodeType(getExtType(), TP);
+      assert(getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled");
+      MadeChange |= UpdateNodeType(0, getChild(0)->getExtType(0), TP);
+      MadeChange |= getChild(0)->UpdateNodeType(0, getExtType(0), TP);
     }
-    
 
     unsigned ChildNo = 0;
     for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) {
@@ -1191,15 +1314,17 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
       
       MVT::SimpleValueType VT;
       TreePatternNode *Child = getChild(ChildNo++);
+      assert(Child->getNumTypes() == 1 && "Unknown case?");
+      
       if (OperandNode->isSubClassOf("RegisterClass")) {
         const CodeGenRegisterClass &RC = 
           CDP.getTargetInfo().getRegisterClass(OperandNode);
-        MadeChange |= Child->UpdateNodeType(RC.getValueTypes(), TP);
+        MadeChange |= Child->UpdateNodeType(0, RC.getValueTypes(), TP);
       } else if (OperandNode->isSubClassOf("Operand")) {
         VT = getValueType(OperandNode->getValueAsDef("Type"));
-        MadeChange |= Child->UpdateNodeType(VT, TP);
+        MadeChange |= Child->UpdateNodeType(0, VT, TP);
       } else if (OperandNode->isSubClassOf("PointerLikeRegClass")) {
-        MadeChange |= Child->UpdateNodeType(MVT::iPTR, TP);
+        MadeChange |= Child->UpdateNodeType(0, MVT::iPTR, TP);
       } else if (OperandNode->getName() == "unknown") {
         // Nothing to do.
       } else {
@@ -1331,6 +1456,7 @@ void TreePattern::ComputeNamedNodes(TreePatternNode *N) {
     ComputeNamedNodes(N->getChild(i));
 }
 
+
 TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
   DefInit *OpDef = dynamic_cast<DefInit*>(Dag->getOperator());
   if (!OpDef) error("Pattern has unexpected operator type!");
@@ -1359,11 +1485,11 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
         Args.push_back(Dag->getArgName(0));
       }
       
-      New = new TreePatternNode(DI);
+      New = new TreePatternNode(DI, 1);
     } else if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
       New = ParseTreePattern(DI);
     } else if (IntInit *II = dynamic_cast<IntInit*>(Arg)) {
-      New = new TreePatternNode(II);
+      New = new TreePatternNode(II, 1);
       if (!Dag->getArgName(0).empty())
         error("Constant int argument should not have a name!");
     } else if (BitsInit *BI = dynamic_cast<BitsInit*>(Arg)) {
@@ -1372,7 +1498,7 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
       if (II == 0 || !dynamic_cast<IntInit*>(II))
         error("Bits value must be constants!");
       
-      New = new TreePatternNode(dynamic_cast<IntInit*>(II));
+      New = new TreePatternNode(dynamic_cast<IntInit*>(II), 1);
       if (!Dag->getArgName(0).empty())
         error("Constant int argument should not have a name!");
     } else {
@@ -1382,7 +1508,8 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
     }
     
     // Apply the type cast.
-    New->UpdateNodeType(getValueType(Operator), *this);
+    assert(New->getNumTypes() == 1 && "FIXME: Unhandled");
+    New->UpdateNodeType(0, getValueType(Operator), *this);
     if (New->getNumChildren() == 0)
       New->setName(Dag->getArgName(0));
     return New;
@@ -1421,7 +1548,7 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
                               std::vector<std::pair<Init*, std::string> >()));
         --i;  // Revisit this node...
       } else {
-        TreePatternNode *Node = new TreePatternNode(DefI);
+        TreePatternNode *Node = new TreePatternNode(DefI, 1);
         Node->setName(Dag->getArgName(i));
         Children.push_back(Node);
         
@@ -1433,7 +1560,7 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
         }
       }
     } else if (IntInit *II = dynamic_cast<IntInit*>(Arg)) {
-      TreePatternNode *Node = new TreePatternNode(II);
+      TreePatternNode *Node = new TreePatternNode(II, 1);
       if (!Dag->getArgName(i).empty())
         error("Constant int argument should not have a name!");
       Children.push_back(Node);
@@ -1443,7 +1570,7 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
       if (II == 0 || !dynamic_cast<IntInit*>(II))
         error("Bits value must be constants!");
       
-      TreePatternNode *Node = new TreePatternNode(dynamic_cast<IntInit*>(II));
+      TreePatternNode *Node = new TreePatternNode(dynamic_cast<IntInit*>(II),1);
       if (!Dag->getArgName(i).empty())
         error("Constant int argument should not have a name!");
       Children.push_back(Node);
@@ -1474,11 +1601,12 @@ TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
       Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode();
     }
     
-    TreePatternNode *IIDNode = new TreePatternNode(new IntInit(IID));
+    TreePatternNode *IIDNode = new TreePatternNode(new IntInit(IID), 1);
     Children.insert(Children.begin(), IIDNode);
   }
   
-  TreePatternNode *Result = new TreePatternNode(Operator, Children);
+  unsigned NumResults = GetNumNodeResults(Operator, CDP);
+  TreePatternNode *Result = new TreePatternNode(Operator, Children, NumResults);
   Result->setName(Dag->getName());
   return Result;
 }
@@ -1525,7 +1653,11 @@ InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) {
               continue;
           }
           
-          MadeChange |=Nodes[i]->UpdateNodeType(InNodes[0]->getExtType(),*this);
+          assert(Nodes[i]->getNumTypes() == 1 &&
+                 InNodes[0]->getNumTypes() == 1 &&
+                 "FIXME: cannot name multiple result nodes yet");
+          MadeChange |= Nodes[i]->UpdateNodeType(0, InNodes[0]->getExtType(0),
+                                                 *this);
         }
       }
       
@@ -1533,8 +1665,12 @@ InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) {
       // same type.
       if (I->second.size() > 1) {
         for (unsigned i = 0, e = Nodes.size()-1; i != e; ++i) {
-          MadeChange |=Nodes[i]->UpdateNodeType(Nodes[i+1]->getExtType(),*this);
-          MadeChange |=Nodes[i+1]->UpdateNodeType(Nodes[i]->getExtType(),*this);
+          TreePatternNode *N1 = Nodes[i], *N2 = Nodes[i+1];
+          assert(N1->getNumTypes() == 1 && N2->getNumTypes() == 1 &&
+                 "FIXME: cannot name multiple result nodes yet");
+          
+          MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this);
+          MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this);
         }
       }
     }
@@ -1832,7 +1968,7 @@ static bool HandleUse(TreePattern *I, TreePatternNode *Pat,
   // Ensure that the inputs agree if we've already seen this input.
   if (Rec != SlotRec)
     I->error("All $" + Pat->getName() + " inputs must agree with each other");
-  if (Slot->getExtType() != Pat->getExtType())
+  if (Slot->getExtTypes() != Pat->getExtTypes())
     I->error("All $" + Pat->getName() + " inputs must agree with each other");
   return true;
 }
@@ -1871,7 +2007,7 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
     // If this is not a set, verify that the children nodes are not void typed,
     // and recurse.
     for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) {
-      if (Pat->getChild(i)->getType() == MVT::isVoid)
+      if (Pat->getChild(i)->getNumTypes() == 0)
         I->error("Cannot have void nodes inside of patterns!");
       FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults,
                                   InstImpInputs, InstImpResults);
@@ -1933,10 +2069,12 @@ class InstAnalyzer {
   bool &mayStore;
   bool &mayLoad;
   bool &HasSideEffects;
+  bool &IsVariadic;
 public:
   InstAnalyzer(const CodeGenDAGPatterns &cdp,
-               bool &maystore, bool &mayload, bool &hse)
-    : CDP(cdp), mayStore(maystore), mayLoad(mayload), HasSideEffects(hse){
+               bool &maystore, bool &mayload, bool &hse, bool &isv)
+    : CDP(cdp), mayStore(maystore), mayLoad(mayload), HasSideEffects(hse),
+      IsVariadic(isv) {
   }
 
   /// Analyze - Analyze the specified instruction, returning true if the
@@ -1985,6 +2123,7 @@ private:
     if (OpInfo.hasProperty(SDNPMayStore)) mayStore = true;
     if (OpInfo.hasProperty(SDNPMayLoad)) mayLoad = true;
     if (OpInfo.hasProperty(SDNPSideEffect)) HasSideEffects = true;
+    if (OpInfo.hasProperty(SDNPVariadic)) IsVariadic = true;
 
     if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) {
       // If this is an intrinsic, analyze it.
@@ -2004,12 +2143,13 @@ private:
 
 static void InferFromPattern(const CodeGenInstruction &Inst,
                              bool &MayStore, bool &MayLoad,
-                             bool &HasSideEffects,
+                             bool &HasSideEffects, bool &IsVariadic,
                              const CodeGenDAGPatterns &CDP) {
-  MayStore = MayLoad = HasSideEffects = false;
+  MayStore = MayLoad = HasSideEffects = IsVariadic = false;
 
   bool HadPattern =
-    InstAnalyzer(CDP, MayStore, MayLoad, HasSideEffects).Analyze(Inst.TheDef);
+    InstAnalyzer(CDP, MayStore, MayLoad, HasSideEffects, IsVariadic)
+    .Analyze(Inst.TheDef);
 
   // InstAnalyzer only correctly analyzes mayStore/mayLoad so far.
   if (Inst.mayStore) {  // If the .td file explicitly sets mayStore, use it.
@@ -2047,6 +2187,9 @@ static void InferFromPattern(const CodeGenInstruction &Inst,
               "which already inferred this.\n", Inst.TheDef->getName().c_str());
     HasSideEffects = true;
   }
+  
+  if (Inst.isVariadic)
+    IsVariadic = true;  // Can warn if we want.
 }
 
 /// ParseInstructions - Parse all of the instructions, inlining and resolving
@@ -2068,7 +2211,7 @@ void CodeGenDAGPatterns::ParseInstructions() {
       std::vector<Record*> Results;
       std::vector<Record*> Operands;
       
-      CodeGenInstruction &InstInfo =Target.getInstruction(Instrs[i]->getName());
+      CodeGenInstruction &InstInfo = Target.getInstruction(Instrs[i]);
 
       if (InstInfo.OperandList.size() != 0) {
         if (InstInfo.NumDefs == 0) {
@@ -2119,7 +2262,7 @@ void CodeGenDAGPatterns::ParseInstructions() {
     // fill in the InstResults map.
     for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) {
       TreePatternNode *Pat = I->getTree(j);
-      if (!Pat->hasTypeSet() || Pat->getType() != MVT::isVoid)
+      if (Pat->getNumTypes() != 0)
         I->error("Top-level forms in instruction pattern should have"
                  " void types");
 
@@ -2135,11 +2278,11 @@ void CodeGenDAGPatterns::ParseInstructions() {
 
     // Parse the operands list from the (ops) list, validating it.
     assert(I->getArgList().empty() && "Args list should still be empty here!");
-    CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]->getName());
+    CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]);
 
     // Check that all of the results occur first in the list.
     std::vector<Record*> Results;
-    TreePatternNode *Res0Node = NULL;
+    TreePatternNode *Res0Node = 0;
     for (unsigned i = 0; i != NumResults; ++i) {
       if (i == CGI.OperandList.size())
         I->error("'" + InstResults.begin()->first +
@@ -2217,7 +2360,7 @@ void CodeGenDAGPatterns::ParseInstructions() {
         OpNode->setTransformFn(0);
         std::vector<TreePatternNode*> Children;
         Children.push_back(OpNode);
-        OpNode = new TreePatternNode(Xform, Children);
+        OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes());
       }
       
       ResultNodeOperands.push_back(OpNode);
@@ -2228,10 +2371,11 @@ void CodeGenDAGPatterns::ParseInstructions() {
                " occurs in pattern but not in operands list!");
 
     TreePatternNode *ResultPattern =
-      new TreePatternNode(I->getRecord(), ResultNodeOperands);
+      new TreePatternNode(I->getRecord(), ResultNodeOperands,
+                          GetNumNodeResults(I->getRecord(), *this));
     // Copy fully inferred output node type to instruction result pattern.
-    if (NumResults > 0)
-      ResultPattern->setType(Res0Node->getExtType());
+    for (unsigned i = 0; i != NumResults; ++i)
+      ResultPattern->setType(i, Res0Node->getExtType(i));
 
     // Create and insert the instruction.
     // FIXME: InstImpResults and InstImpInputs should not be part of
@@ -2292,7 +2436,7 @@ static void FindNames(const TreePatternNode *P,
     // If this is the first instance of the name, remember the node.
     if (Rec.second++ == 0)
       Rec.first = P;
-    else if (Rec.first->getType() != P->getType())
+    else if (Rec.first->getExtTypes() != P->getExtTypes())
       PatternTop->error("repetition of value: $" + P->getName() +
                         " where different uses have different types!");
   }
@@ -2347,17 +2491,19 @@ void CodeGenDAGPatterns::AddPatternToMatch(const TreePattern *Pattern,
 
 
 void CodeGenDAGPatterns::InferInstructionFlags() {
-  std::map<std::string, CodeGenInstruction> &InstrDescs =
-    Target.getInstructions();
-  for (std::map<std::string, CodeGenInstruction>::iterator
-         II = InstrDescs.begin(), E = InstrDescs.end(); II != E; ++II) {
-    CodeGenInstruction &InstInfo = II->second;
+  const std::vector<const CodeGenInstruction*> &Instructions =
+    Target.getInstructionsByEnumValue();
+  for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
+    CodeGenInstruction &InstInfo =
+      const_cast<CodeGenInstruction &>(*Instructions[i]);
     // Determine properties of the instruction from its pattern.
-    bool MayStore, MayLoad, HasSideEffects;
-    InferFromPattern(InstInfo, MayStore, MayLoad, HasSideEffects, *this);
+    bool MayStore, MayLoad, HasSideEffects, IsVariadic;
+    InferFromPattern(InstInfo, MayStore, MayLoad, HasSideEffects, IsVariadic,
+                     *this);
     InstInfo.mayStore = MayStore;
     InstInfo.mayLoad = MayLoad;
     InstInfo.hasSideEffects = HasSideEffects;
+    InstInfo.isVariadic = IsVariadic;
   }
 }
 
@@ -2378,23 +2524,29 @@ static bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) {
 
   // If this type is already concrete or completely unknown we can't do
   // anything.
-  if (N->getExtType().isCompletelyUnknown() || N->getExtType().isConcrete())
-    return false;
+  for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) {
+    if (N->getExtType(i).isCompletelyUnknown() || N->getExtType(i).isConcrete())
+      continue;
+  
+    // Otherwise, force its type to the first possibility (an arbitrary choice).
+    if (N->getExtType(i).MergeInTypeInfo(N->getExtType(i).getTypeList()[0], TP))
+      return true;
+  }
   
-  // Otherwise, force its type to the first possibility (an arbitrary choice).
-  return N->getExtType().MergeInTypeInfo(N->getExtType().getTypeList()[0], TP);
+  return false;
 }
 
 void CodeGenDAGPatterns::ParsePatterns() {
   std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");
 
   for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
-    DagInit *Tree = Patterns[i]->getValueAsDag("PatternToMatch");
+    Record *CurPattern = Patterns[i];
+    DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch");
     DefInit *OpDef = dynamic_cast<DefInit*>(Tree->getOperator());
     Record *Operator = OpDef->getDef();
     TreePattern *Pattern;
     if (Operator->getName() != "parallel")
-      Pattern = new TreePattern(Patterns[i], Tree, true, *this);
+      Pattern = new TreePattern(CurPattern, Tree, true, *this);
     else {
       std::vector<Init*> Values;
       RecTy *ListTy = 0;
@@ -2419,17 +2571,17 @@ void CodeGenDAGPatterns::ParsePatterns() {
         }
       }
       ListInit *LI = new ListInit(Values, new ListRecTy(ListTy));
-      Pattern = new TreePattern(Patterns[i], LI, true, *this);
+      Pattern = new TreePattern(CurPattern, LI, true, *this);
     }
 
     // Inline pattern fragments into it.
     Pattern->InlinePatternFragments();
     
-    ListInit *LI = Patterns[i]->getValueAsListInit("ResultInstrs");
+    ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs");
     if (LI->getSize() == 0) continue;  // no pattern.
     
     // Parse the instruction.
-    TreePattern *Result = new TreePattern(Patterns[i], LI, false, *this);
+    TreePattern *Result = new TreePattern(CurPattern, LI, false, *this);
     
     // Inline pattern fragments into it.
     Result->InlinePatternFragments();
@@ -2451,14 +2603,20 @@ void CodeGenDAGPatterns::ParsePatterns() {
       InferredAllResultTypes =
         Result->InferAllTypes(&Pattern->getNamedNodesMap());
 
+      IterateInference = false;
+      
       // Apply the type of the result to the source pattern.  This helps us
       // resolve cases where the input type is known to be a pointer type (which
       // is considered resolved), but the result knows it needs to be 32- or
       // 64-bits.  Infer the other way for good measure.
-      IterateInference = Pattern->getTree(0)->
-        UpdateNodeType(Result->getTree(0)->getExtType(), *Result);
-      IterateInference |= Result->getTree(0)->
-        UpdateNodeType(Pattern->getTree(0)->getExtType(), *Result);
+      for (unsigned i = 0, e = std::min(Result->getTree(0)->getNumTypes(),
+                                        Pattern->getTree(0)->getNumTypes());
+           i != e; ++i) {
+        IterateInference = Pattern->getTree(0)->
+          UpdateNodeType(i, Result->getTree(0)->getExtType(i), *Result);
+        IterateInference |= Result->getTree(0)->
+          UpdateNodeType(i, Pattern->getTree(0)->getExtType(i), *Result);
+      }
       
       // If our iteration has converged and the input pattern's types are fully
       // resolved but the result pattern is not fully resolved, we may have a
@@ -2473,7 +2631,6 @@ void CodeGenDAGPatterns::ParsePatterns() {
           !InferredAllResultTypes)
         IterateInference = ForceArbitraryInstResultType(Result->getTree(0),
                                                         *Result);
-      
     } while (IterateInference);
     
     // Verify that we inferred enough types that we can do something with the
@@ -2504,25 +2661,29 @@ void CodeGenDAGPatterns::ParsePatterns() {
         OpNode->setTransformFn(0);
         std::vector<TreePatternNode*> Children;
         Children.push_back(OpNode);
-        OpNode = new TreePatternNode(Xform, Children);
+        OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes());
       }
       ResultNodeOperands.push_back(OpNode);
     }
     DstPattern = Result->getOnlyTree();
     if (!DstPattern->isLeaf())
       DstPattern = new TreePatternNode(DstPattern->getOperator(),
-                                       ResultNodeOperands);
-    DstPattern->setType(Result->getOnlyTree()->getExtType());
+                                       ResultNodeOperands,
+                                       DstPattern->getNumTypes());
+    
+    for (unsigned i = 0, e = Result->getOnlyTree()->getNumTypes(); i != e; ++i)
+      DstPattern->setType(i, Result->getOnlyTree()->getExtType(i));
+    
     TreePattern Temp(Result->getRecord(), DstPattern, false, *this);
     Temp.InferAllTypes();
 
     
     AddPatternToMatch(Pattern,
-                 PatternToMatch(Patterns[i]->getValueAsListInit("Predicates"),
-                                Pattern->getTree(0),
-                                Temp.getOnlyTree(), InstImpResults,
-                                Patterns[i]->getValueAsInt("AddedComplexity"),
-                                Patterns[i]->getID()));
+                    PatternToMatch(CurPattern->getValueAsListInit("Predicates"),
+                                   Pattern->getTree(0),
+                                   Temp.getOnlyTree(), InstImpResults,
+                                   CurPattern->getValueAsInt("AddedComplexity"),
+                                   CurPattern->getID()));
   }
 }
 
@@ -2556,13 +2717,15 @@ static void CombineChildVariants(TreePatternNode *Orig,
     std::vector<TreePatternNode*> NewChildren;
     for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i)
       NewChildren.push_back(ChildVariants[i][Idxs[i]]);
-    TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren);
+    TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren,
+                                             Orig->getNumTypes());
     
     // Copy over properties.
     R->setName(Orig->getName());
     R->setPredicateFns(Orig->getPredicateFns());
     R->setTransformFn(Orig->getTransformFn());
-    R->setType(Orig->getExtType());
+    for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i)
+      R->setType(i, Orig->getExtType(i));
     
     // If this pattern cannot match, do not include it as a variant.
     std::string ErrString;