LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 // 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