1 //===-- Value.cpp - Implement the Value class -----------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the Value, ValueHandle, and User classes. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/IR/Value.h" 15 #include "LLVMContextImpl.h" 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/SmallString.h" 18 #include "llvm/IR/CallSite.h" 19 #include "llvm/IR/Constant.h" 20 #include "llvm/IR/Constants.h" 21 #include "llvm/IR/DataLayout.h" 22 #include "llvm/IR/DerivedTypes.h" 23 #include "llvm/IR/GetElementPtrTypeIterator.h" 24 #include "llvm/IR/InstrTypes.h" 25 #include "llvm/IR/Instructions.h" 26 #include "llvm/IR/IntrinsicInst.h" 27 #include "llvm/IR/Module.h" 28 #include "llvm/IR/Operator.h" 29 #include "llvm/IR/Statepoint.h" 30 #include "llvm/IR/ValueHandle.h" 31 #include "llvm/IR/ValueSymbolTable.h" 32 #include "llvm/Support/Debug.h" 33 #include "llvm/Support/ErrorHandling.h" 34 #include "llvm/Support/ManagedStatic.h" 35 #include "llvm/Support/raw_ostream.h" 36 #include <algorithm> 37 using namespace llvm; 38 39 //===----------------------------------------------------------------------===// 40 // Value Class 41 //===----------------------------------------------------------------------===// 42 43 static inline Type *checkType(Type *Ty) { 44 assert(Ty && "Value defined with a null type: Error!"); 45 return Ty; 46 } 47 48 Value::Value(Type *ty, unsigned scid) 49 : VTy(checkType(ty)), UseList(nullptr), SubclassID(scid), HasValueHandle(0), 50 SubclassOptionalData(0), SubclassData(0), NumOperands(0) { 51 // FIXME: Why isn't this in the subclass gunk?? 52 // Note, we cannot call isa<CallInst> before the CallInst has been 53 // constructed. 54 if (SubclassID == Instruction::Call || SubclassID == Instruction::Invoke) 55 assert((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) && 56 "invalid CallInst type!"); 57 else if (SubclassID != BasicBlockVal && 58 (SubclassID < ConstantFirstVal || SubclassID > ConstantLastVal)) 59 assert((VTy->isFirstClassType() || VTy->isVoidTy()) && 60 "Cannot create non-first-class values except for constants!"); 61 } 62 63 Value::~Value() { 64 // Notify all ValueHandles (if present) that this value is going away. 65 if (HasValueHandle) 66 ValueHandleBase::ValueIsDeleted(this); 67 if (isUsedByMetadata()) 68 ValueAsMetadata::handleDeletion(this); 69 70 #ifndef NDEBUG // Only in -g mode... 71 // Check to make sure that there are no uses of this value that are still 72 // around when the value is destroyed. If there are, then we have a dangling 73 // reference and something is wrong. This code is here to print out where 74 // the value is still being referenced. 75 // 76 if (!use_empty()) { 77 dbgs() << "While deleting: " << *VTy << " %" << getName() << "\n"; 78 for (auto *U : users()) 79 dbgs() << "Use still stuck around after Def is destroyed:" << *U << "\n"; 80 } 81 #endif 82 assert(use_empty() && "Uses remain when a value is destroyed!"); 83 84 // If this value is named, destroy the name. This should not be in a symtab 85 // at this point. 86 destroyValueName(); 87 } 88 89 void Value::destroyValueName() { 90 ValueName *Name = getValueName(); 91 if (Name) 92 Name->Destroy(); 93 setValueName(nullptr); 94 } 95 96 bool Value::hasNUses(unsigned N) const { 97 const_use_iterator UI = use_begin(), E = use_end(); 98 99 for (; N; --N, ++UI) 100 if (UI == E) return false; // Too few. 101 return UI == E; 102 } 103 104 bool Value::hasNUsesOrMore(unsigned N) const { 105 const_use_iterator UI = use_begin(), E = use_end(); 106 107 for (; N; --N, ++UI) 108 if (UI == E) return false; // Too few. 109 110 return true; 111 } 112 113 bool Value::isUsedInBasicBlock(const BasicBlock *BB) const { 114 // This can be computed either by scanning the instructions in BB, or by 115 // scanning the use list of this Value. Both lists can be very long, but 116 // usually one is quite short. 117 // 118 // Scan both lists simultaneously until one is exhausted. This limits the 119 // search to the shorter list. 120 BasicBlock::const_iterator BI = BB->begin(), BE = BB->end(); 121 const_user_iterator UI = user_begin(), UE = user_end(); 122 for (; BI != BE && UI != UE; ++BI, ++UI) { 123 // Scan basic block: Check if this Value is used by the instruction at BI. 124 if (std::find(BI->op_begin(), BI->op_end(), this) != BI->op_end()) 125 return true; 126 // Scan use list: Check if the use at UI is in BB. 127 const Instruction *User = dyn_cast<Instruction>(*UI); 128 if (User && User->getParent() == BB) 129 return true; 130 } 131 return false; 132 } 133 134 unsigned Value::getNumUses() const { 135 return (unsigned)std::distance(use_begin(), use_end()); 136 } 137 138 static bool getSymTab(Value *V, ValueSymbolTable *&ST) { 139 ST = nullptr; 140 if (Instruction *I = dyn_cast<Instruction>(V)) { 141 if (BasicBlock *P = I->getParent()) 142 if (Function *PP = P->getParent()) 143 ST = &PP->getValueSymbolTable(); 144 } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 145 if (Function *P = BB->getParent()) 146 ST = &P->getValueSymbolTable(); 147 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 148 if (Module *P = GV->getParent()) 149 ST = &P->getValueSymbolTable(); 150 } else if (Argument *A = dyn_cast<Argument>(V)) { 151 if (Function *P = A->getParent()) 152 ST = &P->getValueSymbolTable(); 153 } else { 154 assert(isa<Constant>(V) && "Unknown value type!"); 155 return true; // no name is setable for this. 156 } 157 return false; 158 } 159 160 StringRef Value::getName() const { 161 // Make sure the empty string is still a C string. For historical reasons, 162 // some clients want to call .data() on the result and expect it to be null 163 // terminated. 164 if (!getValueName()) 165 return StringRef("", 0); 166 return getValueName()->getKey(); 167 } 168 169 void Value::setName(const Twine &NewName) { 170 // Fast path for common IRBuilder case of setName("") when there is no name. 171 if (NewName.isTriviallyEmpty() && !hasName()) 172 return; 173 174 SmallString<256> NameData; 175 StringRef NameRef = NewName.toStringRef(NameData); 176 assert(NameRef.find_first_of(0) == StringRef::npos && 177 "Null bytes are not allowed in names"); 178 179 // Name isn't changing? 180 if (getName() == NameRef) 181 return; 182 183 assert(!getType()->isVoidTy() && "Cannot assign a name to void values!"); 184 185 // Get the symbol table to update for this object. 186 ValueSymbolTable *ST; 187 if (getSymTab(this, ST)) 188 return; // Cannot set a name on this value (e.g. constant). 189 190 if (Function *F = dyn_cast<Function>(this)) 191 getContext().pImpl->IntrinsicIDCache.erase(F); 192 193 if (!ST) { // No symbol table to update? Just do the change. 194 if (NameRef.empty()) { 195 // Free the name for this value. 196 destroyValueName(); 197 return; 198 } 199 200 // NOTE: Could optimize for the case the name is shrinking to not deallocate 201 // then reallocated. 202 destroyValueName(); 203 204 // Create the new name. 205 setValueName(ValueName::Create(NameRef)); 206 getValueName()->setValue(this); 207 return; 208 } 209 210 // NOTE: Could optimize for the case the name is shrinking to not deallocate 211 // then reallocated. 212 if (hasName()) { 213 // Remove old name. 214 ST->removeValueName(getValueName()); 215 destroyValueName(); 216 217 if (NameRef.empty()) 218 return; 219 } 220 221 // Name is changing to something new. 222 setValueName(ST->createValueName(NameRef, this)); 223 } 224 225 void Value::takeName(Value *V) { 226 ValueSymbolTable *ST = nullptr; 227 // If this value has a name, drop it. 228 if (hasName()) { 229 // Get the symtab this is in. 230 if (getSymTab(this, ST)) { 231 // We can't set a name on this value, but we need to clear V's name if 232 // it has one. 233 if (V->hasName()) V->setName(""); 234 return; // Cannot set a name on this value (e.g. constant). 235 } 236 237 // Remove old name. 238 if (ST) 239 ST->removeValueName(getValueName()); 240 destroyValueName(); 241 } 242 243 // Now we know that this has no name. 244 245 // If V has no name either, we're done. 246 if (!V->hasName()) return; 247 248 // Get this's symtab if we didn't before. 249 if (!ST) { 250 if (getSymTab(this, ST)) { 251 // Clear V's name. 252 V->setName(""); 253 return; // Cannot set a name on this value (e.g. constant). 254 } 255 } 256 257 // Get V's ST, this should always succed, because V has a name. 258 ValueSymbolTable *VST; 259 bool Failure = getSymTab(V, VST); 260 assert(!Failure && "V has a name, so it should have a ST!"); (void)Failure; 261 262 // If these values are both in the same symtab, we can do this very fast. 263 // This works even if both values have no symtab yet. 264 if (ST == VST) { 265 // Take the name! 266 setValueName(V->getValueName()); 267 V->setValueName(nullptr); 268 getValueName()->setValue(this); 269 return; 270 } 271 272 // Otherwise, things are slightly more complex. Remove V's name from VST and 273 // then reinsert it into ST. 274 275 if (VST) 276 VST->removeValueName(V->getValueName()); 277 setValueName(V->getValueName()); 278 V->setValueName(nullptr); 279 getValueName()->setValue(this); 280 281 if (ST) 282 ST->reinsertValue(this); 283 } 284 285 #ifndef NDEBUG 286 static bool contains(SmallPtrSetImpl<ConstantExpr *> &Cache, ConstantExpr *Expr, 287 Constant *C) { 288 if (!Cache.insert(Expr).second) 289 return false; 290 291 for (auto &O : Expr->operands()) { 292 if (O == C) 293 return true; 294 auto *CE = dyn_cast<ConstantExpr>(O); 295 if (!CE) 296 continue; 297 if (contains(Cache, CE, C)) 298 return true; 299 } 300 return false; 301 } 302 303 static bool contains(Value *Expr, Value *V) { 304 if (Expr == V) 305 return true; 306 307 auto *C = dyn_cast<Constant>(V); 308 if (!C) 309 return false; 310 311 auto *CE = dyn_cast<ConstantExpr>(Expr); 312 if (!CE) 313 return false; 314 315 SmallPtrSet<ConstantExpr *, 4> Cache; 316 return contains(Cache, CE, C); 317 } 318 #endif 319 320 void Value::replaceAllUsesWith(Value *New) { 321 assert(New && "Value::replaceAllUsesWith(<null>) is invalid!"); 322 assert(!contains(New, this) && 323 "this->replaceAllUsesWith(expr(this)) is NOT valid!"); 324 assert(New->getType() == getType() && 325 "replaceAllUses of value with new value of different type!"); 326 327 // Notify all ValueHandles (if present) that this value is going away. 328 if (HasValueHandle) 329 ValueHandleBase::ValueIsRAUWd(this, New); 330 if (isUsedByMetadata()) 331 ValueAsMetadata::handleRAUW(this, New); 332 333 while (!use_empty()) { 334 Use &U = *UseList; 335 // Must handle Constants specially, we cannot call replaceUsesOfWith on a 336 // constant because they are uniqued. 337 if (auto *C = dyn_cast<Constant>(U.getUser())) { 338 if (!isa<GlobalValue>(C)) { 339 C->replaceUsesOfWithOnConstant(this, New, &U); 340 continue; 341 } 342 } 343 344 U.set(New); 345 } 346 347 if (BasicBlock *BB = dyn_cast<BasicBlock>(this)) 348 BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New)); 349 } 350 351 // Like replaceAllUsesWith except it does not handle constants or basic blocks. 352 // This routine leaves uses within BB. 353 void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) { 354 assert(New && "Value::replaceUsesOutsideBlock(<null>, BB) is invalid!"); 355 assert(!contains(New, this) && 356 "this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!"); 357 assert(New->getType() == getType() && 358 "replaceUses of value with new value of different type!"); 359 assert(BB && "Basic block that may contain a use of 'New' must be defined\n"); 360 361 use_iterator UI = use_begin(), E = use_end(); 362 for (; UI != E;) { 363 Use &U = *UI; 364 ++UI; 365 auto *Usr = dyn_cast<Instruction>(U.getUser()); 366 if (Usr && Usr->getParent() == BB) 367 continue; 368 U.set(New); 369 } 370 return; 371 } 372 373 namespace { 374 // Various metrics for how much to strip off of pointers. 375 enum PointerStripKind { 376 PSK_ZeroIndices, 377 PSK_ZeroIndicesAndAliases, 378 PSK_InBoundsConstantIndices, 379 PSK_InBounds 380 }; 381 382 template <PointerStripKind StripKind> 383 static Value *stripPointerCastsAndOffsets(Value *V) { 384 if (!V->getType()->isPointerTy()) 385 return V; 386 387 // Even though we don't look through PHI nodes, we could be called on an 388 // instruction in an unreachable block, which may be on a cycle. 389 SmallPtrSet<Value *, 4> Visited; 390 391 Visited.insert(V); 392 do { 393 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 394 switch (StripKind) { 395 case PSK_ZeroIndicesAndAliases: 396 case PSK_ZeroIndices: 397 if (!GEP->hasAllZeroIndices()) 398 return V; 399 break; 400 case PSK_InBoundsConstantIndices: 401 if (!GEP->hasAllConstantIndices()) 402 return V; 403 // fallthrough 404 case PSK_InBounds: 405 if (!GEP->isInBounds()) 406 return V; 407 break; 408 } 409 V = GEP->getPointerOperand(); 410 } else if (Operator::getOpcode(V) == Instruction::BitCast || 411 Operator::getOpcode(V) == Instruction::AddrSpaceCast) { 412 V = cast<Operator>(V)->getOperand(0); 413 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 414 if (StripKind == PSK_ZeroIndices || GA->mayBeOverridden()) 415 return V; 416 V = GA->getAliasee(); 417 } else { 418 return V; 419 } 420 assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 421 } while (Visited.insert(V).second); 422 423 return V; 424 } 425 } // namespace 426 427 Value *Value::stripPointerCasts() { 428 return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this); 429 } 430 431 Value *Value::stripPointerCastsNoFollowAliases() { 432 return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this); 433 } 434 435 Value *Value::stripInBoundsConstantOffsets() { 436 return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this); 437 } 438 439 Value *Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, 440 APInt &Offset) { 441 if (!getType()->isPointerTy()) 442 return this; 443 444 assert(Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType>( 445 getType())->getAddressSpace()) && 446 "The offset must have exactly as many bits as our pointer."); 447 448 // Even though we don't look through PHI nodes, we could be called on an 449 // instruction in an unreachable block, which may be on a cycle. 450 SmallPtrSet<Value *, 4> Visited; 451 Visited.insert(this); 452 Value *V = this; 453 do { 454 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 455 if (!GEP->isInBounds()) 456 return V; 457 APInt GEPOffset(Offset); 458 if (!GEP->accumulateConstantOffset(DL, GEPOffset)) 459 return V; 460 Offset = GEPOffset; 461 V = GEP->getPointerOperand(); 462 } else if (Operator::getOpcode(V) == Instruction::BitCast || 463 Operator::getOpcode(V) == Instruction::AddrSpaceCast) { 464 V = cast<Operator>(V)->getOperand(0); 465 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 466 V = GA->getAliasee(); 467 } else { 468 return V; 469 } 470 assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 471 } while (Visited.insert(V).second); 472 473 return V; 474 } 475 476 Value *Value::stripInBoundsOffsets() { 477 return stripPointerCastsAndOffsets<PSK_InBounds>(this); 478 } 479 480 /// \brief Check if Value is always a dereferenceable pointer. 481 /// 482 /// Test if V is always a pointer to allocated and suitably aligned memory for 483 /// a simple load or store. 484 static bool isDereferenceablePointer(const Value *V, const DataLayout &DL, 485 SmallPtrSetImpl<const Value *> &Visited) { 486 // Note that it is not safe to speculate into a malloc'd region because 487 // malloc may return null. 488 489 // These are obviously ok. 490 if (isa<AllocaInst>(V)) return true; 491 492 // It's not always safe to follow a bitcast, for example: 493 // bitcast i8* (alloca i8) to i32* 494 // would result in a 4-byte load from a 1-byte alloca. However, 495 // if we're casting from a pointer from a type of larger size 496 // to a type of smaller size (or the same size), and the alignment 497 // is at least as large as for the resulting pointer type, then 498 // we can look through the bitcast. 499 if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) { 500 Type *STy = BC->getSrcTy()->getPointerElementType(), 501 *DTy = BC->getDestTy()->getPointerElementType(); 502 if (STy->isSized() && DTy->isSized() && 503 (DL.getTypeStoreSize(STy) >= DL.getTypeStoreSize(DTy)) && 504 (DL.getABITypeAlignment(STy) >= DL.getABITypeAlignment(DTy))) 505 return isDereferenceablePointer(BC->getOperand(0), DL, Visited); 506 } 507 508 // Global variables which can't collapse to null are ok. 509 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 510 return !GV->hasExternalWeakLinkage(); 511 512 // byval arguments are okay. Arguments specifically marked as 513 // dereferenceable are okay too. 514 if (const Argument *A = dyn_cast<Argument>(V)) { 515 if (A->hasByValAttr()) 516 return true; 517 else if (uint64_t Bytes = A->getDereferenceableBytes()) { 518 Type *Ty = V->getType()->getPointerElementType(); 519 if (Ty->isSized() && DL.getTypeStoreSize(Ty) <= Bytes) 520 return true; 521 } 522 523 return false; 524 } 525 526 // Return values from call sites specifically marked as dereferenceable are 527 // also okay. 528 if (auto CS = ImmutableCallSite(V)) { 529 if (uint64_t Bytes = CS.getDereferenceableBytes(0)) { 530 Type *Ty = V->getType()->getPointerElementType(); 531 if (Ty->isSized() && DL.getTypeStoreSize(Ty) <= Bytes) 532 return true; 533 } 534 } 535 536 // For GEPs, determine if the indexing lands within the allocated object. 537 if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 538 // Conservatively require that the base pointer be fully dereferenceable. 539 if (!Visited.insert(GEP->getOperand(0)).second) 540 return false; 541 if (!isDereferenceablePointer(GEP->getOperand(0), DL, Visited)) 542 return false; 543 // Check the indices. 544 gep_type_iterator GTI = gep_type_begin(GEP); 545 for (User::const_op_iterator I = GEP->op_begin()+1, 546 E = GEP->op_end(); I != E; ++I) { 547 Value *Index = *I; 548 Type *Ty = *GTI++; 549 // Struct indices can't be out of bounds. 550 if (isa<StructType>(Ty)) 551 continue; 552 ConstantInt *CI = dyn_cast<ConstantInt>(Index); 553 if (!CI) 554 return false; 555 // Zero is always ok. 556 if (CI->isZero()) 557 continue; 558 // Check to see that it's within the bounds of an array. 559 ArrayType *ATy = dyn_cast<ArrayType>(Ty); 560 if (!ATy) 561 return false; 562 if (CI->getValue().getActiveBits() > 64) 563 return false; 564 if (CI->getZExtValue() >= ATy->getNumElements()) 565 return false; 566 } 567 // Indices check out; this is dereferenceable. 568 return true; 569 } 570 571 // For gc.relocate, look through relocations 572 if (const IntrinsicInst *I = dyn_cast<IntrinsicInst>(V)) 573 if (I->getIntrinsicID() == Intrinsic::experimental_gc_relocate) { 574 GCRelocateOperands RelocateInst(I); 575 return isDereferenceablePointer(RelocateInst.derivedPtr(), DL, Visited); 576 } 577 578 if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V)) 579 return isDereferenceablePointer(ASC->getOperand(0), DL, Visited); 580 581 // If we don't know, assume the worst. 582 return false; 583 } 584 585 bool Value::isDereferenceablePointer(const DataLayout &DL) const { 586 // When dereferenceability information is provided by a dereferenceable 587 // attribute, we know exactly how many bytes are dereferenceable. If we can 588 // determine the exact offset to the attributed variable, we can use that 589 // information here. 590 Type *Ty = getType()->getPointerElementType(); 591 if (Ty->isSized()) { 592 APInt Offset(DL.getTypeStoreSizeInBits(getType()), 0); 593 const Value *BV = stripAndAccumulateInBoundsConstantOffsets(DL, Offset); 594 595 APInt DerefBytes(Offset.getBitWidth(), 0); 596 if (const Argument *A = dyn_cast<Argument>(BV)) 597 DerefBytes = A->getDereferenceableBytes(); 598 else if (auto CS = ImmutableCallSite(BV)) 599 DerefBytes = CS.getDereferenceableBytes(0); 600 601 if (DerefBytes.getBoolValue() && Offset.isNonNegative()) { 602 if (DerefBytes.uge(Offset + DL.getTypeStoreSize(Ty))) 603 return true; 604 } 605 } 606 607 SmallPtrSet<const Value *, 32> Visited; 608 return ::isDereferenceablePointer(this, DL, Visited); 609 } 610 611 Value *Value::DoPHITranslation(const BasicBlock *CurBB, 612 const BasicBlock *PredBB) { 613 PHINode *PN = dyn_cast<PHINode>(this); 614 if (PN && PN->getParent() == CurBB) 615 return PN->getIncomingValueForBlock(PredBB); 616 return this; 617 } 618 619 LLVMContext &Value::getContext() const { return VTy->getContext(); } 620 621 void Value::reverseUseList() { 622 if (!UseList || !UseList->Next) 623 // No need to reverse 0 or 1 uses. 624 return; 625 626 Use *Head = UseList; 627 Use *Current = UseList->Next; 628 Head->Next = nullptr; 629 while (Current) { 630 Use *Next = Current->Next; 631 Current->Next = Head; 632 Head->setPrev(&Current->Next); 633 Head = Current; 634 Current = Next; 635 } 636 UseList = Head; 637 Head->setPrev(&UseList); 638 } 639 640 //===----------------------------------------------------------------------===// 641 // ValueHandleBase Class 642 //===----------------------------------------------------------------------===// 643 644 void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) { 645 assert(List && "Handle list is null?"); 646 647 // Splice ourselves into the list. 648 Next = *List; 649 *List = this; 650 setPrevPtr(List); 651 if (Next) { 652 Next->setPrevPtr(&Next); 653 assert(V == Next->V && "Added to wrong list?"); 654 } 655 } 656 657 void ValueHandleBase::AddToExistingUseListAfter(ValueHandleBase *List) { 658 assert(List && "Must insert after existing node"); 659 660 Next = List->Next; 661 setPrevPtr(&List->Next); 662 List->Next = this; 663 if (Next) 664 Next->setPrevPtr(&Next); 665 } 666 667 void ValueHandleBase::AddToUseList() { 668 assert(V && "Null pointer doesn't have a use list!"); 669 670 LLVMContextImpl *pImpl = V->getContext().pImpl; 671 672 if (V->HasValueHandle) { 673 // If this value already has a ValueHandle, then it must be in the 674 // ValueHandles map already. 675 ValueHandleBase *&Entry = pImpl->ValueHandles[V]; 676 assert(Entry && "Value doesn't have any handles?"); 677 AddToExistingUseList(&Entry); 678 return; 679 } 680 681 // Ok, it doesn't have any handles yet, so we must insert it into the 682 // DenseMap. However, doing this insertion could cause the DenseMap to 683 // reallocate itself, which would invalidate all of the PrevP pointers that 684 // point into the old table. Handle this by checking for reallocation and 685 // updating the stale pointers only if needed. 686 DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles; 687 const void *OldBucketPtr = Handles.getPointerIntoBucketsArray(); 688 689 ValueHandleBase *&Entry = Handles[V]; 690 assert(!Entry && "Value really did already have handles?"); 691 AddToExistingUseList(&Entry); 692 V->HasValueHandle = true; 693 694 // If reallocation didn't happen or if this was the first insertion, don't 695 // walk the table. 696 if (Handles.isPointerIntoBucketsArray(OldBucketPtr) || 697 Handles.size() == 1) { 698 return; 699 } 700 701 // Okay, reallocation did happen. Fix the Prev Pointers. 702 for (DenseMap<Value*, ValueHandleBase*>::iterator I = Handles.begin(), 703 E = Handles.end(); I != E; ++I) { 704 assert(I->second && I->first == I->second->V && 705 "List invariant broken!"); 706 I->second->setPrevPtr(&I->second); 707 } 708 } 709 710 void ValueHandleBase::RemoveFromUseList() { 711 assert(V && V->HasValueHandle && 712 "Pointer doesn't have a use list!"); 713 714 // Unlink this from its use list. 715 ValueHandleBase **PrevPtr = getPrevPtr(); 716 assert(*PrevPtr == this && "List invariant broken"); 717 718 *PrevPtr = Next; 719 if (Next) { 720 assert(Next->getPrevPtr() == &Next && "List invariant broken"); 721 Next->setPrevPtr(PrevPtr); 722 return; 723 } 724 725 // If the Next pointer was null, then it is possible that this was the last 726 // ValueHandle watching VP. If so, delete its entry from the ValueHandles 727 // map. 728 LLVMContextImpl *pImpl = V->getContext().pImpl; 729 DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles; 730 if (Handles.isPointerIntoBucketsArray(PrevPtr)) { 731 Handles.erase(V); 732 V->HasValueHandle = false; 733 } 734 } 735 736 737 void ValueHandleBase::ValueIsDeleted(Value *V) { 738 assert(V->HasValueHandle && "Should only be called if ValueHandles present"); 739 740 // Get the linked list base, which is guaranteed to exist since the 741 // HasValueHandle flag is set. 742 LLVMContextImpl *pImpl = V->getContext().pImpl; 743 ValueHandleBase *Entry = pImpl->ValueHandles[V]; 744 assert(Entry && "Value bit set but no entries exist"); 745 746 // We use a local ValueHandleBase as an iterator so that ValueHandles can add 747 // and remove themselves from the list without breaking our iteration. This 748 // is not really an AssertingVH; we just have to give ValueHandleBase a kind. 749 // Note that we deliberately do not the support the case when dropping a value 750 // handle results in a new value handle being permanently added to the list 751 // (as might occur in theory for CallbackVH's): the new value handle will not 752 // be processed and the checking code will mete out righteous punishment if 753 // the handle is still present once we have finished processing all the other 754 // value handles (it is fine to momentarily add then remove a value handle). 755 for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) { 756 Iterator.RemoveFromUseList(); 757 Iterator.AddToExistingUseListAfter(Entry); 758 assert(Entry->Next == &Iterator && "Loop invariant broken."); 759 760 switch (Entry->getKind()) { 761 case Assert: 762 break; 763 case Tracking: 764 // Mark that this value has been deleted by setting it to an invalid Value 765 // pointer. 766 Entry->operator=(DenseMapInfo<Value *>::getTombstoneKey()); 767 break; 768 case Weak: 769 // Weak just goes to null, which will unlink it from the list. 770 Entry->operator=(nullptr); 771 break; 772 case Callback: 773 // Forward to the subclass's implementation. 774 static_cast<CallbackVH*>(Entry)->deleted(); 775 break; 776 } 777 } 778 779 // All callbacks, weak references, and assertingVHs should be dropped by now. 780 if (V->HasValueHandle) { 781 #ifndef NDEBUG // Only in +Asserts mode... 782 dbgs() << "While deleting: " << *V->getType() << " %" << V->getName() 783 << "\n"; 784 if (pImpl->ValueHandles[V]->getKind() == Assert) 785 llvm_unreachable("An asserting value handle still pointed to this" 786 " value!"); 787 788 #endif 789 llvm_unreachable("All references to V were not removed?"); 790 } 791 } 792 793 794 void ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) { 795 assert(Old->HasValueHandle &&"Should only be called if ValueHandles present"); 796 assert(Old != New && "Changing value into itself!"); 797 assert(Old->getType() == New->getType() && 798 "replaceAllUses of value with new value of different type!"); 799 800 // Get the linked list base, which is guaranteed to exist since the 801 // HasValueHandle flag is set. 802 LLVMContextImpl *pImpl = Old->getContext().pImpl; 803 ValueHandleBase *Entry = pImpl->ValueHandles[Old]; 804 805 assert(Entry && "Value bit set but no entries exist"); 806 807 // We use a local ValueHandleBase as an iterator so that 808 // ValueHandles can add and remove themselves from the list without 809 // breaking our iteration. This is not really an AssertingVH; we 810 // just have to give ValueHandleBase some kind. 811 for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) { 812 Iterator.RemoveFromUseList(); 813 Iterator.AddToExistingUseListAfter(Entry); 814 assert(Entry->Next == &Iterator && "Loop invariant broken."); 815 816 switch (Entry->getKind()) { 817 case Assert: 818 // Asserting handle does not follow RAUW implicitly. 819 break; 820 case Tracking: 821 // Tracking goes to new value like a WeakVH. Note that this may make it 822 // something incompatible with its templated type. We don't want to have a 823 // virtual (or inline) interface to handle this though, so instead we make 824 // the TrackingVH accessors guarantee that a client never sees this value. 825 826 // FALLTHROUGH 827 case Weak: 828 // Weak goes to the new value, which will unlink it from Old's list. 829 Entry->operator=(New); 830 break; 831 case Callback: 832 // Forward to the subclass's implementation. 833 static_cast<CallbackVH*>(Entry)->allUsesReplacedWith(New); 834 break; 835 } 836 } 837 838 #ifndef NDEBUG 839 // If any new tracking or weak value handles were added while processing the 840 // list, then complain about it now. 841 if (Old->HasValueHandle) 842 for (Entry = pImpl->ValueHandles[Old]; Entry; Entry = Entry->Next) 843 switch (Entry->getKind()) { 844 case Tracking: 845 case Weak: 846 dbgs() << "After RAUW from " << *Old->getType() << " %" 847 << Old->getName() << " to " << *New->getType() << " %" 848 << New->getName() << "\n"; 849 llvm_unreachable("A tracking or weak value handle still pointed to the" 850 " old value!\n"); 851 default: 852 break; 853 } 854 #endif 855 } 856 857 // Pin the vtable to this file. 858 void CallbackVH::anchor() {} 859