1249259Sdim//===-- Value.cpp - Implement the Value class -----------------------------===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// This file implements the Value, ValueHandle, and User classes. 11249259Sdim// 12249259Sdim//===----------------------------------------------------------------------===// 13249259Sdim 14249259Sdim#include "llvm/IR/Value.h" 15249259Sdim#include "LLVMContextImpl.h" 16249259Sdim#include "llvm/ADT/DenseMap.h" 17249259Sdim#include "llvm/ADT/SmallString.h" 18249259Sdim#include "llvm/IR/Constant.h" 19249259Sdim#include "llvm/IR/Constants.h" 20249259Sdim#include "llvm/IR/DerivedTypes.h" 21249259Sdim#include "llvm/IR/InstrTypes.h" 22249259Sdim#include "llvm/IR/Instructions.h" 23249259Sdim#include "llvm/IR/Module.h" 24249259Sdim#include "llvm/IR/Operator.h" 25249259Sdim#include "llvm/IR/ValueSymbolTable.h" 26249259Sdim#include "llvm/Support/Debug.h" 27249259Sdim#include "llvm/Support/ErrorHandling.h" 28249259Sdim#include "llvm/Support/GetElementPtrTypeIterator.h" 29249259Sdim#include "llvm/Support/LeakDetector.h" 30249259Sdim#include "llvm/Support/ManagedStatic.h" 31249259Sdim#include "llvm/Support/ValueHandle.h" 32249259Sdim#include <algorithm> 33249259Sdimusing namespace llvm; 34249259Sdim 35249259Sdim//===----------------------------------------------------------------------===// 36249259Sdim// Value Class 37249259Sdim//===----------------------------------------------------------------------===// 38249259Sdim 39249259Sdimstatic inline Type *checkType(Type *Ty) { 40249259Sdim assert(Ty && "Value defined with a null type: Error!"); 41249259Sdim return const_cast<Type*>(Ty); 42249259Sdim} 43249259Sdim 44249259SdimValue::Value(Type *ty, unsigned scid) 45249259Sdim : SubclassID(scid), HasValueHandle(0), 46249259Sdim SubclassOptionalData(0), SubclassData(0), VTy((Type*)checkType(ty)), 47249259Sdim UseList(0), Name(0) { 48249259Sdim // FIXME: Why isn't this in the subclass gunk?? 49249259Sdim // Note, we cannot call isa<CallInst> before the CallInst has been 50249259Sdim // constructed. 51249259Sdim if (SubclassID == Instruction::Call || SubclassID == Instruction::Invoke) 52249259Sdim assert((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) && 53249259Sdim "invalid CallInst type!"); 54249259Sdim else if (SubclassID != BasicBlockVal && 55249259Sdim (SubclassID < ConstantFirstVal || SubclassID > ConstantLastVal)) 56249259Sdim assert((VTy->isFirstClassType() || VTy->isVoidTy()) && 57249259Sdim "Cannot create non-first-class values except for constants!"); 58249259Sdim} 59249259Sdim 60249259SdimValue::~Value() { 61249259Sdim // Notify all ValueHandles (if present) that this value is going away. 62249259Sdim if (HasValueHandle) 63249259Sdim ValueHandleBase::ValueIsDeleted(this); 64249259Sdim 65249259Sdim#ifndef NDEBUG // Only in -g mode... 66249259Sdim // Check to make sure that there are no uses of this value that are still 67249259Sdim // around when the value is destroyed. If there are, then we have a dangling 68249259Sdim // reference and something is wrong. This code is here to print out what is 69249259Sdim // still being referenced. The value in question should be printed as 70249259Sdim // a <badref> 71249259Sdim // 72249259Sdim if (!use_empty()) { 73249259Sdim dbgs() << "While deleting: " << *VTy << " %" << getName() << "\n"; 74249259Sdim for (use_iterator I = use_begin(), E = use_end(); I != E; ++I) 75249259Sdim dbgs() << "Use still stuck around after Def is destroyed:" 76249259Sdim << **I << "\n"; 77249259Sdim } 78249259Sdim#endif 79249259Sdim assert(use_empty() && "Uses remain when a value is destroyed!"); 80249259Sdim 81249259Sdim // If this value is named, destroy the name. This should not be in a symtab 82249259Sdim // at this point. 83249259Sdim if (Name && SubclassID != MDStringVal) 84249259Sdim Name->Destroy(); 85249259Sdim 86249259Sdim // There should be no uses of this object anymore, remove it. 87249259Sdim LeakDetector::removeGarbageObject(this); 88249259Sdim} 89249259Sdim 90249259Sdim/// hasNUses - Return true if this Value has exactly N users. 91249259Sdim/// 92249259Sdimbool Value::hasNUses(unsigned N) const { 93249259Sdim const_use_iterator UI = use_begin(), E = use_end(); 94249259Sdim 95249259Sdim for (; N; --N, ++UI) 96249259Sdim if (UI == E) return false; // Too few. 97249259Sdim return UI == E; 98249259Sdim} 99249259Sdim 100249259Sdim/// hasNUsesOrMore - Return true if this value has N users or more. This is 101249259Sdim/// logically equivalent to getNumUses() >= N. 102249259Sdim/// 103249259Sdimbool Value::hasNUsesOrMore(unsigned N) const { 104249259Sdim const_use_iterator UI = use_begin(), E = use_end(); 105249259Sdim 106249259Sdim for (; N; --N, ++UI) 107249259Sdim if (UI == E) return false; // Too few. 108249259Sdim 109249259Sdim return true; 110249259Sdim} 111249259Sdim 112249259Sdim/// isUsedInBasicBlock - Return true if this value is used in the specified 113249259Sdim/// basic block. 114249259Sdimbool Value::isUsedInBasicBlock(const BasicBlock *BB) const { 115263509Sdim // This can be computed either by scanning the instructions in BB, or by 116263509Sdim // scanning the use list of this Value. Both lists can be very long, but 117263509Sdim // usually one is quite short. 118263509Sdim // 119263509Sdim // Scan both lists simultaneously until one is exhausted. This limits the 120263509Sdim // search to the shorter list. 121263509Sdim BasicBlock::const_iterator BI = BB->begin(), BE = BB->end(); 122263509Sdim const_use_iterator UI = use_begin(), UE = use_end(); 123263509Sdim for (; BI != BE && UI != UE; ++BI, ++UI) { 124263509Sdim // Scan basic block: Check if this Value is used by the instruction at BI. 125263509Sdim if (std::find(BI->op_begin(), BI->op_end(), this) != BI->op_end()) 126249259Sdim return true; 127263509Sdim // Scan use list: Check if the use at UI is in BB. 128263509Sdim const Instruction *User = dyn_cast<Instruction>(*UI); 129249259Sdim if (User && User->getParent() == BB) 130249259Sdim return true; 131249259Sdim } 132249259Sdim return false; 133249259Sdim} 134249259Sdim 135249259Sdim 136249259Sdim/// getNumUses - This method computes the number of uses of this Value. This 137249259Sdim/// is a linear time operation. Use hasOneUse or hasNUses to check for specific 138249259Sdim/// values. 139249259Sdimunsigned Value::getNumUses() const { 140249259Sdim return (unsigned)std::distance(use_begin(), use_end()); 141249259Sdim} 142249259Sdim 143249259Sdimstatic bool getSymTab(Value *V, ValueSymbolTable *&ST) { 144249259Sdim ST = 0; 145249259Sdim if (Instruction *I = dyn_cast<Instruction>(V)) { 146249259Sdim if (BasicBlock *P = I->getParent()) 147249259Sdim if (Function *PP = P->getParent()) 148249259Sdim ST = &PP->getValueSymbolTable(); 149249259Sdim } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 150249259Sdim if (Function *P = BB->getParent()) 151249259Sdim ST = &P->getValueSymbolTable(); 152249259Sdim } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 153249259Sdim if (Module *P = GV->getParent()) 154249259Sdim ST = &P->getValueSymbolTable(); 155249259Sdim } else if (Argument *A = dyn_cast<Argument>(V)) { 156249259Sdim if (Function *P = A->getParent()) 157249259Sdim ST = &P->getValueSymbolTable(); 158249259Sdim } else if (isa<MDString>(V)) 159249259Sdim return true; 160249259Sdim else { 161249259Sdim assert(isa<Constant>(V) && "Unknown value type!"); 162249259Sdim return true; // no name is setable for this. 163249259Sdim } 164249259Sdim return false; 165249259Sdim} 166249259Sdim 167249259SdimStringRef Value::getName() const { 168249259Sdim // Make sure the empty string is still a C string. For historical reasons, 169249259Sdim // some clients want to call .data() on the result and expect it to be null 170249259Sdim // terminated. 171249259Sdim if (!Name) return StringRef("", 0); 172249259Sdim return Name->getKey(); 173249259Sdim} 174249259Sdim 175249259Sdimvoid Value::setName(const Twine &NewName) { 176249259Sdim assert(SubclassID != MDStringVal && 177249259Sdim "Cannot set the name of MDString with this method!"); 178249259Sdim 179249259Sdim // Fast path for common IRBuilder case of setName("") when there is no name. 180249259Sdim if (NewName.isTriviallyEmpty() && !hasName()) 181249259Sdim return; 182249259Sdim 183249259Sdim SmallString<256> NameData; 184249259Sdim StringRef NameRef = NewName.toStringRef(NameData); 185249259Sdim 186249259Sdim // Name isn't changing? 187249259Sdim if (getName() == NameRef) 188249259Sdim return; 189249259Sdim 190249259Sdim assert(!getType()->isVoidTy() && "Cannot assign a name to void values!"); 191249259Sdim 192249259Sdim // Get the symbol table to update for this object. 193249259Sdim ValueSymbolTable *ST; 194249259Sdim if (getSymTab(this, ST)) 195249259Sdim return; // Cannot set a name on this value (e.g. constant). 196249259Sdim 197249259Sdim if (Function *F = dyn_cast<Function>(this)) 198249259Sdim getContext().pImpl->IntrinsicIDCache.erase(F); 199249259Sdim 200249259Sdim if (!ST) { // No symbol table to update? Just do the change. 201249259Sdim if (NameRef.empty()) { 202249259Sdim // Free the name for this value. 203249259Sdim Name->Destroy(); 204249259Sdim Name = 0; 205249259Sdim return; 206249259Sdim } 207249259Sdim 208249259Sdim if (Name) 209249259Sdim Name->Destroy(); 210249259Sdim 211249259Sdim // NOTE: Could optimize for the case the name is shrinking to not deallocate 212249259Sdim // then reallocated. 213249259Sdim 214249259Sdim // Create the new name. 215249259Sdim Name = ValueName::Create(NameRef.begin(), NameRef.end()); 216249259Sdim Name->setValue(this); 217249259Sdim return; 218249259Sdim } 219249259Sdim 220249259Sdim // NOTE: Could optimize for the case the name is shrinking to not deallocate 221249259Sdim // then reallocated. 222249259Sdim if (hasName()) { 223249259Sdim // Remove old name. 224249259Sdim ST->removeValueName(Name); 225249259Sdim Name->Destroy(); 226249259Sdim Name = 0; 227249259Sdim 228249259Sdim if (NameRef.empty()) 229249259Sdim return; 230249259Sdim } 231249259Sdim 232249259Sdim // Name is changing to something new. 233249259Sdim Name = ST->createValueName(NameRef, this); 234249259Sdim} 235249259Sdim 236249259Sdim 237249259Sdim/// takeName - transfer the name from V to this value, setting V's name to 238249259Sdim/// empty. It is an error to call V->takeName(V). 239249259Sdimvoid Value::takeName(Value *V) { 240249259Sdim assert(SubclassID != MDStringVal && "Cannot take the name of an MDString!"); 241249259Sdim 242249259Sdim ValueSymbolTable *ST = 0; 243249259Sdim // If this value has a name, drop it. 244249259Sdim if (hasName()) { 245249259Sdim // Get the symtab this is in. 246249259Sdim if (getSymTab(this, ST)) { 247249259Sdim // We can't set a name on this value, but we need to clear V's name if 248249259Sdim // it has one. 249249259Sdim if (V->hasName()) V->setName(""); 250249259Sdim return; // Cannot set a name on this value (e.g. constant). 251249259Sdim } 252249259Sdim 253249259Sdim // Remove old name. 254249259Sdim if (ST) 255249259Sdim ST->removeValueName(Name); 256249259Sdim Name->Destroy(); 257249259Sdim Name = 0; 258249259Sdim } 259249259Sdim 260249259Sdim // Now we know that this has no name. 261249259Sdim 262249259Sdim // If V has no name either, we're done. 263249259Sdim if (!V->hasName()) return; 264249259Sdim 265249259Sdim // Get this's symtab if we didn't before. 266249259Sdim if (!ST) { 267249259Sdim if (getSymTab(this, ST)) { 268249259Sdim // Clear V's name. 269249259Sdim V->setName(""); 270249259Sdim return; // Cannot set a name on this value (e.g. constant). 271249259Sdim } 272249259Sdim } 273249259Sdim 274249259Sdim // Get V's ST, this should always succed, because V has a name. 275249259Sdim ValueSymbolTable *VST; 276249259Sdim bool Failure = getSymTab(V, VST); 277249259Sdim assert(!Failure && "V has a name, so it should have a ST!"); (void)Failure; 278249259Sdim 279249259Sdim // If these values are both in the same symtab, we can do this very fast. 280249259Sdim // This works even if both values have no symtab yet. 281249259Sdim if (ST == VST) { 282249259Sdim // Take the name! 283249259Sdim Name = V->Name; 284249259Sdim V->Name = 0; 285249259Sdim Name->setValue(this); 286249259Sdim return; 287249259Sdim } 288249259Sdim 289249259Sdim // Otherwise, things are slightly more complex. Remove V's name from VST and 290249259Sdim // then reinsert it into ST. 291249259Sdim 292249259Sdim if (VST) 293249259Sdim VST->removeValueName(V->Name); 294249259Sdim Name = V->Name; 295249259Sdim V->Name = 0; 296249259Sdim Name->setValue(this); 297249259Sdim 298249259Sdim if (ST) 299249259Sdim ST->reinsertValue(this); 300249259Sdim} 301249259Sdim 302249259Sdim 303249259Sdimvoid Value::replaceAllUsesWith(Value *New) { 304249259Sdim assert(New && "Value::replaceAllUsesWith(<null>) is invalid!"); 305249259Sdim assert(New != this && "this->replaceAllUsesWith(this) is NOT valid!"); 306249259Sdim assert(New->getType() == getType() && 307249259Sdim "replaceAllUses of value with new value of different type!"); 308249259Sdim 309249259Sdim // Notify all ValueHandles (if present) that this value is going away. 310249259Sdim if (HasValueHandle) 311249259Sdim ValueHandleBase::ValueIsRAUWd(this, New); 312249259Sdim 313249259Sdim while (!use_empty()) { 314249259Sdim Use &U = *UseList; 315249259Sdim // Must handle Constants specially, we cannot call replaceUsesOfWith on a 316249259Sdim // constant because they are uniqued. 317249259Sdim if (Constant *C = dyn_cast<Constant>(U.getUser())) { 318249259Sdim if (!isa<GlobalValue>(C)) { 319249259Sdim C->replaceUsesOfWithOnConstant(this, New, &U); 320249259Sdim continue; 321249259Sdim } 322249259Sdim } 323249259Sdim 324249259Sdim U.set(New); 325249259Sdim } 326249259Sdim 327249259Sdim if (BasicBlock *BB = dyn_cast<BasicBlock>(this)) 328249259Sdim BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New)); 329249259Sdim} 330249259Sdim 331249259Sdimnamespace { 332249259Sdim// Various metrics for how much to strip off of pointers. 333249259Sdimenum PointerStripKind { 334249259Sdim PSK_ZeroIndices, 335252723Sdim PSK_ZeroIndicesAndAliases, 336249259Sdim PSK_InBoundsConstantIndices, 337249259Sdim PSK_InBounds 338249259Sdim}; 339249259Sdim 340249259Sdimtemplate <PointerStripKind StripKind> 341249259Sdimstatic Value *stripPointerCastsAndOffsets(Value *V) { 342249259Sdim if (!V->getType()->isPointerTy()) 343249259Sdim return V; 344249259Sdim 345249259Sdim // Even though we don't look through PHI nodes, we could be called on an 346249259Sdim // instruction in an unreachable block, which may be on a cycle. 347249259Sdim SmallPtrSet<Value *, 4> Visited; 348249259Sdim 349249259Sdim Visited.insert(V); 350249259Sdim do { 351249259Sdim if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 352249259Sdim switch (StripKind) { 353252723Sdim case PSK_ZeroIndicesAndAliases: 354249259Sdim case PSK_ZeroIndices: 355249259Sdim if (!GEP->hasAllZeroIndices()) 356249259Sdim return V; 357249259Sdim break; 358249259Sdim case PSK_InBoundsConstantIndices: 359249259Sdim if (!GEP->hasAllConstantIndices()) 360249259Sdim return V; 361249259Sdim // fallthrough 362249259Sdim case PSK_InBounds: 363249259Sdim if (!GEP->isInBounds()) 364249259Sdim return V; 365249259Sdim break; 366249259Sdim } 367249259Sdim V = GEP->getPointerOperand(); 368263509Sdim } else if (Operator::getOpcode(V) == Instruction::BitCast || 369263509Sdim Operator::getOpcode(V) == Instruction::AddrSpaceCast) { 370249259Sdim V = cast<Operator>(V)->getOperand(0); 371249259Sdim } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 372252723Sdim if (StripKind == PSK_ZeroIndices || GA->mayBeOverridden()) 373249259Sdim return V; 374249259Sdim V = GA->getAliasee(); 375249259Sdim } else { 376249259Sdim return V; 377249259Sdim } 378249259Sdim assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 379249259Sdim } while (Visited.insert(V)); 380249259Sdim 381249259Sdim return V; 382249259Sdim} 383249259Sdim} // namespace 384249259Sdim 385249259SdimValue *Value::stripPointerCasts() { 386252723Sdim return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this); 387252723Sdim} 388252723Sdim 389252723SdimValue *Value::stripPointerCastsNoFollowAliases() { 390249259Sdim return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this); 391249259Sdim} 392249259Sdim 393249259SdimValue *Value::stripInBoundsConstantOffsets() { 394249259Sdim return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this); 395249259Sdim} 396249259Sdim 397263509SdimValue *Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, 398263509Sdim APInt &Offset) { 399263509Sdim if (!getType()->isPointerTy()) 400263509Sdim return this; 401263509Sdim 402263509Sdim assert(Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType>( 403263509Sdim getType())->getAddressSpace()) && 404263509Sdim "The offset must have exactly as many bits as our pointer."); 405263509Sdim 406263509Sdim // Even though we don't look through PHI nodes, we could be called on an 407263509Sdim // instruction in an unreachable block, which may be on a cycle. 408263509Sdim SmallPtrSet<Value *, 4> Visited; 409263509Sdim Visited.insert(this); 410263509Sdim Value *V = this; 411263509Sdim do { 412263509Sdim if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 413263509Sdim if (!GEP->isInBounds()) 414263509Sdim return V; 415263509Sdim APInt GEPOffset(Offset); 416263509Sdim if (!GEP->accumulateConstantOffset(DL, GEPOffset)) 417263509Sdim return V; 418263509Sdim Offset = GEPOffset; 419263509Sdim V = GEP->getPointerOperand(); 420263509Sdim } else if (Operator::getOpcode(V) == Instruction::BitCast) { 421263509Sdim V = cast<Operator>(V)->getOperand(0); 422263509Sdim } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 423263509Sdim V = GA->getAliasee(); 424263509Sdim } else { 425263509Sdim return V; 426263509Sdim } 427263509Sdim assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 428263509Sdim } while (Visited.insert(V)); 429263509Sdim 430263509Sdim return V; 431263509Sdim} 432263509Sdim 433249259SdimValue *Value::stripInBoundsOffsets() { 434249259Sdim return stripPointerCastsAndOffsets<PSK_InBounds>(this); 435249259Sdim} 436249259Sdim 437249259Sdim/// isDereferenceablePointer - Test if this value is always a pointer to 438249259Sdim/// allocated and suitably aligned memory for a simple load or store. 439249259Sdimstatic bool isDereferenceablePointer(const Value *V, 440249259Sdim SmallPtrSet<const Value *, 32> &Visited) { 441249259Sdim // Note that it is not safe to speculate into a malloc'd region because 442249259Sdim // malloc may return null. 443249259Sdim // It's also not always safe to follow a bitcast, for example: 444249259Sdim // bitcast i8* (alloca i8) to i32* 445249259Sdim // would result in a 4-byte load from a 1-byte alloca. Some cases could 446249259Sdim // be handled using DataLayout to check sizes and alignments though. 447249259Sdim 448249259Sdim // These are obviously ok. 449249259Sdim if (isa<AllocaInst>(V)) return true; 450249259Sdim 451249259Sdim // Global variables which can't collapse to null are ok. 452249259Sdim if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 453249259Sdim return !GV->hasExternalWeakLinkage(); 454249259Sdim 455249259Sdim // byval arguments are ok. 456249259Sdim if (const Argument *A = dyn_cast<Argument>(V)) 457249259Sdim return A->hasByValAttr(); 458249259Sdim 459249259Sdim // For GEPs, determine if the indexing lands within the allocated object. 460249259Sdim if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 461249259Sdim // Conservatively require that the base pointer be fully dereferenceable. 462249259Sdim if (!Visited.insert(GEP->getOperand(0))) 463249259Sdim return false; 464249259Sdim if (!isDereferenceablePointer(GEP->getOperand(0), Visited)) 465249259Sdim return false; 466249259Sdim // Check the indices. 467249259Sdim gep_type_iterator GTI = gep_type_begin(GEP); 468249259Sdim for (User::const_op_iterator I = GEP->op_begin()+1, 469249259Sdim E = GEP->op_end(); I != E; ++I) { 470249259Sdim Value *Index = *I; 471249259Sdim Type *Ty = *GTI++; 472249259Sdim // Struct indices can't be out of bounds. 473249259Sdim if (isa<StructType>(Ty)) 474249259Sdim continue; 475249259Sdim ConstantInt *CI = dyn_cast<ConstantInt>(Index); 476249259Sdim if (!CI) 477249259Sdim return false; 478249259Sdim // Zero is always ok. 479249259Sdim if (CI->isZero()) 480249259Sdim continue; 481249259Sdim // Check to see that it's within the bounds of an array. 482249259Sdim ArrayType *ATy = dyn_cast<ArrayType>(Ty); 483249259Sdim if (!ATy) 484249259Sdim return false; 485249259Sdim if (CI->getValue().getActiveBits() > 64) 486249259Sdim return false; 487249259Sdim if (CI->getZExtValue() >= ATy->getNumElements()) 488249259Sdim return false; 489249259Sdim } 490249259Sdim // Indices check out; this is dereferenceable. 491249259Sdim return true; 492249259Sdim } 493249259Sdim 494249259Sdim // If we don't know, assume the worst. 495249259Sdim return false; 496249259Sdim} 497249259Sdim 498249259Sdim/// isDereferenceablePointer - Test if this value is always a pointer to 499249259Sdim/// allocated and suitably aligned memory for a simple load or store. 500249259Sdimbool Value::isDereferenceablePointer() const { 501249259Sdim SmallPtrSet<const Value *, 32> Visited; 502249259Sdim return ::isDereferenceablePointer(this, Visited); 503249259Sdim} 504249259Sdim 505249259Sdim/// DoPHITranslation - If this value is a PHI node with CurBB as its parent, 506249259Sdim/// return the value in the PHI node corresponding to PredBB. If not, return 507249259Sdim/// ourself. This is useful if you want to know the value something has in a 508249259Sdim/// predecessor block. 509249259SdimValue *Value::DoPHITranslation(const BasicBlock *CurBB, 510249259Sdim const BasicBlock *PredBB) { 511249259Sdim PHINode *PN = dyn_cast<PHINode>(this); 512249259Sdim if (PN && PN->getParent() == CurBB) 513249259Sdim return PN->getIncomingValueForBlock(PredBB); 514249259Sdim return this; 515249259Sdim} 516249259Sdim 517249259SdimLLVMContext &Value::getContext() const { return VTy->getContext(); } 518249259Sdim 519249259Sdim//===----------------------------------------------------------------------===// 520249259Sdim// ValueHandleBase Class 521249259Sdim//===----------------------------------------------------------------------===// 522249259Sdim 523249259Sdim/// AddToExistingUseList - Add this ValueHandle to the use list for VP, where 524249259Sdim/// List is known to point into the existing use list. 525249259Sdimvoid ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) { 526249259Sdim assert(List && "Handle list is null?"); 527249259Sdim 528249259Sdim // Splice ourselves into the list. 529249259Sdim Next = *List; 530249259Sdim *List = this; 531249259Sdim setPrevPtr(List); 532249259Sdim if (Next) { 533249259Sdim Next->setPrevPtr(&Next); 534249259Sdim assert(VP.getPointer() == Next->VP.getPointer() && "Added to wrong list?"); 535249259Sdim } 536249259Sdim} 537249259Sdim 538249259Sdimvoid ValueHandleBase::AddToExistingUseListAfter(ValueHandleBase *List) { 539249259Sdim assert(List && "Must insert after existing node"); 540249259Sdim 541249259Sdim Next = List->Next; 542249259Sdim setPrevPtr(&List->Next); 543249259Sdim List->Next = this; 544249259Sdim if (Next) 545249259Sdim Next->setPrevPtr(&Next); 546249259Sdim} 547249259Sdim 548249259Sdim/// AddToUseList - Add this ValueHandle to the use list for VP. 549249259Sdimvoid ValueHandleBase::AddToUseList() { 550249259Sdim assert(VP.getPointer() && "Null pointer doesn't have a use list!"); 551249259Sdim 552249259Sdim LLVMContextImpl *pImpl = VP.getPointer()->getContext().pImpl; 553249259Sdim 554249259Sdim if (VP.getPointer()->HasValueHandle) { 555249259Sdim // If this value already has a ValueHandle, then it must be in the 556249259Sdim // ValueHandles map already. 557249259Sdim ValueHandleBase *&Entry = pImpl->ValueHandles[VP.getPointer()]; 558249259Sdim assert(Entry != 0 && "Value doesn't have any handles?"); 559249259Sdim AddToExistingUseList(&Entry); 560249259Sdim return; 561249259Sdim } 562249259Sdim 563249259Sdim // Ok, it doesn't have any handles yet, so we must insert it into the 564249259Sdim // DenseMap. However, doing this insertion could cause the DenseMap to 565249259Sdim // reallocate itself, which would invalidate all of the PrevP pointers that 566249259Sdim // point into the old table. Handle this by checking for reallocation and 567249259Sdim // updating the stale pointers only if needed. 568249259Sdim DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles; 569249259Sdim const void *OldBucketPtr = Handles.getPointerIntoBucketsArray(); 570249259Sdim 571249259Sdim ValueHandleBase *&Entry = Handles[VP.getPointer()]; 572249259Sdim assert(Entry == 0 && "Value really did already have handles?"); 573249259Sdim AddToExistingUseList(&Entry); 574249259Sdim VP.getPointer()->HasValueHandle = true; 575249259Sdim 576249259Sdim // If reallocation didn't happen or if this was the first insertion, don't 577249259Sdim // walk the table. 578249259Sdim if (Handles.isPointerIntoBucketsArray(OldBucketPtr) || 579249259Sdim Handles.size() == 1) { 580249259Sdim return; 581249259Sdim } 582249259Sdim 583249259Sdim // Okay, reallocation did happen. Fix the Prev Pointers. 584249259Sdim for (DenseMap<Value*, ValueHandleBase*>::iterator I = Handles.begin(), 585249259Sdim E = Handles.end(); I != E; ++I) { 586249259Sdim assert(I->second && I->first == I->second->VP.getPointer() && 587249259Sdim "List invariant broken!"); 588249259Sdim I->second->setPrevPtr(&I->second); 589249259Sdim } 590249259Sdim} 591249259Sdim 592249259Sdim/// RemoveFromUseList - Remove this ValueHandle from its current use list. 593249259Sdimvoid ValueHandleBase::RemoveFromUseList() { 594249259Sdim assert(VP.getPointer() && VP.getPointer()->HasValueHandle && 595249259Sdim "Pointer doesn't have a use list!"); 596249259Sdim 597249259Sdim // Unlink this from its use list. 598249259Sdim ValueHandleBase **PrevPtr = getPrevPtr(); 599249259Sdim assert(*PrevPtr == this && "List invariant broken"); 600249259Sdim 601249259Sdim *PrevPtr = Next; 602249259Sdim if (Next) { 603249259Sdim assert(Next->getPrevPtr() == &Next && "List invariant broken"); 604249259Sdim Next->setPrevPtr(PrevPtr); 605249259Sdim return; 606249259Sdim } 607249259Sdim 608249259Sdim // If the Next pointer was null, then it is possible that this was the last 609249259Sdim // ValueHandle watching VP. If so, delete its entry from the ValueHandles 610249259Sdim // map. 611249259Sdim LLVMContextImpl *pImpl = VP.getPointer()->getContext().pImpl; 612249259Sdim DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles; 613249259Sdim if (Handles.isPointerIntoBucketsArray(PrevPtr)) { 614249259Sdim Handles.erase(VP.getPointer()); 615249259Sdim VP.getPointer()->HasValueHandle = false; 616249259Sdim } 617249259Sdim} 618249259Sdim 619249259Sdim 620249259Sdimvoid ValueHandleBase::ValueIsDeleted(Value *V) { 621249259Sdim assert(V->HasValueHandle && "Should only be called if ValueHandles present"); 622249259Sdim 623249259Sdim // Get the linked list base, which is guaranteed to exist since the 624249259Sdim // HasValueHandle flag is set. 625249259Sdim LLVMContextImpl *pImpl = V->getContext().pImpl; 626249259Sdim ValueHandleBase *Entry = pImpl->ValueHandles[V]; 627249259Sdim assert(Entry && "Value bit set but no entries exist"); 628249259Sdim 629249259Sdim // We use a local ValueHandleBase as an iterator so that ValueHandles can add 630249259Sdim // and remove themselves from the list without breaking our iteration. This 631249259Sdim // is not really an AssertingVH; we just have to give ValueHandleBase a kind. 632249259Sdim // Note that we deliberately do not the support the case when dropping a value 633249259Sdim // handle results in a new value handle being permanently added to the list 634249259Sdim // (as might occur in theory for CallbackVH's): the new value handle will not 635249259Sdim // be processed and the checking code will mete out righteous punishment if 636249259Sdim // the handle is still present once we have finished processing all the other 637249259Sdim // value handles (it is fine to momentarily add then remove a value handle). 638249259Sdim for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) { 639249259Sdim Iterator.RemoveFromUseList(); 640249259Sdim Iterator.AddToExistingUseListAfter(Entry); 641249259Sdim assert(Entry->Next == &Iterator && "Loop invariant broken."); 642249259Sdim 643249259Sdim switch (Entry->getKind()) { 644249259Sdim case Assert: 645249259Sdim break; 646249259Sdim case Tracking: 647249259Sdim // Mark that this value has been deleted by setting it to an invalid Value 648249259Sdim // pointer. 649249259Sdim Entry->operator=(DenseMapInfo<Value *>::getTombstoneKey()); 650249259Sdim break; 651249259Sdim case Weak: 652249259Sdim // Weak just goes to null, which will unlink it from the list. 653249259Sdim Entry->operator=(0); 654249259Sdim break; 655249259Sdim case Callback: 656249259Sdim // Forward to the subclass's implementation. 657249259Sdim static_cast<CallbackVH*>(Entry)->deleted(); 658249259Sdim break; 659249259Sdim } 660249259Sdim } 661249259Sdim 662249259Sdim // All callbacks, weak references, and assertingVHs should be dropped by now. 663249259Sdim if (V->HasValueHandle) { 664249259Sdim#ifndef NDEBUG // Only in +Asserts mode... 665249259Sdim dbgs() << "While deleting: " << *V->getType() << " %" << V->getName() 666249259Sdim << "\n"; 667249259Sdim if (pImpl->ValueHandles[V]->getKind() == Assert) 668249259Sdim llvm_unreachable("An asserting value handle still pointed to this" 669249259Sdim " value!"); 670249259Sdim 671249259Sdim#endif 672249259Sdim llvm_unreachable("All references to V were not removed?"); 673249259Sdim } 674249259Sdim} 675249259Sdim 676249259Sdim 677249259Sdimvoid ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) { 678249259Sdim assert(Old->HasValueHandle &&"Should only be called if ValueHandles present"); 679249259Sdim assert(Old != New && "Changing value into itself!"); 680249259Sdim 681249259Sdim // Get the linked list base, which is guaranteed to exist since the 682249259Sdim // HasValueHandle flag is set. 683249259Sdim LLVMContextImpl *pImpl = Old->getContext().pImpl; 684249259Sdim ValueHandleBase *Entry = pImpl->ValueHandles[Old]; 685249259Sdim 686249259Sdim assert(Entry && "Value bit set but no entries exist"); 687249259Sdim 688249259Sdim // We use a local ValueHandleBase as an iterator so that 689249259Sdim // ValueHandles can add and remove themselves from the list without 690249259Sdim // breaking our iteration. This is not really an AssertingVH; we 691249259Sdim // just have to give ValueHandleBase some kind. 692249259Sdim for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) { 693249259Sdim Iterator.RemoveFromUseList(); 694249259Sdim Iterator.AddToExistingUseListAfter(Entry); 695249259Sdim assert(Entry->Next == &Iterator && "Loop invariant broken."); 696249259Sdim 697249259Sdim switch (Entry->getKind()) { 698249259Sdim case Assert: 699249259Sdim // Asserting handle does not follow RAUW implicitly. 700249259Sdim break; 701249259Sdim case Tracking: 702249259Sdim // Tracking goes to new value like a WeakVH. Note that this may make it 703249259Sdim // something incompatible with its templated type. We don't want to have a 704249259Sdim // virtual (or inline) interface to handle this though, so instead we make 705249259Sdim // the TrackingVH accessors guarantee that a client never sees this value. 706249259Sdim 707249259Sdim // FALLTHROUGH 708249259Sdim case Weak: 709249259Sdim // Weak goes to the new value, which will unlink it from Old's list. 710249259Sdim Entry->operator=(New); 711249259Sdim break; 712249259Sdim case Callback: 713249259Sdim // Forward to the subclass's implementation. 714249259Sdim static_cast<CallbackVH*>(Entry)->allUsesReplacedWith(New); 715249259Sdim break; 716249259Sdim } 717249259Sdim } 718249259Sdim 719249259Sdim#ifndef NDEBUG 720249259Sdim // If any new tracking or weak value handles were added while processing the 721249259Sdim // list, then complain about it now. 722249259Sdim if (Old->HasValueHandle) 723249259Sdim for (Entry = pImpl->ValueHandles[Old]; Entry; Entry = Entry->Next) 724249259Sdim switch (Entry->getKind()) { 725249259Sdim case Tracking: 726249259Sdim case Weak: 727249259Sdim dbgs() << "After RAUW from " << *Old->getType() << " %" 728249259Sdim << Old->getName() << " to " << *New->getType() << " %" 729249259Sdim << New->getName() << "\n"; 730249259Sdim llvm_unreachable("A tracking or weak value handle still pointed to the" 731249259Sdim " old value!\n"); 732249259Sdim default: 733249259Sdim break; 734249259Sdim } 735249259Sdim#endif 736249259Sdim} 737249259Sdim 738263509Sdim// Pin the vtable to this file. 739263509Sdimvoid CallbackVH::anchor() {} 740