X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FIR%2FValue.cpp;h=f554d590284fa895762527e7fa8eab569499e548;hb=67bd697ef77533a1af0621293eebb3cd51addf65;hp=2c90383edd8c2ecff8e015ac161529f94f216758;hpb=edeaa6454ef1dc29fa3144b93e2121495b160b35;p=oota-llvm.git diff --git a/lib/IR/Value.cpp b/lib/IR/Value.cpp index 2c90383edd8..f554d590284 100644 --- a/lib/IR/Value.cpp +++ b/lib/IR/Value.cpp @@ -15,36 +15,39 @@ #include "LLVMContextImpl.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallString.h" +#include "llvm/IR/CallSite.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" +#include "llvm/IR/DataLayout.h" #include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" +#include "llvm/IR/Statepoint.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/IR/ValueSymbolTable.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/GetElementPtrTypeIterator.h" -#include "llvm/Support/LeakDetector.h" #include "llvm/Support/ManagedStatic.h" -#include "llvm/Support/ValueHandle.h" +#include "llvm/Support/raw_ostream.h" #include using namespace llvm; //===----------------------------------------------------------------------===// // Value Class //===----------------------------------------------------------------------===// - static inline Type *checkType(Type *Ty) { assert(Ty && "Value defined with a null type: Error!"); - return const_cast(Ty); + return Ty; } Value::Value(Type *ty, unsigned scid) - : SubclassID(scid), HasValueHandle(0), - SubclassOptionalData(0), SubclassData(0), VTy((Type*)checkType(ty)), - UseList(0), Name(0) { + : VTy(checkType(ty)), UseList(nullptr), SubclassID(scid), + HasValueHandle(0), SubclassOptionalData(0), SubclassData(0), + NumUserOperands(0), IsUsedByMD(false), HasName(false) { // FIXME: Why isn't this in the subclass gunk?? // Note, we cannot call isa before the CallInst has been // constructed. @@ -61,34 +64,35 @@ Value::~Value() { // Notify all ValueHandles (if present) that this value is going away. if (HasValueHandle) ValueHandleBase::ValueIsDeleted(this); + if (isUsedByMetadata()) + ValueAsMetadata::handleDeletion(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 - // reference and something is wrong. This code is here to print out what is - // still being referenced. The value in question should be printed as - // a + // reference and something is wrong. This code is here to print out where + // the value is still being referenced. // if (!use_empty()) { dbgs() << "While deleting: " << *VTy << " %" << getName() << "\n"; - for (use_iterator I = use_begin(), E = use_end(); I != E; ++I) - dbgs() << "Use still stuck around after Def is destroyed:" - << **I << "\n"; + for (auto *U : users()) + dbgs() << "Use still stuck around after Def is destroyed:" << *U << "\n"; } #endif assert(use_empty() && "Uses remain when a value is destroyed!"); // If this value is named, destroy the name. This should not be in a symtab // at this point. - if (Name && SubclassID != MDStringVal) - Name->Destroy(); + destroyValueName(); +} - // There should be no uses of this object anymore, remove it. - LeakDetector::removeGarbageObject(this); +void Value::destroyValueName() { + ValueName *Name = getValueName(); + if (Name) + Name->Destroy(); + setValueName(nullptr); } -/// hasNUses - Return true if this Value has exactly N users. -/// bool Value::hasNUses(unsigned N) const { const_use_iterator UI = use_begin(), E = use_end(); @@ -97,9 +101,6 @@ bool Value::hasNUses(unsigned N) const { return UI == E; } -/// hasNUsesOrMore - Return true if this value has N users or more. This is -/// logically equivalent to getNumUses() >= N. -/// bool Value::hasNUsesOrMore(unsigned N) const { const_use_iterator UI = use_begin(), E = use_end(); @@ -109,8 +110,6 @@ bool Value::hasNUsesOrMore(unsigned N) const { return true; } -/// isUsedInBasicBlock - Return true if this value is used in the specified -/// basic block. bool Value::isUsedInBasicBlock(const BasicBlock *BB) const { // This can be computed either by scanning the instructions in BB, or by // scanning the use list of this Value. Both lists can be very long, but @@ -119,7 +118,7 @@ bool Value::isUsedInBasicBlock(const BasicBlock *BB) const { // Scan both lists simultaneously until one is exhausted. This limits the // search to the shorter list. BasicBlock::const_iterator BI = BB->begin(), BE = BB->end(); - const_use_iterator UI = use_begin(), UE = use_end(); + const_user_iterator UI = user_begin(), UE = user_end(); for (; BI != BE && UI != UE; ++BI, ++UI) { // Scan basic block: Check if this Value is used by the instruction at BI. if (std::find(BI->op_begin(), BI->op_end(), this) != BI->op_end()) @@ -132,16 +131,12 @@ bool Value::isUsedInBasicBlock(const BasicBlock *BB) const { return false; } - -/// 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 Value::getNumUses() const { return (unsigned)std::distance(use_begin(), use_end()); } static bool getSymTab(Value *V, ValueSymbolTable *&ST) { - ST = 0; + ST = nullptr; if (Instruction *I = dyn_cast(V)) { if (BasicBlock *P = I->getParent()) if (Function *PP = P->getParent()) @@ -155,27 +150,51 @@ static bool getSymTab(Value *V, ValueSymbolTable *&ST) { } else if (Argument *A = dyn_cast(V)) { if (Function *P = A->getParent()) ST = &P->getValueSymbolTable(); - } else if (isa(V)) - return true; - else { + } else { assert(isa(V) && "Unknown value type!"); return true; // no name is setable for this. } return false; } +ValueName *Value::getValueName() const { + if (!HasName) return nullptr; + + LLVMContext &Ctx = getContext(); + auto I = Ctx.pImpl->ValueNames.find(this); + assert(I != Ctx.pImpl->ValueNames.end() && + "No name entry found!"); + + return I->second; +} + +void Value::setValueName(ValueName *VN) { + LLVMContext &Ctx = getContext(); + + assert(HasName == Ctx.pImpl->ValueNames.count(this) && + "HasName bit out of sync!"); + + if (!VN) { + if (HasName) + Ctx.pImpl->ValueNames.erase(this); + HasName = false; + return; + } + + HasName = true; + Ctx.pImpl->ValueNames[this] = VN; +} + StringRef Value::getName() const { // Make sure the empty string is still a C string. For historical reasons, // some clients want to call .data() on the result and expect it to be null // terminated. - if (!Name) return StringRef("", 0); - return Name->getKey(); + if (!hasName()) + return StringRef("", 0); + return getValueName()->getKey(); } -void Value::setName(const Twine &NewName) { - assert(SubclassID != MDStringVal && - "Cannot set the name of MDString with this method!"); - +void Value::setNameImpl(const Twine &NewName) { // Fast path for common IRBuilder case of setName("") when there is no name. if (NewName.isTriviallyEmpty() && !hasName()) return; @@ -196,26 +215,20 @@ void Value::setName(const Twine &NewName) { if (getSymTab(this, ST)) return; // Cannot set a name on this value (e.g. constant). - if (Function *F = dyn_cast(this)) - getContext().pImpl->IntrinsicIDCache.erase(F); - if (!ST) { // No symbol table to update? Just do the change. if (NameRef.empty()) { // Free the name for this value. - Name->Destroy(); - Name = 0; + destroyValueName(); return; } - if (Name) - Name->Destroy(); - // NOTE: Could optimize for the case the name is shrinking to not deallocate // then reallocated. + destroyValueName(); // Create the new name. - Name = ValueName::Create(NameRef.begin(), NameRef.end()); - Name->setValue(this); + setValueName(ValueName::Create(NameRef)); + getValueName()->setValue(this); return; } @@ -223,25 +236,25 @@ void Value::setName(const Twine &NewName) { // then reallocated. if (hasName()) { // Remove old name. - ST->removeValueName(Name); - Name->Destroy(); - Name = 0; + ST->removeValueName(getValueName()); + destroyValueName(); if (NameRef.empty()) return; } // Name is changing to something new. - Name = ST->createValueName(NameRef, this); + setValueName(ST->createValueName(NameRef, this)); } +void Value::setName(const Twine &NewName) { + setNameImpl(NewName); + if (Function *F = dyn_cast(this)) + F->recalculateIntrinsicID(); +} -/// takeName - transfer the name from V to this value, setting V's name to -/// empty. It is an error to call V->takeName(V). void Value::takeName(Value *V) { - assert(SubclassID != MDStringVal && "Cannot take the name of an MDString!"); - - ValueSymbolTable *ST = 0; + ValueSymbolTable *ST = nullptr; // If this value has a name, drop it. if (hasName()) { // Get the symtab this is in. @@ -254,9 +267,8 @@ void Value::takeName(Value *V) { // Remove old name. if (ST) - ST->removeValueName(Name); - Name->Destroy(); - Name = 0; + ST->removeValueName(getValueName()); + destroyValueName(); } // Now we know that this has no name. @@ -282,9 +294,9 @@ void Value::takeName(Value *V) { // This works even if both values have no symtab yet. if (ST == VST) { // Take the name! - Name = V->Name; - V->Name = 0; - Name->setValue(this); + setValueName(V->getValueName()); + V->setValueName(nullptr); + getValueName()->setValue(this); return; } @@ -292,33 +304,70 @@ void Value::takeName(Value *V) { // then reinsert it into ST. if (VST) - VST->removeValueName(V->Name); - Name = V->Name; - V->Name = 0; - Name->setValue(this); + VST->removeValueName(V->getValueName()); + setValueName(V->getValueName()); + V->setValueName(nullptr); + getValueName()->setValue(this); if (ST) ST->reinsertValue(this); } +#ifndef NDEBUG +static bool contains(SmallPtrSetImpl &Cache, ConstantExpr *Expr, + Constant *C) { + if (!Cache.insert(Expr).second) + return false; + + for (auto &O : Expr->operands()) { + if (O == C) + return true; + auto *CE = dyn_cast(O); + if (!CE) + continue; + if (contains(Cache, CE, C)) + return true; + } + return false; +} + +static bool contains(Value *Expr, Value *V) { + if (Expr == V) + return true; + + auto *C = dyn_cast(V); + if (!C) + return false; + + auto *CE = dyn_cast(Expr); + if (!CE) + return false; + + SmallPtrSet Cache; + return contains(Cache, CE, C); +} +#endif void Value::replaceAllUsesWith(Value *New) { assert(New && "Value::replaceAllUsesWith() is invalid!"); - assert(New != this && "this->replaceAllUsesWith(this) is NOT valid!"); + assert(!contains(New, this) && + "this->replaceAllUsesWith(expr(this)) is NOT valid!"); assert(New->getType() == getType() && "replaceAllUses of value with new value of different type!"); // Notify all ValueHandles (if present) that this value is going away. if (HasValueHandle) ValueHandleBase::ValueIsRAUWd(this, New); + if (isUsedByMetadata()) + ValueAsMetadata::handleRAUW(this, New); while (!use_empty()) { Use &U = *UseList; // Must handle Constants specially, we cannot call replaceUsesOfWith on a // constant because they are uniqued. - if (Constant *C = dyn_cast(U.getUser())) { + if (auto *C = dyn_cast(U.getUser())) { if (!isa(C)) { - C->replaceUsesOfWithOnConstant(this, New, &U); + C->handleOperandChange(this, New, &U); continue; } } @@ -330,6 +379,28 @@ void Value::replaceAllUsesWith(Value *New) { BB->replaceSuccessorsPhiUsesWith(cast(New)); } +// Like replaceAllUsesWith except it does not handle constants or basic blocks. +// This routine leaves uses within BB. +void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) { + assert(New && "Value::replaceUsesOutsideBlock(, BB) is invalid!"); + assert(!contains(New, this) && + "this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!"); + assert(New->getType() == getType() && + "replaceUses of value with new value of different type!"); + assert(BB && "Basic block that may contain a use of 'New' must be defined\n"); + + use_iterator UI = use_begin(), E = use_end(); + for (; UI != E;) { + Use &U = *UI; + ++UI; + auto *Usr = dyn_cast(U.getUser()); + if (Usr && Usr->getParent() == BB) + continue; + U.set(New); + } + return; +} + namespace { // Various metrics for how much to strip off of pointers. enum PointerStripKind { @@ -378,7 +449,7 @@ static Value *stripPointerCastsAndOffsets(Value *V) { return V; } assert(V->getType()->isPointerTy() && "Unexpected operand type!"); - } while (Visited.insert(V)); + } while (Visited.insert(V).second); return V; } @@ -419,7 +490,8 @@ Value *Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, return V; Offset = GEPOffset; V = GEP->getPointerOperand(); - } else if (Operator::getOpcode(V) == Instruction::BitCast) { + } else if (Operator::getOpcode(V) == Instruction::BitCast || + Operator::getOpcode(V) == Instruction::AddrSpaceCast) { V = cast(V)->getOperand(0); } else if (GlobalAlias *GA = dyn_cast(V)) { V = GA->getAliasee(); @@ -427,7 +499,7 @@ Value *Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, return V; } assert(V->getType()->isPointerTy() && "Unexpected operand type!"); - } while (Visited.insert(V)); + } while (Visited.insert(V).second); return V; } @@ -436,78 +508,6 @@ Value *Value::stripInBoundsOffsets() { return stripPointerCastsAndOffsets(this); } -/// isDereferenceablePointer - Test if this value is always a pointer to -/// allocated and suitably aligned memory for a simple load or store. -static bool isDereferenceablePointer(const Value *V, - SmallPtrSet &Visited) { - // Note that it is not safe to speculate into a malloc'd region because - // malloc may return null. - // It's also not always safe to follow a bitcast, for example: - // bitcast i8* (alloca i8) to i32* - // would result in a 4-byte load from a 1-byte alloca. Some cases could - // be handled using DataLayout to check sizes and alignments though. - - // These are obviously ok. - if (isa(V)) return true; - - // Global variables which can't collapse to null are ok. - if (const GlobalVariable *GV = dyn_cast(V)) - return !GV->hasExternalWeakLinkage(); - - // byval arguments are ok. - if (const Argument *A = dyn_cast(V)) - return A->hasByValAttr(); - - // For GEPs, determine if the indexing lands within the allocated object. - if (const GEPOperator *GEP = dyn_cast(V)) { - // Conservatively require that the base pointer be fully dereferenceable. - if (!Visited.insert(GEP->getOperand(0))) - return false; - if (!isDereferenceablePointer(GEP->getOperand(0), Visited)) - return false; - // Check the indices. - gep_type_iterator GTI = gep_type_begin(GEP); - for (User::const_op_iterator I = GEP->op_begin()+1, - E = GEP->op_end(); I != E; ++I) { - Value *Index = *I; - Type *Ty = *GTI++; - // Struct indices can't be out of bounds. - if (isa(Ty)) - continue; - ConstantInt *CI = dyn_cast(Index); - if (!CI) - return false; - // Zero is always ok. - if (CI->isZero()) - continue; - // Check to see that it's within the bounds of an array. - ArrayType *ATy = dyn_cast(Ty); - if (!ATy) - return false; - if (CI->getValue().getActiveBits() > 64) - return false; - if (CI->getZExtValue() >= ATy->getNumElements()) - return false; - } - // Indices check out; this is dereferenceable. - return true; - } - - // If we don't know, assume the worst. - return false; -} - -/// isDereferenceablePointer - Test if this value is always a pointer to -/// allocated and suitably aligned memory for a simple load or store. -bool Value::isDereferenceablePointer() const { - SmallPtrSet Visited; - return ::isDereferenceablePointer(this, Visited); -} - -/// 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); @@ -518,12 +518,29 @@ Value *Value::DoPHITranslation(const BasicBlock *CurBB, LLVMContext &Value::getContext() const { return VTy->getContext(); } +void Value::reverseUseList() { + if (!UseList || !UseList->Next) + // No need to reverse 0 or 1 uses. + return; + + Use *Head = UseList; + Use *Current = UseList->Next; + Head->Next = nullptr; + while (Current) { + Use *Next = Current->Next; + Current->Next = Head; + Head->setPrev(&Current->Next); + Head = Current; + Current = Next; + } + UseList = Head; + Head->setPrev(&UseList); +} + //===----------------------------------------------------------------------===// // ValueHandleBase Class //===----------------------------------------------------------------------===// -/// 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?"); @@ -533,7 +550,7 @@ void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) { setPrevPtr(List); if (Next) { Next->setPrevPtr(&Next); - assert(VP.getPointer() == Next->VP.getPointer() && "Added to wrong list?"); + assert(V == Next->V && "Added to wrong list?"); } } @@ -547,17 +564,16 @@ void ValueHandleBase::AddToExistingUseListAfter(ValueHandleBase *List) { Next->setPrevPtr(&Next); } -/// AddToUseList - Add this ValueHandle to the use list for VP. void ValueHandleBase::AddToUseList() { - assert(VP.getPointer() && "Null pointer doesn't have a use list!"); + assert(V && "Null pointer doesn't have a use list!"); - LLVMContextImpl *pImpl = VP.getPointer()->getContext().pImpl; + LLVMContextImpl *pImpl = V->getContext().pImpl; - if (VP.getPointer()->HasValueHandle) { + if (V->HasValueHandle) { // If this value already has a ValueHandle, then it must be in the // ValueHandles map already. - ValueHandleBase *&Entry = pImpl->ValueHandles[VP.getPointer()]; - assert(Entry != 0 && "Value doesn't have any handles?"); + ValueHandleBase *&Entry = pImpl->ValueHandles[V]; + assert(Entry && "Value doesn't have any handles?"); AddToExistingUseList(&Entry); return; } @@ -570,10 +586,10 @@ void ValueHandleBase::AddToUseList() { DenseMap &Handles = pImpl->ValueHandles; const void *OldBucketPtr = Handles.getPointerIntoBucketsArray(); - ValueHandleBase *&Entry = Handles[VP.getPointer()]; - assert(Entry == 0 && "Value really did already have handles?"); + ValueHandleBase *&Entry = Handles[V]; + assert(!Entry && "Value really did already have handles?"); AddToExistingUseList(&Entry); - VP.getPointer()->HasValueHandle = true; + V->HasValueHandle = true; // If reallocation didn't happen or if this was the first insertion, don't // walk the table. @@ -585,15 +601,14 @@ void ValueHandleBase::AddToUseList() { // Okay, reallocation did happen. Fix the Prev Pointers. for (DenseMap::iterator I = Handles.begin(), E = Handles.end(); I != E; ++I) { - assert(I->second && I->first == I->second->VP.getPointer() && + assert(I->second && I->first == I->second->V && "List invariant broken!"); I->second->setPrevPtr(&I->second); } } -/// RemoveFromUseList - Remove this ValueHandle from its current use list. void ValueHandleBase::RemoveFromUseList() { - assert(VP.getPointer() && VP.getPointer()->HasValueHandle && + assert(V && V->HasValueHandle && "Pointer doesn't have a use list!"); // Unlink this from its use list. @@ -610,11 +625,11 @@ void ValueHandleBase::RemoveFromUseList() { // 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. - LLVMContextImpl *pImpl = VP.getPointer()->getContext().pImpl; + LLVMContextImpl *pImpl = V->getContext().pImpl; DenseMap &Handles = pImpl->ValueHandles; if (Handles.isPointerIntoBucketsArray(PrevPtr)) { - Handles.erase(VP.getPointer()); - VP.getPointer()->HasValueHandle = false; + Handles.erase(V); + V->HasValueHandle = false; } } @@ -652,7 +667,7 @@ void ValueHandleBase::ValueIsDeleted(Value *V) { break; case Weak: // Weak just goes to null, which will unlink it from the list. - Entry->operator=(0); + Entry->operator=(nullptr); break; case Callback: // Forward to the subclass's implementation. @@ -679,6 +694,8 @@ void ValueHandleBase::ValueIsDeleted(Value *V) { void ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) { assert(Old->HasValueHandle &&"Should only be called if ValueHandles present"); assert(Old != New && "Changing value into itself!"); + assert(Old->getType() == New->getType() && + "replaceAllUses of value with new value of different type!"); // Get the linked list base, which is guaranteed to exist since the // HasValueHandle flag is set.