include/llvm/User.h

   1 //===-- llvm/User.h - User class definition ---------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This class defines the interface that one who 'use's a Value must implement.
  11 // Each instance of the Value class keeps track of what User's have handles
  12 // to it.
  13 //
  14 //  * Instructions are the largest class of User's.
  15 //  * Constants may be users of other constants (think arrays and stuff)
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #ifndef LLVM_USER_H
  20 #define LLVM_USER_H
  21
  22 #include "llvm/Value.h"
  23
  24 namespace llvm {
  25
  26 /*==============================================================================
  27
  28
  29    -----------------------------------------------------------------
  30    --- Interaction and relationship between User and Use objects ---
  31    -----------------------------------------------------------------
  32
  33
  34 A subclass of User can choose between incorporating its Use objects
  35 or refer to them out-of-line by means of a pointer. A mixed variant
  36 (some Uses inline others hung off) is impractical and breaks the invariant
  37 that the Use objects belonging to the same User form a contiguous array.
  38
  39 We have 2 different layouts in the User (sub)classes:
  40
  41 Layout a)
  42 The Use object(s) are inside (resp. at fixed offset) of the User
  43 object and there are a fixed number of them.
  44
  45 Layout b)
  46 The Use object(s) are referenced by a pointer to an
  47 array from the User object and there may be a variable
  48 number of them.
  49
  50 Initially each layout will possess a direct pointer to the
  51 start of the array of Uses. Though not mandatory for layout a),
  52 we stick to this redundancy for the sake of simplicity.
  53 The User object will also store the number of Use objects it
  54 has. (Theoretically this information can also be calculated
  55 given the scheme presented below.)
  56
  57 Special forms of allocation operators (operator new)
  58 will enforce the following memory layouts:
  59
  60
  61 #  Layout a) will be modelled by prepending the User object
  62 #  by the Use[] array.
  63 #
  64 #      ...---.---.---.---.-------...
  65 #        | P | P | P | P | User
  66 #      '''---'---'---'---'-------'''
  67
  68
  69 #  Layout b) will be modelled by pointing at the Use[] array.
  70 #
  71 #      .-------...
  72 #      | User
  73 #      '-------'''
  74 #          |
  75 #          v
  76 #          .---.---.---.---...
  77 #          | P | P | P | P |
  78 #          '---'---'---'---'''
  79
  80    (In the above figures 'P' stands for the Use** that
  81     is stored in each Use object in the member Use::Prev)
  82
  83
  84 Since the Use objects will be deprived of the direct pointer to
  85 their User objects, there must be a fast and exact method to
  86 recover it. This is accomplished by the following scheme:
  87
  88 A bit-encoding in the 2 LSBits of the Use::Prev will allow to find the
  89 start of the User object:
  90
  91 00 --> binary digit 0
  92 01 --> binary digit 1
  93 10 --> stop and calc (s)
  94 11 --> full stop (S)
  95
  96 Given a Use*, all we have to do is to walk till we get
  97 a stop and we either have a User immediately behind or
  98 we have to walk to the next stop picking up digits
  99 and calculating the offset:
 100
 101 .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.----------------
 102 | 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*)
 103 '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'----------------
 104     |+15                |+10            |+6         |+3     |+1
 105     |                   |               |           |       |__>
 106     |                   |               |           |__________>
 107     |                   |               |______________________>
 108     |                   |______________________________________>
 109     |__________________________________________________________>
 110
 111
 112 Only the significant number of bits need to be stored between the
 113 stops, so that the worst case is 20 memory accesses when there are
 114 1000 Use objects.
 115
 116 The following literate Haskell fragment demonstrates the concept:
 117
 118 > import Test.QuickCheck
 119 >
 120 > digits :: Int -> [Char] -> [Char]
 121 > digits 0 acc = '0' : acc
 122 > digits 1 acc = '1' : acc
 123 > digits n acc = digits (n `div` 2) $ digits (n `mod` 2) acc
 124 >
 125 > dist :: Int -> [Char] -> [Char]
 126 > dist 0 [] = ['S']
 127 > dist 0 acc = acc
 128 > dist 1 acc = let r = dist 0 acc in 's' : digits (length r) r
 129 > dist n acc = dist (n - 1) $ dist 1 acc
 130 >
 131 > takeLast n ss = reverse $ take n $ reverse ss
 132 >
 133 > test = takeLast 40 $ dist 20 []
 134 >
 135
 136 Printing <test> gives: "1s100000s11010s10100s1111s1010s110s11s1S"
 137
 138 The reverse algorithm computes the
 139 length of the string just by examining
 140 a certain prefix:
 141
 142 > pref :: [Char] -> Int
 143 > pref "S" = 1
 144 > pref ('s':'1':rest) = decode 2 1 rest
 145 > pref (_:rest) = 1 + pref rest
 146 >
 147 > decode walk acc ('0':rest) = decode (walk + 1) (acc * 2) rest
 148 > decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest
 149 > decode walk acc _ = walk + acc
 150 >
 151
 152 Now, as expected, printing <pref test> gives 40.
 153
 154 We can quickCheck this with following property:
 155
 156 > testcase = dist 2000 []
 157 > testcaseLength = length testcase
 158 >
 159 > identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr
 160 >     where arr = takeLast n testcase
 161
 162 As expected <quickCheck identityProp> gives:
 163
 164 *Main> quickCheck identityProp
 165 OK, passed 100 tests.
 166
 167 Let's be a bit more exhaustive:
 168
 169 >
 170 > deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
 171 >
 172
 173 And here is the result of <deepCheck identityProp>:
 174
 175 *Main> deepCheck identityProp
 176 OK, passed 500 tests.
 177
 178
 179 To maintain the invariant that the 2 LSBits of each Use** in Use
 180 never change after being set up, setters of Use::Prev must re-tag the
 181 new Use** on every modification. Accordingly getters must strip the
 182 tag bits.
 183
 184 For layout b) instead of the User we will find a pointer (User* with LSBit set).
 185 Following this pointer brings us to the User. A portable trick will ensure
 186 that the first bytes of User (if interpreted as a pointer) will never have
 187 the LSBit set.
 188
 189 ==============================================================================*/
 190
 191 /// OperandTraits - Compile-time customization of
 192 /// operand-related allocators and accessors
 193 /// for use of the User class
 194 template <class>
 195 struct OperandTraits;
 196
 197 class User;
 198
 199 /// OperandTraits<User> - specialization to User
 200 template <>
 201 struct OperandTraits<User> {
 202   static inline Use *op_begin(User*);
 203   static inline Use *op_end(User*);
 204   static inline unsigned operands(const User*);
 205   template <class U>
 206   struct Layout {
 207     typedef U overlay;
 208   };
 209   static inline void *allocate(unsigned);
 210 };
 211
 212 class User : public Value {
 213   User(const User &);             // Do not implement
 214   void *operator new(size_t);     // Do not implement
 215   template <unsigned>
 216   friend struct HungoffOperandTraits;
 217 protected:
 218   /// OperandList - This is a pointer to the array of Users for this operand.
 219   /// For nodes of fixed arity (e.g. a binary operator) this array will live
 220   /// prefixed to the derived class.  For nodes of resizable variable arity
 221   /// (e.g. PHINodes, SwitchInst etc.), this memory will be dynamically
 222   /// allocated and should be destroyed by the classes'
 223   /// virtual dtor.
 224   Use *OperandList;
 225
 226   /// NumOperands - The number of values used by this User.
 227   ///
 228   unsigned NumOperands;
 229
 230   void *operator new(size_t s, unsigned Us) {
 231     void *Storage = ::operator new(s + sizeof(Use) * Us);
 232     Use *Start = static_cast<Use*>(Storage);
 233     Use *End = Start + Us;
 234     User *Obj = reinterpret_cast<User*>(End);
 235     Obj->OperandList = Start;
 236     Obj->NumOperands = Us;
 237     Use::initTags(Start, End);
 238     return Obj;
 239   }
 240   User(const Type *Ty, unsigned vty, Use *OpList, unsigned NumOps)
 241     : Value(Ty, vty), OperandList(OpList), NumOperands(NumOps) {}
 242   Use *allocHungoffUses(unsigned) const;
 243   void dropHungoffUses(Use *U) {
 244     if (OperandList == U) {
 245       OperandList = 0;
 246       NumOperands = 0;
 247     }
 248     Use::zap(U, U->getImpliedUser(), true);
 249   }
 250 public:
 251   ~User() {
 252     Use::zap(OperandList, OperandList + NumOperands);
 253   }
 254   void operator delete(void *Usr) {
 255     User *Start = static_cast<User*>(Usr);
 256     Use *Storage = static_cast<Use*>(Usr) - Start->NumOperands;
 257     ::operator delete(Storage == Start->OperandList
 258                       ? Storage
 259                       : Usr);
 260   }
 261   template <unsigned Idx> Use &Op() {
 262     return OperandTraits<User>::op_begin(this)[Idx];
 263   }
 264   template <unsigned Idx> const Use &Op() const {
 265     return OperandTraits<User>::op_begin(const_cast<User*>(this))[Idx];
 266   }
 267   Value *getOperand(unsigned i) const {
 268     assert(i < NumOperands && "getOperand() out of range!");
 269     return OperandList[i];
 270   }
 271   void setOperand(unsigned i, Value *Val) {
 272     assert(i < NumOperands && "setOperand() out of range!");
 273     OperandList[i] = Val;
 274   }
 275   unsigned getNumOperands() const { return NumOperands; }
 276
 277   // ---------------------------------------------------------------------------
 278   // Operand Iterator interface...
 279   //
 280   typedef Use*       op_iterator;
 281   typedef const Use* const_op_iterator;
 282
 283   inline op_iterator       op_begin()       { return OperandList; }
 284   inline const_op_iterator op_begin() const { return OperandList; }
 285   inline op_iterator       op_end()         { return OperandList+NumOperands; }
 286   inline const_op_iterator op_end()   const { return OperandList+NumOperands; }
 287
 288   // dropAllReferences() - This function is in charge of "letting go" of all
 289   // objects that this User refers to.  This allows one to
 290   // 'delete' a whole class at a time, even though there may be circular
 291   // references... first all references are dropped, and all use counts go to
 292   // zero.  Then everything is delete'd for real.  Note that no operations are
 293   // valid on an object that has "dropped all references", except operator
 294   // delete.
 295   //
 296   void dropAllReferences() {
 297     Use *OL = OperandList;
 298     for (unsigned i = 0, e = NumOperands; i != e; ++i)
 299       OL[i].set(0);
 300   }
 301
 302   /// replaceUsesOfWith - Replaces all references to the "From" definition with
 303   /// references to the "To" definition.
 304   ///
 305   void replaceUsesOfWith(Value *From, Value *To);
 306
 307   // Methods for support type inquiry through isa, cast, and dyn_cast:
 308   static inline bool classof(const User *) { return true; }
 309   static inline bool classof(const Value *V) {
 310     return isa<Instruction>(V) || isa<Constant>(V);
 311   }
 312 };
 313
 314 inline Use *OperandTraits<User>::op_begin(User *U) {
 315   return U->op_begin();
 316 }
 317
 318 inline Use *OperandTraits<User>::op_end(User *U) {
 319   return U->op_end();
 320 }
 321
 322 inline unsigned OperandTraits<User>::operands(const User *U) {
 323   return U->getNumOperands();
 324 }
 325
 326 template<> struct simplify_type<User::op_iterator> {
 327   typedef Value* SimpleType;
 328
 329   static SimpleType getSimplifiedValue(const User::op_iterator &Val) {
 330     return static_cast<SimpleType>(Val->get());
 331   }
 332 };
 333
 334 template<> struct simplify_type<const User::op_iterator>
 335   : public simplify_type<User::op_iterator> {};
 336
 337 template<> struct simplify_type<User::const_op_iterator> {
 338   typedef Value* SimpleType;
 339
 340   static SimpleType getSimplifiedValue(const User::const_op_iterator &Val) {
 341     return static_cast<SimpleType>(Val->get());
 342   }
 343 };
 344
 345 template<> struct simplify_type<const User::const_op_iterator>
 346   : public simplify_type<User::const_op_iterator> {};
 347
 348
 349 // value_use_iterator::getOperandNo - Requires the definition of the User class.
 350 template<typename UserTy>
 351 unsigned value_use_iterator<UserTy>::getOperandNo() const {
 352   return U - U->getUser()->op_begin();
 353 }
 354
 355 } // End llvm namespace
 356
 357 #endif