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 // Remove a value 00095 void SymbolTable::remove(Value *N) { 00096 assert(N->hasName() && "Value doesn't have name!"); 00097 if (InternallyInconsistent) return; 00098 00099 plane_iterator PI = pmap.find(N->getType()); 00100 assert(PI != pmap.end() && 00101 "Trying to remove a value that doesn't have a type plane yet!"); 00102 removeEntry(PI, PI->second.find(N->getName())); 00103 } 00104 00105 00106 // removeEntry - Remove a value from the symbol table... 00107 Value *SymbolTable::removeEntry(plane_iterator Plane, value_iterator Entry) { 00108 if (InternallyInconsistent) return 0; 00109 assert(Plane != pmap.end() && 00110 Entry != Plane->second.end() && "Invalid entry to remove!"); 00111 00112 Value *Result = Entry->second; 00113 #if DEBUG_SYMBOL_TABLE 00114 dump(); 00115 std::cerr << " Removing Value: " << Result->getName() << "\n"; 00116 #endif 00117 00118 // Remove the value from the plane... 00119 Plane->second.erase(Entry); 00120 00121 // If the plane is empty, remove it now! 00122 if (Plane->second.empty()) { 00123 // If the plane represented an abstract type that we were interested in, 00124 // unlink ourselves from this plane. 00125 // 00126 if (Plane->first->isAbstract()) { 00127 #if DEBUG_ABSTYPE 00128 std::cerr << "Plane Empty: Removing type: " 00129 << Plane->first->getDescription() << "\n"; 00130 #endif 00131 cast<DerivedType>(Plane->first)->removeAbstractTypeUser(this); 00132 } 00133 00134 pmap.erase(Plane); 00135 } 00136 return Result; 00137 } 00138 00139 00140 // remove - Remove a type 00141 void SymbolTable::remove(const Type* Ty ) { 00142 type_iterator TI = this->type_begin(); 00143 type_iterator TE = this->type_end(); 00144 00145 // Search for the entry 00146 while ( TI != TE && TI->second != Ty ) 00147 ++TI; 00148 00149 if ( TI != TE ) 00150 this->removeEntry( TI ); 00151 } 00152 00153 00154 // removeEntry - Remove a type from the symbol table... 00155 Type* SymbolTable::removeEntry(type_iterator Entry) { 00156 if (InternallyInconsistent) return 0; 00157 assert( Entry != tmap.end() && "Invalid entry to remove!"); 00158 00159 const Type* Result = Entry->second; 00160 00161 #if DEBUG_SYMBOL_TABLE 00162 dump(); 00163 std::cerr << " Removing Value: " << Result->getName() << "\n"; 00164 #endif 00165 00166 tmap.erase(Entry); 00167 00168 // If we are removing an abstract type, remove the symbol table from it's use 00169 // list... 00170 if (Result->isAbstract()) { 00171 #if DEBUG_ABSTYPE 00172 std::cerr << "Removing abstract type from symtab" << Result->getDescription()<<"\n"; 00173 #endif 00174 cast<DerivedType>(Result)->removeAbstractTypeUser(this); 00175 } 00176 00177 return const_cast<Type*>(Result); 00178 } 00179 00180 00181 // insertEntry - Insert a value into the symbol table with the specified name. 00182 void SymbolTable::insertEntry(const std::string &Name, const Type *VTy, 00183 Value *V) { 00184 plane_iterator PI = pmap.find(VTy); // Plane iterator 00185 value_iterator VI; // Actual value iterator 00186 ValueMap *VM; // The plane we care about. 00187 00188 #if DEBUG_SYMBOL_TABLE 00189 dump(); 00190 std::cerr << " Inserting definition: " << Name << ": " 00191 << VTy->getDescription() << "\n"; 00192 #endif 00193 00194 if (PI == pmap.end()) { // Not in collection yet... insert dummy entry 00195 // Insert a new empty element. I points to the new elements. 00196 VM = &pmap.insert(make_pair(VTy, ValueMap())).first->second; 00197 VI = VM->end(); 00198 00199 // Check to see if the type is abstract. If so, it might be refined in the 00200 // future, which would cause the plane of the old type to get merged into 00201 // a new type plane. 00202 // 00203 if (VTy->isAbstract()) { 00204 cast<DerivedType>(VTy)->addAbstractTypeUser(this); 00205 #if DEBUG_ABSTYPE 00206 std::cerr << "Added abstract type value: " << VTy->getDescription() 00207 << "\n"; 00208 #endif 00209 } 00210 00211 } else { 00212 // Check to see if there is a naming conflict. If so, rename this value! 00213 VM = &PI->second; 00214 VI = VM->lower_bound(Name); 00215 if (VI != VM->end() && VI->first == Name) { 00216 std::string UniqueName = getUniqueName(VTy, Name); 00217 assert(InternallyInconsistent == false && 00218 "Infinite loop inserting value!"); 00219 InternallyInconsistent = true; 00220 V->setName(UniqueName, this); 00221 InternallyInconsistent = false; 00222 return; 00223 } 00224 } 00225 00226 VM->insert(VI, make_pair(Name, V)); 00227 } 00228 00229 00230 // insertEntry - Insert a value into the symbol table with the specified 00231 // name... 00232 // 00233 void SymbolTable::insertEntry(const std::string& Name, const Type* T) { 00234 00235 // Check to see if there is a naming conflict. If so, rename this type! 00236 std::string UniqueName = Name; 00237 if (lookupType(Name)) 00238 UniqueName = getUniqueName(T, Name); 00239 00240 #if DEBUG_SYMBOL_TABLE 00241 dump(); 00242 std::cerr << " Inserting type: " << UniqueName << ": " 00243 << T->getDescription() << "\n"; 00244 #endif 00245 00246 // Insert the tmap entry 00247 tmap.insert(make_pair(UniqueName, T)); 00248 00249 // If we are adding an abstract type, add the symbol table to it's use list. 00250 if (T->isAbstract()) { 00251 cast<DerivedType>(T)->addAbstractTypeUser(this); 00252 #if DEBUG_ABSTYPE 00253 std::cerr << "Added abstract type to ST: " << T->getDescription() << "\n"; 00254 #endif 00255 } 00256 } 00257 00258 00259 // Determine how many entries for a given type. 00260 unsigned SymbolTable::type_size(const Type *Ty) const { 00261 plane_const_iterator PI = pmap.find(Ty); 00262 if ( PI == pmap.end() ) return 0; 00263 return PI->second.size(); 00264 } 00265 00266 00267 // Get the name of a value 00268 std::string SymbolTable::get_name( const Value* V ) const { 00269 value_const_iterator VI = this->value_begin( V->getType() ); 00270 value_const_iterator VE = this->value_end( V->getType() ); 00271 00272 // Search for the entry 00273 while ( VI != VE && VI->second != V ) 00274 ++VI; 00275 00276 if ( VI != VE ) 00277 return VI->first; 00278 00279 return ""; 00280 } 00281 00282 00283 // Get the name of a type 00284 std::string SymbolTable::get_name( const Type* T ) const { 00285 if (tmap.empty()) return ""; // No types at all. 00286 00287 type_const_iterator TI = tmap.begin(); 00288 type_const_iterator TE = tmap.end(); 00289 00290 // Search for the entry 00291 while (TI != TE && TI->second != T ) 00292 ++TI; 00293 00294 if (TI != TE) // Must have found an entry! 00295 return TI->first; 00296 return ""; // Must not have found anything... 00297 } 00298 00299 00300 // Strip the symbol table of its names. 00301 bool SymbolTable::strip( void ) { 00302 bool RemovedSymbol = false; 00303 for (plane_iterator I = pmap.begin(); I != pmap.end();) { 00304 // Removing items from the plane can cause the plane itself to get deleted. 00305 // If this happens, make sure we incremented our plane iterator already! 00306 ValueMap &Plane = (I++)->second; 00307 value_iterator B = Plane.begin(), Bend = Plane.end(); 00308 while (B != Bend) { // Found nonempty type plane! 00309 Value *V = B->second; 00310 if (!isa<GlobalValue>(V) || cast<GlobalValue>(V)->hasInternalLinkage()){ 00311 // Set name to "", removing from symbol table! 00312 V->setName("", this); 00313 RemovedSymbol = true; 00314 } else if (isa<Constant>(V) ) { 00315 remove(V); 00316 RemovedSymbol = true; 00317 } 00318 ++B; 00319 } 00320 } 00321 00322 for (type_iterator TI = tmap.begin(); TI != tmap.end(); ) { 00323 const Type* T = (TI++)->second; 00324 remove(T); 00325 RemovedSymbol = true; 00326 } 00327 00328 return RemovedSymbol; 00329 } 00330 00331 00332 // This function is called when one of the types in the type plane are refined 00333 void SymbolTable::refineAbstractType(const DerivedType *OldType, 00334 const Type *NewType) { 00335 00336 // Search to see if we have any values of the type Oldtype. If so, we need to 00337 // move them into the newtype plane... 00338 plane_iterator PI = pmap.find(OldType); 00339 if (PI != pmap.end()) { 00340 // Get a handle to the new type plane... 00341 plane_iterator NewTypeIt = pmap.find(NewType); 00342 if (NewTypeIt == pmap.end()) { // If no plane exists, add one 00343 NewTypeIt = pmap.insert(make_pair(NewType, ValueMap())).first; 00344 00345 if (NewType->isAbstract()) { 00346 cast<DerivedType>(NewType)->addAbstractTypeUser(this); 00347 #if DEBUG_ABSTYPE 00348 std::cerr << "[Added] refined to abstype: " << NewType->getDescription() 00349 << "\n"; 00350 #endif 00351 } 00352 } 00353 00354 ValueMap &NewPlane = NewTypeIt->second; 00355 ValueMap &OldPlane = PI->second; 00356 while (!OldPlane.empty()) { 00357 std::pair<const std::string, Value*> V = *OldPlane.begin(); 00358 00359 // Check to see if there is already a value in the symbol table that this 00360 // would collide with. 00361 value_iterator VI = NewPlane.find(V.first); 00362 if (VI != NewPlane.end() && VI->second == V.second) { 00363 // No action 00364 00365 } else if (VI != NewPlane.end()) { 00366 // The only thing we are allowing for now is two external global values 00367 // folded into one. 00368 // 00369 GlobalValue *ExistGV = dyn_cast<GlobalValue>(VI->second); 00370 GlobalValue *NewGV = dyn_cast<GlobalValue>(V.second); 00371 00372 if (ExistGV && NewGV) { 00373 assert((ExistGV->isExternal() || NewGV->isExternal()) && 00374 "Two planes folded together with overlapping value names!"); 00375 00376 // Make sure that ExistGV is the one we want to keep! 00377 if (!NewGV->isExternal()) 00378 std::swap(NewGV, ExistGV); 00379 00380 // Ok we have two external global values. Make all uses of the new 00381 // one use the old one... 00382 NewGV->uncheckedReplaceAllUsesWith(ExistGV); 00383 00384 // Now we just convert it to an unnamed method... which won't get 00385 // added to our symbol table. The problem is that if we call 00386 // setName on the method that it will try to remove itself from 00387 // the symbol table and die... because it's not in the symtab 00388 // right now. To fix this, we have an internally consistent flag 00389 // that turns remove into a noop. Thus the name will get null'd 00390 // out, but the symbol table won't get upset. 00391 // 00392 assert(InternallyInconsistent == false && 00393 "Symbol table already inconsistent!"); 00394 InternallyInconsistent = true; 00395 00396 // Remove newM from the symtab 00397 NewGV->setName(""); 00398 InternallyInconsistent = false; 00399 00400 // Now we can remove this global from the module entirely... 00401 Module *M = NewGV->getParent(); 00402 if (Function *F = dyn_cast<Function>(NewGV)) 00403 M->getFunctionList().remove(F); 00404 else 00405 M->getGlobalList().remove(cast<GlobalVariable>(NewGV)); 00406 delete NewGV; 00407 } else { 00408 // If they are not global values, they must be just random values who 00409 // happen to conflict now that types have been resolved. If this is 00410 // the case, reinsert the value into the new plane, allowing it to get 00411 // renamed. 00412 assert(V.second->getType() == NewType &&"Type resolution is broken!"); 00413 insert(V.second); 00414 } 00415 } else { 00416 insertEntry(V.first, NewType, V.second); 00417 00418 } 00419 // Remove the item from the old type plane 00420 OldPlane.erase(OldPlane.begin()); 00421 } 00422 00423 // Ok, now we are not referencing the type anymore... take me off your user 00424 // list please! 00425 #if DEBUG_ABSTYPE 00426 std::cerr << "Removing type " << OldType->getDescription() << "\n"; 00427 #endif 00428 OldType->removeAbstractTypeUser(this); 00429 00430 // Remove the plane that is no longer used 00431 pmap.erase(PI); 00432 } 00433 00434 // Loop over all of the types in the symbol table, replacing any references 00435 // to OldType with references to NewType. Note that there may be multiple 00436 // occurrences, and although we only need to remove one at a time, it's 00437 // faster to remove them all in one pass. 00438 // 00439 for (type_iterator I = type_begin(), E = type_end(); I != E; ++I) { 00440 if (I->second == (Type*)OldType) { // FIXME when Types aren't const. 00441 #if DEBUG_ABSTYPE 00442 std::cerr << "Removing type " << OldType->getDescription() << "\n"; 00443 #endif 00444 OldType->removeAbstractTypeUser(this); 00445 00446 I->second = (Type*)NewType; // TODO FIXME when types aren't const 00447 if (NewType->isAbstract()) { 00448 #if DEBUG_ABSTYPE 00449 std::cerr << "Added type " << NewType->getDescription() << "\n"; 00450 #endif 00451 cast<DerivedType>(NewType)->addAbstractTypeUser(this); 00452 } 00453 } 00454 } 00455 } 00456 00457 00458 // Handle situation where type becomes Concreate from Abstract 00459 void SymbolTable::typeBecameConcrete(const DerivedType *AbsTy) { 00460 plane_iterator PI = pmap.find(AbsTy); 00461 00462 // If there are any values in the symbol table of this type, then the type 00463 // plane is a use of the abstract type which must be dropped. 00464 if (PI != pmap.end()) 00465 AbsTy->removeAbstractTypeUser(this); 00466 00467 // Loop over all of the types in the symbol table, dropping any abstract 00468 // type user entries for AbsTy which occur because there are names for the 00469 // type. 00470 for (type_iterator TI = type_begin(), TE = type_end(); TI != TE; ++TI) 00471 if (TI->second == (Type*)AbsTy) // FIXME when Types aren't const. 00472 AbsTy->removeAbstractTypeUser(this); 00473 } 00474 00475 static void DumpVal(const std::pair<const std::string, Value *> &V) { 00476 std::cerr << " '" << V.first << "' = "; 00477 V.second->dump(); 00478 std::cerr << "\n"; 00479 } 00480 00481 static void DumpPlane(const std::pair<const Type *, 00482 std::map<const std::string, Value *> >&P){ 00483 P.first->dump(); 00484 std::cerr << "\n"; 00485 for_each(P.second.begin(), P.second.end(), DumpVal); 00486 } 00487 00488 static void DumpTypes(const std::pair<const std::string, const Type*>& T ) { 00489 std::cerr << " '" << T.first << "' = "; 00490 T.second->dump(); 00491 std::cerr << "\n"; 00492 } 00493 00494 void SymbolTable::dump() const { 00495 std::cerr << "Symbol table dump:\n Plane:"; 00496 for_each(pmap.begin(), pmap.end(), DumpPlane); 00497 std::cerr << " Types: "; 00498 for_each(tmap.begin(), tmap.end(), DumpTypes); 00499 } 00500 00501 // vim: sw=2 ai