1 files changed, 236 insertions, 6 deletions

diff --git a/include/llvm/User.h b/include/llvm/User.h
index d3e4f1ede2..1454779154 100644
--- a/include/llvm/User.h
+++ b/include/llvm/User.h
@@ -23,15 +23,203 @@
 
 namespace llvm {
 
+/*==============================================================================
+
+
+   -----------------------------------------------------------------
+   --- Interaction and relationship between User and Use objects ---
+   -----------------------------------------------------------------
+
+
+A subclass of User can choose between incorporating its Use objects
+or refer to them out-of-line by means of a pointer. A mixed variant
+(some Uses inline others hung off) is impractical and breaks the invariant
+that the Use objects belonging to the same User form a contiguous array.
+
+We have 2 different layouts in the User (sub)classes:
+
+Layout a)
+The Use object(s) are inside (resp. at fixed offset) of the User
+object and there are a fixed number of them.
+
+Layout b)
+The Use object(s) are referenced by a pointer to an
+array from the User object and there may be a variable
+number of them.
+
+Initially each layout will possess a direct pointer to the
+start of the array of Uses. Though not mandatory for layout a),
+we stick to this redundancy for the sake of simplicity.
+The User object will also store the number of Use objects it
+has. (Theoretically this information can also be calculated
+given the scheme presented below.)
+
+Special forms of allocation operators (operator new)
+will enforce the following memory layouts:
+
+
+#  Layout a) will be modelled by prepending the User object
+#  by the Use[] array.
+#      
+#      ...---.---.---.---.-------...
+#        | P | P | P | P | User
+#      '''---'---'---'---'-------'''
+
+
+#  Layout b) will be modelled by pointing at the Use[] array.
+#      
+#      .-------...
+#      | User
+#      '-------'''
+#          |
+#          v
+#          .---.---.---.---...
+#          | P | P | P | P |
+#          '---'---'---'---'''
+
+   (In the above figures 'P' stands for the Use** that
+    is stored in each Use object in the member Use::Prev)
+
+
+Since the Use objects will be deprived of the direct pointer to
+their User objects, there must be a fast and exact method to
+recover it. This is accomplished by the following scheme:
+
+A bit-encoding in the 2 LSBits of the Use::Prev will allow to find the
+start of the User object:
+
+00 --> binary digit 0
+01 --> binary digit 1
+10 --> stop and calc (s)
+11 --> full stop (S)
+
+Given a Use*, all we have to do is to walk till we get
+a stop and we either have a User immediately behind or
+we have to walk to the next stop picking up digits
+and calculating the offset:
+
+.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.----------------
+| 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*)
+'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'----------------
+    |+15                |+10            |+6         |+3     |+1
+    |                   |               |           |       |__>
+    |                   |               |           |__________>
+    |                   |               |______________________>
+    |                   |______________________________________>
+    |__________________________________________________________>
+
+
+Only the significant number of bits need to be stored between the
+stops, so that the worst case is 20 memory accesses when there are
+1000 Use objects.
+
+The following literate Haskell fragment demonstrates the concept:
+
+> import Test.QuickCheck
+> 
+> digits :: Int -> [Char] -> [Char]
+> digits 0 acc = '0' : acc
+> digits 1 acc = '1' : acc
+> digits n acc = digits (n `div` 2) $ digits (n `mod` 2) acc
+> 
+> dist :: Int -> [Char] -> [Char]
+> dist 0 [] = ['S']
+> dist 0 acc = acc
+> dist 1 acc = let r = dist 0 acc in 's' : digits (length r) r
+> dist n acc = dist (n - 1) $ dist 1 acc
+> 
+> takeLast n ss = reverse $ take n $ reverse ss
+> 
+> test = takeLast 40 $ dist 20 []
+> 
+
+Printing <test> gives: "1s100000s11010s10100s1111s1010s110s11s1S"
+
+The reverse algorithm computes the
+length of the string just by examining
+a certain prefix:
+
+> pref :: [Char] -> Int
+> pref "S" = 1
+> pref ('s':'1':rest) = decode 2 1 rest
+> pref (_:rest) = 1 + pref rest
+> 
+> decode walk acc ('0':rest) = decode (walk + 1) (acc * 2) rest
+> decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest
+> decode walk acc _ = walk + acc
+> 
+
+Now, as expected, printing <pref test> gives 40.
+
+We can quickCheck this with following property:
+
+> testcase = dist 2000 []
+> testcaseLength = length testcase
+> 
+> identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr
+>     where arr = takeLast n testcase
+
+As expected <quickCheck identityProp> gives:
+
+*Main> quickCheck identityProp
+OK, passed 100 tests.
+
+Let's be a bit more exhaustive:
+
+> 
+> deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
+> 
+
+And here is the result of <deepCheck identityProp>:
+
+*Main> deepCheck identityProp
+OK, passed 500 tests.
+
+
+To maintain the invariant that the 2 LSBits of each Use** in Use
+never change after being set up, setters of Use::Prev must re-tag the
+new Use** on every modification. Accordingly getters must strip the
+tag bits.
+
+For layout b) instead of the User we will find a pointer (User* with LSBit set).
+Following this pointer brings us to the User. A portable trick will ensure
+that the first bytes of User (if interpreted as a pointer) will never have
+the LSBit set.
+
+==============================================================================*/
+
+/// OperandTraits - Compile-time customization of
+/// operand-related allocators and accessors
+/// for use of the User class
+template <class>
+struct OperandTraits;
+
+class User;
+
+/// OperandTraits<User> - specialization to User
+template <>
+struct OperandTraits<User> {
+  static inline Use *op_begin(User*);
+  static inline Use *op_end(User*);
+  static inline unsigned operands(const User*);
+  template <class U>
+  struct Layout {
+    typedef U overlay;
+  };
+  static inline void *allocate(unsigned);
+};
+
 class User : public Value {
   User(const User &);             // Do not implement
   void *operator new(size_t);     // Do not implement
+  template <unsigned>
+  friend struct HungoffOperandTraits;
 protected:
   /// OperandList - This is a pointer to the array of Users for this operand.
   /// For nodes of fixed arity (e.g. a binary operator) this array will live
-  /// embedded into the derived class.  For nodes of variable arity
-  /// (e.g. ConstantArrays, CallInst, PHINodes, ReturnInst etc), this memory 
-  /// will be dynamically allocated and should be destroyed by the classes 
+  /// prefixed to the derived class.  For nodes of resizable variable arity
+  /// (e.g. PHINodes, SwitchInst etc.), this memory will be dynamically
+  /// allocated and should be destroyed by the classes' 
   /// virtual dtor.
   Use *OperandList;
 
@@ -39,13 +227,43 @@ protected:
   ///
   unsigned NumOperands;
 
-  void *operator new(size_t s, size_t) {
-    return ::operator new(s);
+  void *operator new(size_t s, unsigned Us) {
+    void *Storage = ::operator new(s + sizeof(Use) * Us);
+    Use *Start = static_cast<Use*>(Storage);
+    Use *End = Start + Us;
+    User *Obj = reinterpret_cast<User*>(End);
+    Obj->OperandList = Start;
+    Obj->NumOperands = Us;
+    Use::initTags(Start, End);
+    return Obj;
   }
   User(const Type *Ty, unsigned vty, Use *OpList, unsigned NumOps)
     : Value(Ty, vty), OperandList(OpList), NumOperands(NumOps) {}
-
+  Use *allocHungoffUses(unsigned) const;
+  void dropHungoffUses(Use *U) {
+    if (OperandList == U) {
+      OperandList = 0;
+      NumOperands = 0;
+    }
+    Use::zap(U, U->getImpliedUser(), true);
+  }
 public:
+  ~User() {
+    Use::zap(OperandList, OperandList + NumOperands);
+  }
+  void operator delete(void *Usr) {
+    User *Start = static_cast<User*>(Usr);
+    Use *Storage = static_cast<Use*>(Usr) - Start->NumOperands;
+    ::operator delete(Storage == Start->OperandList
+                      ? Storage
+                      : Usr);
+  }
+  template <unsigned Idx> Use &Op() {
+    return OperandTraits<User>::op_begin(this)[Idx];
+  }
+  template <unsigned Idx> const Use &Op() const {
+    return OperandTraits<User>::op_begin(const_cast<User*>(this))[Idx];
+  }
   Value *getOperand(unsigned i) const {
     assert(i < NumOperands && "getOperand() out of range!");
     return OperandList[i];
@@ -93,6 +311,18 @@ public:
   }
 };
 
+inline Use *OperandTraits<User>::op_begin(User *U) {
+  return U->op_begin();
+}
+
+inline Use *OperandTraits<User>::op_end(User *U) {
+  return U->op_end();
+}
+
+inline unsigned OperandTraits<User>::operands(const User *U) {
+  return U->getNumOperands();
+}
+
 template<> struct simplify_type<User::op_iterator> {
   typedef Value* SimpleType;