lib/VMCore/Value.cpp

   1 //===-- Value.cpp - Implement the Value class -----------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the Value and User classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Constant.h"
  15 #include "llvm/DerivedTypes.h"
  16 #include "llvm/InstrTypes.h"
  17 #include "llvm/Module.h"
  18 #include "llvm/ValueSymbolTable.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/LeakDetector.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/InlineAsm.h"
  23 #include "llvm/Instructions.h"
  24 #include "llvm/IntrinsicInst.h"
  25 #include "llvm/InstrTypes.h"
  26 #include <algorithm>
  27 using namespace llvm;
  28
  29 //===----------------------------------------------------------------------===//
  30 //                                Value Class
  31 //===----------------------------------------------------------------------===//
  32
  33 static inline const Type *checkType(const Type *Ty) {
  34   assert(Ty && "Value defined with a null type: Error!");
  35   return Ty;
  36 }
  37
  38 Value::Value(const Type *ty, unsigned scid)
  39   : SubclassID(scid), SubclassData(0), Ty(checkType(ty)),
  40     UseList(0), Name(0) {
  41   if (!isa<Constant>(this) && !isa<BasicBlock>(this))
  42     assert((Ty->isFirstClassType() || Ty == Type::VoidTy ||
  43            isa<OpaqueType>(ty)) &&
  44            "Cannot create non-first-class values except for constants!");
  45 }
  46
  47 Value::~Value()
  48 {
  49   switch(SubclassID)
  50   {
  51   case ArgumentVal:
  52     Argument::destroyThis(cast<Argument>(this));
  53     break;
  54   case BasicBlockVal:
  55     BasicBlock::destroyThis(cast<BasicBlock>(this));
  56     break;
  57   case FunctionVal:
  58     Function::destroyThis(cast<Function>(this));
  59     break;
  60   case GlobalAliasVal:
  61     GlobalAlias::destroyThis(cast<GlobalAlias>(this));
  62     break;
  63   case GlobalVariableVal:
  64     GlobalVariable::destroyThis(cast<GlobalVariable>(this));
  65     break;
  66   case UndefValueVal:
  67     UndefValue::destroyThis(cast<UndefValue>(this));
  68     break;
  69   case ConstantExprVal:
  70     {
  71       ConstantExpr* CE = dyn_cast<ConstantExpr>(this);
  72       if(CE->getOpcode() == Instruction::GetElementPtr)
  73       {
  74         GetElementPtrConstantExpr* GECE =
  75           dyn_cast<GetElementPtrConstantExpr>(CE);
  76         GetElementPtrConstantExpr::destroyThis(GECE);
  77       }
  78       else if(CE->getOpcode() == Instruction::ExtractElement)
  79       {
  80         ExtractElementConstantExpr* EECE =
  81           dyn_cast<ExtractElementConstantExpr>(CE);
  82         ExtractElementConstantExpr::destroyThis(EECE);
  83       }
  84       else if(CE->getOpcode() == Instruction::InsertElement)
  85       {
  86         InsertElementConstantExpr* IECE =
  87           dyn_cast<InsertElementConstantExpr>(CE);
  88         InsertElementConstantExpr::destroyThis(IECE);
  89       }
  90       else if(CE->getOpcode() == Instruction::Select)
  91       {
  92         SelectConstantExpr* SCE = dyn_cast<SelectConstantExpr>(CE);
  93         SelectConstantExpr::destroyThis(SCE);
  94       }
  95       else if(CE->getOpcode() == Instruction::ShuffleVector)
  96       {
  97         ShuffleVectorConstantExpr* SVCE =
  98           dyn_cast<ShuffleVectorConstantExpr>(CE);
  99         ShuffleVectorConstantExpr::destroyThis(SVCE);
 100       }
 101       else if(BinaryConstantExpr* BCE = dyn_cast<BinaryConstantExpr>(this))
 102         BinaryConstantExpr::destroyThis(BCE);
 103       else if(UnaryConstantExpr* UCE = dyn_cast<UnaryConstantExpr>(this))
 104         UnaryConstantExpr::destroyThis(UCE);
 105       else if(CompareConstantExpr* CCE = dyn_cast<CompareConstantExpr>(this))
 106         CompareConstantExpr::destroyThis(CCE);
 107       else
 108         assert(0 && "Unknown ConstantExpr-inherited class in ~Value.");
 109     }
 110     break;
 111   case ConstantAggregateZeroVal:
 112     ConstantAggregateZero::destroyThis(cast<ConstantAggregateZero>(this));
 113     break;
 114   case ConstantIntVal:
 115     ConstantInt::destroyThis(cast<ConstantInt>(this));
 116     break;
 117   case ConstantFPVal:
 118     ConstantFP::destroyThis(cast<ConstantFP>(this));
 119     break;
 120   case ConstantArrayVal:
 121     ConstantArray::destroyThis(cast<ConstantArray>(this));
 122     break;
 123   case ConstantStructVal:
 124     ConstantStruct::destroyThis(cast<ConstantStruct>(this));
 125     break;
 126   case ConstantVectorVal:
 127     ConstantVector::destroyThis(cast<ConstantVector>(this));
 128     break;
 129   case ConstantPointerNullVal:
 130     ConstantPointerNull::destroyThis(cast<ConstantPointerNull>(this));
 131     break;
 132   case InlineAsmVal:
 133     InlineAsm::destroyThis(cast<InlineAsm>(this));
 134     break;
 135
 136   default:
 137     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(this))
 138       BinaryOperator::destroyThis(BO);
 139     else if (CallInst *CI = dyn_cast<CallInst>(this))
 140     {
 141       if(IntrinsicInst* II = dyn_cast<IntrinsicInst>(this))
 142       {
 143         if(DbgInfoIntrinsic* DII = dyn_cast<DbgInfoIntrinsic>(this))
 144         {
 145           if(DbgDeclareInst* DDI = dyn_cast<DbgDeclareInst>(this))
 146             DbgDeclareInst::destroyThis(DDI);
 147           else if(DbgFuncStartInst* DFSI = dyn_cast<DbgFuncStartInst>(this))
 148             DbgFuncStartInst::destroyThis(DFSI);
 149           else if(DbgRegionEndInst* DREI = dyn_cast<DbgRegionEndInst>(this))
 150             DbgRegionEndInst::destroyThis(DREI);
 151           else if(DbgRegionStartInst* DRSI = dyn_cast<DbgRegionStartInst>(this))
 152             DbgRegionStartInst::destroyThis(DRSI);
 153           else if(DbgStopPointInst* DSPI = dyn_cast<DbgStopPointInst>(this))
 154             DbgStopPointInst::destroyThis(DSPI);
 155           else
 156             assert(0 && "Unknown DbgInfo-inherited class in ~Value.");
 157         }
 158         else if(MemIntrinsic* MI = dyn_cast<MemIntrinsic>(this))
 159         {
 160           if(MemCpyInst* MCI = dyn_cast<MemCpyInst>(this))
 161             MemCpyInst::destroyThis(MCI);
 162           else if(MemMoveInst* MMI = dyn_cast<MemMoveInst>(this))
 163             MemMoveInst::destroyThis(MMI);
 164           else if(MemSetInst* MSI = dyn_cast<MemSetInst>(this))
 165             MemSetInst::destroyThis(MSI);
 166           else
 167             assert(0 && "Unknown MemIntrinsic-inherited class in ~Value.");
 168         }
 169         else
 170           assert(0 && "Unknown IntrinsicInst-inherited class in ~Value.");
 171       }
 172       else
 173         assert(0 && "Unknown CallInst-inherited class in ~Value.");
 174     }
 175     else if (CmpInst *CI = dyn_cast<CmpInst>(this))
 176     {
 177       if (FCmpInst *FCI = dyn_cast<FCmpInst>(this))
 178         FCmpInst::destroyThis(FCI);
 179       else if (ICmpInst *ICI = dyn_cast<ICmpInst>(this))
 180         ICmpInst::destroyThis(ICI);
 181       else
 182         assert(0 && "Unknown CmpInst-inherited class in ~Value.");
 183     }
 184     else if (ExtractElementInst *EEI = dyn_cast<ExtractElementInst>(this))
 185       ExtractElementInst::destroyThis(EEI);
 186     else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(this))
 187       GetElementPtrInst::destroyThis(GEP);
 188     else if (InsertElementInst* IE = dyn_cast<InsertElementInst>(this))
 189       InsertElementInst::destroyThis(IE);
 190     else if (PHINode *PN = dyn_cast<PHINode>(this))
 191       PHINode::destroyThis(PN);
 192     else if (SelectInst *SI = dyn_cast<SelectInst>(this))
 193       SelectInst::destroyThis(SI);
 194     else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(this))
 195       ShuffleVectorInst::destroyThis(SVI);
 196     else if (StoreInst *SI = dyn_cast<StoreInst>(this))
 197       StoreInst::destroyThis(SI);
 198     else if (TerminatorInst *TI = dyn_cast<TerminatorInst>(this))
 199     {
 200       if (BranchInst* BI = dyn_cast<BranchInst>(this))
 201         BranchInst::destroyThis(BI);
 202       else if (InvokeInst* II = dyn_cast<InvokeInst>(this))
 203         InvokeInst::destroyThis(II);
 204       else if (ReturnInst* RI = dyn_cast<ReturnInst>(this))
 205         ReturnInst::destroyThis(RI);
 206       else if (SwitchInst *SI = dyn_cast<SwitchInst>(this))
 207         SwitchInst::destroyThis(SI);
 208       else if (UnreachableInst *UI = dyn_cast<UnreachableInst>(this))
 209         UnreachableInst::destroyThis(UI);
 210       else if (UnwindInst *UI = dyn_cast<UnwindInst>(this))
 211         UnwindInst::destroyThis(UI);
 212       else
 213         assert(0 && "Unknown TerminatorInst-inherited class in ~Value.");
 214     }
 215     else if(UnaryInstruction* UI = dyn_cast<UnaryInstruction>(this))
 216     {
 217       if(AllocationInst* AI = dyn_cast<AllocationInst>(this))
 218       {
 219         if(AllocaInst* AI = dyn_cast<AllocaInst>(this))
 220           AllocaInst::destroyThis(AI);
 221         else if(MallocInst* MI = dyn_cast<MallocInst>(this))
 222           MallocInst::destroyThis(MI);
 223         else
 224           assert(0 && "Unknown AllocationInst-inherited class in ~Value.");
 225       }
 226       else if(CastInst* CI = dyn_cast<CastInst>(this))
 227       {
 228         if(BitCastInst* BCI = dyn_cast<BitCastInst>(this))
 229           BitCastInst::destroyThis(BCI);
 230         else if(FPExtInst* FPEI = dyn_cast<FPExtInst>(this))
 231           FPExtInst::destroyThis(FPEI);
 232         else if(FPToSIInst* FPSII = dyn_cast<FPToSIInst>(this))
 233           FPToSIInst::destroyThis(FPSII);
 234         else if(FPToUIInst* FPUII = dyn_cast<FPToUIInst>(this))
 235           FPToUIInst::destroyThis(FPUII);
 236         else if(FPTruncInst* FPTI = dyn_cast<FPTruncInst>(this))
 237           FPTruncInst::destroyThis(FPTI);
 238         else if(IntToPtrInst* I2PI = dyn_cast<IntToPtrInst>(this))
 239           IntToPtrInst::destroyThis(I2PI);
 240         else if(PtrToIntInst* P2II = dyn_cast<PtrToIntInst>(this))
 241           PtrToIntInst::destroyThis(P2II);
 242         else if(SExtInst* SEI = dyn_cast<SExtInst>(this))
 243           SExtInst::destroyThis(SEI);
 244         else if(SIToFPInst* SIFPI = dyn_cast<SIToFPInst>(this))
 245           SIToFPInst::destroyThis(SIFPI);
 246         else if(TruncInst* TI = dyn_cast<TruncInst>(this))
 247           TruncInst::destroyThis(TI);
 248         else if(UIToFPInst* UIFPI = dyn_cast<UIToFPInst>(this))
 249           UIToFPInst::destroyThis(UIFPI);
 250         else if(ZExtInst* ZEI = dyn_cast<ZExtInst>(this))
 251           ZExtInst::destroyThis(ZEI);
 252         else
 253           assert(0 && "Unknown CastInst-inherited class in ~Value.");
 254       }
 255       else if(FreeInst* FI = dyn_cast<FreeInst>(this))
 256         FreeInst::destroyThis(FI);
 257       else if(LoadInst* LI = dyn_cast<LoadInst>(this))
 258         LoadInst::destroyThis(LI);
 259       else if(VAArgInst* VAI = dyn_cast<VAArgInst>(this))
 260         VAArgInst::destroyThis(VAI);
 261       else
 262         assert(0 && "Unknown UnaryInstruction-inherited class in ~Value.");
 263     }
 264     else if (DummyInst *DI = dyn_cast<DummyInst>(this))
 265       DummyInst::destroyThis(DI);
 266     else
 267       assert(0 && "Unknown Instruction-inherited class in ~Value.");
 268     break;
 269   }
 270 }
 271
 272 void Value::destroyThis(Value*v)
 273 {
 274 #ifndef NDEBUG      // Only in -g mode...
 275   // Check to make sure that there are no uses of this value that are still
 276   // around when the value is destroyed.  If there are, then we have a dangling
 277   // reference and something is wrong.  This code is here to print out what is
 278   // still being referenced.  The value in question should be printed as
 279   // a <badref>
 280   //
 281   if (!v->use_empty()) {
 282     DOUT << "While deleting: " << *v->Ty << " %" << v->Name << "\n";
 283     for (use_iterator I = v->use_begin(), E = v->use_end(); I != E; ++I)
 284       DOUT << "Use still stuck around after Def is destroyed:"
 285            << **I << "\n";
 286   }
 287 #endif
 288   assert(v->use_empty() && "Uses remain when a value is destroyed!");
 289
 290   // If this value is named, destroy the name.  This should not be in a symtab
 291   // at this point.
 292   if (v->Name)
 293     v->Name->Destroy();
 294
 295   // There should be no uses of this object anymore, remove it.
 296   LeakDetector::removeGarbageObject(v);
 297 }
 298
 299 /// hasNUses - Return true if this Value has exactly N users.
 300 ///
 301 bool Value::hasNUses(unsigned N) const {
 302   use_const_iterator UI = use_begin(), E = use_end();
 303
 304   for (; N; --N, ++UI)
 305     if (UI == E) return false;  // Too few.
 306   return UI == E;
 307 }
 308
 309 /// hasNUsesOrMore - Return true if this value has N users or more.  This is
 310 /// logically equivalent to getNumUses() >= N.
 311 ///
 312 bool Value::hasNUsesOrMore(unsigned N) const {
 313   use_const_iterator UI = use_begin(), E = use_end();
 314
 315   for (; N; --N, ++UI)
 316     if (UI == E) return false;  // Too few.
 317
 318   return true;
 319 }
 320
 321
 322 /// getNumUses - This method computes the number of uses of this Value.  This
 323 /// is a linear time operation.  Use hasOneUse or hasNUses to check for specific
 324 /// values.
 325 unsigned Value::getNumUses() const {
 326   return (unsigned)std::distance(use_begin(), use_end());
 327 }
 328
 329 static bool getSymTab(Value *V, ValueSymbolTable *&ST) {
 330   ST = 0;
 331   if (Instruction *I = dyn_cast<Instruction>(V)) {
 332     if (BasicBlock *P = I->getParent())
 333       if (Function *PP = P->getParent())
 334         ST = &PP->getValueSymbolTable();
 335   } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
 336     if (Function *P = BB->getParent())
 337       ST = &P->getValueSymbolTable();
 338   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 339     if (Module *P = GV->getParent())
 340       ST = &P->getValueSymbolTable();
 341   } else if (Argument *A = dyn_cast<Argument>(V)) {
 342     if (Function *P = A->getParent())
 343       ST = &P->getValueSymbolTable();
 344   } else {
 345     assert(isa<Constant>(V) && "Unknown value type!");
 346     return true;  // no name is setable for this.
 347   }
 348   return false;
 349 }
 350
 351 /// getNameStart - Return a pointer to a null terminated string for this name.
 352 /// Note that names can have null characters within the string as well as at
 353 /// their end.  This always returns a non-null pointer.
 354 const char *Value::getNameStart() const {
 355   if (Name == 0) return "";
 356   return Name->getKeyData();
 357 }
 358
 359 /// getNameLen - Return the length of the string, correctly handling nul
 360 /// characters embedded into them.
 361 unsigned Value::getNameLen() const {
 362   return Name ? Name->getKeyLength() : 0;
 363 }
 364
 365
 366 std::string Value::getNameStr() const {
 367   if (Name == 0) return "";
 368   return std::string(Name->getKeyData(),
 369                      Name->getKeyData()+Name->getKeyLength());
 370 }
 371
 372 void Value::setName(const std::string &name) {
 373   setName(&name[0], name.size());
 374 }
 375
 376 void Value::setName(const char *Name) {
 377   setName(Name, Name ? strlen(Name) : 0);
 378 }
 379
 380 void Value::setName(const char *NameStr, unsigned NameLen) {
 381   if (NameLen == 0 && !hasName()) return;
 382   assert(getType() != Type::VoidTy && "Cannot assign a name to void values!");
 383
 384   // Get the symbol table to update for this object.
 385   ValueSymbolTable *ST;
 386   if (getSymTab(this, ST))
 387     return;  // Cannot set a name on this value (e.g. constant).
 388
 389   if (!ST) { // No symbol table to update?  Just do the change.
 390     if (NameLen == 0) {
 391       // Free the name for this value.
 392       Name->Destroy();
 393       Name = 0;
 394       return;
 395     }
 396
 397     if (Name) {
 398       // Name isn't changing?
 399       if (NameLen == Name->getKeyLength() &&
 400           !memcmp(Name->getKeyData(), NameStr, NameLen))
 401         return;
 402       Name->Destroy();
 403     }
 404
 405     // NOTE: Could optimize for the case the name is shrinking to not deallocate
 406     // then reallocated.
 407
 408     // Create the new name.
 409     Name = ValueName::Create(NameStr, NameStr+NameLen);
 410     Name->setValue(this);
 411     return;
 412   }
 413
 414   // NOTE: Could optimize for the case the name is shrinking to not deallocate
 415   // then reallocated.
 416   if (hasName()) {
 417     // Name isn't changing?
 418     if (NameLen == Name->getKeyLength() &&
 419         !memcmp(Name->getKeyData(), NameStr, NameLen))
 420       return;
 421
 422     // Remove old name.
 423     ST->removeValueName(Name);
 424     Name->Destroy();
 425     Name = 0;
 426
 427     if (NameLen == 0)
 428       return;
 429   }
 430
 431   // Name is changing to something new.
 432   Name = ST->createValueName(NameStr, NameLen, this);
 433 }
 434
 435
 436 /// takeName - transfer the name from V to this value, setting V's name to
 437 /// empty.  It is an error to call V->takeName(V).
 438 void Value::takeName(Value *V) {
 439   ValueSymbolTable *ST = 0;
 440   // If this value has a name, drop it.
 441   if (hasName()) {
 442     // Get the symtab this is in.
 443     if (getSymTab(this, ST)) {
 444       // We can't set a name on this value, but we need to clear V's name if
 445       // it has one.
 446       if (V->hasName()) V->setName(0, 0);
 447       return;  // Cannot set a name on this value (e.g. constant).
 448     }
 449
 450     // Remove old name.
 451     if (ST)
 452       ST->removeValueName(Name);
 453     Name->Destroy();
 454     Name = 0;
 455   }
 456
 457   // Now we know that this has no name.
 458
 459   // If V has no name either, we're done.
 460   if (!V->hasName()) return;
 461
 462   // Get this's symtab if we didn't before.
 463   if (!ST) {
 464     if (getSymTab(this, ST)) {
 465       // Clear V's name.
 466       V->setName(0, 0);
 467       return;  // Cannot set a name on this value (e.g. constant).
 468     }
 469   }
 470
 471   // Get V's ST, this should always succed, because V has a name.
 472   ValueSymbolTable *VST;
 473   bool Failure = getSymTab(V, VST);
 474   assert(!Failure && "V has a name, so it should have a ST!");
 475
 476   // If these values are both in the same symtab, we can do this very fast.
 477   // This works even if both values have no symtab yet.
 478   if (ST == VST) {
 479     // Take the name!
 480     Name = V->Name;
 481     V->Name = 0;
 482     Name->setValue(this);
 483     return;
 484   }
 485
 486   // Otherwise, things are slightly more complex.  Remove V's name from VST and
 487   // then reinsert it into ST.
 488
 489   if (VST)
 490     VST->removeValueName(V->Name);
 491   Name = V->Name;
 492   V->Name = 0;
 493   Name->setValue(this);
 494
 495   if (ST)
 496     ST->reinsertValue(this);
 497 }
 498
 499
 500 // uncheckedReplaceAllUsesWith - This is exactly the same as replaceAllUsesWith,
 501 // except that it doesn't have all of the asserts.  The asserts fail because we
 502 // are half-way done resolving types, which causes some types to exist as two
 503 // different Type*'s at the same time.  This is a sledgehammer to work around
 504 // this problem.
 505 //
 506 void Value::uncheckedReplaceAllUsesWith(Value *New) {
 507   while (!use_empty()) {
 508     Use &U = *UseList;
 509     // Must handle Constants specially, we cannot call replaceUsesOfWith on a
 510     // constant because they are uniqued.
 511     if (Constant *C = dyn_cast<Constant>(U.getUser())) {
 512       if (!isa<GlobalValue>(C)) {
 513         C->replaceUsesOfWithOnConstant(this, New, &U);
 514         continue;
 515       }
 516     }
 517
 518     U.set(New);
 519   }
 520 }
 521
 522 void Value::replaceAllUsesWith(Value *New) {
 523   assert(New && "Value::replaceAllUsesWith(<null>) is invalid!");
 524   assert(New != this && "this->replaceAllUsesWith(this) is NOT valid!");
 525   assert(New->getType() == getType() &&
 526          "replaceAllUses of value with new value of different type!");
 527
 528   uncheckedReplaceAllUsesWith(New);
 529 }
 530
 531 //===----------------------------------------------------------------------===//
 532 //                                 User Class
 533 //===----------------------------------------------------------------------===//
 534
 535 // replaceUsesOfWith - Replaces all references to the "From" definition with
 536 // references to the "To" definition.
 537 //
 538 void User::replaceUsesOfWith(Value *From, Value *To) {
 539   if (From == To) return;   // Duh what?
 540
 541   assert(!isa<Constant>(this) || isa<GlobalValue>(this) &&
 542          "Cannot call User::replaceUsesofWith on a constant!");
 543
 544   for (unsigned i = 0, E = getNumOperands(); i != E; ++i)
 545     if (getOperand(i) == From) {  // Is This operand is pointing to oldval?
 546       // The side effects of this setOperand call include linking to
 547       // "To", adding "this" to the uses list of To, and
 548       // most importantly, removing "this" from the use list of "From".
 549       setOperand(i, To); // Fix it now...
 550     }
 551 }
 552