lib/VMCore/Value.cpp

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