X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FUse.h;h=a496325c1fc667e5416cf35986993917ca4373bf;hb=8c74f7f2991a10977fd5a003b2901b56eb2e19a8;hp=b4d2c488243fe663e837d938be22a4c90deac7f4;hpb=4fbed982fb09cb67c0d19ae553a06eb9321b3913;p=oota-llvm.git diff --git a/include/llvm/Use.h b/include/llvm/Use.h index b4d2c488243..a496325c1fc 100644 --- a/include/llvm/Use.h +++ b/include/llvm/Use.h @@ -11,60 +11,42 @@ // instruction or some other User instance which refers to a Value. The Use // class keeps the "use list" of the referenced value up to date. // +// Pointer tagging is used to efficiently find the User corresponding +// to a Use without having to store a User pointer in every Use. A +// User is preceded in memory by all the Uses corresponding to its +// operands, and the low bits of one of the fields (Prev) of the Use +// class are used to encode offsets to be able to find that User given +// a pointer to any Use. For details, see: +// +// http://www.llvm.org/docs/ProgrammersManual.html#UserLayout +// //===----------------------------------------------------------------------===// #ifndef LLVM_USE_H #define LLVM_USE_H -#include "llvm/Support/Casting.h" -#include "llvm/ADT/iterator.h" +#include "llvm/ADT/PointerIntPair.h" +#include +#include namespace llvm { class Value; class User; +class Use; +template +struct simplify_type; - -//===----------------------------------------------------------------------===// -// Generic Tagging Functions -//===----------------------------------------------------------------------===// - -// We adhere to the following convention: The type of a tagged pointer -// to T is T volatile*. This means that functions that superpose a tag -// on a pointer will be supplied a T* (or T const*) and will return a -// tagged one: T volatile*. Untagging functions do it the other way -// 'round. While this scheme does not prevent dereferencing of tagged -// pointers, proper type annotations do catch most inappropriate uses. - -/// Tag - generic tag type for (at least 32 bit) pointers -enum Tag { noTag, tagOne, tagTwo, tagThree }; - -/// addTag - insert tag bits into an (untagged) pointer -template -inline volatile T *addTag(const T *P, TAG Tag) { - return reinterpret_cast(ptrdiff_t(P) | Tag); -} - -/// stripTag - remove tag bits from a pointer, -/// making it dereferencable -template -inline T *stripTag(const volatile T *P) { - return reinterpret_cast(ptrdiff_t(P) & ~MASK); -} - -/// extractTag - extract tag bits from a pointer -template -inline TAG extractTag(const volatile T *P) { - return TAG(ptrdiff_t(P) & MASK); -} - -/// transferTag - transfer tag bits from a pointer, -/// to an untagged pointer -template -inline volatile T *transferTag(const volatile T *From, const T *To) { - return reinterpret_cast((ptrdiff_t(From) & MASK) | ptrdiff_t(To)); -} - +// Use** is only 4-byte aligned. +template<> +class PointerLikeTypeTraits { +public: + static inline void *getAsVoidPointer(Use** P) { return P; } + static inline Use **getFromVoidPointer(void *P) { + return static_cast(P); + } + enum { NumLowBitsAvailable = 2 }; +}; //===----------------------------------------------------------------------===// // Use Class @@ -78,22 +60,28 @@ public: /// that also works with less standard-compliant compilers void swap(Use &RHS); + // A type for the word following an array of hung-off Uses in memory, which is + // a pointer back to their User with the bottom bit set. + typedef PointerIntPair UserRef; + private: /// Copy ctor - do not implement Use(const Use &U); /// Destructor - Only for zap() - inline ~Use() { + ~Use() { if (Val) removeFromList(); } - /// Default ctor - This leaves the Use completely uninitialized. The only - /// thing that is valid to do with this use is to call the "init" method. - inline Use() {} - enum PrevPtrTag { zeroDigitTag = noTag - , oneDigitTag = tagOne - , stopTag = tagTwo - , fullStopTag = tagThree }; + enum PrevPtrTag { zeroDigitTag + , oneDigitTag + , stopTag + , fullStopTag }; + + /// Constructor + Use(PrevPtrTag tag) : Val(0) { + Prev.setInt(tag); + } public: /// Normally Use will just implicitly convert to a Value* that it holds. @@ -124,19 +112,23 @@ public: Use *getNext() const { return Next; } + /// initTags - initialize the waymarking tags on an array of Uses, so that + /// getUser() can find the User from any of those Uses. + static Use *initTags(Use *Start, Use *Stop); + /// zap - This is used to destroy Use operands when the number of operands of /// a User changes. static void zap(Use *Start, const Use *Stop, bool del = false); private: const Use* getImpliedUser() const; - static Use *initTags(Use *Start, Use *Stop, ptrdiff_t Done = 0); Value *Val; - Use *Next, *volatile*Prev; + Use *Next; + PointerIntPair Prev; void setPrev(Use **NewPrev) { - Prev = transferTag(Prev, NewPrev); + Prev.setPointer(NewPrev); } void addToList(Use **List) { Next = *List; @@ -145,13 +137,12 @@ private: *List = this; } void removeFromList() { - Use **StrippedPrev = stripTag(Prev); + Use **StrippedPrev = Prev.getPointer(); *StrippedPrev = Next; if (Next) Next->setPrev(StrippedPrev); } friend class Value; - friend class User; }; // simplify_type - Allow clients to treat uses just like values when using @@ -172,8 +163,9 @@ template<> struct simplify_type { template // UserTy == 'User' or 'const User' -class value_use_iterator : public forward_iterator { - typedef forward_iterator super; +class value_use_iterator : public std::iterator { + typedef std::iterator super; typedef value_use_iterator _Self; Use *U; @@ -222,30 +214,6 @@ public: unsigned getOperandNo() const; }; - -template<> struct simplify_type > { - typedef User* SimpleType; - - static SimpleType getSimplifiedValue(const value_use_iterator &Val) { - return *Val; - } -}; - -template<> struct simplify_type > - : public simplify_type > {}; - -template<> struct simplify_type > { - typedef const User* SimpleType; - - static SimpleType getSimplifiedValue(const - value_use_iterator &Val) { - return *Val; - } -}; - -template<> struct simplify_type > - : public simplify_type > {}; - } // End llvm namespace #endif