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