diff options
| -rw-r--r-- | include/llvm/Support/ValueHandle.h | 217 | ||||
| -rw-r--r-- | include/llvm/Value.h | 8 | ||||
| -rw-r--r-- | lib/VMCore/Value.cpp | 167 |
3 files changed, 389 insertions, 3 deletions
diff --git a/include/llvm/Support/ValueHandle.h b/include/llvm/Support/ValueHandle.h new file mode 100644 index 0000000000..0494b27019 --- /dev/null +++ b/include/llvm/Support/ValueHandle.h @@ -0,0 +1,217 @@ +//===- llvm/Support/ValueHandle.h - Value Smart Pointer classes -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares the ValueHandle class and its sub-classes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_VALUEHANDLE_H +#define LLVM_SUPPORT_VALUEHANDLE_H + +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/Value.h" + +namespace llvm { + +/// ValueHandleBase - This is the common base class of value handles. +/// ValueHandle's are smart pointers to Value's that have special behavior when +/// the value is deleted or ReplaceAllUsesWith'd. See the specific handles +/// below for details. +/// +class ValueHandleBase { + friend class Value; +protected: + /// HandleBaseKind - This indicates what base class the handle actually is. + /// This is to avoid having a vtable for the light-weight handle pointers. The + /// fully generally Callback version does have a vtable. + enum HandleBaseKind { + Assert, + Weak, + Callback + }; +private: + + PointerIntPair<ValueHandleBase**, 2, HandleBaseKind> PrevPair; + ValueHandleBase *Next; + Value *VP; +public: + ValueHandleBase(HandleBaseKind Kind) : PrevPair(0, Kind), Next(0), VP(0) {} + ValueHandleBase(HandleBaseKind Kind, Value *V) + : PrevPair(0, Kind), Next(0), VP(V) { + if (V) + AddToUseList(); + } + ValueHandleBase(HandleBaseKind Kind, const ValueHandleBase &RHS) + : PrevPair(0, Kind), Next(0), VP(RHS.VP) { + if (VP) + AddToExistingUseList(RHS.getPrevPtr()); + } + ~ValueHandleBase() { + if (VP) + RemoveFromUseList(); + } + + Value *operator=(Value *RHS) { + if (VP == RHS) return RHS; + if (VP) RemoveFromUseList(); + VP = RHS; + if (VP) AddToUseList(); + return RHS; + } + + Value *operator=(const ValueHandleBase &RHS) { + if (VP == RHS.VP) return RHS.VP; + if (VP) RemoveFromUseList(); + VP = RHS.VP; + if (VP) AddToExistingUseList(RHS.getPrevPtr()); + return VP; + } + + Value *operator->() const { return getValPtr(); } + Value &operator*() const { return *getValPtr(); } + + bool operator==(const Value *RHS) const { return VP == RHS; } + bool operator==(const ValueHandleBase &RHS) const { return VP == RHS.VP; } + bool operator!=(const Value *RHS) const { return VP != RHS; } + bool operator!=(const ValueHandleBase &RHS) const { return VP != RHS.VP; } + bool operator<(const Value *RHS) const { return VP < RHS; } + bool operator<(const ValueHandleBase &RHS) const { return VP < RHS.VP; } + bool operator>(const Value *RHS) const { return VP > RHS; } + bool operator>(const ValueHandleBase &RHS) const { return VP > RHS.VP; } + bool operator<=(const Value *RHS) const { return VP <= RHS; } + bool operator<=(const ValueHandleBase &RHS) const { return VP <= RHS.VP; } + bool operator>=(const Value *RHS) const { return VP >= RHS; } + bool operator>=(const ValueHandleBase &RHS) const { return VP >= RHS.VP; } + +protected: + Value *getValPtr() const { return VP; } +private: + // Callbacks made from Value. + static void ValueIsDeleted(Value *V); + static void ValueIsRAUWd(Value *Old, Value *New); + + // Internal implementation details. + ValueHandleBase **getPrevPtr() const { return PrevPair.getPointer(); } + HandleBaseKind getKind() const { return PrevPair.getInt(); } + void setPrevPtr(ValueHandleBase **Ptr) { PrevPair.setPointer(Ptr); } + + /// AddToUseList - Add this ValueHandle to the use list for VP, where List is + /// known to point into the existing use list. + void AddToExistingUseList(ValueHandleBase **List); + + /// AddToUseList - Add this ValueHandle to the use list for VP. + void AddToUseList(); + /// RemoveFromUseList - Remove this ValueHandle from its current use list. + void RemoveFromUseList(); +}; + +/// WeakVH - This is a value handle that tries hard to point to a Value, even +/// across RAUW operations, but will null itself out if the value is destroyed. +/// this is useful for advisory sorts of information, but should not be used as +/// the key of a map (since the map would have to rearrange itself when the +/// pointer changes). +class WeakVH : public ValueHandleBase { +public: + WeakVH() : ValueHandleBase(Weak) {} + WeakVH(Value *P) : ValueHandleBase(Weak, P) {} + WeakVH(const WeakVH &RHS) + : ValueHandleBase(Weak, RHS) {} + +}; + +/// AssertingVH - This is a Value Handle that points to a value and asserts out +/// if the value is destroyed while the handle is still live. This is very +/// useful for catching dangling pointer bugs and other things which can be +/// non-obvious. One particularly useful place to use this is as the Key of a +/// map. Dangling pointer bugs often lead to really subtle bugs that only occur +/// if another object happens to get allocated to the same address as the old +/// one. Using an AssertingVH ensures that an assert is triggered as soon as +/// the bad delete occurs. +/// +/// Note that an AssertingVH handle does *not* follow values across RAUW +/// operations. This means that RAUW's need to explicitly update the +/// AssertingVH's as it moves. This is required because in non-assert mode this + /// class turns into a trivial wrapper around a pointer. +template <typename ValueTy = Value> +class AssertingVH +#ifndef NDEBUG + : public ValueHandleBase +#endif + { + +#ifndef NDEBUG + ValueTy *getValPtr() const { + return static_cast<ValueTy*>(ValueHandleBase::getValPtr()); + } + void setValPtr(ValueTy *P) { + ValueHandleBase::operator=(P); + } +#else + ValueTy *ThePtr; + ValueTy *getValPtr() const { return ThePtr; } + void setValPtr(ValueTy *P) { ThePtr = P; } +#endif + +public: +#ifndef NDEBUG + AssertingVH() : ValueHandleBase(Assert) {} + AssertingVH(ValueTy *P) : ValueHandleBase(Assert, P) {} + AssertingVH(const AssertingVH &RHS) : ValueHandleBase(Assert, RHS) {} +#else + AssertingVH() : ThePtr(0) {} + AssertingVH(ValueTy *P) : ThePtr(P) {} +#endif + + operator ValueTy*() const { + return getValPtr(); + } + + ValueTy *operator=(ValueTy *RHS) { + setValPtr(RHS); + return getValPtr(); + } + ValueTy *operator=(AssertingVH<ValueTy> &RHS) { + setValPtr(RHS.getValPtr()); + return getValPtr(); + } + + ValueTy *operator->() const { return getValPtr(); } + ValueTy &operator*() const { return getValPtr(); } + + // Duplicate these from the base class so that they work when assertions are + // off. + bool operator==(const Value *RHS) const { return getValPtr() == RHS; } + bool operator!=(const Value *RHS) const { return getValPtr() != RHS; } + bool operator<(const Value *RHS) const { return getValPtr() < RHS; } + bool operator>(const Value *RHS) const { return getValPtr() > RHS; } + bool operator<=(const Value *RHS) const { return getValPtr() <= RHS; } + bool operator>=(const Value *RHS) const { return getValPtr() >= RHS; } + bool operator==(const AssertingVH &RHS) const { + return getValPtr() == RHS.getValPtr(); + } + bool operator!=(const AssertingVH &RHS) const { + return getValPtr() != RHS.getValPtr(); + } + bool operator<(const AssertingVH &RHS) const { + return getValPtr() < RHS.getValPtr(); + } + bool operator>(const AssertingVH &RHS) const { + return getValPtr() > RHS.getValPtr(); + } + bool operator<=(const AssertingVH &RHS) const { + return getValPtr() <= RHS.getValPtr(); + } + bool operator>=(const AssertingVH &RHS) const { + return getValPtr() >= RHS.getValPtr(); + } +}; + +} // End llvm namespace + +#endif diff --git a/include/llvm/Value.h b/include/llvm/Value.h index 3600a5cef3..531d560a9c 100644 --- a/include/llvm/Value.h +++ b/include/llvm/Value.h @@ -37,6 +37,7 @@ template<typename ValueTy> class StringMapEntry; typedef StringMapEntry<Value*> ValueName; class raw_ostream; class AssemblyAnnotationWriter; +class ValueHandleBase; //===----------------------------------------------------------------------===// // Value Class @@ -50,10 +51,14 @@ class AssemblyAnnotationWriter; /// automatically updates the module's symbol table. /// /// Every value has a "use list" that keeps track of which other Values are -/// using this Value. +/// using this Value. A Value can also have an arbitrary number of ValueHandle +/// objects that watch it and listen to RAUW and Destroy events see +/// llvm/Support/ValueHandle.h for details. +/// /// @brief LLVM Value Representation class Value { const unsigned char SubclassID; // Subclass identifier (for isa/dyn_cast) + unsigned char HasValueHandle : 1; // Has a ValueHandle pointing to this? protected: /// SubclassData - This member is defined by this class, but is not used for /// anything. Subclasses can use it to hold whatever state they find useful. @@ -65,6 +70,7 @@ private: friend class ValueSymbolTable; // Allow ValueSymbolTable to directly mod Name. friend class SymbolTable; // Allow SymbolTable to directly poke Name. + friend class ValueHandleBase; ValueName *Name; void operator=(const Value &); // Do not implement diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp index 0aa2db4439..499b936e29 100644 --- a/lib/VMCore/Value.cpp +++ b/lib/VMCore/Value.cpp @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// // -// This file implements the Value and User classes. +// This file implements the Value, ValueHandle, and User classes. // //===----------------------------------------------------------------------===// @@ -20,6 +20,9 @@ #include "llvm/ValueSymbolTable.h" #include "llvm/Support/Debug.h" #include "llvm/Support/LeakDetector.h" +#include "llvm/Support/ManagedStatic.h" +#include "llvm/Support/ValueHandle.h" +#include "llvm/ADT/DenseMap.h" #include <algorithm> using namespace llvm; @@ -33,7 +36,7 @@ static inline const Type *checkType(const Type *Ty) { } Value::Value(const Type *ty, unsigned scid) - : SubclassID(scid), SubclassData(0), VTy(checkType(ty)), + : SubclassID(scid), HasValueHandle(0), SubclassData(0), VTy(checkType(ty)), UseList(0), Name(0) { if (isa<CallInst>(this) || isa<InvokeInst>(this)) assert((VTy->isFirstClassType() || VTy == Type::VoidTy || @@ -46,6 +49,10 @@ Value::Value(const Type *ty, unsigned scid) } Value::~Value() { + // Notify all ValueHandles (if present) that this value is going away. + if (HasValueHandle) + ValueHandleBase::ValueIsDeleted(this); + #ifndef NDEBUG // Only in -g mode... // Check to make sure that there are no uses of this value that are still // around when the value is destroyed. If there are, then we have a dangling @@ -297,6 +304,10 @@ void Value::takeName(Value *V) { // this problem. // void Value::uncheckedReplaceAllUsesWith(Value *New) { + // Notify all ValueHandles (if present) that this value is going away. + if (HasValueHandle) + ValueHandleBase::ValueIsRAUWd(this, New); + while (!use_empty()) { Use &U = *UseList; // Must handle Constants specially, we cannot call replaceUsesOfWith on a @@ -383,6 +394,158 @@ Value *Value::DoPHITranslation(const BasicBlock *CurBB, return this; } +//===----------------------------------------------------------------------===// +// ValueHandleBase Class +//===----------------------------------------------------------------------===// + +/// ValueHandles - This map keeps track of all of the value handles that are +/// watching a Value*. The Value::HasValueHandle bit is used to know whether or +/// not a value has an entry in this map. +typedef DenseMap<Value*, ValueHandleBase*> ValueHandlesTy; +static ManagedStatic<ValueHandlesTy> ValueHandles; + +/// AddToUseList - Add this ValueHandle to the use list for VP, where List is +/// known to point into the existing use list. +void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) { + assert(List && "Handle list is null?"); + + // Splice ourselves into the list. + Next = *List; + *List = this; + setPrevPtr(List); + if (Next) { + Next->setPrevPtr(&Next); + assert(VP == Next->VP && "Added to wrong list?"); + } +} + +/// AddToUseList - Add this ValueHandle to the use list for VP. +void ValueHandleBase::AddToUseList() { + assert(VP && "Null pointer doesn't have a use list!"); + if (VP->HasValueHandle) { + // If this value already has a ValueHandle, then it must be in the + // ValueHandles map already. + ValueHandleBase *&Entry = (*ValueHandles)[VP]; + assert(Entry != 0 && "Value doesn't have any handles?"); + return AddToExistingUseList(&Entry); + } + + // Ok, it doesn't have any handles yet, so we must insert it into the + // DenseMap. However, doing this insertion could cause the DenseMap to + // reallocate itself, which would invalidate all of the PrevP pointers that + // point into the old table. Handle this by checking for reallocation and + // updating the stale pointers only if needed. + ValueHandlesTy &Handles = *ValueHandles; + const void *OldBucketPtr = Handles.getPointerIntoBucketsArray(); + + ValueHandleBase *&Entry = Handles[VP]; + assert(Entry == 0 && "Value really did already have handles?"); + AddToExistingUseList(&Entry); + VP->HasValueHandle = 1; + + // If reallocation didn't happen or if this was the first insertion, don't + // walk the table. + if (Handles.isPointerIntoBucketsArray(OldBucketPtr) || + Handles.size() == 1) + return; + + // Okay, reallocation did happen. Fix the Prev Pointers. + for (ValueHandlesTy::iterator I = Handles.begin(), E = Handles.end(); + I != E; ++I) { + assert(I->second && I->first == I->second->VP && "List invariant broken!"); + I->second->setPrevPtr(&I->second); + } +} + +/// RemoveFromUseList - Remove this ValueHandle from its current use list. +void ValueHandleBase::RemoveFromUseList() { + assert(VP && VP->HasValueHandle && "Pointer doesn't have a use list!"); + + // Unlink this from its use list. + ValueHandleBase **PrevPtr = getPrevPtr(); + assert(*PrevPtr == this && "List invariant broken"); + + *PrevPtr = Next; + if (Next) { + assert(Next->getPrevPtr() == &Next && "List invariant broken"); + Next->setPrevPtr(PrevPtr); + return; + } + + // If the Next pointer was null, then it is possible that this was the last + // ValueHandle watching VP. If so, delete its entry from the ValueHandles + // map. + ValueHandlesTy &Handles = *ValueHandles; + if (Handles.isPointerIntoBucketsArray(PrevPtr)) { + Handles.erase(VP); + VP->HasValueHandle = false; + } +} + + +void ValueHandleBase::ValueIsDeleted(Value *V) { + assert(V->HasValueHandle && "Should only be called if ValueHandles present"); + + // Get the linked list base, which is guaranteed to exist since the + // HasValueHandle flag is set. + ValueHandleBase *Entry = (*ValueHandles)[V]; + assert(Entry && "Value bit set but no entries exist"); + + while (Entry) { + // Advance pointer to avoid invalidation. + ValueHandleBase *ThisNode = Entry; + Entry = Entry->Next; + + switch (ThisNode->getKind()) { + case Assert: +#ifndef NDEBUG // Only in -g mode... + cerr << "While deleting: " << *V->getType() << " %" << V->getNameStr() + << "\n"; +#endif + cerr << "An asserting value handle still pointed to this value!\n"; + abort(); + case Weak: + // Weak just goes to null, which will unlink it from the list. + ThisNode->operator=(0); + break; + case Callback: + assert(0 && "Callback not implemented yet!"); + } + } + + // All callbacks and weak references should be dropped by now. + assert(!V->HasValueHandle && "All references to V were not removed?"); +} + + +void ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) { + assert(Old->HasValueHandle &&"Should only be called if ValueHandles present"); + assert(Old != New && "Changing value into itself!"); + + // Get the linked list base, which is guaranteed to exist since the + // HasValueHandle flag is set. + ValueHandleBase *Entry = (*ValueHandles)[Old]; + assert(Entry && "Value bit set but no entries exist"); + + while (Entry) { + // Advance pointer to avoid invalidation. + ValueHandleBase *ThisNode = Entry; + Entry = Entry->Next; + + switch (ThisNode->getKind()) { + case Assert: + // Asserting handle does not follow RAUW implicitly. + break; + case Weak: + // Weak goes to the new value, which will unlink it from Old's list. + ThisNode->operator=(New); + break; + case Callback: + assert(0 && "Callback not implemented yet!"); + } + } +} + //===----------------------------------------------------------------------===// // User Class |