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