Value.cpp revision b95c2fd2700a92a7b857ebd1ecf6c7d561d676d2
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/Constant.h" 15#include "llvm/Constants.h" 16#include "llvm/DerivedTypes.h" 17#include "llvm/InstrTypes.h" 18#include "llvm/Instructions.h" 19#include "llvm/Operator.h" 20#include "llvm/Module.h" 21#include "llvm/MDNode.h" 22#include "llvm/ValueSymbolTable.h" 23#include "llvm/Support/Debug.h" 24#include "llvm/Support/ErrorHandling.h" 25#include "llvm/Support/LeakDetector.h" 26#include "llvm/Support/ManagedStatic.h" 27#include "llvm/Support/ValueHandle.h" 28#include "llvm/Support/raw_ostream.h" 29#include "llvm/System/RWMutex.h" 30#include "llvm/System/Threading.h" 31#include "llvm/ADT/DenseMap.h" 32#include <algorithm> 33using namespace llvm; 34 35//===----------------------------------------------------------------------===// 36// Value Class 37//===----------------------------------------------------------------------===// 38 39static inline const Type *checkType(const Type *Ty) { 40 assert(Ty && "Value defined with a null type: Error!"); 41 return Ty; 42} 43 44Value::Value(const Type *ty, unsigned scid) 45 : SubclassID(scid), HasValueHandle(0), SubclassOptionalData(0), 46 SubclassData(0), VTy(checkType(ty)), 47 UseList(0), Name(0) { 48 if (isa<CallInst>(this) || isa<InvokeInst>(this)) 49 assert((VTy->isFirstClassType() || VTy == Type::VoidTy || 50 isa<OpaqueType>(ty) || VTy->getTypeID() == Type::StructTyID) && 51 "invalid CallInst type!"); 52 else if (!isa<Constant>(this) && !isa<BasicBlock>(this)) 53 assert((VTy->isFirstClassType() || VTy == Type::VoidTy || 54 isa<OpaqueType>(ty)) && 55 "Cannot create non-first-class values except for constants!"); 56} 57 58Value::~Value() { 59 // Notify all ValueHandles (if present) that this value is going away. 60 if (HasValueHandle) 61 ValueHandleBase::ValueIsDeleted(this); 62 63#ifndef NDEBUG // Only in -g mode... 64 // Check to make sure that there are no uses of this value that are still 65 // around when the value is destroyed. If there are, then we have a dangling 66 // reference and something is wrong. This code is here to print out what is 67 // still being referenced. The value in question should be printed as 68 // a <badref> 69 // 70 if (!use_empty()) { 71 errs() << "While deleting: " << *VTy << " %" << getNameStr() << "\n"; 72 for (use_iterator I = use_begin(), E = use_end(); I != E; ++I) 73 errs() << "Use still stuck around after Def is destroyed:" 74 << **I << "\n"; 75 } 76#endif 77 assert(use_empty() && "Uses remain when a value is destroyed!"); 78 79 // If this value is named, destroy the name. This should not be in a symtab 80 // at this point. 81 if (Name) 82 Name->Destroy(); 83 84 // There should be no uses of this object anymore, remove it. 85 LeakDetector::removeGarbageObject(this); 86} 87 88/// hasNUses - Return true if this Value has exactly N users. 89/// 90bool Value::hasNUses(unsigned N) const { 91 use_const_iterator UI = use_begin(), E = use_end(); 92 93 for (; N; --N, ++UI) 94 if (UI == E) return false; // Too few. 95 return UI == E; 96} 97 98/// hasNUsesOrMore - Return true if this value has N users or more. This is 99/// logically equivalent to getNumUses() >= N. 100/// 101bool Value::hasNUsesOrMore(unsigned N) const { 102 use_const_iterator UI = use_begin(), E = use_end(); 103 104 for (; N; --N, ++UI) 105 if (UI == E) return false; // Too few. 106 107 return true; 108} 109 110/// isUsedInBasicBlock - Return true if this value is used in the specified 111/// basic block. 112bool Value::isUsedInBasicBlock(const BasicBlock *BB) const { 113 for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I) { 114 const Instruction *User = dyn_cast<Instruction>(*I); 115 if (User && User->getParent() == BB) 116 return true; 117 } 118 return false; 119} 120 121 122/// getNumUses - This method computes the number of uses of this Value. This 123/// is a linear time operation. Use hasOneUse or hasNUses to check for specific 124/// values. 125unsigned Value::getNumUses() const { 126 return (unsigned)std::distance(use_begin(), use_end()); 127} 128 129static bool getSymTab(Value *V, ValueSymbolTable *&ST) { 130 ST = 0; 131 if (Instruction *I = dyn_cast<Instruction>(V)) { 132 if (BasicBlock *P = I->getParent()) 133 if (Function *PP = P->getParent()) 134 ST = &PP->getValueSymbolTable(); 135 } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 136 if (Function *P = BB->getParent()) 137 ST = &P->getValueSymbolTable(); 138 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 139 if (Module *P = GV->getParent()) 140 ST = &P->getValueSymbolTable(); 141 } else if (Argument *A = dyn_cast<Argument>(V)) { 142 if (Function *P = A->getParent()) 143 ST = &P->getValueSymbolTable(); 144 } else if (isa<MDString>(V)) 145 return true; 146 else { 147 assert(isa<Constant>(V) && "Unknown value type!"); 148 return true; // no name is setable for this. 149 } 150 return false; 151} 152 153/// getNameStart - Return a pointer to a null terminated string for this name. 154/// Note that names can have null characters within the string as well as at 155/// their end. This always returns a non-null pointer. 156const char *Value::getNameStart() const { 157 if (Name == 0) return ""; 158 return Name->getKeyData(); 159} 160 161/// getNameLen - Return the length of the string, correctly handling nul 162/// characters embedded into them. 163unsigned Value::getNameLen() const { 164 return Name ? Name->getKeyLength() : 0; 165} 166 167/// isName - Return true if this value has the name specified by the provided 168/// nul terminated string. 169bool Value::isName(const char *N) const { 170 unsigned InLen = strlen(N); 171 return InLen == getNameLen() && memcmp(getNameStart(), N, InLen) == 0; 172} 173 174 175std::string Value::getNameStr() const { 176 if (Name == 0) return ""; 177 return std::string(Name->getKeyData(), 178 Name->getKeyData()+Name->getKeyLength()); 179} 180 181StringRef Value::getNameRef() const { 182 if (Name == 0) return StringRef(); 183 return StringRef(Name->getKeyData(), Name->getKeyLength()); 184} 185 186void Value::setName(const std::string &name) { 187 setName(&name[0], name.size()); 188} 189 190void Value::setName(const char *Name) { 191 setName(Name, Name ? strlen(Name) : 0); 192} 193 194void Value::setName(const char *NameStr, unsigned NameLen) { 195 if (NameLen == 0 && !hasName()) return; 196 assert(getType() != Type::VoidTy && "Cannot assign a name to void values!"); 197 198 // Get the symbol table to update for this object. 199 ValueSymbolTable *ST; 200 if (getSymTab(this, ST)) 201 return; // Cannot set a name on this value (e.g. constant). 202 203 if (!ST) { // No symbol table to update? Just do the change. 204 if (NameLen == 0) { 205 // Free the name for this value. 206 Name->Destroy(); 207 Name = 0; 208 return; 209 } 210 211 if (Name) { 212 // Name isn't changing? 213 if (NameLen == Name->getKeyLength() && 214 !memcmp(Name->getKeyData(), NameStr, NameLen)) 215 return; 216 Name->Destroy(); 217 } 218 219 // NOTE: Could optimize for the case the name is shrinking to not deallocate 220 // then reallocated. 221 222 // Create the new name. 223 Name = ValueName::Create(NameStr, NameStr+NameLen); 224 Name->setValue(this); 225 return; 226 } 227 228 // NOTE: Could optimize for the case the name is shrinking to not deallocate 229 // then reallocated. 230 if (hasName()) { 231 // Name isn't changing? 232 if (NameLen == Name->getKeyLength() && 233 !memcmp(Name->getKeyData(), NameStr, NameLen)) 234 return; 235 236 // Remove old name. 237 ST->removeValueName(Name); 238 Name->Destroy(); 239 Name = 0; 240 241 if (NameLen == 0) 242 return; 243 } 244 245 // Name is changing to something new. 246 Name = ST->createValueName(StringRef(NameStr, NameLen), this); 247} 248 249 250/// takeName - transfer the name from V to this value, setting V's name to 251/// empty. It is an error to call V->takeName(V). 252void Value::takeName(Value *V) { 253 ValueSymbolTable *ST = 0; 254 // If this value has a name, drop it. 255 if (hasName()) { 256 // Get the symtab this is in. 257 if (getSymTab(this, ST)) { 258 // We can't set a name on this value, but we need to clear V's name if 259 // it has one. 260 if (V->hasName()) V->setName(0, 0); 261 return; // Cannot set a name on this value (e.g. constant). 262 } 263 264 // Remove old name. 265 if (ST) 266 ST->removeValueName(Name); 267 Name->Destroy(); 268 Name = 0; 269 } 270 271 // Now we know that this has no name. 272 273 // If V has no name either, we're done. 274 if (!V->hasName()) return; 275 276 // Get this's symtab if we didn't before. 277 if (!ST) { 278 if (getSymTab(this, ST)) { 279 // Clear V's name. 280 V->setName(0, 0); 281 return; // Cannot set a name on this value (e.g. constant). 282 } 283 } 284 285 // Get V's ST, this should always succed, because V has a name. 286 ValueSymbolTable *VST; 287 bool Failure = getSymTab(V, VST); 288 assert(!Failure && "V has a name, so it should have a ST!"); Failure=Failure; 289 290 // If these values are both in the same symtab, we can do this very fast. 291 // This works even if both values have no symtab yet. 292 if (ST == VST) { 293 // Take the name! 294 Name = V->Name; 295 V->Name = 0; 296 Name->setValue(this); 297 return; 298 } 299 300 // Otherwise, things are slightly more complex. Remove V's name from VST and 301 // then reinsert it into ST. 302 303 if (VST) 304 VST->removeValueName(V->Name); 305 Name = V->Name; 306 V->Name = 0; 307 Name->setValue(this); 308 309 if (ST) 310 ST->reinsertValue(this); 311} 312 313 314// uncheckedReplaceAllUsesWith - This is exactly the same as replaceAllUsesWith, 315// except that it doesn't have all of the asserts. The asserts fail because we 316// are half-way done resolving types, which causes some types to exist as two 317// different Type*'s at the same time. This is a sledgehammer to work around 318// this problem. 319// 320void Value::uncheckedReplaceAllUsesWith(Value *New) { 321 // Notify all ValueHandles (if present) that this value is going away. 322 if (HasValueHandle) 323 ValueHandleBase::ValueIsRAUWd(this, New); 324 325 while (!use_empty()) { 326 Use &U = *UseList; 327 // Must handle Constants specially, we cannot call replaceUsesOfWith on a 328 // constant because they are uniqued. 329 if (Constant *C = dyn_cast<Constant>(U.getUser())) { 330 if (!isa<GlobalValue>(C)) { 331 C->replaceUsesOfWithOnConstant(this, New, &U); 332 continue; 333 } 334 } 335 336 U.set(New); 337 } 338} 339 340void Value::replaceAllUsesWith(Value *New) { 341 assert(New && "Value::replaceAllUsesWith(<null>) is invalid!"); 342 assert(New != this && "this->replaceAllUsesWith(this) is NOT valid!"); 343 assert(New->getType() == getType() && 344 "replaceAllUses of value with new value of different type!"); 345 346 uncheckedReplaceAllUsesWith(New); 347} 348 349Value *Value::stripPointerCasts() { 350 if (!isa<PointerType>(getType())) 351 return this; 352 Value *V = this; 353 do { 354 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 355 if (!GEP->hasAllZeroIndices()) 356 return V; 357 V = GEP->getPointerOperand(); 358 } else if (Operator::getOpcode(V) == Instruction::BitCast) { 359 V = cast<Operator>(V)->getOperand(0); 360 } else { 361 return V; 362 } 363 assert(isa<PointerType>(V->getType()) && "Unexpected operand type!"); 364 } while (1); 365} 366 367Value *Value::getUnderlyingObject() { 368 if (!isa<PointerType>(getType())) 369 return this; 370 Value *V = this; 371 unsigned MaxLookup = 6; 372 do { 373 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 374 V = GEP->getPointerOperand(); 375 } else if (Operator::getOpcode(V) == Instruction::BitCast) { 376 V = cast<Operator>(V)->getOperand(0); 377 } else { 378 return V; 379 } 380 assert(isa<PointerType>(V->getType()) && "Unexpected operand type!"); 381 } while (--MaxLookup); 382 return V; 383} 384 385/// DoPHITranslation - If this value is a PHI node with CurBB as its parent, 386/// return the value in the PHI node corresponding to PredBB. If not, return 387/// ourself. This is useful if you want to know the value something has in a 388/// predecessor block. 389Value *Value::DoPHITranslation(const BasicBlock *CurBB, 390 const BasicBlock *PredBB) { 391 PHINode *PN = dyn_cast<PHINode>(this); 392 if (PN && PN->getParent() == CurBB) 393 return PN->getIncomingValueForBlock(PredBB); 394 return this; 395} 396 397LLVMContext &Value::getContext() const { return VTy->getContext(); } 398 399//===----------------------------------------------------------------------===// 400// ValueHandleBase Class 401//===----------------------------------------------------------------------===// 402 403/// ValueHandles - This map keeps track of all of the value handles that are 404/// watching a Value*. The Value::HasValueHandle bit is used to know whether or 405/// not a value has an entry in this map. 406typedef DenseMap<Value*, ValueHandleBase*> ValueHandlesTy; 407static ManagedStatic<ValueHandlesTy> ValueHandles; 408static ManagedStatic<sys::SmartRWMutex<true> > ValueHandlesLock; 409 410/// AddToExistingUseList - Add this ValueHandle to the use list for VP, where 411/// List is known to point into the existing use list. 412void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) { 413 assert(List && "Handle list is null?"); 414 415 // Splice ourselves into the list. 416 Next = *List; 417 *List = this; 418 setPrevPtr(List); 419 if (Next) { 420 Next->setPrevPtr(&Next); 421 assert(VP == Next->VP && "Added to wrong list?"); 422 } 423} 424 425/// AddToUseList - Add this ValueHandle to the use list for VP. 426void ValueHandleBase::AddToUseList() { 427 assert(VP && "Null pointer doesn't have a use list!"); 428 if (VP->HasValueHandle) { 429 // If this value already has a ValueHandle, then it must be in the 430 // ValueHandles map already. 431 sys::SmartScopedReader<true> Reader(*ValueHandlesLock); 432 ValueHandleBase *&Entry = (*ValueHandles)[VP]; 433 assert(Entry != 0 && "Value doesn't have any handles?"); 434 AddToExistingUseList(&Entry); 435 return; 436 } 437 438 // Ok, it doesn't have any handles yet, so we must insert it into the 439 // DenseMap. However, doing this insertion could cause the DenseMap to 440 // reallocate itself, which would invalidate all of the PrevP pointers that 441 // point into the old table. Handle this by checking for reallocation and 442 // updating the stale pointers only if needed. 443 sys::SmartScopedWriter<true> Writer(*ValueHandlesLock); 444 ValueHandlesTy &Handles = *ValueHandles; 445 const void *OldBucketPtr = Handles.getPointerIntoBucketsArray(); 446 447 ValueHandleBase *&Entry = Handles[VP]; 448 assert(Entry == 0 && "Value really did already have handles?"); 449 AddToExistingUseList(&Entry); 450 VP->HasValueHandle = true; 451 452 // If reallocation didn't happen or if this was the first insertion, don't 453 // walk the table. 454 if (Handles.isPointerIntoBucketsArray(OldBucketPtr) || 455 Handles.size() == 1) { 456 return; 457 } 458 459 // Okay, reallocation did happen. Fix the Prev Pointers. 460 for (ValueHandlesTy::iterator I = Handles.begin(), E = Handles.end(); 461 I != E; ++I) { 462 assert(I->second && I->first == I->second->VP && "List invariant broken!"); 463 I->second->setPrevPtr(&I->second); 464 } 465} 466 467/// RemoveFromUseList - Remove this ValueHandle from its current use list. 468void ValueHandleBase::RemoveFromUseList() { 469 assert(VP && VP->HasValueHandle && "Pointer doesn't have a use list!"); 470 471 // Unlink this from its use list. 472 ValueHandleBase **PrevPtr = getPrevPtr(); 473 assert(*PrevPtr == this && "List invariant broken"); 474 475 *PrevPtr = Next; 476 if (Next) { 477 assert(Next->getPrevPtr() == &Next && "List invariant broken"); 478 Next->setPrevPtr(PrevPtr); 479 return; 480 } 481 482 // If the Next pointer was null, then it is possible that this was the last 483 // ValueHandle watching VP. If so, delete its entry from the ValueHandles 484 // map. 485 sys::SmartScopedWriter<true> Writer(*ValueHandlesLock); 486 ValueHandlesTy &Handles = *ValueHandles; 487 if (Handles.isPointerIntoBucketsArray(PrevPtr)) { 488 Handles.erase(VP); 489 VP->HasValueHandle = false; 490 } 491} 492 493 494void ValueHandleBase::ValueIsDeleted(Value *V) { 495 assert(V->HasValueHandle && "Should only be called if ValueHandles present"); 496 497 // Get the linked list base, which is guaranteed to exist since the 498 // HasValueHandle flag is set. 499 ValueHandlesLock->reader_acquire(); 500 ValueHandleBase *Entry = (*ValueHandles)[V]; 501 ValueHandlesLock->reader_release(); 502 assert(Entry && "Value bit set but no entries exist"); 503 504 while (Entry) { 505 // Advance pointer to avoid invalidation. 506 ValueHandleBase *ThisNode = Entry; 507 Entry = Entry->Next; 508 509 switch (ThisNode->getKind()) { 510 case Assert: 511#ifndef NDEBUG // Only in -g mode... 512 errs() << "While deleting: " << *V->getType() << " %" << V->getNameStr() 513 << "\n"; 514#endif 515 llvm_unreachable("An asserting value handle still pointed to this" 516 " value!"); 517 case Weak: 518 // Weak just goes to null, which will unlink it from the list. 519 ThisNode->operator=(0); 520 break; 521 case Callback: 522 // Forward to the subclass's implementation. 523 static_cast<CallbackVH*>(ThisNode)->deleted(); 524 break; 525 } 526 } 527 528 // All callbacks and weak references should be dropped by now. 529 assert(!V->HasValueHandle && "All references to V were not removed?"); 530} 531 532 533void ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) { 534 assert(Old->HasValueHandle &&"Should only be called if ValueHandles present"); 535 assert(Old != New && "Changing value into itself!"); 536 537 // Get the linked list base, which is guaranteed to exist since the 538 // HasValueHandle flag is set. 539 ValueHandlesLock->reader_acquire(); 540 ValueHandleBase *Entry = (*ValueHandles)[Old]; 541 ValueHandlesLock->reader_release(); 542 assert(Entry && "Value bit set but no entries exist"); 543 544 while (Entry) { 545 // Advance pointer to avoid invalidation. 546 ValueHandleBase *ThisNode = Entry; 547 Entry = Entry->Next; 548 549 switch (ThisNode->getKind()) { 550 case Assert: 551 // Asserting handle does not follow RAUW implicitly. 552 break; 553 case Weak: 554 // Weak goes to the new value, which will unlink it from Old's list. 555 ThisNode->operator=(New); 556 break; 557 case Callback: 558 // Forward to the subclass's implementation. 559 static_cast<CallbackVH*>(ThisNode)->allUsesReplacedWith(New); 560 break; 561 } 562 } 563} 564 565/// ~CallbackVH. Empty, but defined here to avoid emitting the vtable 566/// more than once. 567CallbackVH::~CallbackVH() {} 568 569 570//===----------------------------------------------------------------------===// 571// User Class 572//===----------------------------------------------------------------------===// 573 574// replaceUsesOfWith - Replaces all references to the "From" definition with 575// references to the "To" definition. 576// 577void User::replaceUsesOfWith(Value *From, Value *To) { 578 if (From == To) return; // Duh what? 579 580 assert((!isa<Constant>(this) || isa<GlobalValue>(this)) && 581 "Cannot call User::replaceUsesofWith on a constant!"); 582 583 for (unsigned i = 0, E = getNumOperands(); i != E; ++i) 584 if (getOperand(i) == From) { // Is This operand is pointing to oldval? 585 // The side effects of this setOperand call include linking to 586 // "To", adding "this" to the uses list of To, and 587 // most importantly, removing "this" from the use list of "From". 588 setOperand(i, To); // Fix it now... 589 } 590} 591