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