LLVM API Documentation
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 }