diff options
| -rw-r--r-- | include/llvm/Support/CFG.h | 15 | ||||
| -rw-r--r-- | include/llvm/Use.h | 130 | ||||
| -rw-r--r-- | include/llvm/Value.h | 52 |
3 files changed, 79 insertions, 118 deletions
diff --git a/include/llvm/Support/CFG.h b/include/llvm/Support/CFG.h index badb846bac..231531a7ae 100644 --- a/include/llvm/Support/CFG.h +++ b/include/llvm/Support/CFG.h @@ -27,22 +27,22 @@ namespace llvm { //===--------------------------------------------------------------------===// template <class _Ptr, class _USE_iterator> // Predecessor Iterator -class PredIterator : public bidirectional_iterator<_Ptr, ptrdiff_t> { - typedef bidirectional_iterator<_Ptr, ptrdiff_t> super; +class PredIterator : public forward_iterator<_Ptr, ptrdiff_t> { + typedef forward_iterator<_Ptr, ptrdiff_t> super; _Ptr *BB; _USE_iterator It; public: typedef PredIterator<_Ptr,_USE_iterator> _Self; typedef typename super::pointer pointer; - inline void advancePastConstants() { + inline void advancePastNonTerminators() { // Loop to ignore non terminator uses (for example PHI nodes)... while (It != BB->use_end() && !isa<TerminatorInst>(*It)) ++It; } inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) { - advancePastConstants(); + advancePastNonTerminators(); } inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {} @@ -57,18 +57,13 @@ public: inline _Self& operator++() { // Preincrement assert(It != BB->use_end() && "pred_iterator out of range!"); - ++It; advancePastConstants(); + ++It; advancePastNonTerminators(); return *this; } inline _Self operator++(int) { // Postincrement _Self tmp = *this; ++*this; return tmp; } - - inline _Self& operator--() { --It; return *this; } // Predecrement - inline _Self operator--(int) { // Postdecrement - _Self tmp = *this; --*this; return tmp; - } }; typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator; diff --git a/include/llvm/Use.h b/include/llvm/Use.h index 26923a26da..bbf523574c 100644 --- a/include/llvm/Use.h +++ b/include/llvm/Use.h @@ -16,11 +16,11 @@ #ifndef LLVM_USE_H #define LLVM_USE_H -#include "llvm/ADT/ilist" +#include "llvm/Support/Casting.h" +#include "llvm/ADT/iterator" namespace llvm { -template<typename NodeTy> struct ilist_traits; class Value; class User; @@ -62,43 +62,28 @@ public: Value *operator->() { return Val; } const Value *operator->() const { return Val; } + Use *getNext() const { return Next; } private: - // NOTE!! The Next/Prev fields MUST stay at the start of this structure. The - // end-token for the ilist is allocated as JUST the next/prev pair to reduce - // memory usage instead of allocating an entire Use. - struct NextPrevPtrs { - Use *Next, *Prev; - } UseLinks; - + Use *Next, **Prev; Value *Val; User *U; - friend struct ilist_traits<Use>; -}; -template<> -struct ilist_traits<Use> { - static Use *getPrev(Use *N) { return N->UseLinks.Prev; } - static Use *getNext(Use *N) { return N->UseLinks.Next; } - static const Use *getPrev(const Use *N) { return N->UseLinks.Prev; } - static const Use *getNext(const Use *N) { return N->UseLinks.Next; } - static void setPrev(Use *N, Use *Prev) { N->UseLinks.Prev = Prev; } - static void setNext(Use *N, Use *Next) { N->UseLinks.Next = Next; } - - /// createSentinel - this is used to create the end marker for the use list. - /// Note that we only allocate a UseLinks structure, which is just enough to - /// hold the next/prev pointers. This saves us 8 bytes of memory for every - /// Value allocated. - static Use *createSentinel() { return (Use*)new Use::NextPrevPtrs(); } - static void destroySentinel(Use *S) { delete (Use::NextPrevPtrs*)S; } - - void addNodeToList(Use *NTy) {} - void removeNodeFromList(Use *NTy) {} - void transferNodesFromList(iplist<Use, ilist_traits> &L2, - ilist_iterator<Use> first, - ilist_iterator<Use> last) {} -}; + void addToList(Use **List) { + Next = *List; + if (Next) Next->Prev = &Next; + Prev = List; + *List = this; + } + void removeFromList() { + *Prev = Next; + if (Next) Next->Prev = Prev; + } + friend class Value; +}; +// simplify_type - Allow clients to treat uses just like values when using +// casting operators. template<> struct simplify_type<Use> { typedef Value* SimpleType; static SimpleType getSimplifiedValue(const Use &Val) { @@ -112,64 +97,49 @@ template<> struct simplify_type<const Use> { } }; -struct UseListIteratorWrapper : public iplist<Use>::iterator { - typedef iplist<Use>::iterator Super; - UseListIteratorWrapper() {} - UseListIteratorWrapper(const Super &RHS) : Super(RHS) {} - UseListIteratorWrapper &operator=(const Super &RHS) { - Super::operator=(RHS); - return *this; - } - inline User *operator*() const; - User *operator->() const { return operator*(); } +template<typename UserTy> // UserTy == 'User' or 'const User' +class value_use_iterator : public forward_iterator<UserTy*, ptrdiff_t> { + typedef forward_iterator<UserTy*, ptrdiff_t> super; + typedef value_use_iterator<UserTy> _Self; + + Use *U; + value_use_iterator(Use *u) : U(u) {} + friend class Value; +public: + typedef typename super::reference reference; + typedef typename super::pointer pointer; - UseListIteratorWrapper operator--() { return Super::operator--(); } - UseListIteratorWrapper operator++() { return Super::operator++(); } + value_use_iterator(const _Self &I) : U(I.U) {} + value_use_iterator() {} - UseListIteratorWrapper operator--(int) { // postdecrement operators... - UseListIteratorWrapper tmp = *this; - --*this; - return tmp; + bool operator==(const _Self &x) const { + return U == x.U; } - UseListIteratorWrapper operator++(int) { // postincrement operators... - UseListIteratorWrapper tmp = *this; - ++*this; - return tmp; + bool operator!=(const _Self &x) const { + return !operator==(x); } -}; - -struct UseListConstIteratorWrapper : public iplist<Use>::const_iterator { - typedef iplist<Use>::const_iterator Super; - UseListConstIteratorWrapper() {} - UseListConstIteratorWrapper(const Super &RHS) : Super(RHS) {} - // Allow conversion from non-const to const iterators - UseListConstIteratorWrapper(const UseListIteratorWrapper &RHS) : Super(RHS) {} - UseListConstIteratorWrapper(const iplist<Use>::iterator &RHS) : Super(RHS) {} - - UseListConstIteratorWrapper &operator=(const Super &RHS) { - Super::operator=(RHS); - return *this; + // Iterator traversal: forward iteration only + _Self &operator++() { // Preincrement + assert(U && "Cannot increment end iterator!"); + U = U->getNext(); + return *this; + } + _Self operator++(int) { // Postincrement + _Self tmp = *this; ++*this; return tmp; } - inline const User *operator*() const; - const User *operator->() const { return operator*(); } + // Retrieve a reference to the current SCC + UserTy *operator*() const { + assert(U && "Cannot increment end iterator!"); + return U->getUser(); + } - UseListConstIteratorWrapper operator--() { return Super::operator--(); } - UseListConstIteratorWrapper operator++() { return Super::operator++(); } + UserTy *operator->() const { return operator*(); } - UseListConstIteratorWrapper operator--(int) { // postdecrement operators... - UseListConstIteratorWrapper tmp = *this; - --*this; - return tmp; - } - UseListConstIteratorWrapper operator++(int) { // postincrement operators... - UseListConstIteratorWrapper tmp = *this; - ++*this; - return tmp; - } + Use &getUse() const { return *U; } }; } // End llvm namespace diff --git a/include/llvm/Value.h b/include/llvm/Value.h index 90bbe6fe91..46257cc7a3 100644 --- a/include/llvm/Value.h +++ b/include/llvm/Value.h @@ -43,7 +43,7 @@ class SymbolTable; class Value { unsigned SubclassID; // Subclass identifier (for isa/dyn_cast) PATypeHolder Ty; - iplist<Use> Uses; + Use *UseList; std::string Name; void operator=(const Value &); // Do not implement @@ -86,33 +86,39 @@ public: //---------------------------------------------------------------------- // Methods for handling the vector of uses of this Value. // - typedef UseListIteratorWrapper use_iterator; - typedef UseListConstIteratorWrapper use_const_iterator; - typedef iplist<Use>::size_type size_type; - - size_type use_size() const { return Uses.size(); } - bool use_empty() const { return Uses.empty(); } - use_iterator use_begin() { return Uses.begin(); } - use_const_iterator use_begin() const { return Uses.begin(); } - use_iterator use_end() { return Uses.end(); } - use_const_iterator use_end() const { return Uses.end(); } - User *use_back() { return Uses.back().getUser(); } - const User *use_back() const { return Uses.back().getUser(); } + typedef value_use_iterator<User> use_iterator; + typedef value_use_iterator<const User> use_const_iterator; + + bool use_empty() const { return UseList == 0; } + use_iterator use_begin() { return use_iterator(UseList); } + use_const_iterator use_begin() const { return use_const_iterator(UseList); } + use_iterator use_end() { return use_iterator(0); } + use_const_iterator use_end() const { return use_const_iterator(0); } + User *use_back() { return *use_begin(); } + const User *use_back() const { return *use_begin(); } /// hasOneUse - Return true if there is exactly one user of this value. This /// is specialized because it is a common request and does not require /// traversing the whole use list. /// bool hasOneUse() const { - iplist<Use>::const_iterator I = Uses.begin(), E = Uses.end(); + use_const_iterator I = use_begin(), E = use_end(); if (I == E) return false; return ++I == E; } + /// hasNUses - Return true if this Value has exactly N users. + /// + bool hasNUses(unsigned N) const; + + /// getNumUses - This method computes the number of uses of this Value. This + /// is a linear time operation. Use hasOneUse or hasNUses to check for + /// specific values. + unsigned getNumUses() const; + /// addUse/killUse - These two methods should only be used by the Use class. /// - void addUse(Use &U) { Uses.push_back(&U); } - void killUse(Use &U) { Uses.remove(&U); } + void addUse(Use &U) { U.addToList(&UseList); } /// getValueType - Return an ID for the concrete type of this object. This is /// used to implement the classof checks. This should not be used for any @@ -157,16 +163,6 @@ inline std::ostream &operator<<(std::ostream &OS, const Value &V) { return OS; } - -inline User *UseListIteratorWrapper::operator*() const { - return Super::operator*().getUser(); -} - -inline const User *UseListConstIteratorWrapper::operator*() const { - return Super::operator*().getUser(); -} - - void Use::init(Value *v, User *user) { Val = v; U = user; @@ -174,11 +170,11 @@ void Use::init(Value *v, User *user) { } Use::~Use() { - if (Val) Val->killUse(*this); + if (Val) removeFromList(); } void Use::set(Value *V) { - if (Val) Val->killUse(*this); + if (Val) removeFromList(); Val = V; if (V) V->addUse(*this); } |