X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FSelectionDAG.cpp;h=db315380865225503ccabf052ac10dcf0062ba2c;hb=dddc6291fb5274282a20d5923b50535d456d34a4;hp=bca5e756d457a3a267752336cd0b36f42fafab3c;hpb=507a58ac9b20ddcea2e56a014be26b8f8cc0ecb8;p=oota-llvm.git

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index bca5e756d45..db315380865 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -12,6 +12,7 @@
 //===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/Constants.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/GlobalAlias.h"
 #include "llvm/GlobalVariable.h"
 #include "llvm/Intrinsics.h"
@@ -191,19 +192,15 @@ bool ISD::isScalarToVector(const SDNode *N) {
 
 
 /// isDebugLabel - Return true if the specified node represents a debug
-/// label (i.e. ISD::LABEL or TargetInstrInfo::LABEL node and third operand
-/// is 0).
+/// label (i.e. ISD::DBG_LABEL or TargetInstrInfo::DBG_LABEL node).
 bool ISD::isDebugLabel(const SDNode *N) {
   SDOperand Zero;
-  if (N->getOpcode() == ISD::LABEL)
-    Zero = N->getOperand(2);
-  else if (N->isTargetOpcode() &&
-           N->getTargetOpcode() == TargetInstrInfo::LABEL)
-    // Chain moved to last operand.
-    Zero = N->getOperand(1);
-  else
-    return false;
-  return isa<ConstantSDNode>(Zero) && cast<ConstantSDNode>(Zero)->isNullValue();
+  if (N->getOpcode() == ISD::DBG_LABEL)
+    return true;
+  if (N->isTargetOpcode() &&
+      N->getTargetOpcode() == TargetInstrInfo::DBG_LABEL)
+    return true;
+  return false;
 }
 
 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
@@ -326,16 +323,26 @@ static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
 ///
 static void AddNodeIDOperands(FoldingSetNodeID &ID,
-                              SDOperandPtr Ops, unsigned NumOps) {
+                              const SDOperand *Ops, unsigned NumOps) {
   for (; NumOps; --NumOps, ++Ops) {
     ID.AddPointer(Ops->Val);
     ID.AddInteger(Ops->ResNo);
   }
 }
 
+/// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
+///
+static void AddNodeIDOperands(FoldingSetNodeID &ID,
+                              const SDUse *Ops, unsigned NumOps) {
+  for (; NumOps; --NumOps, ++Ops) {
+    ID.AddPointer(Ops->getSDOperand().Val);
+    ID.AddInteger(Ops->getSDOperand().ResNo);
+  }
+}
+
 static void AddNodeIDNode(FoldingSetNodeID &ID,
                           unsigned short OpC, SDVTList VTList, 
-                          SDOperandPtr OpList, unsigned N) {
+                          const SDOperand *OpList, unsigned N) {
   AddNodeIDOpcode(ID, OpC);
   AddNodeIDValueTypes(ID, VTList);
   AddNodeIDOperands(ID, OpList, N);
@@ -381,6 +388,13 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) {
   case ISD::Register:
     ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
     break;
+  case ISD::DBG_STOPPOINT: {
+    const DbgStopPointSDNode *DSP = cast<DbgStopPointSDNode>(N);
+    ID.AddInteger(DSP->getLine());
+    ID.AddInteger(DSP->getColumn());
+    ID.AddPointer(DSP->getCompileUnit());
+    break;
+  }
   case ISD::SRCVALUE:
     ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
     break;
@@ -430,13 +444,35 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) {
     ID.AddInteger(ST->isVolatile());
     break;
   }
+  case ISD::ATOMIC_CMP_SWAP:
+  case ISD::ATOMIC_LOAD_ADD:
+  case ISD::ATOMIC_SWAP:
+  case ISD::ATOMIC_LOAD_SUB:
+  case ISD::ATOMIC_LOAD_AND:
+  case ISD::ATOMIC_LOAD_OR:
+  case ISD::ATOMIC_LOAD_XOR:
+  case ISD::ATOMIC_LOAD_NAND:
+  case ISD::ATOMIC_LOAD_MIN:
+  case ISD::ATOMIC_LOAD_MAX:
+  case ISD::ATOMIC_LOAD_UMIN:
+  case ISD::ATOMIC_LOAD_UMAX: {
+    AtomicSDNode *AT = cast<AtomicSDNode>(N);
+    ID.AddInteger(AT->getAlignment());
+    ID.AddInteger(AT->isVolatile());
+    break;
   }
+  } // end switch (N->getOpcode())
 }
 
 //===----------------------------------------------------------------------===//
 //                              SelectionDAG Class
 //===----------------------------------------------------------------------===//
 
+inline alist_traits<SDNode, LargestSDNode>::AllocatorType &
+SelectionDAG::getAllocator() {
+  return AllNodes.getTraits().Allocator;
+}
+
 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
 /// SelectionDAG.
 void SelectionDAG::RemoveDeadNodes() {
@@ -451,42 +487,16 @@ void SelectionDAG::RemoveDeadNodes() {
     if (I->use_empty())
       DeadNodes.push_back(I);
 
-  // Process the worklist, deleting the nodes and adding their uses to the
-  // worklist.
-  while (!DeadNodes.empty()) {
-    SDNode *N = DeadNodes.back();
-    DeadNodes.pop_back();
-    
-    // Take the node out of the appropriate CSE map.
-    RemoveNodeFromCSEMaps(N);
-
-    // Next, brutally remove the operand list.  This is safe to do, as there are
-    // no cycles in the graph.
-    for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
-      SDNode *Operand = I->getVal();
-      Operand->removeUser(std::distance(N->op_begin(), I), N);
-      
-      // Now that we removed this operand, see if there are no uses of it left.
-      if (Operand->use_empty())
-        DeadNodes.push_back(Operand);
-    }
-    if (N->OperandsNeedDelete) {
-      delete[] N->OperandList;
-    }
-    N->OperandList = 0;
-    N->NumOperands = 0;
-    
-    // Finally, remove N itself.
-    AllNodes.erase(N);
-  }
+  RemoveDeadNodes(DeadNodes);
   
   // If the root changed (e.g. it was a dead load, update the root).
   setRoot(Dummy.getValue());
 }
 
-void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
-  SmallVector<SDNode*, 16> DeadNodes;
-  DeadNodes.push_back(N);
+/// RemoveDeadNodes - This method deletes the unreachable nodes in the
+/// given list, and any nodes that become unreachable as a result.
+void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
+                                   DAGUpdateListener *UpdateListener) {
 
   // Process the worklist, deleting the nodes and adding their uses to the
   // worklist.
@@ -521,6 +531,12 @@ void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
   }
 }
 
+void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
+  SmallVector<SDNode*, 16> DeadNodes;
+  DeadNodes.push_back(N);
+  RemoveDeadNodes(DeadNodes, UpdateListener);
+}
+
 void SelectionDAG::DeleteNode(SDNode *N) {
   assert(N->use_empty() && "Cannot delete a node that is not dead!");
 
@@ -534,9 +550,6 @@ void SelectionDAG::DeleteNode(SDNode *N) {
 
 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
 
-  // Remove it from the AllNodes list.
-  AllNodes.remove(N);
-    
   // Drop all of the operands and decrement used nodes use counts.
   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
     I->getVal()->removeUser(std::distance(N->op_begin(), I), N);
@@ -546,7 +559,7 @@ void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
   N->OperandList = 0;
   N->NumOperands = 0;
   
-  delete N;
+  AllNodes.erase(N);
 }
 
 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
@@ -557,9 +570,6 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
   bool Erased = false;
   switch (N->getOpcode()) {
   case ISD::HANDLENODE: return;  // noop.
-  case ISD::STRING:
-    Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue());
-    break;
   case ISD::CONDCODE:
     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
            "Cond code doesn't exist!");
@@ -593,7 +603,11 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
   // flag result (which cannot be CSE'd) or is one of the special cases that are
   // not subject to CSE.
   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag &&
-      !N->isTargetOpcode()) {
+      !N->isTargetOpcode() &&
+      N->getOpcode() != ISD::DBG_LABEL &&
+      N->getOpcode() != ISD::DBG_STOPPOINT &&
+      N->getOpcode() != ISD::EH_LABEL &&
+      N->getOpcode() != ISD::DECLARE) {
     N->dump(this);
     cerr << "\n";
     assert(0 && "Node is not in map!");
@@ -608,8 +622,19 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
 ///
 SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
   assert(N->getNumOperands() && "This is a leaf node!");
-  if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
+
+  if (N->getValueType(0) == MVT::Flag)
+    return 0;   // Never CSE anything that produces a flag.
+
+  switch (N->getOpcode()) {
+  default: break;
+  case ISD::HANDLENODE:
+  case ISD::DBG_LABEL:
+  case ISD::DBG_STOPPOINT:
+  case ISD::EH_LABEL:
+  case ISD::DECLARE:
     return 0;    // Never add these nodes.
+  }
   
   // Check that remaining values produced are not flags.
   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
@@ -627,8 +652,17 @@ SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
 /// node already exists with these operands, the slot will be non-null.
 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op,
                                            void *&InsertPos) {
-  if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
+  if (N->getValueType(0) == MVT::Flag)
+    return 0;   // Never CSE anything that produces a flag.
+
+  switch (N->getOpcode()) {
+  default: break;
+  case ISD::HANDLENODE:
+  case ISD::DBG_LABEL:
+  case ISD::DBG_STOPPOINT:
+  case ISD::EH_LABEL:
     return 0;    // Never add these nodes.
+  }
   
   // Check that remaining values produced are not flags.
   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
@@ -649,7 +683,6 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
                                            SDOperand Op1, SDOperand Op2,
                                            void *&InsertPos) {
   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
-    return 0;    // Never add these nodes.
   
   // Check that remaining values produced are not flags.
   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
@@ -668,10 +701,20 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
 /// return null, otherwise return a pointer to the slot it would take.  If a
 /// node already exists with these operands, the slot will be non-null.
 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, 
-                                           SDOperandPtr Ops,unsigned NumOps,
+                                           const SDOperand *Ops,unsigned NumOps,
                                            void *&InsertPos) {
-  if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
+  if (N->getValueType(0) == MVT::Flag)
+    return 0;   // Never CSE anything that produces a flag.
+
+  switch (N->getOpcode()) {
+  default: break;
+  case ISD::HANDLENODE:
+  case ISD::DBG_LABEL:
+  case ISD::DBG_STOPPOINT:
+  case ISD::EH_LABEL:
+  case ISD::DECLARE:
     return 0;    // Never add these nodes.
+  }
   
   // Check that remaining values produced are not flags.
   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
@@ -698,6 +741,16 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 }
 
+/// getMVTAlignment - Compute the default alignment value for the
+/// given type.
+///
+unsigned SelectionDAG::getMVTAlignment(MVT VT) const {
+  const Type *Ty = VT == MVT::iPTR ?
+                   PointerType::get(Type::Int8Ty, 0) :
+                   VT.getTypeForMVT();
+
+  return TLI.getTargetData()->getABITypeAlignment(Ty);
+}
 
 SelectionDAG::~SelectionDAG() {
   while (!AllNodes.empty()) {
@@ -720,34 +773,21 @@ SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT VT) {
                  getConstant(Imm, Op.getValueType()));
 }
 
-SDOperand SelectionDAG::getString(const std::string &Val) {
-  StringSDNode *&N = StringNodes[Val];
-  if (!N) {
-    N = new StringSDNode(Val);
-    AllNodes.push_back(N);
-  }
-  return SDOperand(N, 0);
-}
-
 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT VT, bool isT) {
-  MVT EltVT =
-    VT.isVector() ? VT.getVectorElementType() : VT;
-
+  MVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT;
   return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
 }
 
 SDOperand SelectionDAG::getConstant(const APInt &Val, MVT VT, bool isT) {
   assert(VT.isInteger() && "Cannot create FP integer constant!");
 
-  MVT EltVT =
-    VT.isVector() ? VT.getVectorElementType() : VT;
-  
+  MVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT;
   assert(Val.getBitWidth() == EltVT.getSizeInBits() &&
          "APInt size does not match type size!");
 
   unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, Opc, getVTList(EltVT), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
   ID.Add(Val);
   void *IP = 0;
   SDNode *N = NULL;
@@ -755,7 +795,8 @@ SDOperand SelectionDAG::getConstant(const APInt &Val, MVT VT, bool isT) {
     if (!VT.isVector())
       return SDOperand(N, 0);
   if (!N) {
-    N = new ConstantSDNode(isT, Val, EltVT);
+    N = getAllocator().Allocate<ConstantSDNode>();
+    new (N) ConstantSDNode(isT, Val, EltVT);
     CSEMap.InsertNode(N, IP);
     AllNodes.push_back(N);
   }
@@ -785,7 +826,7 @@ SDOperand SelectionDAG::getConstantFP(const APFloat& V, MVT VT, bool isTarget) {
   // we don't have issues with SNANs.
   unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, Opc, getVTList(EltVT), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
   ID.Add(V);
   void *IP = 0;
   SDNode *N = NULL;
@@ -793,7 +834,8 @@ SDOperand SelectionDAG::getConstantFP(const APFloat& V, MVT VT, bool isTarget) {
     if (!VT.isVector())
       return SDOperand(N, 0);
   if (!N) {
-    N = new ConstantFPSDNode(isTarget, V, EltVT);
+    N = getAllocator().Allocate<ConstantFPSDNode>();
+    new (N) ConstantFPSDNode(isTarget, V, EltVT);
     CSEMap.InsertNode(N, IP);
     AllNodes.push_back(N);
   }
@@ -834,13 +876,14 @@ SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
     Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
 
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
   ID.AddPointer(GV);
   ID.AddInteger(Offset);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
    return SDOperand(E, 0);
-  SDNode *N = new GlobalAddressSDNode(isTargetGA, GV, VT, Offset);
+  SDNode *N = getAllocator().Allocate<GlobalAddressSDNode>();
+  new (N) GlobalAddressSDNode(isTargetGA, GV, VT, Offset);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -849,12 +892,13 @@ SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
 SDOperand SelectionDAG::getFrameIndex(int FI, MVT VT, bool isTarget) {
   unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
   ID.AddInteger(FI);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new FrameIndexSDNode(FI, VT, isTarget);
+  SDNode *N = getAllocator().Allocate<FrameIndexSDNode>();
+  new (N) FrameIndexSDNode(FI, VT, isTarget);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -863,12 +907,13 @@ SDOperand SelectionDAG::getFrameIndex(int FI, MVT VT, bool isTarget) {
 SDOperand SelectionDAG::getJumpTable(int JTI, MVT VT, bool isTarget){
   unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
   ID.AddInteger(JTI);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new JumpTableSDNode(JTI, VT, isTarget);
+  SDNode *N = getAllocator().Allocate<JumpTableSDNode>();
+  new (N) JumpTableSDNode(JTI, VT, isTarget);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -879,14 +924,15 @@ SDOperand SelectionDAG::getConstantPool(Constant *C, MVT VT,
                                         bool isTarget) {
   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
   ID.AddInteger(Alignment);
   ID.AddInteger(Offset);
   ID.AddPointer(C);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
+  SDNode *N = getAllocator().Allocate<ConstantPoolSDNode>();
+  new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -898,14 +944,15 @@ SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C, MVT VT,
                                         bool isTarget) {
   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
   ID.AddInteger(Alignment);
   ID.AddInteger(Offset);
   C->AddSelectionDAGCSEId(ID);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
+  SDNode *N = getAllocator().Allocate<ConstantPoolSDNode>();
+  new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -914,12 +961,13 @@ SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C, MVT VT,
 
 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
   ID.AddPointer(MBB);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new BasicBlockSDNode(MBB);
+  SDNode *N = getAllocator().Allocate<BasicBlockSDNode>();
+  new (N) BasicBlockSDNode(MBB);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -927,12 +975,13 @@ SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
 
 SDOperand SelectionDAG::getArgFlags(ISD::ArgFlagsTy Flags) {
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::ARG_FLAGS, getVTList(MVT::Other), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, ISD::ARG_FLAGS, getVTList(MVT::Other), 0, 0);
   ID.AddInteger(Flags.getRawBits());
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new ARG_FLAGSSDNode(Flags);
+  SDNode *N = getAllocator().Allocate<ARG_FLAGSSDNode>();
+  new (N) ARG_FLAGSSDNode(Flags);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -946,7 +995,8 @@ SDOperand SelectionDAG::getValueType(MVT VT) {
     ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT()];
 
   if (N) return SDOperand(N, 0);
-  N = new VTSDNode(VT);
+  N = getAllocator().Allocate<VTSDNode>();
+  new (N) VTSDNode(VT);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
 }
@@ -954,7 +1004,8 @@ SDOperand SelectionDAG::getValueType(MVT VT) {
 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT VT) {
   SDNode *&N = ExternalSymbols[Sym];
   if (N) return SDOperand(N, 0);
-  N = new ExternalSymbolSDNode(false, Sym, VT);
+  N = getAllocator().Allocate<ExternalSymbolSDNode>();
+  new (N) ExternalSymbolSDNode(false, Sym, VT);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
 }
@@ -962,7 +1013,8 @@ SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT VT) {
 SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym, MVT VT) {
   SDNode *&N = TargetExternalSymbols[Sym];
   if (N) return SDOperand(N, 0);
-  N = new ExternalSymbolSDNode(true, Sym, VT);
+  N = getAllocator().Allocate<ExternalSymbolSDNode>();
+  new (N) ExternalSymbolSDNode(true, Sym, VT);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
 }
@@ -972,20 +1024,49 @@ SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
     CondCodeNodes.resize(Cond+1);
 
   if (CondCodeNodes[Cond] == 0) {
-    CondCodeNodes[Cond] = new CondCodeSDNode(Cond);
-    AllNodes.push_back(CondCodeNodes[Cond]);
+    CondCodeSDNode *N = getAllocator().Allocate<CondCodeSDNode>();
+    new (N) CondCodeSDNode(Cond);
+    CondCodeNodes[Cond] = N;
+    AllNodes.push_back(N);
   }
   return SDOperand(CondCodeNodes[Cond], 0);
 }
 
 SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT VT) {
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::Register, getVTList(VT), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
   ID.AddInteger(RegNo);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new RegisterSDNode(RegNo, VT);
+  SDNode *N = getAllocator().Allocate<RegisterSDNode>();
+  new (N) RegisterSDNode(RegNo, VT);
+  CSEMap.InsertNode(N, IP);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+SDOperand SelectionDAG::getDbgStopPoint(SDOperand Root,
+                                        unsigned Line, unsigned Col,
+                                        const CompileUnitDesc *CU) {
+  SDNode *N = getAllocator().Allocate<DbgStopPointSDNode>();
+  new (N) DbgStopPointSDNode(Root, Line, Col, CU);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+SDOperand SelectionDAG::getLabel(unsigned Opcode,
+                                 SDOperand Root,
+                                 unsigned LabelID) {
+  FoldingSetNodeID ID;
+  SDOperand Ops[] = { Root };
+  AddNodeIDNode(ID, Opcode, getVTList(MVT::Other), &Ops[0], 1);
+  ID.AddInteger(LabelID);
+  void *IP = 0;
+  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
+    return SDOperand(E, 0);
+  SDNode *N = getAllocator().Allocate<LabelSDNode>();
+  new (N) LabelSDNode(Opcode, Root, LabelID);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -996,14 +1077,15 @@ SDOperand SelectionDAG::getSrcValue(const Value *V) {
          "SrcValue is not a pointer?");
 
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
   ID.AddPointer(V);
 
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
 
-  SDNode *N = new SrcValueSDNode(V);
+  SDNode *N = getAllocator().Allocate<SrcValueSDNode>();
+  new (N) SrcValueSDNode(V);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -1015,7 +1097,7 @@ SDOperand SelectionDAG::getMemOperand(const MachineMemOperand &MO) {
          "SrcValue is not a pointer?");
 
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::MEMOPERAND, getVTList(MVT::Other), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, ISD::MEMOPERAND, getVTList(MVT::Other), 0, 0);
   ID.AddPointer(v);
   ID.AddInteger(MO.getFlags());
   ID.AddInteger(MO.getOffset());
@@ -1026,7 +1108,8 @@ SDOperand SelectionDAG::getMemOperand(const MachineMemOperand &MO) {
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
 
-  SDNode *N = new MemOperandSDNode(MO);
+  SDNode *N = getAllocator().Allocate<MemOperandSDNode>();
+  new (N) MemOperandSDNode(MO);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -1034,16 +1117,17 @@ SDOperand SelectionDAG::getMemOperand(const MachineMemOperand &MO) {
 
 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
 /// specified value type.
-SDOperand SelectionDAG::CreateStackTemporary(MVT VT) {
+SDOperand SelectionDAG::CreateStackTemporary(MVT VT, unsigned minAlign) {
   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
   unsigned ByteSize = VT.getSizeInBits()/8;
   const Type *Ty = VT.getTypeForMVT();
-  unsigned StackAlign = (unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty);
+  unsigned StackAlign =
+  std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign);
+  
   int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign);
   return getFrameIndex(FrameIdx, TLI.getPointerTy());
 }
 
-
 SDOperand SelectionDAG::FoldSetCC(MVT VT, SDOperand N1,
                                   SDOperand N2, ISD::CondCode Cond) {
   // These setcc operations always fold.
@@ -1406,7 +1490,7 @@ void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask,
   case ISD::CTPOP: {
     unsigned LowBits = Log2_32(BitWidth)+1;
     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
-    KnownOne  = APInt(BitWidth, 0);
+    KnownOne.clear();
     return;
   }
   case ISD::LOAD: {
@@ -1554,7 +1638,7 @@ void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask,
   }
   case ISD::SREM:
     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
-      APInt RA = Rem->getAPIntValue();
+      const APInt &RA = Rem->getAPIntValue();
       if (RA.isPowerOf2() || (-RA).isPowerOf2()) {
         APInt LowBits = RA.isStrictlyPositive() ? (RA - 1) : ~RA;
         APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
@@ -1576,7 +1660,7 @@ void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask,
     return;
   case ISD::UREM: {
     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
-      APInt RA = Rem->getAPIntValue();
+      const APInt &RA = Rem->getAPIntValue();
       if (RA.isPowerOf2()) {
         APInt LowBits = (RA - 1);
         APInt Mask2 = LowBits & Mask;
@@ -1842,12 +1926,16 @@ bool SelectionDAG::isVerifiedDebugInfoDesc(SDOperand Op) const {
 
 /// getShuffleScalarElt - Returns the scalar element that will make up the ith
 /// element of the result of the vector shuffle.
-SDOperand SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned Idx) {
+SDOperand SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned i) {
   MVT VT = N->getValueType(0);
   SDOperand PermMask = N->getOperand(2);
+  SDOperand Idx = PermMask.getOperand(i);
+  if (Idx.getOpcode() == ISD::UNDEF)
+    return getNode(ISD::UNDEF, VT.getVectorElementType());
+  unsigned Index = cast<ConstantSDNode>(Idx)->getValue();
   unsigned NumElems = PermMask.getNumOperands();
-  SDOperand V = (Idx < NumElems) ? N->getOperand(0) : N->getOperand(1);
-  Idx %= NumElems;
+  SDOperand V = (Index < NumElems) ? N->getOperand(0) : N->getOperand(1);
+  Index %= NumElems;
 
   if (V.getOpcode() == ISD::BIT_CONVERT) {
     V = V.getOperand(0);
@@ -1855,16 +1943,12 @@ SDOperand SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned Idx) {
       return SDOperand();
   }
   if (V.getOpcode() == ISD::SCALAR_TO_VECTOR)
-    return (Idx == 0) ? V.getOperand(0)
+    return (Index == 0) ? V.getOperand(0)
                       : getNode(ISD::UNDEF, VT.getVectorElementType());
   if (V.getOpcode() == ISD::BUILD_VECTOR)
-    return V.getOperand(Idx);
-  if (V.getOpcode() == ISD::VECTOR_SHUFFLE) {
-    SDOperand Elt = PermMask.getOperand(Idx);
-    if (Elt.getOpcode() == ISD::UNDEF)
-      return getNode(ISD::UNDEF, VT.getVectorElementType());
-    return getShuffleScalarElt(V.Val,cast<ConstantSDNode>(Elt)->getValue());
-  }
+    return V.getOperand(Index);
+  if (V.getOpcode() == ISD::VECTOR_SHUFFLE)
+    return getShuffleScalarElt(V.Val, Index);
   return SDOperand();
 }
 
@@ -1873,11 +1957,12 @@ SDOperand SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned Idx) {
 ///
 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT) {
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, Opcode, getVTList(VT), (SDOperand*)0, 0);
+  AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new SDNode(Opcode, SDNode::getSDVTList(VT));
+  SDNode *N = getAllocator().Allocate<SDNode>();
+  new (N) SDNode(Opcode, SDNode::getSDVTList(VT));
   CSEMap.InsertNode(N, IP);
   
   AllNodes.push_back(N);
@@ -1969,8 +2054,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) {
   unsigned OpOpcode = Operand.Val->getOpcode();
   switch (Opcode) {
   case ISD::TokenFactor:
-  case ISD::MERGE_VALUES:
-    return Operand;         // Factor or merge of one node?  No need.
+    return Operand;         // Factor of one node?  No need.
   case ISD::FP_ROUND: assert(0 && "Invalid method to make FP_ROUND node");
   case ISD::FP_EXTEND:
     assert(VT.isFloatingPoint() &&
@@ -2071,10 +2155,12 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) {
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDOperand(E, 0);
-    N = new UnarySDNode(Opcode, VTs, Operand);
+    N = getAllocator().Allocate<UnarySDNode>();
+    new (N) UnarySDNode(Opcode, VTs, Operand);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = new UnarySDNode(Opcode, VTs, Operand);
+    N = getAllocator().Allocate<UnarySDNode>();
+    new (N) UnarySDNode(Opcode, VTs, Operand);
   }
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -2147,7 +2233,13 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
     assert(VT == N1.getValueType() &&
            "Shift operators return type must be the same as their first arg");
     assert(VT.isInteger() && N2.getValueType().isInteger() &&
-           VT != MVT::i1 && "Shifts only work on integers");
+           "Shifts only work on integers");
+
+    // Always fold shifts of i1 values so the code generator doesn't need to
+    // handle them.  Since we know the size of the shift has to be less than the
+    // size of the value, the shift/rotate count is guaranteed to be zero.
+    if (VT == MVT::i1)
+      return N1;
     break;
   case ISD::FP_ROUND_INREG: {
     MVT EVT = cast<VTSDNode>(N2)->getVT();
@@ -2227,10 +2319,9 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
     break;
   case ISD::EXTRACT_ELEMENT:
     assert(N2C && (unsigned)N2C->getValue() < 2 && "Bad EXTRACT_ELEMENT!");
-    assert(!N1.getValueType().isVector() &&
-           N1.getValueType().isInteger() &&
-           !VT.isVector() && VT.isInteger() &&
-           "EXTRACT_ELEMENT only applies to integers!");
+    assert(!N1.getValueType().isVector() && !VT.isVector() &&
+           (N1.getValueType().isInteger() == VT.isInteger()) &&
+           "Wrong types for EXTRACT_ELEMENT!");
 
     // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
     // 64-bit integers into 32-bit parts.  Instead of building the extract of
@@ -2254,7 +2345,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
 
   if (N1C) {
     if (N2C) {
-      APInt C1 = N1C->getAPIntValue(), C2 = N2C->getAPIntValue();
+      const APInt &C1 = N1C->getAPIntValue(), &C2 = N2C->getAPIntValue();
       switch (Opcode) {
       case ISD::ADD: return getConstant(C1 + C2, VT);
       case ISD::SUB: return getConstant(C1 - C2, VT);
@@ -2416,10 +2507,12 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDOperand(E, 0);
-    N = new BinarySDNode(Opcode, VTs, N1, N2);
+    N = getAllocator().Allocate<BinarySDNode>();
+    new (N) BinarySDNode(Opcode, VTs, N1, N2);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = new BinarySDNode(Opcode, VTs, N1, N2);
+    N = getAllocator().Allocate<BinarySDNode>();
+    new (N) BinarySDNode(Opcode, VTs, N1, N2);
   }
 
   AllNodes.push_back(N);
@@ -2480,10 +2573,12 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDOperand(E, 0);
-    N = new TernarySDNode(Opcode, VTs, N1, N2, N3);
+    N = getAllocator().Allocate<TernarySDNode>();
+    new (N) TernarySDNode(Opcode, VTs, N1, N2, N3);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = new TernarySDNode(Opcode, VTs, N1, N2, N3);
+    N = getAllocator().Allocate<TernarySDNode>();
+    new (N) TernarySDNode(Opcode, VTs, N1, N2, N3);
   }
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -2538,6 +2633,16 @@ static SDOperand getMemsetValue(SDOperand Value, MVT VT, SelectionDAG &DAG) {
 static SDOperand getMemsetStringVal(MVT VT, SelectionDAG &DAG,
                                     const TargetLowering &TLI,
                                     std::string &Str, unsigned Offset) {
+  // Handle vector with all elements zero.
+  if (Str.empty()) {
+    if (VT.isInteger())
+      return DAG.getConstant(0, VT);
+    unsigned NumElts = VT.getVectorNumElements();
+    MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
+    return DAG.getNode(ISD::BIT_CONVERT, VT,
+                       DAG.getConstant(0, MVT::getVectorVT(EltVT, NumElts)));
+  }
+
   assert(!VT.isVector() && "Can't handle vector type here!");
   unsigned NumBits = VT.getSizeInBits();
   unsigned MSB = NumBits / 8;
@@ -2561,8 +2666,7 @@ static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
 
 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
 ///
-static bool isMemSrcFromString(SDOperand Src, std::string &Str,
-                               uint64_t &SrcOff) {
+static bool isMemSrcFromString(SDOperand Src, std::string &Str) {
   unsigned SrcDelta = 0;
   GlobalAddressSDNode *G = NULL;
   if (Src.getOpcode() == ISD::GlobalAddress)
@@ -2577,13 +2681,8 @@ static bool isMemSrcFromString(SDOperand Src, std::string &Str,
     return false;
 
   GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
-  if (GV && GV->isConstant()) {
-    Str = GV->getStringValue(false);
-    if (!Str.empty()) {
-      SrcOff += SrcDelta;
-      return true;
-    }
-  }
+  if (GV && GetConstantStringInfo(GV, Str, SrcDelta, false))
+    return true;
 
   return false;
 }
@@ -2595,14 +2694,12 @@ static
 bool MeetsMaxMemopRequirement(std::vector<MVT> &MemOps,
                               SDOperand Dst, SDOperand Src,
                               unsigned Limit, uint64_t Size, unsigned &Align,
+                              std::string &Str, bool &isSrcStr,
                               SelectionDAG &DAG,
                               const TargetLowering &TLI) {
-  bool AllowUnalign = TLI.allowsUnalignedMemoryAccesses();
-
-  std::string Str;
-  uint64_t SrcOff = 0;
-  bool isSrcStr = isMemSrcFromString(Src, Str, SrcOff);
+  isSrcStr = isMemSrcFromString(Src, Str);
   bool isSrcConst = isa<ConstantSDNode>(Src);
+  bool AllowUnalign = TLI.allowsUnalignedMemoryAccesses();
   MVT VT= TLI.getOptimalMemOpType(Size, Align, isSrcConst, isSrcStr);
   if (VT != MVT::iAny) {
     unsigned NewAlign = (unsigned)
@@ -2691,30 +2788,32 @@ static SDOperand getMemcpyLoadsAndStores(SelectionDAG &DAG,
   if (!AlwaysInline)
     Limit = TLI.getMaxStoresPerMemcpy();
   unsigned DstAlign = Align;  // Destination alignment can change.
+  std::string Str;
+  bool CopyFromStr;
   if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign,
-                                DAG, TLI))
+                                Str, CopyFromStr, DAG, TLI))
     return SDOperand();
 
-  std::string Str;
-  uint64_t SrcOff = 0, DstOff = 0;
-  bool CopyFromStr = isMemSrcFromString(Src, Str, SrcOff);
 
+  bool isZeroStr = CopyFromStr && Str.empty();
   SmallVector<SDOperand, 8> OutChains;
   unsigned NumMemOps = MemOps.size();
+  uint64_t SrcOff = 0, DstOff = 0;
   for (unsigned i = 0; i < NumMemOps; i++) {
     MVT VT = MemOps[i];
     unsigned VTSize = VT.getSizeInBits() / 8;
     SDOperand Value, Store;
 
-    if (CopyFromStr && !VT.isVector()) {
+    if (CopyFromStr && (isZeroStr || !VT.isVector())) {
       // It's unlikely a store of a vector immediate can be done in a single
       // instruction. It would require a load from a constantpool first.
-      // FIXME: Handle cases where store of vector immediate is done in a
-      // single instruction.
+      // We also handle store a vector with all zero's.
+      // FIXME: Handle other cases where store of vector immediate is done in
+      // a single instruction.
       Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
       Store = DAG.getStore(Chain, Value,
                            getMemBasePlusOffset(Dst, DstOff, DAG),
-                           DstSV, DstSVOff + DstOff);
+                           DstSV, DstSVOff + DstOff, false, DstAlign);
     } else {
       Value = DAG.getLoad(VT, Chain,
                           getMemBasePlusOffset(Src, SrcOff, DAG),
@@ -2747,8 +2846,10 @@ static SDOperand getMemmoveLoadsAndStores(SelectionDAG &DAG,
   if (!AlwaysInline)
     Limit = TLI.getMaxStoresPerMemmove();
   unsigned DstAlign = Align;  // Destination alignment can change.
+  std::string Str;
+  bool CopyFromStr;
   if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign,
-                                DAG, TLI))
+                                Str, CopyFromStr, DAG, TLI))
     return SDOperand();
 
   uint64_t SrcOff = 0, DstOff = 0;
@@ -2798,8 +2899,10 @@ static SDOperand getMemsetStores(SelectionDAG &DAG,
   // Expand memset to a series of load/store ops if the size operand
   // falls below a certain threshold.
   std::vector<MVT> MemOps;
+  std::string Str;
+  bool CopyFromStr;
   if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, TLI.getMaxStoresPerMemset(),
-                                Size, Align, DAG, TLI))
+                                Size, Align, Str, CopyFromStr, DAG, TLI))
     return SDOperand();
 
   SmallVector<SDOperand, 8> OutChains;
@@ -2972,18 +3075,25 @@ SDOperand SelectionDAG::getMemset(SDOperand Chain, SDOperand Dst,
 
 SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain, 
                                   SDOperand Ptr, SDOperand Cmp, 
-                                  SDOperand Swp, MVT VT) {
-  assert(Opcode == ISD::ATOMIC_LCS && "Invalid Atomic Op");
+                                  SDOperand Swp, const Value* PtrVal,
+                                  unsigned Alignment) {
+  assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
   assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
-  SDVTList VTs = getVTList(Cmp.getValueType(), MVT::Other);
+
+  MVT VT = Cmp.getValueType();
+
+  if (Alignment == 0)  // Ensure that codegen never sees alignment 0
+    Alignment = getMVTAlignment(VT);
+
+  SDVTList VTs = getVTList(VT, MVT::Other);
   FoldingSetNodeID ID;
   SDOperand Ops[] = {Chain, Ptr, Cmp, Swp};
   AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
-  ID.AddInteger(VT.getRawBits());
   void* IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp, VT);
+  SDNode* N = getAllocator().Allocate<AtomicSDNode>();
+  new (N) AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp, PtrVal, Alignment);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -2991,46 +3101,57 @@ SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain,
 
 SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain, 
                                   SDOperand Ptr, SDOperand Val, 
-                                  MVT VT) {
-  assert((   Opcode == ISD::ATOMIC_LAS || Opcode == ISD::ATOMIC_LSS
+                                  const Value* PtrVal,
+                                  unsigned Alignment) {
+  assert((   Opcode == ISD::ATOMIC_LOAD_ADD || Opcode == ISD::ATOMIC_LOAD_SUB
           || Opcode == ISD::ATOMIC_SWAP || Opcode == ISD::ATOMIC_LOAD_AND
           || Opcode == ISD::ATOMIC_LOAD_OR || Opcode == ISD::ATOMIC_LOAD_XOR
           || Opcode == ISD::ATOMIC_LOAD_NAND 
           || Opcode == ISD::ATOMIC_LOAD_MIN || Opcode == ISD::ATOMIC_LOAD_MAX
           || Opcode == ISD::ATOMIC_LOAD_UMIN || Opcode == ISD::ATOMIC_LOAD_UMAX) 
          && "Invalid Atomic Op");
-  SDVTList VTs = getVTList(Val.getValueType(), MVT::Other);
+
+  MVT VT = Val.getValueType();
+
+  if (Alignment == 0)  // Ensure that codegen never sees alignment 0
+    Alignment = getMVTAlignment(VT);
+
+  SDVTList VTs = getVTList(VT, MVT::Other);
   FoldingSetNodeID ID;
   SDOperand Ops[] = {Chain, Ptr, Val};
   AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
-  ID.AddInteger(VT.getRawBits());
   void* IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Val, VT);
+  SDNode* N = getAllocator().Allocate<AtomicSDNode>();
+  new (N) AtomicSDNode(Opcode, VTs, Chain, Ptr, Val, PtrVal, Alignment);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
 }
 
+/// getMergeValues - Create a MERGE_VALUES node from the given operands.
+/// Allowed to return something different (and simpler) if Simplify is true.
+SDOperand SelectionDAG::getMergeValues(const SDOperand *Ops, unsigned NumOps,
+                                       bool Simplify) {
+  if (Simplify && NumOps == 1)
+    return Ops[0];
+
+  SmallVector<MVT, 4> VTs;
+  VTs.reserve(NumOps);
+  for (unsigned i = 0; i < NumOps; ++i)
+    VTs.push_back(Ops[i].getValueType());
+  return getNode(ISD::MERGE_VALUES, getVTList(&VTs[0], NumOps), Ops, NumOps);
+}
+
 SDOperand
 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
                       MVT VT, SDOperand Chain,
                       SDOperand Ptr, SDOperand Offset,
                       const Value *SV, int SVOffset, MVT EVT,
                       bool isVolatile, unsigned Alignment) {
-  if (Alignment == 0) { // Ensure that codegen never sees alignment 0
-    const Type *Ty = 0;
-    if (VT != MVT::iPTR) {
-      Ty = VT.getTypeForMVT();
-    } else if (SV) {
-      const PointerType *PT = dyn_cast<PointerType>(SV->getType());
-      assert(PT && "Value for load must be a pointer");
-      Ty = PT->getElementType();
-    }
-    assert(Ty && "Could not get type information for load");
-    Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
-  }
+  if (Alignment == 0)  // Ensure that codegen never sees alignment 0
+    Alignment = getMVTAlignment(VT);
 
   if (VT == EVT) {
     ExtType = ISD::NON_EXTLOAD;
@@ -3066,8 +3187,9 @@ SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset,
-                             Alignment, isVolatile);
+  SDNode *N = getAllocator().Allocate<LoadSDNode>();
+  new (N) LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset,
+                     Alignment, isVolatile);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -3109,18 +3231,9 @@ SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Val,
                                  bool isVolatile, unsigned Alignment) {
   MVT VT = Val.getValueType();
 
-  if (Alignment == 0) { // Ensure that codegen never sees alignment 0
-    const Type *Ty = 0;
-    if (VT != MVT::iPTR) {
-      Ty = VT.getTypeForMVT();
-    } else if (SV) {
-      const PointerType *PT = dyn_cast<PointerType>(SV->getType());
-      assert(PT && "Value for store must be a pointer");
-      Ty = PT->getElementType();
-    }
-    assert(Ty && "Could not get type information for store");
-    Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
-  }
+  if (Alignment == 0)  // Ensure that codegen never sees alignment 0
+    Alignment = getMVTAlignment(VT);
+
   SDVTList VTs = getVTList(MVT::Other);
   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
   SDOperand Ops[] = { Chain, Val, Ptr, Undef };
@@ -3134,8 +3247,9 @@ SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Val,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, false,
-                              VT, SV, SVOffset, Alignment, isVolatile);
+  SDNode *N = getAllocator().Allocate<StoreSDNode>();
+  new (N) StoreSDNode(Ops, VTs, ISD::UNINDEXED, false,
+                      VT, SV, SVOffset, Alignment, isVolatile);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -3154,18 +3268,9 @@ SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Val,
   assert(VT.isInteger() == SVT.isInteger() &&
          "Can't do FP-INT conversion!");
 
-  if (Alignment == 0) { // Ensure that codegen never sees alignment 0
-    const Type *Ty = 0;
-    if (VT != MVT::iPTR) {
-      Ty = VT.getTypeForMVT();
-    } else if (SV) {
-      const PointerType *PT = dyn_cast<PointerType>(SV->getType());
-      assert(PT && "Value for store must be a pointer");
-      Ty = PT->getElementType();
-    }
-    assert(Ty && "Could not get type information for store");
-    Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
-  }
+  if (Alignment == 0)  // Ensure that codegen never sees alignment 0
+    Alignment = getMVTAlignment(VT);
+
   SDVTList VTs = getVTList(MVT::Other);
   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
   SDOperand Ops[] = { Chain, Val, Ptr, Undef };
@@ -3179,8 +3284,9 @@ SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Val,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, true,
-                              SVT, SV, SVOffset, Alignment, isVolatile);
+  SDNode *N = getAllocator().Allocate<StoreSDNode>();
+  new (N) StoreSDNode(Ops, VTs, ISD::UNINDEXED, true,
+                      SVT, SV, SVOffset, Alignment, isVolatile);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -3204,10 +3310,11 @@ SelectionDAG::getIndexedStore(SDOperand OrigStore, SDOperand Base,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new StoreSDNode(Ops, VTs, AM,
-                              ST->isTruncatingStore(), ST->getMemoryVT(),
-                              ST->getSrcValue(), ST->getSrcValueOffset(),
-                              ST->getAlignment(), ST->isVolatile());
+  SDNode *N = getAllocator().Allocate<StoreSDNode>();
+  new (N) StoreSDNode(Ops, VTs, AM,
+                      ST->isTruncatingStore(), ST->getMemoryVT(),
+                      ST->getSrcValue(), ST->getSrcValueOffset(),
+                      ST->getAlignment(), ST->isVolatile());
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -3221,7 +3328,28 @@ SDOperand SelectionDAG::getVAArg(MVT VT,
 }
 
 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
-                                SDOperandPtr Ops, unsigned NumOps) {
+                                const SDUse *Ops, unsigned NumOps) {
+  switch (NumOps) {
+  case 0: return getNode(Opcode, VT);
+  case 1: return getNode(Opcode, VT, Ops[0].getSDOperand());
+  case 2: return getNode(Opcode, VT, Ops[0].getSDOperand(),
+                         Ops[1].getSDOperand());
+  case 3: return getNode(Opcode, VT, Ops[0].getSDOperand(),
+                         Ops[1].getSDOperand(), Ops[2].getSDOperand());
+  default: break;
+  }
+
+  // Copy from an SDUse array into an SDOperand array for use with
+  // the regular getNode logic.
+  SmallVector<SDOperand, 8> NewOps;
+  NewOps.reserve(NumOps);
+  for (unsigned i = 0; i != NumOps; ++i)
+    NewOps.push_back(Ops[i].getSDOperand());
+  return getNode(Opcode, VT, Ops, NumOps);
+}
+
+SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
+                                const SDOperand *Ops, unsigned NumOps) {
   switch (NumOps) {
   case 0: return getNode(Opcode, VT);
   case 1: return getNode(Opcode, VT, Ops[0]);
@@ -3259,32 +3387,34 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDOperand(E, 0);
-    N = new SDNode(Opcode, VTs, Ops, NumOps);
+    N = getAllocator().Allocate<SDNode>();
+    new (N) SDNode(Opcode, VTs, Ops, NumOps);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = new SDNode(Opcode, VTs, Ops, NumOps);
+    N = getAllocator().Allocate<SDNode>();
+    new (N) SDNode(Opcode, VTs, Ops, NumOps);
   }
   AllNodes.push_back(N);
   return SDOperand(N, 0);
 }
 
 SDOperand SelectionDAG::getNode(unsigned Opcode,
-                                std::vector<MVT> &ResultTys,
-                                SDOperandPtr Ops, unsigned NumOps) {
+                                const std::vector<MVT> &ResultTys,
+                                const SDOperand *Ops, unsigned NumOps) {
   return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(),
                  Ops, NumOps);
 }
 
 SDOperand SelectionDAG::getNode(unsigned Opcode,
                                 const MVT *VTs, unsigned NumVTs,
-                                SDOperandPtr Ops, unsigned NumOps) {
+                                const SDOperand *Ops, unsigned NumOps) {
   if (NumVTs == 1)
     return getNode(Opcode, VTs[0], Ops, NumOps);
   return getNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps);
 }  
   
 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
-                                SDOperandPtr Ops, unsigned NumOps) {
+                                const SDOperand *Ops, unsigned NumOps) {
   if (VTList.NumVTs == 1)
     return getNode(Opcode, VTList.VTs[0], Ops, NumOps);
 
@@ -3319,31 +3449,41 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDOperand(E, 0);
-    if (NumOps == 1)
-      N = new UnarySDNode(Opcode, VTList, Ops[0]);
-    else if (NumOps == 2)
-      N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
-    else if (NumOps == 3)
-      N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
-    else
-      N = new SDNode(Opcode, VTList, Ops, NumOps);
+    if (NumOps == 1) {
+      N = getAllocator().Allocate<UnarySDNode>();
+      new (N) UnarySDNode(Opcode, VTList, Ops[0]);
+    } else if (NumOps == 2) {
+      N = getAllocator().Allocate<BinarySDNode>();
+      new (N) BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
+    } else if (NumOps == 3) {
+      N = getAllocator().Allocate<TernarySDNode>();
+      new (N) TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
+    } else {
+      N = getAllocator().Allocate<SDNode>();
+      new (N) SDNode(Opcode, VTList, Ops, NumOps);
+    }
     CSEMap.InsertNode(N, IP);
   } else {
-    if (NumOps == 1)
-      N = new UnarySDNode(Opcode, VTList, Ops[0]);
-    else if (NumOps == 2)
-      N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
-    else if (NumOps == 3)
-      N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
-    else
-      N = new SDNode(Opcode, VTList, Ops, NumOps);
+    if (NumOps == 1) {
+      N = getAllocator().Allocate<UnarySDNode>();
+      new (N) UnarySDNode(Opcode, VTList, Ops[0]);
+    } else if (NumOps == 2) {
+      N = getAllocator().Allocate<BinarySDNode>();
+      new (N) BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
+    } else if (NumOps == 3) {
+      N = getAllocator().Allocate<TernarySDNode>();
+      new (N) TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
+    } else {
+      N = getAllocator().Allocate<SDNode>();
+      new (N) SDNode(Opcode, VTList, Ops, NumOps);
+    }
   }
   AllNodes.push_back(N);
   return SDOperand(N, 0);
 }
 
 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList) {
-  return getNode(Opcode, VTList, (SDOperand*)0, 0);
+  return getNode(Opcode, VTList, 0, 0);
 }
 
 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
@@ -3530,7 +3670,7 @@ UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
 }
 
 SDOperand SelectionDAG::
-UpdateNodeOperands(SDOperand InN, SDOperandPtr Ops, unsigned NumOps) {
+UpdateNodeOperands(SDOperand InN, const SDOperand *Ops, unsigned NumOps) {
   SDNode *N = InN.Val;
   assert(N->getNumOperands() == NumOps &&
          "Update with wrong number of operands");
@@ -3575,16 +3715,22 @@ UpdateNodeOperands(SDOperand InN, SDOperandPtr Ops, unsigned NumOps) {
 /// opcode, types, and operands to the specified value.  This should only be
 /// used by the SelectionDAG class.
 void SDNode::MorphNodeTo(unsigned Opc, SDVTList L,
-                         SDOperandPtr Ops, unsigned NumOps) {
+                         const SDOperand *Ops, unsigned NumOps,
+                         SmallVectorImpl<SDNode *> &DeadNodes) {
   NodeType = Opc;
   ValueList = L.VTs;
   NumValues = L.NumVTs;
   
   // Clear the operands list, updating used nodes to remove this from their
-  // use list.
-  for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
-    I->getVal()->removeUser(std::distance(op_begin(), I), this);
-  
+  // use list.  Keep track of any operands that become dead as a result.
+  SmallPtrSet<SDNode*, 16> DeadNodeSet;
+  for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) {
+    SDNode *N = I->getVal();
+    N->removeUser(std::distance(op_begin(), I), this);
+    if (N->use_empty())
+      DeadNodeSet.insert(N);
+  }
+
   // If NumOps is larger than the # of operands we currently have, reallocate
   // the operand list.
   if (NumOps > NumOperands) {
@@ -3603,8 +3749,29 @@ void SDNode::MorphNodeTo(unsigned Opc, SDVTList L,
     OperandList[i].setUser(this);
     SDNode *N = OperandList[i].getVal();
     N->addUser(i, this);
-    ++N->UsesSize;
+    DeadNodeSet.erase(N);
   }
+
+  // Clean up any nodes that are still dead after adding the uses for the
+  // new operands.
+  for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
+       E = DeadNodeSet.end(); I != E; ++I)
+    DeadNodes.push_back(*I);
+}
+
+/// DropOperands - Release the operands and set this node to have
+/// zero operands.  This should only be used by HandleSDNode to clear
+/// its operand list.
+void SDNode::DropOperands() {
+  assert(NodeType == ISD::HANDLENODE &&
+         "DropOperands is for HANDLENODE only!");
+
+  // Unlike the code in MorphNodeTo that does this, we don't need to
+  // watch for dead nodes here.
+  for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
+    I->getVal()->removeUser(std::distance(op_begin(), I), this);
+
+  NumOperands = 0;
 }
 
 /// SelectNodeTo - These are used for target selectors to *mutate* the
@@ -3618,130 +3785,100 @@ void SDNode::MorphNodeTo(unsigned Opc, SDVTList L,
 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    MVT VT) {
   SDVTList VTs = getVTList(VT);
-  FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, (SDOperand*)0, 0);
-  void *IP = 0;
-  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
-    return ON;
-   
-  RemoveNodeFromCSEMaps(N);
-  
-  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, SDOperandPtr(), 0);
-
-  CSEMap.InsertNode(N, IP);
-  return N;
+  return SelectNodeTo(N, TargetOpc, VTs, 0, 0);
 }
 
 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    MVT VT, SDOperand Op1) {
-  // If an identical node already exists, use it.
   SDVTList VTs = getVTList(VT);
   SDOperand Ops[] = { Op1 };
-  
-  FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1);
-  void *IP = 0;
-  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
-    return ON;
-                                       
-  RemoveNodeFromCSEMaps(N);
-  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1);
-  CSEMap.InsertNode(N, IP);
-  return N;
+  return SelectNodeTo(N, TargetOpc, VTs, Ops, 1);
 }
 
 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    MVT VT, SDOperand Op1,
                                    SDOperand Op2) {
-  // If an identical node already exists, use it.
   SDVTList VTs = getVTList(VT);
   SDOperand Ops[] = { Op1, Op2 };
-  
-  FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
-  void *IP = 0;
-  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
-    return ON;
-                                       
-  RemoveNodeFromCSEMaps(N);
-  
-  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
-  
-  CSEMap.InsertNode(N, IP);   // Memoize the new node.
-  return N;
+  return SelectNodeTo(N, TargetOpc, VTs, Ops, 2);
 }
 
 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    MVT VT, SDOperand Op1,
                                    SDOperand Op2, SDOperand Op3) {
-  // If an identical node already exists, use it.
   SDVTList VTs = getVTList(VT);
   SDOperand Ops[] = { Op1, Op2, Op3 };
-  FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
-  void *IP = 0;
-  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
-    return ON;
-                                       
-  RemoveNodeFromCSEMaps(N);
-  
-  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
-
-  CSEMap.InsertNode(N, IP);   // Memoize the new node.
-  return N;
+  return SelectNodeTo(N, TargetOpc, VTs, Ops, 3);
 }
 
 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
-                                   MVT VT, SDOperandPtr Ops,
+                                   MVT VT, const SDOperand *Ops,
                                    unsigned NumOps) {
-  // If an identical node already exists, use it.
   SDVTList VTs = getVTList(VT);
-  FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
-  void *IP = 0;
-  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
-    return ON;
-                                       
-  RemoveNodeFromCSEMaps(N);
-  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
-  
-  CSEMap.InsertNode(N, IP);   // Memoize the new node.
-  return N;
+  return SelectNodeTo(N, TargetOpc, VTs, Ops, NumOps);
+}
+
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+                                   MVT VT1, MVT VT2, const SDOperand *Ops,
+                                   unsigned NumOps) {
+  SDVTList VTs = getVTList(VT1, VT2);
+  return SelectNodeTo(N, TargetOpc, VTs, Ops, NumOps);
+}
+
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+                                   MVT VT1, MVT VT2) {
+  SDVTList VTs = getVTList(VT1, VT2);
+  return SelectNodeTo(N, TargetOpc, VTs, (SDOperand *)0, 0);
+}
+
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+                                   MVT VT1, MVT VT2, MVT VT3,
+                                   const SDOperand *Ops, unsigned NumOps) {
+  SDVTList VTs = getVTList(VT1, VT2, VT3);
+  return SelectNodeTo(N, TargetOpc, VTs, Ops, NumOps);
+}
+
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 
+                                   MVT VT1, MVT VT2,
+                                   SDOperand Op1) {
+  SDVTList VTs = getVTList(VT1, VT2);
+  SDOperand Ops[] = { Op1 };
+  return SelectNodeTo(N, TargetOpc, VTs, Ops, 1);
 }
 
 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 
                                    MVT VT1, MVT VT2,
                                    SDOperand Op1, SDOperand Op2) {
   SDVTList VTs = getVTList(VT1, VT2);
-  FoldingSetNodeID ID;
   SDOperand Ops[] = { Op1, Op2 };
-  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
-  void *IP = 0;
-  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
-    return ON;
-
-  RemoveNodeFromCSEMaps(N);
-  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
-  CSEMap.InsertNode(N, IP);   // Memoize the new node.
-  return N;
+  return SelectNodeTo(N, TargetOpc, VTs, Ops, 2);
 }
 
 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    MVT VT1, MVT VT2,
                                    SDOperand Op1, SDOperand Op2, 
                                    SDOperand Op3) {
-  // If an identical node already exists, use it.
   SDVTList VTs = getVTList(VT1, VT2);
   SDOperand Ops[] = { Op1, Op2, Op3 };
+  return SelectNodeTo(N, TargetOpc, VTs, Ops, 3);
+}
+
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+                                   SDVTList VTs, const SDOperand *Ops,
+                                   unsigned NumOps) {
+  // If an identical node already exists, use it.
   FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
+  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
   void *IP = 0;
   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
     return ON;
 
   RemoveNodeFromCSEMaps(N);
 
-  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
+  SmallVector<SDNode *, 16> DeadNodes;
+  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps, DeadNodes);
+  RemoveDeadNodes(DeadNodes);
+
   CSEMap.InsertNode(N, IP);   // Memoize the new node.
   return N;
 }
@@ -3769,7 +3906,7 @@ SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT,
   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT,
-                                    SDOperandPtr Ops, unsigned NumOps) {
+                                    const SDOperand *Ops, unsigned NumOps) {
   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2) {
@@ -3797,7 +3934,7 @@ SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2,
-                                    SDOperandPtr Ops, unsigned NumOps) {
+                                    const SDOperand *Ops, unsigned NumOps) {
   const MVT *VTs = getNodeValueTypes(VT1, VT2);
   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val;
 }
@@ -3815,13 +3952,13 @@ SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3,
   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 3).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3,
-                                    SDOperandPtr Ops, unsigned NumOps) {
+                                    const SDOperand *Ops, unsigned NumOps) {
   const MVT *VTs = getNodeValueTypes(VT1, VT2, VT3);
   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
                                     MVT VT2, MVT VT3, MVT VT4,
-                                    SDOperandPtr Ops, unsigned NumOps) {
+                                    const SDOperand *Ops, unsigned NumOps) {
   std::vector<MVT> VTList;
   VTList.push_back(VT1);
   VTList.push_back(VT2);
@@ -3831,8 +3968,8 @@ SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 4, Ops, NumOps).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode,
-                                    std::vector<MVT> &ResultTys,
-                                    SDOperandPtr Ops, unsigned NumOps) {
+                                    const std::vector<MVT> &ResultTys,
+                                    const SDOperand *Ops, unsigned NumOps) {
   const MVT *VTs = getNodeValueTypes(ResultTys);
   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, ResultTys.size(),
                  Ops, NumOps).Val;
@@ -3841,7 +3978,7 @@ SDNode *SelectionDAG::getTargetNode(unsigned Opcode,
 /// getNodeIfExists - Get the specified node if it's already available, or
 /// else return NULL.
 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
-                                      SDOperandPtr Ops, unsigned NumOps) {
+                                      const SDOperand *Ops, unsigned NumOps) {
   if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
     FoldingSetNodeID ID;
     AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
@@ -3951,7 +4088,7 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
 /// This version can replace From with any result values.  To must match the
 /// number and types of values returned by From.
 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
-                                      SDOperandPtr To,
+                                      const SDOperand *To,
                                       DAGUpdateListener *UpdateListener) {
   if (From->getNumValues() == 1)  // Handle the simple case efficiently.
     return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener);
@@ -4034,8 +4171,7 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
   for (SDNode::use_iterator UI = From.Val->use_begin(), 
       E = From.Val->use_end(); UI != E; ++UI) {
     SDNode *User = UI->getUser();
-    if (!Users.count(User))
-      Users.insert(User);
+    Users.insert(User);
   }
 
   // When one of the recursive merges deletes nodes from the graph, we need to
@@ -4123,6 +4259,7 @@ unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
   }
 
   TopOrder.clear();
+  TopOrder.reserve(DAGSize);
   while (!Sources.empty()) {
     SDNode *N = Sources.back();
     Sources.pop_back();
@@ -4156,7 +4293,6 @@ void UnarySDNode::ANCHOR() {}
 void BinarySDNode::ANCHOR() {}
 void TernarySDNode::ANCHOR() {}
 void HandleSDNode::ANCHOR() {}
-void StringSDNode::ANCHOR() {}
 void ConstantSDNode::ANCHOR() {}
 void ConstantFPSDNode::ANCHOR() {}
 void GlobalAddressSDNode::ANCHOR() {}
@@ -4167,17 +4303,19 @@ void BasicBlockSDNode::ANCHOR() {}
 void SrcValueSDNode::ANCHOR() {}
 void MemOperandSDNode::ANCHOR() {}
 void RegisterSDNode::ANCHOR() {}
+void DbgStopPointSDNode::ANCHOR() {}
+void LabelSDNode::ANCHOR() {}
 void ExternalSymbolSDNode::ANCHOR() {}
 void CondCodeSDNode::ANCHOR() {}
 void ARG_FLAGSSDNode::ANCHOR() {}
 void VTSDNode::ANCHOR() {}
+void MemSDNode::ANCHOR() {}
 void LoadSDNode::ANCHOR() {}
 void StoreSDNode::ANCHOR() {}
 void AtomicSDNode::ANCHOR() {}
 
 HandleSDNode::~HandleSDNode() {
-  SDVTList VTs = { 0, 0 };
-  MorphNodeTo(ISD::HANDLENODE, VTs, SDOperandPtr(), 0);  // Drops operand uses.
+  DropOperands();
 }
 
 GlobalAddressSDNode::GlobalAddressSDNode(bool isTarget, const GlobalValue *GA,
@@ -4192,25 +4330,42 @@ GlobalAddressSDNode::GlobalAddressSDNode(bool isTarget, const GlobalValue *GA,
   TheGlobal = const_cast<GlobalValue*>(GA);
 }
 
+MemSDNode::MemSDNode(unsigned Opc, SDVTList VTs, MVT memvt,
+                     const Value *srcValue, int SVO,
+                     unsigned alignment, bool vol)
+ : SDNode(Opc, VTs), MemoryVT(memvt), SrcValue(srcValue), SVOffset(SVO),
+   Flags(vol | ((Log2_32(alignment) + 1) << 1)) {
+
+  assert(isPowerOf2_32(alignment) && "Alignment is not a power of 2!");
+  assert(getAlignment() == alignment && "Alignment representation error!");
+  assert(isVolatile() == vol && "Volatile representation error!");
+}
+
 /// getMemOperand - Return a MachineMemOperand object describing the memory
-/// reference performed by this load or store.
-MachineMemOperand LSBaseSDNode::getMemOperand() const {
+/// reference performed by this memory reference.
+MachineMemOperand MemSDNode::getMemOperand() const {
+  int Flags;
+  if (isa<LoadSDNode>(this))
+    Flags = MachineMemOperand::MOLoad;
+  else if (isa<StoreSDNode>(this))
+    Flags = MachineMemOperand::MOStore;
+  else {
+    assert(isa<AtomicSDNode>(this) && "Unknown MemSDNode opcode!");
+    Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore;
+  }
+
   int Size = (getMemoryVT().getSizeInBits() + 7) >> 3;
-  int Flags =
-    getOpcode() == ISD::LOAD ? MachineMemOperand::MOLoad :
-                               MachineMemOperand::MOStore;
-  if (IsVolatile) Flags |= MachineMemOperand::MOVolatile;
-
-  // Check if the load references a frame index, and does not have
-  // an SV attached.
-  const FrameIndexSDNode *FI =
-    dyn_cast<const FrameIndexSDNode>(getBasePtr().Val);
+  if (isVolatile()) Flags |= MachineMemOperand::MOVolatile;
+  
+  // Check if the memory reference references a frame index
+  const FrameIndexSDNode *FI = 
+  dyn_cast<const FrameIndexSDNode>(getBasePtr().Val);
   if (!getSrcValue() && FI)
     return MachineMemOperand(PseudoSourceValue::getFixedStack(), Flags,
-                             FI->getIndex(), Size, Alignment);
+                             FI->getIndex(), Size, getAlignment());
   else
-    return MachineMemOperand(getSrcValue(), Flags,
-                             getSrcValueOffset(), Size, Alignment);
+    return MachineMemOperand(getSrcValue(), Flags, getSrcValueOffset(),
+                             Size, getAlignment());
 }
 
 /// Profile - Gather unique data for the node.
@@ -4238,18 +4393,9 @@ const MVT *SDNode::getValueTypeList(MVT VT) {
 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
   assert(Value < getNumValues() && "Bad value!");
 
-  // If there is only one value, this is easy.
-  if (getNumValues() == 1)
-    return use_size() == NUses;
-  if (use_size() < NUses) return false;
-
-  SDOperand TheValue(const_cast<SDNode *>(this), Value);
-
-  SmallPtrSet<SDNode*, 32> UsersHandled;
-
   // TODO: Only iterate over uses of a given value of the node
   for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
-    if (*UI == TheValue) {
+    if (UI->getSDOperand().ResNo == Value) {
       if (NUses == 0)
         return false;
       --NUses;
@@ -4266,21 +4412,9 @@ bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
   assert(Value < getNumValues() && "Bad value!");
 
-  if (use_empty()) return false;
-
-  SDOperand TheValue(const_cast<SDNode *>(this), Value);
-
-  SmallPtrSet<SDNode*, 32> UsersHandled;
-
-  for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
-    SDNode *User = UI->getUser();
-    if (User->getNumOperands() == 1 ||
-        UsersHandled.insert(User))     // First time we've seen this?
-      for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
-        if (User->getOperand(i) == TheValue) {
-          return true;
-        }
-  }
+  for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
+    if (UI->getSDOperand().ResNo == Value)
+      return true;
 
   return false;
 }
@@ -4401,9 +4535,9 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const {
    
   case ISD::PREFETCH:      return "Prefetch";
   case ISD::MEMBARRIER:    return "MemBarrier";
-  case ISD::ATOMIC_LCS:    return "AtomicLCS";
-  case ISD::ATOMIC_LAS:    return "AtomicLAS";
-  case ISD::ATOMIC_LSS:    return "AtomicLSS";
+  case ISD::ATOMIC_CMP_SWAP:  return "AtomicCmpSwap";
+  case ISD::ATOMIC_LOAD_ADD:  return "AtomicLoadAdd";
+  case ISD::ATOMIC_LOAD_SUB:  return "AtomicLoadSub";
   case ISD::ATOMIC_LOAD_AND:  return "AtomicLoadAnd";
   case ISD::ATOMIC_LOAD_OR:   return "AtomicLoadOr";
   case ISD::ATOMIC_LOAD_XOR:  return "AtomicLoadXor";
@@ -4422,7 +4556,6 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const {
   case ISD::AssertSext:    return "AssertSext";
   case ISD::AssertZext:    return "AssertZext";
 
-  case ISD::STRING:        return "String";
   case ISD::BasicBlock:    return "BasicBlock";
   case ISD::ARG_FLAGS:     return "ArgFlags";
   case ISD::VALUETYPE:     return "ValueType";
@@ -4468,7 +4601,8 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const {
   case ISD::UNDEF:         return "undef";
   case ISD::MERGE_VALUES:  return "merge_values";
   case ISD::INLINEASM:     return "inlineasm";
-  case ISD::LABEL:         return "label";
+  case ISD::DBG_LABEL:     return "dbg_label";
+  case ISD::EH_LABEL:      return "eh_label";
   case ISD::DECLARE:       return "declare";
   case ISD::HANDLENODE:    return "handlenode";
   case ISD::FORMAL_ARGUMENTS: return "formal_arguments";
@@ -4583,7 +4717,7 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const {
   case ISD::CTLZ:    return "ctlz";
 
   // Debug info
-  case ISD::LOCATION: return "location";
+  case ISD::DBG_STOPPOINT: return "dbg_stoppoint";
   case ISD::DEBUG_LOC: return "debug_loc";
 
   // Trampolines
@@ -4692,7 +4826,7 @@ void SDNode::dump(const SelectionDAG *G) const {
   }
 
   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
-    cerr << "<" << CSDN->getValue() << ">";
+    cerr << "<" << CSDN->getAPIntValue().toStringUnsigned() << ">";
   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
     if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEsingle)
       cerr << "<" << CSDN->getValueAPF().convertToFloat() << ">";
@@ -4756,7 +4890,8 @@ void SDNode::dump(const SelectionDAG *G) const {
     cerr << N->getArgFlags().getArgFlagsString();
   } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
     cerr << ":" << N->getVT().getMVTString();
-  } else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) {
+  }
+  else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) {
     const Value *SrcValue = LD->getSrcValue();
     int SrcOffset = LD->getSrcValueOffset();
     cerr << " <";
@@ -4808,6 +4943,18 @@ void SDNode::dump(const SelectionDAG *G) const {
     if (ST->isVolatile())
       cerr << " <volatile>";
     cerr << " alignment=" << ST->getAlignment();
+  } else if (const AtomicSDNode* AT = dyn_cast<AtomicSDNode>(this)) {
+    const Value *SrcValue = AT->getSrcValue();
+    int SrcOffset = AT->getSrcValueOffset();
+    cerr << " <";
+    if (SrcValue)
+      cerr << SrcValue;
+    else
+      cerr << "null";
+    cerr << ":" << SrcOffset << ">";
+    if (AT->isVolatile())
+      cerr << " <volatile>";
+    cerr << " alignment=" << AT->getAlignment();
   }
 }