Fold the useful features of alist and alist_node into ilist, and

a new ilist_node class, and remove them. Unlike alist_node,
ilist_node doesn't attempt to manage storage itself, so it avoids
the associated problems, including being opaque in gdb.

Adjust the Recycler class so that it doesn't depend on alist_node.
Also, change it to use explicit Size and Align parameters, allowing
it to work when the largest-sized node doesn't have the greatest
alignment requirement.

Change MachineInstr's MachineMemOperand list from a pool-backed
alist to a std::list for now.


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

33 files changed, 340 insertions, 815 deletions

diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index adeb541d3d..efd0accaad 100644
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -39,7 +39,8 @@ namespace llvm {
 
 
 template <unsigned ElementSize = 128>
-struct SparseBitVectorElement {
+struct SparseBitVectorElement
+  : ilist_node<SparseBitVectorElement<ElementSize> > {
 public:
   typedef unsigned long BitWord;
   enum {
@@ -48,56 +49,23 @@ public:
     BITS_PER_ELEMENT = ElementSize
   };
 
-  SparseBitVectorElement<ElementSize> *getNext() const {
-    return Next;
-  }
-  SparseBitVectorElement<ElementSize> *getPrev() const {
-    return Prev;
-  }
-
-  void setNext(SparseBitVectorElement<ElementSize> *RHS) {
-    Next = RHS;
-  }
-  void setPrev(SparseBitVectorElement<ElementSize> *RHS) {
-    Prev = RHS;
-  }
-
 private:
-  SparseBitVectorElement<ElementSize> *Next;
-  SparseBitVectorElement<ElementSize> *Prev;
   // Index of Element in terms of where first bit starts.
   unsigned ElementIndex;
   BitWord Bits[BITWORDS_PER_ELEMENT];
   // Needed for sentinels
+  friend class ilist_sentinel_traits<SparseBitVectorElement>;
   SparseBitVectorElement() {
     ElementIndex = ~0U;
     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
   }
 
-  friend struct ilist_traits<SparseBitVectorElement<ElementSize> >;
 public:
   explicit SparseBitVectorElement(unsigned Idx) {
     ElementIndex = Idx;
     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
   }
 
-  ~SparseBitVectorElement() {
-  }
-
-  // Copy ctor.
-  SparseBitVectorElement(const SparseBitVectorElement &RHS) {
-    ElementIndex = RHS.ElementIndex;
-    std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
-  }
-  
-  // Assignment 
-  SparseBitVectorElement& operator=(const SparseBitVectorElement& RHS) {
-    ElementIndex = RHS.ElementIndex;
-    std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
-    
-    return *this;
-  }
-
   // Comparison.
   bool operator==(const SparseBitVectorElement &RHS) const {
     if (ElementIndex != RHS.ElementIndex)
diff --git a/include/llvm/ADT/alist.h b/include/llvm/ADT/alist.h
deleted file mode 100644
index 1af3e4a5c0..0000000000
--- a/include/llvm/ADT/alist.h
+++ /dev/null
@@ -1,296 +0,0 @@
-//==- llvm/ADT/alist.h - Linked lists with hooks -----------------*- C++ -*-==//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines the alist class template, and related infrastructure.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ADT_ALIST_H
-#define LLVM_ADT_ALIST_H
-
-#include "llvm/ADT/alist_node.h"
-#include "llvm/ADT/STLExtras.h"
-
-namespace llvm {
-
-/// alist_iterator - An iterator class for alist.
-///
-template<class T, class LargestT = T, class ValueT = T,
-         class NodeIterT = ilist_iterator<alist_node<T, LargestT> > >
-class alist_iterator : public bidirectional_iterator<ValueT, ptrdiff_t> {
-public:
-  typedef bidirectional_iterator<ValueT, ptrdiff_t> super;
-  typedef alist_node<T, LargestT> NodeTy;
-
-private:
-  /// NodeIter - The underlying iplist iterator that is being wrapped.
-  NodeIterT NodeIter;
-
-public:
-  typedef size_t size_type;
-
-  // FIX for MSVC++.  This should be reviewed more.
-  // typedef typename super::pointer pointer;
-  typedef ValueT* pointer;
-
-  typedef typename super::reference reference;
-
-  alist_iterator(NodeIterT NI) : NodeIter(NI) {}
-  alist_iterator(pointer EP) : NodeIter(NodeTy::getNode(EP)) {}
-  alist_iterator() : NodeIter() {}
-
-  // This is templated so that we can allow constructing a const iterator from
-  // a nonconst iterator...
-  template<class V, class W, class X, class Y>
-  alist_iterator(const alist_iterator<V, W, X, Y> &RHS)
-    : NodeIter(RHS.getNodeIterUnchecked()) {}
-
-  // This is templated so that we can allow assigning to a const iterator from
-  // a nonconst iterator...
-  template<class V, class W, class X, class Y>
-  const alist_iterator &operator=(const alist_iterator<V, W, X, Y> &RHS) {
-    NodeIter = RHS.getNodeIterUnchecked();
-    return *this;
-  }
-
-  operator pointer() const { return NodeIter->getElement((T*)0); }
-
-  reference operator*() const { return *NodeIter->getElement((T*)0); }
-  pointer   operator->() const { return &operator*(); }
-
-  bool operator==(const alist_iterator &RHS) const {
-    return NodeIter == RHS.NodeIter;
-  }
-  bool operator!=(const alist_iterator &RHS) const {
-    return NodeIter != RHS.NodeIter;
-  }
-
-  alist_iterator &operator--() {
-    --NodeIter;
-    return *this;
-  }
-  alist_iterator &operator++() {
-    ++NodeIter;
-    return *this;
-  }
-  alist_iterator operator--(int) {
-    alist_iterator tmp = *this;
-    --*this;
-    return tmp;
-  }
-  alist_iterator operator++(int) {
-    alist_iterator tmp = *this;
-    ++*this;
-    return tmp;
-  }
-
-  NodeIterT getNodeIterUnchecked() const { return NodeIter; }
-};
-
-// do not implement. this is to catch errors when people try to use
-// them as random access iterators
-template<class T, class LargestT, class ValueT, class NodeIterT>
-void operator-(int, alist_iterator<T, LargestT, ValueT, NodeIterT>);
-template<class T, class LargestT, class ValueT, class NodeIterT>
-void operator-(alist_iterator<T, LargestT, ValueT, NodeIterT>,int);
-
-template<class T, class LargestT, class ValueT, class NodeIterT>
-void operator+(int, alist_iterator<T, LargestT, ValueT, NodeIterT>);
-template<class T, class LargestT, class ValueT, class NodeIterT>
-void operator+(alist_iterator<T, LargestT, ValueT, NodeIterT>,int);
-
-// operator!=/operator== - Allow mixed comparisons without dereferencing
-// the iterator, which could very likely be pointing to end().
-template<class T, class V, class W, class X, class Y>
-bool operator!=(T* LHS, const alist_iterator<V, W, X, Y> &RHS) {
-  return LHS != RHS.getNodeIterUnchecked().getNodePtrUnchecked()
-                                                            ->getElement((T*)0);
-}
-template<class T, class V, class W, class X, class Y>
-bool operator==(T* LHS, const alist_iterator<V, W, X, Y> &RHS) {
-  return LHS == RHS.getNodeIterUnchecked().getNodePtrUnchecked()
-                                                            ->getElement((T*)0);
-}
-
-// Allow alist_iterators to convert into pointers to a node automatically when
-// used by the dyn_cast, cast, isa mechanisms...
-
-template<class From> struct simplify_type;
-
-template<class V, class W, class X, class Y>
-struct simplify_type<alist_iterator<V, W, X, Y> > {
-  typedef alist_node<V, W> NodeTy;
-  typedef NodeTy* SimpleType;
-
-  static SimpleType
-  getSimplifiedValue(const alist_iterator<V, W, X, Y> &Node) {
-    return &*Node;
-  }
-};
-template<class V, class W, class X, class Y>
-struct simplify_type<const alist_iterator<V, W, X, Y> > {
-  typedef alist_node<V, W> NodeTy;
-  typedef NodeTy* SimpleType;
-
-  static SimpleType
-  getSimplifiedValue(const alist_iterator<V, W, X, Y> &Node) {
-    return &*Node;
-  }
-};
-
-/// Template traits for alist.  By specializing this template class, you
-/// can register custom actions to be run when a node is added to or removed
-/// from an alist. A common use of this is to update parent pointers.
-///
-template<class T, class LargestT = T>
-class alist_traits {
-public:
-  typedef alist_iterator<T, LargestT> iterator;
-
-  void addNodeToList(T *) {}
-  void removeNodeFromList(T *) {}
-  void transferNodesFromList(alist_traits &, iterator, iterator) {}
-  void deleteNode(T *E) { delete alist_node<T, LargestT>::getNode(E); }
-};
-
-/// alist - This class is an ilist-style container that automatically
-/// adds the next/prev pointers. It is designed to work in cooperation
-/// with <llvm/Support/Recycler.h>.
-///
-template<class T, class LargestT = T>
-class alist {
-public:
-  typedef alist_node<T, LargestT> NodeTy;
-  typedef typename ilist<NodeTy>::size_type size_type;
-
-private:
-  /// NodeListTraits - ilist traits for NodeList.
-  ///
-  struct NodeListTraits : ilist_traits<alist_node<T, LargestT> > {
-    alist_traits<T, LargestT> UserTraits;
-
-    void addNodeToList(NodeTy *N) {
-      UserTraits.addNodeToList(N->getElement((T*)0));
-    }
-    void removeNodeFromList(NodeTy *N) {
-      UserTraits.removeNodeFromList(N->getElement((T*)0));
-    }
-    void transferNodesFromList(iplist<NodeTy, NodeListTraits> &L2,
-                               ilist_iterator<NodeTy> first,
-                               ilist_iterator<NodeTy> last) {
-      UserTraits.transferNodesFromList(L2.UserTraits,
-                                       iterator(first),
-                                       iterator(last));
-    }
-  };
-
-  /// NodeList - Doubly-linked list of nodes that have constructed
-  /// contents and may be in active use.
-  ///
-  iplist<NodeTy, NodeListTraits> NodeList;
-
-public:
-  ~alist() { clear(); }
-
-  typedef alist_iterator<T, LargestT, T, ilist_iterator<NodeTy> >
-    iterator;
-  typedef alist_iterator<T, LargestT, const T, ilist_iterator<const NodeTy> >
-    const_iterator;
-  typedef std::reverse_iterator<iterator> reverse_iterator;
-  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
-
-  iterator begin() { return iterator(NodeList.begin()); }
-  iterator end() { return iterator(NodeList.end()); }
-  const_iterator begin() const { return const_iterator(NodeList.begin()); }
-  const_iterator end() const { return const_iterator(NodeList.end()); }
-  reverse_iterator rbegin() { return reverse_iterator(NodeList.rbegin()); }
-  reverse_iterator rend() { return reverse_iterator(NodeList.rend()); }
-  const_reverse_iterator rbegin() const {
-    return const_reverse_iterator(NodeList.rbegin());
-  }
-  const_reverse_iterator rend() const {
-    return const_reverse_iterator(NodeList.rend());
-  }
-
-  typedef T& reference;
-  typedef const T& const_reference;
-  reference front() { return *NodeList.front().getElement((T*)0); }
-  reference back()  { return *NodeList.back().getElement((T*)0); }
-  const_reference front() const { return *NodeList.front().getElement((T*)0); }
-  const_reference back()  const { return *NodeList.back().getElement((T*)0); }
-
-  bool empty() const { return NodeList.empty(); }
-  size_type size() const { return NodeList.size(); }
-
-  void push_front(T *E) {
-    NodeTy *N = alist_node<T, LargestT>::getNode(E);
-    assert(N->getPrev() == 0);
-    assert(N->getNext() == 0);
-    NodeList.push_front(N);
-  }
-  void push_back(T *E) {
-    NodeTy *N = alist_node<T, LargestT>::getNode(E);
-    assert(N->getPrev() == 0);
-    assert(N->getNext() == 0);
-    NodeList.push_back(N);
-  }
-  iterator insert(iterator I, T *E) {
-    NodeTy *N = alist_node<T, LargestT>::getNode(E);
-    assert(N->getPrev() == 0);
-    assert(N->getNext() == 0);
-    return iterator(NodeList.insert(I.getNodeIterUnchecked(), N));
-  }
-  void splice(iterator where, alist &Other) {
-    NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList);
-  }
-  void splice(iterator where, alist &Other, iterator From) {
-    NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList,
-                    From.getNodeIterUnchecked());
-  }
-  void splice(iterator where, alist &Other, iterator From,
-              iterator To) {
-    NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList,
-                    From.getNodeIterUnchecked(), To.getNodeIterUnchecked());
-  }
-
-  void pop_front() {
-    erase(NodeList.begin());
-  }
-  void pop_back() {
-    erase(prior(NodeList.end()));
-  }
-  iterator erase(iterator I) {
-    iterator Next = next(I);
-    NodeTy *N = NodeList.remove(I.getNodeIterUnchecked());
-    NodeList.UserTraits.deleteNode(N->getElement((T*)0));
-    return Next;
-  }
-  iterator erase(iterator first, iterator last) {
-    while (first != last)
-      first = erase(first);
-    return last;
-  }
-
-  T *remove(T *E) {
-    NodeTy *N = alist_node<T, LargestT>::getNode(E);
-    return NodeList.remove(N)->getElement((T*)0);
-  }
-
-  void clear() {
-    while (!empty()) pop_front();
-  }
-
-  alist_traits<T, LargestT> &getTraits() {
-    return NodeList.UserTraits;
-  }
-};
-
-}
-
-#endif
diff --git a/include/llvm/ADT/alist_node.h b/include/llvm/ADT/alist_node.h
deleted file mode 100644
index fcdf22c45c..0000000000
--- a/include/llvm/ADT/alist_node.h
+++ /dev/null
@@ -1,123 +0,0 @@
-//==- llvm/ADT/alist_node.h - Next/Prev helper class for alist ---*- C++ -*-==//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines the alist_node class template, which is used by the alist
-// class template to provide next/prev pointers for arbitrary objects.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ADT_ALIST_NODE_H
-#define LLVM_ADT_ALIST_NODE_H
-
-#include "llvm/ADT/ilist.h"
-#include "llvm/Support/AlignOf.h"
-#include "llvm/Support/DataTypes.h"
-#include <cassert>
-
-namespace llvm {
-
-/// alist_node - This is a utility class used by alist. It holds prev and next
-/// pointers for use with ilists, as well as storage for objects as large as
-/// LargestT, that are in T's inheritance tree.
-///
-template<class T, class LargestT = T>
-class alist_node {
-  alist_node *Prev, *Next;
-
-public:
-  alist_node() : Prev(0), Next(0) {}
-
-  alist_node *getPrev() const { return Prev; }
-  alist_node *getNext() const { return Next; }
-  void setPrev(alist_node *N) { Prev = N; }
-  void setNext(alist_node *N) { Next = N; }
-
-  union {
-    char Bytes[sizeof(LargestT)];
-    long long L;
-    void *P;
-  } Storage;
-
-  template<class SubClass>
-  SubClass *getElement(SubClass *) {
-    assert(sizeof(SubClass) <= sizeof(LargestT));
-    return reinterpret_cast<SubClass*>(&Storage.Bytes);
-  }
-
-  template<class SubClass>
-  const SubClass *getElement(SubClass *) const {
-    assert(sizeof(SubClass) <= sizeof(LargestT));
-    return reinterpret_cast<const SubClass*>(&Storage.Bytes);
-  }
-
-  // This code essentially does offsetof, but actual offsetof hits an ICE in
-  // GCC 4.0 relating to offsetof being used inside a template.
-  static alist_node* getNode(T *D) {
-    return reinterpret_cast<alist_node*>(reinterpret_cast<char*>(D) -
-                                                (uintptr_t)&getNull()->Storage);
-  }
-  static const alist_node* getNode(const T *D) {
-    return reinterpret_cast<alist_node*>(reinterpret_cast<char*>(D) -
-                                                (uintptr_t)&getNull()->Storage);
-  }
-private:
-  static alist_node* getNull() { return 0; }
-};
-
-// A specialization of ilist_traits for alist_nodes.
-template<class T, class LargestT>
-class ilist_traits<alist_node<T, LargestT> > {
-public:
-  typedef alist_node<T, LargestT> NodeTy;
-
-protected:
-  // Allocate a sentinel inside the traits class. This works
-  // because iplist carries an instance of the traits class.
-  NodeTy Sentinel;
-
-public:
-  static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); }
-  static NodeTy *getNext(NodeTy *N) { return N->getNext(); }
-  static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); }
-  static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); }
-
-  static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); }
-  static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); }
-
-  NodeTy *createSentinel() const {
-    assert(Sentinel.getPrev() == 0);
-    assert(Sentinel.getNext() == 0);
-    return const_cast<NodeTy*>(&Sentinel);
-  }
-
-  void destroySentinel(NodeTy *N) {
-    assert(N == &Sentinel); N = N;
-    Sentinel.setPrev(0);
-    Sentinel.setNext(0);
-  }
-
-  void addNodeToList(NodeTy *) {}
-  void removeNodeFromList(NodeTy *) {}
-  void transferNodesFromList(iplist<NodeTy, ilist_traits> &,
-                             ilist_iterator<NodeTy> /*first*/,
-                             ilist_iterator<NodeTy> /*last*/) {}
-
-  // Ideally we wouldn't implement this, but ilist's clear calls it,
-  // which is called from ilist's destructor. We won't ever call
-  // either of those with a non-empty list, but statically this
-  // method needs to exist.
-  void deleteNode(NodeTy *) { assert(0); }
-
-private:
-  static NodeTy *createNode(const NodeTy &V); // do not implement
-};
-
-}
-
-#endif
diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h
index 41253e030c..3ffc8010ee 100644
--- a/include/llvm/ADT/ilist.h
+++ b/include/llvm/ADT/ilist.h
@@ -47,10 +47,11 @@ namespace llvm {
 template<typename NodeTy, typename Traits> class iplist;
 template<typename NodeTy> class ilist_iterator;
 
-// Template traits for intrusive list.  By specializing this template class, you
-// can change what next/prev fields are used to store the links...
+/// ilist_nextprev_traits - A fragment for template traits for intrusive list
+/// that provides default next/prev implementations for common operations.
+///
 template<typename NodeTy>
-struct ilist_traits {
+struct ilist_nextprev_traits {
   static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); }
   static NodeTy *getNext(NodeTy *N) { return N->getNext(); }
   static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); }
@@ -58,25 +59,43 @@ struct ilist_traits {
 
   static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); }
   static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); }
+};
 
-  static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); }
-  static void deleteNode(NodeTy *V) { delete V; }
-
+/// ilist_sentinel_traits - A fragment for template traits for intrusive list
+/// that provides default sentinel implementations for common operations.
+///
+template<typename NodeTy>
+struct ilist_sentinel_traits {
   static NodeTy *createSentinel() { return new NodeTy(); }
   static void destroySentinel(NodeTy *N) { delete N; }
+};
+
+/// ilist_default_traits - Default template traits for intrusive list.
+/// By inheriting from this, you can easily use default implementations
+/// for all common operations.
+///
+template<typename NodeTy>
+struct ilist_default_traits : ilist_nextprev_traits<NodeTy>,
+                              ilist_sentinel_traits<NodeTy> {
+  static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); }
+  static void deleteNode(NodeTy *V) { delete V; }
 
   void addNodeToList(NodeTy *NTy) {}
   void removeNodeFromList(NodeTy *NTy) {}
-  void transferNodesFromList(iplist<NodeTy, ilist_traits> &L2,
+  void transferNodesFromList(ilist_default_traits &SrcTraits,
                              ilist_iterator<NodeTy> first,
                              ilist_iterator<NodeTy> last) {}
 };
 
+// Template traits for intrusive list.  By specializing this template class, you
+// can change what next/prev fields are used to store the links...
+template<typename NodeTy>
+struct ilist_traits : ilist_default_traits<NodeTy> {};
+
 // Const traits are the same as nonconst traits...
 template<typename Ty>
 struct ilist_traits<const Ty> : public ilist_traits<Ty> {};
 
-
 //===----------------------------------------------------------------------===//
 // ilist_iterator<Node> - Iterator for intrusive list.
 //
diff --git a/include/llvm/ADT/ilist_node.h b/include/llvm/ADT/ilist_node.h
new file mode 100644
index 0000000000..9e60311706
--- /dev/null
+++ b/include/llvm/ADT/ilist_node.h
@@ -0,0 +1,43 @@
+//==-- llvm/ADT/ilist_node.h - Intrusive Linked List Helper ------*- C++ -*-==//
+// 
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file defines the ilist_node class template, which is a convenient
+// base class for creating classes that can be used with ilists.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_ILIST_NODE_H
+#define LLVM_ADT_ILIST_NODE_H
+
+namespace llvm {
+
+template<typename NodeTy>
+struct ilist_nextprev_traits;
+
+/// ilist_node - Base class that provides next/prev services for nodes
+/// that use ilist_nextprev_traits or ilist_default_traits.
+///
+template<typename NodeTy>
+class ilist_node {
+private:
+  friend struct ilist_nextprev_traits<NodeTy>;
+  NodeTy *Prev, *Next;
+  NodeTy *getPrev() { return Prev; }
+  NodeTy *getNext() { return Next; }
+  const NodeTy *getPrev() const { return Prev; }
+  const NodeTy *getNext() const { return Next; }
+  void setPrev(NodeTy *N) { Prev = N; }
+  void setNext(NodeTy *N) { Next = N; }
+protected:
+  ilist_node() : Prev(0), Next(0) {}
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h
index d9e45ce9a1..2dcc2bebe0 100644
--- a/include/llvm/Analysis/AliasSetTracker.h
+++ b/include/llvm/Analysis/AliasSetTracker.h
@@ -22,6 +22,7 @@
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/hash_map.h"
 #include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
 
 namespace llvm {
 
@@ -33,7 +34,7 @@ class VAArgInst;
 class AliasSetTracker;
 class AliasSet;
 
-class AliasSet {
+class AliasSet : public ilist_node<AliasSet> {
   friend class AliasSetTracker;
 
   class PointerRec;
@@ -118,12 +119,6 @@ class AliasSet {
   // Volatile - True if this alias set contains volatile loads or stores.
   bool Volatile : 1;
 
-  friend struct ilist_traits<AliasSet>;
-  AliasSet *getPrev() const { return Prev; }
-  AliasSet *getNext() const { return Next; }
-  void setPrev(AliasSet *P) { Prev = P; }
-  void setNext(AliasSet *N) { Next = N; }
-
   void addRef() { ++RefCount; }
   void dropRef(AliasSetTracker &AST) {
     assert(RefCount >= 1 && "Invalid reference count detected!");
@@ -197,15 +192,15 @@ public:
   };
 
 private:
-  // Can only be created by AliasSetTracker
+  // Can only be created by AliasSetTracker. Also, ilist creates one
+  // to serve as a sentinel.
+  friend struct ilist_sentinel_traits<AliasSet>;
   AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0),
                AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) {
   }
 
-  AliasSet(const AliasSet &AS) {
-    assert(0 && "Copy ctor called!?!?!");
-    abort();
-  }
+  AliasSet(const AliasSet &AS);        // do not implement
+  void operator=(const AliasSet &AS);  // do not implement
 
   HashNodePair *getSomePointer() const {
     return PtrList;
diff --git a/include/llvm/Argument.h b/include/llvm/Argument.h
index d203a935bd..650bee3d10 100644
--- a/include/llvm/Argument.h
+++ b/include/llvm/Argument.h
@@ -27,12 +27,9 @@ template<typename ValueSubClass, typename ItemParentClass>
 /// in the body of a function, it represents the value of the actual argument
 /// the function was called with.
 /// @brief LLVM Argument representation  
-class Argument : public Value {  // Defined in the Function.cpp file
+class Argument : public Value, public ilist_node<Argument> {
   Function *Parent;
 
-  Argument *Prev, *Next; // Next and Prev links for our intrusive linked list
-  void setNext(Argument *N) { Next = N; }
-  void setPrev(Argument *N) { Prev = N; }
   friend class SymbolTableListTraits<Argument, Function>;
   void setParent(Function *parent);
 
@@ -80,13 +77,6 @@ public:
   static inline bool classof(const Value *V) {
     return V->getValueID() == ArgumentVal;
   }
-  
-private:
-  // getNext/Prev - Return the next or previous argument in the list.
-  Argument *getNext()       { return Next; }
-  const Argument *getNext() const { return Next; }
-  Argument *getPrev()       { return Prev; }
-  const Argument *getPrev() const { return Prev; }
 };
 
 } // End llvm namespace
diff --git a/include/llvm/BasicBlock.h b/include/llvm/BasicBlock.h
index 108f43a767..47478f2009 100644
--- a/include/llvm/BasicBlock.h
+++ b/include/llvm/BasicBlock.h
@@ -49,17 +49,15 @@ template<> struct ilist_traits<Instruction>
 /// modifying a program. However, the verifier will ensure that basic blocks
 /// are "well formed".
 /// @brief LLVM Basic Block Representation
-class BasicBlock : public Value {       // Basic blocks are data objects also
+class BasicBlock : public Value, // Basic blocks are data objects also
+                   public ilist_node<BasicBlock> {
 public:
   typedef iplist<Instruction> InstListType;
 private :
   InstListType InstList;
-  BasicBlock *Prev, *Next; // Next and Prev links for our intrusive linked list
   Function *Parent;
 
   void setParent(Function *parent);
-  void setNext(BasicBlock *N) { Next = N; }
-  void setPrev(BasicBlock *N) { Prev = N; }
   friend class SymbolTableListTraits<BasicBlock, Function>;
 
   BasicBlock(const BasicBlock &);     // Do not implement
@@ -204,14 +202,6 @@ public:
     BasicBlock *Obj = 0;
     return unsigned(reinterpret_cast<uintptr_t>(&Obj->InstList));
   }
-
-private:
-  // getNext/Prev - Return the next or previous basic block in the list.  Access
-  // these with Function::iterator.
-  BasicBlock *getNext()       { return Next; }
-  const BasicBlock *getNext() const { return Next; }
-  BasicBlock *getPrev()       { return Prev; }
-  const BasicBlock *getPrev() const { return Prev; }
 };
 
 inline int 
diff --git a/include/llvm/Bitcode/Archive.h b/include/llvm/Bitcode/Archive.h
index 91684c62e2..6ba11531dd 100644
--- a/include/llvm/Bitcode/Archive.h
+++ b/include/llvm/Bitcode/Archive.h
@@ -18,6 +18,7 @@
 #define LLVM_BITCODE_ARCHIVE_H
 
 #include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
 #include "llvm/System/Path.h"
 #include <map>
 #include <set>
@@ -39,7 +40,7 @@ class ArchiveMemberHeader; // Internal implementation class
 /// construct ArchiveMember instances. You should obtain them from the methods
 /// of the Archive class instead.
 /// @brief This class represents a single archive member.
-class ArchiveMember {
+class ArchiveMember : public ilist_node<ArchiveMember> {
   /// @name Types
   /// @{
   public:
@@ -165,22 +166,9 @@ class ArchiveMember {
     bool replaceWith(const sys::Path &aFile, std::string* ErrMsg);
 
   /// @}
-  /// @name ilist methods - do not use
-  /// @{
-  public:
-    const ArchiveMember *getNext() const { return next; }
-    const ArchiveMember *getPrev() const { return prev; }
-    ArchiveMember *getNext()             { return next; }
-    ArchiveMember *getPrev()             { return prev; }
-    void setPrev(ArchiveMember* p)       { prev = p; }
-    void setNext(ArchiveMember* n)       { next = n; }
-
-  /// @}
   /// @name Data
   /// @{
   private:
-    ArchiveMember*      next;     ///< Pointer to next archive member
-    ArchiveMember*      prev;     ///< Pointer to previous archive member
     Archive*            parent;   ///< Pointer to parent archive
     sys::PathWithStatus path;     ///< Path of file containing the member
     sys::FileStatus     info;     ///< Status info (size,mode,date)
diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h
index f0f9d54af5..8ee75c9c9f 100644
--- a/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/include/llvm/CodeGen/MachineBasicBlock.h
@@ -19,30 +19,34 @@
 #include "llvm/Support/Streams.h"
 
 namespace llvm {
-  class MachineFunction;
+
+class BasicBlock;
+class MachineFunction;
 
 template <>
-struct alist_traits<MachineInstr, MachineInstr> {
-protected:
+class ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> {
+  mutable MachineInstr Sentinel;
+
   // this is only set by the MachineBasicBlock owning the LiveList
   friend class MachineBasicBlock;
   MachineBasicBlock* Parent;
 
-  typedef alist_iterator<MachineInstr> iterator;
-
 public:
-  alist_traits<MachineInstr, MachineInstr>() : Parent(0) { }
+  MachineInstr *createSentinel() const { return &Sentinel; }
+  void destroySentinel(MachineInstr *) const {}
 
   void addNodeToList(MachineInstr* N);
   void removeNodeFromList(MachineInstr* N);
-  void transferNodesFromList(alist_traits &, iterator, iterator);
+  void transferNodesFromList(ilist_traits &SrcTraits,
+                             ilist_iterator<MachineInstr> first,
+                             ilist_iterator<MachineInstr> last);
   void deleteNode(MachineInstr *N);
+private:
+  void createNode(const MachineInstr &);
 };
 
-class BasicBlock;
-
-class MachineBasicBlock {
-  typedef alist<MachineInstr> Instructions;
+class MachineBasicBlock : public ilist_node<MachineBasicBlock> {
+  typedef ilist<MachineInstr> Instructions;
   Instructions Insts;
   const BasicBlock *BB;
   int Number;
@@ -65,6 +69,10 @@ class MachineBasicBlock {
   /// exception handler.
   bool IsLandingPad;
 
+  // Intrusive list support
+  friend class ilist_sentinel_traits<MachineBasicBlock>;
+  MachineBasicBlock() {}
+
   explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb);
 
   ~MachineBasicBlock();
@@ -287,7 +295,7 @@ public:
   void setNumber(int N) { Number = N; }
 
 private:   // Methods used to maintain doubly linked list of blocks...
-  friend struct alist_traits<MachineBasicBlock>;
+  friend struct ilist_traits<MachineBasicBlock>;
 
   // Machine-CFG mutators
 
diff --git a/include/llvm/CodeGen/MachineFunction.h b/include/llvm/CodeGen/MachineFunction.h
index 98f3a94839..7b24600b49 100644
--- a/include/llvm/CodeGen/MachineFunction.h
+++ b/include/llvm/CodeGen/MachineFunction.h
@@ -18,7 +18,7 @@
 #ifndef LLVM_CODEGEN_MACHINEFUNCTION_H
 #define LLVM_CODEGEN_MACHINEFUNCTION_H
 
-#include "llvm/ADT/alist.h"
+#include "llvm/ADT/ilist.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/Support/Annotation.h"
 #include "llvm/Support/Allocator.h"
@@ -34,15 +34,18 @@ class MachineConstantPool;
 class MachineJumpTableInfo;
 
 template <>
-class alist_traits<MachineBasicBlock, MachineBasicBlock> {
-  typedef alist_iterator<MachineBasicBlock> iterator;
+class ilist_traits<MachineBasicBlock>
+    : public ilist_default_traits<MachineBasicBlock> {
+  mutable MachineBasicBlock Sentinel;
 public:
+  MachineBasicBlock *createSentinel() const { return &Sentinel; }
+  void destroySentinel(MachineBasicBlock *) const {}
+
   void addNodeToList(MachineBasicBlock* MBB);
   void removeNodeFromList(MachineBasicBlock* MBB);
-  void transferNodesFromList(alist_traits<MachineBasicBlock> &,
-                             iterator,
-                             iterator) {}
   void deleteNode(MachineBasicBlock *MBB);
+private:
+  void createNode(const MachineBasicBlock &);
 };
 
 /// MachineFunctionInfo - This class can be derived from and used by targets to
@@ -87,11 +90,8 @@ class MachineFunction : private Annotation {
   // Allocation management for basic blocks in function.
   Recycler<MachineBasicBlock> BasicBlockRecycler;
 
-  // Allocation management for memoperands in function.
-  Recycler<MachineMemOperand> MemOperandRecycler;
-
   // List of machine basic blocks in function
-  typedef alist<MachineBasicBlock> BasicBlockListType;
+  typedef ilist<MachineBasicBlock> BasicBlockListType;
   BasicBlockListType BasicBlocks;
 
 public:
@@ -302,15 +302,6 @@ public:
   /// DeleteMachineBasicBlock - Delete the given MachineBasicBlock.
   ///
   void DeleteMachineBasicBlock(MachineBasicBlock *MBB);
-
-  /// CreateMachineMemOperand - Allocate a new MachineMemOperand. Use this
-  /// instead of `new MachineMemOperand'.
-  ///
-  MachineMemOperand *CreateMachineMemOperand(const MachineMemOperand &MMO);
-
-  /// DeleteMachineMemOperand - Delete the given MachineMemOperand.
-  ///
-  void DeleteMachineMemOperand(MachineMemOperand *MMO);
 };
 
 //===--------------------------------------------------------------------===//
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index 31f4974699..bcbcf316d0 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -16,9 +16,12 @@
 #ifndef LLVM_CODEGEN_MACHINEINSTR_H
 #define LLVM_CODEGEN_MACHINEINSTR_H
 
-#include "llvm/ADT/alist.h"
+#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
+#include <list>
 #include <vector>
 
 namespace llvm {
@@ -31,13 +34,13 @@ class MachineFunction;
 //===----------------------------------------------------------------------===//
 /// MachineInstr - Representation of each machine instruction.
 ///
-class MachineInstr {
+class MachineInstr : public ilist_node<MachineInstr> {
   const TargetInstrDesc *TID;           // Instruction descriptor.
   unsigned short NumImplicitOps;        // Number of implicit operands (which
                                         // are determined at construction time).
 
   std::vector<MachineOperand> Operands; // the operands
-  alist<MachineMemOperand> MemOperands; // information on memory references
+  std::list<MachineMemOperand> MemOperands; // information on memory references
   MachineBasicBlock *Parent;            // Pointer to the owning basic block.
 
   // OperandComplete - Return true if it's illegal to add a new operand
@@ -47,8 +50,9 @@ class MachineInstr {
   void operator=(const MachineInstr&); // DO NOT IMPLEMENT
 
   // Intrusive list support
-  friend struct alist_traits<MachineInstr>;
-  friend struct alist_traits<MachineBasicBlock>;
+  friend struct ilist_traits<MachineInstr>;
+  friend struct ilist_traits<MachineBasicBlock>;
+  friend struct ilist_sentinel_traits<MachineInstr>;
   void setParent(MachineBasicBlock *P) { Parent = P; }
 
   /// MachineInstr ctor - This constructor creates a copy of the given
@@ -105,13 +109,13 @@ public:
   unsigned getNumExplicitOperands() const;
   
   /// Access to memory operands of the instruction
-  alist<MachineMemOperand>::iterator memoperands_begin()
+  std::list<MachineMemOperand>::iterator memoperands_begin()
   { return MemOperands.begin(); }
-  alist<MachineMemOperand>::iterator memoperands_end()
+  std::list<MachineMemOperand>::iterator memoperands_end()
   { return MemOperands.end(); }
-  alist<MachineMemOperand>::const_iterator memoperands_begin() const
+  std::list<MachineMemOperand>::const_iterator memoperands_begin() const
   { return MemOperands.begin(); }
-  alist<MachineMemOperand>::const_iterator memoperands_end() const
+  std::list<MachineMemOperand>::const_iterator memoperands_end() const
   { return MemOperands.end(); }
   bool memoperands_empty() const { return MemOperands.empty(); }
 
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 692d9027c5..49dbd4347a 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -15,6 +15,7 @@
 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
 #define LLVM_CODEGEN_SELECTIONDAG_H
 
+#include "llvm/ADT/ilist.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
@@ -26,13 +27,38 @@
 #include <string>
 
 namespace llvm {
-  class AliasAnalysis;
-  class TargetLowering;
-  class TargetMachine;
-  class MachineModuleInfo;
-  class MachineFunction;
-  class MachineConstantPoolValue;
-  class FunctionLoweringInfo;
+
+class AliasAnalysis;
+class TargetLowering;
+class TargetMachine;
+class MachineModuleInfo;
+class MachineFunction;
+class MachineConstantPoolValue;
+class FunctionLoweringInfo;
+
+/// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
+/// pool allocation with recycling.
+///
+typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
+                           AlignOf<MostAlignedSDNode>::Alignment>
+  NodeAllocatorType;
+
+template<> class ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
+  mutable SDNode Sentinel;
+public:
+  ilist_traits() : Sentinel(ISD::DELETED_NODE, SDVTList()) {}
+
+  SDNode *createSentinel() const {
+    return &Sentinel;
+  }
+  static void destroySentinel(SDNode *) {}
+
+  static void deleteNode(SDNode *) {
+    assert(0 && "ilist_traits<SDNode> shouldn't see a deleteNode call!");
+  }
+private:
+  static void createNode(const SDNode &);
+};
 
 /// SelectionDAG class - This is used to represent a portion of an LLVM function
 /// in a low-level Data Dependence DAG representation suitable for instruction
@@ -55,7 +81,12 @@ class SelectionDAG {
   SDValue Root, EntryNode;
 
   /// AllNodes - A linked list of nodes in the current DAG.
-  alist<SDNode, LargestSDNode> &AllNodes;
+  ilist<SDNode> AllNodes;
+
+  /// NodeAllocator - Pool allocation for nodes. The allocator isn't
+  /// allocated inside this class because we want to reuse a single
+  /// recycler across multiple SelectionDAG runs.
+  NodeAllocatorType &NodeAllocator;
 
   /// CSEMap - This structure is used to memoize nodes, automatically performing
   /// CSE with existing nodes with a duplicate is requested.
@@ -71,8 +102,8 @@ class SelectionDAG {
 public:
   SelectionDAG(TargetLowering &tli, MachineFunction &mf, 
                FunctionLoweringInfo &fli, MachineModuleInfo *mmi,
-               alist<SDNode, LargestSDNode> &NodePool)
-  : TLI(tli), MF(mf), FLI(fli), MMI(mmi), AllNodes(NodePool) {
+               NodeAllocatorType &nodeallocator)
+  : TLI(tli), MF(mf), FLI(fli), MMI(mmi), NodeAllocator(nodeallocator) {
     EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
   }
   ~SelectionDAG();
@@ -108,13 +139,13 @@ public:
   ///
   void setGraphColor(const SDNode *N, const char *Color);
 
-  typedef alist<SDNode, LargestSDNode>::const_iterator allnodes_const_iterator;
+  typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
   allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
   allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
-  typedef alist<SDNode, LargestSDNode>::iterator allnodes_iterator;
+  typedef ilist<SDNode>::iterator allnodes_iterator;
   allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
   allnodes_iterator allnodes_end() { return AllNodes.end(); }
-  alist<SDNode, LargestSDNode>::size_type allnodes_size() const {
+  ilist<SDNode>::size_type allnodes_size() const {
     return AllNodes.size();
   }
   
@@ -682,7 +713,6 @@ public:
   SDValue 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, SDValue Op, void *&InsertPos);
diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h
index c384fa512d..668e64eb87 100644
--- a/include/llvm/CodeGen/SelectionDAGISel.h
+++ b/include/llvm/CodeGen/SelectionDAGISel.h
@@ -182,7 +182,7 @@ private:
                             FunctionLoweringInfo &FuncInfo);
   void SelectBasicBlock(BasicBlock *BB, MachineFunction &MF,
                         FunctionLoweringInfo &FuncInfo,
-                        alist<SDNode, LargestSDNode> &AllNodes);
+                        NodeAllocatorType &NodeAllocator);
 
   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 d690732ec2..dbb12947f2 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -25,7 +25,8 @@
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
-#include "llvm/ADT/alist.h"
+#include "llvm/ADT/ilist_node.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/Support/Allocator.h"
@@ -43,6 +44,7 @@ class SDNode;
 class CompileUnitDesc;
 template <typename T> struct DenseMapInfo;
 template <typename T> struct simplify_type;
+template <typename T> class ilist_traits;
 
 /// 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
@@ -1028,7 +1030,7 @@ public:
 
 /// SDNode - Represents one node in the SelectionDAG.
 ///
-class SDNode : public FoldingSetNode {
+class SDNode : public FoldingSetNode, public ilist_node<SDNode> {
 private:
   /// NodeType - The operation that this node performs.
   ///
@@ -1268,6 +1270,7 @@ public:
 
 protected:
   friend class SelectionDAG;
+  friend class ilist_traits<SDNode>;
   
   /// getValueTypeList - Return a pointer to the specified value type.
   ///
@@ -2236,27 +2239,10 @@ template <> struct GraphTraits<SDNode*> {
 ///
 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*) {}
-  void removeNodeFromList(SDNode*) {}
-  void transferNodesFromList(alist_traits &, iterator, iterator) {}
-  void deleteNode(SDNode *N) {
-    N->~SDNode();
-    Allocator.Deallocate(N);
-  }
-};
+/// MostAlignedSDNode - The SDNode class with the greatest alignment
+/// requirement.
+///
+typedef ConstantSDNode MostAlignedSDNode;
 
 namespace ISD {
   /// isNormalLoad - Returns true if the specified node is a non-extending
diff --git a/include/llvm/Function.h b/include/llvm/Function.h
index 2ec38e1d00..9954418ab8 100644
--- a/include/llvm/Function.h
+++ b/include/llvm/Function.h
@@ -51,7 +51,8 @@ template<> struct ilist_traits<Argument>
   static int getListOffset();
 };
 
-class Function : public GlobalValue, public Annotable {
+class Function : public GlobalValue, public Annotable,
+                 public ilist_node<Function> {
 public:
   typedef iplist<Argument> ArgumentListType;
   typedef iplist<BasicBlock> BasicBlockListType;
@@ -76,18 +77,6 @@ private:
   friend class SymbolTableListTraits<Function, Module>;
 
   void setParent(Module *parent);
-  Function *Prev, *Next;
-  void setNext(Function *N) { Next = N; }
-  void setPrev(Function *N) { Prev = N; }
-
-  // getNext/Prev - Return the next or previous function in the list.  These
-  // methods should never be used directly, and are only used to implement the
-  // function list as part of the module.
-  //
-  Function *getNext()             { return Next; }
-  const Function *getNext() const { return Next; }
-  Function *getPrev()             { return Prev; }
-  const Function *getPrev() const { return Prev; }
 
   /// hasLazyArguments/CheckLazyArguments - The argument list of a function is
   /// built on demand, so that the list isn't allocated until the first client
diff --git a/include/llvm/GlobalAlias.h b/include/llvm/GlobalAlias.h
index 7c147eb62a..124cf94fa9 100644
--- a/include/llvm/GlobalAlias.h
+++ b/include/llvm/GlobalAlias.h
@@ -17,6 +17,7 @@
 
 #include "llvm/GlobalValue.h"
 #include "llvm/OperandTraits.h"
+#include "llvm/ADT/ilist_node.h"
 
 namespace llvm {
 
@@ -26,23 +27,13 @@ class PointerType;
 template<typename ValueSubClass, typename ItemParentClass>
   class SymbolTableListTraits;
 
-class GlobalAlias : public GlobalValue {
+class GlobalAlias : public GlobalValue, public ilist_node<GlobalAlias> {
   friend class SymbolTableListTraits<GlobalAlias, Module>;
   void operator=(const GlobalAlias &);     // Do not implement
   GlobalAlias(const GlobalAlias &);     // Do not implement
 
   void setParent(Module *parent);
 
-  GlobalAlias *Prev, *Next;
-  void setNext(GlobalAlias *N) { Next = N; }
-  void setPrev(GlobalAlias *N) { Prev = N; }
-
-  // getNext/Prev - Return the next or previous alias in the list.
-        GlobalAlias *getNext()       { return Next; }
-  const GlobalAlias *getNext() const { return Next; }
-        GlobalAlias *getPrev()       { return Prev; }
-  const GlobalAlias *getPrev() const { return Prev; }
-
 public:
   // allocate space for exactly one operand
   void *operator new(size_t s) {
diff --git a/include/llvm/GlobalVariable.h b/include/llvm/GlobalVariable.h
index a578cd1c09..b6910d54c9 100644
--- a/include/llvm/GlobalVariable.h
+++ b/include/llvm/GlobalVariable.h
@@ -22,6 +22,7 @@
 
 #include "llvm/GlobalValue.h"
 #include "llvm/OperandTraits.h"
+#include "llvm/ADT/ilist_node.h"
 
 namespace llvm {
 
@@ -31,7 +32,7 @@ class PointerType;
 template<typename ValueSubClass, typename ItemParentClass>
   class SymbolTableListTraits;
 
-class GlobalVariable : public GlobalValue {
+class GlobalVariable : public GlobalValue, public ilist_node<GlobalVariable> {
   friend class SymbolTableListTraits<GlobalVariable, Module>;
   void *operator new(size_t, unsigned);       // Do not implement
   void operator=(const GlobalVariable &);     // Do not implement
@@ -39,10 +40,6 @@ class GlobalVariable : public GlobalValue {
 
   void setParent(Module *parent);
 
-  GlobalVariable *Prev, *Next;
-  void setNext(GlobalVariable *N) { Next = N; }
-  void setPrev(GlobalVariable *N) { Prev = N; }
-
   bool isConstantGlobal : 1;           // Is this a global constant?
   bool isThreadLocalSymbol : 1;        // Is this symbol "Thread Local"?
 
@@ -144,12 +141,6 @@ public:
   static inline bool classof(const Value *V) {
     return V->getValueID() == Value::GlobalVariableVal;
   }
-private:
-  // getNext/Prev - Return the next or previous global variable in the list.
-        GlobalVariable *getNext()       { return Next; }
-  const GlobalVariable *getNext() const { return Next; }
-        GlobalVariable *getPrev()       { return Prev; }
-  const GlobalVariable *getPrev() const { return Prev; }
 };
 
 template <>
diff --git a/include/llvm/Instruction.h b/include/llvm/Instruction.h
index 89e3e23499..ac33a68bbf 100644
--- a/include/llvm/Instruction.h
+++ b/include/llvm/Instruction.h
@@ -16,6 +16,7 @@
 #define LLVM_INSTRUCTION_H
 
 #include "llvm/User.h"
+#include "llvm/ADT/ilist_node.h"
 
 namespace llvm {
 
@@ -24,15 +25,11 @@ struct AssemblyAnnotationWriter;
 template<typename ValueSubClass, typename ItemParentClass>
   class SymbolTableListTraits;
 
-class Instruction : public User {
+class Instruction : public User, public ilist_node<Instruction> {
   void operator=(const Instruction &);     // Do not implement
   Instruction(const Instruction &);        // Do not implement
 
   BasicBlock *Parent;
-  Instruction *Prev, *Next; // Next and Prev links for our intrusive linked list
-
-  void setNext(Instruction *N) { Next = N; }
-  void setPrev(Instruction *N) { Prev = N; }
 
   friend class SymbolTableListTraits<Instruction, BasicBlock>;
   void setParent(BasicBlock *P);
@@ -230,14 +227,6 @@ public:
 #define   LAST_OTHER_INST(N)             OtherOpsEnd = N+1
 #include "llvm/Instruction.def"
   };
-  
-private:
-  // getNext/Prev - Return the next or previous instruction in the list.  The
-  // last node in the list is a terminator instruction.
-  Instruction *getNext()             { return Next; }
-  const Instruction *getNext() const { return Next; }
-  Instruction *getPrev()             { return Prev; }
-  const Instruction *getPrev() const { return Prev; }
 };
 
 } // End llvm namespace
diff --git a/include/llvm/Support/Recycler.h b/include/llvm/Support/Recycler.h
index 4750a6d178..3f235b6e72 100644
--- a/include/llvm/Support/Recycler.h
+++ b/include/llvm/Support/Recycler.h
@@ -15,62 +15,81 @@
 #ifndef LLVM_SUPPORT_RECYCLER_H
 #define LLVM_SUPPORT_RECYCLER_H
 
-#include "llvm/ADT/alist_node.h"
+#include "llvm/ADT/ilist.h"
+#include "llvm/Support/AlignOf.h"
+#include <cassert>
 
 namespace llvm {
 
 /// PrintRecyclingAllocatorStats - Helper for RecyclingAllocator for
 /// printing statistics.
 ///
-void PrintRecyclerStats(size_t LargestTypeSize, size_t FreeListSize);
+void PrintRecyclerStats(size_t Size, size_t Align, size_t FreeListSize);
+
+/// RecyclerStruct - Implementation detail for Recycler. This is a
+/// class that the recycler imposes on free'd memory to carve out
+/// next/prev pointers.
+struct RecyclerStruct {
+  RecyclerStruct *Prev, *Next;
+};
+
+template<>
+struct ilist_traits<RecyclerStruct> : ilist_default_traits<RecyclerStruct> {
+  static RecyclerStruct *getPrev(const RecyclerStruct *t) { return t->Prev; }
+  static RecyclerStruct *getNext(const RecyclerStruct *t) { return t->Next; }
+  static void setPrev(RecyclerStruct *t, RecyclerStruct *p) { t->Prev = p; }
+  static void setNext(RecyclerStruct *t, RecyclerStruct *n) { t->Next = n; }
+
+  mutable RecyclerStruct Sentinel;
+  RecyclerStruct *createSentinel() const {
+    return &Sentinel;
+  }
+  static void destroySentinel(RecyclerStruct *) {}
+
+  static void deleteNode(RecyclerStruct *) {
+    assert(0 && "Recycler's ilist_traits shouldn't see a deleteNode call!");
+  }
+};
 
 /// Recycler - This class manages a linked-list of deallocated nodes
 /// and facilitates reusing deallocated memory in place of allocating
-/// new memory. The objects it allocates are stored in alist_node
-/// containers, so they may be used in alists.
+/// new memory.
 ///
-template<class T, class LargestT = T>
+template<class T, size_t Size = sizeof(T), size_t Align = AlignOf<T>::Alignment>
 class Recycler {
-  typedef alist_node<T, LargestT> NodeTy;
-
-  /// FreeListTraits - ilist traits for FreeList.
-  ///
-  struct FreeListTraits : ilist_traits<alist_node<T, LargestT> > {
-    NodeTy &getSentinel() { return this->Sentinel; }
-  };
-
   /// FreeList - Doubly-linked list of nodes that have deleted contents and
   /// are not in active use.
   ///
-  iplist<NodeTy, FreeListTraits> FreeList;
-
-  /// CreateNewNode - Allocate a new node object and initialize its
-  /// prev and next pointers to 0.
-  ///
-  template<class AllocatorType>
-  NodeTy *CreateNewNode(AllocatorType &Allocator) {
-    // Note that we're calling new on the *node*, to initialize its
-    // Next/Prev pointers, not new on the end-user object.
-    return new (Allocator.Allocate<NodeTy>()) NodeTy();
-  }
+  iplist<RecyclerStruct> FreeList;
 
 public:
-  ~Recycler() { assert(FreeList.empty()); }
+  ~Recycler() {
+    // If this fails, either the callee has lost track of some allocation,
+    // or the callee isn't tracking allocations and should just call
+    // clear() before deleting the Recycler.
+    assert(FreeList.empty() && "Non-empty recycler deleted!");
+  }
 
+  /// clear - Release all the tracked allocations to the allocator. The
+  /// recycler must be free of any tracked allocations before being
+  /// deleted; calling clear is one way to ensure this.
   template<class AllocatorType>
   void clear(AllocatorType &Allocator) {
-    while (!FreeList.empty())
-      Allocator.Deallocate(FreeList.remove(FreeList.begin()));
+    while (!FreeList.empty()) {
+      T *t = reinterpret_cast<T *>(FreeList.remove(FreeList.begin()));
+      Allocator.Deallocate(t);
+    }
   }
 
   template<class SubClass, class AllocatorType>
   SubClass *Allocate(AllocatorType &Allocator) {
-    NodeTy *N = !FreeList.empty() ?
-                FreeList.remove(FreeList.front()) :
-                CreateNewNode(Allocator);
-    assert(N->getPrev() == 0);
-    assert(N->getNext() == 0);
-    return N->getElement((SubClass*)0);
+    assert(sizeof(SubClass) <= Size &&
+           "Recycler allocation size is less than object size!");
+    assert(AlignOf<SubClass>::Alignment <= Align &&
+           "Recycler allocation alignment is less than object alignment!");
+    return !FreeList.empty() ?
+           reinterpret_cast<SubClass *>(FreeList.remove(FreeList.begin())) :
+           static_cast<SubClass *>(Allocator.Allocate(Size, Align));
   }
 
   template<class AllocatorType>
@@ -80,14 +99,11 @@ public:
 
   template<class SubClass, class AllocatorType>
   void Deallocate(AllocatorType & /*Allocator*/, SubClass* Element) {
-    NodeTy *N = NodeTy::getNode(Element);
-    assert(N->getPrev() == 0);
-    assert(N->getNext() == 0);
-    FreeList.push_front(N);
+    FreeList.push_front(reinterpret_cast<RecyclerStruct *>(Element));
   }
 
   void PrintStats() {
-    PrintRecyclerStats(sizeof(LargestT), FreeList.size());
+    PrintRecyclerStats(Size, Align, FreeList.size());
   }
 };
 
diff --git a/include/llvm/Support/RecyclingAllocator.h b/include/llvm/Support/RecyclingAllocator.h
index 071a61d9dc..8e957f1b26 100644
--- a/include/llvm/Support/RecyclingAllocator.h
+++ b/include/llvm/Support/RecyclingAllocator.h
@@ -22,12 +22,13 @@ namespace llvm {
 /// RecyclingAllocator - This class wraps an Allocator, adding the
 /// functionality of recycling deleted objects.
 ///
-template<class AllocatorType, class T, class LargestT = T>
+template<class AllocatorType, class T,
+         size_t Size = sizeof(T), size_t Align = AlignOf<T>::Alignment>
 class RecyclingAllocator {
 private:
   /// Base - Implementation details.
   ///
-  Recycler<T, LargestT> Base;
+  Recycler<T, Size, Align> Base;
 
   /// Allocator - The wrapped allocator.
   ///
diff --git a/include/llvm/SymbolTableListTraits.h b/include/llvm/SymbolTableListTraits.h
index 7d747d4c5e..911d1ce19d 100644
--- a/include/llvm/SymbolTableListTraits.h
+++ b/include/llvm/SymbolTableListTraits.h
@@ -25,6 +25,8 @@
 #ifndef LLVM_SYMBOLTABLELISTTRAITS_H
 #define LLVM_SYMBOLTABLELISTTRAITS_H
 
+#include "llvm/ADT/ilist.h"
+
 namespace llvm {
 
 template<typename NodeTy> class ilist_iterator;
@@ -37,7 +39,7 @@ template<typename Ty> struct ilist_traits;
 //                  inherit from ilist_traits<ValueSubClass>
 //
 template<typename ValueSubClass, typename ItemParentClass>
-class SymbolTableListTraits {
+class SymbolTableListTraits : public ilist_default_traits<ValueSubClass> {
   typedef ilist_traits<ValueSubClass> TraitsClass;
 public:
   SymbolTableListTraits() {}
@@ -48,26 +50,14 @@ public:
     return reinterpret_cast<ItemParentClass*>(reinterpret_cast<char*>(this)-
                                               TraitsClass::getListOffset());
   }
-  static ValueSubClass *getPrev(ValueSubClass *V) { return V->getPrev(); }
-  static ValueSubClass *getNext(ValueSubClass *V) { return V->getNext(); }
-  static const ValueSubClass *getPrev(const ValueSubClass *V) {
-    return V->getPrev();
-  }
-  static const ValueSubClass *getNext(const ValueSubClass *V) {
-    return V->getNext();
-  }
 
   void deleteNode(ValueSubClass *V) {
     delete V;
   }
 
-  static void setPrev(ValueSubClass *V, ValueSubClass *P) { V->setPrev(P); }
-  static void setNext(ValueSubClass *V, ValueSubClass *N) { V->setNext(N); }
-
   void addNodeToList(ValueSubClass *V);
   void removeNodeFromList(ValueSubClass *V);
-  void transferNodesFromList(iplist<ValueSubClass,
-                             ilist_traits<ValueSubClass> > &L2,
+  void transferNodesFromList(ilist_traits<ValueSubClass> &L2,
                              ilist_iterator<ValueSubClass> first,
                              ilist_iterator<ValueSubClass> last);
 //private:
diff --git a/lib/Archive/Archive.cpp b/lib/Archive/Archive.cpp
index a0e5eedc9c..776f4dd367 100644
--- a/lib/Archive/Archive.cpp
+++ b/lib/Archive/Archive.cpp
@@ -43,7 +43,7 @@ ArchiveMember::getMemberSize() const {
 // This default constructor is only use by the ilist when it creates its
 // sentry node. We give it specific static values to make it stand out a bit.
 ArchiveMember::ArchiveMember()
-  : next(0), prev(0), parent(0), path("--invalid--"), flags(0), data(0)
+  : parent(0), path("--invalid--"), flags(0), data(0)
 {
   info.user = sys::Process::GetCurrentUserId();
   info.group = sys::Process::GetCurrentGroupId();
@@ -58,7 +58,7 @@ ArchiveMember::ArchiveMember()
 // This is required because correctly setting the data may depend on other
 // things in the Archive.
 ArchiveMember::ArchiveMember(Archive* PAR)
-  : next(0), prev(0), parent(PAR), path(), flags(0), data(0)
+  : parent(PAR), path(), flags(0), data(0)
 {
 }
 
diff --git a/lib/Archive/ArchiveReader.cpp b/lib/Archive/ArchiveReader.cpp
index 1ded9e5c4c..8d607f0df7 100644
--- a/lib/Archive/ArchiveReader.cpp
+++ b/lib/Archive/ArchiveReader.cpp
@@ -218,8 +218,6 @@ Archive::parseMemberHeader(const char*& At, const char* End, std::string* error)
   ArchiveMember* member = new ArchiveMember(this);
 
   // Fill in fields of the ArchiveMember
-  member->next = 0;
-  member->prev = 0;
   member->parent = this;
   member->path.set(pathname);
   member->info.fileSize = MemberSize;
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index baaed71d23..fde27b07a8 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -828,7 +828,7 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li,
 
     // If the instruction accesses memory and the memory could be non-constant,
     // assume the instruction is not rematerializable.
-    for (alist<MachineMemOperand>::const_iterator I = MI->memoperands_begin(),
+    for (std::list<MachineMemOperand>::const_iterator I = MI->memoperands_begin(),
          E = MI->memoperands_end(); I != E; ++I) {
       const MachineMemOperand &MMO = *I;
       if (MMO.isVolatile() || MMO.isStore())
diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp
index 9a9f5b9271..5cfeeb63a7 100644
--- a/lib/CodeGen/MachineBasicBlock.cpp
+++ b/lib/CodeGen/MachineBasicBlock.cpp
@@ -24,7 +24,7 @@ using namespace llvm;
 
 MachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb)
   : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false) {
-  Insts.getTraits().Parent = this;
+  Insts.Parent = this;
 }
 
 MachineBasicBlock::~MachineBasicBlock() {
@@ -43,7 +43,7 @@ std::ostream& llvm::operator<<(std::ostream &OS, const MachineBasicBlock &MBB) {
 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
 /// gets the next available unique MBB number. If it is removed from a
 /// MachineFunction, it goes back to being #-1.
-void alist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock* N) {
+void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock* N) {
   MachineFunction &MF = *N->getParent();
   N->Number = MF.addToMBBNumbering(N);
 
@@ -55,7 +55,7 @@ void alist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock* N) {
   LeakDetector::removeGarbageObject(N);
 }
 
-void alist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock* N) {
+void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock* N) {
   N->getParent()->removeFromMBBNumbering(N->Number);
   N->Number = -1;
   LeakDetector::addGarbageObject(N);
@@ -65,7 +65,7 @@ void alist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock* N) {
 /// addNodeToList (MI) - When we add an instruction to a basic block
 /// list, we update its parent pointer and add its operands from reg use/def
 /// lists if appropriate.
-void alist_traits<MachineInstr>::addNodeToList(MachineInstr* N) {
+void ilist_traits<MachineInstr>::addNodeToList(MachineInstr* N) {
   assert(N->getParent() == 0 && "machine instruction already in a basic block");
   N->setParent(Parent);
   
@@ -80,7 +80,7 @@ void alist_traits<MachineInstr>::addNodeToList(MachineInstr* N) {
 /// removeNodeFromList (MI) - When we remove an instruction from a basic block
 /// list, we update its parent pointer and remove its operands from reg use/def
 /// lists if appropriate.
-void alist_traits<MachineInstr>::removeNodeFromList(MachineInstr* N) {
+void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr* N) {
   assert(N->getParent() != 0 && "machine instruction not in a basic block");
 
   // Remove from the use/def lists.
@@ -94,35 +94,23 @@ void alist_traits<MachineInstr>::removeNodeFromList(MachineInstr* N) {
 /// transferNodesFromList (MI) - When moving a range of instructions from one
 /// MBB list to another, we need to update the parent pointers and the use/def
 /// lists.
-void alist_traits<MachineInstr>::transferNodesFromList(
-      alist_traits<MachineInstr>& fromList,
+void ilist_traits<MachineInstr>::transferNodesFromList(
+      ilist_traits<MachineInstr>& fromList,
       MachineBasicBlock::iterator first,
       MachineBasicBlock::iterator last) {
+  assert(Parent->getParent() == fromList.Parent->getParent() &&
+        "MachineInstr parent mismatch!");
+
   // Splice within the same MBB -> no change.
   if (Parent == fromList.Parent) return;
 
   // If splicing between two blocks within the same function, just update the
   // parent pointers.
-  if (Parent->getParent() == fromList.Parent->getParent()) {
-    for (; first != last; ++first)
-      first->setParent(Parent);
-    return;
-  }
-  
-  // Otherwise, we have to update the parent and the use/def lists.  The common
-  // case when this occurs is if we're splicing from a block in a MF to a block
-  // that is not in an MF.
-  bool HasOldMF = fromList.Parent->getParent() != 0;
-  MachineFunction *NewMF = Parent->getParent();
-  
-  for (; first != last; ++first) {
-    if (HasOldMF) first->RemoveRegOperandsFromUseLists();
+  for (; first != last; ++first)
     first->setParent(Parent);
-    if (NewMF) first->AddRegOperandsToUseLists(NewMF->getRegInfo());
-  }
 }
 
-void alist_traits<MachineInstr>::deleteNode(MachineInstr* MI) {
+void ilist_traits<MachineInstr>::deleteNode(MachineInstr* MI) {
   assert(!MI->getParent() && "MI is still in a block!");
   Parent->getParent()->DeleteMachineInstr(MI);
 }
diff --git a/lib/CodeGen/MachineFunction.cpp b/lib/CodeGen/MachineFunction.cpp
index 2cac96a4a8..b243297253 100644
--- a/lib/CodeGen/MachineFunction.cpp
+++ b/lib/CodeGen/MachineFunction.cpp
@@ -102,7 +102,7 @@ FunctionPass *llvm::createMachineCodeDeleter() {
 // MachineFunction implementation
 //===---------------------------------------------------------------------===//
 
-void alist_traits<MachineBasicBlock>::deleteNode(MachineBasicBlock *MBB) {
+void ilist_traits<MachineBasicBlock>::deleteNode(MachineBasicBlock *MBB) {
   MBB->getParent()->DeleteMachineBasicBlock(MBB);
 }
 
@@ -131,7 +131,6 @@ MachineFunction::~MachineFunction() {
   BasicBlocks.clear();
   InstructionRecycler.clear(Allocator);
   BasicBlockRecycler.clear(Allocator);
-  MemOperandRecycler.clear(Allocator);
   RegInfo->~MachineRegisterInfo();        Allocator.Deallocate(RegInfo);
   if (MFInfo) {
     MFInfo->~MachineFunctionInfo();       Allocator.Deallocate(MFInfo);
@@ -234,23 +233,6 @@ MachineFunction::DeleteMachineBasicBlock(MachineBasicBlock *MBB) {
   BasicBlockRecycler.Deallocate(Allocator, MBB);
 }
 
-/// CreateMachineMemOperand - Allocate a new MachineMemOperand. Use this
-/// instead of `new MachineMemOperand'.
-///
-MachineMemOperand *
-MachineFunction::CreateMachineMemOperand(const MachineMemOperand &MMO) {
-  return new (MemOperandRecycler.Allocate<MachineMemOperand>(Allocator))
-             MachineMemOperand(MMO);
-}
-
-/// DeleteMachineMemOperand - Delete the given MachineMemOperand.
-///
-void
-MachineFunction::DeleteMachineMemOperand(MachineMemOperand *MO) {
-  MO->~MachineMemOperand();
-  MemOperandRecycler.Deallocate(Allocator, MO);
-}
-
 void MachineFunction::dump() const {
   print(*cerr.stream());
 }
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index d577582637..c952293976 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -322,7 +322,7 @@ MachineInstr::MachineInstr(MachineFunction &MF, const MachineInstr &MI)
   NumImplicitOps = MI.NumImplicitOps;
 
   // Add memory operands.
-  for (alist<MachineMemOperand>::const_iterator i = MI.memoperands_begin(),
+  for (std::list<MachineMemOperand>::const_iterator i = MI.memoperands_begin(),
        j = MI.memoperands_end(); i != j; ++i)
     addMemOperand(MF, *i);
 
@@ -506,13 +506,12 @@ void MachineInstr::RemoveOperand(unsigned OpNo) {
 /// referencing arbitrary storage.
 void MachineInstr::addMemOperand(MachineFunction &MF,
                                  const MachineMemOperand &MO) {
-  MemOperands.push_back(MF.CreateMachineMemOperand(MO));
+  MemOperands.push_back(MO);
 }
 
 /// clearMemOperands - Erase all of this MachineInstr's MachineMemOperands.
 void MachineInstr::clearMemOperands(MachineFunction &MF) {
-  while (!MemOperands.empty())
-    MF.DeleteMachineMemOperand(MemOperands.remove(MemOperands.begin()));
+  MemOperands.clear();
 }
 
 
@@ -731,7 +730,7 @@ void MachineInstr::print(std::ostream &OS, const TargetMachine *TM) const {
 
   if (!memoperands_empty()) {
     OS << ", Mem:";
-    for (alist<MachineMemOperand>::const_iterator i = memoperands_begin(),
+    for (std::list<MachineMemOperand>::const_iterator i = memoperands_begin(),
          e = memoperands_end(); i != e; ++i) {
       const MachineMemOperand &MRO = *i;
       const Value *V = MRO.getValue();
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index c99d504f27..f8c11456d9 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -468,11 +468,6 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) {
 //                              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() {
@@ -527,7 +522,7 @@ void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
     N->NumOperands = 0;
     
     // Finally, remove N itself.
-    AllNodes.erase(N);
+    AllNodes.remove(N);
   }
 }
 
@@ -558,7 +553,7 @@ void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
   N->OperandList = 0;
   N->NumOperands = 0;
   
-  AllNodes.erase(N);
+  AllNodes.remove(N);
 }
 
 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
@@ -772,14 +767,13 @@ unsigned SelectionDAG::getMVTAlignment(MVT VT) const {
 
 SelectionDAG::~SelectionDAG() {
   while (!AllNodes.empty()) {
-    SDNode *N = AllNodes.begin();
+    SDNode *N = AllNodes.remove(AllNodes.begin());
     N->SetNextInBucket(0);
     if (N->OperandsNeedDelete) {
       delete [] N->OperandList;
     }
     N->OperandList = 0;
     N->NumOperands = 0;
-    AllNodes.pop_front();
   }
 }
 
@@ -813,7 +807,7 @@ SDValue SelectionDAG::getConstant(const APInt &Val, MVT VT, bool isT) {
     if (!VT.isVector())
       return SDValue(N, 0);
   if (!N) {
-    N = getAllocator().Allocate<ConstantSDNode>();
+    N = NodeAllocator.Allocate<ConstantSDNode>();
     new (N) ConstantSDNode(isT, Val, EltVT);
     CSEMap.InsertNode(N, IP);
     AllNodes.push_back(N);
@@ -852,7 +846,7 @@ SDValue SelectionDAG::getConstantFP(const APFloat& V, MVT VT, bool isTarget) {
     if (!VT.isVector())
       return SDValue(N, 0);
   if (!N) {
-    N = getAllocator().Allocate<ConstantFPSDNode>();
+    N = NodeAllocator.Allocate<ConstantFPSDNode>();
     new (N) ConstantFPSDNode(isTarget, V, EltVT);
     CSEMap.InsertNode(N, IP);
     AllNodes.push_back(N);
@@ -900,7 +894,7 @@ SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
    return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<GlobalAddressSDNode>();
+  SDNode *N = NodeAllocator.Allocate<GlobalAddressSDNode>();
   new (N) GlobalAddressSDNode(isTargetGA, GV, VT, Offset);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -915,7 +909,7 @@ SDValue SelectionDAG::getFrameIndex(int FI, MVT VT, bool isTarget) {
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<FrameIndexSDNode>();
+  SDNode *N = NodeAllocator.Allocate<FrameIndexSDNode>();
   new (N) FrameIndexSDNode(FI, VT, isTarget);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -930,7 +924,7 @@ SDValue SelectionDAG::getJumpTable(int JTI, MVT VT, bool isTarget){
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<JumpTableSDNode>();
+  SDNode *N = NodeAllocator.Allocate<JumpTableSDNode>();
   new (N) JumpTableSDNode(JTI, VT, isTarget);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -949,7 +943,7 @@ SDValue SelectionDAG::getConstantPool(Constant *C, MVT VT,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<ConstantPoolSDNode>();
+  SDNode *N = NodeAllocator.Allocate<ConstantPoolSDNode>();
   new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -969,7 +963,7 @@ SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, MVT VT,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<ConstantPoolSDNode>();
+  SDNode *N = NodeAllocator.Allocate<ConstantPoolSDNode>();
   new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -984,7 +978,7 @@ SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<BasicBlockSDNode>();
+  SDNode *N = NodeAllocator.Allocate<BasicBlockSDNode>();
   new (N) BasicBlockSDNode(MBB);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -998,7 +992,7 @@ SDValue SelectionDAG::getArgFlags(ISD::ArgFlagsTy Flags) {
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<ARG_FLAGSSDNode>();
+  SDNode *N = NodeAllocator.Allocate<ARG_FLAGSSDNode>();
   new (N) ARG_FLAGSSDNode(Flags);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -1013,7 +1007,7 @@ SDValue SelectionDAG::getValueType(MVT VT) {
     ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT()];
 
   if (N) return SDValue(N, 0);
-  N = getAllocator().Allocate<VTSDNode>();
+  N = NodeAllocator.Allocate<VTSDNode>();
   new (N) VTSDNode(VT);
   AllNodes.push_back(N);
   return SDValue(N, 0);
@@ -1022,7 +1016,7 @@ SDValue SelectionDAG::getValueType(MVT VT) {
 SDValue SelectionDAG::getExternalSymbol(const char *Sym, MVT VT) {
   SDNode *&N = ExternalSymbols[Sym];
   if (N) return SDValue(N, 0);
-  N = getAllocator().Allocate<ExternalSymbolSDNode>();
+  N = NodeAllocator.Allocate<ExternalSymbolSDNode>();
   new (N) ExternalSymbolSDNode(false, Sym, VT);
   AllNodes.push_back(N);
   return SDValue(N, 0);
@@ -1031,7 +1025,7 @@ SDValue SelectionDAG::getExternalSymbol(const char *Sym, MVT VT) {
 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, MVT VT) {
   SDNode *&N = TargetExternalSymbols[Sym];
   if (N) return SDValue(N, 0);
-  N = getAllocator().Allocate<ExternalSymbolSDNode>();
+  N = NodeAllocator.Allocate<ExternalSymbolSDNode>();
   new (N) ExternalSymbolSDNode(true, Sym, VT);
   AllNodes.push_back(N);
   return SDValue(N, 0);
@@ -1042,7 +1036,7 @@ SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
     CondCodeNodes.resize(Cond+1);
 
   if (CondCodeNodes[Cond] == 0) {
-    CondCodeSDNode *N = getAllocator().Allocate<CondCodeSDNode>();
+    CondCodeSDNode *N = NodeAllocator.Allocate<CondCodeSDNode>();
     new (N) CondCodeSDNode(Cond);
     CondCodeNodes[Cond] = N;
     AllNodes.push_back(N);
@@ -1057,7 +1051,7 @@ SDValue SelectionDAG::getRegister(unsigned RegNo, MVT VT) {
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<RegisterSDNode>();
+  SDNode *N = NodeAllocator.Allocate<RegisterSDNode>();
   new (N) RegisterSDNode(RegNo, VT);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -1065,9 +1059,9 @@ SDValue SelectionDAG::getRegister(unsigned RegNo, MVT VT) {
 }
 
 SDValue SelectionDAG::getDbgStopPoint(SDValue Root,
-                                      unsigned Line, unsigned Col,
-                                      const CompileUnitDesc *CU) {
-  SDNode *N = getAllocator().Allocate<DbgStopPointSDNode>();
+                                        unsigned Line, unsigned Col,
+                                        const CompileUnitDesc *CU) {
+  SDNode *N = NodeAllocator.Allocate<DbgStopPointSDNode>();
   new (N) DbgStopPointSDNode(Root, Line, Col, CU);
   AllNodes.push_back(N);
   return SDValue(N, 0);
@@ -1083,7 +1077,7 @@ SDValue SelectionDAG::getLabel(unsigned Opcode,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<LabelSDNode>();
+  SDNode *N = NodeAllocator.Allocate<LabelSDNode>();
   new (N) LabelSDNode(Opcode, Root, LabelID);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -1102,7 +1096,7 @@ SDValue SelectionDAG::getSrcValue(const Value *V) {
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = getAllocator().Allocate<SrcValueSDNode>();
+  SDNode *N = NodeAllocator.Allocate<SrcValueSDNode>();
   new (N) SrcValueSDNode(V);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -1126,7 +1120,7 @@ SDValue SelectionDAG::getMemOperand(const MachineMemOperand &MO) {
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = getAllocator().Allocate<MemOperandSDNode>();
+  SDNode *N = NodeAllocator.Allocate<MemOperandSDNode>();
   new (N) MemOperandSDNode(MO);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -1979,7 +1973,7 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT) {
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<SDNode>();
+  SDNode *N = NodeAllocator.Allocate<SDNode>();
   new (N) SDNode(Opcode, SDNode::getSDVTList(VT));
   CSEMap.InsertNode(N, IP);
   
@@ -2176,11 +2170,11 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, SDValue Operand) {
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDValue(E, 0);
-    N = getAllocator().Allocate<UnarySDNode>();
+    N = NodeAllocator.Allocate<UnarySDNode>();
     new (N) UnarySDNode(Opcode, VTs, Operand);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = getAllocator().Allocate<UnarySDNode>();
+    N = NodeAllocator.Allocate<UnarySDNode>();
     new (N) UnarySDNode(Opcode, VTs, Operand);
   }
 
@@ -2530,11 +2524,11 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT,
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDValue(E, 0);
-    N = getAllocator().Allocate<BinarySDNode>();
+    N = NodeAllocator.Allocate<BinarySDNode>();
     new (N) BinarySDNode(Opcode, VTs, N1, N2);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = getAllocator().Allocate<BinarySDNode>();
+    N = NodeAllocator.Allocate<BinarySDNode>();
     new (N) BinarySDNode(Opcode, VTs, N1, N2);
   }
 
@@ -2599,11 +2593,11 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT,
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDValue(E, 0);
-    N = getAllocator().Allocate<TernarySDNode>();
+    N = NodeAllocator.Allocate<TernarySDNode>();
     new (N) TernarySDNode(Opcode, VTs, N1, N2, N3);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = getAllocator().Allocate<TernarySDNode>();
+    N = NodeAllocator.Allocate<TernarySDNode>();
     new (N) TernarySDNode(Opcode, VTs, N1, N2, N3);
   }
   AllNodes.push_back(N);
@@ -3121,7 +3115,7 @@ SDValue SelectionDAG::getAtomic(unsigned Opcode, SDValue Chain,
   void* IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode* N = getAllocator().Allocate<AtomicSDNode>();
+  SDNode* N = NodeAllocator.Allocate<AtomicSDNode>();
   new (N) AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp, PtrVal, Alignment);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -3152,7 +3146,7 @@ SDValue SelectionDAG::getAtomic(unsigned Opcode, SDValue Chain,
   void* IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode* N = getAllocator().Allocate<AtomicSDNode>();
+  SDNode* N = NodeAllocator.Allocate<AtomicSDNode>();
   new (N) AtomicSDNode(Opcode, VTs, Chain, Ptr, Val, PtrVal, Alignment);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
@@ -3216,7 +3210,7 @@ SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<LoadSDNode>();
+  SDNode *N = NodeAllocator.Allocate<LoadSDNode>();
   new (N) LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset,
                      Alignment, isVolatile);
   CSEMap.InsertNode(N, IP);
@@ -3276,7 +3270,7 @@ SDValue SelectionDAG::getStore(SDValue Chain, SDValue Val,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<StoreSDNode>();
+  SDNode *N = NodeAllocator.Allocate<StoreSDNode>();
   new (N) StoreSDNode(Ops, VTs, ISD::UNINDEXED, false,
                       VT, SV, SVOffset, Alignment, isVolatile);
   CSEMap.InsertNode(N, IP);
@@ -3313,7 +3307,7 @@ SDValue SelectionDAG::getTruncStore(SDValue Chain, SDValue Val,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<StoreSDNode>();
+  SDNode *N = NodeAllocator.Allocate<StoreSDNode>();
   new (N) StoreSDNode(Ops, VTs, ISD::UNINDEXED, true,
                       SVT, SV, SVOffset, Alignment, isVolatile);
   CSEMap.InsertNode(N, IP);
@@ -3339,7 +3333,7 @@ SelectionDAG::getIndexedStore(SDValue OrigStore, SDValue Base,
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
-  SDNode *N = getAllocator().Allocate<StoreSDNode>();
+  SDNode *N = NodeAllocator.Allocate<StoreSDNode>();
   new (N) StoreSDNode(Ops, VTs, AM,
                       ST->isTruncatingStore(), ST->getMemoryVT(),
                       ST->getSrcValue(), ST->getSrcValueOffset(),
@@ -3411,11 +3405,11 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT,
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDValue(E, 0);
-    N = getAllocator().Allocate<SDNode>();
+    N = NodeAllocator.Allocate<SDNode>();
     new (N) SDNode(Opcode, VTs, Ops, NumOps);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = getAllocator().Allocate<SDNode>();
+    N = NodeAllocator.Allocate<SDNode>();
     new (N) SDNode(Opcode, VTs, Ops, NumOps);
   }
   AllNodes.push_back(N);
@@ -3477,31 +3471,31 @@ SDValue SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDValue(E, 0);
     if (NumOps == 1) {
-      N = getAllocator().Allocate<UnarySDNode>();
+      N = NodeAllocator.Allocate<UnarySDNode>();
       new (N) UnarySDNode(Opcode, VTList, Ops[0]);
     } else if (NumOps == 2) {
-      N = getAllocator().Allocate<BinarySDNode>();
+      N = NodeAllocator.Allocate<BinarySDNode>();
       new (N) BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
     } else if (NumOps == 3) {
-      N = getAllocator().Allocate<TernarySDNode>();
+      N = NodeAllocator.Allocate<TernarySDNode>();
       new (N) TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
     } else {
-      N = getAllocator().Allocate<SDNode>();
+      N = NodeAllocator.Allocate<SDNode>();
       new (N) SDNode(Opcode, VTList, Ops, NumOps);
     }
     CSEMap.InsertNode(N, IP);
   } else {
     if (NumOps == 1) {
-      N = getAllocator().Allocate<UnarySDNode>();
+      N = NodeAllocator.Allocate<UnarySDNode>();
       new (N) UnarySDNode(Opcode, VTList, Ops[0]);
     } else if (NumOps == 2) {
-      N = getAllocator().Allocate<BinarySDNode>();
+      N = NodeAllocator.Allocate<BinarySDNode>();
       new (N) BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
     } else if (NumOps == 3) {
-      N = getAllocator().Allocate<TernarySDNode>();
+      N = NodeAllocator.Allocate<TernarySDNode>();
       new (N) TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
     } else {
-      N = getAllocator().Allocate<SDNode>();
+      N = NodeAllocator.Allocate<SDNode>();
       new (N) SDNode(Opcode, VTList, Ops, NumOps);
     }
   }
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index 7d34ca2744..c0652da35d 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -5425,24 +5425,23 @@ void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) {
 
 void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF,
                                             FunctionLoweringInfo &FuncInfo) {
-  // Define AllNodes here so that memory allocation is reused for
+  // Define NodeAllocator here so that memory allocation is reused for
   // each basic block.
-  alist<SDNode, LargestSDNode> AllNodes;
+  NodeAllocatorType NodeAllocator;
 
-  for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
-    SelectBasicBlock(I, MF, FuncInfo, AllNodes);
-    AllNodes.clear();
-  }
+  for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
+    SelectBasicBlock(I, MF, FuncInfo, NodeAllocator);
 }
 
-void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
-                                        FunctionLoweringInfo &FuncInfo,
-                                        alist<SDNode, LargestSDNode> &AllNodes) {
+void
+SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
+                                   FunctionLoweringInfo &FuncInfo,
+                                   NodeAllocatorType &NodeAllocator) {
   std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
   {
     SelectionDAG DAG(TLI, MF, FuncInfo, 
                      getAnalysisToUpdate<MachineModuleInfo>(),
-                     AllNodes);
+                     NodeAllocator);
     CurDAG = &DAG;
   
     // First step, lower LLVM code to some DAG.  This DAG may use operations and
@@ -5478,7 +5477,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
     if (!BitTestCases[i].Emitted) {
       SelectionDAG HSDAG(TLI, MF, FuncInfo, 
                          getAnalysisToUpdate<MachineModuleInfo>(),
-                         AllNodes);
+                         NodeAllocator);
       CurDAG = &HSDAG;
       SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI);
       // Set the current basic block to the mbb we wish to insert the code into
@@ -5493,7 +5492,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
     for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) {
       SelectionDAG BSDAG(TLI, MF, FuncInfo, 
                          getAnalysisToUpdate<MachineModuleInfo>(),
-                         AllNodes);
+                         NodeAllocator);
       CurDAG = &BSDAG;
       SelectionDAGLowering BSDL(BSDAG, TLI, *AA, FuncInfo, GCI);
       // Set the current basic block to the mbb we wish to insert the code into
@@ -5552,7 +5551,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
     if (!JTCases[i].first.Emitted) {
       SelectionDAG HSDAG(TLI, MF, FuncInfo, 
                          getAnalysisToUpdate<MachineModuleInfo>(),
-                         AllNodes);
+                         NodeAllocator);
       CurDAG = &HSDAG;
       SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI);
       // Set the current basic block to the mbb we wish to insert the code into
@@ -5566,7 +5565,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
     
     SelectionDAG JSDAG(TLI, MF, FuncInfo, 
                        getAnalysisToUpdate<MachineModuleInfo>(),
-                       AllNodes);
+                       NodeAllocator);
     CurDAG = &JSDAG;
     SelectionDAGLowering JSDL(JSDAG, TLI, *AA, FuncInfo, GCI);
     // Set the current basic block to the mbb we wish to insert the code into
@@ -5616,7 +5615,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
   for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
     SelectionDAG SDAG(TLI, MF, FuncInfo, 
                       getAnalysisToUpdate<MachineModuleInfo>(),
-                      AllNodes);
+                      NodeAllocator);
     CurDAG = &SDAG;
     SelectionDAGLowering SDL(SDAG, TLI, *AA, FuncInfo, GCI);
     
diff --git a/lib/Support/Allocator.cpp b/lib/Support/Allocator.cpp
index 584ca125b7..db0d8f31e5 100644
--- a/lib/Support/Allocator.cpp
+++ b/lib/Support/Allocator.cpp
@@ -132,8 +132,10 @@ void BumpPtrAllocator::PrintStats() const {
   cerr << "Bytes allocated: " << BytesUsed << "\n";
 }
 
-void llvm::PrintRecyclerStats(size_t LargestTypeSize,
+void llvm::PrintRecyclerStats(size_t Size,
+                              size_t Align,
                               size_t FreeListSize) {
-  cerr << "Recycler element size: " << LargestTypeSize << '\n';
+  cerr << "Recycler element size: " << Size << '\n';
+  cerr << "Recycler element alignment: " << Align << '\n';
   cerr << "Number of elements free for recycling: " << FreeListSize << '\n';
 }
diff --git a/lib/VMCore/BasicBlock.cpp b/lib/VMCore/BasicBlock.cpp
index 64711fea0c..514aa1de23 100644
--- a/lib/VMCore/BasicBlock.cpp
+++ b/lib/VMCore/BasicBlock.cpp
@@ -15,6 +15,7 @@
 #include "llvm/Constants.h"
 #include "llvm/Instructions.h"
 #include "llvm/Type.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/LeakDetector.h"
 #include "llvm/Support/Compiler.h"
@@ -260,7 +261,9 @@ BasicBlock *BasicBlock::splitBasicBlock(iterator I, const std::string &BBName) {
   assert(I != InstList.end() &&
          "Trying to get me to create degenerate basic block!");
 
-  BasicBlock *New = BasicBlock::Create(BBName, getParent(), getNext());
+  BasicBlock *InsertBefore = next(Function::iterator(this))
+                               .getNodePtrUnchecked();
+  BasicBlock *New = BasicBlock::Create(BBName, getParent(), InsertBefore);
 
   // Move all of the specified instructions from the original basic block into
   // the new basic block.
diff --git a/lib/VMCore/SymbolTableListTraitsImpl.h b/lib/VMCore/SymbolTableListTraitsImpl.h
index 2a3b3d835d..72687bb5e0 100644
--- a/lib/VMCore/SymbolTableListTraitsImpl.h
+++ b/lib/VMCore/SymbolTableListTraitsImpl.h
@@ -84,7 +84,7 @@ void SymbolTableListTraits<ValueSubClass,ItemParentClass>
 
 template<typename ValueSubClass, typename ItemParentClass>
 void SymbolTableListTraits<ValueSubClass,ItemParentClass>
-::transferNodesFromList(iplist<ValueSubClass, ilist_traits<ValueSubClass> > &L2,
+::transferNodesFromList(ilist_traits<ValueSubClass> &L2,
                         ilist_iterator<ValueSubClass> first,
                         ilist_iterator<ValueSubClass> last) {
   // We only have to do work here if transferring instructions between BBs