LCOV - code coverage report
Current view: top level - lib/IR - Value.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 304 313 97.1 %
Date: 2018-06-17 00:07:59 Functions: 44 46 95.7 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13