LLVM API Documentation

Value.cpp
Go to the documentation of this file.
00001 //===-- Value.cpp - Implement the Value class -----------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the Value, ValueHandle, and User classes.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/IR/Value.h"
00015 #include "LLVMContextImpl.h"
00016 #include "llvm/ADT/DenseMap.h"
00017 #include "llvm/ADT/SmallString.h"
00018 #include "llvm/IR/CallSite.h"
00019 #include "llvm/IR/Constant.h"
00020 #include "llvm/IR/Constants.h"
00021 #include "llvm/IR/DataLayout.h"
00022 #include "llvm/IR/DerivedTypes.h"
00023 #include "llvm/IR/GetElementPtrTypeIterator.h"
00024 #include "llvm/IR/InstrTypes.h"
00025 #include "llvm/IR/Instructions.h"
00026 #include "llvm/IR/Module.h"
00027 #include "llvm/IR/Operator.h"
00028 #include "llvm/IR/ValueHandle.h"
00029 #include "llvm/IR/ValueSymbolTable.h"
00030 #include "llvm/Support/Debug.h"
00031 #include "llvm/Support/ErrorHandling.h"
00032 #include "llvm/Support/ManagedStatic.h"
00033 #include <algorithm>
00034 using namespace llvm;
00035 
00036 //===----------------------------------------------------------------------===//
00037 //                                Value Class
00038 //===----------------------------------------------------------------------===//
00039 
00040 static inline Type *checkType(Type *Ty) {
00041   assert(Ty && "Value defined with a null type: Error!");
00042   return Ty;
00043 }
00044 
00045 Value::Value(Type *ty, unsigned scid)
00046     : VTy(checkType(ty)), UseList(nullptr), SubclassID(scid), HasValueHandle(0),
00047       SubclassOptionalData(0), SubclassData(0), NumOperands(0) {
00048   // FIXME: Why isn't this in the subclass gunk??
00049   // Note, we cannot call isa<CallInst> before the CallInst has been
00050   // constructed.
00051   if (SubclassID == Instruction::Call || SubclassID == Instruction::Invoke)
00052     assert((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) &&
00053            "invalid CallInst type!");
00054   else if (SubclassID != BasicBlockVal &&
00055            (SubclassID < ConstantFirstVal || SubclassID > ConstantLastVal))
00056     assert((VTy->isFirstClassType() || VTy->isVoidTy()) &&
00057            "Cannot create non-first-class values except for constants!");
00058 }
00059 
00060 Value::~Value() {
00061   // Notify all ValueHandles (if present) that this value is going away.
00062   if (HasValueHandle)
00063     ValueHandleBase::ValueIsDeleted(this);
00064   if (isUsedByMetadata())
00065     ValueAsMetadata::handleDeletion(this);
00066 
00067 #ifndef NDEBUG      // Only in -g mode...
00068   // Check to make sure that there are no uses of this value that are still
00069   // around when the value is destroyed.  If there are, then we have a dangling
00070   // reference and something is wrong.  This code is here to print out what is
00071   // still being referenced.  The value in question should be printed as
00072   // a <badref>
00073   //
00074   if (!use_empty()) {
00075     dbgs() << "While deleting: " << *VTy << " %" << getName() << "\n";
00076     for (use_iterator I = use_begin(), E = use_end(); I != E; ++I)
00077       dbgs() << "Use still stuck around after Def is destroyed:"
00078            << **I << "\n";
00079   }
00080 #endif
00081   assert(use_empty() && "Uses remain when a value is destroyed!");
00082 
00083   // If this value is named, destroy the name.  This should not be in a symtab
00084   // at this point.
00085   destroyValueName();
00086 }
00087 
00088 void Value::destroyValueName() {
00089   ValueName *Name = getValueName();
00090   if (Name)
00091     Name->Destroy();
00092   setValueName(nullptr);
00093 }
00094 
00095 bool Value::hasNUses(unsigned N) const {
00096   const_use_iterator UI = use_begin(), E = use_end();
00097 
00098   for (; N; --N, ++UI)
00099     if (UI == E) return false;  // Too few.
00100   return UI == E;
00101 }
00102 
00103 bool Value::hasNUsesOrMore(unsigned N) const {
00104   const_use_iterator UI = use_begin(), E = use_end();
00105 
00106   for (; N; --N, ++UI)
00107     if (UI == E) return false;  // Too few.
00108 
00109   return true;
00110 }
00111 
00112 bool Value::isUsedInBasicBlock(const BasicBlock *BB) const {
00113   // This can be computed either by scanning the instructions in BB, or by
00114   // scanning the use list of this Value. Both lists can be very long, but
00115   // usually one is quite short.
00116   //
00117   // Scan both lists simultaneously until one is exhausted. This limits the
00118   // search to the shorter list.
00119   BasicBlock::const_iterator BI = BB->begin(), BE = BB->end();
00120   const_user_iterator UI = user_begin(), UE = user_end();
00121   for (; BI != BE && UI != UE; ++BI, ++UI) {
00122     // Scan basic block: Check if this Value is used by the instruction at BI.
00123     if (std::find(BI->op_begin(), BI->op_end(), this) != BI->op_end())
00124       return true;
00125     // Scan use list: Check if the use at UI is in BB.
00126     const Instruction *User = dyn_cast<Instruction>(*UI);
00127     if (User && User->getParent() == BB)
00128       return true;
00129   }
00130   return false;
00131 }
00132 
00133 unsigned Value::getNumUses() const {
00134   return (unsigned)std::distance(use_begin(), use_end());
00135 }
00136 
00137 static bool getSymTab(Value *V, ValueSymbolTable *&ST) {
00138   ST = nullptr;
00139   if (Instruction *I = dyn_cast<Instruction>(V)) {
00140     if (BasicBlock *P = I->getParent())
00141       if (Function *PP = P->getParent())
00142         ST = &PP->getValueSymbolTable();
00143   } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
00144     if (Function *P = BB->getParent())
00145       ST = &P->getValueSymbolTable();
00146   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
00147     if (Module *P = GV->getParent())
00148       ST = &P->getValueSymbolTable();
00149   } else if (Argument *A = dyn_cast<Argument>(V)) {
00150     if (Function *P = A->getParent())
00151       ST = &P->getValueSymbolTable();
00152   } else {
00153     assert(isa<Constant>(V) && "Unknown value type!");
00154     return true;  // no name is setable for this.
00155   }
00156   return false;
00157 }
00158 
00159 StringRef Value::getName() const {
00160   // Make sure the empty string is still a C string. For historical reasons,
00161   // some clients want to call .data() on the result and expect it to be null
00162   // terminated.
00163   if (!getValueName())
00164     return StringRef("", 0);
00165   return getValueName()->getKey();
00166 }
00167 
00168 void Value::setName(const Twine &NewName) {
00169   // Fast path for common IRBuilder case of setName("") when there is no name.
00170   if (NewName.isTriviallyEmpty() && !hasName())
00171     return;
00172 
00173   SmallString<256> NameData;
00174   StringRef NameRef = NewName.toStringRef(NameData);
00175   assert(NameRef.find_first_of(0) == StringRef::npos &&
00176          "Null bytes are not allowed in names");
00177 
00178   // Name isn't changing?
00179   if (getName() == NameRef)
00180     return;
00181 
00182   assert(!getType()->isVoidTy() && "Cannot assign a name to void values!");
00183 
00184   // Get the symbol table to update for this object.
00185   ValueSymbolTable *ST;
00186   if (getSymTab(this, ST))
00187     return;  // Cannot set a name on this value (e.g. constant).
00188 
00189   if (Function *F = dyn_cast<Function>(this))
00190     getContext().pImpl->IntrinsicIDCache.erase(F);
00191 
00192   if (!ST) { // No symbol table to update?  Just do the change.
00193     if (NameRef.empty()) {
00194       // Free the name for this value.
00195       destroyValueName();
00196       return;
00197     }
00198 
00199     // NOTE: Could optimize for the case the name is shrinking to not deallocate
00200     // then reallocated.
00201     destroyValueName();
00202 
00203     // Create the new name.
00204     setValueName(ValueName::Create(NameRef));
00205     getValueName()->setValue(this);
00206     return;
00207   }
00208 
00209   // NOTE: Could optimize for the case the name is shrinking to not deallocate
00210   // then reallocated.
00211   if (hasName()) {
00212     // Remove old name.
00213     ST->removeValueName(getValueName());
00214     destroyValueName();
00215 
00216     if (NameRef.empty())
00217       return;
00218   }
00219 
00220   // Name is changing to something new.
00221   setValueName(ST->createValueName(NameRef, this));
00222 }
00223 
00224 void Value::takeName(Value *V) {
00225   ValueSymbolTable *ST = nullptr;
00226   // If this value has a name, drop it.
00227   if (hasName()) {
00228     // Get the symtab this is in.
00229     if (getSymTab(this, ST)) {
00230       // We can't set a name on this value, but we need to clear V's name if
00231       // it has one.
00232       if (V->hasName()) V->setName("");
00233       return;  // Cannot set a name on this value (e.g. constant).
00234     }
00235 
00236     // Remove old name.
00237     if (ST)
00238       ST->removeValueName(getValueName());
00239     destroyValueName();
00240   }
00241 
00242   // Now we know that this has no name.
00243 
00244   // If V has no name either, we're done.
00245   if (!V->hasName()) return;
00246 
00247   // Get this's symtab if we didn't before.
00248   if (!ST) {
00249     if (getSymTab(this, ST)) {
00250       // Clear V's name.
00251       V->setName("");
00252       return;  // Cannot set a name on this value (e.g. constant).
00253     }
00254   }
00255 
00256   // Get V's ST, this should always succed, because V has a name.
00257   ValueSymbolTable *VST;
00258   bool Failure = getSymTab(V, VST);
00259   assert(!Failure && "V has a name, so it should have a ST!"); (void)Failure;
00260 
00261   // If these values are both in the same symtab, we can do this very fast.
00262   // This works even if both values have no symtab yet.
00263   if (ST == VST) {
00264     // Take the name!
00265     setValueName(V->getValueName());
00266     V->setValueName(nullptr);
00267     getValueName()->setValue(this);
00268     return;
00269   }
00270 
00271   // Otherwise, things are slightly more complex.  Remove V's name from VST and
00272   // then reinsert it into ST.
00273 
00274   if (VST)
00275     VST->removeValueName(V->getValueName());
00276   setValueName(V->getValueName());
00277   V->setValueName(nullptr);
00278   getValueName()->setValue(this);
00279 
00280   if (ST)
00281     ST->reinsertValue(this);
00282 }
00283 
00284 #ifndef NDEBUG
00285 static bool contains(SmallPtrSetImpl<ConstantExpr *> &Cache, ConstantExpr *Expr,
00286                      Constant *C) {
00287   if (!Cache.insert(Expr).second)
00288     return false;
00289 
00290   for (auto &O : Expr->operands()) {
00291     if (O == C)
00292       return true;
00293     auto *CE = dyn_cast<ConstantExpr>(O);
00294     if (!CE)
00295       continue;
00296     if (contains(Cache, CE, C))
00297       return true;
00298   }
00299   return false;
00300 }
00301 
00302 static bool contains(Value *Expr, Value *V) {
00303   if (Expr == V)
00304     return true;
00305 
00306   auto *C = dyn_cast<Constant>(V);
00307   if (!C)
00308     return false;
00309 
00310   auto *CE = dyn_cast<ConstantExpr>(Expr);
00311   if (!CE)
00312     return false;
00313 
00314   SmallPtrSet<ConstantExpr *, 4> Cache;
00315   return contains(Cache, CE, C);
00316 }
00317 #endif
00318 
00319 void Value::replaceAllUsesWith(Value *New) {
00320   assert(New && "Value::replaceAllUsesWith(<null>) is invalid!");
00321   assert(!contains(New, this) &&
00322          "this->replaceAllUsesWith(expr(this)) is NOT valid!");
00323   assert(New->getType() == getType() &&
00324          "replaceAllUses of value with new value of different type!");
00325 
00326   // Notify all ValueHandles (if present) that this value is going away.
00327   if (HasValueHandle)
00328     ValueHandleBase::ValueIsRAUWd(this, New);
00329   if (isUsedByMetadata())
00330     ValueAsMetadata::handleRAUW(this, New);
00331 
00332   while (!use_empty()) {
00333     Use &U = *UseList;
00334     // Must handle Constants specially, we cannot call replaceUsesOfWith on a
00335     // constant because they are uniqued.
00336     if (auto *C = dyn_cast<Constant>(U.getUser())) {
00337       if (!isa<GlobalValue>(C)) {
00338         C->replaceUsesOfWithOnConstant(this, New, &U);
00339         continue;
00340       }
00341     }
00342 
00343     U.set(New);
00344   }
00345 
00346   if (BasicBlock *BB = dyn_cast<BasicBlock>(this))
00347     BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New));
00348 }
00349 
00350 // Like replaceAllUsesWith except it does not handle constants or basic blocks.
00351 // This routine leaves uses within BB.
00352 void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) {
00353   assert(New && "Value::replaceUsesOutsideBlock(<null>, BB) is invalid!");
00354   assert(!contains(New, this) &&
00355          "this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!");
00356   assert(New->getType() == getType() &&
00357          "replaceUses of value with new value of different type!");
00358   assert(BB && "Basic block that may contain a use of 'New' must be defined\n");
00359 
00360   use_iterator UI = use_begin(), E = use_end();
00361   for (; UI != E;) {
00362     Use &U = *UI;
00363     ++UI;
00364     auto *Usr = dyn_cast<Instruction>(U.getUser());
00365     if (Usr && Usr->getParent() == BB)
00366       continue;
00367     U.set(New);
00368   }
00369   return;
00370 }
00371 
00372 namespace {
00373 // Various metrics for how much to strip off of pointers.
00374 enum PointerStripKind {
00375   PSK_ZeroIndices,
00376   PSK_ZeroIndicesAndAliases,
00377   PSK_InBoundsConstantIndices,
00378   PSK_InBounds
00379 };
00380 
00381 template <PointerStripKind StripKind>
00382 static Value *stripPointerCastsAndOffsets(Value *V) {
00383   if (!V->getType()->isPointerTy())
00384     return V;
00385 
00386   // Even though we don't look through PHI nodes, we could be called on an
00387   // instruction in an unreachable block, which may be on a cycle.
00388   SmallPtrSet<Value *, 4> Visited;
00389 
00390   Visited.insert(V);
00391   do {
00392     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
00393       switch (StripKind) {
00394       case PSK_ZeroIndicesAndAliases:
00395       case PSK_ZeroIndices:
00396         if (!GEP->hasAllZeroIndices())
00397           return V;
00398         break;
00399       case PSK_InBoundsConstantIndices:
00400         if (!GEP->hasAllConstantIndices())
00401           return V;
00402         // fallthrough
00403       case PSK_InBounds:
00404         if (!GEP->isInBounds())
00405           return V;
00406         break;
00407       }
00408       V = GEP->getPointerOperand();
00409     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
00410                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
00411       V = cast<Operator>(V)->getOperand(0);
00412     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
00413       if (StripKind == PSK_ZeroIndices || GA->mayBeOverridden())
00414         return V;
00415       V = GA->getAliasee();
00416     } else {
00417       return V;
00418     }
00419     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
00420   } while (Visited.insert(V).second);
00421 
00422   return V;
00423 }
00424 } // namespace
00425 
00426 Value *Value::stripPointerCasts() {
00427   return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this);
00428 }
00429 
00430 Value *Value::stripPointerCastsNoFollowAliases() {
00431   return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this);
00432 }
00433 
00434 Value *Value::stripInBoundsConstantOffsets() {
00435   return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
00436 }
00437 
00438 Value *Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
00439                                                         APInt &Offset) {
00440   if (!getType()->isPointerTy())
00441     return this;
00442 
00443   assert(Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType>(
00444                                      getType())->getAddressSpace()) &&
00445          "The offset must have exactly as many bits as our pointer.");
00446 
00447   // Even though we don't look through PHI nodes, we could be called on an
00448   // instruction in an unreachable block, which may be on a cycle.
00449   SmallPtrSet<Value *, 4> Visited;
00450   Visited.insert(this);
00451   Value *V = this;
00452   do {
00453     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
00454       if (!GEP->isInBounds())
00455         return V;
00456       APInt GEPOffset(Offset);
00457       if (!GEP->accumulateConstantOffset(DL, GEPOffset))
00458         return V;
00459       Offset = GEPOffset;
00460       V = GEP->getPointerOperand();
00461     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
00462                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
00463       V = cast<Operator>(V)->getOperand(0);
00464     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
00465       V = GA->getAliasee();
00466     } else {
00467       return V;
00468     }
00469     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
00470   } while (Visited.insert(V).second);
00471 
00472   return V;
00473 }
00474 
00475 Value *Value::stripInBoundsOffsets() {
00476   return stripPointerCastsAndOffsets<PSK_InBounds>(this);
00477 }
00478 
00479 /// \brief Check if Value is always a dereferenceable pointer.
00480 ///
00481 /// Test if V is always a pointer to allocated and suitably aligned memory for
00482 /// a simple load or store.
00483 static bool isDereferenceablePointer(const Value *V, const DataLayout *DL,
00484                                      SmallPtrSetImpl<const Value *> &Visited) {
00485   // Note that it is not safe to speculate into a malloc'd region because
00486   // malloc may return null.
00487 
00488   // These are obviously ok.
00489   if (isa<AllocaInst>(V)) return true;
00490 
00491   // It's not always safe to follow a bitcast, for example:
00492   //   bitcast i8* (alloca i8) to i32*
00493   // would result in a 4-byte load from a 1-byte alloca. However,
00494   // if we're casting from a pointer from a type of larger size
00495   // to a type of smaller size (or the same size), and the alignment
00496   // is at least as large as for the resulting pointer type, then
00497   // we can look through the bitcast.
00498   if (DL)
00499     if (const BitCastInst* BC = dyn_cast<BitCastInst>(V)) {
00500       Type *STy = BC->getSrcTy()->getPointerElementType(),
00501            *DTy = BC->getDestTy()->getPointerElementType();
00502       if (STy->isSized() && DTy->isSized() &&
00503           (DL->getTypeStoreSize(STy) >=
00504            DL->getTypeStoreSize(DTy)) &&
00505           (DL->getABITypeAlignment(STy) >=
00506            DL->getABITypeAlignment(DTy)))
00507         return isDereferenceablePointer(BC->getOperand(0), DL, Visited);
00508     }
00509 
00510   // Global variables which can't collapse to null are ok.
00511   if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
00512     return !GV->hasExternalWeakLinkage();
00513 
00514   // byval arguments are okay. Arguments specifically marked as
00515   // dereferenceable are okay too.
00516   if (const Argument *A = dyn_cast<Argument>(V)) {
00517     if (A->hasByValAttr())
00518       return true;
00519     else if (uint64_t Bytes = A->getDereferenceableBytes()) {
00520       Type *Ty = V->getType()->getPointerElementType();
00521       if (Ty->isSized() && DL && DL->getTypeStoreSize(Ty) <= Bytes)
00522         return true;
00523     }
00524 
00525     return false;
00526   }
00527 
00528   // Return values from call sites specifically marked as dereferenceable are
00529   // also okay.
00530   if (ImmutableCallSite CS = V) {
00531     if (uint64_t Bytes = CS.getDereferenceableBytes(0)) {
00532       Type *Ty = V->getType()->getPointerElementType();
00533       if (Ty->isSized() && DL && DL->getTypeStoreSize(Ty) <= Bytes)
00534         return true;
00535     }
00536   }
00537 
00538   // For GEPs, determine if the indexing lands within the allocated object.
00539   if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
00540     // Conservatively require that the base pointer be fully dereferenceable.
00541     if (!Visited.insert(GEP->getOperand(0)).second)
00542       return false;
00543     if (!isDereferenceablePointer(GEP->getOperand(0), DL, Visited))
00544       return false;
00545     // Check the indices.
00546     gep_type_iterator GTI = gep_type_begin(GEP);
00547     for (User::const_op_iterator I = GEP->op_begin()+1,
00548          E = GEP->op_end(); I != E; ++I) {
00549       Value *Index = *I;
00550       Type *Ty = *GTI++;
00551       // Struct indices can't be out of bounds.
00552       if (isa<StructType>(Ty))
00553         continue;
00554       ConstantInt *CI = dyn_cast<ConstantInt>(Index);
00555       if (!CI)
00556         return false;
00557       // Zero is always ok.
00558       if (CI->isZero())
00559         continue;
00560       // Check to see that it's within the bounds of an array.
00561       ArrayType *ATy = dyn_cast<ArrayType>(Ty);
00562       if (!ATy)
00563         return false;
00564       if (CI->getValue().getActiveBits() > 64)
00565         return false;
00566       if (CI->getZExtValue() >= ATy->getNumElements())
00567         return false;
00568     }
00569     // Indices check out; this is dereferenceable.
00570     return true;
00571   }
00572 
00573   if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
00574     return isDereferenceablePointer(ASC->getOperand(0), DL, Visited);
00575 
00576   // If we don't know, assume the worst.
00577   return false;
00578 }
00579 
00580 bool Value::isDereferenceablePointer(const DataLayout *DL) const {
00581   // When dereferenceability information is provided by a dereferenceable
00582   // attribute, we know exactly how many bytes are dereferenceable. If we can
00583   // determine the exact offset to the attributed variable, we can use that
00584   // information here.
00585   Type *Ty = getType()->getPointerElementType();
00586   if (Ty->isSized() && DL) {
00587     APInt Offset(DL->getTypeStoreSizeInBits(getType()), 0);
00588     const Value *BV = stripAndAccumulateInBoundsConstantOffsets(*DL, Offset);
00589 
00590     APInt DerefBytes(Offset.getBitWidth(), 0);
00591     if (const Argument *A = dyn_cast<Argument>(BV))
00592       DerefBytes = A->getDereferenceableBytes();
00593     else if (ImmutableCallSite CS = BV)
00594       DerefBytes = CS.getDereferenceableBytes(0);
00595 
00596     if (DerefBytes.getBoolValue() && Offset.isNonNegative()) {
00597       if (DerefBytes.uge(Offset + DL->getTypeStoreSize(Ty)))
00598         return true;
00599     }
00600   }
00601 
00602   SmallPtrSet<const Value *, 32> Visited;
00603   return ::isDereferenceablePointer(this, DL, Visited);
00604 }
00605 
00606 Value *Value::DoPHITranslation(const BasicBlock *CurBB,
00607                                const BasicBlock *PredBB) {
00608   PHINode *PN = dyn_cast<PHINode>(this);
00609   if (PN && PN->getParent() == CurBB)
00610     return PN->getIncomingValueForBlock(PredBB);
00611   return this;
00612 }
00613 
00614 LLVMContext &Value::getContext() const { return VTy->getContext(); }
00615 
00616 void Value::reverseUseList() {
00617   if (!UseList || !UseList->Next)
00618     // No need to reverse 0 or 1 uses.
00619     return;
00620 
00621   Use *Head = UseList;
00622   Use *Current = UseList->Next;
00623   Head->Next = nullptr;
00624   while (Current) {
00625     Use *Next = Current->Next;
00626     Current->Next = Head;
00627     Head->setPrev(&Current->Next);
00628     Head = Current;
00629     Current = Next;
00630   }
00631   UseList = Head;
00632   Head->setPrev(&UseList);
00633 }
00634 
00635 //===----------------------------------------------------------------------===//
00636 //                             ValueHandleBase Class
00637 //===----------------------------------------------------------------------===//
00638 
00639 void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) {
00640   assert(List && "Handle list is null?");
00641 
00642   // Splice ourselves into the list.
00643   Next = *List;
00644   *List = this;
00645   setPrevPtr(List);
00646   if (Next) {
00647     Next->setPrevPtr(&Next);
00648     assert(V == Next->V && "Added to wrong list?");
00649   }
00650 }
00651 
00652 void ValueHandleBase::AddToExistingUseListAfter(ValueHandleBase *List) {
00653   assert(List && "Must insert after existing node");
00654 
00655   Next = List->Next;
00656   setPrevPtr(&List->Next);
00657   List->Next = this;
00658   if (Next)
00659     Next->setPrevPtr(&Next);
00660 }
00661 
00662 void ValueHandleBase::AddToUseList() {
00663   assert(V && "Null pointer doesn't have a use list!");
00664 
00665   LLVMContextImpl *pImpl = V->getContext().pImpl;
00666 
00667   if (V->HasValueHandle) {
00668     // If this value already has a ValueHandle, then it must be in the
00669     // ValueHandles map already.
00670     ValueHandleBase *&Entry = pImpl->ValueHandles[V];
00671     assert(Entry && "Value doesn't have any handles?");
00672     AddToExistingUseList(&Entry);
00673     return;
00674   }
00675 
00676   // Ok, it doesn't have any handles yet, so we must insert it into the
00677   // DenseMap.  However, doing this insertion could cause the DenseMap to
00678   // reallocate itself, which would invalidate all of the PrevP pointers that
00679   // point into the old table.  Handle this by checking for reallocation and
00680   // updating the stale pointers only if needed.
00681   DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles;
00682   const void *OldBucketPtr = Handles.getPointerIntoBucketsArray();
00683 
00684   ValueHandleBase *&Entry = Handles[V];
00685   assert(!Entry && "Value really did already have handles?");
00686   AddToExistingUseList(&Entry);
00687   V->HasValueHandle = true;
00688 
00689   // If reallocation didn't happen or if this was the first insertion, don't
00690   // walk the table.
00691   if (Handles.isPointerIntoBucketsArray(OldBucketPtr) ||
00692       Handles.size() == 1) {
00693     return;
00694   }
00695 
00696   // Okay, reallocation did happen.  Fix the Prev Pointers.
00697   for (DenseMap<Value*, ValueHandleBase*>::iterator I = Handles.begin(),
00698        E = Handles.end(); I != E; ++I) {
00699     assert(I->second && I->first == I->second->V &&
00700            "List invariant broken!");
00701     I->second->setPrevPtr(&I->second);
00702   }
00703 }
00704 
00705 void ValueHandleBase::RemoveFromUseList() {
00706   assert(V && V->HasValueHandle &&
00707          "Pointer doesn't have a use list!");
00708 
00709   // Unlink this from its use list.
00710   ValueHandleBase **PrevPtr = getPrevPtr();
00711   assert(*PrevPtr == this && "List invariant broken");
00712 
00713   *PrevPtr = Next;
00714   if (Next) {
00715     assert(Next->getPrevPtr() == &Next && "List invariant broken");
00716     Next->setPrevPtr(PrevPtr);
00717     return;
00718   }
00719 
00720   // If the Next pointer was null, then it is possible that this was the last
00721   // ValueHandle watching VP.  If so, delete its entry from the ValueHandles
00722   // map.
00723   LLVMContextImpl *pImpl = V->getContext().pImpl;
00724   DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles;
00725   if (Handles.isPointerIntoBucketsArray(PrevPtr)) {
00726     Handles.erase(V);
00727     V->HasValueHandle = false;
00728   }
00729 }
00730 
00731 
00732 void ValueHandleBase::ValueIsDeleted(Value *V) {
00733   assert(V->HasValueHandle && "Should only be called if ValueHandles present");
00734 
00735   // Get the linked list base, which is guaranteed to exist since the
00736   // HasValueHandle flag is set.
00737   LLVMContextImpl *pImpl = V->getContext().pImpl;
00738   ValueHandleBase *Entry = pImpl->ValueHandles[V];
00739   assert(Entry && "Value bit set but no entries exist");
00740 
00741   // We use a local ValueHandleBase as an iterator so that ValueHandles can add
00742   // and remove themselves from the list without breaking our iteration.  This
00743   // is not really an AssertingVH; we just have to give ValueHandleBase a kind.
00744   // Note that we deliberately do not the support the case when dropping a value
00745   // handle results in a new value handle being permanently added to the list
00746   // (as might occur in theory for CallbackVH's): the new value handle will not
00747   // be processed and the checking code will mete out righteous punishment if
00748   // the handle is still present once we have finished processing all the other
00749   // value handles (it is fine to momentarily add then remove a value handle).
00750   for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) {
00751     Iterator.RemoveFromUseList();
00752     Iterator.AddToExistingUseListAfter(Entry);
00753     assert(Entry->Next == &Iterator && "Loop invariant broken.");
00754 
00755     switch (Entry->getKind()) {
00756     case Assert:
00757       break;
00758     case Tracking:
00759       // Mark that this value has been deleted by setting it to an invalid Value
00760       // pointer.
00761       Entry->operator=(DenseMapInfo<Value *>::getTombstoneKey());
00762       break;
00763     case Weak:
00764       // Weak just goes to null, which will unlink it from the list.
00765       Entry->operator=(nullptr);
00766       break;
00767     case Callback:
00768       // Forward to the subclass's implementation.
00769       static_cast<CallbackVH*>(Entry)->deleted();
00770       break;
00771     }
00772   }
00773 
00774   // All callbacks, weak references, and assertingVHs should be dropped by now.
00775   if (V->HasValueHandle) {
00776 #ifndef NDEBUG      // Only in +Asserts mode...
00777     dbgs() << "While deleting: " << *V->getType() << " %" << V->getName()
00778            << "\n";
00779     if (pImpl->ValueHandles[V]->getKind() == Assert)
00780       llvm_unreachable("An asserting value handle still pointed to this"
00781                        " value!");
00782 
00783 #endif
00784     llvm_unreachable("All references to V were not removed?");
00785   }
00786 }
00787 
00788 
00789 void ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) {
00790   assert(Old->HasValueHandle &&"Should only be called if ValueHandles present");
00791   assert(Old != New && "Changing value into itself!");
00792   assert(Old->getType() == New->getType() &&
00793          "replaceAllUses of value with new value of different type!");
00794 
00795   // Get the linked list base, which is guaranteed to exist since the
00796   // HasValueHandle flag is set.
00797   LLVMContextImpl *pImpl = Old->getContext().pImpl;
00798   ValueHandleBase *Entry = pImpl->ValueHandles[Old];
00799 
00800   assert(Entry && "Value bit set but no entries exist");
00801 
00802   // We use a local ValueHandleBase as an iterator so that
00803   // ValueHandles can add and remove themselves from the list without
00804   // breaking our iteration.  This is not really an AssertingVH; we
00805   // just have to give ValueHandleBase some kind.
00806   for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) {
00807     Iterator.RemoveFromUseList();
00808     Iterator.AddToExistingUseListAfter(Entry);
00809     assert(Entry->Next == &Iterator && "Loop invariant broken.");
00810 
00811     switch (Entry->getKind()) {
00812     case Assert:
00813       // Asserting handle does not follow RAUW implicitly.
00814       break;
00815     case Tracking:
00816       // Tracking goes to new value like a WeakVH. Note that this may make it
00817       // something incompatible with its templated type. We don't want to have a
00818       // virtual (or inline) interface to handle this though, so instead we make
00819       // the TrackingVH accessors guarantee that a client never sees this value.
00820 
00821       // FALLTHROUGH
00822     case Weak:
00823       // Weak goes to the new value, which will unlink it from Old's list.
00824       Entry->operator=(New);
00825       break;
00826     case Callback:
00827       // Forward to the subclass's implementation.
00828       static_cast<CallbackVH*>(Entry)->allUsesReplacedWith(New);
00829       break;
00830     }
00831   }
00832 
00833 #ifndef NDEBUG
00834   // If any new tracking or weak value handles were added while processing the
00835   // list, then complain about it now.
00836   if (Old->HasValueHandle)
00837     for (Entry = pImpl->ValueHandles[Old]; Entry; Entry = Entry->Next)
00838       switch (Entry->getKind()) {
00839       case Tracking:
00840       case Weak:
00841         dbgs() << "After RAUW from " << *Old->getType() << " %"
00842                << Old->getName() << " to " << *New->getType() << " %"
00843                << New->getName() << "\n";
00844         llvm_unreachable("A tracking or weak value handle still pointed to the"
00845                          " old value!\n");
00846       default:
00847         break;
00848       }
00849 #endif
00850 }
00851 
00852 // Pin the vtable to this file.
00853 void CallbackVH::anchor() {}