X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FIR%2FValue.cpp;h=bda94d057f743ff4d82be1247aff92b20744814b;hp=2ebdb702cf96a60792a08668b9e290dfa8e3ac51;hb=9ed44978efe98a42df1cbf9c3737e29c556b9885;hpb=0b6cb7104b15504cd41f48cc2babcbcee70775f3 diff --git a/lib/IR/Value.cpp b/lib/IR/Value.cpp index 2ebdb702cf9..bda94d057f7 100644 --- a/lib/IR/Value.cpp +++ b/lib/IR/Value.cpp @@ -15,8 +15,10 @@ #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" @@ -38,13 +40,13 @@ using namespace llvm; 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(nullptr), Name(nullptr) { + : VTy(checkType(ty)), UseList(nullptr), Name(nullptr), SubclassID(scid), + HasValueHandle(0), SubclassOptionalData(0), SubclassData(0), + NumOperands(0) { // FIXME: Why isn't this in the subclass gunk?? // Note, we cannot call isa before the CallInst has been // constructed. @@ -87,8 +89,6 @@ Value::~Value() { LeakDetector::removeGarbageObject(this); } -/// 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 +97,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 +106,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 @@ -132,10 +127,6 @@ 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()); } @@ -214,7 +205,7 @@ void Value::setName(const Twine &NewName) { // then reallocated. // Create the new name. - Name = ValueName::Create(NameRef.begin(), NameRef.end()); + Name = ValueName::Create(NameRef); Name->setValue(this); return; } @@ -235,9 +226,6 @@ void Value::setName(const Twine &NewName) { Name = ST->createValueName(NameRef, this); } - -/// 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!"); @@ -301,10 +289,45 @@ void Value::takeName(Value *V) { ST->reinsertValue(this); } +#ifndef NDEBUG +static bool contains(SmallPtrSetImpl &Cache, ConstantExpr *Expr, + Constant *C) { + if (!Cache.insert(Expr)) + 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!"); @@ -316,7 +339,7 @@ void Value::replaceAllUsesWith(Value *New) { 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); continue; @@ -419,7 +442,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(); @@ -436,34 +460,71 @@ 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) { +/// \brief Check if Value is always a dereferenceable pointer. +/// +/// Test if V is always a pointer to allocated and suitably aligned memory for +/// a simple load or store. +static bool isDereferenceablePointer(const Value *V, const DataLayout *DL, + SmallPtrSetImpl &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; + // It's 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. However, + // if we're casting from a pointer from a type of larger size + // to a type of smaller size (or the same size), and the alignment + // is at least as large as for the resulting pointer type, then + // we can look through the bitcast. + if (DL) + if (const BitCastInst* BC = dyn_cast(V)) { + Type *STy = BC->getSrcTy()->getPointerElementType(), + *DTy = BC->getDestTy()->getPointerElementType(); + if (STy->isSized() && DTy->isSized() && + (DL->getTypeStoreSize(STy) >= + DL->getTypeStoreSize(DTy)) && + (DL->getABITypeAlignment(STy) >= + DL->getABITypeAlignment(DTy))) + return isDereferenceablePointer(BC->getOperand(0), DL, Visited); + } + // 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(); + // byval arguments are okay. Arguments specifically marked as + // dereferenceable are okay too. + if (const Argument *A = dyn_cast(V)) { + if (A->hasByValAttr()) + return true; + else if (uint64_t Bytes = A->getDereferenceableBytes()) { + Type *Ty = V->getType()->getPointerElementType(); + if (Ty->isSized() && DL && DL->getTypeStoreSize(Ty) <= Bytes) + return true; + } + + return false; + } + + // Return values from call sites specifically marked as dereferenceable are + // also okay. + if (ImmutableCallSite CS = V) { + if (uint64_t Bytes = CS.getDereferenceableBytes(0)) { + Type *Ty = V->getType()->getPointerElementType(); + if (Ty->isSized() && DL && DL->getTypeStoreSize(Ty) <= Bytes) + return true; + } + } // 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)) + if (!isDereferenceablePointer(GEP->getOperand(0), DL, Visited)) return false; // Check the indices. gep_type_iterator GTI = gep_type_begin(GEP); @@ -493,21 +554,39 @@ static bool isDereferenceablePointer(const Value *V, return true; } + if (const AddrSpaceCastInst *ASC = dyn_cast(V)) + return isDereferenceablePointer(ASC->getOperand(0), DL, Visited); + // 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 { +bool Value::isDereferenceablePointer(const DataLayout *DL) const { + // When dereferenceability information is provided by a dereferenceable + // attribute, we know exactly how many bytes are dereferenceable. If we can + // determine the exact offset to the attributed variable, we can use that + // information here. + Type *Ty = getType()->getPointerElementType(); + if (Ty->isSized() && DL) { + APInt Offset(DL->getTypeStoreSizeInBits(getType()), 0); + const Value *BV = stripAndAccumulateInBoundsConstantOffsets(*DL, Offset); + + APInt DerefBytes(Offset.getBitWidth(), 0); + if (const Argument *A = dyn_cast(BV)) + DerefBytes = A->getDereferenceableBytes(); + else if (ImmutableCallSite CS = BV) + DerefBytes = CS.getDereferenceableBytes(0); + + if (DerefBytes.getBoolValue() && Offset.isNonNegative()) { + if (DerefBytes.uge(Offset + DL->getTypeStoreSize(Ty))) + return true; + } + } + SmallPtrSet Visited; - return ::isDereferenceablePointer(this, Visited); + return ::isDereferenceablePointer(this, DL, 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 +597,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?"); @@ -547,7 +643,6 @@ 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!"); @@ -591,7 +686,6 @@ void ValueHandleBase::AddToUseList() { } } -/// RemoveFromUseList - Remove this ValueHandle from its current use list. void ValueHandleBase::RemoveFromUseList() { assert(VP.getPointer() && VP.getPointer()->HasValueHandle && "Pointer doesn't have a use list!"); @@ -679,6 +773,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.