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