lib/VMCore/SymbolTable.cpp

   1 //===-- SymbolTable.cpp - Implement the SymbolTable class -------------------=//
   2 //
   3 // This file implements the SymbolTable class for the VMCore library.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/SymbolTable.h"
   8 #include "llvm/InstrTypes.h"
   9 #include "llvm/DerivedTypes.h"
  10 #include "llvm/Module.h"
  11 #include "llvm/Method.h"
  12 #include "Support/StringExtras.h"
  13
  14 #define DEBUG_SYMBOL_TABLE 0
  15 #define DEBUG_ABSTYPE 0
  16
  17 SymbolTable::~SymbolTable() {
  18   // Drop all abstract type references in the type plane...
  19   iterator TyPlane = find(Type::TypeTy);
  20   if (TyPlane != end()) {
  21     VarMap &TyP = TyPlane->second;
  22     for (VarMap::iterator I = TyP.begin(), E = TyP.end(); I != E; ++I) {
  23       const Type *Ty = cast<const Type>(I->second);
  24       if (Ty->isAbstract())   // If abstract, drop the reference...
  25         cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
  26     }
  27   }
  28
  29  // TODO: FIXME: BIG ONE: This doesn't unreference abstract types for the planes
  30  // that could still have entries!
  31
  32 #ifndef NDEBUG   // Only do this in -g mode...
  33   bool LeftoverValues = true;
  34   for (iterator i = begin(); i != end(); ++i) {
  35     for (type_iterator I = i->second.begin(); I != i->second.end(); ++I)
  36       if (!isa<Constant>(I->second) && !isa<Type>(I->second)) {
  37         cerr << "Value still in symbol table! Type = '"
  38              << i->first->getDescription() << "' Name = '" << I->first << "'\n";
  39         LeftoverValues = false;
  40       }
  41   }
  42
  43   assert(LeftoverValues && "Values remain in symbol table!");
  44 #endif
  45 }
  46
  47 // getUniqueName - Given a base name, return a string that is either equal to
  48 // it (or derived from it) that does not already occur in the symbol table for
  49 // the specified type.
  50 //
  51 string SymbolTable::getUniqueName(const Type *Ty, const string &BaseName) {
  52   iterator I = find(Ty);
  53   if (I == end()) return BaseName;
  54
  55   string TryName = BaseName;
  56   unsigned Counter = 0;
  57   type_iterator End = I->second.end();
  58
  59   while (I->second.find(TryName) != End)     // Loop until we find unoccupied
  60     TryName = BaseName + utostr(++Counter);  // Name in the symbol table
  61   return TryName;
  62 }
  63
  64
  65
  66 // lookup - Returns null on failure...
  67 Value *SymbolTable::lookup(const Type *Ty, const string &Name) {
  68   iterator I = find(Ty);
  69   if (I != end()) {                      // We have symbols in that plane...
  70     type_iterator J = I->second.find(Name);
  71     if (J != I->second.end())            // and the name is in our hash table...
  72       return J->second;
  73   }
  74
  75   return ParentSymTab ? ParentSymTab->lookup(Ty, Name) : 0;
  76 }
  77
  78 void SymbolTable::remove(Value *N) {
  79   assert(N->hasName() && "Value doesn't have name!");
  80
  81   iterator I = find(N->getType());
  82   removeEntry(I, I->second.find(N->getName()));
  83 }
  84
  85 // removeEntry - Remove a value from the symbol table...
  86 //
  87 Value *SymbolTable::removeEntry(iterator Plane, type_iterator Entry) {
  88   if (InternallyInconsistent) return 0;
  89   assert(Plane != super::end() &&
  90          Entry != Plane->second.end() && "Invalid entry to remove!");
  91
  92   Value *Result = Entry->second;
  93   const Type *Ty = Result->getType();
  94 #if DEBUG_SYMBOL_TABLE
  95   cerr << this << " Removing Value: " << Result->getName() << endl;
  96 #endif
  97
  98   // Remove the value from the plane...
  99   Plane->second.erase(Entry);
 100
 101   // If the plane is empty, remove it now!
 102   if (Plane->second.empty()) {
 103     // If the plane represented an abstract type that we were interested in,
 104     // unlink ourselves from this plane.
 105     //
 106     if (Plane->first->isAbstract()) {
 107 #if DEBUG_ABSTYPE
 108       cerr << "Plane Empty: Removing type: " << Plane->first->getDescription()
 109            << endl;
 110 #endif
 111       cast<DerivedType>(Plane->first)->removeAbstractTypeUser(this);
 112     }
 113
 114     erase(Plane);
 115   }
 116
 117   // If we are removing an abstract type, remove the symbol table from it's use
 118   // list...
 119   if (Ty == Type::TypeTy) {
 120     const Type *T = cast<const Type>(Result);
 121     if (T->isAbstract()) {
 122 #if DEBUG_ABSTYPE
 123       cerr << "Removing abs type from symtab" << T->getDescription() << endl;
 124 #endif
 125       cast<DerivedType>(T)->removeAbstractTypeUser(this);
 126     }
 127   }
 128
 129   return Result;
 130 }
 131
 132 // insertEntry - Insert a value into the symbol table with the specified
 133 // name...
 134 //
 135 void SymbolTable::insertEntry(const string &Name, const Type *VTy, Value *V) {
 136   // Check to see if there is a naming conflict.  If so, rename this value!
 137   if (lookup(VTy, Name)) {
 138     string UniqueName = getUniqueName(VTy, Name);
 139     InternallyInconsistent = true;
 140     V->setName(UniqueName, this);
 141     InternallyInconsistent = false;
 142     return;
 143   }
 144
 145 #if DEBUG_SYMBOL_TABLE
 146   cerr << this << " Inserting definition: " << Name << ": "
 147        << VTy->getDescription() << endl;
 148 #endif
 149
 150   iterator I = find(VTy);
 151   if (I == end()) {      // Not in collection yet... insert dummy entry
 152     // Insert a new empty element.  I points to the new elements.
 153     I = super::insert(make_pair(VTy, VarMap())).first;
 154     assert(I != end() && "How did insert fail?");
 155
 156     // Check to see if the type is abstract.  If so, it might be refined in the
 157     // future, which would cause the plane of the old type to get merged into
 158     // a new type plane.
 159     //
 160     if (VTy->isAbstract()) {
 161       cast<DerivedType>(VTy)->addAbstractTypeUser(this);
 162 #if DEBUG_ABSTYPE
 163       cerr << "Added abstract type value: " << VTy->getDescription() << endl;
 164 #endif
 165     }
 166   }
 167
 168   I->second.insert(make_pair(Name, V));
 169
 170   // If we are adding an abstract type, add the symbol table to it's use list.
 171   if (VTy == Type::TypeTy) {
 172     const Type *T = cast<const Type>(V);
 173     if (T->isAbstract()) {
 174       cast<DerivedType>(T)->addAbstractTypeUser(this);
 175 #if DEBUG_ABSTYPE
 176       cerr << "Added abstract type to ST: " << T->getDescription() << endl;
 177 #endif
 178     }
 179   }
 180 }
 181
 182 // This function is called when one of the types in the type plane are refined
 183 void SymbolTable::refineAbstractType(const DerivedType *OldType,
 184                                      const Type *NewType) {
 185   if (OldType == NewType && OldType->isAbstract())
 186     return;  // Noop, don't waste time dinking around
 187
 188   // Search to see if we have any values of the type oldtype.  If so, we need to
 189   // move them into the newtype plane...
 190   iterator TPI = find(OldType);
 191   if (OldType != NewType && TPI != end()) {
 192     // Get a handle to the new type plane...
 193     iterator NewTypeIt = find(NewType);
 194     if (NewTypeIt == super::end()) {      // If no plane exists, add one
 195       NewTypeIt = super::insert(make_pair(NewType, VarMap())).first;
 196
 197       if (NewType->isAbstract()) {
 198         cast<DerivedType>(NewType)->addAbstractTypeUser(this);
 199 #if DEBUG_ABSTYPE
 200         cerr << "[Added] refined to abstype: "<<NewType->getDescription()<<endl;
 201 #endif
 202     }
 203   }
 204
 205     VarMap &NewPlane = NewTypeIt->second;
 206     VarMap &OldPlane = TPI->second;
 207     while (!OldPlane.empty()) {
 208       pair<const string, Value*> V = *OldPlane.begin();
 209
 210       // Check to see if there is already a value in the symbol table that this
 211       // would collide with.
 212       type_iterator TI = NewPlane.find(V.first);
 213       if (TI != NewPlane.end() && TI->second == V.second) {
 214         // No action
 215
 216       } else if (TI != NewPlane.end()) {
 217         // The only thing we are allowing for now is two method prototypes being
 218         // folded into one.
 219         //
 220         Method *ExistM = dyn_cast<Method>(TI->second);
 221         Method *NewM = dyn_cast<Method>(V.second);
 222
 223         if (ExistM && NewM && ExistM->isExternal() && NewM->isExternal()) {
 224           // Ok we have two external methods.  Make all uses of the new one
 225           // use the old one...
 226           //
 227           NewM->replaceAllUsesWith(ExistM);
 228
 229           // Now we just convert it to an unnamed method... which won't get
 230           // added to our symbol table.  The problem is that if we call
 231           // setName on the method that it will try to remove itself from
 232           // the symbol table and die... because it's not in the symtab
 233           // right now.  To fix this, we have an internally consistent flag
 234           // that turns remove into a noop.  Thus the name will get null'd
 235           // out, but the symbol table won't get upset.
 236           //
 237           InternallyInconsistent = true;
 238
 239           // Remove newM from the symtab
 240           NewM->setName("");
 241           InternallyInconsistent = false;
 242
 243           // Now we can remove this method from the module entirely...
 244           NewM->getParent()->getMethodList().remove(NewM);
 245           delete NewM;
 246
 247         } else {
 248           assert(0 && "Two ploanes folded together with overlapping "
 249                  "value names!");
 250         }
 251       } else {
 252         insertEntry(V.first, NewType, V.second);
 253
 254       }
 255       // Remove the item from the old type plane
 256       OldPlane.erase(OldPlane.begin());
 257     }
 258
 259     // Ok, now we are not referencing the type anymore... take me off your user
 260     // list please!
 261 #if DEBUG_ABSTYPE
 262     cerr << "Removing type " << OldType->getDescription() << endl;
 263 #endif
 264     OldType->removeAbstractTypeUser(this);
 265
 266     // Remove the plane that is no longer used
 267     erase(TPI);
 268   } else if (TPI != end()) {
 269     assert(OldType == NewType);
 270 #if DEBUG_ABSTYPE
 271     cerr << "Removing SELF type " << OldType->getDescription() << endl;
 272 #endif
 273     OldType->removeAbstractTypeUser(this);
 274   }
 275
 276   TPI = find(Type::TypeTy);
 277   assert(TPI != end() &&"Type plane not in symbol table but we contain types!");
 278
 279   // Loop over all of the types in the symbol table, replacing any references to
 280   // OldType with references to NewType.  Note that there may be multiple
 281   // occurances, and although we only need to remove one at a time, it's faster
 282   // to remove them all in one pass.
 283   //
 284   VarMap &TyPlane = TPI->second;
 285   for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I)
 286     if (I->second == (Value*)OldType) {  // FIXME when Types aren't const.
 287 #if DEBUG_ABSTYPE
 288       cerr << "Removing type " << OldType->getDescription() << endl;
 289 #endif
 290       OldType->removeAbstractTypeUser(this);
 291
 292       I->second = (Value*)NewType;  // TODO FIXME when types aren't const
 293       if (NewType->isAbstract()) {
 294 #if DEBUG_ABSTYPE
 295         cerr << "Added type " << NewType->getDescription() << endl;
 296 #endif
 297         cast<const DerivedType>(NewType)->addAbstractTypeUser(this);
 298       }
 299     }
 300 }
 301
 302
 303 #ifndef NDEBUG
 304 #include "llvm/Assembly/Writer.h"
 305 #include <algorithm>
 306
 307 static void DumpVal(const pair<const string, Value *> &V) {
 308   cout << "  '" << V.first << "' = " << V.second << endl;
 309 }
 310
 311 static void DumpPlane(const pair<const Type *, map<const string, Value *> >&P) {
 312   cout << "  Plane: " << P.first << endl;
 313   for_each(P.second.begin(), P.second.end(), DumpVal);
 314 }
 315
 316 void SymbolTable::dump() const {
 317   cout << "Symbol table dump:\n";
 318   for_each(begin(), end(), DumpPlane);
 319
 320   if (ParentSymTab) {
 321     cout << "Parent ";
 322     ParentSymTab->dump();
 323   }
 324 }
 325
 326 #endif