1 //===-- llvm/User.h - User class definition ---------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
14 // * Instructions are the largest class of User's.
15 // * Constants may be users of other constants (think arrays and stuff)
17 //===----------------------------------------------------------------------===//
22 #include "llvm/Value.h"
26 /*==============================================================================
29 -----------------------------------------------------------------
30 --- Interaction and relationship between User and Use objects ---
31 -----------------------------------------------------------------
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.
39 We have 2 different layouts in the User (sub)classes:
42 The Use object(s) are inside (resp. at fixed offset) of the User
43 object and there are a fixed number of them.
46 The Use object(s) are referenced by a pointer to an
47 array from the User object and there may be a variable
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.)
57 Special forms of allocation operators (operator new)
58 will enforce the following memory layouts:
61 # Layout a) will be modelled by prepending the User object
64 # ...---.---.---.---.-------...
65 # | P | P | P | P | User
66 # '''---'---'---'---'-------'''
69 # Layout b) will be modelled by pointing at the Use[] array.
80 (In the above figures 'P' stands for the Use** that
81 is stored in each Use object in the member Use::Prev)
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:
88 A bit-encoding in the 2 LSBits of the Use::Prev will allow to find the
89 start of the User object:
93 10 --> stop and calc (s)
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:
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
107 | | |______________________>
108 | |______________________________________>
109 |__________________________________________________________>
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
116 The following literate Haskell fragment demonstrates the concept:
118 > import Test.QuickCheck
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
125 > dist :: Int -> [Char] -> [Char]
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
131 > takeLast n ss = reverse $ take n $ reverse ss
133 > test = takeLast 40 $ dist 20 []
136 Printing <test> gives: "1s100000s11010s10100s1111s1010s110s11s1S"
138 The reverse algorithm computes the
139 length of the string just by examining
142 > pref :: [Char] -> Int
144 > pref ('s':'1':rest) = decode 2 1 rest
145 > pref (_:rest) = 1 + pref rest
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
152 Now, as expected, printing <pref test> gives 40.
154 We can quickCheck this with following property:
156 > testcase = dist 2000 []
157 > testcaseLength = length testcase
159 > identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr
160 > where arr = takeLast n testcase
162 As expected <quickCheck identityProp> gives:
164 *Main> quickCheck identityProp
165 OK, passed 100 tests.
167 Let's be a bit more exhaustive:
170 > deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
173 And here is the result of <deepCheck identityProp>:
175 *Main> deepCheck identityProp
176 OK, passed 500 tests.
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
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
189 ==============================================================================*/
191 /// OperandTraits - Compile-time customization of
192 /// operand-related allocators and accessors
193 /// for use of the User class
195 struct OperandTraits;
199 /// OperandTraits<User> - specialization to User
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*);
209 static inline void *allocate(unsigned);
212 class User : public Value {
213 User(const User &); // Do not implement
214 void *operator new(size_t); // Do not implement
216 friend struct HungoffOperandTraits;
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'
226 /// NumOperands - The number of values used by this User.
228 unsigned NumOperands;
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) {
239 Use::zap(U, U->getImpliedUser(), true);
243 Use::zap(OperandList, OperandList + NumOperands);
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?");
251 template <unsigned Idx> Use &Op() {
252 return OperandTraits<User>::op_begin(this)[Idx];
254 template <unsigned Idx> const Use &Op() const {
255 return OperandTraits<User>::op_begin(const_cast<User*>(this))[Idx];
257 Value *getOperand(unsigned i) const {
258 assert(i < NumOperands && "getOperand() out of range!");
259 return OperandList[i];
261 void setOperand(unsigned i, Value *Val) {
262 assert(i < NumOperands && "setOperand() out of range!");
263 OperandList[i] = Val;
265 unsigned getNumOperands() const { return NumOperands; }
267 // ---------------------------------------------------------------------------
268 // Operand Iterator interface...
270 typedef Use* op_iterator;
271 typedef const Use* const_op_iterator;
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; }
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
286 void dropAllReferences() {
287 Use *OL = OperandList;
288 for (unsigned i = 0, e = NumOperands; i != e; ++i)
292 /// replaceUsesOfWith - Replaces all references to the "From" definition with
293 /// references to the "To" definition.
295 void replaceUsesOfWith(Value *From, Value *To);
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);
304 inline Use *OperandTraits<User>::op_begin(User *U) {
305 return U->op_begin();
308 inline Use *OperandTraits<User>::op_end(User *U) {
312 inline unsigned OperandTraits<User>::operands(const User *U) {
313 return U->getNumOperands();
316 template<> struct simplify_type<User::op_iterator> {
317 typedef Value* SimpleType;
319 static SimpleType getSimplifiedValue(const User::op_iterator &Val) {
320 return static_cast<SimpleType>(Val->get());
324 template<> struct simplify_type<const User::op_iterator>
325 : public simplify_type<User::op_iterator> {};
327 template<> struct simplify_type<User::const_op_iterator> {
328 typedef Value* SimpleType;
330 static SimpleType getSimplifiedValue(const User::const_op_iterator &Val) {
331 return static_cast<SimpleType>(Val->get());
335 template<> struct simplify_type<const User::const_op_iterator>
336 : public simplify_type<User::const_op_iterator> {};
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();
345 } // End llvm namespace