contrib/llvm-project/llvm/lib/IR/Value.cpp

   1 //===-- Value.cpp - Implement the Value class -----------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the Value, ValueHandle, and User classes.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/IR/Value.h"
  14 #include "LLVMContextImpl.h"
  15 #include "llvm/ADT/DenseMap.h"
  16 #include "llvm/ADT/SetVector.h"
  17 #include "llvm/ADT/SmallString.h"
  18 #include "llvm/IR/Constant.h"
  19 #include "llvm/IR/Constants.h"
  20 #include "llvm/IR/DataLayout.h"
  21 #include "llvm/IR/DerivedTypes.h"
  22 #include "llvm/IR/DerivedUser.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/CommandLine.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 static cl::opt<unsigned> NonGlobalValueMaxNameSize(
  42     "non-global-value-max-name-size", cl::Hidden, cl::init(1024),
  43     cl::desc("Maximum size for the name of non-global values."));
  44
  45 //===----------------------------------------------------------------------===//
  46 //                                Value Class
  47 //===----------------------------------------------------------------------===//
  48 static inline Type *checkType(Type *Ty) {
  49   assert(Ty && "Value defined with a null type: Error!");
  50   return Ty;
  51 }
  52
  53 Value::Value(Type *ty, unsigned scid)
  54     : VTy(checkType(ty)), UseList(nullptr), SubclassID(scid),
  55       HasValueHandle(0), SubclassOptionalData(0), SubclassData(0),
  56       NumUserOperands(0), IsUsedByMD(false), HasName(false) {
  57   static_assert(ConstantFirstVal == 0, "!(SubclassID < ConstantFirstVal)");
  58   // FIXME: Why isn't this in the subclass gunk??
  59   // Note, we cannot call isa<CallInst> before the CallInst has been
  60   // constructed.
  61   if (SubclassID == Instruction::Call || SubclassID == Instruction::Invoke ||
  62       SubclassID == Instruction::CallBr)
  63     assert((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) &&
  64            "invalid CallInst type!");
  65   else if (SubclassID != BasicBlockVal &&
  66            (/*SubclassID < ConstantFirstVal ||*/ SubclassID > ConstantLastVal))
  67     assert((VTy->isFirstClassType() || VTy->isVoidTy()) &&
  68            "Cannot create non-first-class values except for constants!");
  69   static_assert(sizeof(Value) == 2 * sizeof(void *) + 2 * sizeof(unsigned),
  70                 "Value too big");
  71 }
  72
  73 Value::~Value() {
  74   // Notify all ValueHandles (if present) that this value is going away.
  75   if (HasValueHandle)
  76     ValueHandleBase::ValueIsDeleted(this);
  77   if (isUsedByMetadata())
  78     ValueAsMetadata::handleDeletion(this);
  79
  80 #ifndef NDEBUG      // Only in -g mode...
  81   // Check to make sure that there are no uses of this value that are still
  82   // around when the value is destroyed.  If there are, then we have a dangling
  83   // reference and something is wrong.  This code is here to print out where
  84   // the value is still being referenced.
  85   //
  86   // Note that use_empty() cannot be called here, as it eventually downcasts
  87   // 'this' to GlobalValue (derived class of Value), but GlobalValue has already
  88   // been destructed, so accessing it is UB.
  89   //
  90   if (!materialized_use_empty()) {
  91     dbgs() << "While deleting: " << *VTy << " %" << getName() << "\n";
  92     for (auto *U : users())
  93       dbgs() << "Use still stuck around after Def is destroyed:" << *U << "\n";
  94   }
  95 #endif
  96   assert(materialized_use_empty() && "Uses remain when a value is destroyed!");
  97
  98   // If this value is named, destroy the name.  This should not be in a symtab
  99   // at this point.
 100   destroyValueName();
 101 }
 102
 103 void Value::deleteValue() {
 104   switch (getValueID()) {
 105 #define HANDLE_VALUE(Name)                                                     \
 106   case Value::Name##Val:                                                       \
 107     delete static_cast<Name *>(this);                                          \
 108     break;
 109 #define HANDLE_MEMORY_VALUE(Name)                                              \
 110   case Value::Name##Val:                                                       \
 111     static_cast<DerivedUser *>(this)->DeleteValue(                             \
 112         static_cast<DerivedUser *>(this));                                     \
 113     break;
 114 #define HANDLE_CONSTANT(Name)                                                  \
 115   case Value::Name##Val:                                                       \
 116     llvm_unreachable("constants should be destroyed with destroyConstant");    \
 117     break;
 118 #define HANDLE_INSTRUCTION(Name)  /* nothing */
 119 #include "llvm/IR/Value.def"
 120
 121 #define HANDLE_INST(N, OPC, CLASS)                                             \
 122   case Value::InstructionVal + Instruction::OPC:                               \
 123     delete static_cast<CLASS *>(this);                                         \
 124     break;
 125 #define HANDLE_USER_INST(N, OPC, CLASS)
 126 #include "llvm/IR/Instruction.def"
 127
 128   default:
 129     llvm_unreachable("attempting to delete unknown value kind");
 130   }
 131 }
 132
 133 void Value::destroyValueName() {
 134   ValueName *Name = getValueName();
 135   if (Name) {
 136     MallocAllocator Allocator;
 137     Name->Destroy(Allocator);
 138   }
 139   setValueName(nullptr);
 140 }
 141
 142 bool Value::hasNUses(unsigned N) const {
 143   return hasNItems(use_begin(), use_end(), N);
 144 }
 145
 146 bool Value::hasNUsesOrMore(unsigned N) const {
 147   return hasNItemsOrMore(use_begin(), use_end(), N);
 148 }
 149
 150 static bool isUnDroppableUser(const User *U) { return !U->isDroppable(); }
 151
 152 Use *Value::getSingleUndroppableUse() {
 153   Use *Result = nullptr;
 154   for (Use &U : uses()) {
 155     if (!U.getUser()->isDroppable()) {
 156       if (Result)
 157         return nullptr;
 158       Result = &U;
 159     }
 160   }
 161   return Result;
 162 }
 163
 164 bool Value::hasNUndroppableUses(unsigned int N) const {
 165   return hasNItems(user_begin(), user_end(), N, isUnDroppableUser);
 166 }
 167
 168 bool Value::hasNUndroppableUsesOrMore(unsigned int N) const {
 169   return hasNItemsOrMore(user_begin(), user_end(), N, isUnDroppableUser);
 170 }
 171
 172 void Value::dropDroppableUses(
 173     llvm::function_ref<bool(const Use *)> ShouldDrop) {
 174   SmallVector<Use *, 8> ToBeEdited;
 175   for (Use &U : uses())
 176     if (U.getUser()->isDroppable() && ShouldDrop(&U))
 177       ToBeEdited.push_back(&U);
 178   for (Use *U : ToBeEdited) {
 179     U->removeFromList();
 180     if (auto *Assume = dyn_cast<IntrinsicInst>(U->getUser())) {
 181       assert(Assume->getIntrinsicID() == Intrinsic::assume);
 182       unsigned OpNo = U->getOperandNo();
 183       if (OpNo == 0)
 184         Assume->setOperand(0, ConstantInt::getTrue(Assume->getContext()));
 185       else {
 186         Assume->setOperand(OpNo, UndefValue::get(U->get()->getType()));
 187         CallInst::BundleOpInfo &BOI = Assume->getBundleOpInfoForOperand(OpNo);
 188         BOI.Tag = getContext().pImpl->getOrInsertBundleTag("ignore");
 189       }
 190     } else
 191       llvm_unreachable("unkown droppable use");
 192   }
 193 }
 194
 195 bool Value::isUsedInBasicBlock(const BasicBlock *BB) const {
 196   // This can be computed either by scanning the instructions in BB, or by
 197   // scanning the use list of this Value. Both lists can be very long, but
 198   // usually one is quite short.
 199   //
 200   // Scan both lists simultaneously until one is exhausted. This limits the
 201   // search to the shorter list.
 202   BasicBlock::const_iterator BI = BB->begin(), BE = BB->end();
 203   const_user_iterator UI = user_begin(), UE = user_end();
 204   for (; BI != BE && UI != UE; ++BI, ++UI) {
 205     // Scan basic block: Check if this Value is used by the instruction at BI.
 206     if (is_contained(BI->operands(), this))
 207       return true;
 208     // Scan use list: Check if the use at UI is in BB.
 209     const auto *User = dyn_cast<Instruction>(*UI);
 210     if (User && User->getParent() == BB)
 211       return true;
 212   }
 213   return false;
 214 }
 215
 216 unsigned Value::getNumUses() const {
 217   return (unsigned)std::distance(use_begin(), use_end());
 218 }
 219
 220 static bool getSymTab(Value *V, ValueSymbolTable *&ST) {
 221   ST = nullptr;
 222   if (Instruction *I = dyn_cast<Instruction>(V)) {
 223     if (BasicBlock *P = I->getParent())
 224       if (Function *PP = P->getParent())
 225         ST = PP->getValueSymbolTable();
 226   } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
 227     if (Function *P = BB->getParent())
 228       ST = P->getValueSymbolTable();
 229   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 230     if (Module *P = GV->getParent())
 231       ST = &P->getValueSymbolTable();
 232   } else if (Argument *A = dyn_cast<Argument>(V)) {
 233     if (Function *P = A->getParent())
 234       ST = P->getValueSymbolTable();
 235   } else {
 236     assert(isa<Constant>(V) && "Unknown value type!");
 237     return true;  // no name is setable for this.
 238   }
 239   return false;
 240 }
 241
 242 ValueName *Value::getValueName() const {
 243   if (!HasName) return nullptr;
 244
 245   LLVMContext &Ctx = getContext();
 246   auto I = Ctx.pImpl->ValueNames.find(this);
 247   assert(I != Ctx.pImpl->ValueNames.end() &&
 248          "No name entry found!");
 249
 250   return I->second;
 251 }
 252
 253 void Value::setValueName(ValueName *VN) {
 254   LLVMContext &Ctx = getContext();
 255
 256   assert(HasName == Ctx.pImpl->ValueNames.count(this) &&
 257          "HasName bit out of sync!");
 258
 259   if (!VN) {
 260     if (HasName)
 261       Ctx.pImpl->ValueNames.erase(this);
 262     HasName = false;
 263     return;
 264   }
 265
 266   HasName = true;
 267   Ctx.pImpl->ValueNames[this] = VN;
 268 }
 269
 270 StringRef Value::getName() const {
 271   // Make sure the empty string is still a C string. For historical reasons,
 272   // some clients want to call .data() on the result and expect it to be null
 273   // terminated.
 274   if (!hasName())
 275     return StringRef("", 0);
 276   return getValueName()->getKey();
 277 }
 278
 279 void Value::setNameImpl(const Twine &NewName) {
 280   // Fast-path: LLVMContext can be set to strip out non-GlobalValue names
 281   if (getContext().shouldDiscardValueNames() && !isa<GlobalValue>(this))
 282     return;
 283
 284   // Fast path for common IRBuilder case of setName("") when there is no name.
 285   if (NewName.isTriviallyEmpty() && !hasName())
 286     return;
 287
 288   SmallString<256> NameData;
 289   StringRef NameRef = NewName.toStringRef(NameData);
 290   assert(NameRef.find_first_of(0) == StringRef::npos &&
 291          "Null bytes are not allowed in names");
 292
 293   // Name isn't changing?
 294   if (getName() == NameRef)
 295     return;
 296
 297   // Cap the size of non-GlobalValue names.
 298   if (NameRef.size() > NonGlobalValueMaxNameSize && !isa<GlobalValue>(this))
 299     NameRef =
 300         NameRef.substr(0, std::max(1u, (unsigned)NonGlobalValueMaxNameSize));
 301
 302   assert(!getType()->isVoidTy() && "Cannot assign a name to void values!");
 303
 304   // Get the symbol table to update for this object.
 305   ValueSymbolTable *ST;
 306   if (getSymTab(this, ST))
 307     return;  // Cannot set a name on this value (e.g. constant).
 308
 309   if (!ST) { // No symbol table to update?  Just do the change.
 310     if (NameRef.empty()) {
 311       // Free the name for this value.
 312       destroyValueName();
 313       return;
 314     }
 315
 316     // NOTE: Could optimize for the case the name is shrinking to not deallocate
 317     // then reallocated.
 318     destroyValueName();
 319
 320     // Create the new name.
 321     MallocAllocator Allocator;
 322     setValueName(ValueName::Create(NameRef, Allocator));
 323     getValueName()->setValue(this);
 324     return;
 325   }
 326
 327   // NOTE: Could optimize for the case the name is shrinking to not deallocate
 328   // then reallocated.
 329   if (hasName()) {
 330     // Remove old name.
 331     ST->removeValueName(getValueName());
 332     destroyValueName();
 333
 334     if (NameRef.empty())
 335       return;
 336   }
 337
 338   // Name is changing to something new.
 339   setValueName(ST->createValueName(NameRef, this));
 340 }
 341
 342 void Value::setName(const Twine &NewName) {
 343   setNameImpl(NewName);
 344   if (Function *F = dyn_cast<Function>(this))
 345     F->recalculateIntrinsicID();
 346 }
 347
 348 void Value::takeName(Value *V) {
 349   ValueSymbolTable *ST = nullptr;
 350   // If this value has a name, drop it.
 351   if (hasName()) {
 352     // Get the symtab this is in.
 353     if (getSymTab(this, ST)) {
 354       // We can't set a name on this value, but we need to clear V's name if
 355       // it has one.
 356       if (V->hasName()) V->setName("");
 357       return;  // Cannot set a name on this value (e.g. constant).
 358     }
 359
 360     // Remove old name.
 361     if (ST)
 362       ST->removeValueName(getValueName());
 363     destroyValueName();
 364   }
 365
 366   // Now we know that this has no name.
 367
 368   // If V has no name either, we're done.
 369   if (!V->hasName()) return;
 370
 371   // Get this's symtab if we didn't before.
 372   if (!ST) {
 373     if (getSymTab(this, ST)) {
 374       // Clear V's name.
 375       V->setName("");
 376       return;  // Cannot set a name on this value (e.g. constant).
 377     }
 378   }
 379
 380   // Get V's ST, this should always succed, because V has a name.
 381   ValueSymbolTable *VST;
 382   bool Failure = getSymTab(V, VST);
 383   assert(!Failure && "V has a name, so it should have a ST!"); (void)Failure;
 384
 385   // If these values are both in the same symtab, we can do this very fast.
 386   // This works even if both values have no symtab yet.
 387   if (ST == VST) {
 388     // Take the name!
 389     setValueName(V->getValueName());
 390     V->setValueName(nullptr);
 391     getValueName()->setValue(this);
 392     return;
 393   }
 394
 395   // Otherwise, things are slightly more complex.  Remove V's name from VST and
 396   // then reinsert it into ST.
 397
 398   if (VST)
 399     VST->removeValueName(V->getValueName());
 400   setValueName(V->getValueName());
 401   V->setValueName(nullptr);
 402   getValueName()->setValue(this);
 403
 404   if (ST)
 405     ST->reinsertValue(this);
 406 }
 407
 408 void Value::assertModuleIsMaterializedImpl() const {
 409 #ifndef NDEBUG
 410   const GlobalValue *GV = dyn_cast<GlobalValue>(this);
 411   if (!GV)
 412     return;
 413   const Module *M = GV->getParent();
 414   if (!M)
 415     return;
 416   assert(M->isMaterialized());
 417 #endif
 418 }
 419
 420 #ifndef NDEBUG
 421 static bool contains(SmallPtrSetImpl<ConstantExpr *> &Cache, ConstantExpr *Expr,
 422                      Constant *C) {
 423   if (!Cache.insert(Expr).second)
 424     return false;
 425
 426   for (auto &O : Expr->operands()) {
 427     if (O == C)
 428       return true;
 429     auto *CE = dyn_cast<ConstantExpr>(O);
 430     if (!CE)
 431       continue;
 432     if (contains(Cache, CE, C))
 433       return true;
 434   }
 435   return false;
 436 }
 437
 438 static bool contains(Value *Expr, Value *V) {
 439   if (Expr == V)
 440     return true;
 441
 442   auto *C = dyn_cast<Constant>(V);
 443   if (!C)
 444     return false;
 445
 446   auto *CE = dyn_cast<ConstantExpr>(Expr);
 447   if (!CE)
 448     return false;
 449
 450   SmallPtrSet<ConstantExpr *, 4> Cache;
 451   return contains(Cache, CE, C);
 452 }
 453 #endif // NDEBUG
 454
 455 void Value::doRAUW(Value *New, ReplaceMetadataUses ReplaceMetaUses) {
 456   assert(New && "Value::replaceAllUsesWith(<null>) is invalid!");
 457   assert(!contains(New, this) &&
 458          "this->replaceAllUsesWith(expr(this)) is NOT valid!");
 459   assert(New->getType() == getType() &&
 460          "replaceAllUses of value with new value of different type!");
 461
 462   // Notify all ValueHandles (if present) that this value is going away.
 463   if (HasValueHandle)
 464     ValueHandleBase::ValueIsRAUWd(this, New);
 465   if (ReplaceMetaUses == ReplaceMetadataUses::Yes && isUsedByMetadata())
 466     ValueAsMetadata::handleRAUW(this, New);
 467
 468   while (!materialized_use_empty()) {
 469     Use &U = *UseList;
 470     // Must handle Constants specially, we cannot call replaceUsesOfWith on a
 471     // constant because they are uniqued.
 472     if (auto *C = dyn_cast<Constant>(U.getUser())) {
 473       if (!isa<GlobalValue>(C)) {
 474         C->handleOperandChange(this, New);
 475         continue;
 476       }
 477     }
 478
 479     U.set(New);
 480   }
 481
 482   if (BasicBlock *BB = dyn_cast<BasicBlock>(this))
 483     BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New));
 484 }
 485
 486 void Value::replaceAllUsesWith(Value *New) {
 487   doRAUW(New, ReplaceMetadataUses::Yes);
 488 }
 489
 490 void Value::replaceNonMetadataUsesWith(Value *New) {
 491   doRAUW(New, ReplaceMetadataUses::No);
 492 }
 493
 494 // Like replaceAllUsesWith except it does not handle constants or basic blocks.
 495 // This routine leaves uses within BB.
 496 void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) {
 497   assert(New && "Value::replaceUsesOutsideBlock(<null>, BB) is invalid!");
 498   assert(!contains(New, this) &&
 499          "this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!");
 500   assert(New->getType() == getType() &&
 501          "replaceUses of value with new value of different type!");
 502   assert(BB && "Basic block that may contain a use of 'New' must be defined\n");
 503
 504   replaceUsesWithIf(New, [BB](Use &U) {
 505     auto *I = dyn_cast<Instruction>(U.getUser());
 506     // Don't replace if it's an instruction in the BB basic block.
 507     return !I || I->getParent() != BB;
 508   });
 509 }
 510
 511 namespace {
 512 // Various metrics for how much to strip off of pointers.
 513 enum PointerStripKind {
 514   PSK_ZeroIndices,
 515   PSK_ZeroIndicesAndAliases,
 516   PSK_ZeroIndicesSameRepresentation,
 517   PSK_ZeroIndicesAndInvariantGroups,
 518   PSK_InBoundsConstantIndices,
 519   PSK_InBounds
 520 };
 521
 522 template <PointerStripKind StripKind> static void NoopCallback(const Value *) {}
 523
 524 template <PointerStripKind StripKind>
 525 static const Value *stripPointerCastsAndOffsets(
 526     const Value *V,
 527     function_ref<void(const Value *)> Func = NoopCallback<StripKind>) {
 528   if (!V->getType()->isPointerTy())
 529     return V;
 530
 531   // Even though we don't look through PHI nodes, we could be called on an
 532   // instruction in an unreachable block, which may be on a cycle.
 533   SmallPtrSet<const Value *, 4> Visited;
 534
 535   Visited.insert(V);
 536   do {
 537     Func(V);
 538     if (auto *GEP = dyn_cast<GEPOperator>(V)) {
 539       switch (StripKind) {
 540       case PSK_ZeroIndices:
 541       case PSK_ZeroIndicesAndAliases:
 542       case PSK_ZeroIndicesSameRepresentation:
 543       case PSK_ZeroIndicesAndInvariantGroups:
 544         if (!GEP->hasAllZeroIndices())
 545           return V;
 546         break;
 547       case PSK_InBoundsConstantIndices:
 548         if (!GEP->hasAllConstantIndices())
 549           return V;
 550         LLVM_FALLTHROUGH;
 551       case PSK_InBounds:
 552         if (!GEP->isInBounds())
 553           return V;
 554         break;
 555       }
 556       V = GEP->getPointerOperand();
 557     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
 558       V = cast<Operator>(V)->getOperand(0);
 559       if (!V->getType()->isPointerTy())
 560         return V;
 561     } else if (StripKind != PSK_ZeroIndicesSameRepresentation &&
 562                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
 563       // TODO: If we know an address space cast will not change the
 564       //       representation we could look through it here as well.
 565       V = cast<Operator>(V)->getOperand(0);
 566     } else if (StripKind == PSK_ZeroIndicesAndAliases && isa<GlobalAlias>(V)) {
 567       V = cast<GlobalAlias>(V)->getAliasee();
 568     } else {
 569       if (const auto *Call = dyn_cast<CallBase>(V)) {
 570         if (const Value *RV = Call->getReturnedArgOperand()) {
 571           V = RV;
 572           continue;
 573         }
 574         // The result of launder.invariant.group must alias it's argument,
 575         // but it can't be marked with returned attribute, that's why it needs
 576         // special case.
 577         if (StripKind == PSK_ZeroIndicesAndInvariantGroups &&
 578             (Call->getIntrinsicID() == Intrinsic::launder_invariant_group ||
 579              Call->getIntrinsicID() == Intrinsic::strip_invariant_group)) {
 580           V = Call->getArgOperand(0);
 581           continue;
 582         }
 583       }
 584       return V;
 585     }
 586     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
 587   } while (Visited.insert(V).second);
 588
 589   return V;
 590 }
 591 } // end anonymous namespace
 592
 593 const Value *Value::stripPointerCasts() const {
 594   return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this);
 595 }
 596
 597 const Value *Value::stripPointerCastsAndAliases() const {
 598   return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this);
 599 }
 600
 601 const Value *Value::stripPointerCastsSameRepresentation() const {
 602   return stripPointerCastsAndOffsets<PSK_ZeroIndicesSameRepresentation>(this);
 603 }
 604
 605 const Value *Value::stripInBoundsConstantOffsets() const {
 606   return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
 607 }
 608
 609 const Value *Value::stripPointerCastsAndInvariantGroups() const {
 610   return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndInvariantGroups>(this);
 611 }
 612
 613 const Value *Value::stripAndAccumulateConstantOffsets(
 614     const DataLayout &DL, APInt &Offset, bool AllowNonInbounds,
 615     function_ref<bool(Value &, APInt &)> ExternalAnalysis) const {
 616   if (!getType()->isPtrOrPtrVectorTy())
 617     return this;
 618
 619   unsigned BitWidth = Offset.getBitWidth();
 620   assert(BitWidth == DL.getIndexTypeSizeInBits(getType()) &&
 621          "The offset bit width does not match the DL specification.");
 622
 623   // Even though we don't look through PHI nodes, we could be called on an
 624   // instruction in an unreachable block, which may be on a cycle.
 625   SmallPtrSet<const Value *, 4> Visited;
 626   Visited.insert(this);
 627   const Value *V = this;
 628   do {
 629     if (auto *GEP = dyn_cast<GEPOperator>(V)) {
 630       // If in-bounds was requested, we do not strip non-in-bounds GEPs.
 631       if (!AllowNonInbounds && !GEP->isInBounds())
 632         return V;
 633
 634       // If one of the values we have visited is an addrspacecast, then
 635       // the pointer type of this GEP may be different from the type
 636       // of the Ptr parameter which was passed to this function.  This
 637       // means when we construct GEPOffset, we need to use the size
 638       // of GEP's pointer type rather than the size of the original
 639       // pointer type.
 640       APInt GEPOffset(DL.getIndexTypeSizeInBits(V->getType()), 0);
 641       if (!GEP->accumulateConstantOffset(DL, GEPOffset, ExternalAnalysis))
 642         return V;
 643
 644       // Stop traversal if the pointer offset wouldn't fit in the bit-width
 645       // provided by the Offset argument. This can happen due to AddrSpaceCast
 646       // stripping.
 647       if (GEPOffset.getMinSignedBits() > BitWidth)
 648         return V;
 649
 650       // External Analysis can return a result higher/lower than the value
 651       // represents. We need to detect overflow/underflow.
 652       APInt GEPOffsetST = GEPOffset.sextOrTrunc(BitWidth);
 653       if (!ExternalAnalysis) {
 654         Offset += GEPOffsetST;
 655       } else {
 656         bool Overflow = false;
 657         APInt OldOffset = Offset;
 658         Offset = Offset.sadd_ov(GEPOffsetST, Overflow);
 659         if (Overflow) {
 660           Offset = OldOffset;
 661           return V;
 662         }
 663       }
 664       V = GEP->getPointerOperand();
 665     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
 666                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
 667       V = cast<Operator>(V)->getOperand(0);
 668     } else if (auto *GA = dyn_cast<GlobalAlias>(V)) {
 669       if (!GA->isInterposable())
 670         V = GA->getAliasee();
 671     } else if (const auto *Call = dyn_cast<CallBase>(V)) {
 672         if (const Value *RV = Call->getReturnedArgOperand())
 673           V = RV;
 674     }
 675     assert(V->getType()->isPtrOrPtrVectorTy() && "Unexpected operand type!");
 676   } while (Visited.insert(V).second);
 677
 678   return V;
 679 }
 680
 681 const Value *
 682 Value::stripInBoundsOffsets(function_ref<void(const Value *)> Func) const {
 683   return stripPointerCastsAndOffsets<PSK_InBounds>(this, Func);
 684 }
 685
 686 uint64_t Value::getPointerDereferenceableBytes(const DataLayout &DL,
 687                                                bool &CanBeNull) const {
 688   assert(getType()->isPointerTy() && "must be pointer");
 689
 690   uint64_t DerefBytes = 0;
 691   CanBeNull = false;
 692   if (const Argument *A = dyn_cast<Argument>(this)) {
 693     DerefBytes = A->getDereferenceableBytes();
 694     if (DerefBytes == 0 && (A->hasByValAttr() || A->hasStructRetAttr())) {
 695       Type *PT = cast<PointerType>(A->getType())->getElementType();
 696       if (PT->isSized())
 697         DerefBytes = DL.getTypeStoreSize(PT).getKnownMinSize();
 698     }
 699     if (DerefBytes == 0) {
 700       DerefBytes = A->getDereferenceableOrNullBytes();
 701       CanBeNull = true;
 702     }
 703   } else if (const auto *Call = dyn_cast<CallBase>(this)) {
 704     DerefBytes = Call->getDereferenceableBytes(AttributeList::ReturnIndex);
 705     if (DerefBytes == 0) {
 706       DerefBytes =
 707           Call->getDereferenceableOrNullBytes(AttributeList::ReturnIndex);
 708       CanBeNull = true;
 709     }
 710   } else if (const LoadInst *LI = dyn_cast<LoadInst>(this)) {
 711     if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) {
 712       ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
 713       DerefBytes = CI->getLimitedValue();
 714     }
 715     if (DerefBytes == 0) {
 716       if (MDNode *MD =
 717               LI->getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
 718         ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
 719         DerefBytes = CI->getLimitedValue();
 720       }
 721       CanBeNull = true;
 722     }
 723   } else if (auto *IP = dyn_cast<IntToPtrInst>(this)) {
 724     if (MDNode *MD = IP->getMetadata(LLVMContext::MD_dereferenceable)) {
 725       ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
 726       DerefBytes = CI->getLimitedValue();
 727     }
 728     if (DerefBytes == 0) {
 729       if (MDNode *MD =
 730               IP->getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
 731         ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
 732         DerefBytes = CI->getLimitedValue();
 733       }
 734       CanBeNull = true;
 735     }
 736   } else if (auto *AI = dyn_cast<AllocaInst>(this)) {
 737     if (!AI->isArrayAllocation()) {
 738       DerefBytes =
 739           DL.getTypeStoreSize(AI->getAllocatedType()).getKnownMinSize();
 740       CanBeNull = false;
 741     }
 742   } else if (auto *GV = dyn_cast<GlobalVariable>(this)) {
 743     if (GV->getValueType()->isSized() && !GV->hasExternalWeakLinkage()) {
 744       // TODO: Don't outright reject hasExternalWeakLinkage but set the
 745       // CanBeNull flag.
 746       DerefBytes = DL.getTypeStoreSize(GV->getValueType()).getFixedSize();
 747       CanBeNull = false;
 748     }
 749   }
 750   return DerefBytes;
 751 }
 752
 753 Align Value::getPointerAlignment(const DataLayout &DL) const {
 754   assert(getType()->isPointerTy() && "must be pointer");
 755   if (auto *GO = dyn_cast<GlobalObject>(this)) {
 756     if (isa<Function>(GO)) {
 757       Align FunctionPtrAlign = DL.getFunctionPtrAlign().valueOrOne();
 758       switch (DL.getFunctionPtrAlignType()) {
 759       case DataLayout::FunctionPtrAlignType::Independent:
 760         return FunctionPtrAlign;
 761       case DataLayout::FunctionPtrAlignType::MultipleOfFunctionAlign:
 762         return std::max(FunctionPtrAlign, GO->getAlign().valueOrOne());
 763       }
 764       llvm_unreachable("Unhandled FunctionPtrAlignType");
 765     }
 766     const MaybeAlign Alignment(GO->getAlignment());
 767     if (!Alignment) {
 768       if (auto *GVar = dyn_cast<GlobalVariable>(GO)) {
 769         Type *ObjectType = GVar->getValueType();
 770         if (ObjectType->isSized()) {
 771           // If the object is defined in the current Module, we'll be giving
 772           // it the preferred alignment. Otherwise, we have to assume that it
 773           // may only have the minimum ABI alignment.
 774           if (GVar->isStrongDefinitionForLinker())
 775             return DL.getPreferredAlign(GVar);
 776           else
 777             return DL.getABITypeAlign(ObjectType);
 778         }
 779       }
 780     }
 781     return Alignment.valueOrOne();
 782   } else if (const Argument *A = dyn_cast<Argument>(this)) {
 783     const MaybeAlign Alignment = A->getParamAlign();
 784     if (!Alignment && A->hasStructRetAttr()) {
 785       // An sret parameter has at least the ABI alignment of the return type.
 786       Type *EltTy = cast<PointerType>(A->getType())->getElementType();
 787       if (EltTy->isSized())
 788         return DL.getABITypeAlign(EltTy);
 789     }
 790     return Alignment.valueOrOne();
 791   } else if (const AllocaInst *AI = dyn_cast<AllocaInst>(this)) {
 792     return AI->getAlign();
 793   } else if (const auto *Call = dyn_cast<CallBase>(this)) {
 794     MaybeAlign Alignment = Call->getRetAlign();
 795     if (!Alignment && Call->getCalledFunction())
 796       Alignment = Call->getCalledFunction()->getAttributes().getRetAlignment();
 797     return Alignment.valueOrOne();
 798   } else if (const LoadInst *LI = dyn_cast<LoadInst>(this)) {
 799     if (MDNode *MD = LI->getMetadata(LLVMContext::MD_align)) {
 800       ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
 801       return Align(CI->getLimitedValue());
 802     }
 803   } else if (auto *CstPtr = dyn_cast<Constant>(this)) {
 804     if (auto *CstInt = dyn_cast_or_null<ConstantInt>(ConstantExpr::getPtrToInt(
 805             const_cast<Constant *>(CstPtr), DL.getIntPtrType(getType()),
 806             /*OnlyIfReduced=*/true))) {
 807       size_t TrailingZeros = CstInt->getValue().countTrailingZeros();
 808       // While the actual alignment may be large, elsewhere we have
 809       // an arbitrary upper alignmet limit, so let's clamp to it.
 810       return Align(TrailingZeros < Value::MaxAlignmentExponent
 811                        ? uint64_t(1) << TrailingZeros
 812                        : Value::MaximumAlignment);
 813     }
 814   }
 815   return Align(1);
 816 }
 817
 818 const Value *Value::DoPHITranslation(const BasicBlock *CurBB,
 819                                      const BasicBlock *PredBB) const {
 820   auto *PN = dyn_cast<PHINode>(this);
 821   if (PN && PN->getParent() == CurBB)
 822     return PN->getIncomingValueForBlock(PredBB);
 823   return this;
 824 }
 825
 826 LLVMContext &Value::getContext() const { return VTy->getContext(); }
 827
 828 void Value::reverseUseList() {
 829   if (!UseList || !UseList->Next)
 830     // No need to reverse 0 or 1 uses.
 831     return;
 832
 833   Use *Head = UseList;
 834   Use *Current = UseList->Next;
 835   Head->Next = nullptr;
 836   while (Current) {
 837     Use *Next = Current->Next;
 838     Current->Next = Head;
 839     Head->Prev = &Current->Next;
 840     Head = Current;
 841     Current = Next;
 842   }
 843   UseList = Head;
 844   Head->Prev = &UseList;
 845 }
 846
 847 bool Value::isSwiftError() const {
 848   auto *Arg = dyn_cast<Argument>(this);
 849   if (Arg)
 850     return Arg->hasSwiftErrorAttr();
 851   auto *Alloca = dyn_cast<AllocaInst>(this);
 852   if (!Alloca)
 853     return false;
 854   return Alloca->isSwiftError();
 855 }
 856
 857 //===----------------------------------------------------------------------===//
 858 //                             ValueHandleBase Class
 859 //===----------------------------------------------------------------------===//
 860
 861 void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) {
 862   assert(List && "Handle list is null?");
 863
 864   // Splice ourselves into the list.
 865   Next = *List;
 866   *List = this;
 867   setPrevPtr(List);
 868   if (Next) {
 869     Next->setPrevPtr(&Next);
 870     assert(getValPtr() == Next->getValPtr() && "Added to wrong list?");
 871   }
 872 }
 873
 874 void ValueHandleBase::AddToExistingUseListAfter(ValueHandleBase *List) {
 875   assert(List && "Must insert after existing node");
 876
 877   Next = List->Next;
 878   setPrevPtr(&List->Next);
 879   List->Next = this;
 880   if (Next)
 881     Next->setPrevPtr(&Next);
 882 }
 883
 884 void ValueHandleBase::AddToUseList() {
 885   assert(getValPtr() && "Null pointer doesn't have a use list!");
 886
 887   LLVMContextImpl *pImpl = getValPtr()->getContext().pImpl;
 888
 889   if (getValPtr()->HasValueHandle) {
 890     // If this value already has a ValueHandle, then it must be in the
 891     // ValueHandles map already.
 892     ValueHandleBase *&Entry = pImpl->ValueHandles[getValPtr()];
 893     assert(Entry && "Value doesn't have any handles?");
 894     AddToExistingUseList(&Entry);
 895     return;
 896   }
 897
 898   // Ok, it doesn't have any handles yet, so we must insert it into the
 899   // DenseMap.  However, doing this insertion could cause the DenseMap to
 900   // reallocate itself, which would invalidate all of the PrevP pointers that
 901   // point into the old table.  Handle this by checking for reallocation and
 902   // updating the stale pointers only if needed.
 903   DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles;
 904   const void *OldBucketPtr = Handles.getPointerIntoBucketsArray();
 905
 906   ValueHandleBase *&Entry = Handles[getValPtr()];
 907   assert(!Entry && "Value really did already have handles?");
 908   AddToExistingUseList(&Entry);
 909   getValPtr()->HasValueHandle = true;
 910
 911   // If reallocation didn't happen or if this was the first insertion, don't
 912   // walk the table.
 913   if (Handles.isPointerIntoBucketsArray(OldBucketPtr) ||
 914       Handles.size() == 1) {
 915     return;
 916   }
 917
 918   // Okay, reallocation did happen.  Fix the Prev Pointers.
 919   for (DenseMap<Value*, ValueHandleBase*>::iterator I = Handles.begin(),
 920        E = Handles.end(); I != E; ++I) {
 921     assert(I->second && I->first == I->second->getValPtr() &&
 922            "List invariant broken!");
 923     I->second->setPrevPtr(&I->second);
 924   }
 925 }
 926
 927 void ValueHandleBase::RemoveFromUseList() {
 928   assert(getValPtr() && getValPtr()->HasValueHandle &&
 929          "Pointer doesn't have a use list!");
 930
 931   // Unlink this from its use list.
 932   ValueHandleBase **PrevPtr = getPrevPtr();
 933   assert(*PrevPtr == this && "List invariant broken");
 934
 935   *PrevPtr = Next;
 936   if (Next) {
 937     assert(Next->getPrevPtr() == &Next && "List invariant broken");
 938     Next->setPrevPtr(PrevPtr);
 939     return;
 940   }
 941
 942   // If the Next pointer was null, then it is possible that this was the last
 943   // ValueHandle watching VP.  If so, delete its entry from the ValueHandles
 944   // map.
 945   LLVMContextImpl *pImpl = getValPtr()->getContext().pImpl;
 946   DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles;
 947   if (Handles.isPointerIntoBucketsArray(PrevPtr)) {
 948     Handles.erase(getValPtr());
 949     getValPtr()->HasValueHandle = false;
 950   }
 951 }
 952
 953 void ValueHandleBase::ValueIsDeleted(Value *V) {
 954   assert(V->HasValueHandle && "Should only be called if ValueHandles present");
 955
 956   // Get the linked list base, which is guaranteed to exist since the
 957   // HasValueHandle flag is set.
 958   LLVMContextImpl *pImpl = V->getContext().pImpl;
 959   ValueHandleBase *Entry = pImpl->ValueHandles[V];
 960   assert(Entry && "Value bit set but no entries exist");
 961
 962   // We use a local ValueHandleBase as an iterator so that ValueHandles can add
 963   // and remove themselves from the list without breaking our iteration.  This
 964   // is not really an AssertingVH; we just have to give ValueHandleBase a kind.
 965   // Note that we deliberately do not the support the case when dropping a value
 966   // handle results in a new value handle being permanently added to the list
 967   // (as might occur in theory for CallbackVH's): the new value handle will not
 968   // be processed and the checking code will mete out righteous punishment if
 969   // the handle is still present once we have finished processing all the other
 970   // value handles (it is fine to momentarily add then remove a value handle).
 971   for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) {
 972     Iterator.RemoveFromUseList();
 973     Iterator.AddToExistingUseListAfter(Entry);
 974     assert(Entry->Next == &Iterator && "Loop invariant broken.");
 975
 976     switch (Entry->getKind()) {
 977     case Assert:
 978       break;
 979     case Weak:
 980     case WeakTracking:
 981       // WeakTracking and Weak just go to null, which unlinks them
 982       // from the list.
 983       Entry->operator=(nullptr);
 984       break;
 985     case Callback:
 986       // Forward to the subclass's implementation.
 987       static_cast<CallbackVH*>(Entry)->deleted();
 988       break;
 989     }
 990   }
 991
 992   // All callbacks, weak references, and assertingVHs should be dropped by now.
 993   if (V->HasValueHandle) {
 994 #ifndef NDEBUG      // Only in +Asserts mode...
 995     dbgs() << "While deleting: " << *V->getType() << " %" << V->getName()
 996            << "\n";
 997     if (pImpl->ValueHandles[V]->getKind() == Assert)
 998       llvm_unreachable("An asserting value handle still pointed to this"
 999                        " value!");
1000
1001 #endif
1002     llvm_unreachable("All references to V were not removed?");
1003   }
1004 }
1005
1006 void ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) {
1007   assert(Old->HasValueHandle &&"Should only be called if ValueHandles present");
1008   assert(Old != New && "Changing value into itself!");
1009   assert(Old->getType() == New->getType() &&
1010          "replaceAllUses of value with new value of different type!");
1011
1012   // Get the linked list base, which is guaranteed to exist since the
1013   // HasValueHandle flag is set.
1014   LLVMContextImpl *pImpl = Old->getContext().pImpl;
1015   ValueHandleBase *Entry = pImpl->ValueHandles[Old];
1016
1017   assert(Entry && "Value bit set but no entries exist");
1018
1019   // We use a local ValueHandleBase as an iterator so that
1020   // ValueHandles can add and remove themselves from the list without
1021   // breaking our iteration.  This is not really an AssertingVH; we
1022   // just have to give ValueHandleBase some kind.
1023   for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) {
1024     Iterator.RemoveFromUseList();
1025     Iterator.AddToExistingUseListAfter(Entry);
1026     assert(Entry->Next == &Iterator && "Loop invariant broken.");
1027
1028     switch (Entry->getKind()) {
1029     case Assert:
1030     case Weak:
1031       // Asserting and Weak handles do not follow RAUW implicitly.
1032       break;
1033     case WeakTracking:
1034       // Weak goes to the new value, which will unlink it from Old's list.
1035       Entry->operator=(New);
1036       break;
1037     case Callback:
1038       // Forward to the subclass's implementation.
1039       static_cast<CallbackVH*>(Entry)->allUsesReplacedWith(New);
1040       break;
1041     }
1042   }
1043
1044 #ifndef NDEBUG
1045   // If any new weak value handles were added while processing the
1046   // list, then complain about it now.
1047   if (Old->HasValueHandle)
1048     for (Entry = pImpl->ValueHandles[Old]; Entry; Entry = Entry->Next)
1049       switch (Entry->getKind()) {
1050       case WeakTracking:
1051         dbgs() << "After RAUW from " << *Old->getType() << " %"
1052                << Old->getName() << " to " << *New->getType() << " %"
1053                << New->getName() << "\n";
1054         llvm_unreachable(
1055             "A weak tracking value handle still pointed to the old value!\n");
1056       default:
1057         break;
1058       }
1059 #endif
1060 }
1061
1062 // Pin the vtable to this file.
1063 void CallbackVH::anchor() {}