From 202884fd9b575396f7ca220755cc4e3dac9b5a97 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 16 Oct 2003 16:53:04 +0000 Subject: Completely rewrite support for the Value::use_* list. Now, all operations on this list (except use_size()) are constant time. Before the killUse method (used whenever something stopped using a value) was linear time, and thus very very slow for large programs. This speeds GCCAS up _substantially_ on large programs: almost 2x for 176.gcc: 176.gcc: 77.07s -> 37.38s 177.mesa: 7.59s -> 5.57s 252.eon: 21.02s -> 19.52s (*) 253.perlbmk: 11.40s -> 13.05s 254.gap: 7.25s -> 7.42s 252.eon would speed up a whole lot more, but optimization time is being dominated by the inlining pass, which needs to be fixed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9159 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Use.h | 146 +++++++++++++++++++++++++++++++++++++++++++++++++++ include/llvm/Value.h | 104 ++++++++++++++---------------------- 2 files changed, 185 insertions(+), 65 deletions(-) create mode 100644 include/llvm/Use.h (limited to 'include') diff --git a/include/llvm/Use.h b/include/llvm/Use.h new file mode 100644 index 0000000000..a0f920d2e5 --- /dev/null +++ b/include/llvm/Use.h @@ -0,0 +1,146 @@ +//===-- llvm/Use.h - Definition of the Use class ----------------*- C++ -*-===// +// +// This defines the Use class. The Use class represents the operand of an +// 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. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_USE_H +#define LLVM_USE_H + +#include "Support/ilist" +template struct ilist_traits; +class Value; +class User; + + +//===----------------------------------------------------------------------===// +// Use Class +//===----------------------------------------------------------------------===// + +// Use is here to make keeping the "use" list of a Value up-to-date really easy. +// +class Use { + Value *Val; + User *U; + Use *Prev, *Next; + friend class ilist_traits; +public: + inline Use(Value *v, User *user); + inline Use(const Use &u); + inline ~Use(); + + operator Value*() const { return Val; } + Value *get() const { return Val; } + User *getUser() const { return U; } + + inline void set(Value *Val); + + Value *operator=(Value *RHS) { + set(RHS); + return RHS; + } + const Use &operator=(const Use &RHS) { + set(RHS.Val); + return *this; + } + + Value *operator->() { return Val; } + const Value *operator->() const { return Val; } +}; + +template<> +struct ilist_traits { + static Use *getPrev(Use *N) { return N->Prev; } + static Use *getNext(Use *N) { return N->Next; } + static const Use *getPrev(const Use *N) { return N->Prev; } + static const Use *getNext(const Use *N) { return N->Next; } + static void setPrev(Use *N, Use *Prev) { N->Prev = Prev; } + static void setNext(Use *N, Use *Next) { N->Next = Next; } + + // createNode - this is used to create the end marker for the use list + static Use *createNode() { return new Use(0,0); } + + void addNodeToList(Use *NTy) {} + void removeNodeFromList(Use *NTy) {} + void transferNodesFromList(iplist &L2, + ilist_iterator first, + ilist_iterator last) {} +}; + + +template<> struct simplify_type { + typedef Value* SimpleType; + static SimpleType getSimplifiedValue(const Use &Val) { + return (SimpleType)Val.get(); + } +}; +template<> struct simplify_type { + typedef Value* SimpleType; + static SimpleType getSimplifiedValue(const Use &Val) { + return (SimpleType)Val.get(); + } +}; + +struct UseListIteratorWrapper : public iplist::iterator { + typedef iplist::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*(); } + + UseListIteratorWrapper operator--() { return Super::operator--(); } + UseListIteratorWrapper operator++() { return Super::operator++(); } + + UseListIteratorWrapper operator--(int) { // postdecrement operators... + UseListIteratorWrapper tmp = *this; + --*this; + return tmp; + } + UseListIteratorWrapper operator++(int) { // postincrement operators... + UseListIteratorWrapper tmp = *this; + ++*this; + return tmp; + } +}; + +struct UseListConstIteratorWrapper : public iplist::const_iterator { + typedef iplist::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::iterator &RHS) : Super(RHS) {} + + UseListConstIteratorWrapper &operator=(const Super &RHS) { + Super::operator=(RHS); + return *this; + } + + inline const User *operator*() const; + const User *operator->() const { return operator*(); } + + UseListConstIteratorWrapper operator--() { return Super::operator--(); } + UseListConstIteratorWrapper operator++() { return Super::operator++(); } + + UseListConstIteratorWrapper operator--(int) { // postdecrement operators... + UseListConstIteratorWrapper tmp = *this; + --*this; + return tmp; + } + UseListConstIteratorWrapper operator++(int) { // postincrement operators... + UseListConstIteratorWrapper tmp = *this; + ++*this; + return tmp; + } +}; + +#endif diff --git a/include/llvm/Value.h b/include/llvm/Value.h index 7b50c94954..5fa1497dae 100644 --- a/include/llvm/Value.h +++ b/include/llvm/Value.h @@ -11,12 +11,11 @@ #define LLVM_VALUE_H #include "llvm/AbstractTypeUser.h" +#include "llvm/Use.h" #include "Support/Annotation.h" #include "Support/Casting.h" #include -#include -class User; class Type; class Constant; class Argument; @@ -46,7 +45,7 @@ struct Value : public Annotable { // Values are annotable }; private: - std::vector Uses; + iplist Uses; std::string Name; PATypeHolder Ty; ValueTy VTy; @@ -94,8 +93,8 @@ public: //---------------------------------------------------------------------- // Methods for handling the vector of uses of this Value. // - typedef std::vector::iterator use_iterator; - typedef std::vector::const_iterator use_const_iterator; + typedef UseListIteratorWrapper use_iterator; + typedef UseListConstIteratorWrapper use_const_iterator; unsigned use_size() const { return Uses.size(); } bool use_empty() const { return Uses.empty(); } @@ -103,17 +102,23 @@ public: 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(); } - const User *use_back() const { return Uses.back(); } + User *use_back() { return Uses.back().getUser(); } + const User *use_back() const { return Uses.back().getUser(); } - /// hasOneUse - Return true if there is exactly one user of this value. + /// 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 { return use_size() == 1; } + bool hasOneUse() const { + iplist::const_iterator I = Uses.begin(), E = Uses.end(); + if (I == E) return false; + return ++I == E; + } - /// addUse/killUse - These two methods should only be used by the Use class - /// below. - void addUse(User *I) { Uses.push_back(I); } - void killUse(User *I); + /// 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); } }; inline std::ostream &operator<<(std::ostream &OS, const Value *V) { @@ -130,64 +135,33 @@ inline std::ostream &operator<<(std::ostream &OS, const Value &V) { } -//===----------------------------------------------------------------------===// -// Use Class -//===----------------------------------------------------------------------===// +inline User *UseListIteratorWrapper::operator*() const { + return Super::operator*().getUser(); +} -// Use is here to make keeping the "use" list of a Value up-to-date really easy. -// -class Use { - Value *Val; - User *U; -public: - inline Use(Value *v, User *user) { - Val = v; U = user; - if (Val) Val->addUse(U); - } +inline const User *UseListConstIteratorWrapper::operator*() const { + return Super::operator*().getUser(); +} - inline Use(const Use &user) { - Val = 0; - U = user.U; - operator=(user.Val); - } - inline ~Use() { if (Val) Val->killUse(U); } - inline operator Value*() const { return Val; } - - inline Value *operator=(Value *V) { - if (Val) Val->killUse(U); - Val = V; - if (V) V->addUse(U); - return V; - } - inline Value *operator->() { return Val; } - inline const Value *operator->() const { return Val; } +Use::Use(Value *v, User *user) : Val(v), U(user) { + if (Val) Val->addUse(*this); +} + +Use::Use(const Use &u) : Val(u.Val), U(u.U) { + if (Val) Val->addUse(*this); +} - inline Value *get() { return Val; } - inline const Value *get() const { return Val; } +Use::~Use() { + if (Val) Val->killUse(*this); +} - inline const Use &operator=(const Use &user) { - if (Val) Val->killUse(U); - Val = user.Val; - Val->addUse(U); - return *this; - } -}; +void Use::set(Value *V) { + if (Val) Val->killUse(*this); + Val = V; + if (V) V->addUse(*this); +} -template<> struct simplify_type { - typedef Value* SimpleType; - - static SimpleType getSimplifiedValue(const Use &Val) { - return (SimpleType)Val.get(); - } -}; -template<> struct simplify_type { - typedef Value* SimpleType; - - static SimpleType getSimplifiedValue(const Use &Val) { - return (SimpleType)Val.get(); - } -}; // isa - Provide some specializations of isa so that we don't have to include // the subtype header files to test to see if the value is a subclass... -- cgit v1.2.3