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 { 115249259Sdim // Start by scanning over the instructions looking for a use before we start 116249259Sdim // the expensive use iteration. 117249259Sdim unsigned MaxBlockSize = 3; 118249259Sdim for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 119249259Sdim if (std::find(I->op_begin(), I->op_end(), this) != I->op_end()) 120249259Sdim return true; 121251662Sdim if (--MaxBlockSize == 0) // If the block is larger fall back to use_iterator 122249259Sdim break; 123249259Sdim } 124249259Sdim 125249259Sdim if (MaxBlockSize != 0) // We scanned the entire block and found no use. 126249259Sdim return false; 127249259Sdim 128249259Sdim for (const_use_iterator I = use_begin(), E = use_end(); I != E; ++I) { 129249259Sdim const Instruction *User = dyn_cast<Instruction>(*I); 130249259Sdim if (User && User->getParent() == BB) 131249259Sdim return true; 132249259Sdim } 133249259Sdim return false; 134249259Sdim} 135249259Sdim 136249259Sdim 137249259Sdim/// getNumUses - This method computes the number of uses of this Value. This 138249259Sdim/// is a linear time operation. Use hasOneUse or hasNUses to check for specific 139249259Sdim/// values. 140249259Sdimunsigned Value::getNumUses() const { 141249259Sdim return (unsigned)std::distance(use_begin(), use_end()); 142249259Sdim} 143249259Sdim 144249259Sdimstatic bool getSymTab(Value *V, ValueSymbolTable *&ST) { 145249259Sdim ST = 0; 146249259Sdim if (Instruction *I = dyn_cast<Instruction>(V)) { 147249259Sdim if (BasicBlock *P = I->getParent()) 148249259Sdim if (Function *PP = P->getParent()) 149249259Sdim ST = &PP->getValueSymbolTable(); 150249259Sdim } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 151249259Sdim if (Function *P = BB->getParent()) 152249259Sdim ST = &P->getValueSymbolTable(); 153249259Sdim } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 154249259Sdim if (Module *P = GV->getParent()) 155249259Sdim ST = &P->getValueSymbolTable(); 156249259Sdim } else if (Argument *A = dyn_cast<Argument>(V)) { 157249259Sdim if (Function *P = A->getParent()) 158249259Sdim ST = &P->getValueSymbolTable(); 159249259Sdim } else if (isa<MDString>(V)) 160249259Sdim return true; 161249259Sdim else { 162249259Sdim assert(isa<Constant>(V) && "Unknown value type!"); 163249259Sdim return true; // no name is setable for this. 164249259Sdim } 165249259Sdim return false; 166249259Sdim} 167249259Sdim 168249259SdimStringRef Value::getName() const { 169249259Sdim // Make sure the empty string is still a C string. For historical reasons, 170249259Sdim // some clients want to call .data() on the result and expect it to be null 171249259Sdim // terminated. 172249259Sdim if (!Name) return StringRef("", 0); 173249259Sdim return Name->getKey(); 174249259Sdim} 175249259Sdim 176249259Sdimvoid Value::setName(const Twine &NewName) { 177249259Sdim assert(SubclassID != MDStringVal && 178249259Sdim "Cannot set the name of MDString with this method!"); 179249259Sdim 180249259Sdim // Fast path for common IRBuilder case of setName("") when there is no name. 181249259Sdim if (NewName.isTriviallyEmpty() && !hasName()) 182249259Sdim return; 183249259Sdim 184249259Sdim SmallString<256> NameData; 185249259Sdim StringRef NameRef = NewName.toStringRef(NameData); 186249259Sdim 187249259Sdim // Name isn't changing? 188249259Sdim if (getName() == NameRef) 189249259Sdim return; 190249259Sdim 191249259Sdim assert(!getType()->isVoidTy() && "Cannot assign a name to void values!"); 192249259Sdim 193249259Sdim // Get the symbol table to update for this object. 194249259Sdim ValueSymbolTable *ST; 195249259Sdim if (getSymTab(this, ST)) 196249259Sdim return; // Cannot set a name on this value (e.g. constant). 197249259Sdim 198249259Sdim if (Function *F = dyn_cast<Function>(this)) 199249259Sdim getContext().pImpl->IntrinsicIDCache.erase(F); 200249259Sdim 201249259Sdim if (!ST) { // No symbol table to update? Just do the change. 202249259Sdim if (NameRef.empty()) { 203249259Sdim // Free the name for this value. 204249259Sdim Name->Destroy(); 205249259Sdim Name = 0; 206249259Sdim return; 207249259Sdim } 208249259Sdim 209249259Sdim if (Name) 210249259Sdim Name->Destroy(); 211249259Sdim 212249259Sdim // NOTE: Could optimize for the case the name is shrinking to not deallocate 213249259Sdim // then reallocated. 214249259Sdim 215249259Sdim // Create the new name. 216249259Sdim Name = ValueName::Create(NameRef.begin(), NameRef.end()); 217249259Sdim Name->setValue(this); 218249259Sdim return; 219249259Sdim } 220249259Sdim 221249259Sdim // NOTE: Could optimize for the case the name is shrinking to not deallocate 222249259Sdim // then reallocated. 223249259Sdim if (hasName()) { 224249259Sdim // Remove old name. 225249259Sdim ST->removeValueName(Name); 226249259Sdim Name->Destroy(); 227249259Sdim Name = 0; 228249259Sdim 229249259Sdim if (NameRef.empty()) 230249259Sdim return; 231249259Sdim } 232249259Sdim 233249259Sdim // Name is changing to something new. 234249259Sdim Name = ST->createValueName(NameRef, this); 235249259Sdim} 236249259Sdim 237249259Sdim 238249259Sdim/// takeName - transfer the name from V to this value, setting V's name to 239249259Sdim/// empty. It is an error to call V->takeName(V). 240249259Sdimvoid Value::takeName(Value *V) { 241249259Sdim assert(SubclassID != MDStringVal && "Cannot take the name of an MDString!"); 242249259Sdim 243249259Sdim ValueSymbolTable *ST = 0; 244249259Sdim // If this value has a name, drop it. 245249259Sdim if (hasName()) { 246249259Sdim // Get the symtab this is in. 247249259Sdim if (getSymTab(this, ST)) { 248249259Sdim // We can't set a name on this value, but we need to clear V's name if 249249259Sdim // it has one. 250249259Sdim if (V->hasName()) V->setName(""); 251249259Sdim return; // Cannot set a name on this value (e.g. constant). 252249259Sdim } 253249259Sdim 254249259Sdim // Remove old name. 255249259Sdim if (ST) 256249259Sdim ST->removeValueName(Name); 257249259Sdim Name->Destroy(); 258249259Sdim Name = 0; 259249259Sdim } 260249259Sdim 261249259Sdim // Now we know that this has no name. 262249259Sdim 263249259Sdim // If V has no name either, we're done. 264249259Sdim if (!V->hasName()) return; 265249259Sdim 266249259Sdim // Get this's symtab if we didn't before. 267249259Sdim if (!ST) { 268249259Sdim if (getSymTab(this, ST)) { 269249259Sdim // Clear V's name. 270249259Sdim V->setName(""); 271249259Sdim return; // Cannot set a name on this value (e.g. constant). 272249259Sdim } 273249259Sdim } 274249259Sdim 275249259Sdim // Get V's ST, this should always succed, because V has a name. 276249259Sdim ValueSymbolTable *VST; 277249259Sdim bool Failure = getSymTab(V, VST); 278249259Sdim assert(!Failure && "V has a name, so it should have a ST!"); (void)Failure; 279249259Sdim 280249259Sdim // If these values are both in the same symtab, we can do this very fast. 281249259Sdim // This works even if both values have no symtab yet. 282249259Sdim if (ST == VST) { 283249259Sdim // Take the name! 284249259Sdim Name = V->Name; 285249259Sdim V->Name = 0; 286249259Sdim Name->setValue(this); 287249259Sdim return; 288249259Sdim } 289249259Sdim 290249259Sdim // Otherwise, things are slightly more complex. Remove V's name from VST and 291249259Sdim // then reinsert it into ST. 292249259Sdim 293249259Sdim if (VST) 294249259Sdim VST->removeValueName(V->Name); 295249259Sdim Name = V->Name; 296249259Sdim V->Name = 0; 297249259Sdim Name->setValue(this); 298249259Sdim 299249259Sdim if (ST) 300249259Sdim ST->reinsertValue(this); 301249259Sdim} 302249259Sdim 303249259Sdim 304249259Sdimvoid Value::replaceAllUsesWith(Value *New) { 305249259Sdim assert(New && "Value::replaceAllUsesWith(<null>) is invalid!"); 306249259Sdim assert(New != this && "this->replaceAllUsesWith(this) is NOT valid!"); 307249259Sdim assert(New->getType() == getType() && 308249259Sdim "replaceAllUses of value with new value of different type!"); 309249259Sdim 310249259Sdim // Notify all ValueHandles (if present) that this value is going away. 311249259Sdim if (HasValueHandle) 312249259Sdim ValueHandleBase::ValueIsRAUWd(this, New); 313249259Sdim 314249259Sdim while (!use_empty()) { 315249259Sdim Use &U = *UseList; 316249259Sdim // Must handle Constants specially, we cannot call replaceUsesOfWith on a 317249259Sdim // constant because they are uniqued. 318249259Sdim if (Constant *C = dyn_cast<Constant>(U.getUser())) { 319249259Sdim if (!isa<GlobalValue>(C)) { 320249259Sdim C->replaceUsesOfWithOnConstant(this, New, &U); 321249259Sdim continue; 322249259Sdim } 323249259Sdim } 324249259Sdim 325249259Sdim U.set(New); 326249259Sdim } 327249259Sdim 328249259Sdim if (BasicBlock *BB = dyn_cast<BasicBlock>(this)) 329249259Sdim BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New)); 330249259Sdim} 331249259Sdim 332249259Sdimnamespace { 333249259Sdim// Various metrics for how much to strip off of pointers. 334249259Sdimenum PointerStripKind { 335249259Sdim PSK_ZeroIndices, 336251662Sdim PSK_ZeroIndicesAndAliases, 337249259Sdim PSK_InBoundsConstantIndices, 338249259Sdim PSK_InBounds 339249259Sdim}; 340249259Sdim 341249259Sdimtemplate <PointerStripKind StripKind> 342249259Sdimstatic Value *stripPointerCastsAndOffsets(Value *V) { 343249259Sdim if (!V->getType()->isPointerTy()) 344249259Sdim return V; 345249259Sdim 346249259Sdim // Even though we don't look through PHI nodes, we could be called on an 347249259Sdim // instruction in an unreachable block, which may be on a cycle. 348249259Sdim SmallPtrSet<Value *, 4> Visited; 349249259Sdim 350249259Sdim Visited.insert(V); 351249259Sdim do { 352249259Sdim if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 353249259Sdim switch (StripKind) { 354251662Sdim case PSK_ZeroIndicesAndAliases: 355249259Sdim case PSK_ZeroIndices: 356249259Sdim if (!GEP->hasAllZeroIndices()) 357249259Sdim return V; 358249259Sdim break; 359249259Sdim case PSK_InBoundsConstantIndices: 360249259Sdim if (!GEP->hasAllConstantIndices()) 361249259Sdim return V; 362249259Sdim // fallthrough 363249259Sdim case PSK_InBounds: 364249259Sdim if (!GEP->isInBounds()) 365249259Sdim return V; 366249259Sdim break; 367249259Sdim } 368249259Sdim V = GEP->getPointerOperand(); 369249259Sdim } else if (Operator::getOpcode(V) == Instruction::BitCast) { 370249259Sdim V = cast<Operator>(V)->getOperand(0); 371249259Sdim } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 372251662Sdim 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() { 386251662Sdim return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this); 387251662Sdim} 388251662Sdim 389251662SdimValue *Value::stripPointerCastsNoFollowAliases() { 390249259Sdim return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this); 391249259Sdim} 392249259Sdim 393249259SdimValue *Value::stripInBoundsConstantOffsets() { 394249259Sdim return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this); 395249259Sdim} 396249259Sdim 397249259SdimValue *Value::stripInBoundsOffsets() { 398249259Sdim return stripPointerCastsAndOffsets<PSK_InBounds>(this); 399249259Sdim} 400249259Sdim 401249259Sdim/// isDereferenceablePointer - Test if this value is always a pointer to 402249259Sdim/// allocated and suitably aligned memory for a simple load or store. 403249259Sdimstatic bool isDereferenceablePointer(const Value *V, 404249259Sdim SmallPtrSet<const Value *, 32> &Visited) { 405249259Sdim // Note that it is not safe to speculate into a malloc'd region because 406249259Sdim // malloc may return null. 407249259Sdim // It's also not always safe to follow a bitcast, for example: 408249259Sdim // bitcast i8* (alloca i8) to i32* 409249259Sdim // would result in a 4-byte load from a 1-byte alloca. Some cases could 410249259Sdim // be handled using DataLayout to check sizes and alignments though. 411249259Sdim 412249259Sdim // These are obviously ok. 413249259Sdim if (isa<AllocaInst>(V)) return true; 414249259Sdim 415249259Sdim // Global variables which can't collapse to null are ok. 416249259Sdim if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 417249259Sdim return !GV->hasExternalWeakLinkage(); 418249259Sdim 419249259Sdim // byval arguments are ok. 420249259Sdim if (const Argument *A = dyn_cast<Argument>(V)) 421249259Sdim return A->hasByValAttr(); 422249259Sdim 423249259Sdim // For GEPs, determine if the indexing lands within the allocated object. 424249259Sdim if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 425249259Sdim // Conservatively require that the base pointer be fully dereferenceable. 426249259Sdim if (!Visited.insert(GEP->getOperand(0))) 427249259Sdim return false; 428249259Sdim if (!isDereferenceablePointer(GEP->getOperand(0), Visited)) 429249259Sdim return false; 430249259Sdim // Check the indices. 431249259Sdim gep_type_iterator GTI = gep_type_begin(GEP); 432249259Sdim for (User::const_op_iterator I = GEP->op_begin()+1, 433249259Sdim E = GEP->op_end(); I != E; ++I) { 434249259Sdim Value *Index = *I; 435249259Sdim Type *Ty = *GTI++; 436249259Sdim // Struct indices can't be out of bounds. 437249259Sdim if (isa<StructType>(Ty)) 438249259Sdim continue; 439249259Sdim ConstantInt *CI = dyn_cast<ConstantInt>(Index); 440249259Sdim if (!CI) 441249259Sdim return false; 442249259Sdim // Zero is always ok. 443249259Sdim if (CI->isZero()) 444249259Sdim continue; 445249259Sdim // Check to see that it's within the bounds of an array. 446249259Sdim ArrayType *ATy = dyn_cast<ArrayType>(Ty); 447249259Sdim if (!ATy) 448249259Sdim return false; 449249259Sdim if (CI->getValue().getActiveBits() > 64) 450249259Sdim return false; 451249259Sdim if (CI->getZExtValue() >= ATy->getNumElements()) 452249259Sdim return false; 453249259Sdim } 454249259Sdim // Indices check out; this is dereferenceable. 455249259Sdim return true; 456249259Sdim } 457249259Sdim 458249259Sdim // If we don't know, assume the worst. 459249259Sdim return false; 460249259Sdim} 461249259Sdim 462249259Sdim/// isDereferenceablePointer - Test if this value is always a pointer to 463249259Sdim/// allocated and suitably aligned memory for a simple load or store. 464249259Sdimbool Value::isDereferenceablePointer() const { 465249259Sdim SmallPtrSet<const Value *, 32> Visited; 466249259Sdim return ::isDereferenceablePointer(this, Visited); 467249259Sdim} 468249259Sdim 469249259Sdim/// DoPHITranslation - If this value is a PHI node with CurBB as its parent, 470249259Sdim/// return the value in the PHI node corresponding to PredBB. If not, return 471249259Sdim/// ourself. This is useful if you want to know the value something has in a 472249259Sdim/// predecessor block. 473249259SdimValue *Value::DoPHITranslation(const BasicBlock *CurBB, 474249259Sdim const BasicBlock *PredBB) { 475249259Sdim PHINode *PN = dyn_cast<PHINode>(this); 476249259Sdim if (PN && PN->getParent() == CurBB) 477249259Sdim return PN->getIncomingValueForBlock(PredBB); 478249259Sdim return this; 479249259Sdim} 480249259Sdim 481249259SdimLLVMContext &Value::getContext() const { return VTy->getContext(); } 482249259Sdim 483249259Sdim//===----------------------------------------------------------------------===// 484249259Sdim// ValueHandleBase Class 485249259Sdim//===----------------------------------------------------------------------===// 486249259Sdim 487249259Sdim/// AddToExistingUseList - Add this ValueHandle to the use list for VP, where 488249259Sdim/// List is known to point into the existing use list. 489249259Sdimvoid ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) { 490249259Sdim assert(List && "Handle list is null?"); 491249259Sdim 492249259Sdim // Splice ourselves into the list. 493249259Sdim Next = *List; 494249259Sdim *List = this; 495249259Sdim setPrevPtr(List); 496249259Sdim if (Next) { 497249259Sdim Next->setPrevPtr(&Next); 498249259Sdim assert(VP.getPointer() == Next->VP.getPointer() && "Added to wrong list?"); 499249259Sdim } 500249259Sdim} 501249259Sdim 502249259Sdimvoid ValueHandleBase::AddToExistingUseListAfter(ValueHandleBase *List) { 503249259Sdim assert(List && "Must insert after existing node"); 504249259Sdim 505249259Sdim Next = List->Next; 506249259Sdim setPrevPtr(&List->Next); 507249259Sdim List->Next = this; 508249259Sdim if (Next) 509249259Sdim Next->setPrevPtr(&Next); 510249259Sdim} 511249259Sdim 512249259Sdim/// AddToUseList - Add this ValueHandle to the use list for VP. 513249259Sdimvoid ValueHandleBase::AddToUseList() { 514249259Sdim assert(VP.getPointer() && "Null pointer doesn't have a use list!"); 515249259Sdim 516249259Sdim LLVMContextImpl *pImpl = VP.getPointer()->getContext().pImpl; 517249259Sdim 518249259Sdim if (VP.getPointer()->HasValueHandle) { 519249259Sdim // If this value already has a ValueHandle, then it must be in the 520249259Sdim // ValueHandles map already. 521249259Sdim ValueHandleBase *&Entry = pImpl->ValueHandles[VP.getPointer()]; 522249259Sdim assert(Entry != 0 && "Value doesn't have any handles?"); 523249259Sdim AddToExistingUseList(&Entry); 524249259Sdim return; 525249259Sdim } 526249259Sdim 527249259Sdim // Ok, it doesn't have any handles yet, so we must insert it into the 528249259Sdim // DenseMap. However, doing this insertion could cause the DenseMap to 529249259Sdim // reallocate itself, which would invalidate all of the PrevP pointers that 530249259Sdim // point into the old table. Handle this by checking for reallocation and 531249259Sdim // updating the stale pointers only if needed. 532249259Sdim DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles; 533249259Sdim const void *OldBucketPtr = Handles.getPointerIntoBucketsArray(); 534249259Sdim 535249259Sdim ValueHandleBase *&Entry = Handles[VP.getPointer()]; 536249259Sdim assert(Entry == 0 && "Value really did already have handles?"); 537249259Sdim AddToExistingUseList(&Entry); 538249259Sdim VP.getPointer()->HasValueHandle = true; 539249259Sdim 540249259Sdim // If reallocation didn't happen or if this was the first insertion, don't 541249259Sdim // walk the table. 542249259Sdim if (Handles.isPointerIntoBucketsArray(OldBucketPtr) || 543249259Sdim Handles.size() == 1) { 544249259Sdim return; 545249259Sdim } 546249259Sdim 547249259Sdim // Okay, reallocation did happen. Fix the Prev Pointers. 548249259Sdim for (DenseMap<Value*, ValueHandleBase*>::iterator I = Handles.begin(), 549249259Sdim E = Handles.end(); I != E; ++I) { 550249259Sdim assert(I->second && I->first == I->second->VP.getPointer() && 551249259Sdim "List invariant broken!"); 552249259Sdim I->second->setPrevPtr(&I->second); 553249259Sdim } 554249259Sdim} 555249259Sdim 556249259Sdim/// RemoveFromUseList - Remove this ValueHandle from its current use list. 557249259Sdimvoid ValueHandleBase::RemoveFromUseList() { 558249259Sdim assert(VP.getPointer() && VP.getPointer()->HasValueHandle && 559249259Sdim "Pointer doesn't have a use list!"); 560249259Sdim 561249259Sdim // Unlink this from its use list. 562249259Sdim ValueHandleBase **PrevPtr = getPrevPtr(); 563249259Sdim assert(*PrevPtr == this && "List invariant broken"); 564249259Sdim 565249259Sdim *PrevPtr = Next; 566249259Sdim if (Next) { 567249259Sdim assert(Next->getPrevPtr() == &Next && "List invariant broken"); 568249259Sdim Next->setPrevPtr(PrevPtr); 569249259Sdim return; 570249259Sdim } 571249259Sdim 572249259Sdim // If the Next pointer was null, then it is possible that this was the last 573249259Sdim // ValueHandle watching VP. If so, delete its entry from the ValueHandles 574249259Sdim // map. 575249259Sdim LLVMContextImpl *pImpl = VP.getPointer()->getContext().pImpl; 576249259Sdim DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles; 577249259Sdim if (Handles.isPointerIntoBucketsArray(PrevPtr)) { 578249259Sdim Handles.erase(VP.getPointer()); 579249259Sdim VP.getPointer()->HasValueHandle = false; 580249259Sdim } 581249259Sdim} 582249259Sdim 583249259Sdim 584249259Sdimvoid ValueHandleBase::ValueIsDeleted(Value *V) { 585249259Sdim assert(V->HasValueHandle && "Should only be called if ValueHandles present"); 586249259Sdim 587249259Sdim // Get the linked list base, which is guaranteed to exist since the 588249259Sdim // HasValueHandle flag is set. 589249259Sdim LLVMContextImpl *pImpl = V->getContext().pImpl; 590249259Sdim ValueHandleBase *Entry = pImpl->ValueHandles[V]; 591249259Sdim assert(Entry && "Value bit set but no entries exist"); 592249259Sdim 593249259Sdim // We use a local ValueHandleBase as an iterator so that ValueHandles can add 594249259Sdim // and remove themselves from the list without breaking our iteration. This 595249259Sdim // is not really an AssertingVH; we just have to give ValueHandleBase a kind. 596249259Sdim // Note that we deliberately do not the support the case when dropping a value 597249259Sdim // handle results in a new value handle being permanently added to the list 598249259Sdim // (as might occur in theory for CallbackVH's): the new value handle will not 599249259Sdim // be processed and the checking code will mete out righteous punishment if 600249259Sdim // the handle is still present once we have finished processing all the other 601249259Sdim // value handles (it is fine to momentarily add then remove a value handle). 602249259Sdim for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) { 603249259Sdim Iterator.RemoveFromUseList(); 604249259Sdim Iterator.AddToExistingUseListAfter(Entry); 605249259Sdim assert(Entry->Next == &Iterator && "Loop invariant broken."); 606249259Sdim 607249259Sdim switch (Entry->getKind()) { 608249259Sdim case Assert: 609249259Sdim break; 610249259Sdim case Tracking: 611249259Sdim // Mark that this value has been deleted by setting it to an invalid Value 612249259Sdim // pointer. 613249259Sdim Entry->operator=(DenseMapInfo<Value *>::getTombstoneKey()); 614249259Sdim break; 615249259Sdim case Weak: 616249259Sdim // Weak just goes to null, which will unlink it from the list. 617249259Sdim Entry->operator=(0); 618249259Sdim break; 619249259Sdim case Callback: 620249259Sdim // Forward to the subclass's implementation. 621249259Sdim static_cast<CallbackVH*>(Entry)->deleted(); 622249259Sdim break; 623249259Sdim } 624249259Sdim } 625249259Sdim 626249259Sdim // All callbacks, weak references, and assertingVHs should be dropped by now. 627249259Sdim if (V->HasValueHandle) { 628249259Sdim#ifndef NDEBUG // Only in +Asserts mode... 629249259Sdim dbgs() << "While deleting: " << *V->getType() << " %" << V->getName() 630249259Sdim << "\n"; 631249259Sdim if (pImpl->ValueHandles[V]->getKind() == Assert) 632249259Sdim llvm_unreachable("An asserting value handle still pointed to this" 633249259Sdim " value!"); 634249259Sdim 635249259Sdim#endif 636249259Sdim llvm_unreachable("All references to V were not removed?"); 637249259Sdim } 638249259Sdim} 639249259Sdim 640249259Sdim 641249259Sdimvoid ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) { 642249259Sdim assert(Old->HasValueHandle &&"Should only be called if ValueHandles present"); 643249259Sdim assert(Old != New && "Changing value into itself!"); 644249259Sdim 645249259Sdim // Get the linked list base, which is guaranteed to exist since the 646249259Sdim // HasValueHandle flag is set. 647249259Sdim LLVMContextImpl *pImpl = Old->getContext().pImpl; 648249259Sdim ValueHandleBase *Entry = pImpl->ValueHandles[Old]; 649249259Sdim 650249259Sdim assert(Entry && "Value bit set but no entries exist"); 651249259Sdim 652249259Sdim // We use a local ValueHandleBase as an iterator so that 653249259Sdim // ValueHandles can add and remove themselves from the list without 654249259Sdim // breaking our iteration. This is not really an AssertingVH; we 655249259Sdim // just have to give ValueHandleBase some kind. 656249259Sdim for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) { 657249259Sdim Iterator.RemoveFromUseList(); 658249259Sdim Iterator.AddToExistingUseListAfter(Entry); 659249259Sdim assert(Entry->Next == &Iterator && "Loop invariant broken."); 660249259Sdim 661249259Sdim switch (Entry->getKind()) { 662249259Sdim case Assert: 663249259Sdim // Asserting handle does not follow RAUW implicitly. 664249259Sdim break; 665249259Sdim case Tracking: 666249259Sdim // Tracking goes to new value like a WeakVH. Note that this may make it 667249259Sdim // something incompatible with its templated type. We don't want to have a 668249259Sdim // virtual (or inline) interface to handle this though, so instead we make 669249259Sdim // the TrackingVH accessors guarantee that a client never sees this value. 670249259Sdim 671249259Sdim // FALLTHROUGH 672249259Sdim case Weak: 673249259Sdim // Weak goes to the new value, which will unlink it from Old's list. 674249259Sdim Entry->operator=(New); 675249259Sdim break; 676249259Sdim case Callback: 677249259Sdim // Forward to the subclass's implementation. 678249259Sdim static_cast<CallbackVH*>(Entry)->allUsesReplacedWith(New); 679249259Sdim break; 680249259Sdim } 681249259Sdim } 682249259Sdim 683249259Sdim#ifndef NDEBUG 684249259Sdim // If any new tracking or weak value handles were added while processing the 685249259Sdim // list, then complain about it now. 686249259Sdim if (Old->HasValueHandle) 687249259Sdim for (Entry = pImpl->ValueHandles[Old]; Entry; Entry = Entry->Next) 688249259Sdim switch (Entry->getKind()) { 689249259Sdim case Tracking: 690249259Sdim case Weak: 691249259Sdim dbgs() << "After RAUW from " << *Old->getType() << " %" 692249259Sdim << Old->getName() << " to " << *New->getType() << " %" 693249259Sdim << New->getName() << "\n"; 694249259Sdim llvm_unreachable("A tracking or weak value handle still pointed to the" 695249259Sdim " old value!\n"); 696249259Sdim default: 697249259Sdim break; 698249259Sdim } 699249259Sdim#endif 700249259Sdim} 701249259Sdim 702249259Sdim// Default implementation for CallbackVH. 703249259Sdimvoid CallbackVH::allUsesReplacedWith(Value *) {} 704249259Sdim 705249259Sdimvoid CallbackVH::deleted() { 706249259Sdim setValPtr(NULL); 707249259Sdim} 708