LLVM API Documentation

SymbolTable.cpp

Go to the documentation of this file.
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