19 files changed, 699 insertions, 561 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;