diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 56bd40a..d31bb4e 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -17,7 +17,6 @@
 
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/StringMap.h"
-#include "llvm/ADT/ilist.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 
 #include <list>
@@ -55,7 +54,7 @@
   SDOperand Root, EntryNode;
 
   /// AllNodes - A linked list of nodes in the current DAG.
-  ilist<SDNode> AllNodes;
+  alist<SDNode, LargestSDNode> &AllNodes;
 
   /// CSEMap - This structure is used to memoize nodes, automatically performing
   /// CSE with existing nodes with a duplicate is requested.
@@ -63,8 +62,9 @@
 
 public:
   SelectionDAG(TargetLowering &tli, MachineFunction &mf, 
-               FunctionLoweringInfo &fli, MachineModuleInfo *mmi)
-  : TLI(tli), MF(mf), FLI(fli), MMI(mmi) {
+               FunctionLoweringInfo &fli, MachineModuleInfo *mmi,
+               alist<SDNode, LargestSDNode> &NodePool)
+  : TLI(tli), MF(mf), FLI(fli), MMI(mmi), AllNodes(NodePool) {
     EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
   }
   ~SelectionDAG();
@@ -99,13 +99,15 @@
   ///
   void setGraphColor(const SDNode *N, const char *Color);
 
-  typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
+  typedef alist<SDNode, LargestSDNode>::const_iterator allnodes_const_iterator;
   allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
   allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
-  typedef ilist<SDNode>::iterator allnodes_iterator;
+  typedef alist<SDNode, LargestSDNode>::iterator allnodes_iterator;
   allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
   allnodes_iterator allnodes_end() { return AllNodes.end(); }
-  ilist<SDNode>::size_type allnodes_size() const { return AllNodes.size(); }
+  alist<SDNode, LargestSDNode>::size_type allnodes_size() const {
+    return AllNodes.size();
+  }
   
   /// getRoot - Return the root tag of the SelectionDAG.
   ///
@@ -642,6 +644,7 @@
   SDOperand getShuffleScalarElt(const SDNode *N, unsigned Idx);
   
 private:
+  inline alist_traits<SDNode, LargestSDNode>::AllocatorType &getAllocator();
   void RemoveNodeFromCSEMaps(SDNode *N);
   SDNode *AddNonLeafNodeToCSEMaps(SDNode *N);
   SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos);
diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h
index c5aa77a..ad573b4 100644
--- a/include/llvm/CodeGen/SelectionDAGISel.h
+++ b/include/llvm/CodeGen/SelectionDAGISel.h
@@ -178,8 +178,11 @@
                     int64_t DesiredMaskS) const;
   
 private:
+  void SelectAllBasicBlocks(Function &Fn, MachineFunction &MF,
+                            FunctionLoweringInfo &FuncInfo);
   void SelectBasicBlock(BasicBlock *BB, MachineFunction &MF,
-                        FunctionLoweringInfo &FuncInfo);
+                        FunctionLoweringInfo &FuncInfo,
+                        alist<SDNode, LargestSDNode> &AllNodes);
 
   void BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
            std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index fe1cab6..c4f1f96 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -25,8 +25,11 @@
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
+#include "llvm/ADT/alist.h"
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/RecyclingAllocator.h"
 #include "llvm/Support/DataTypes.h"
 #include <cassert>
 
@@ -40,9 +43,6 @@
 class CompileUnitDesc;
 template <typename T> struct DenseMapInfo;
 template <typename T> struct simplify_type;
-template <typename T> struct ilist_traits;
-template<typename NodeTy, typename Traits> class iplist;
-template<typename NodeTy> class ilist_iterator;
 
 /// SDVTList - This represents a list of ValueType's that has been intern'd by
 /// a SelectionDAG.  Instances of this simple value class are returned by
@@ -1054,11 +1054,6 @@
   /// Uses - List of uses for this SDNode.
   SDUse *Uses;
 
-  /// Prev/Next pointers - These pointers form the linked list of of the
-  /// AllNodes list in the current DAG.
-  SDNode *Prev, *Next;
-  friend struct ilist_traits<SDNode>;
-
   /// addUse - add SDUse to the list of uses.
   void addUse(SDUse &U) { U.addToList(&Uses); }
 
@@ -1268,7 +1263,6 @@
     
     ValueList = VTs.VTs;
     NumValues = VTs.NumVTs;
-    Prev = 0; Next = 0;
   }
 
   SDNode(unsigned Opc, SDVTList VTs, const SDUse *Ops, unsigned NumOps)
@@ -1286,7 +1280,6 @@
     
     ValueList = VTs.VTs;
     NumValues = VTs.NumVTs;
-    Prev = 0; Next = 0;
   }
 
   SDNode(unsigned Opc, SDVTList VTs)
@@ -1296,7 +1289,6 @@
     OperandList = 0;
     ValueList = VTs.VTs;
     NumValues = VTs.NumVTs;
-    Prev = 0; Next = 0;
   }
   
   /// InitOperands - Initialize the operands list of this node with the
@@ -2234,26 +2226,30 @@
   }
 };
 
-template<>
-struct ilist_traits<SDNode> {
-  static SDNode *getPrev(const SDNode *N) { return N->Prev; }
-  static SDNode *getNext(const SDNode *N) { return N->Next; }
-  
-  static void setPrev(SDNode *N, SDNode *Prev) { N->Prev = Prev; }
-  static void setNext(SDNode *N, SDNode *Next) { N->Next = Next; }
-  
-  static SDNode *createSentinel() {
-    return new SDNode(ISD::EntryToken, SDNode::getSDVTList(MVT::Other));
+/// LargestSDNode - The largest SDNode class.
+///
+typedef LoadSDNode LargestSDNode;
+
+// alist_traits specialization for pool-allocating SDNodes.
+template <>
+class alist_traits<SDNode, LargestSDNode> {
+  typedef alist_iterator<SDNode, LargestSDNode> iterator;
+
+public:
+  // Pool-allocate and recycle SDNodes.
+  typedef RecyclingAllocator<BumpPtrAllocator, SDNode, LargestSDNode>
+    AllocatorType;
+
+  // Allocate the allocator immediately inside the traits class.
+  AllocatorType Allocator;
+
+  void addNodeToList(SDNode* N) {}
+  void removeNodeFromList(SDNode* N) {}
+  void transferNodesFromList(alist_traits &, iterator, iterator) {}
+  void deleteNode(SDNode *N) {
+    N->~SDNode();
+    Allocator.Deallocate(N);
   }
-  static void destroySentinel(SDNode *N) { delete N; }
-  //static SDNode *createNode(const SDNode &V) { return new SDNode(V); }
-  
-  
-  void addNodeToList(SDNode *) {}
-  void removeNodeFromList(SDNode *) {}
-  void transferNodesFromList(iplist<SDNode, ilist_traits> &,
-                             const ilist_iterator<SDNode> &,
-                             const ilist_iterator<SDNode> &) {}
 };
 
 namespace ISD {
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 3f262df..14ae801 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -472,6 +472,11 @@
 //                              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() {
@@ -549,9 +554,6 @@
 
 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);
@@ -561,7 +563,7 @@
   N->OperandList = 0;
   N->NumOperands = 0;
   
-  delete N;
+  AllNodes.erase(N);
 }
 
 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
@@ -754,7 +756,8 @@
     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);
   }
@@ -792,7 +795,8 @@
     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);
   }
@@ -839,7 +843,8 @@
   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);
@@ -853,7 +858,8 @@
   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);
@@ -867,7 +873,8 @@
   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);
@@ -885,7 +892,8 @@
   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);
@@ -904,7 +912,8 @@
   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);
@@ -918,7 +927,8 @@
   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);
@@ -931,7 +941,8 @@
   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);
@@ -945,7 +956,8 @@
     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);
 }
@@ -953,7 +965,8 @@
 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);
 }
@@ -961,7 +974,8 @@
 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);
 }
@@ -971,8 +985,10 @@
     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);
 }
@@ -984,7 +1000,8 @@
   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);
@@ -1002,7 +1019,8 @@
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new DbgStopPointSDNode(Root, Line, Col, CU);
+  SDNode *N = getAllocator().Allocate<DbgStopPointSDNode>();
+  new (N) DbgStopPointSDNode(Root, Line, Col, CU);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -1018,7 +1036,8 @@
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode *N = new LabelSDNode(Opcode, Root, LabelID);
+  SDNode *N = getAllocator().Allocate<LabelSDNode>();
+  new (N) LabelSDNode(Opcode, Root, LabelID);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDOperand(N, 0);
@@ -1036,7 +1055,8 @@
   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);
@@ -1059,7 +1079,8 @@
   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);
@@ -1911,7 +1932,8 @@
   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);
@@ -2104,10 +2126,12 @@
     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);
@@ -2454,10 +2478,12 @@
     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);
@@ -2518,10 +2544,12 @@
     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);
@@ -3029,8 +3057,8 @@
   void* IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp,
-                               PtrVal, Alignment);
+  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);
@@ -3054,8 +3082,8 @@
   void* IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
-  SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Val,
-                               PtrVal, Alignment);
+  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);
@@ -3128,8 +3156,9 @@
   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);
@@ -3196,8 +3225,9 @@
   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);
@@ -3241,8 +3271,9 @@
   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);
@@ -3266,10 +3297,11 @@
   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);
@@ -3342,10 +3374,12 @@
     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);
@@ -3402,24 +3436,34 @@
     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);
@@ -4203,6 +4247,7 @@
   }
 
   TopOrder.clear();
+  TopOrder.reserve(DAGSize);
   while (!Sources.empty()) {
     SDNode *N = Sources.back();
     Sources.pop_back();
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index 9e7e9d8..bc1eda3 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -414,9 +414,9 @@
   // also creates the initial PHI MachineInstrs, though none of the input
   // operands are populated.
   for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) {
-    MachineBasicBlock *MBB = new MachineBasicBlock(BB);
+    MachineBasicBlock *MBB = mf.CreateMachineBasicBlock(BB);
     MBBMap[BB] = MBB;
-    MF.getBasicBlockList().push_back(MBB);
+    MF.push_back(MBB);
 
     // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
     // appropriate.
@@ -1432,8 +1432,9 @@
   
   //  Create TmpBB after CurBB.
   MachineFunction::iterator BBI = CurBB;
-  MachineBasicBlock *TmpBB = new MachineBasicBlock(CurBB->getBasicBlock());
-  CurBB->getParent()->getBasicBlockList().insert(++BBI, TmpBB);
+  MachineFunction &MF = DAG.getMachineFunction();
+  MachineBasicBlock *TmpBB = MF.CreateMachineBasicBlock(CurBB->getBasicBlock());
+  CurBB->getParent()->insert(++BBI, TmpBB);
   
   if (Opc == Instruction::Or) {
     // Codegen X | Y as:
@@ -1554,7 +1555,7 @@
       // Okay, we decided not to do this, remove any inserted MBB's and clear
       // SwitchCases.
       for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i)
-        CurMBB->getParent()->getBasicBlockList().erase(SwitchCases[i].ThisBB);
+        CurMBB->getParent()->erase(SwitchCases[i].ThisBB);
       
       SwitchCases.clear();
     }
@@ -1861,8 +1862,8 @@
   for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++I) {
     MachineBasicBlock *FallThrough;
     if (I != E-1) {
-      FallThrough = new MachineBasicBlock(CurBlock->getBasicBlock());
-      CurMF->getBasicBlockList().insert(BBI, FallThrough);
+      FallThrough = CurMF->CreateMachineBasicBlock(CurBlock->getBasicBlock());
+      CurMF->insert(BBI, FallThrough);
     } else {
       // If the last case doesn't match, go to the default block.
       FallThrough = Default;
@@ -1945,8 +1946,8 @@
   // of the jump table, and jumping to it.  Update successor information;
   // we will either branch to the default case for the switch, or the jump
   // table.
-  MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB);
-  CurMF->getBasicBlockList().insert(BBI, JumpTableBB);
+  MachineBasicBlock *JumpTableBB = CurMF->CreateMachineBasicBlock(LLVMBB);
+  CurMF->insert(BBI, JumpTableBB);
   CR.CaseBB->addSuccessor(Default);
   CR.CaseBB->addSuccessor(JumpTableBB);
                 
@@ -2083,8 +2084,8 @@
       (cast<ConstantInt>(CR.GE)->getSExtValue() + 1LL)) {
     TrueBB = LHSR.first->BB;
   } else {
-    TrueBB = new MachineBasicBlock(LLVMBB);
-    CurMF->getBasicBlockList().insert(BBI, TrueBB);
+    TrueBB = CurMF->CreateMachineBasicBlock(LLVMBB);
+    CurMF->insert(BBI, TrueBB);
     WorkList.push_back(CaseRec(TrueBB, C, CR.GE, LHSR));
   }
   
@@ -2097,8 +2098,8 @@
       (cast<ConstantInt>(CR.LT)->getSExtValue() - 1LL)) {
     FalseBB = RHSR.first->BB;
   } else {
-    FalseBB = new MachineBasicBlock(LLVMBB);
-    CurMF->getBasicBlockList().insert(BBI, FalseBB);
+    FalseBB = CurMF->CreateMachineBasicBlock(LLVMBB);
+    CurMF->insert(BBI, FalseBB);
     WorkList.push_back(CaseRec(FalseBB,CR.LT,C,RHSR));
   }
 
@@ -2220,8 +2221,8 @@
     DOUT << "Mask: " << CasesBits[i].Mask << ", Bits: " << CasesBits[i].Bits
          << ", BB: " << CasesBits[i].BB << "\n";
 
-    MachineBasicBlock *CaseBB = new MachineBasicBlock(LLVMBB);
-    CurMF->getBasicBlockList().insert(BBI, CaseBB);
+    MachineBasicBlock *CaseBB = CurMF->CreateMachineBasicBlock(LLVMBB);
+    CurMF->insert(BBI, CaseBB);
     BTC.push_back(SelectionDAGISel::BitTestCase(CasesBits[i].Mask,
                                                 CaseBB,
                                                 CasesBits[i].BB));
@@ -4877,8 +4878,7 @@
       // Mark landing pad.
       FuncInfo.MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
 
-  for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
-    SelectBasicBlock(I, MF, FuncInfo);
+  SelectAllBasicBlocks(Fn, MF, FuncInfo);
 
   // Add function live-ins to entry block live-in set.
   BasicBlock *EntryBB = &Fn.getEntryBlock();
@@ -5002,10 +5002,11 @@
  
   // Fix tail call attribute of CALL nodes.
   for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(),
-         BI = prior(DAG.allnodes_end()); BI != BE; --BI) {
+         BI = DAG.allnodes_end(); BI != BE; ) {
+    --BI;
     if (BI->getOpcode() == ISD::CALL) {
       SDOperand OpRet(Ret, 0);
-      SDOperand OpCall(static_cast<SDNode*>(BI), 0);
+      SDOperand OpCall(BI, 0);
       bool isMarkedTailCall = 
         cast<ConstantSDNode>(OpCall.getOperand(3))->getValue() != 0;
       // If CALL node has tail call attribute set to true and the call is not
@@ -5355,12 +5356,26 @@
   DEBUG(BB->dump());
 }  
 
+void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF,
+                                            FunctionLoweringInfo &FuncInfo) {
+  // Define AllNodes here so that memory allocation is reused for
+  // each basic block.
+  alist<SDNode, LargestSDNode> AllNodes;
+
+  for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
+    SelectBasicBlock(I, MF, FuncInfo, AllNodes);
+    AllNodes.clear();
+  }
+}
+
 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
-                                        FunctionLoweringInfo &FuncInfo) {
+                                        FunctionLoweringInfo &FuncInfo,
+                                        alist<SDNode, LargestSDNode> &AllNodes) {
   std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
   {
     SelectionDAG DAG(TLI, MF, FuncInfo, 
-                     getAnalysisToUpdate<MachineModuleInfo>());
+                     getAnalysisToUpdate<MachineModuleInfo>(),
+                     AllNodes);
     CurDAG = &DAG;
   
     // First step, lower LLVM code to some DAG.  This DAG may use operations and
@@ -5395,7 +5410,8 @@
     // Lower header first, if it wasn't already lowered
     if (!BitTestCases[i].Emitted) {
       SelectionDAG HSDAG(TLI, MF, FuncInfo, 
-                         getAnalysisToUpdate<MachineModuleInfo>());
+                         getAnalysisToUpdate<MachineModuleInfo>(),
+                         AllNodes);
       CurDAG = &HSDAG;
       SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI);
       // Set the current basic block to the mbb we wish to insert the code into
@@ -5409,7 +5425,8 @@
 
     for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) {
       SelectionDAG BSDAG(TLI, MF, FuncInfo, 
-                         getAnalysisToUpdate<MachineModuleInfo>());
+                         getAnalysisToUpdate<MachineModuleInfo>(),
+                         AllNodes);
       CurDAG = &BSDAG;
       SelectionDAGLowering BSDL(BSDAG, TLI, *AA, FuncInfo, GCI);
       // Set the current basic block to the mbb we wish to insert the code into
@@ -5467,7 +5484,8 @@
     // Lower header first, if it wasn't already lowered
     if (!JTCases[i].first.Emitted) {
       SelectionDAG HSDAG(TLI, MF, FuncInfo, 
-                         getAnalysisToUpdate<MachineModuleInfo>());
+                         getAnalysisToUpdate<MachineModuleInfo>(),
+                         AllNodes);
       CurDAG = &HSDAG;
       SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI);
       // Set the current basic block to the mbb we wish to insert the code into
@@ -5480,7 +5498,8 @@
     }
     
     SelectionDAG JSDAG(TLI, MF, FuncInfo, 
-                       getAnalysisToUpdate<MachineModuleInfo>());
+                       getAnalysisToUpdate<MachineModuleInfo>(),
+                       AllNodes);
     CurDAG = &JSDAG;
     SelectionDAGLowering JSDL(JSDAG, TLI, *AA, FuncInfo, GCI);
     // Set the current basic block to the mbb we wish to insert the code into
@@ -5529,7 +5548,8 @@
   // additional DAGs necessary.
   for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
     SelectionDAG SDAG(TLI, MF, FuncInfo, 
-                      getAnalysisToUpdate<MachineModuleInfo>());
+                      getAnalysisToUpdate<MachineModuleInfo>(),
+                      AllNodes);
     CurDAG = &SDAG;
     SelectionDAGLowering SDL(SDAG, TLI, *AA, FuncInfo, GCI);