Value.cpp revision 6f4266506bca785828bacda55bd5db9172f990c6
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 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/Module.h" 20#include "llvm/ValueSymbolTable.h" 21#include "llvm/Support/Debug.h" 22#include "llvm/Support/LeakDetector.h" 23#include <algorithm> 24using namespace llvm; 25 26//===----------------------------------------------------------------------===// 27// Value Class 28//===----------------------------------------------------------------------===// 29 30static inline const Type *checkType(const Type *Ty) { 31 assert(Ty && "Value defined with a null type: Error!"); 32 return Ty; 33} 34 35Value::Value(const Type *ty, unsigned scid) 36 : SubclassID(scid), SubclassData(0), VTy(checkType(ty)), 37 UseList(0), Name(0) { 38 if (isa<CallInst>(this) || isa<InvokeInst>(this)) 39 assert((VTy->isFirstClassType() || VTy == Type::VoidTy || 40 isa<OpaqueType>(ty) || VTy->getTypeID() == Type::StructTyID) && 41 "invalid CallInst type!"); 42 else if (!isa<Constant>(this) && !isa<BasicBlock>(this)) 43 assert((VTy->isFirstClassType() || VTy == Type::VoidTy || 44 isa<OpaqueType>(ty)) && 45 "Cannot create non-first-class values except for constants!"); 46} 47 48Value::~Value() { 49#ifndef NDEBUG // Only in -g mode... 50 // Check to make sure that there are no uses of this value that are still 51 // around when the value is destroyed. If there are, then we have a dangling 52 // reference and something is wrong. This code is here to print out what is 53 // still being referenced. The value in question should be printed as 54 // a <badref> 55 // 56 if (!use_empty()) { 57 DOUT << "While deleting: " << *VTy << " %" << getNameStr() << "\n"; 58 for (use_iterator I = use_begin(), E = use_end(); I != E; ++I) 59 DOUT << "Use still stuck around after Def is destroyed:" 60 << **I << "\n"; 61 } 62#endif 63 assert(use_empty() && "Uses remain when a value is destroyed!"); 64 65 // If this value is named, destroy the name. This should not be in a symtab 66 // at this point. 67 if (Name) 68 Name->Destroy(); 69 70 // There should be no uses of this object anymore, remove it. 71 LeakDetector::removeGarbageObject(this); 72} 73 74/// hasNUses - Return true if this Value has exactly N users. 75/// 76bool Value::hasNUses(unsigned N) const { 77 use_const_iterator UI = use_begin(), E = use_end(); 78 79 for (; N; --N, ++UI) 80 if (UI == E) return false; // Too few. 81 return UI == E; 82} 83 84/// hasNUsesOrMore - Return true if this value has N users or more. This is 85/// logically equivalent to getNumUses() >= N. 86/// 87bool Value::hasNUsesOrMore(unsigned N) const { 88 use_const_iterator UI = use_begin(), E = use_end(); 89 90 for (; N; --N, ++UI) 91 if (UI == E) return false; // Too few. 92 93 return true; 94} 95 96/// isUsedInBasicBlock - Return true if this value is used in the specified 97/// basic block. 98bool Value::isUsedInBasicBlock(BasicBlock *BB) const { 99 for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I) { 100 const Instruction *User = dyn_cast<Instruction>(*I); 101 if (User && User->getParent() == BB) 102 return true; 103 } 104 return false; 105} 106 107 108/// getNumUses - This method computes the number of uses of this Value. This 109/// is a linear time operation. Use hasOneUse or hasNUses to check for specific 110/// values. 111unsigned Value::getNumUses() const { 112 return (unsigned)std::distance(use_begin(), use_end()); 113} 114 115static bool getSymTab(Value *V, ValueSymbolTable *&ST) { 116 ST = 0; 117 if (Instruction *I = dyn_cast<Instruction>(V)) { 118 if (BasicBlock *P = I->getParent()) 119 if (Function *PP = P->getParent()) 120 ST = &PP->getValueSymbolTable(); 121 } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 122 if (Function *P = BB->getParent()) 123 ST = &P->getValueSymbolTable(); 124 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 125 if (Module *P = GV->getParent()) 126 ST = &P->getValueSymbolTable(); 127 } else if (Argument *A = dyn_cast<Argument>(V)) { 128 if (Function *P = A->getParent()) 129 ST = &P->getValueSymbolTable(); 130 } else { 131 assert(isa<Constant>(V) && "Unknown value type!"); 132 return true; // no name is setable for this. 133 } 134 return false; 135} 136 137/// getNameStart - Return a pointer to a null terminated string for this name. 138/// Note that names can have null characters within the string as well as at 139/// their end. This always returns a non-null pointer. 140const char *Value::getNameStart() const { 141 if (Name == 0) return ""; 142 return Name->getKeyData(); 143} 144 145/// getNameLen - Return the length of the string, correctly handling nul 146/// characters embedded into them. 147unsigned Value::getNameLen() const { 148 return Name ? Name->getKeyLength() : 0; 149} 150 151/// isName - Return true if this value has the name specified by the provided 152/// nul terminated string. 153bool Value::isName(const char *N) const { 154 unsigned InLen = strlen(N); 155 return InLen == getNameLen() && memcmp(getNameStart(), N, InLen) == 0; 156} 157 158 159std::string Value::getNameStr() const { 160 if (Name == 0) return ""; 161 return std::string(Name->getKeyData(), 162 Name->getKeyData()+Name->getKeyLength()); 163} 164 165void Value::setName(const std::string &name) { 166 setName(&name[0], name.size()); 167} 168 169void Value::setName(const char *Name) { 170 setName(Name, Name ? strlen(Name) : 0); 171} 172 173void Value::setName(const char *NameStr, unsigned NameLen) { 174 if (NameLen == 0 && !hasName()) return; 175 assert(getType() != Type::VoidTy && "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 (NameLen == 0) { 184 // Free the name for this value. 185 Name->Destroy(); 186 Name = 0; 187 return; 188 } 189 190 if (Name) { 191 // Name isn't changing? 192 if (NameLen == Name->getKeyLength() && 193 !memcmp(Name->getKeyData(), NameStr, NameLen)) 194 return; 195 Name->Destroy(); 196 } 197 198 // NOTE: Could optimize for the case the name is shrinking to not deallocate 199 // then reallocated. 200 201 // Create the new name. 202 Name = ValueName::Create(NameStr, NameStr+NameLen); 203 Name->setValue(this); 204 return; 205 } 206 207 // NOTE: Could optimize for the case the name is shrinking to not deallocate 208 // then reallocated. 209 if (hasName()) { 210 // Name isn't changing? 211 if (NameLen == Name->getKeyLength() && 212 !memcmp(Name->getKeyData(), NameStr, NameLen)) 213 return; 214 215 // Remove old name. 216 ST->removeValueName(Name); 217 Name->Destroy(); 218 Name = 0; 219 220 if (NameLen == 0) 221 return; 222 } 223 224 // Name is changing to something new. 225 Name = ST->createValueName(NameStr, NameLen, this); 226} 227 228 229/// takeName - transfer the name from V to this value, setting V's name to 230/// empty. It is an error to call V->takeName(V). 231void Value::takeName(Value *V) { 232 ValueSymbolTable *ST = 0; 233 // If this value has a name, drop it. 234 if (hasName()) { 235 // Get the symtab this is in. 236 if (getSymTab(this, ST)) { 237 // We can't set a name on this value, but we need to clear V's name if 238 // it has one. 239 if (V->hasName()) V->setName(0, 0); 240 return; // Cannot set a name on this value (e.g. constant). 241 } 242 243 // Remove old name. 244 if (ST) 245 ST->removeValueName(Name); 246 Name->Destroy(); 247 Name = 0; 248 } 249 250 // Now we know that this has no name. 251 252 // If V has no name either, we're done. 253 if (!V->hasName()) return; 254 255 // Get this's symtab if we didn't before. 256 if (!ST) { 257 if (getSymTab(this, ST)) { 258 // Clear V's name. 259 V->setName(0, 0); 260 return; // Cannot set a name on this value (e.g. constant). 261 } 262 } 263 264 // Get V's ST, this should always succed, because V has a name. 265 ValueSymbolTable *VST; 266 bool Failure = getSymTab(V, VST); 267 assert(!Failure && "V has a name, so it should have a ST!"); Failure=Failure; 268 269 // If these values are both in the same symtab, we can do this very fast. 270 // This works even if both values have no symtab yet. 271 if (ST == VST) { 272 // Take the name! 273 Name = V->Name; 274 V->Name = 0; 275 Name->setValue(this); 276 return; 277 } 278 279 // Otherwise, things are slightly more complex. Remove V's name from VST and 280 // then reinsert it into ST. 281 282 if (VST) 283 VST->removeValueName(V->Name); 284 Name = V->Name; 285 V->Name = 0; 286 Name->setValue(this); 287 288 if (ST) 289 ST->reinsertValue(this); 290} 291 292 293// uncheckedReplaceAllUsesWith - This is exactly the same as replaceAllUsesWith, 294// except that it doesn't have all of the asserts. The asserts fail because we 295// are half-way done resolving types, which causes some types to exist as two 296// different Type*'s at the same time. This is a sledgehammer to work around 297// this problem. 298// 299void Value::uncheckedReplaceAllUsesWith(Value *New) { 300 while (!use_empty()) { 301 Use &U = *UseList; 302 // Must handle Constants specially, we cannot call replaceUsesOfWith on a 303 // constant because they are uniqued. 304 if (Constant *C = dyn_cast<Constant>(U.getUser())) { 305 if (!isa<GlobalValue>(C)) { 306 C->replaceUsesOfWithOnConstant(this, New, &U); 307 continue; 308 } 309 } 310 311 U.set(New); 312 } 313} 314 315void Value::replaceAllUsesWith(Value *New) { 316 assert(New && "Value::replaceAllUsesWith(<null>) is invalid!"); 317 assert(New != this && "this->replaceAllUsesWith(this) is NOT valid!"); 318 assert(New->getType() == getType() && 319 "replaceAllUses of value with new value of different type!"); 320 321 uncheckedReplaceAllUsesWith(New); 322} 323 324Value *Value::stripPointerCasts() { 325 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(this)) { 326 if (CE->getOpcode() == Instruction::BitCast) { 327 if (isa<PointerType>(CE->getOperand(0)->getType())) 328 return CE->getOperand(0)->stripPointerCasts(); 329 } else if (CE->getOpcode() == Instruction::GetElementPtr) { 330 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 331 if (!CE->getOperand(i)->isNullValue()) 332 return this; 333 return CE->getOperand(0)->stripPointerCasts(); 334 } 335 return this; 336 } 337 338 if (BitCastInst *CI = dyn_cast<BitCastInst>(this)) { 339 if (isa<PointerType>(CI->getOperand(0)->getType())) 340 return CI->getOperand(0)->stripPointerCasts(); 341 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(this)) { 342 if (GEP->hasAllZeroIndices()) 343 return GEP->getOperand(0)->stripPointerCasts(); 344 } 345 return this; 346} 347 348//===----------------------------------------------------------------------===// 349// User Class 350//===----------------------------------------------------------------------===// 351 352// replaceUsesOfWith - Replaces all references to the "From" definition with 353// references to the "To" definition. 354// 355void User::replaceUsesOfWith(Value *From, Value *To) { 356 if (From == To) return; // Duh what? 357 358 assert((!isa<Constant>(this) || isa<GlobalValue>(this)) && 359 "Cannot call User::replaceUsesofWith on a constant!"); 360 361 for (unsigned i = 0, E = getNumOperands(); i != E; ++i) 362 if (getOperand(i) == From) { // Is This operand is pointing to oldval? 363 // The side effects of this setOperand call include linking to 364 // "To", adding "this" to the uses list of To, and 365 // most importantly, removing "this" from the use list of "From". 366 setOperand(i, To); // Fix it now... 367 } 368} 369 370void *User::operator new(size_t s, unsigned Us) { 371 void *Storage = ::operator new(s + sizeof(Use) * Us); 372 Use *Start = static_cast<Use*>(Storage); 373 Use *End = Start + Us; 374 User *Obj = reinterpret_cast<User*>(End); 375 Obj->OperandList = Start; 376 Obj->NumOperands = Us; 377 Use::initTags(Start, End); 378 return Obj; 379} 380 381void User::operator delete(void *Usr) { 382 User *Start = static_cast<User*>(Usr); 383 Use *Storage = static_cast<Use*>(Usr) - Start->NumOperands; 384 ::operator delete(Storage == Start->OperandList 385 ? Storage 386 : Usr); 387} 388