LLVM API Documentation
00001 //===-- SymbolTable.cpp - Implement the SymbolTable class -----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and revised by Reid 00006 // Spencer. It is distributed under the University of Illinois Open Source 00007 // License. See LICENSE.TXT for details. 00008 // 00009 //===----------------------------------------------------------------------===// 00010 // 00011 // This file implements the SymbolTable class for the VMCore library. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/SymbolTable.h" 00016 #include "llvm/DerivedTypes.h" 00017 #include "llvm/Module.h" 00018 #include "llvm/ADT/StringExtras.h" 00019 #include <algorithm> 00020 #include <iostream> 00021 00022 using namespace llvm; 00023 00024 #define DEBUG_SYMBOL_TABLE 0 00025 #define DEBUG_ABSTYPE 0 00026 00027 SymbolTable::~SymbolTable() { 00028 // Drop all abstract type references in the type plane... 00029 for (type_iterator TI = tmap.begin(), TE = tmap.end(); TI != TE; ++TI) { 00030 if (TI->second->isAbstract()) // If abstract, drop the reference... 00031 cast<DerivedType>(TI->second)->removeAbstractTypeUser(this); 00032 } 00033 00034 // TODO: FIXME: BIG ONE: This doesn't unreference abstract types for the 00035 // planes that could still have entries! 00036 00037 #ifndef NDEBUG // Only do this in -g mode... 00038 bool LeftoverValues = true; 00039 for (plane_iterator PI = pmap.begin(); PI != pmap.end(); ++PI) { 00040 for (value_iterator VI = PI->second.begin(); VI != PI->second.end(); ++VI) 00041 if (!isa<Constant>(VI->second) ) { 00042 std::cerr << "Value still in symbol table! Type = '" 00043 << PI->first->getDescription() << "' Name = '" 00044 << VI->first << "'\n"; 00045 LeftoverValues = false; 00046 } 00047 } 00048 00049 assert(LeftoverValues && "Values remain in symbol table!"); 00050 #endif 00051 } 00052 00053 // getUniqueName - Given a base name, return a string that is either equal to 00054 // it (or derived from it) that does not already occur in the symbol table for 00055 // the specified type. 00056 // 00057 std::string SymbolTable::getUniqueName(const Type *Ty, 00058 const std::string &BaseName) const { 00059 // Find the plane 00060 plane_const_iterator PI = pmap.find(Ty); 00061 if (PI == pmap.end()) return BaseName; 00062 00063 std::string TryName = BaseName; 00064 const ValueMap& vmap = PI->second; 00065 value_const_iterator End = vmap.end(); 00066 00067 // See if the name exists 00068 while (vmap.find(TryName) != End) // Loop until we find a free 00069 TryName = BaseName + utostr(++LastUnique); // name in the symbol table 00070 return TryName; 00071 } 00072 00073 00074 // lookup a value - Returns null on failure... 00075 Value *SymbolTable::lookup(const Type *Ty, const std::string &Name) const { 00076 plane_const_iterator PI = pmap.find(Ty); 00077 if (PI != pmap.end()) { // We have symbols in that plane. 00078 value_const_iterator VI = PI->second.find(Name); 00079 if (VI != PI->second.end()) // and the name is in our hash table. 00080 return VI->second; 00081 } 00082 return 0; 00083 } 00084 00085 00086 // lookup a type by name - returns null on failure 00087 Type* SymbolTable::lookupType(const std::string& Name) const { 00088 type_const_iterator TI = tmap.find(Name); 00089 if (TI != tmap.end()) 00090 return const_cast<Type*>(TI->second); 00091 return 0; 00092 } 00093 00094 /// changeName - Given a value with a non-empty name, remove its existing entry 00095 /// from the symbol table and insert a new one for Name. This is equivalent to 00096 /// doing "remove(V), V->Name = Name, insert(V)", but is faster, and will not 00097 /// temporarily remove the symbol table plane if V is the last value in the 00098 /// symtab with that name (which could invalidate iterators to that plane). 00099 void SymbolTable::changeName(Value *V, const std::string &name) { 00100 assert(!V->getName().empty() && !name.empty() && V->getName() != name && 00101 "Illegal use of this method!"); 00102 00103 plane_iterator PI = pmap.find(V->getType()); 00104 assert(PI != pmap.end() && "Value doesn't have an entry in this table?"); 00105 ValueMap &VM = PI->second; 00106 00107 value_iterator VI = VM.find(V->getName()); 00108 assert(VI != VM.end() && "Value does have an entry in this table?"); 00109 00110 // Remove the old entry. 00111 VM.erase(VI); 00112 00113 // See if we can insert the new name. 00114 VI = VM.lower_bound(name); 00115 00116 // Is there a naming conflict? 00117 if (VI != VM.end() && VI->first == name) { 00118 V->Name = getUniqueName(V->getType(), name); 00119 VM.insert(make_pair(V->Name, V)); 00120 } else { 00121 V->Name = name; 00122 VM.insert(VI, make_pair(name, V)); 00123 } 00124 } 00125 00126 // Remove a value 00127 void SymbolTable::remove(Value *N) { 00128 assert(N->hasName() && "Value doesn't have name!"); 00129 00130 plane_iterator PI = pmap.find(N->getType()); 00131 assert(PI != pmap.end() && 00132 "Trying to remove a value that doesn't have a type plane yet!"); 00133 ValueMap &VM = PI->second; 00134 value_iterator Entry = VM.find(N->getName()); 00135 assert(Entry != VM.end() && "Invalid entry to remove!"); 00136 00137 #if DEBUG_SYMBOL_TABLE 00138 dump(); 00139 std::cerr << " Removing Value: " << Entry->second->getName() << "\n"; 00140 #endif 00141 00142 // Remove the value from the plane... 00143 VM.erase(Entry); 00144 00145 // If the plane is empty, remove it now! 00146 if (VM.empty()) { 00147 // If the plane represented an abstract type that we were interested in, 00148 // unlink ourselves from this plane. 00149 // 00150 if (N->getType()->isAbstract()) { 00151 #if DEBUG_ABSTYPE 00152 std::cerr << "Plane Empty: Removing type: " 00153 << N->getType()->getDescription() << "\n"; 00154 #endif 00155 cast<DerivedType>(N->getType())->removeAbstractTypeUser(this); 00156 } 00157 00158 pmap.erase(PI); 00159 } 00160 } 00161 00162 // remove - Remove a type from the symbol table... 00163 Type* SymbolTable::remove(type_iterator Entry) { 00164 assert(Entry != tmap.end() && "Invalid entry to remove!"); 00165 00166 const Type* Result = Entry->second; 00167 00168 #if DEBUG_SYMBOL_TABLE 00169 dump(); 00170 std::cerr << " Removing Value: " << Result->getName() << "\n"; 00171 #endif 00172 00173 tmap.erase(Entry); 00174 00175 // If we are removing an abstract type, remove the symbol table from it's use 00176 // list... 00177 if (Result->isAbstract()) { 00178 #if DEBUG_ABSTYPE 00179 std::cerr << "Removing abstract type from symtab" << Result->getDescription()<<"\n"; 00180 #endif 00181 cast<DerivedType>(Result)->removeAbstractTypeUser(this); 00182 } 00183 00184 return const_cast<Type*>(Result); 00185 } 00186 00187 00188 // insertEntry - Insert a value into the symbol table with the specified name. 00189 void SymbolTable::insertEntry(const std::string &Name, const Type *VTy, 00190 Value *V) { 00191 plane_iterator PI = pmap.find(VTy); // Plane iterator 00192 value_iterator VI; // Actual value iterator 00193 ValueMap *VM; // The plane we care about. 00194 00195 #if DEBUG_SYMBOL_TABLE 00196 dump(); 00197 std::cerr << " Inserting definition: " << Name << ": " 00198 << VTy->getDescription() << "\n"; 00199 #endif 00200 00201 if (PI == pmap.end()) { // Not in collection yet... insert dummy entry 00202 // Insert a new empty element. I points to the new elements. 00203 VM = &pmap.insert(make_pair(VTy, ValueMap())).first->second; 00204 VI = VM->end(); 00205 00206 // Check to see if the type is abstract. If so, it might be refined in the 00207 // future, which would cause the plane of the old type to get merged into 00208 // a new type plane. 00209 // 00210 if (VTy->isAbstract()) { 00211 cast<DerivedType>(VTy)->addAbstractTypeUser(this); 00212 #if DEBUG_ABSTYPE 00213 std::cerr << "Added abstract type value: " << VTy->getDescription() 00214 << "\n"; 00215 #endif 00216 } 00217 00218 } else { 00219 // Check to see if there is a naming conflict. If so, rename this value! 00220 VM = &PI->second; 00221 VI = VM->lower_bound(Name); 00222 if (VI != VM->end() && VI->first == Name) { 00223 V->Name = getUniqueName(VTy, Name); 00224 VM->insert(make_pair(V->Name, V)); 00225 return; 00226 } 00227 } 00228 00229 VM->insert(VI, make_pair(Name, V)); 00230 } 00231 00232 00233 // insertEntry - Insert a value into the symbol table with the specified 00234 // name... 00235 // 00236 void SymbolTable::insert(const std::string& Name, const Type* T) { 00237 assert(T && "Can't insert null type into symbol table!"); 00238 00239 // Check to see if there is a naming conflict. If so, rename this type! 00240 std::string UniqueName = Name; 00241 if (lookupType(Name)) 00242 UniqueName = getUniqueName(T, Name); 00243 00244 #if DEBUG_SYMBOL_TABLE 00245 dump(); 00246 std::cerr << " Inserting type: " << UniqueName << ": " 00247 << T->getDescription() << "\n"; 00248 #endif 00249 00250 // Insert the tmap entry 00251 tmap.insert(make_pair(UniqueName, T)); 00252 00253 // If we are adding an abstract type, add the symbol table to it's use list. 00254 if (T->isAbstract()) { 00255 cast<DerivedType>(T)->addAbstractTypeUser(this); 00256 #if DEBUG_ABSTYPE 00257 std::cerr << "Added abstract type to ST: " << T->getDescription() << "\n"; 00258 #endif 00259 } 00260 } 00261 00262 // Strip the symbol table of its names. 00263 bool SymbolTable::strip() { 00264 bool RemovedSymbol = false; 00265 for (plane_iterator I = pmap.begin(); I != pmap.end();) { 00266 // Removing items from the plane can cause the plane itself to get deleted. 00267 // If this happens, make sure we incremented our plane iterator already! 00268 ValueMap &Plane = (I++)->second; 00269 value_iterator B = Plane.begin(), Bend = Plane.end(); 00270 while (B != Bend) { // Found nonempty type plane! 00271 Value *V = B->second; 00272 ++B; 00273 if (!isa<GlobalValue>(V) || cast<GlobalValue>(V)->hasInternalLinkage()) { 00274 // Set name to "", removing from symbol table! 00275 V->setName(""); 00276 RemovedSymbol = true; 00277 } 00278 } 00279 } 00280 00281 for (type_iterator TI = tmap.begin(); TI != tmap.end(); ) { 00282 remove(TI++); 00283 RemovedSymbol = true; 00284 } 00285 00286 return RemovedSymbol; 00287 } 00288 00289 00290 // This function is called when one of the types in the type plane are refined 00291 void SymbolTable::refineAbstractType(const DerivedType *OldType, 00292 const Type *NewType) { 00293 00294 // Search to see if we have any values of the type Oldtype. If so, we need to 00295 // move them into the newtype plane... 00296 plane_iterator PI = pmap.find(OldType); 00297 if (PI != pmap.end()) { 00298 // Get a handle to the new type plane... 00299 plane_iterator NewTypeIt = pmap.find(NewType); 00300 if (NewTypeIt == pmap.end()) { // If no plane exists, add one 00301 NewTypeIt = pmap.insert(make_pair(NewType, ValueMap())).first; 00302 00303 if (NewType->isAbstract()) { 00304 cast<DerivedType>(NewType)->addAbstractTypeUser(this); 00305 #if DEBUG_ABSTYPE 00306 std::cerr << "[Added] refined to abstype: " << NewType->getDescription() 00307 << "\n"; 00308 #endif 00309 } 00310 } 00311 00312 ValueMap &NewPlane = NewTypeIt->second; 00313 ValueMap &OldPlane = PI->second; 00314 while (!OldPlane.empty()) { 00315 std::pair<const std::string, Value*> V = *OldPlane.begin(); 00316 00317 // Check to see if there is already a value in the symbol table that this 00318 // would collide with. 00319 value_iterator VI = NewPlane.find(V.first); 00320 if (VI != NewPlane.end() && VI->second == V.second) { 00321 // No action 00322 00323 } else if (VI != NewPlane.end()) { 00324 // The only thing we are allowing for now is two external global values 00325 // folded into one. 00326 // 00327 GlobalValue *ExistGV = dyn_cast<GlobalValue>(VI->second); 00328 GlobalValue *NewGV = dyn_cast<GlobalValue>(V.second); 00329 00330 if (ExistGV && NewGV) { 00331 assert((ExistGV->isExternal() || NewGV->isExternal()) && 00332 "Two planes folded together with overlapping value names!"); 00333 00334 // Make sure that ExistGV is the one we want to keep! 00335 if (!NewGV->isExternal()) 00336 std::swap(NewGV, ExistGV); 00337 00338 // Ok we have two external global values. Make all uses of the new 00339 // one use the old one... 00340 NewGV->uncheckedReplaceAllUsesWith(ExistGV); 00341 00342 // Update NewGV's name, we're about the remove it from the symbol 00343 // table. 00344 NewGV->Name = ""; 00345 00346 // Now we can remove this global from the module entirely... 00347 Module *M = NewGV->getParent(); 00348 if (Function *F = dyn_cast<Function>(NewGV)) 00349 M->getFunctionList().remove(F); 00350 else 00351 M->getGlobalList().remove(cast<GlobalVariable>(NewGV)); 00352 delete NewGV; 00353 } else { 00354 // If they are not global values, they must be just random values who 00355 // happen to conflict now that types have been resolved. If this is 00356 // the case, reinsert the value into the new plane, allowing it to get 00357 // renamed. 00358 assert(V.second->getType() == NewType &&"Type resolution is broken!"); 00359 insert(V.second); 00360 } 00361 } else { 00362 insertEntry(V.first, NewType, V.second); 00363 } 00364 // Remove the item from the old type plane 00365 OldPlane.erase(OldPlane.begin()); 00366 } 00367 00368 // Ok, now we are not referencing the type anymore... take me off your user 00369 // list please! 00370 #if DEBUG_ABSTYPE 00371 std::cerr << "Removing type " << OldType->getDescription() << "\n"; 00372 #endif 00373 OldType->removeAbstractTypeUser(this); 00374 00375 // Remove the plane that is no longer used 00376 pmap.erase(PI); 00377 } 00378 00379 // Loop over all of the types in the symbol table, replacing any references 00380 // to OldType with references to NewType. Note that there may be multiple 00381 // occurrences, and although we only need to remove one at a time, it's 00382 // faster to remove them all in one pass. 00383 // 00384 for (type_iterator I = type_begin(), E = type_end(); I != E; ++I) { 00385 if (I->second == (Type*)OldType) { // FIXME when Types aren't const. 00386 #if DEBUG_ABSTYPE 00387 std::cerr << "Removing type " << OldType->getDescription() << "\n"; 00388 #endif 00389 OldType->removeAbstractTypeUser(this); 00390 00391 I->second = (Type*)NewType; // TODO FIXME when types aren't const 00392 if (NewType->isAbstract()) { 00393 #if DEBUG_ABSTYPE 00394 std::cerr << "Added type " << NewType->getDescription() << "\n"; 00395 #endif 00396 cast<DerivedType>(NewType)->addAbstractTypeUser(this); 00397 } 00398 } 00399 } 00400 } 00401 00402 00403 // Handle situation where type becomes Concreate from Abstract 00404 void SymbolTable::typeBecameConcrete(const DerivedType *AbsTy) { 00405 plane_iterator PI = pmap.find(AbsTy); 00406 00407 // If there are any values in the symbol table of this type, then the type 00408 // plane is a use of the abstract type which must be dropped. 00409 if (PI != pmap.end()) 00410 AbsTy->removeAbstractTypeUser(this); 00411 00412 // Loop over all of the types in the symbol table, dropping any abstract 00413 // type user entries for AbsTy which occur because there are names for the 00414 // type. 00415 for (type_iterator TI = type_begin(), TE = type_end(); TI != TE; ++TI) 00416 if (TI->second == (Type*)AbsTy) // FIXME when Types aren't const. 00417 AbsTy->removeAbstractTypeUser(this); 00418 } 00419 00420 static void DumpVal(const std::pair<const std::string, Value *> &V) { 00421 std::cerr << " '" << V.first << "' = "; 00422 V.second->dump(); 00423 std::cerr << "\n"; 00424 } 00425 00426 static void DumpPlane(const std::pair<const Type *, 00427 std::map<const std::string, Value *> >&P){ 00428 P.first->dump(); 00429 std::cerr << "\n"; 00430 for_each(P.second.begin(), P.second.end(), DumpVal); 00431 } 00432 00433 static void DumpTypes(const std::pair<const std::string, const Type*>& T ) { 00434 std::cerr << " '" << T.first << "' = "; 00435 T.second->dump(); 00436 std::cerr << "\n"; 00437 } 00438 00439 void SymbolTable::dump() const { 00440 std::cerr << "Symbol table dump:\n Plane:"; 00441 for_each(pmap.begin(), pmap.end(), DumpPlane); 00442 std::cerr << " Types: "; 00443 for_each(tmap.begin(), tmap.end(), DumpTypes); 00444 } 00445 00446 // vim: sw=2 ai