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 "LLVMContextImpl.h" 15 #include "llvm/Constant.h" 16 #include "llvm/Constants.h" 17 #include "llvm/DerivedTypes.h" 18 #include "llvm/InstrTypes.h" 19 #include "llvm/Instructions.h" 20 #include "llvm/Operator.h" 21 #include "llvm/Module.h" 22 #include "llvm/ValueSymbolTable.h" 23 #include "llvm/ADT/SmallString.h" 24 #include "llvm/Support/Debug.h" 25 #include "llvm/Support/GetElementPtrTypeIterator.h" 26 #include "llvm/Support/ErrorHandling.h" 27 #include "llvm/Support/LeakDetector.h" 28 #include "llvm/Support/ManagedStatic.h" 29 #include "llvm/Support/ValueHandle.h" 30 #include "llvm/ADT/DenseMap.h" 31 #include <algorithm> 32 using namespace llvm; 33 34 //===----------------------------------------------------------------------===// 35 // Value Class 36 //===----------------------------------------------------------------------===// 37 38 static inline Type *checkType(Type *Ty) { 39 assert(Ty && "Value defined with a null type: Error!"); 40 return const_cast<Type*>(Ty); 41 } 42 43 Value::Value(Type *ty, unsigned scid) 44 : SubclassID(scid), HasValueHandle(0), 45 SubclassOptionalData(0), SubclassData(0), VTy((Type*)checkType(ty)), 46 UseList(0), Name(0) { 47 // FIXME: Why isn't this in the subclass gunk?? 48 if (isa<CallInst>(this) || isa<InvokeInst>(this)) 49 assert((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) && 50 "invalid CallInst type!"); 51 else if (!isa<Constant>(this) && !isa<BasicBlock>(this)) 52 assert((VTy->isFirstClassType() || VTy->isVoidTy()) && 53 "Cannot create non-first-class values except for constants!"); 54 } 55 56 Value::~Value() { 57 // Notify all ValueHandles (if present) that this value is going away. 58 if (HasValueHandle) 59 ValueHandleBase::ValueIsDeleted(this); 60 61 #ifndef NDEBUG // Only in -g mode... 62 // Check to make sure that there are no uses of this value that are still 63 // around when the value is destroyed. If there are, then we have a dangling 64 // reference and something is wrong. This code is here to print out what is 65 // still being referenced. The value in question should be printed as 66 // a <badref> 67 // 68 if (!use_empty()) { 69 dbgs() << "While deleting: " << *VTy << " %" << getNameStr() << "\n"; 70 for (use_iterator I = use_begin(), E = use_end(); I != E; ++I) 71 dbgs() << "Use still stuck around after Def is destroyed:" 72 << **I << "\n"; 73 } 74 #endif 75 assert(use_empty() && "Uses remain when a value is destroyed!"); 76 77 // If this value is named, destroy the name. This should not be in a symtab 78 // at this point. 79 if (Name) 80 Name->Destroy(); 81 82 // There should be no uses of this object anymore, remove it. 83 LeakDetector::removeGarbageObject(this); 84 } 85 86 /// hasNUses - Return true if this Value has exactly N users. 87 /// 88 bool Value::hasNUses(unsigned N) const { 89 const_use_iterator UI = use_begin(), E = use_end(); 90 91 for (; N; --N, ++UI) 92 if (UI == E) return false; // Too few. 93 return UI == E; 94 } 95 96 /// hasNUsesOrMore - Return true if this value has N users or more. This is 97 /// logically equivalent to getNumUses() >= N. 98 /// 99 bool Value::hasNUsesOrMore(unsigned N) const { 100 const_use_iterator UI = use_begin(), E = use_end(); 101 102 for (; N; --N, ++UI) 103 if (UI == E) return false; // Too few. 104 105 return true; 106 } 107 108 /// isUsedInBasicBlock - Return true if this value is used in the specified 109 /// basic block. 110 bool Value::isUsedInBasicBlock(const BasicBlock *BB) const { 111 for (const_use_iterator I = use_begin(), E = use_end(); I != E; ++I) { 112 const Instruction *User = dyn_cast<Instruction>(*I); 113 if (User && User->getParent() == BB) 114 return true; 115 } 116 return false; 117 } 118 119 120 /// getNumUses - This method computes the number of uses of this Value. This 121 /// is a linear time operation. Use hasOneUse or hasNUses to check for specific 122 /// values. 123 unsigned Value::getNumUses() const { 124 return (unsigned)std::distance(use_begin(), use_end()); 125 } 126 127 static bool getSymTab(Value *V, ValueSymbolTable *&ST) { 128 ST = 0; 129 if (Instruction *I = dyn_cast<Instruction>(V)) { 130 if (BasicBlock *P = I->getParent()) 131 if (Function *PP = P->getParent()) 132 ST = &PP->getValueSymbolTable(); 133 } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 134 if (Function *P = BB->getParent()) 135 ST = &P->getValueSymbolTable(); 136 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 137 if (Module *P = GV->getParent()) 138 ST = &P->getValueSymbolTable(); 139 } else if (Argument *A = dyn_cast<Argument>(V)) { 140 if (Function *P = A->getParent()) 141 ST = &P->getValueSymbolTable(); 142 } else if (isa<MDString>(V)) 143 return true; 144 else { 145 assert(isa<Constant>(V) && "Unknown value type!"); 146 return true; // no name is setable for this. 147 } 148 return false; 149 } 150 151 StringRef Value::getName() const { 152 // Make sure the empty string is still a C string. For historical reasons, 153 // some clients want to call .data() on the result and expect it to be null 154 // terminated. 155 if (!Name) return StringRef("", 0); 156 return Name->getKey(); 157 } 158 159 std::string Value::getNameStr() const { 160 return getName().str(); 161 } 162 163 void Value::setName(const Twine &NewName) { 164 // Fast path for common IRBuilder case of setName("") when there is no name. 165 if (NewName.isTriviallyEmpty() && !hasName()) 166 return; 167 168 SmallString<256> NameData; 169 StringRef NameRef = NewName.toStringRef(NameData); 170 171 // Name isn't changing? 172 if (getName() == NameRef) 173 return; 174 175 assert(!getType()->isVoidTy() && "Cannot assign a name to void values!"); 176 177 // Get the symbol table to update for this object. 178 ValueSymbolTable *ST; 179 if (getSymTab(this, ST)) 180 return; // Cannot set a name on this value (e.g. constant). 181 182 if (!ST) { // No symbol table to update? Just do the change. 183 if (NameRef.empty()) { 184 // Free the name for this value. 185 Name->Destroy(); 186 Name = 0; 187 return; 188 } 189 190 if (Name) 191 Name->Destroy(); 192 193 // NOTE: Could optimize for the case the name is shrinking to not deallocate 194 // then reallocated. 195 196 // Create the new name. 197 Name = ValueName::Create(NameRef.begin(), NameRef.end()); 198 Name->setValue(this); 199 return; 200 } 201 202 // NOTE: Could optimize for the case the name is shrinking to not deallocate 203 // then reallocated. 204 if (hasName()) { 205 // Remove old name. 206 ST->removeValueName(Name); 207 Name->Destroy(); 208 Name = 0; 209 210 if (NameRef.empty()) 211 return; 212 } 213 214 // Name is changing to something new. 215 Name = ST->createValueName(NameRef, this); 216 } 217 218 219 /// takeName - transfer the name from V to this value, setting V's name to 220 /// empty. It is an error to call V->takeName(V). 221 void Value::takeName(Value *V) { 222 ValueSymbolTable *ST = 0; 223 // If this value has a name, drop it. 224 if (hasName()) { 225 // Get the symtab this is in. 226 if (getSymTab(this, ST)) { 227 // We can't set a name on this value, but we need to clear V's name if 228 // it has one. 229 if (V->hasName()) V->setName(""); 230 return; // Cannot set a name on this value (e.g. constant). 231 } 232 233 // Remove old name. 234 if (ST) 235 ST->removeValueName(Name); 236 Name->Destroy(); 237 Name = 0; 238 } 239 240 // Now we know that this has no name. 241 242 // If V has no name either, we're done. 243 if (!V->hasName()) return; 244 245 // Get this's symtab if we didn't before. 246 if (!ST) { 247 if (getSymTab(this, ST)) { 248 // Clear V's name. 249 V->setName(""); 250 return; // Cannot set a name on this value (e.g. constant). 251 } 252 } 253 254 // Get V's ST, this should always succed, because V has a name. 255 ValueSymbolTable *VST; 256 bool Failure = getSymTab(V, VST); 257 assert(!Failure && "V has a name, so it should have a ST!"); (void)Failure; 258 259 // If these values are both in the same symtab, we can do this very fast. 260 // This works even if both values have no symtab yet. 261 if (ST == VST) { 262 // Take the name! 263 Name = V->Name; 264 V->Name = 0; 265 Name->setValue(this); 266 return; 267 } 268 269 // Otherwise, things are slightly more complex. Remove V's name from VST and 270 // then reinsert it into ST. 271 272 if (VST) 273 VST->removeValueName(V->Name); 274 Name = V->Name; 275 V->Name = 0; 276 Name->setValue(this); 277 278 if (ST) 279 ST->reinsertValue(this); 280 } 281 282 283 void Value::replaceAllUsesWith(Value *New) { 284 assert(New && "Value::replaceAllUsesWith(<null>) is invalid!"); 285 assert(New != this && "this->replaceAllUsesWith(this) is NOT valid!"); 286 assert(New->getType() == getType() && 287 "replaceAllUses of value with new value of different type!"); 288 289 // Notify all ValueHandles (if present) that this value is going away. 290 if (HasValueHandle) 291 ValueHandleBase::ValueIsRAUWd(this, New); 292 293 while (!use_empty()) { 294 Use &U = *UseList; 295 // Must handle Constants specially, we cannot call replaceUsesOfWith on a 296 // constant because they are uniqued. 297 if (Constant *C = dyn_cast<Constant>(U.getUser())) { 298 if (!isa<GlobalValue>(C)) { 299 C->replaceUsesOfWithOnConstant(this, New, &U); 300 continue; 301 } 302 } 303 304 U.set(New); 305 } 306 307 if (BasicBlock *BB = dyn_cast<BasicBlock>(this)) 308 BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New)); 309 } 310 311 Value *Value::stripPointerCasts() { 312 if (!getType()->isPointerTy()) 313 return this; 314 315 // Even though we don't look through PHI nodes, we could be called on an 316 // instruction in an unreachable block, which may be on a cycle. 317 SmallPtrSet<Value *, 4> Visited; 318 319 Value *V = this; 320 Visited.insert(V); 321 do { 322 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 323 if (!GEP->hasAllZeroIndices()) 324 return V; 325 V = GEP->getPointerOperand(); 326 } else if (Operator::getOpcode(V) == Instruction::BitCast) { 327 V = cast<Operator>(V)->getOperand(0); 328 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 329 if (GA->mayBeOverridden()) 330 return V; 331 V = GA->getAliasee(); 332 } else { 333 return V; 334 } 335 assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 336 } while (Visited.insert(V)); 337 338 return V; 339 } 340 341 /// isDereferenceablePointer - Test if this value is always a pointer to 342 /// allocated and suitably aligned memory for a simple load or store. 343 bool Value::isDereferenceablePointer() const { 344 // Note that it is not safe to speculate into a malloc'd region because 345 // malloc may return null. 346 // It's also not always safe to follow a bitcast, for example: 347 // bitcast i8* (alloca i8) to i32* 348 // would result in a 4-byte load from a 1-byte alloca. Some cases could 349 // be handled using TargetData to check sizes and alignments though. 350 351 // These are obviously ok. 352 if (isa<AllocaInst>(this)) return true; 353 354 // Global variables which can't collapse to null are ok. 355 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(this)) 356 return !GV->hasExternalWeakLinkage(); 357 358 // byval arguments are ok. 359 if (const Argument *A = dyn_cast<Argument>(this)) 360 return A->hasByValAttr(); 361 362 // For GEPs, determine if the indexing lands within the allocated object. 363 if (const GEPOperator *GEP = dyn_cast<GEPOperator>(this)) { 364 // Conservatively require that the base pointer be fully dereferenceable. 365 if (!GEP->getOperand(0)->isDereferenceablePointer()) 366 return false; 367 // Check the indices. 368 gep_type_iterator GTI = gep_type_begin(GEP); 369 for (User::const_op_iterator I = GEP->op_begin()+1, 370 E = GEP->op_end(); I != E; ++I) { 371 Value *Index = *I; 372 Type *Ty = *GTI++; 373 // Struct indices can't be out of bounds. 374 if (isa<StructType>(Ty)) 375 continue; 376 ConstantInt *CI = dyn_cast<ConstantInt>(Index); 377 if (!CI) 378 return false; 379 // Zero is always ok. 380 if (CI->isZero()) 381 continue; 382 // Check to see that it's within the bounds of an array. 383 ArrayType *ATy = dyn_cast<ArrayType>(Ty); 384 if (!ATy) 385 return false; 386 if (CI->getValue().getActiveBits() > 64) 387 return false; 388 if (CI->getZExtValue() >= ATy->getNumElements()) 389 return false; 390 } 391 // Indices check out; this is dereferenceable. 392 return true; 393 } 394 395 // If we don't know, assume the worst. 396 return false; 397 } 398 399 /// DoPHITranslation - If this value is a PHI node with CurBB as its parent, 400 /// return the value in the PHI node corresponding to PredBB. If not, return 401 /// ourself. This is useful if you want to know the value something has in a 402 /// predecessor block. 403 Value *Value::DoPHITranslation(const BasicBlock *CurBB, 404 const BasicBlock *PredBB) { 405 PHINode *PN = dyn_cast<PHINode>(this); 406 if (PN && PN->getParent() == CurBB) 407 return PN->getIncomingValueForBlock(PredBB); 408 return this; 409 } 410 411 LLVMContext &Value::getContext() const { return VTy->getContext(); } 412 413 //===----------------------------------------------------------------------===// 414 // ValueHandleBase Class 415 //===----------------------------------------------------------------------===// 416 417 /// AddToExistingUseList - Add this ValueHandle to the use list for VP, where 418 /// List is known to point into the existing use list. 419 void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) { 420 assert(List && "Handle list is null?"); 421 422 // Splice ourselves into the list. 423 Next = *List; 424 *List = this; 425 setPrevPtr(List); 426 if (Next) { 427 Next->setPrevPtr(&Next); 428 assert(VP == Next->VP && "Added to wrong list?"); 429 } 430 } 431 432 void ValueHandleBase::AddToExistingUseListAfter(ValueHandleBase *List) { 433 assert(List && "Must insert after existing node"); 434 435 Next = List->Next; 436 setPrevPtr(&List->Next); 437 List->Next = this; 438 if (Next) 439 Next->setPrevPtr(&Next); 440 } 441 442 /// AddToUseList - Add this ValueHandle to the use list for VP. 443 void ValueHandleBase::AddToUseList() { 444 assert(VP && "Null pointer doesn't have a use list!"); 445 446 LLVMContextImpl *pImpl = VP->getContext().pImpl; 447 448 if (VP->HasValueHandle) { 449 // If this value already has a ValueHandle, then it must be in the 450 // ValueHandles map already. 451 ValueHandleBase *&Entry = pImpl->ValueHandles[VP]; 452 assert(Entry != 0 && "Value doesn't have any handles?"); 453 AddToExistingUseList(&Entry); 454 return; 455 } 456 457 // Ok, it doesn't have any handles yet, so we must insert it into the 458 // DenseMap. However, doing this insertion could cause the DenseMap to 459 // reallocate itself, which would invalidate all of the PrevP pointers that 460 // point into the old table. Handle this by checking for reallocation and 461 // updating the stale pointers only if needed. 462 DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles; 463 const void *OldBucketPtr = Handles.getPointerIntoBucketsArray(); 464 465 ValueHandleBase *&Entry = Handles[VP]; 466 assert(Entry == 0 && "Value really did already have handles?"); 467 AddToExistingUseList(&Entry); 468 VP->HasValueHandle = true; 469 470 // If reallocation didn't happen or if this was the first insertion, don't 471 // walk the table. 472 if (Handles.isPointerIntoBucketsArray(OldBucketPtr) || 473 Handles.size() == 1) { 474 return; 475 } 476 477 // Okay, reallocation did happen. Fix the Prev Pointers. 478 for (DenseMap<Value*, ValueHandleBase*>::iterator I = Handles.begin(), 479 E = Handles.end(); I != E; ++I) { 480 assert(I->second && I->first == I->second->VP && "List invariant broken!"); 481 I->second->setPrevPtr(&I->second); 482 } 483 } 484 485 /// RemoveFromUseList - Remove this ValueHandle from its current use list. 486 void ValueHandleBase::RemoveFromUseList() { 487 assert(VP && VP->HasValueHandle && "Pointer doesn't have a use list!"); 488 489 // Unlink this from its use list. 490 ValueHandleBase **PrevPtr = getPrevPtr(); 491 assert(*PrevPtr == this && "List invariant broken"); 492 493 *PrevPtr = Next; 494 if (Next) { 495 assert(Next->getPrevPtr() == &Next && "List invariant broken"); 496 Next->setPrevPtr(PrevPtr); 497 return; 498 } 499 500 // If the Next pointer was null, then it is possible that this was the last 501 // ValueHandle watching VP. If so, delete its entry from the ValueHandles 502 // map. 503 LLVMContextImpl *pImpl = VP->getContext().pImpl; 504 DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles; 505 if (Handles.isPointerIntoBucketsArray(PrevPtr)) { 506 Handles.erase(VP); 507 VP->HasValueHandle = false; 508 } 509 } 510 511 512 void ValueHandleBase::ValueIsDeleted(Value *V) { 513 assert(V->HasValueHandle && "Should only be called if ValueHandles present"); 514 515 // Get the linked list base, which is guaranteed to exist since the 516 // HasValueHandle flag is set. 517 LLVMContextImpl *pImpl = V->getContext().pImpl; 518 ValueHandleBase *Entry = pImpl->ValueHandles[V]; 519 assert(Entry && "Value bit set but no entries exist"); 520 521 // We use a local ValueHandleBase as an iterator so that ValueHandles can add 522 // and remove themselves from the list without breaking our iteration. This 523 // is not really an AssertingVH; we just have to give ValueHandleBase a kind. 524 // Note that we deliberately do not the support the case when dropping a value 525 // handle results in a new value handle being permanently added to the list 526 // (as might occur in theory for CallbackVH's): the new value handle will not 527 // be processed and the checking code will mete out righteous punishment if 528 // the handle is still present once we have finished processing all the other 529 // value handles (it is fine to momentarily add then remove a value handle). 530 for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) { 531 Iterator.RemoveFromUseList(); 532 Iterator.AddToExistingUseListAfter(Entry); 533 assert(Entry->Next == &Iterator && "Loop invariant broken."); 534 535 switch (Entry->getKind()) { 536 case Assert: 537 break; 538 case Tracking: 539 // Mark that this value has been deleted by setting it to an invalid Value 540 // pointer. 541 Entry->operator=(DenseMapInfo<Value *>::getTombstoneKey()); 542 break; 543 case Weak: 544 // Weak just goes to null, which will unlink it from the list. 545 Entry->operator=(0); 546 break; 547 case Callback: 548 // Forward to the subclass's implementation. 549 static_cast<CallbackVH*>(Entry)->deleted(); 550 break; 551 } 552 } 553 554 // All callbacks, weak references, and assertingVHs should be dropped by now. 555 if (V->HasValueHandle) { 556 #ifndef NDEBUG // Only in +Asserts mode... 557 dbgs() << "While deleting: " << *V->getType() << " %" << V->getNameStr() 558 << "\n"; 559 if (pImpl->ValueHandles[V]->getKind() == Assert) 560 llvm_unreachable("An asserting value handle still pointed to this" 561 " value!"); 562 563 #endif 564 llvm_unreachable("All references to V were not removed?"); 565 } 566 } 567 568 569 void ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) { 570 assert(Old->HasValueHandle &&"Should only be called if ValueHandles present"); 571 assert(Old != New && "Changing value into itself!"); 572 573 // Get the linked list base, which is guaranteed to exist since the 574 // HasValueHandle flag is set. 575 LLVMContextImpl *pImpl = Old->getContext().pImpl; 576 ValueHandleBase *Entry = pImpl->ValueHandles[Old]; 577 578 assert(Entry && "Value bit set but no entries exist"); 579 580 // We use a local ValueHandleBase as an iterator so that 581 // ValueHandles can add and remove themselves from the list without 582 // breaking our iteration. This is not really an AssertingVH; we 583 // just have to give ValueHandleBase some kind. 584 for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) { 585 Iterator.RemoveFromUseList(); 586 Iterator.AddToExistingUseListAfter(Entry); 587 assert(Entry->Next == &Iterator && "Loop invariant broken."); 588 589 switch (Entry->getKind()) { 590 case Assert: 591 // Asserting handle does not follow RAUW implicitly. 592 break; 593 case Tracking: 594 // Tracking goes to new value like a WeakVH. Note that this may make it 595 // something incompatible with its templated type. We don't want to have a 596 // virtual (or inline) interface to handle this though, so instead we make 597 // the TrackingVH accessors guarantee that a client never sees this value. 598 599 // FALLTHROUGH 600 case Weak: 601 // Weak goes to the new value, which will unlink it from Old's list. 602 Entry->operator=(New); 603 break; 604 case Callback: 605 // Forward to the subclass's implementation. 606 static_cast<CallbackVH*>(Entry)->allUsesReplacedWith(New); 607 break; 608 } 609 } 610 611 #ifndef NDEBUG 612 // If any new tracking or weak value handles were added while processing the 613 // list, then complain about it now. 614 if (Old->HasValueHandle) 615 for (Entry = pImpl->ValueHandles[Old]; Entry; Entry = Entry->Next) 616 switch (Entry->getKind()) { 617 case Tracking: 618 case Weak: 619 dbgs() << "After RAUW from " << *Old->getType() << " %" 620 << Old->getNameStr() << " to " << *New->getType() << " %" 621 << New->getNameStr() << "\n"; 622 llvm_unreachable("A tracking or weak value handle still pointed to the" 623 " old value!\n"); 624 default: 625 break; 626 } 627 #endif 628 } 629 630 /// ~CallbackVH. Empty, but defined here to avoid emitting the vtable 631 /// more than once. 632 CallbackVH::~CallbackVH() {} 633