X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FUser.h;h=5d5460cd6fffdeeabde8d2ce2956b928d01f5f3f;hb=a32ccf92c1d53e0f16d2f29ad1fae75c3aa013a0;hp=23967c7420b81d09dc7f87ef6311b2187cccb631;hpb=b074f80d8e0ab47012904634cef5468fea8d0165;p=oota-llvm.git diff --git a/include/llvm/User.h b/include/llvm/User.h index 23967c7420b..5d5460cd6ff 100644 --- a/include/llvm/User.h +++ b/include/llvm/User.h @@ -7,11 +7,11 @@ // //===----------------------------------------------------------------------===// // -// This class defines the interface that one who 'use's a Value must implement. +// This class defines the interface that one who uses a Value must implement. // Each instance of the Value class keeps track of what User's have handles // to it. // -// * Instructions are the largest class of User's. +// * Instructions are the largest class of Users. // * Constants may be users of other constants (think arrays and stuff) // //===----------------------------------------------------------------------===// @@ -19,208 +19,29 @@ #ifndef LLVM_USER_H #define LLVM_USER_H +#include "llvm/Support/ErrorHandling.h" #include "llvm/Value.h" 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 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 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 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 : - -*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 struct OperandTraits; -class User; - -/// OperandTraits - specialization to User -template <> -struct OperandTraits { - static inline Use *op_begin(User*); - static inline Use *op_end(User*); - static inline unsigned operands(const User*); - template - 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 friend struct HungoffOperandTraits; + virtual void anchor(); protected: - /// OperandList - This is a pointer to the array of Users for this operand. + /// OperandList - This is a pointer to the array of Uses for this User. /// For nodes of fixed arity (e.g. a binary operator) this array will live - /// 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. + /// prefixed to some derived class instance. 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; /// NumOperands - The number of values used by this User. @@ -228,15 +49,14 @@ protected: unsigned NumOperands; void *operator new(size_t s, unsigned Us); - User(const Type *ty, unsigned vty, Use *OpList, unsigned NumOps) + User(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); + void dropHungoffUses() { + Use::zap(OperandList, OperandList + NumOperands, true); + OperandList = 0; + // Reset NumOperands so User::operator delete() does the right thing. + NumOperands = 0; } public: ~User() { @@ -246,22 +66,45 @@ public: void operator delete(void *Usr); /// placement delete - required by std, but never called. void operator delete(void*, unsigned) { - assert(0 && "Constructor throws?"); + llvm_unreachable("Constructor throws?"); } - template Use &Op() { - return OperandTraits::op_begin(this)[Idx]; + /// placement delete - required by std, but never called. + void operator delete(void*, unsigned, bool) { + llvm_unreachable("Constructor throws?"); } - template const Use &Op() const { - return OperandTraits::op_begin(const_cast(this))[Idx]; +protected: + template static Use &OpFrom(const U *that) { + return Idx < 0 + ? OperandTraits::op_end(const_cast(that))[Idx] + : OperandTraits::op_begin(const_cast(that))[Idx]; + } + template Use &Op() { + return OpFrom(this); } + template const Use &Op() const { + return OpFrom(this); + } +public: Value *getOperand(unsigned i) const { assert(i < NumOperands && "getOperand() out of range!"); return OperandList[i]; } void setOperand(unsigned i, Value *Val) { assert(i < NumOperands && "setOperand() out of range!"); + assert((!isa((const Value*)this) || + isa((const Value*)this)) && + "Cannot mutate a constant with setOperand!"); OperandList[i] = Val; } + const Use &getOperandUse(unsigned i) const { + assert(i < NumOperands && "getOperandUse() out of range!"); + return OperandList[i]; + } + Use &getOperandUse(unsigned i) { + assert(i < NumOperands && "getOperandUse() out of range!"); + return OperandList[i]; + } + unsigned getNumOperands() const { return NumOperands; } // --------------------------------------------------------------------------- @@ -278,15 +121,14 @@ public: // dropAllReferences() - This function is in charge of "letting go" of all // objects that this User refers to. This allows one to // 'delete' a whole class at a time, even though there may be circular - // references... first all references are dropped, and all use counts go to - // zero. Then everything is delete'd for real. Note that no operations are + // references... First all references are dropped, and all use counts go to + // zero. Then everything is deleted for real. Note that no operations are // valid on an object that has "dropped all references", except operator // delete. // void dropAllReferences() { - Use *OL = OperandList; - for (unsigned i = 0, e = NumOperands; i != e; ++i) - OL[i].set(0); + for (op_iterator i = op_begin(), e = op_end(); i != e; ++i) + i->set(0); } /// replaceUsesOfWith - Replaces all references to the "From" definition with @@ -301,18 +143,6 @@ public: } }; -inline Use *OperandTraits::op_begin(User *U) { - return U->op_begin(); -} - -inline Use *OperandTraits::op_end(User *U) { - return U->op_end(); -} - -inline unsigned OperandTraits::operands(const User *U) { - return U->getNumOperands(); -} - template<> struct simplify_type { typedef Value* SimpleType;