lib/IR/Value.cpp

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