Reapply r143177 and r143179 (reverting r143188), with scheduler

fixes: Use a separate register, instead of SP, as the
calling-convention resource, to avoid spurious conflicts with
actual uses of SP. Also, fix unscheduling of calling sequences,
which can be triggered by pseudo-two-address dependencies.


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

4 files changed, 436 insertions, 518 deletions

diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index a8bccda291..7425669192 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -46,37 +46,18 @@ using namespace llvm;
 /// will attempt merge setcc and brc instructions into brcc's.
 ///
 namespace {
-class SelectionDAGLegalize {
+class SelectionDAGLegalize : public SelectionDAG::DAGUpdateListener {
   const TargetMachine &TM;
   const TargetLowering &TLI;
   SelectionDAG &DAG;
 
-  // Libcall insertion helpers.
-
-  /// LastCALLSEQ_END - This keeps track of the CALLSEQ_END node that has been
-  /// legalized.  We use this to ensure that calls are properly serialized
-  /// against each other, including inserted libcalls.
-  SDValue LastCALLSEQ_END;
-
-  /// IsLegalizingCall - This member is used *only* for purposes of providing
-  /// helpful assertions that a libcall isn't created while another call is
-  /// being legalized (which could lead to non-serialized call sequences).
-  bool IsLegalizingCall;
+  /// LegalizePosition - The iterator for walking through the node list.
+  SelectionDAG::allnodes_iterator LegalizePosition;
 
-  /// LegalizedNodes - For nodes that are of legal width, and that have more
-  /// than one use, this map indicates what regularized operand to use.  This
-  /// allows us to avoid legalizing the same thing more than once.
-  DenseMap<SDValue, SDValue> LegalizedNodes;
+  /// LegalizedNodes - The set of nodes which have already been legalized.
+  SmallPtrSet<SDNode *, 16> LegalizedNodes;
 
-  void AddLegalizedOperand(SDValue From, SDValue To) {
-    LegalizedNodes.insert(std::make_pair(From, To));
-    // If someone requests legalization of the new node, return itself.
-    if (From != To)
-      LegalizedNodes.insert(std::make_pair(To, To));
-
-    // Transfer SDDbgValues.
-    DAG.TransferDbgValues(From, To);
-  }
+  // Libcall insertion helpers.
 
 public:
   explicit SelectionDAGLegalize(SelectionDAG &DAG);
@@ -84,9 +65,8 @@ public:
   void LegalizeDAG();
 
 private:
-  /// LegalizeOp - Return a legal replacement for the given operation, with
-  /// all legal operands.
-  SDValue LegalizeOp(SDValue O);
+  /// LegalizeOp - Legalizes the given operation.
+  void LegalizeOp(SDNode *Node);
 
   SDValue OptimizeFloatStore(StoreSDNode *ST);
 
@@ -107,9 +87,6 @@ private:
                                      SDValue N1, SDValue N2,
                                      SmallVectorImpl<int> &Mask) const;
 
-  bool LegalizeAllNodesNotLeadingTo(SDNode *N, SDNode *Dest,
-                                    SmallPtrSet<SDNode*, 32> &NodesLeadingTo);
-
   void LegalizeSetCCCondCode(EVT VT, SDValue &LHS, SDValue &RHS, SDValue &CC,
                              DebugLoc dl);
 
@@ -150,10 +127,21 @@ private:
   SDValue ExpandInsertToVectorThroughStack(SDValue Op);
   SDValue ExpandVectorBuildThroughStack(SDNode* Node);
 
+  SDValue ExpandConstantFP(ConstantFPSDNode *CFP, bool UseCP);
+
   std::pair<SDValue, SDValue> ExpandAtomic(SDNode *Node);
 
-  void ExpandNode(SDNode *Node, SmallVectorImpl<SDValue> &Results);
-  void PromoteNode(SDNode *Node, SmallVectorImpl<SDValue> &Results);
+  void ExpandNode(SDNode *Node);
+  void PromoteNode(SDNode *Node);
+
+  // DAGUpdateListener implementation.
+  virtual void NodeDeleted(SDNode *N, SDNode *E) {
+    LegalizedNodes.erase(N);
+    if (LegalizePosition == SelectionDAG::allnodes_iterator(N))
+      ++LegalizePosition;
+  }
+
+  virtual void NodeUpdated(SDNode *N) {}
 };
 }
 
@@ -195,145 +183,37 @@ SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag)
 }
 
 void SelectionDAGLegalize::LegalizeDAG() {
-  LastCALLSEQ_END = DAG.getEntryNode();
-  IsLegalizingCall = false;
-
-  // The legalize process is inherently a bottom-up recursive process (users
-  // legalize their uses before themselves).  Given infinite stack space, we
-  // could just start legalizing on the root and traverse the whole graph.  In
-  // practice however, this causes us to run out of stack space on large basic
-  // blocks.  To avoid this problem, compute an ordering of the nodes where each
-  // node is only legalized after all of its operands are legalized.
   DAG.AssignTopologicalOrder();
-  for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
-       E = prior(DAG.allnodes_end()); I != llvm::next(E); ++I)
-    LegalizeOp(SDValue(I, 0));
-
-  // Finally, it's possible the root changed.  Get the new root.
-  SDValue OldRoot = DAG.getRoot();
-  assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?");
-  DAG.setRoot(LegalizedNodes[OldRoot]);
-
-  LegalizedNodes.clear();
-
-  // Remove dead nodes now.
-  DAG.RemoveDeadNodes();
-}
-
 
-/// FindCallEndFromCallStart - Given a chained node that is part of a call
-/// sequence, find the CALLSEQ_END node that terminates the call sequence.
-static SDNode *FindCallEndFromCallStart(SDNode *Node, int depth = 0) {
-  // Nested CALLSEQ_START/END constructs aren't yet legal,
-  // but we can DTRT and handle them correctly here.
-  if (Node->getOpcode() == ISD::CALLSEQ_START)
-    depth++;
-  else if (Node->getOpcode() == ISD::CALLSEQ_END) {
-    depth--;
-    if (depth == 0)
-      return Node;
-  }
-  if (Node->use_empty())
-    return 0;   // No CallSeqEnd
-
-  // The chain is usually at the end.
-  SDValue TheChain(Node, Node->getNumValues()-1);
-  if (TheChain.getValueType() != MVT::Other) {
-    // Sometimes it's at the beginning.
-    TheChain = SDValue(Node, 0);
-    if (TheChain.getValueType() != MVT::Other) {
-      // Otherwise, hunt for it.
-      for (unsigned i = 1, e = Node->getNumValues(); i != e; ++i)
-        if (Node->getValueType(i) == MVT::Other) {
-          TheChain = SDValue(Node, i);
-          break;
-        }
-
-      // Otherwise, we walked into a node without a chain.
-      if (TheChain.getValueType() != MVT::Other)
-        return 0;
+  // Visit all the nodes. We start in topological order, so that we see
+  // nodes with their original operands intact. Legalization can produce
+  // new nodes which may themselves need to be legalized. Iterate until all
+  // nodes have been legalized.
+  for (;;) {
+    bool AnyLegalized = false;
+    for (LegalizePosition = DAG.allnodes_end();
+         LegalizePosition != DAG.allnodes_begin(); ) {
+      --LegalizePosition;
+
+      SDNode *N = LegalizePosition;
+      if (LegalizedNodes.insert(N)) {
+        AnyLegalized = true;
+        LegalizeOp(N);
+      }
     }
-  }
-
-  for (SDNode::use_iterator UI = Node->use_begin(),
-       E = Node->use_end(); UI != E; ++UI) {
-
-    // Make sure to only follow users of our token chain.
-    SDNode *User = *UI;
-    for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
-      if (User->getOperand(i) == TheChain)
-        if (SDNode *Result = FindCallEndFromCallStart(User, depth))
-          return Result;
-  }
-  return 0;
-}
-
-/// FindCallStartFromCallEnd - Given a chained node that is part of a call
-/// sequence, find the CALLSEQ_START node that initiates the call sequence.
-static SDNode *FindCallStartFromCallEnd(SDNode *Node) {
-  int nested = 0;
-  assert(Node && "Didn't find callseq_start for a call??");
-  while (Node->getOpcode() != ISD::CALLSEQ_START || nested) {
-    Node = Node->getOperand(0).getNode();
-    assert(Node->getOperand(0).getValueType() == MVT::Other &&
-           "Node doesn't have a token chain argument!");
-    switch (Node->getOpcode()) {
-    default:
+    if (!AnyLegalized)
       break;
-    case ISD::CALLSEQ_START:
-      if (!nested)
-        return Node;
-      nested--;
-      break;
-    case ISD::CALLSEQ_END:
-      nested++;
-      break;
-    }
-  }
-  return 0;
-}
-
-/// LegalizeAllNodesNotLeadingTo - Recursively walk the uses of N, looking to
-/// see if any uses can reach Dest.  If no dest operands can get to dest,
-/// legalize them, legalize ourself, and return false, otherwise, return true.
-///
-/// Keep track of the nodes we fine that actually do lead to Dest in
-/// NodesLeadingTo.  This avoids retraversing them exponential number of times.
-///
-bool SelectionDAGLegalize::LegalizeAllNodesNotLeadingTo(SDNode *N, SDNode *Dest,
-                                     SmallPtrSet<SDNode*, 32> &NodesLeadingTo) {
-  if (N == Dest) return true;  // N certainly leads to Dest :)
-
-  // If we've already processed this node and it does lead to Dest, there is no
-  // need to reprocess it.
-  if (NodesLeadingTo.count(N)) return true;
 
-  // If the first result of this node has been already legalized, then it cannot
-  // reach N.
-  if (LegalizedNodes.count(SDValue(N, 0))) return false;
-
-  // Okay, this node has not already been legalized.  Check and legalize all
-  // operands.  If none lead to Dest, then we can legalize this node.
-  bool OperandsLeadToDest = false;
-  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
-    OperandsLeadToDest |=     // If an operand leads to Dest, so do we.
-      LegalizeAllNodesNotLeadingTo(N->getOperand(i).getNode(), Dest,
-                                   NodesLeadingTo);
-
-  if (OperandsLeadToDest) {
-    NodesLeadingTo.insert(N);
-    return true;
   }
 
-  // Okay, this node looks safe, legalize it and return false.
-  LegalizeOp(SDValue(N, 0));
-  return false;
+  // Remove dead nodes now.
+  DAG.RemoveDeadNodes();
 }
 
 /// ExpandConstantFP - Expands the ConstantFP node to an integer constant or
 /// a load from the constant pool.
-static SDValue ExpandConstantFP(ConstantFPSDNode *CFP, bool UseCP,
-                                SelectionDAG &DAG, const TargetLowering &TLI) {
+SDValue
+SelectionDAGLegalize::ExpandConstantFP(ConstantFPSDNode *CFP, bool UseCP) {
   bool Extend = false;
   DebugLoc dl = CFP->getDebugLoc();
 
@@ -369,20 +249,25 @@ static SDValue ExpandConstantFP(ConstantFPSDNode *CFP, bool UseCP,
 
   SDValue CPIdx = DAG.getConstantPool(LLVMC, TLI.getPointerTy());
   unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment();
-  if (Extend)
-    return DAG.getExtLoad(ISD::EXTLOAD, dl, OrigVT,
-                          DAG.getEntryNode(),
-                          CPIdx, MachinePointerInfo::getConstantPool(),
-                          VT, false, false, Alignment);
-  return DAG.getLoad(OrigVT, dl, DAG.getEntryNode(), CPIdx,
-                     MachinePointerInfo::getConstantPool(), false, false,
-                     Alignment);
+  if (Extend) {
+    SDValue Result =
+      DAG.getExtLoad(ISD::EXTLOAD, dl, OrigVT,
+                     DAG.getEntryNode(),
+                     CPIdx, MachinePointerInfo::getConstantPool(),
+                     VT, false, false, Alignment);
+    return Result;
+  }
+  SDValue Result =
+    DAG.getLoad(OrigVT, dl, DAG.getEntryNode(), CPIdx,
+                MachinePointerInfo::getConstantPool(), false, false,
+                Alignment);
+  return Result;
 }
 
 /// ExpandUnalignedStore - Expands an unaligned store to 2 half-size stores.
-static
-SDValue ExpandUnalignedStore(StoreSDNode *ST, SelectionDAG &DAG,
-                             const TargetLowering &TLI) {
+static void ExpandUnalignedStore(StoreSDNode *ST, SelectionDAG &DAG,
+                                 const TargetLowering &TLI,
+                                 SelectionDAG::DAGUpdateListener *DUL) {
   SDValue Chain = ST->getChain();
   SDValue Ptr = ST->getBasePtr();
   SDValue Val = ST->getValue();
@@ -397,8 +282,10 @@ SDValue ExpandUnalignedStore(StoreSDNode *ST, SelectionDAG &DAG,
       // same size, then a (misaligned) int store.
       // FIXME: Does not handle truncating floating point stores!
       SDValue Result = DAG.getNode(ISD::BITCAST, dl, intVT, Val);
-      return DAG.getStore(Chain, dl, Result, Ptr, ST->getPointerInfo(),
-                          ST->isVolatile(), ST->isNonTemporal(), Alignment);
+      Result = DAG.getStore(Chain, dl, Result, Ptr, ST->getPointerInfo(),
+                           ST->isVolatile(), ST->isNonTemporal(), Alignment);
+      DAG.ReplaceAllUsesWith(SDValue(ST, 0), Result, DUL);
+      return;
     }
     // Do a (aligned) store to a stack slot, then copy from the stack slot
     // to the final destination using (unaligned) integer loads and stores.
@@ -458,8 +345,11 @@ SDValue ExpandUnalignedStore(StoreSDNode *ST, SelectionDAG &DAG,
                                        ST->isNonTemporal(),
                                        MinAlign(ST->getAlignment(), Offset)));
     // The order of the stores doesn't matter - say it with a TokenFactor.
-    return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, &Stores[0],
-                       Stores.size());
+    SDValue Result =
+      DAG.getNode(ISD::TokenFactor, dl, MVT::Other, &Stores[0],
+                  Stores.size());
+    DAG.ReplaceAllUsesWith(SDValue(ST, 0), Result, DUL);
+    return;
   }
   assert(ST->getMemoryVT().isInteger() &&
          !ST->getMemoryVT().isVector() &&
@@ -488,13 +378,16 @@ SDValue ExpandUnalignedStore(StoreSDNode *ST, SelectionDAG &DAG,
                              NewStoredVT, ST->isVolatile(), ST->isNonTemporal(),
                              Alignment);
 
-  return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Store1, Store2);
+  SDValue Result =
+    DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Store1, Store2);
+  DAG.ReplaceAllUsesWith(SDValue(ST, 0), Result, DUL);
 }
 
 /// ExpandUnalignedLoad - Expands an unaligned load to 2 half-size loads.
-static
-SDValue ExpandUnalignedLoad(LoadSDNode *LD, SelectionDAG &DAG,
-                            const TargetLowering &TLI) {
+static void
+ExpandUnalignedLoad(LoadSDNode *LD, SelectionDAG &DAG,
+                    const TargetLowering &TLI,
+                    SDValue &ValResult, SDValue &ChainResult) {
   SDValue Chain = LD->getChain();
   SDValue Ptr = LD->getBasePtr();
   EVT VT = LD->getValueType(0);
@@ -512,8 +405,9 @@ SDValue ExpandUnalignedLoad(LoadSDNode *LD, SelectionDAG &DAG,
       if (VT.isFloatingPoint() && LoadedVT != VT)
         Result = DAG.getNode(ISD::FP_EXTEND, dl, VT, Result);
 
-      SDValue Ops[] = { Result, Chain };
-      return DAG.getMergeValues(Ops, 2, dl);
+      ValResult = Result;
+      ChainResult = Chain;
+      return;
     }
 
     // Copy the value to a (aligned) stack slot using (unaligned) integer
@@ -572,8 +466,9 @@ SDValue ExpandUnalignedLoad(LoadSDNode *LD, SelectionDAG &DAG,
                           MachinePointerInfo(), LoadedVT, false, false, 0);
 
     // Callers expect a MERGE_VALUES node.
-    SDValue Ops[] = { Load, TF };
-    return DAG.getMergeValues(Ops, 2, dl);
+    ValResult = Load;
+    ChainResult = TF;
+    return;
   }
   assert(LoadedVT.isInteger() && !LoadedVT.isVector() &&
          "Unaligned load of unsupported type.");
@@ -626,8 +521,8 @@ SDValue ExpandUnalignedLoad(LoadSDNode *LD, SelectionDAG &DAG,
   SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
                              Hi.getValue(1));
 
-  SDValue Ops[] = { Result, TF };
-  return DAG.getMergeValues(Ops, 2, dl);
+  ValResult = Result;
+  ChainResult = TF;
 }
 
 /// PerformInsertVectorEltInMemory - Some target cannot handle a variable
@@ -763,11 +658,10 @@ SDValue SelectionDAGLegalize::OptimizeFloatStore(StoreSDNode* ST) {
 
 /// LegalizeOp - Return a legal replacement for the given operation, with
 /// all legal operands.
-SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
-  if (Op.getOpcode() == ISD::TargetConstant) // Allow illegal target nodes.
-    return Op;
+void SelectionDAGLegalize::LegalizeOp(SDNode *Node) {
+  if (Node->getOpcode() == ISD::TargetConstant) // Allow illegal target nodes.
+    return;
 
-  SDNode *Node = Op.getNode();
   DebugLoc dl = Node->getDebugLoc();
 
   for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
@@ -782,13 +676,7 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
             Node->getOperand(i).getOpcode() == ISD::TargetConstant) &&
            "Unexpected illegal type!");
 
-  // Note that LegalizeOp may be reentered even from single-use nodes, which
-  // means that we always must cache transformed nodes.
-  DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op);
-  if (I != LegalizedNodes.end()) return I->second;
-
   SDValue Tmp1, Tmp2, Tmp3, Tmp4;
-  SDValue Result = Op;
   bool isCustom = false;
 
   // Figure out the correct action; the way to query this varies by opcode
@@ -882,17 +770,6 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
     if (Action == TargetLowering::Legal)
       Action = TargetLowering::Custom;
     break;
-  case ISD::BUILD_VECTOR:
-    // A weird case: legalization for BUILD_VECTOR never legalizes the
-    // operands!
-    // FIXME: This really sucks... changing it isn't semantically incorrect,
-    // but it massively pessimizes the code for floating-point BUILD_VECTORs
-    // because ConstantFP operands get legalized into constant pool loads
-    // before the BUILD_VECTOR code can see them.  It doesn't usually bite,
-    // though, because BUILD_VECTORS usually get lowered into other nodes
-    // which get legalized properly.
-    SimpleFinishLegalizing = false;
-    break;
   default:
     if (Node->getOpcode() >= ISD::BUILTIN_OP_END) {
       Action = TargetLowering::Legal;
@@ -903,22 +780,11 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
   }
 
   if (SimpleFinishLegalizing) {
-    SmallVector<SDValue, 8> Ops, ResultVals;
+    SmallVector<SDValue, 8> Ops;
     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
-      Ops.push_back(LegalizeOp(Node->getOperand(i)));
+      Ops.push_back(Node->getOperand(i));
     switch (Node->getOpcode()) {
     default: break;
-    case ISD::BR:
-    case ISD::BRIND:
-    case ISD::BR_JT:
-    case ISD::BR_CC:
-    case ISD::BRCOND:
-      // Branches tweak the chain to include LastCALLSEQ_END
-      Ops[0] = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Ops[0],
-                           LastCALLSEQ_END);
-      Ops[0] = LegalizeOp(Ops[0]);
-      LastCALLSEQ_END = DAG.getEntryNode();
-      break;
     case ISD::SHL:
     case ISD::SRL:
     case ISD::SRA:
@@ -926,57 +792,66 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
     case ISD::ROTR:
       // Legalizing shifts/rotates requires adjusting the shift amount
       // to the appropriate width.
-      if (!Ops[1].getValueType().isVector())
-        Ops[1] = LegalizeOp(DAG.getShiftAmountOperand(Ops[0].getValueType(),
-                                                      Ops[1]));
+      if (!Ops[1].getValueType().isVector()) {
+        SDValue SAO = DAG.getShiftAmountOperand(Ops[0].getValueType(), Ops[1]);
+        HandleSDNode Handle(SAO);
+        LegalizeOp(SAO.getNode());
+        Ops[1] = Handle.getValue();
+      }
       break;
     case ISD::SRL_PARTS:
     case ISD::SRA_PARTS:
     case ISD::SHL_PARTS:
       // Legalizing shifts/rotates requires adjusting the shift amount
       // to the appropriate width.
-      if (!Ops[2].getValueType().isVector())
-        Ops[2] = LegalizeOp(DAG.getShiftAmountOperand(Ops[0].getValueType(),
-                                                      Ops[2]));
+      if (!Ops[2].getValueType().isVector()) {
+        SDValue SAO = DAG.getShiftAmountOperand(Ops[0].getValueType(), Ops[2]);
+        HandleSDNode Handle(SAO);
+        LegalizeOp(SAO.getNode());
+        Ops[2] = Handle.getValue();
+      }
       break;
     }
 
-    Result = SDValue(DAG.UpdateNodeOperands(Result.getNode(), Ops.data(),
-                                            Ops.size()), 0);
+    SDNode *NewNode = DAG.UpdateNodeOperands(Node, Ops.data(), Ops.size());
+    if (NewNode != Node) {
+      DAG.ReplaceAllUsesWith(Node, NewNode, this);
+      for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
+        DAG.TransferDbgValues(SDValue(Node, i), SDValue(NewNode, i));
+      DAG.RemoveDeadNode(Node, this);
+      Node = NewNode;
+    }
     switch (Action) {
     case TargetLowering::Legal:
-      for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
-        ResultVals.push_back(Result.getValue(i));
-      break;
+      return;
     case TargetLowering::Custom:
       // FIXME: The handling for custom lowering with multiple results is
       // a complete mess.
-      Tmp1 = TLI.LowerOperation(Result, DAG);
+      Tmp1 = TLI.LowerOperation(SDValue(Node, 0), DAG);
       if (Tmp1.getNode()) {
+        SmallVector<SDValue, 8> ResultVals;
         for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) {
           if (e == 1)
             ResultVals.push_back(Tmp1);
           else
             ResultVals.push_back(Tmp1.getValue(i));
         }
-        break;
+        if (Tmp1.getNode() != Node || Tmp1.getResNo() != 0) {
+          DAG.ReplaceAllUsesWith(Node, ResultVals.data(), this);
+          for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
+            DAG.TransferDbgValues(SDValue(Node, i), ResultVals[i]);
+          DAG.RemoveDeadNode(Node, this);
+        }
+        return;
       }
 
       // FALL THROUGH
     case TargetLowering::Expand:
-      ExpandNode(Result.getNode(), ResultVals);
-      break;
+      ExpandNode(Node);
+      return;
     case TargetLowering::Promote:
-      PromoteNode(Result.getNode(), ResultVals);
-      break;
-    }
-    if (!ResultVals.empty()) {
-      for (unsigned i = 0, e = ResultVals.size(); i != e; ++i) {
-        if (ResultVals[i] != SDValue(Node, i))
-          ResultVals[i] = LegalizeOp(ResultVals[i]);
-        AddLegalizedOperand(SDValue(Node, i), ResultVals[i]);
-      }
-      return ResultVals[Op.getResNo()];
+      PromoteNode(Node);
+      return;
     }
   }
 
@@ -989,155 +864,20 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
 #endif
     assert(0 && "Do not know how to legalize this operator!");
 
-  case ISD::SRA:
-  case ISD::SRL:
-  case ISD::SHL: {
-    // Scalarize vector SRA/SRL/SHL.
-    EVT VT = Node->getValueType(0);
-    assert(VT.isVector() && "Unable to legalize non-vector shift");
-    assert(TLI.isTypeLegal(VT.getScalarType())&& "Element type must be legal");
-    unsigned NumElem = VT.getVectorNumElements();
-
-    SmallVector<SDValue, 8> Scalars;
-    for (unsigned Idx = 0; Idx < NumElem; Idx++) {
-      SDValue Ex = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
-                               VT.getScalarType(),
-                               Node->getOperand(0), DAG.getIntPtrConstant(Idx));
-      SDValue Sh = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
-                               VT.getScalarType(),
-                               Node->getOperand(1), DAG.getIntPtrConstant(Idx));
-      Scalars.push_back(DAG.getNode(Node->getOpcode(), dl,
-                                    VT.getScalarType(), Ex, Sh));
-    }
-    Result = DAG.getNode(ISD::BUILD_VECTOR, dl, Node->getValueType(0),
-                         &Scalars[0], Scalars.size());
-    break;
-  }
-
-  case ISD::BUILD_VECTOR:
-    switch (TLI.getOperationAction(ISD::BUILD_VECTOR, Node->getValueType(0))) {
-    default: assert(0 && "This action is not supported yet!");
-    case TargetLowering::Custom:
-      Tmp3 = TLI.LowerOperation(Result, DAG);
-      if (Tmp3.getNode()) {
-        Result = Tmp3;
-        break;
-      }
-      // FALLTHROUGH
-    case TargetLowering::Expand:
-      Result = ExpandBUILD_VECTOR(Result.getNode());
-      break;
-    }
-    break;
-  case ISD::CALLSEQ_START: {
-    SDNode *CallEnd = FindCallEndFromCallStart(Node);
-
-    // Recursively Legalize all of the inputs of the call end that do not lead
-    // to this call start.  This ensures that any libcalls that need be inserted
-    // are inserted *before* the CALLSEQ_START.
-    {SmallPtrSet<SDNode*, 32> NodesLeadingTo;
-    for (unsigned i = 0, e = CallEnd->getNumOperands(); i != e; ++i)
-      LegalizeAllNodesNotLeadingTo(CallEnd->getOperand(i).getNode(), Node,
-                                   NodesLeadingTo);
-    }
-
-    // Now that we have legalized all of the inputs (which may have inserted
-    // libcalls), create the new CALLSEQ_START node.
-    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
-
-    // Merge in the last call to ensure that this call starts after the last
-    // call ended.
-    if (LastCALLSEQ_END.getOpcode() != ISD::EntryToken) {
-      Tmp1 = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
-                         Tmp1, LastCALLSEQ_END);
-      Tmp1 = LegalizeOp(Tmp1);
-    }
-
-    // Do not try to legalize the target-specific arguments (#1+).
-    if (Tmp1 != Node->getOperand(0)) {
-      SmallVector<SDValue, 8> Ops(Node->op_begin(), Node->op_end());
-      Ops[0] = Tmp1;
-      Result = SDValue(DAG.UpdateNodeOperands(Result.getNode(), &Ops[0],
-                                              Ops.size()), Result.getResNo());
-    }
-
-    // Remember that the CALLSEQ_START is legalized.
-    AddLegalizedOperand(Op.getValue(0), Result);
-    if (Node->getNumValues() == 2)    // If this has a flag result, remember it.
-      AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
-
-    // Now that the callseq_start and all of the non-call nodes above this call
-    // sequence have been legalized, legalize the call itself.  During this
-    // process, no libcalls can/will be inserted, guaranteeing that no calls
-    // can overlap.
-    assert(!IsLegalizingCall && "Inconsistent sequentialization of calls!");
-    // Note that we are selecting this call!
-    LastCALLSEQ_END = SDValue(CallEnd, 0);
-    IsLegalizingCall = true;
-
-    // Legalize the call, starting from the CALLSEQ_END.
-    LegalizeOp(LastCALLSEQ_END);
-    assert(!IsLegalizingCall && "CALLSEQ_END should have cleared this!");
-    return Result;
-  }
+  case ISD::CALLSEQ_START:
   case ISD::CALLSEQ_END:
-    // If the CALLSEQ_START node hasn't been legalized first, legalize it.  This
-    // will cause this node to be legalized as well as handling libcalls right.
-    if (LastCALLSEQ_END.getNode() != Node) {
-      LegalizeOp(SDValue(FindCallStartFromCallEnd(Node), 0));
-      DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op);
-      assert(I != LegalizedNodes.end() &&
-             "Legalizing the call start should have legalized this node!");
-      return I->second;
-    }
-
-    // Otherwise, the call start has been legalized and everything is going
-    // according to plan.  Just legalize ourselves normally here.
-    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
-    // Do not try to legalize the target-specific arguments (#1+), except for
-    // an optional flag input.
-    if (Node->getOperand(Node->getNumOperands()-1).getValueType() != MVT::Glue){
-      if (Tmp1 != Node->getOperand(0)) {
-        SmallVector<SDValue, 8> Ops(Node->op_begin(), Node->op_end());
-        Ops[0] = Tmp1;
-        Result = SDValue(DAG.UpdateNodeOperands(Result.getNode(),
-                                                &Ops[0], Ops.size()),
-                         Result.getResNo());
-      }
-    } else {
-      Tmp2 = LegalizeOp(Node->getOperand(Node->getNumOperands()-1));
-      if (Tmp1 != Node->getOperand(0) ||
-          Tmp2 != Node->getOperand(Node->getNumOperands()-1)) {
-        SmallVector<SDValue, 8> Ops(Node->op_begin(), Node->op_end());
-        Ops[0] = Tmp1;
-        Ops.back() = Tmp2;
-        Result = SDValue(DAG.UpdateNodeOperands(Result.getNode(),
-                                                &Ops[0], Ops.size()),
-                         Result.getResNo());
-      }
-    }
-    assert(IsLegalizingCall && "Call sequence imbalance between start/end?");
-    // This finishes up call legalization.
-    IsLegalizingCall = false;
-
-    // If the CALLSEQ_END node has a flag, remember that we legalized it.
-    AddLegalizedOperand(SDValue(Node, 0), Result.getValue(0));
-    if (Node->getNumValues() == 2)
-      AddLegalizedOperand(SDValue(Node, 1), Result.getValue(1));
-    return Result.getValue(Op.getResNo());
+    break;
   case ISD::LOAD: {
     LoadSDNode *LD = cast<LoadSDNode>(Node);
-    Tmp1 = LegalizeOp(LD->getChain());   // Legalize the chain.
-    Tmp2 = LegalizeOp(LD->getBasePtr()); // Legalize the base pointer.
+    Tmp1 = LD->getChain();   // Legalize the chain.
+    Tmp2 = LD->getBasePtr(); // Legalize the base pointer.
 
     ISD::LoadExtType ExtType = LD->getExtensionType();
     if (ExtType == ISD::NON_EXTLOAD) {
       EVT VT = Node->getValueType(0);
-      Result = SDValue(DAG.UpdateNodeOperands(Result.getNode(),
-                                              Tmp1, Tmp2, LD->getOffset()),
-                       Result.getResNo());
-      Tmp3 = Result.getValue(0);
-      Tmp4 = Result.getValue(1);
+      Node = DAG.UpdateNodeOperands(Node, Tmp1, Tmp2, LD->getOffset());
+      Tmp3 = SDValue(Node, 0);
+      Tmp4 = SDValue(Node, 1);
 
       switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
       default: assert(0 && "This action is not supported yet!");
@@ -1148,20 +888,16 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
           Type *Ty = LD->getMemoryVT().getTypeForEVT(*DAG.getContext());
           unsigned ABIAlignment = TLI.getTargetData()->getABITypeAlignment(Ty);
           if (LD->getAlignment() < ABIAlignment){
-            Result = ExpandUnalignedLoad(cast<LoadSDNode>(Result.getNode()),
-                                         DAG, TLI);
-            Tmp3 = Result.getOperand(0);
-            Tmp4 = Result.getOperand(1);
-            Tmp3 = LegalizeOp(Tmp3);
-            Tmp4 = LegalizeOp(Tmp4);
+            ExpandUnalignedLoad(cast<LoadSDNode>(Node),
+                                DAG, TLI, Tmp3, Tmp4);
           }
         }
         break;
       case TargetLowering::Custom:
         Tmp1 = TLI.LowerOperation(Tmp3, DAG);
         if (Tmp1.getNode()) {
-          Tmp3 = LegalizeOp(Tmp1);
-          Tmp4 = LegalizeOp(Tmp1.getValue(1));
+          Tmp3 = Tmp1;
+          Tmp4 = Tmp1.getValue(1);
         }
         break;
       case TargetLowering::Promote: {
@@ -1173,16 +909,16 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
         Tmp1 = DAG.getLoad(NVT, dl, Tmp1, Tmp2, LD->getPointerInfo(),
                            LD->isVolatile(), LD->isNonTemporal(),
                            LD->getAlignment());
-        Tmp3 = LegalizeOp(DAG.getNode(ISD::BITCAST, dl, VT, Tmp1));
-        Tmp4 = LegalizeOp(Tmp1.getValue(1));
+        Tmp3 = DAG.getNode(ISD::BITCAST, dl, VT, Tmp1);
+        Tmp4 = Tmp1.getValue(1);
         break;
       }
       }
       // Since loads produce two values, make sure to remember that we
       // legalized both of them.
-      AddLegalizedOperand(SDValue(Node, 0), Tmp3);
-      AddLegalizedOperand(SDValue(Node, 1), Tmp4);
-      return Op.getResNo() ? Tmp4 : Tmp3;
+      DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 0), Tmp3);
+      DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 1), Tmp4);
+      return;
     }
 
     EVT SrcVT = LD->getMemoryVT();
@@ -1213,9 +949,10 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
       ISD::LoadExtType NewExtType =
         ExtType == ISD::ZEXTLOAD ? ISD::ZEXTLOAD : ISD::EXTLOAD;
 
-      Result = DAG.getExtLoad(NewExtType, dl, Node->getValueType(0),
-                              Tmp1, Tmp2, LD->getPointerInfo(),
-                              NVT, isVolatile, isNonTemporal, Alignment);
+      SDValue Result =
+        DAG.getExtLoad(NewExtType, dl, Node->getValueType(0),
+                       Tmp1, Tmp2, LD->getPointerInfo(),
+                       NVT, isVolatile, isNonTemporal, Alignment);
 
       Ch = Result.getValue(1); // The chain.
 
@@ -1230,8 +967,8 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
                              Result.getValueType(), Result,
                              DAG.getValueType(SrcVT));
 
-      Tmp1 = LegalizeOp(Result);
-      Tmp2 = LegalizeOp(Ch);
+      Tmp1 = Result;
+      Tmp2 = Ch;
     } else if (SrcWidth & (SrcWidth - 1)) {
       // If not loading a power-of-2 number of bits, expand as two loads.
       assert(!SrcVT.isVector() && "Unsupported extload!");
@@ -1274,7 +1011,7 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
                                       TLI.getShiftAmountTy(Hi.getValueType())));
 
         // Join the hi and lo parts.
-        Result = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi);
+        Tmp1 = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi);
       } else {
         // Big endian - avoid unaligned loads.
         // EXTLOAD:i24 -> (shl EXTLOAD:i16, 8) | ZEXTLOAD@+2:i8
@@ -1304,11 +1041,10 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
                                       TLI.getShiftAmountTy(Hi.getValueType())));
 
         // Join the hi and lo parts.
-        Result = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi);
+        Tmp1 = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi);
       }
 
-      Tmp1 = LegalizeOp(Result);
-      Tmp2 = LegalizeOp(Ch);
+      Tmp2 = Ch;
     } else {
       switch (TLI.getLoadExtAction(ExtType, SrcVT)) {
       default: assert(0 && "This action is not supported yet!");
@@ -1316,17 +1052,16 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
         isCustom = true;
         // FALLTHROUGH
       case TargetLowering::Legal:
-        Result = SDValue(DAG.UpdateNodeOperands(Result.getNode(),
-                                                Tmp1, Tmp2, LD->getOffset()),
-                         Result.getResNo());
-        Tmp1 = Result.getValue(0);
-        Tmp2 = Result.getValue(1);
+        Node = DAG.UpdateNodeOperands(Node,
+                                      Tmp1, Tmp2, LD->getOffset());
+        Tmp1 = SDValue(Node, 0);
+        Tmp2 = SDValue(Node, 1);
 
         if (isCustom) {
-          Tmp3 = TLI.LowerOperation(Result, DAG);
+          Tmp3 = TLI.LowerOperation(SDValue(Node, 0), DAG);
           if (Tmp3.getNode()) {
-            Tmp1 = LegalizeOp(Tmp3);
-            Tmp2 = LegalizeOp(Tmp3.getValue(1));
+            Tmp1 = Tmp3;
+            Tmp2 = Tmp3.getValue(1);
           }
         } else {
           // If this is an unaligned load and the target doesn't support it,
@@ -1337,12 +1072,8 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
             unsigned ABIAlignment =
               TLI.getTargetData()->getABITypeAlignment(Ty);
             if (LD->getAlignment() < ABIAlignment){
-              Result = ExpandUnalignedLoad(cast<LoadSDNode>(Result.getNode()),
-                                           DAG, TLI);
-              Tmp1 = Result.getOperand(0);
-              Tmp2 = Result.getOperand(1);
-              Tmp1 = LegalizeOp(Tmp1);
-              Tmp2 = LegalizeOp(Tmp2);
+              ExpandUnalignedLoad(cast<LoadSDNode>(Node),
+                                  DAG, TLI, Tmp1, Tmp2);
             }
           }
         }
@@ -1363,9 +1094,8 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
           case ISD::ZEXTLOAD: ExtendOp = ISD::ZERO_EXTEND; break;
           default: llvm_unreachable("Unexpected extend load type!");
           }
-          Result = DAG.getNode(ExtendOp, dl, Node->getValueType(0), Load);
-          Tmp1 = LegalizeOp(Result);  // Relegalize new nodes.
-          Tmp2 = LegalizeOp(Load.getValue(1));
+          Tmp1 = DAG.getNode(ExtendOp, dl, Node->getValueType(0), Load);
+          Tmp2 = Load.getValue(1);
           break;
         }
 
@@ -1380,10 +1110,10 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
                "EXTLOAD should always be supported!");
         // Turn the unsupported load into an EXTLOAD followed by an explicit
         // zero/sign extend inreg.
-        Result = DAG.getExtLoad(ISD::EXTLOAD, dl, Node->getValueType(0),
-                                Tmp1, Tmp2, LD->getPointerInfo(), SrcVT,
-                                LD->isVolatile(), LD->isNonTemporal(),
-                                LD->getAlignment());
+        SDValue Result = DAG.getExtLoad(ISD::EXTLOAD, dl, Node->getValueType(0),
+                                        Tmp1, Tmp2, LD->getPointerInfo(), SrcVT,
+                                        LD->isVolatile(), LD->isNonTemporal(),
+                                        LD->getAlignment());
         SDValue ValRes;
         if (ExtType == ISD::SEXTLOAD)
           ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl,
@@ -1391,38 +1121,37 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
                                Result, DAG.getValueType(SrcVT));
         else
           ValRes = DAG.getZeroExtendInReg(Result, dl, SrcVT.getScalarType());
-        Tmp1 = LegalizeOp(ValRes);  // Relegalize new nodes.
-        Tmp2 = LegalizeOp(Result.getValue(1));  // Relegalize new nodes.
+        Tmp1 = ValRes;
+        Tmp2 = Result.getValue(1);
         break;
       }
     }
 
     // Since loads produce two values, make sure to remember that we legalized
     // both of them.
-    AddLegalizedOperand(SDValue(Node, 0), Tmp1);
-    AddLegalizedOperand(SDValue(Node, 1), Tmp2);
-    return Op.getResNo() ? Tmp2 : Tmp1;
+    DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 0), Tmp1);
+    DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 1), Tmp2);
+    break;
   }
   case ISD::STORE: {
     StoreSDNode *ST = cast<StoreSDNode>(Node);
-    Tmp1 = LegalizeOp(ST->getChain());    // Legalize the chain.
-    Tmp2 = LegalizeOp(ST->getBasePtr());  // Legalize the pointer.
+    Tmp1 = ST->getChain();
+    Tmp2 = ST->getBasePtr();
     unsigned Alignment = ST->getAlignment();
     bool isVolatile = ST->isVolatile();
     bool isNonTemporal = ST->isNonTemporal();
 
     if (!ST->isTruncatingStore()) {
       if (SDNode *OptStore = OptimizeFloatStore(ST).getNode()) {
-        Result = SDValue(OptStore, 0);
+        DAG.ReplaceAllUsesWith(ST, OptStore, this);
         break;
       }
 
       {
-        Tmp3 = LegalizeOp(ST->getValue());
-        Result = SDValue(DAG.UpdateNodeOperands(Result.getNode(),
-                                                Tmp1, Tmp3, Tmp2,
-                                                ST->getOffset()),
-                         Result.getResNo());
+        Tmp3 = ST->getValue();
+        Node = DAG.UpdateNodeOperands(Node,
+                                      Tmp1, Tmp3, Tmp2,
+                                      ST->getOffset());
 
         EVT VT = Tmp3.getValueType();
         switch (TLI.getOperationAction(ISD::STORE, VT)) {
@@ -1434,27 +1163,31 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
             Type *Ty = ST->getMemoryVT().getTypeForEVT(*DAG.getContext());
             unsigned ABIAlignment= TLI.getTargetData()->getABITypeAlignment(Ty);
             if (ST->getAlignment() < ABIAlignment)
-              Result = ExpandUnalignedStore(cast<StoreSDNode>(Result.getNode()),
-                                            DAG, TLI);
+              ExpandUnalignedStore(cast<StoreSDNode>(Node),
+                                   DAG, TLI, this);
           }
           break;
         case TargetLowering::Custom:
-          Tmp1 = TLI.LowerOperation(Result, DAG);
-          if (Tmp1.getNode()) Result = Tmp1;
+          Tmp1 = TLI.LowerOperation(SDValue(Node, 0), DAG);
+          if (Tmp1.getNode())
+            DAG.ReplaceAllUsesWith(SDValue(Node, 0), Tmp1, this);
           break;
-        case TargetLowering::Promote:
+        case TargetLowering::Promote: {
           assert(VT.isVector() && "Unknown legal promote case!");
           Tmp3 = DAG.getNode(ISD::BITCAST, dl,
                              TLI.getTypeToPromoteTo(ISD::STORE, VT), Tmp3);
-          Result = DAG.getStore(Tmp1, dl, Tmp3, Tmp2,
-                                ST->getPointerInfo(), isVolatile,
-                                isNonTemporal, Alignment);
+          SDValue Result =
+            DAG.getStore(Tmp1, dl, Tmp3, Tmp2,
+                         ST->getPointerInfo(), isVolatile,
+                         isNonTemporal, Alignment);
+          DAG.ReplaceAllUsesWith(SDValue(Node, 0), Result, this);
           break;
         }
+        }
         break;
       }
     } else {
-      Tmp3 = LegalizeOp(ST->getValue());
+      Tmp3 = ST->getValue();
 
       EVT StVT = ST->getMemoryVT();
       unsigned StWidth = StVT.getSizeInBits();
@@ -1466,8 +1199,10 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
         EVT NVT = EVT::getIntegerVT(*DAG.getContext(),
                                     StVT.getStoreSizeInBits());
         Tmp3 = DAG.getZeroExtendInReg(Tmp3, dl, StVT);
-        Result = DAG.getTruncStore(Tmp1, dl, Tmp3, Tmp2, ST->getPointerInfo(),
-                                   NVT, isVolatile, isNonTemporal, Alignment);
+        SDValue Result =
+          DAG.getTruncStore(Tmp1, dl, Tmp3, Tmp2, ST->getPointerInfo(),
+                            NVT, isVolatile, isNonTemporal, Alignment);
+        DAG.ReplaceAllUsesWith(SDValue(Node, 0), Result, this);
       } else if (StWidth & (StWidth - 1)) {
         // If not storing a power-of-2 number of bits, expand as two stores.
         assert(!StVT.isVector() && "Unsupported truncstore!");
@@ -1521,14 +1256,13 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
         }
 
         // The order of the stores doesn't matter.
-        Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
+        SDValue Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
+        DAG.ReplaceAllUsesWith(SDValue(Node, 0), Result, this);
       } else {
         if (Tmp1 != ST->getChain() || Tmp3 != ST->getValue() ||
             Tmp2 != ST->getBasePtr())
-          Result = SDValue(DAG.UpdateNodeOperands(Result.getNode(),
-                                                  Tmp1, Tmp3, Tmp2,
-                                                  ST->getOffset()),
-                           Result.getResNo());
+          Node = DAG.UpdateNodeOperands(Node, Tmp1, Tmp3, Tmp2,
+                                        ST->getOffset());
 
         switch (TLI.getTruncStoreAction(ST->getValue().getValueType(), StVT)) {
         default: assert(0 && "This action is not supported yet!");
@@ -1539,12 +1273,13 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
             Type *Ty = ST->getMemoryVT().getTypeForEVT(*DAG.getContext());
             unsigned ABIAlignment= TLI.getTargetData()->getABITypeAlignment(Ty);
             if (ST->getAlignment() < ABIAlignment)
-              Result = ExpandUnalignedStore(cast<StoreSDNode>(Result.getNode()),
-                                            DAG, TLI);
+              ExpandUnalignedStore(cast<StoreSDNode>(Node), DAG, TLI, this);
           }
           break;
         case TargetLowering::Custom:
-          Result = TLI.LowerOperation(Result, DAG);
+          DAG.ReplaceAllUsesWith(SDValue(Node, 0),
+                                 TLI.LowerOperation(SDValue(Node, 0), DAG),
+                                 this);
           break;
         case TargetLowering::Expand:
           assert(!StVT.isVector() &&
@@ -1553,8 +1288,10 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
           // TRUNCSTORE:i16 i32 -> STORE i16
           assert(TLI.isTypeLegal(StVT) && "Do not know how to expand this store!");
           Tmp3 = DAG.getNode(ISD::TRUNCATE, dl, StVT, Tmp3);
-          Result = DAG.getStore(Tmp1, dl, Tmp3, Tmp2, ST->getPointerInfo(),
-                                isVolatile, isNonTemporal, Alignment);
+          SDValue Result =
+            DAG.getStore(Tmp1, dl, Tmp3, Tmp2, ST->getPointerInfo(),
+                         isVolatile, isNonTemporal, Alignment);
+          DAG.ReplaceAllUsesWith(SDValue(Node, 0), Result, this);
           break;
         }
       }
@@ -1562,17 +1299,6 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
     break;
   }
   }
-  assert(Result.getValueType() == Op.getValueType() &&
-         "Bad legalization!");
-
-  // Make sure that the generated code is itself legal.
-  if (Result != Op)
-    Result = LegalizeOp(Result);
-
-  // Note that LegalizeOp may be reentered even from single-use nodes, which
-  // means that we always must cache transformed nodes.
-  AddLegalizedOperand(Op, Result);
-  return Result;
 }
 
 SDValue SelectionDAGLegalize::ExpandExtractFromVectorThroughStack(SDValue Op) {
@@ -2011,7 +1737,6 @@ SDValue SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
 // and leave the Hi part unset.
 SDValue SelectionDAGLegalize::ExpandLibCall(RTLIB::Libcall LC, SDNode *Node,
                                             bool isSigned) {
-  assert(!IsLegalizingCall && "Cannot overlap legalization of calls!");
   // The input chain to this libcall is the entry node of the function.
   // Legalizing the call will automatically add the previous call to the
   // dependence.
@@ -2030,7 +1755,6 @@ SDValue SelectionDAGLegalize::ExpandLibCall(RTLIB::Libcall LC, SDNode *Node,
   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
                                          TLI.getPointerTy());
 
-  // Splice the libcall in wherever FindInputOutputChains tells us to.
   Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext());
 
   // isTailCall may be true since the callee does not reference caller stack
@@ -2046,10 +1770,6 @@ SDValue SelectionDAGLegalize::ExpandLibCall(RTLIB::Libcall LC, SDNode *Node,
     // It's a tailcall, return the chain (which is the DAG root).
     return DAG.getRoot();
 
-  // Legalize the call sequence, starting with the chain.  This will advance
-  // the LastCALLSEQ_END to the legalized version of the CALLSEQ_END node that
-  // was added by LowerCallTo (guaranteeing proper serialization of calls).
-  LegalizeOp(CallInfo.second);
   return CallInfo.first;
 }
 
@@ -2079,11 +1799,6 @@ SDValue SelectionDAGLegalize::ExpandLibCall(RTLIB::Libcall LC, EVT RetVT,
                   /*isReturnValueUsed=*/true,
                   Callee, Args, DAG, dl);
 
-  // Legalize the call sequence, starting with the chain.  This will advance
-  // the LastCALLSEQ_END to the legalized version of the CALLSEQ_END node that
-  // was added by LowerCallTo (guaranteeing proper serialization of calls).
-  LegalizeOp(CallInfo.second);
-
   return CallInfo.first;
 }
 
@@ -2093,7 +1808,6 @@ std::pair<SDValue, SDValue>
 SelectionDAGLegalize::ExpandChainLibCall(RTLIB::Libcall LC,
                                          SDNode *Node,
                                          bool isSigned) {
-  assert(!IsLegalizingCall && "Cannot overlap legalization of calls!");
   SDValue InChain = Node->getOperand(0);
 
   TargetLowering::ArgListTy Args;
@@ -2110,7 +1824,6 @@ SelectionDAGLegalize::ExpandChainLibCall(RTLIB::Libcall LC,
   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
                                          TLI.getPointerTy());
 
-  // Splice the libcall in wherever FindInputOutputChains tells us to.
   Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext());
   std::pair<SDValue, SDValue> CallInfo =
     TLI.LowerCallTo(InChain, RetTy, isSigned, !isSigned, false, false,
@@ -2118,10 +1831,6 @@ SelectionDAGLegalize::ExpandChainLibCall(RTLIB::Libcall LC,
                     /*isReturnValueUsed=*/true,
                     Callee, Args, DAG, Node->getDebugLoc());
 
-  // Legalize the call sequence, starting with the chain.  This will advance
-  // the LastCALLSEQ_END to the legalized version of the CALLSEQ_END node that
-  // was added by LowerCallTo (guaranteeing proper serialization of calls).
-  LegalizeOp(CallInfo.second);
   return CallInfo;
 }
 
@@ -2247,20 +1956,14 @@ SelectionDAGLegalize::ExpandDivRemLibCall(SDNode *Node,
   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
                                          TLI.getPointerTy());
 
-  // Splice the libcall in wherever FindInputOutputChains tells us to.
   DebugLoc dl = Node->getDebugLoc();
   std::pair<SDValue, SDValue> CallInfo =
     TLI.LowerCallTo(InChain, RetTy, isSigned, !isSigned, false, false,
                     0, TLI.getLibcallCallingConv(LC), /*isTailCall=*/false,
                     /*isReturnValueUsed=*/true, Callee, Args, DAG, dl);
 
-  // Legalize the call sequence, starting with the chain.  This will advance
-  // the LastCALLSEQ to the legalized version of the CALLSEQ_END node that
-  // was added by LowerCallTo (guaranteeing proper serialization of calls).
-  LegalizeOp(CallInfo.second);
-
   // Remainder is loaded back from the stack frame.
-  SDValue Rem = DAG.getLoad(RetVT, dl, LastCALLSEQ_END, FIPtr,
+  SDValue Rem = DAG.getLoad(RetVT, dl, CallInfo.second, FIPtr,
                             MachinePointerInfo(), false, false, 0);
   Results.push_back(CallInfo.first);
   Results.push_back(Rem);
@@ -2452,11 +2155,13 @@ SDValue SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned,
                              MachinePointerInfo::getConstantPool(),
                              false, false, Alignment);
   else {
-    FudgeInReg =
-      LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, dl, DestVT,
-                                DAG.getEntryNode(), CPIdx,
-                                MachinePointerInfo::getConstantPool(),
-                                MVT::f32, false, false, Alignment));
+    SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, DestVT,
+                                  DAG.getEntryNode(), CPIdx,
+                                  MachinePointerInfo::getConstantPool(),
+                                  MVT::f32, false, false, Alignment);
+    HandleSDNode Handle(Load);
+    LegalizeOp(Load.getNode());
+    FudgeInReg = Handle.getValue();
   }
 
   return DAG.getNode(ISD::FADD, dl, DestVT, Tmp1, FudgeInReg);
@@ -2780,8 +2485,8 @@ std::pair <SDValue, SDValue> SelectionDAGLegalize::ExpandAtomic(SDNode *Node) {
   return ExpandChainLibCall(LC, Node, false);
 }
 
-void SelectionDAGLegalize::ExpandNode(SDNode *Node,
-                                      SmallVectorImpl<SDValue> &Results) {
+void SelectionDAGLegalize::ExpandNode(SDNode *Node) {
+  SmallVector<SDValue, 8> Results;
   DebugLoc dl = Node->getDebugLoc();
   SDValue Tmp1, Tmp2, Tmp3, Tmp4;
   switch (Node->getOpcode()) {
@@ -3229,10 +2934,8 @@ void SelectionDAGLegalize::ExpandNode(SDNode *Node,
     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
     // Check to see if this FP immediate is already legal.
     // If this is a legal constant, turn it into a TargetConstantFP node.
-    if (TLI.isFPImmLegal(CFP->getValueAPF(), Node->getValueType(0)))
-      Results.push_back(SDValue(Node, 0));
-    else
-      Results.push_back(ExpandConstantFP(CFP, true, DAG, TLI));
+    if (!TLI.isFPImmLegal(CFP->getValueAPF(), Node->getValueType(0)))
+      Results.push_back(ExpandConstantFP(CFP, true));
     break;
   }
   case ISD::EHSELECTION: {
@@ -3478,6 +3181,10 @@ void SelectionDAGLegalize::ExpandNode(SDNode *Node,
                                DAG.getIntPtrConstant(0));
       TopHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Ret,
                             DAG.getIntPtrConstant(1));
+      // Ret is a node with an illegal type. Because such things are not
+      // generally permitted during this phase of legalization, delete the
+      // node. The above EXTRACT_ELEMENT nodes should have been folded.
+      DAG.DeleteNode(Ret.getNode());
     }
 
     if (isSigned) {
@@ -3618,7 +3325,6 @@ void SelectionDAGLegalize::ExpandNode(SDNode *Node,
 
     LegalizeSetCCCondCode(TLI.getSetCCResultType(Tmp2.getValueType()),
                           Tmp2, Tmp3, Tmp4, dl);
-    LastCALLSEQ_END = DAG.getEntryNode();
 
     assert(!Tmp3.getNode() && "Can't legalize BR_CC with legal condition!");
     Tmp3 = DAG.getConstant(0, Tmp2.getValueType());
@@ -3628,6 +3334,35 @@ void SelectionDAGLegalize::ExpandNode(SDNode *Node,
     Results.push_back(Tmp1);
     break;
   }
+  case ISD::BUILD_VECTOR:
+    Results.push_back(ExpandBUILD_VECTOR(Node));
+    break;
+  case ISD::SRA:
+  case ISD::SRL:
+  case ISD::SHL: {
+    // Scalarize vector SRA/SRL/SHL.
+    EVT VT = Node->getValueType(0);
+    assert(VT.isVector() && "Unable to legalize non-vector shift");
+    assert(TLI.isTypeLegal(VT.getScalarType())&& "Element type must be legal");
+    unsigned NumElem = VT.getVectorNumElements();
+
+    SmallVector<SDValue, 8> Scalars;
+    for (unsigned Idx = 0; Idx < NumElem; Idx++) {
+      SDValue Ex = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
+                               VT.getScalarType(),
+                               Node->getOperand(0), DAG.getIntPtrConstant(Idx));
+      SDValue Sh = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
+                               VT.getScalarType(),
+                               Node->getOperand(1), DAG.getIntPtrConstant(Idx));
+      Scalars.push_back(DAG.getNode(Node->getOpcode(), dl,
+                                    VT.getScalarType(), Ex, Sh));
+    }
+    SDValue Result =
+      DAG.getNode(ISD::BUILD_VECTOR, dl, Node->getValueType(0),
+                  &Scalars[0], Scalars.size());
+    DAG.ReplaceAllUsesWith(SDValue(Node, 0), Result, this);
+    break;
+  }
   case ISD::GLOBAL_OFFSET_TABLE:
   case ISD::GlobalAddress:
   case ISD::GlobalTLSAddress:
@@ -3638,13 +3373,16 @@ void SelectionDAGLegalize::ExpandNode(SDNode *Node,
   case ISD::INTRINSIC_WO_CHAIN:
   case ISD::INTRINSIC_VOID:
     // FIXME: Custom lowering for these operations shouldn't return null!
-    for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
-      Results.push_back(SDValue(Node, i));
     break;
   }
+
+  // Replace the original node with the legalized result.
+  if (!Results.empty())
+    DAG.ReplaceAllUsesWith(Node, Results.data(), this);
 }
-void SelectionDAGLegalize::PromoteNode(SDNode *Node,
-                                       SmallVectorImpl<SDValue> &Results) {
+
+void SelectionDAGLegalize::PromoteNode(SDNode *Node) {
+  SmallVector<SDValue, 8> Results;
   EVT OVT = Node->getValueType(0);
   if (Node->getOpcode() == ISD::UINT_TO_FP ||
       Node->getOpcode() == ISD::SINT_TO_FP ||
@@ -3772,6 +3510,10 @@ void SelectionDAGLegalize::PromoteNode(SDNode *Node,
     break;
   }
   }
+
+  // Replace the original node with the legalized result.
+  if (!Results.empty())
+    DAG.ReplaceAllUsesWith(Node, Results.data(), this);
 }
 
 // SelectionDAG::Legalize - This is the entry point for the file.
diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
index a4bb577433..7ed1b98f10 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
@@ -1084,7 +1084,6 @@ DAGTypeLegalizer::ExpandChainLibCall(RTLIB::Libcall LC,
   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
                                          TLI.getPointerTy());
 
-  // Splice the libcall in wherever FindInputOutputChains tells us to.
   Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext());
   std::pair<SDValue, SDValue> CallInfo =
     TLI.LowerCallTo(InChain, RetTy, isSigned, !isSigned, false, false,
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index a1abdb4d9b..b8cf9984f1 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -315,8 +315,10 @@ void ScheduleDAGRRList::Schedule() {
   IssueCount = 0;
   MinAvailableCycle = DisableSchedCycles ? 0 : UINT_MAX;
   NumLiveRegs = 0;
-  LiveRegDefs.resize(TRI->getNumRegs(), NULL);
-  LiveRegGens.resize(TRI->getNumRegs(), NULL);
+  // Allocate slots for each physical register, plus one for a special register
+  // to track the virtual resource of a calling sequence.
+  LiveRegDefs.resize(TRI->getNumRegs() + 1, NULL);
+  LiveRegGens.resize(TRI->getNumRegs() + 1, NULL);
 
   // Build the scheduling graph.
   BuildSchedGraph(NULL);
@@ -386,6 +388,90 @@ void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
   }
 }
 
+/// IsChainDependent - Test if Outer is reachable from Inner through
+/// chain dependencies.
+static bool IsChainDependent(SDNode *Outer, SDNode *Inner) {
+  SDNode *N = Outer;
+  for (;;) {
+    if (N == Inner)
+      return true;
+    if (N->getOpcode() == ISD::TokenFactor) {
+      for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
+        if (IsChainDependent(N->getOperand(i).getNode(), Inner))
+          return true;
+      return false;
+    }
+    for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
+      if (N->getOperand(i).getValueType() == MVT::Other) {
+        N = N->getOperand(i).getNode();
+        goto found_chain_operand;
+      }
+    return false;
+  found_chain_operand:;
+    if (N->getOpcode() == ISD::EntryToken)
+      return false;
+  }
+}
+
+/// FindCallSeqStart - Starting from the (lowered) CALLSEQ_END node, locate
+/// the corresponding (lowered) CALLSEQ_BEGIN node.
+///
+/// NestLevel and MaxNested are used in recursion to indcate the current level
+/// of nesting of CALLSEQ_BEGIN and CALLSEQ_END pairs, as well as the maximum
+/// level seen so far.
+///
+/// TODO: It would be better to give CALLSEQ_END an explicit operand to point
+/// to the corresponding CALLSEQ_BEGIN to avoid needing to search for it.
+static SDNode *
+FindCallSeqStart(SDNode *N, unsigned &NestLevel, unsigned &MaxNest,
+                 const TargetInstrInfo *TII) {
+  for (;;) {
+    // For a TokenFactor, examine each operand. There may be multiple ways
+    // to get to the CALLSEQ_BEGIN, but we need to find the path with the
+    // most nesting in order to ensure that we find the corresponding match.
+    if (N->getOpcode() == ISD::TokenFactor) {
+      SDNode *Best = 0;
+      unsigned BestMaxNest = MaxNest;
+      for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
+        unsigned MyNestLevel = NestLevel;
+        unsigned MyMaxNest = MaxNest;
+        if (SDNode *New = FindCallSeqStart(N->getOperand(i).getNode(),
+                                           MyNestLevel, MyMaxNest, TII))
+          if (!Best || (MyMaxNest > BestMaxNest)) {
+            Best = New;
+            BestMaxNest = MyMaxNest;
+          }
+      }
+      assert(Best);
+      MaxNest = BestMaxNest;
+      return Best;
+    }
+    // Check for a lowered CALLSEQ_BEGIN or CALLSEQ_END.
+    if (N->isMachineOpcode()) {
+      if (N->getMachineOpcode() ==
+          (unsigned)TII->getCallFrameDestroyOpcode()) {
+        ++NestLevel;
+        MaxNest = std::max(MaxNest, NestLevel);
+      } else if (N->getMachineOpcode() ==
+                 (unsigned)TII->getCallFrameSetupOpcode()) {
+        --NestLevel;
+        if (NestLevel == 0)
+          return N;
+      }
+    }
+    // Otherwise, find the chain and continue climbing.
+    for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
+      if (N->getOperand(i).getValueType() == MVT::Other) {
+        N = N->getOperand(i).getNode();
+        goto found_chain_operand;
+      }
+    return 0;
+  found_chain_operand:;
+    if (N->getOpcode() == ISD::EntryToken)
+      return 0;
+  }
+}
+
 /// Call ReleasePred for each predecessor, then update register live def/gen.
 /// Always update LiveRegDefs for a register dependence even if the current SU
 /// also defines the register. This effectively create one large live range
@@ -423,6 +509,25 @@ void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU) {
       }
     }
   }
+
+  // If we're scheduling a lowered CALLSEQ_END, find the corresponding CALLSEQ_BEGIN.
+  // Inject an artificial physical register dependence between these nodes, to
+  // prevent other calls from being interscheduled with them.
+  unsigned CallResource = TRI->getNumRegs();
+  if (!LiveRegDefs[CallResource])
+    for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode())
+      if (Node->isMachineOpcode() &&
+          Node->getMachineOpcode() == (unsigned)TII->getCallFrameDestroyOpcode()) {
+        unsigned NestLevel = 0;
+        unsigned MaxNest = 0;
+        SDNode *N = FindCallSeqStart(Node, NestLevel, MaxNest, TII);
+
+        SUnit *Def = &SUnits[N->getNodeId()];
+        ++NumLiveRegs;
+        LiveRegDefs[CallResource] = Def;
+        LiveRegGens[CallResource] = SU;
+        break;
+      }
 }
 
 /// Check to see if any of the pending instructions are ready to issue.  If
@@ -605,6 +710,20 @@ void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU) {
       LiveRegGens[I->getReg()] = NULL;
     }
   }
+  // Release the special call resource dependence, if this is the beginning
+  // of a call.
+  unsigned CallResource = TRI->getNumRegs();
+  if (LiveRegDefs[CallResource] == SU)
+    for (const SDNode *SUNode = SU->getNode(); SUNode;
+         SUNode = SUNode->getGluedNode()) {
+      if (SUNode->isMachineOpcode() &&
+          SUNode->getMachineOpcode() == (unsigned)TII->getCallFrameSetupOpcode()) {
+        assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
+        --NumLiveRegs;
+        LiveRegDefs[CallResource] = NULL;
+        LiveRegGens[CallResource] = NULL;
+      }
+    }
 
   resetVRegCycle(SU);
 
@@ -661,6 +780,33 @@ void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
     }
   }
 
+  // Reclaim the special call resource dependence, if this is the beginning
+  // of a call.
+  unsigned CallResource = TRI->getNumRegs();
+  for (const SDNode *SUNode = SU->getNode(); SUNode;
+       SUNode = SUNode->getGluedNode()) {
+    if (SUNode->isMachineOpcode() &&
+        SUNode->getMachineOpcode() == (unsigned)TII->getCallFrameSetupOpcode()) {
+      ++NumLiveRegs;
+      LiveRegDefs[CallResource] = SU;
+      LiveRegGens[CallResource] = NULL;
+    }
+  }
+
+  // Release the special call resource dependence, if this is the end
+  // of a call.
+  if (LiveRegGens[CallResource] == SU)
+    for (const SDNode *SUNode = SU->getNode(); SUNode;
+         SUNode = SUNode->getGluedNode()) {
+      if (SUNode->isMachineOpcode() &&
+          SUNode->getMachineOpcode() == (unsigned)TII->getCallFrameDestroyOpcode()) {
+        assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
+        --NumLiveRegs;
+        LiveRegDefs[CallResource] = NULL;
+        LiveRegGens[CallResource] = NULL;
+      }
+    }
+
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
     if (I->isAssignedRegDep()) {
@@ -1083,6 +1229,21 @@ DelayForLiveRegsBottomUp(SUnit *SU, SmallVector<unsigned, 4> &LRegs) {
 
     if (!Node->isMachineOpcode())
       continue;
+    // If we're in the middle of scheduling a call, don't begin scheduling
+    // another call. Also, don't allow any physical registers to be live across
+    // the call.
+    if (Node->getMachineOpcode() == (unsigned)TII->getCallFrameDestroyOpcode()) {
+      // Add one here so that we include the special calling-sequence resource.
+      for (unsigned i = 0, e = TRI->getNumRegs() + 1; i != e; ++i)
+        if (LiveRegDefs[i]) {
+          SDNode *Gen = LiveRegGens[i]->getNode();
+          while (SDNode *Glued = Gen->getGluedNode())
+            Gen = Glued;
+          if (!IsChainDependent(Gen, Node) && RegAdded.insert(i))
+            LRegs.push_back(i);
+        }
+      continue;
+    }
     const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());
     if (!MCID.ImplicitDefs)
       continue;
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 07d2db63fa..010a740dc7 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -5290,6 +5290,10 @@ void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To,
     // already exists there, recursively merge the results together.
     AddModifiedNodeToCSEMaps(User, &Listener);
   }
+
+  // If we just RAUW'd the root, take note.
+  if (FromN == getRoot())
+    setRoot(To);
 }
 
 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
@@ -5335,6 +5339,10 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
     // already exists there, recursively merge the results together.
     AddModifiedNodeToCSEMaps(User, &Listener);
   }
+
+  // If we just RAUW'd the root, take note.
+  if (From == getRoot().getNode())
+    setRoot(SDValue(To, getRoot().getResNo()));
 }
 
 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
@@ -5373,6 +5381,10 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
     // already exists there, recursively merge the results together.
     AddModifiedNodeToCSEMaps(User, &Listener);
   }
+
+  // If we just RAUW'd the root, take note.
+  if (From == getRoot().getNode())
+    setRoot(SDValue(To[getRoot().getResNo()]));
 }
 
 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
@@ -5431,6 +5443,10 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
     // already exists there, recursively merge the results together.
     AddModifiedNodeToCSEMaps(User, &Listener);
   }
+
+  // If we just RAUW'd the root, take note.
+  if (From == getRoot())
+    setRoot(To);
 }
 
 namespace {