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       CallInst::destroyThis(CI);
 141     else if (CmpInst *CI = dyn_cast<CmpInst>(this))
 142     {
 143       if (FCmpInst *FCI = dyn_cast<FCmpInst>(CI))
 144         FCmpInst::destroyThis(FCI);
 145       else if (ICmpInst *ICI = dyn_cast<ICmpInst>(CI))
 146         ICmpInst::destroyThis(ICI);
 147       else
 148         assert(0 && "Unknown CmpInst-inherited class in ~Value.");
 149     }
 150     else if (ExtractElementInst *EEI = dyn_cast<ExtractElementInst>(this))
 151       ExtractElementInst::destroyThis(EEI);
 152     else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(this))
 153       GetElementPtrInst::destroyThis(GEP);
 154     else if (InsertElementInst* IE = dyn_cast<InsertElementInst>(this))
 155       InsertElementInst::destroyThis(IE);
 156     else if (PHINode *PN = dyn_cast<PHINode>(this))
 157       PHINode::destroyThis(PN);
 158     else if (SelectInst *SI = dyn_cast<SelectInst>(this))
 159       SelectInst::destroyThis(SI);
 160     else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(this))
 161       ShuffleVectorInst::destroyThis(SVI);
 162     else if (StoreInst *SI = dyn_cast<StoreInst>(this))
 163       StoreInst::destroyThis(SI);
 164     else if (TerminatorInst *TI = dyn_cast<TerminatorInst>(this))
 165     {
 166       if (BranchInst* BI = dyn_cast<BranchInst>(TI))
 167         BranchInst::destroyThis(BI);
 168       else if (InvokeInst* II = dyn_cast<InvokeInst>(TI))
 169         InvokeInst::destroyThis(II);
 170       else if (ReturnInst* RI = dyn_cast<ReturnInst>(TI))
 171         ReturnInst::destroyThis(RI);
 172       else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
 173         SwitchInst::destroyThis(SI);
 174       else if (UnreachableInst *UI = dyn_cast<UnreachableInst>(TI))
 175         UnreachableInst::destroyThis(UI);
 176       else if (UnwindInst *UI = dyn_cast<UnwindInst>(TI))
 177         UnwindInst::destroyThis(UI);
 178       else
 179         assert(0 && "Unknown TerminatorInst-inherited class in ~Value.");
 180     } else if(UnaryInstruction* UI = dyn_cast<UnaryInstruction>(this)) {
 181       if(AllocationInst* AI = dyn_cast<AllocationInst>(UI)) {
 182         if(AllocaInst* AI = dyn_cast<AllocaInst>(UI))
 183           AllocaInst::destroyThis(AI);
 184         else if(MallocInst* MI = dyn_cast<MallocInst>(UI))
 185           MallocInst::destroyThis(MI);
 186         else
 187           assert(0 && "Unknown AllocationInst-inherited class in ~Value.");
 188       } else if(CastInst* CI = dyn_cast<CastInst>(this)) {
 189         if(BitCastInst* BCI = dyn_cast<BitCastInst>(CI))
 190           BitCastInst::destroyThis(BCI);
 191         else if(FPExtInst* FPEI = dyn_cast<FPExtInst>(CI))
 192           FPExtInst::destroyThis(FPEI);
 193         else if(FPToSIInst* FPSII = dyn_cast<FPToSIInst>(CI))
 194           FPToSIInst::destroyThis(FPSII);
 195         else if(FPToUIInst* FPUII = dyn_cast<FPToUIInst>(CI))
 196           FPToUIInst::destroyThis(FPUII);
 197         else if(FPTruncInst* FPTI = dyn_cast<FPTruncInst>(CI))
 198           FPTruncInst::destroyThis(FPTI);
 199         else if(IntToPtrInst* I2PI = dyn_cast<IntToPtrInst>(CI))
 200           IntToPtrInst::destroyThis(I2PI);
 201         else if(PtrToIntInst* P2II = dyn_cast<PtrToIntInst>(CI))
 202           PtrToIntInst::destroyThis(P2II);
 203         else if(SExtInst* SEI = dyn_cast<SExtInst>(CI))
 204           SExtInst::destroyThis(SEI);
 205         else if(SIToFPInst* SIFPI = dyn_cast<SIToFPInst>(CI))
 206           SIToFPInst::destroyThis(SIFPI);
 207         else if(TruncInst* TI = dyn_cast<TruncInst>(CI))
 208           TruncInst::destroyThis(TI);
 209         else if(UIToFPInst* UIFPI = dyn_cast<UIToFPInst>(CI))
 210           UIToFPInst::destroyThis(UIFPI);
 211         else if(ZExtInst* ZEI = dyn_cast<ZExtInst>(CI))
 212           ZExtInst::destroyThis(ZEI);
 213         else
 214           assert(0 && "Unknown CastInst-inherited class in ~Value.");
 215       }
 216       else if(FreeInst* FI = dyn_cast<FreeInst>(this))
 217         FreeInst::destroyThis(FI);
 218       else if(LoadInst* LI = dyn_cast<LoadInst>(this))
 219         LoadInst::destroyThis(LI);
 220       else if(VAArgInst* VAI = dyn_cast<VAArgInst>(this))
 221         VAArgInst::destroyThis(VAI);
 222       else
 223         assert(0 && "Unknown UnaryInstruction-inherited class in ~Value.");
 224     }
 225     else if (DummyInst *DI = dyn_cast<DummyInst>(this))
 226       DummyInst::destroyThis(DI);
 227     else
 228       assert(0 && "Unknown Instruction-inherited class in ~Value.");
 229     break;
 230   }
 231 }
 232
 233 void Value::destroyThis(Value*v)
 234 {
 235 #ifndef NDEBUG      // Only in -g mode...
 236   // Check to make sure that there are no uses of this value that are still
 237   // around when the value is destroyed.  If there are, then we have a dangling
 238   // reference and something is wrong.  This code is here to print out what is
 239   // still being referenced.  The value in question should be printed as
 240   // a <badref>
 241   //
 242   if (!v->use_empty()) {
 243     DOUT << "While deleting: " << *v->Ty << " %" << v->Name << "\n";
 244     for (use_iterator I = v->use_begin(), E = v->use_end(); I != E; ++I)
 245       DOUT << "Use still stuck around after Def is destroyed:"
 246            << **I << "\n";
 247   }
 248 #endif
 249   assert(v->use_empty() && "Uses remain when a value is destroyed!");
 250
 251   // If this value is named, destroy the name.  This should not be in a symtab
 252   // at this point.
 253   if (v->Name)
 254     v->Name->Destroy();
 255
 256   // There should be no uses of this object anymore, remove it.
 257   LeakDetector::removeGarbageObject(v);
 258 }
 259
 260 /// hasNUses - Return true if this Value has exactly N users.
 261 ///
 262 bool Value::hasNUses(unsigned N) const {
 263   use_const_iterator UI = use_begin(), E = use_end();
 264
 265   for (; N; --N, ++UI)
 266     if (UI == E) return false;  // Too few.
 267   return UI == E;
 268 }
 269
 270 /// hasNUsesOrMore - Return true if this value has N users or more.  This is
 271 /// logically equivalent to getNumUses() >= N.
 272 ///
 273 bool Value::hasNUsesOrMore(unsigned N) const {
 274   use_const_iterator UI = use_begin(), E = use_end();
 275
 276   for (; N; --N, ++UI)
 277     if (UI == E) return false;  // Too few.
 278
 279   return true;
 280 }
 281
 282
 283 /// getNumUses - This method computes the number of uses of this Value.  This
 284 /// is a linear time operation.  Use hasOneUse or hasNUses to check for specific
 285 /// values.
 286 unsigned Value::getNumUses() const {
 287   return (unsigned)std::distance(use_begin(), use_end());
 288 }
 289
 290 static bool getSymTab(Value *V, ValueSymbolTable *&ST) {
 291   ST = 0;
 292   if (Instruction *I = dyn_cast<Instruction>(V)) {
 293     if (BasicBlock *P = I->getParent())
 294       if (Function *PP = P->getParent())
 295         ST = &PP->getValueSymbolTable();
 296   } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
 297     if (Function *P = BB->getParent())
 298       ST = &P->getValueSymbolTable();
 299   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 300     if (Module *P = GV->getParent())
 301       ST = &P->getValueSymbolTable();
 302   } else if (Argument *A = dyn_cast<Argument>(V)) {
 303     if (Function *P = A->getParent())
 304       ST = &P->getValueSymbolTable();
 305   } else {
 306     assert(isa<Constant>(V) && "Unknown value type!");
 307     return true;  // no name is setable for this.
 308   }
 309   return false;
 310 }
 311
 312 /// getNameStart - Return a pointer to a null terminated string for this name.
 313 /// Note that names can have null characters within the string as well as at
 314 /// their end.  This always returns a non-null pointer.
 315 const char *Value::getNameStart() const {
 316   if (Name == 0) return "";
 317   return Name->getKeyData();
 318 }
 319
 320 /// getNameLen - Return the length of the string, correctly handling nul
 321 /// characters embedded into them.
 322 unsigned Value::getNameLen() const {
 323   return Name ? Name->getKeyLength() : 0;
 324 }
 325
 326
 327 std::string Value::getNameStr() const {
 328   if (Name == 0) return "";
 329   return std::string(Name->getKeyData(),
 330                      Name->getKeyData()+Name->getKeyLength());
 331 }
 332
 333 void Value::setName(const std::string &name) {
 334   setName(&name[0], name.size());
 335 }
 336
 337 void Value::setName(const char *Name) {
 338   setName(Name, Name ? strlen(Name) : 0);
 339 }
 340
 341 void Value::setName(const char *NameStr, unsigned NameLen) {
 342   if (NameLen == 0 && !hasName()) return;
 343   assert(getType() != Type::VoidTy && "Cannot assign a name to void values!");
 344
 345   // Get the symbol table to update for this object.
 346   ValueSymbolTable *ST;
 347   if (getSymTab(this, ST))
 348     return;  // Cannot set a name on this value (e.g. constant).
 349
 350   if (!ST) { // No symbol table to update?  Just do the change.
 351     if (NameLen == 0) {
 352       // Free the name for this value.
 353       Name->Destroy();
 354       Name = 0;
 355       return;
 356     }
 357
 358     if (Name) {
 359       // Name isn't changing?
 360       if (NameLen == Name->getKeyLength() &&
 361           !memcmp(Name->getKeyData(), NameStr, NameLen))
 362         return;
 363       Name->Destroy();
 364     }
 365
 366     // NOTE: Could optimize for the case the name is shrinking to not deallocate
 367     // then reallocated.
 368
 369     // Create the new name.
 370     Name = ValueName::Create(NameStr, NameStr+NameLen);
 371     Name->setValue(this);
 372     return;
 373   }
 374
 375   // NOTE: Could optimize for the case the name is shrinking to not deallocate
 376   // then reallocated.
 377   if (hasName()) {
 378     // Name isn't changing?
 379     if (NameLen == Name->getKeyLength() &&
 380         !memcmp(Name->getKeyData(), NameStr, NameLen))
 381       return;
 382
 383     // Remove old name.
 384     ST->removeValueName(Name);
 385     Name->Destroy();
 386     Name = 0;
 387
 388     if (NameLen == 0)
 389       return;
 390   }
 391
 392   // Name is changing to something new.
 393   Name = ST->createValueName(NameStr, NameLen, this);
 394 }
 395
 396
 397 /// takeName - transfer the name from V to this value, setting V's name to
 398 /// empty.  It is an error to call V->takeName(V).
 399 void Value::takeName(Value *V) {
 400   ValueSymbolTable *ST = 0;
 401   // If this value has a name, drop it.
 402   if (hasName()) {
 403     // Get the symtab this is in.
 404     if (getSymTab(this, ST)) {
 405       // We can't set a name on this value, but we need to clear V's name if
 406       // it has one.
 407       if (V->hasName()) V->setName(0, 0);
 408       return;  // Cannot set a name on this value (e.g. constant).
 409     }
 410
 411     // Remove old name.
 412     if (ST)
 413       ST->removeValueName(Name);
 414     Name->Destroy();
 415     Name = 0;
 416   }
 417
 418   // Now we know that this has no name.
 419
 420   // If V has no name either, we're done.
 421   if (!V->hasName()) return;
 422
 423   // Get this's symtab if we didn't before.
 424   if (!ST) {
 425     if (getSymTab(this, ST)) {
 426       // Clear V's name.
 427       V->setName(0, 0);
 428       return;  // Cannot set a name on this value (e.g. constant).
 429     }
 430   }
 431
 432   // Get V's ST, this should always succed, because V has a name.
 433   ValueSymbolTable *VST;
 434   bool Failure = getSymTab(V, VST);
 435   assert(!Failure && "V has a name, so it should have a ST!");
 436
 437   // If these values are both in the same symtab, we can do this very fast.
 438   // This works even if both values have no symtab yet.
 439   if (ST == VST) {
 440     // Take the name!
 441     Name = V->Name;
 442     V->Name = 0;
 443     Name->setValue(this);
 444     return;
 445   }
 446
 447   // Otherwise, things are slightly more complex.  Remove V's name from VST and
 448   // then reinsert it into ST.
 449
 450   if (VST)
 451     VST->removeValueName(V->Name);
 452   Name = V->Name;
 453   V->Name = 0;
 454   Name->setValue(this);
 455
 456   if (ST)
 457     ST->reinsertValue(this);
 458 }
 459
 460
 461 // uncheckedReplaceAllUsesWith - This is exactly the same as replaceAllUsesWith,
 462 // except that it doesn't have all of the asserts.  The asserts fail because we
 463 // are half-way done resolving types, which causes some types to exist as two
 464 // different Type*'s at the same time.  This is a sledgehammer to work around
 465 // this problem.
 466 //
 467 void Value::uncheckedReplaceAllUsesWith(Value *New) {
 468   while (!use_empty()) {
 469     Use &U = *UseList;
 470     // Must handle Constants specially, we cannot call replaceUsesOfWith on a
 471     // constant because they are uniqued.
 472     if (Constant *C = dyn_cast<Constant>(U.getUser())) {
 473       if (!isa<GlobalValue>(C)) {
 474         C->replaceUsesOfWithOnConstant(this, New, &U);
 475         continue;
 476       }
 477     }
 478
 479     U.set(New);
 480   }
 481 }
 482
 483 void Value::replaceAllUsesWith(Value *New) {
 484   assert(New && "Value::replaceAllUsesWith(<null>) is invalid!");
 485   assert(New != this && "this->replaceAllUsesWith(this) is NOT valid!");
 486   assert(New->getType() == getType() &&
 487          "replaceAllUses of value with new value of different type!");
 488
 489   uncheckedReplaceAllUsesWith(New);
 490 }
 491
 492 //===----------------------------------------------------------------------===//
 493 //                                 User Class
 494 //===----------------------------------------------------------------------===//
 495
 496 // replaceUsesOfWith - Replaces all references to the "From" definition with
 497 // references to the "To" definition.
 498 //
 499 void User::replaceUsesOfWith(Value *From, Value *To) {
 500   if (From == To) return;   // Duh what?
 501
 502   assert(!isa<Constant>(this) || isa<GlobalValue>(this) &&
 503          "Cannot call User::replaceUsesofWith on a constant!");
 504
 505   for (unsigned i = 0, E = getNumOperands(); i != E; ++i)
 506     if (getOperand(i) == From) {  // Is This operand is pointing to oldval?
 507       // The side effects of this setOperand call include linking to
 508       // "To", adding "this" to the uses list of To, and
 509       // most importantly, removing "this" from the use list of "From".
 510       setOperand(i, To); // Fix it now...
 511     }
 512 }
 513