X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FValue.cpp;h=c952b7888cddcf3a3dce97c14ac5846887dcf32b;hb=7ce720b448c581b822577aaf44b73a5aa9689dfc;hp=e581fe83807331d7569e4c55e09c167a998f5741;hpb=502a4f5162498ec420e3cb22f667808d726dd7da;p=oota-llvm.git diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp index e581fe83807..c952b7888cd 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,11 @@ #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/System/RWMutex.h" +#include "llvm/System/Threading.h" +#include "llvm/ADT/DenseMap.h" #include using namespace llvm; @@ -33,19 +38,23 @@ static inline const Type *checkType(const Type *Ty) { } Value::Value(const Type *ty, unsigned scid) - : SubclassID(scid), SubclassData(0), Ty(checkType(ty)), + : SubclassID(scid), HasValueHandle(0), SubclassData(0), VTy(checkType(ty)), UseList(0), Name(0) { if (isa(this) || isa(this)) - assert((Ty->isFirstClassType() || Ty == Type::VoidTy || - isa(ty) || Ty->getTypeID() == Type::StructTyID) && + assert((VTy->isFirstClassType() || VTy == Type::VoidTy || + isa(ty) || VTy->getTypeID() == Type::StructTyID) && "invalid CallInst type!"); else if (!isa(this) && !isa(this)) - assert((Ty->isFirstClassType() || Ty == Type::VoidTy || + assert((VTy->isFirstClassType() || VTy == Type::VoidTy || isa(ty)) && "Cannot create non-first-class values except for constants!"); } 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 @@ -54,9 +63,9 @@ Value::~Value() { // a // if (!use_empty()) { - DOUT << "While deleting: " << *Ty << " %" << getNameStr() << "\n"; + cerr << "While deleting: " << *VTy << " %" << getNameStr() << "\n"; for (use_iterator I = use_begin(), E = use_end(); I != E; ++I) - DOUT << "Use still stuck around after Def is destroyed:" + cerr << "Use still stuck around after Def is destroyed:" << **I << "\n"; } #endif @@ -95,7 +104,7 @@ bool Value::hasNUsesOrMore(unsigned N) const { /// isUsedInBasicBlock - Return true if this value is used in the specified /// basic block. -bool Value::isUsedInBasicBlock(BasicBlock *BB) const { +bool Value::isUsedInBasicBlock(const BasicBlock *BB) const { for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I) { const Instruction *User = dyn_cast(*I); if (User && User->getParent() == BB) @@ -264,7 +273,7 @@ void Value::takeName(Value *V) { // Get V's ST, this should always succed, because V has a name. ValueSymbolTable *VST; bool Failure = getSymTab(V, VST); - assert(!Failure && "V has a name, so it should have a ST!"); + assert(!Failure && "V has a name, so it should have a ST!"); Failure=Failure; // If these values are both in the same symtab, we can do this very fast. // This works even if both values have no symtab yet. @@ -297,6 +306,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 @@ -322,29 +335,240 @@ void Value::replaceAllUsesWith(Value *New) { } Value *Value::stripPointerCasts() { - if (ConstantExpr *CE = dyn_cast(this)) { - if (CE->getOpcode() == Instruction::BitCast) { - if (isa(CE->getOperand(0)->getType())) - return CE->getOperand(0)->stripPointerCasts(); - } else if (CE->getOpcode() == Instruction::GetElementPtr) { - for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) - if (!CE->getOperand(i)->isNullValue()) - return this; - return CE->getOperand(0)->stripPointerCasts(); + if (!isa(getType())) + return this; + Value *V = this; + do { + if (ConstantExpr *CE = dyn_cast(V)) { + if (CE->getOpcode() == Instruction::GetElementPtr) { + for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) + if (!CE->getOperand(i)->isNullValue()) + return V; + V = CE->getOperand(0); + } else if (CE->getOpcode() == Instruction::BitCast) { + V = CE->getOperand(0); + } else { + return V; + } + } else if (GetElementPtrInst *GEP = dyn_cast(V)) { + if (!GEP->hasAllZeroIndices()) + return V; + V = GEP->getOperand(0); + } else if (BitCastInst *CI = dyn_cast(V)) { + V = CI->getOperand(0); + } else { + return V; } + assert(isa(V->getType()) && "Unexpected operand type!"); + } while (1); +} + +Value *Value::getUnderlyingObject() { + if (!isa(getType())) return this; + Value *V = this; + unsigned MaxLookup = 6; + do { + if (Instruction *I = dyn_cast(V)) { + if (!isa(I) && !isa(I)) + return V; + V = I->getOperand(0); + } else if (ConstantExpr *CE = dyn_cast(V)) { + if (CE->getOpcode() != Instruction::BitCast && + CE->getOpcode() != Instruction::GetElementPtr) + return V; + V = CE->getOperand(0); + } else { + return V; + } + assert(isa(V->getType()) && "Unexpected operand type!"); + } while (--MaxLookup); + return V; +} + +/// DoPHITranslation - If this value is a PHI node with CurBB as its parent, +/// return the value in the PHI node corresponding to PredBB. If not, return +/// ourself. This is useful if you want to know the value something has in a +/// predecessor block. +Value *Value::DoPHITranslation(const BasicBlock *CurBB, + const BasicBlock *PredBB) { + PHINode *PN = dyn_cast(this); + if (PN && PN->getParent() == CurBB) + return PN->getIncomingValueForBlock(PredBB); + 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 ValueHandlesTy; +static ManagedStatic ValueHandles; +static ManagedStatic > ValueHandlesLock; + +/// AddToExistingUseList - 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?"); } +} - if (BitCastInst *CI = dyn_cast(this)) { - if (isa(CI->getOperand(0)->getType())) - return CI->getOperand(0)->stripPointerCasts(); - } else if (GetElementPtrInst *GEP = dyn_cast(this)) { - if (GEP->hasAllZeroIndices()) - return GEP->getOperand(0)->stripPointerCasts(); +/// 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. + sys::SmartScopedReader Reader(&*ValueHandlesLock); + ValueHandleBase *&Entry = (*ValueHandles)[VP]; + assert(Entry != 0 && "Value doesn't have any handles?"); + AddToExistingUseList(&Entry); + return; + } + + // 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. + sys::SmartScopedWriter Writer(&*ValueHandlesLock); + 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 = true; + + // 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); } - return this; } +/// 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. + sys::SmartScopedWriter Writer(&*ValueHandlesLock); + 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. + ValueHandlesLock->reader_acquire(); + ValueHandleBase *Entry = (*ValueHandles)[V]; + ValueHandlesLock->reader_release(); + 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: + // Forward to the subclass's implementation. + static_cast(ThisNode)->deleted(); + break; + } + } + + // 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. + ValueHandlesLock->reader_acquire(); + ValueHandleBase *Entry = (*ValueHandles)[Old]; + ValueHandlesLock->reader_release(); + 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: + // Forward to the subclass's implementation. + static_cast(ThisNode)->allUsesReplacedWith(New); + break; + } + } +} + +/// ~CallbackVH. Empty, but defined here to avoid emitting the vtable +/// more than once. +CallbackVH::~CallbackVH() {} + + //===----------------------------------------------------------------------===// // User Class //===----------------------------------------------------------------------===// @@ -367,21 +591,3 @@ void User::replaceUsesOfWith(Value *From, Value *To) { } } -void *User::operator new(size_t s, unsigned Us) { - void *Storage = ::operator new(s + sizeof(Use) * Us); - Use *Start = static_cast(Storage); - Use *End = Start + Us; - User *Obj = reinterpret_cast(End); - Obj->OperandList = Start; - Obj->NumOperands = Us; - Use::initTags(Start, End); - return Obj; -} - -void User::operator delete(void *Usr) { - User *Start = static_cast(Usr); - Use *Storage = static_cast(Usr) - Start->NumOperands; - ::operator delete(Storage == Start->OperandList - ? Storage - : Usr); -}