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   User(const Type *ty, unsigned vty, Use *OpList, unsigned NumOps)
 232     : Value(ty, vty), OperandList(OpList), NumOperands(NumOps) {}
 233   Use *allocHungoffUses(unsigned) const;
 234   void dropHungoffUses(Use *U) {
 235     if (OperandList == U) {
 236       OperandList = 0;
 237       NumOperands = 0;
 238     }
 239     Use::zap(U, U->getImpliedUser(), true);
 240   }
 241 public:
 242   ~User() {
 243     Use::zap(OperandList, OperandList + NumOperands);
 244   }
 245   /// operator delete - free memory allocated for User and Use objects
 246   void operator delete(void *Usr);
 247   /// placement delete - required by std, but never called.
 248   void operator delete(void*, unsigned) {
 249     assert(0 && "Constructor throws?");
 250   }
 251   template <unsigned Idx> Use &Op() {
 252     return OperandTraits<User>::op_begin(this)[Idx];
 253   }
 254   template <unsigned Idx> const Use &Op() const {
 255     return OperandTraits<User>::op_begin(const_cast<User*>(this))[Idx];
 256   }
 257   Value *getOperand(unsigned i) const {
 258     assert(i < NumOperands && "getOperand() out of range!");
 259     return OperandList[i];
 260   }
 261   void setOperand(unsigned i, Value *Val) {
 262     assert(i < NumOperands && "setOperand() out of range!");
 263     OperandList[i] = Val;
 264   }
 265   unsigned getNumOperands() const { return NumOperands; }
 266
 267   // ---------------------------------------------------------------------------
 268   // Operand Iterator interface...
 269   //
 270   typedef Use*       op_iterator;
 271   typedef const Use* const_op_iterator;
 272
 273   inline op_iterator       op_begin()       { return OperandList; }
 274   inline const_op_iterator op_begin() const { return OperandList; }
 275   inline op_iterator       op_end()         { return OperandList+NumOperands; }
 276   inline const_op_iterator op_end()   const { return OperandList+NumOperands; }
 277
 278   // dropAllReferences() - This function is in charge of "letting go" of all
 279   // objects that this User refers to.  This allows one to
 280   // 'delete' a whole class at a time, even though there may be circular
 281   // references... first all references are dropped, and all use counts go to
 282   // zero.  Then everything is delete'd for real.  Note that no operations are
 283   // valid on an object that has "dropped all references", except operator
 284   // delete.
 285   //
 286   void dropAllReferences() {
 287     Use *OL = OperandList;
 288     for (unsigned i = 0, e = NumOperands; i != e; ++i)
 289       OL[i].set(0);
 290   }
 291
 292   /// replaceUsesOfWith - Replaces all references to the "From" definition with
 293   /// references to the "To" definition.
 294   ///
 295   void replaceUsesOfWith(Value *From, Value *To);
 296
 297   // Methods for support type inquiry through isa, cast, and dyn_cast:
 298   static inline bool classof(const User *) { return true; }
 299   static inline bool classof(const Value *V) {
 300     return isa<Instruction>(V) || isa<Constant>(V);
 301   }
 302 };
 303
 304 inline Use *OperandTraits<User>::op_begin(User *U) {
 305   return U->op_begin();
 306 }
 307
 308 inline Use *OperandTraits<User>::op_end(User *U) {
 309   return U->op_end();
 310 }
 311
 312 inline unsigned OperandTraits<User>::operands(const User *U) {
 313   return U->getNumOperands();
 314 }
 315
 316 template<> struct simplify_type<User::op_iterator> {
 317   typedef Value* SimpleType;
 318
 319   static SimpleType getSimplifiedValue(const User::op_iterator &Val) {
 320     return static_cast<SimpleType>(Val->get());
 321   }
 322 };
 323
 324 template<> struct simplify_type<const User::op_iterator>
 325   : public simplify_type<User::op_iterator> {};
 326
 327 template<> struct simplify_type<User::const_op_iterator> {
 328   typedef Value* SimpleType;
 329
 330   static SimpleType getSimplifiedValue(const User::const_op_iterator &Val) {
 331     return static_cast<SimpleType>(Val->get());
 332   }
 333 };
 334
 335 template<> struct simplify_type<const User::const_op_iterator>
 336   : public simplify_type<User::const_op_iterator> {};
 337
 338
 339 // value_use_iterator::getOperandNo - Requires the definition of the User class.
 340 template<typename UserTy>
 341 unsigned value_use_iterator<UserTy>::getOperandNo() const {
 342   return U - U->getUser()->op_begin();
 343 }
 344
 345 } // End llvm namespace
 346
 347 #endif