Switch from using an ilist for uses to using a custom doubly linked list.

This list does not provide the ability to go backwards in the list (its
more of an unordered collection, stored in the shape of a list).

This change means that use iterators are now only forward iterators, not
bidirectional.

This improves the memory usage of use lists from '5 + 4*#use' per value to
'1 + 4*#use'.  While it would be better to reduce the multiplied factor,
I'm not smart enough to do so.  This list also has slightly more efficient
operators for manipulating list nodes (a few less loads/stores), due to not
needing to be able to iterate backwards through the list.

This change reduces the memory footprint required to hold 176.gcc from
66.025M -> 57.687M, a 14% reduction.  It also speeds up the compiler,
7.73% in the case of bytecode loading alone (release build loading 176.gcc).


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

1 files changed, 50 insertions, 80 deletions

diff --git a/include/llvm/Use.h b/include/llvm/Use.h
index 26923a26da..bbf523574c 100644
--- a/include/llvm/Use.h
+++ b/include/llvm/Use.h
@@ -16,11 +16,11 @@
 #ifndef LLVM_USE_H
 #define LLVM_USE_H
 
-#include "llvm/ADT/ilist"
+#include "llvm/Support/Casting.h"
+#include "llvm/ADT/iterator"
 
 namespace llvm {
 
-template<typename NodeTy> struct ilist_traits;
 class Value;
 class User;
 
@@ -62,43 +62,28 @@ public:
         Value *operator->()       { return Val; }
   const Value *operator->() const { return Val; }
 
+  Use *getNext() const { return Next; }
 private:
-  // NOTE!! The Next/Prev fields MUST stay at the start of this structure.  The
-  // end-token for the ilist is allocated as JUST the next/prev pair to reduce
-  // memory usage instead of allocating an entire Use.
-  struct NextPrevPtrs {
-    Use *Next, *Prev;
-  } UseLinks;
-
+  Use *Next, **Prev;
   Value *Val;
   User *U;
-  friend struct ilist_traits<Use>;
-};
 
-template<>
-struct ilist_traits<Use> {
-  static Use *getPrev(Use *N) { return N->UseLinks.Prev; }
-  static Use *getNext(Use *N) { return N->UseLinks.Next; }
-  static const Use *getPrev(const Use *N) { return N->UseLinks.Prev; }
-  static const Use *getNext(const Use *N) { return N->UseLinks.Next; }
-  static void setPrev(Use *N, Use *Prev) { N->UseLinks.Prev = Prev; }
-  static void setNext(Use *N, Use *Next) { N->UseLinks.Next = Next; }
-
-  /// createSentinel - this is used to create the end marker for the use list.
-  /// Note that we only allocate a UseLinks structure, which is just enough to
-  /// hold the next/prev pointers.  This saves us 8 bytes of memory for every
-  /// Value allocated.
-  static Use *createSentinel() { return (Use*)new Use::NextPrevPtrs(); }
-  static void destroySentinel(Use *S) { delete (Use::NextPrevPtrs*)S; }
-
-  void addNodeToList(Use *NTy) {}
-  void removeNodeFromList(Use *NTy) {}
-  void transferNodesFromList(iplist<Use, ilist_traits> &L2,
-                             ilist_iterator<Use> first,
-                             ilist_iterator<Use> last) {}
-};
+  void addToList(Use **List) {
+    Next = *List;
+    if (Next) Next->Prev = &Next;
+    Prev = List;
+    *List = this;
+  }
+  void removeFromList() {
+    *Prev = Next;
+    if (Next) Next->Prev = Prev;
+  }
 
+  friend class Value;
+};
 
+// simplify_type - Allow clients to treat uses just like values when using
+// casting operators.
 template<> struct simplify_type<Use> {
   typedef Value* SimpleType;
   static SimpleType getSimplifiedValue(const Use &Val) {
@@ -112,64 +97,49 @@ template<> struct simplify_type<const Use> {
   }
 };
 
-struct UseListIteratorWrapper : public iplist<Use>::iterator {
-  typedef iplist<Use>::iterator Super;
-  UseListIteratorWrapper() {}
-  UseListIteratorWrapper(const Super &RHS) : Super(RHS) {}
 
-  UseListIteratorWrapper &operator=(const Super &RHS) {
-    Super::operator=(RHS);
-    return *this;
-  }
 
-  inline User *operator*() const;
-  User *operator->() const { return operator*(); }
+template<typename UserTy>  // UserTy == 'User' or 'const User'
+class value_use_iterator : public forward_iterator<UserTy*, ptrdiff_t> {
+  typedef forward_iterator<UserTy*, ptrdiff_t> super;
+  typedef value_use_iterator<UserTy> _Self;
+
+  Use *U;
+  value_use_iterator(Use *u) : U(u) {}
+  friend class Value;
+public:
+  typedef typename super::reference reference;
+  typedef typename super::pointer pointer;
 
-  UseListIteratorWrapper operator--() { return Super::operator--(); }
-  UseListIteratorWrapper operator++() { return Super::operator++(); }
+  value_use_iterator(const _Self &I) : U(I.U) {}
+  value_use_iterator() {}
 
-  UseListIteratorWrapper operator--(int) {    // postdecrement operators...
-    UseListIteratorWrapper tmp = *this;
-    --*this;
-    return tmp;
+  bool operator==(const _Self &x) const { 
+    return U == x.U;
   }
-  UseListIteratorWrapper operator++(int) {    // postincrement operators...
-    UseListIteratorWrapper tmp = *this;
-    ++*this;
-    return tmp;
+  bool operator!=(const _Self &x) const {
+    return !operator==(x);
   }
-};
-
-struct UseListConstIteratorWrapper : public iplist<Use>::const_iterator {
-  typedef iplist<Use>::const_iterator Super;
-  UseListConstIteratorWrapper() {}
-  UseListConstIteratorWrapper(const Super &RHS) : Super(RHS) {}
 
-  // Allow conversion from non-const to const iterators
-  UseListConstIteratorWrapper(const UseListIteratorWrapper &RHS) : Super(RHS) {}
-  UseListConstIteratorWrapper(const iplist<Use>::iterator &RHS) : Super(RHS) {}
-
-  UseListConstIteratorWrapper &operator=(const Super &RHS) {
-    Super::operator=(RHS);
-    return *this;
+  // Iterator traversal: forward iteration only
+  _Self &operator++() {          // Preincrement
+    assert(U && "Cannot increment end iterator!");
+    U = U->getNext();
+    return *this; 
+  }
+  _Self operator++(int) {        // Postincrement
+    _Self tmp = *this; ++*this; return tmp; 
   }
 
-  inline const User *operator*() const;
-  const User *operator->() const { return operator*(); }
+  // Retrieve a reference to the current SCC
+   UserTy *operator*() const { 
+    assert(U && "Cannot increment end iterator!");
+    return U->getUser();
+  }
 
-  UseListConstIteratorWrapper operator--() { return Super::operator--(); }
-  UseListConstIteratorWrapper operator++() { return Super::operator++(); }
+  UserTy *operator->() const { return operator*(); }
 
-  UseListConstIteratorWrapper operator--(int) {    // postdecrement operators...
-    UseListConstIteratorWrapper tmp = *this;
-    --*this;
-    return tmp;
-  }
-  UseListConstIteratorWrapper operator++(int) {    // postincrement operators...
-    UseListConstIteratorWrapper tmp = *this;
-    ++*this;
-    return tmp;
-  }
+  Use &getUse() const { return *U; }
 };
 
 } // End llvm namespace