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 "LLVMContextImpl.h"
00015 #include "llvm/Constant.h"
00016 #include "llvm/Constants.h"
00017 #include "llvm/DerivedTypes.h"
00018 #include "llvm/InstrTypes.h"
00019 #include "llvm/Instructions.h"
00020 #include "llvm/Operator.h"
00021 #include "llvm/Module.h"
00022 #include "llvm/Metadata.h"
00023 #include "llvm/ValueSymbolTable.h"
00024 #include "llvm/ADT/SmallString.h"
00025 #include "llvm/Support/Debug.h"
00026 #include "llvm/Support/ErrorHandling.h"
00027 #include "llvm/Support/LeakDetector.h"
00028 #include "llvm/Support/ManagedStatic.h"
00029 #include "llvm/Support/ValueHandle.h"
00030 #include "llvm/Support/raw_ostream.h"
00031 #include "llvm/System/RWMutex.h"
00032 #include "llvm/System/Threading.h"
00033 #include "llvm/ADT/DenseMap.h"
00034 #include <algorithm>
00035 using namespace llvm;
00036 
00037 //===----------------------------------------------------------------------===//
00038 //                                Value Class
00039 //===----------------------------------------------------------------------===//
00040 
00041 static inline const Type *checkType(const Type *Ty) {
00042   assert(Ty && "Value defined with a null type: Error!");
00043   return Ty;
00044 }
00045 
00046 Value::Value(const Type *ty, unsigned scid)
00047   : SubclassID(scid), HasValueHandle(0), SubclassOptionalData(0),
00048     SubclassData(0), VTy(checkType(ty)),
00049     UseList(0), Name(0) {
00050   if (isa<CallInst>(this) || isa<InvokeInst>(this))
00051     assert((VTy->isFirstClassType() ||
00052             VTy == Type::getVoidTy(ty->getContext()) ||
00053             isa<OpaqueType>(ty) || VTy->getTypeID() == Type::StructTyID) &&
00054            "invalid CallInst  type!");
00055   else if (!isa<Constant>(this) && !isa<BasicBlock>(this))
00056     assert((VTy->isFirstClassType() ||
00057             VTy == Type::getVoidTy(ty->getContext()) ||
00058            isa<OpaqueType>(ty)) &&
00059            "Cannot create non-first-class values except for constants!");
00060 }
00061 
00062 Value::~Value() {
00063   // Notify all ValueHandles (if present) that this value is going away.
00064   if (HasValueHandle)
00065     ValueHandleBase::ValueIsDeleted(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     errs() << "While deleting: " << *VTy << " %" << getNameStr() << "\n";
00076     for (use_iterator I = use_begin(), E = use_end(); I != E; ++I)
00077       errs() << "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   if (Name)
00086     Name->Destroy();
00087   
00088   // There should be no uses of this object anymore, remove it.
00089   LeakDetector::removeGarbageObject(this);
00090 }
00091 
00092 /// hasNUses - Return true if this Value has exactly N users.
00093 ///
00094 bool Value::hasNUses(unsigned N) const {
00095   use_const_iterator UI = use_begin(), E = use_end();
00096 
00097   for (; N; --N, ++UI)
00098     if (UI == E) return false;  // Too few.
00099   return UI == E;
00100 }
00101 
00102 /// hasNUsesOrMore - Return true if this value has N users or more.  This is
00103 /// logically equivalent to getNumUses() >= N.
00104 ///
00105 bool Value::hasNUsesOrMore(unsigned N) const {
00106   use_const_iterator UI = use_begin(), E = use_end();
00107 
00108   for (; N; --N, ++UI)
00109     if (UI == E) return false;  // Too few.
00110 
00111   return true;
00112 }
00113 
00114 /// isUsedInBasicBlock - Return true if this value is used in the specified
00115 /// basic block.
00116 bool Value::isUsedInBasicBlock(const BasicBlock *BB) const {
00117   for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I) {
00118     const Instruction *User = dyn_cast<Instruction>(*I);
00119     if (User && User->getParent() == BB)
00120       return true;
00121   }
00122   return false;
00123 }
00124 
00125 
00126 /// getNumUses - This method computes the number of uses of this Value.  This
00127 /// is a linear time operation.  Use hasOneUse or hasNUses to check for specific
00128 /// values.
00129 unsigned Value::getNumUses() const {
00130   return (unsigned)std::distance(use_begin(), use_end());
00131 }
00132 
00133 static bool getSymTab(Value *V, ValueSymbolTable *&ST) {
00134   ST = 0;
00135   if (Instruction *I = dyn_cast<Instruction>(V)) {
00136     if (BasicBlock *P = I->getParent())
00137       if (Function *PP = P->getParent())
00138         ST = &PP->getValueSymbolTable();
00139   } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
00140     if (Function *P = BB->getParent()) 
00141       ST = &P->getValueSymbolTable();
00142   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
00143     if (Module *P = GV->getParent()) 
00144       ST = &P->getValueSymbolTable();
00145   } else if (Argument *A = dyn_cast<Argument>(V)) {
00146     if (Function *P = A->getParent()) 
00147       ST = &P->getValueSymbolTable();
00148   } else if (NamedMDNode *N = dyn_cast<NamedMDNode>(V)) {
00149     if (Module *P = N->getParent()) {
00150       ST = &P->getValueSymbolTable();
00151     }
00152   } else if (isa<MDString>(V))
00153     return true;
00154   else {
00155     assert(isa<Constant>(V) && "Unknown value type!");
00156     return true;  // no name is setable for this.
00157   }
00158   return false;
00159 }
00160 
00161 StringRef Value::getName() const {
00162   // Make sure the empty string is still a C string. For historical reasons,
00163   // some clients want to call .data() on the result and expect it to be null
00164   // terminated.
00165   if (!Name) return StringRef("", 0);
00166   return Name->getKey();
00167 }
00168 
00169 std::string Value::getNameStr() const {
00170   return getName().str();
00171 }
00172 
00173 void Value::setName(const Twine &NewName) {
00174   // Fast path for common IRBuilder case of setName("") when there is no name.
00175   if (NewName.isTriviallyEmpty() && !hasName())
00176     return;
00177 
00178   SmallString<256> NameData;
00179   NewName.toVector(NameData);
00180 
00181   const char *NameStr = NameData.data();
00182   unsigned NameLen = NameData.size();
00183 
00184   // Name isn't changing?
00185   if (getName() == StringRef(NameStr, NameLen))
00186     return;
00187 
00188   assert(getType() != Type::getVoidTy(getContext()) &&
00189          "Cannot assign a name to void values!");
00190   
00191   // Get the symbol table to update for this object.
00192   ValueSymbolTable *ST;
00193   if (getSymTab(this, ST))
00194     return;  // Cannot set a name on this value (e.g. constant).
00195 
00196   if (!ST) { // No symbol table to update?  Just do the change.
00197     if (NameLen == 0) {
00198       // Free the name for this value.
00199       Name->Destroy();
00200       Name = 0;
00201       return;
00202     }
00203     
00204     if (Name)
00205       Name->Destroy();
00206     
00207     // NOTE: Could optimize for the case the name is shrinking to not deallocate
00208     // then reallocated.
00209       
00210     // Create the new name.
00211     Name = ValueName::Create(NameStr, NameStr+NameLen);
00212     Name->setValue(this);
00213     return;
00214   }
00215   
00216   // NOTE: Could optimize for the case the name is shrinking to not deallocate
00217   // then reallocated.
00218   if (hasName()) {
00219     // Remove old name.
00220     ST->removeValueName(Name);
00221     Name->Destroy();
00222     Name = 0;
00223 
00224     if (NameLen == 0)
00225       return;
00226   }
00227 
00228   // Name is changing to something new.
00229   Name = ST->createValueName(StringRef(NameStr, NameLen), this);
00230 }
00231 
00232 
00233 /// takeName - transfer the name from V to this value, setting V's name to
00234 /// empty.  It is an error to call V->takeName(V). 
00235 void Value::takeName(Value *V) {
00236   ValueSymbolTable *ST = 0;
00237   // If this value has a name, drop it.
00238   if (hasName()) {
00239     // Get the symtab this is in.
00240     if (getSymTab(this, ST)) {
00241       // We can't set a name on this value, but we need to clear V's name if
00242       // it has one.
00243       if (V->hasName()) V->setName("");
00244       return;  // Cannot set a name on this value (e.g. constant).
00245     }
00246     
00247     // Remove old name.
00248     if (ST)
00249       ST->removeValueName(Name);
00250     Name->Destroy();
00251     Name = 0;
00252   } 
00253   
00254   // Now we know that this has no name.
00255   
00256   // If V has no name either, we're done.
00257   if (!V->hasName()) return;
00258    
00259   // Get this's symtab if we didn't before.
00260   if (!ST) {
00261     if (getSymTab(this, ST)) {
00262       // Clear V's name.
00263       V->setName("");
00264       return;  // Cannot set a name on this value (e.g. constant).
00265     }
00266   }
00267   
00268   // Get V's ST, this should always succed, because V has a name.
00269   ValueSymbolTable *VST;
00270   bool Failure = getSymTab(V, VST);
00271   assert(!Failure && "V has a name, so it should have a ST!"); Failure=Failure;
00272   
00273   // If these values are both in the same symtab, we can do this very fast.
00274   // This works even if both values have no symtab yet.
00275   if (ST == VST) {
00276     // Take the name!
00277     Name = V->Name;
00278     V->Name = 0;
00279     Name->setValue(this);
00280     return;
00281   }
00282   
00283   // Otherwise, things are slightly more complex.  Remove V's name from VST and
00284   // then reinsert it into ST.
00285   
00286   if (VST)
00287     VST->removeValueName(V->Name);
00288   Name = V->Name;
00289   V->Name = 0;
00290   Name->setValue(this);
00291   
00292   if (ST)
00293     ST->reinsertValue(this);
00294 }
00295 
00296 
00297 // uncheckedReplaceAllUsesWith - This is exactly the same as replaceAllUsesWith,
00298 // except that it doesn't have all of the asserts.  The asserts fail because we
00299 // are half-way done resolving types, which causes some types to exist as two
00300 // different Type*'s at the same time.  This is a sledgehammer to work around
00301 // this problem.
00302 //
00303 void Value::uncheckedReplaceAllUsesWith(Value *New) {
00304   // Notify all ValueHandles (if present) that this value is going away.
00305   if (HasValueHandle)
00306     ValueHandleBase::ValueIsRAUWd(this, New);
00307  
00308   while (!use_empty()) {
00309     Use &U = *UseList;
00310     // Must handle Constants specially, we cannot call replaceUsesOfWith on a
00311     // constant because they are uniqued.
00312     if (Constant *C = dyn_cast<Constant>(U.getUser())) {
00313       if (!isa<GlobalValue>(C)) {
00314         C->replaceUsesOfWithOnConstant(this, New, &U);
00315         continue;
00316       }
00317     }
00318     
00319     U.set(New);
00320   }
00321 }
00322 
00323 void Value::replaceAllUsesWith(Value *New) {
00324   assert(New && "Value::replaceAllUsesWith(<null>) is invalid!");
00325   assert(New != this && "this->replaceAllUsesWith(this) is NOT valid!");
00326   assert(New->getType() == getType() &&
00327          "replaceAllUses of value with new value of different type!");
00328 
00329   uncheckedReplaceAllUsesWith(New);
00330 }
00331 
00332 Value *Value::stripPointerCasts() {
00333   if (!isa<PointerType>(getType()))
00334     return this;
00335   Value *V = this;
00336   do {
00337     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
00338       if (!GEP->hasAllZeroIndices())
00339         return V;
00340       V = GEP->getPointerOperand();
00341     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
00342       V = cast<Operator>(V)->getOperand(0);
00343     } else {
00344       return V;
00345     }
00346     assert(isa<PointerType>(V->getType()) && "Unexpected operand type!");
00347   } while (1);
00348 }
00349 
00350 Value *Value::getUnderlyingObject() {
00351   if (!isa<PointerType>(getType()))
00352     return this;
00353   Value *V = this;
00354   unsigned MaxLookup = 6;
00355   do {
00356     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
00357       V = GEP->getPointerOperand();
00358     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
00359       V = cast<Operator>(V)->getOperand(0);
00360     } else {
00361       return V;
00362     }
00363     assert(isa<PointerType>(V->getType()) && "Unexpected operand type!");
00364   } while (--MaxLookup);
00365   return V;
00366 }
00367 
00368 /// DoPHITranslation - If this value is a PHI node with CurBB as its parent,
00369 /// return the value in the PHI node corresponding to PredBB.  If not, return
00370 /// ourself.  This is useful if you want to know the value something has in a
00371 /// predecessor block.
00372 Value *Value::DoPHITranslation(const BasicBlock *CurBB, 
00373                                const BasicBlock *PredBB) {
00374   PHINode *PN = dyn_cast<PHINode>(this);
00375   if (PN && PN->getParent() == CurBB)
00376     return PN->getIncomingValueForBlock(PredBB);
00377   return this;
00378 }
00379 
00380 LLVMContext &Value::getContext() const { return VTy->getContext(); }
00381 
00382 //===----------------------------------------------------------------------===//
00383 //                             ValueHandleBase Class
00384 //===----------------------------------------------------------------------===//
00385 
00386 /// AddToExistingUseList - Add this ValueHandle to the use list for VP, where
00387 /// List is known to point into the existing use list.
00388 void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) {
00389   assert(List && "Handle list is null?");
00390   
00391   // Splice ourselves into the list.
00392   Next = *List;
00393   *List = this;
00394   setPrevPtr(List);
00395   if (Next) {
00396     Next->setPrevPtr(&Next);
00397     assert(VP == Next->VP && "Added to wrong list?");
00398   }
00399 }
00400 
00401 /// AddToUseList - Add this ValueHandle to the use list for VP.
00402 void ValueHandleBase::AddToUseList() {
00403   assert(VP && "Null pointer doesn't have a use list!");
00404   
00405   LLVMContextImpl *pImpl = VP->getContext().pImpl;
00406   
00407   if (VP->HasValueHandle) {
00408     // If this value already has a ValueHandle, then it must be in the
00409     // ValueHandles map already.
00410     ValueHandleBase *&Entry = pImpl->ValueHandles[VP];
00411     assert(Entry != 0 && "Value doesn't have any handles?");
00412     AddToExistingUseList(&Entry);
00413     return;
00414   }
00415   
00416   // Ok, it doesn't have any handles yet, so we must insert it into the
00417   // DenseMap.  However, doing this insertion could cause the DenseMap to
00418   // reallocate itself, which would invalidate all of the PrevP pointers that
00419   // point into the old table.  Handle this by checking for reallocation and
00420   // updating the stale pointers only if needed.
00421   DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles;
00422   const void *OldBucketPtr = Handles.getPointerIntoBucketsArray();
00423   
00424   ValueHandleBase *&Entry = Handles[VP];
00425   assert(Entry == 0 && "Value really did already have handles?");
00426   AddToExistingUseList(&Entry);
00427   VP->HasValueHandle = true;
00428   
00429   // If reallocation didn't happen or if this was the first insertion, don't
00430   // walk the table.
00431   if (Handles.isPointerIntoBucketsArray(OldBucketPtr) || 
00432       Handles.size() == 1) {
00433     return;
00434   }
00435   
00436   // Okay, reallocation did happen.  Fix the Prev Pointers.
00437   for (DenseMap<Value*, ValueHandleBase*>::iterator I = Handles.begin(),
00438        E = Handles.end(); I != E; ++I) {
00439     assert(I->second && I->first == I->second->VP && "List invariant broken!");
00440     I->second->setPrevPtr(&I->second);
00441   }
00442 }
00443 
00444 /// RemoveFromUseList - Remove this ValueHandle from its current use list.
00445 void ValueHandleBase::RemoveFromUseList() {
00446   assert(VP && VP->HasValueHandle && "Pointer doesn't have a use list!");
00447 
00448   // Unlink this from its use list.
00449   ValueHandleBase **PrevPtr = getPrevPtr();
00450   assert(*PrevPtr == this && "List invariant broken");
00451   
00452   *PrevPtr = Next;
00453   if (Next) {
00454     assert(Next->getPrevPtr() == &Next && "List invariant broken");
00455     Next->setPrevPtr(PrevPtr);
00456     return;
00457   }
00458   
00459   // If the Next pointer was null, then it is possible that this was the last
00460   // ValueHandle watching VP.  If so, delete its entry from the ValueHandles
00461   // map.
00462   LLVMContextImpl *pImpl = VP->getContext().pImpl;
00463   DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles;
00464   if (Handles.isPointerIntoBucketsArray(PrevPtr)) {
00465     Handles.erase(VP);
00466     VP->HasValueHandle = false;
00467   }
00468 }
00469 
00470 
00471 void ValueHandleBase::ValueIsDeleted(Value *V) {
00472   assert(V->HasValueHandle && "Should only be called if ValueHandles present");
00473 
00474   // Get the linked list base, which is guaranteed to exist since the
00475   // HasValueHandle flag is set.
00476   LLVMContextImpl *pImpl = V->getContext().pImpl;
00477   ValueHandleBase *Entry = pImpl->ValueHandles[V];
00478   assert(Entry && "Value bit set but no entries exist");
00479   
00480   while (Entry) {
00481     // Advance pointer to avoid invalidation.
00482     ValueHandleBase *ThisNode = Entry;
00483     Entry = Entry->Next;
00484     
00485     switch (ThisNode->getKind()) {
00486     case Assert:
00487 #ifndef NDEBUG      // Only in -g mode...
00488       errs() << "While deleting: " << *V->getType() << " %" << V->getNameStr()
00489              << "\n";
00490 #endif
00491       llvm_unreachable("An asserting value handle still pointed to this"
00492                        " value!");
00493     case Weak:
00494       // Weak just goes to null, which will unlink it from the list.
00495       ThisNode->operator=(0);
00496       break;
00497     case Callback:
00498       // Forward to the subclass's implementation.
00499       static_cast<CallbackVH*>(ThisNode)->deleted();
00500       break;
00501     }
00502   }
00503   
00504   // All callbacks and weak references should be dropped by now.
00505   assert(!V->HasValueHandle && "All references to V were not removed?");
00506 }
00507 
00508 
00509 void ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) {
00510   assert(Old->HasValueHandle &&"Should only be called if ValueHandles present");
00511   assert(Old != New && "Changing value into itself!");
00512   
00513   // Get the linked list base, which is guaranteed to exist since the
00514   // HasValueHandle flag is set.
00515   LLVMContextImpl *pImpl = Old->getContext().pImpl;
00516   ValueHandleBase *Entry = pImpl->ValueHandles[Old];
00517 
00518   assert(Entry && "Value bit set but no entries exist");
00519   
00520   while (Entry) {
00521     // Advance pointer to avoid invalidation.
00522     ValueHandleBase *ThisNode = Entry;
00523     Entry = Entry->Next;
00524     
00525     switch (ThisNode->getKind()) {
00526     case Assert:
00527       // Asserting handle does not follow RAUW implicitly.
00528       break;
00529     case Weak:
00530       // Weak goes to the new value, which will unlink it from Old's list.
00531       ThisNode->operator=(New);
00532       break;
00533     case Callback:
00534       // Forward to the subclass's implementation.
00535       static_cast<CallbackVH*>(ThisNode)->allUsesReplacedWith(New);
00536       break;
00537     }
00538   }
00539 }
00540 
00541 /// ~CallbackVH. Empty, but defined here to avoid emitting the vtable
00542 /// more than once.
00543 CallbackVH::~CallbackVH() {}
00544 
00545 
00546 //===----------------------------------------------------------------------===//
00547 //                                 User Class
00548 //===----------------------------------------------------------------------===//
00549 
00550 // replaceUsesOfWith - Replaces all references to the "From" definition with
00551 // references to the "To" definition.
00552 //
00553 void User::replaceUsesOfWith(Value *From, Value *To) {
00554   if (From == To) return;   // Duh what?
00555 
00556   assert((!isa<Constant>(this) || isa<GlobalValue>(this)) &&
00557          "Cannot call User::replaceUsesOfWith on a constant!");
00558 
00559   for (unsigned i = 0, E = getNumOperands(); i != E; ++i)
00560     if (getOperand(i) == From) {  // Is This operand is pointing to oldval?
00561       // The side effects of this setOperand call include linking to
00562       // "To", adding "this" to the uses list of To, and
00563       // most importantly, removing "this" from the use list of "From".
00564       setOperand(i, To); // Fix it now...
00565     }
00566 }