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/Support/StringExtras.h"
  10 #include "llvm/DerivedTypes.h"
  11 #include "llvm/Module.h"
  12 #include "llvm/Method.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<ConstPoolVal>(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   // TODO: The typeverifier should catch this when its implemented
 137   assert(lookup(VTy, Name) == 0 &&
 138          "SymbolTable::insertEntry - Name already in symbol table!");
 139
 140 #if DEBUG_SYMBOL_TABLE
 141   cerr << this << " Inserting definition: " << Name << ": "
 142        << VTy->getDescription() << endl;
 143 #endif
 144
 145   iterator I = find(VTy);
 146   if (I == end()) {      // Not in collection yet... insert dummy entry
 147     // Insert a new empty element.  I points to the new elements.
 148     I = super::insert(make_pair(VTy, VarMap())).first;
 149     assert(I != end() && "How did insert fail?");
 150
 151     // Check to see if the type is abstract.  If so, it might be refined in the
 152     // future, which would cause the plane of the old type to get merged into
 153     // a new type plane.
 154     //
 155     if (VTy->isAbstract()) {
 156       cast<DerivedType>(VTy)->addAbstractTypeUser(this);
 157 #if DEBUG_ABSTYPE
 158       cerr << "Added abstract type value: " << VTy->getDescription() << endl;
 159 #endif
 160     }
 161   }
 162
 163   I->second.insert(make_pair(Name, V));
 164
 165   // If we are adding an abstract type, add the symbol table to it's use list.
 166   if (VTy == Type::TypeTy) {
 167     const Type *T = cast<const Type>(V);
 168     if (T->isAbstract()) {
 169       cast<DerivedType>(T)->addAbstractTypeUser(this);
 170 #if DEBUG_ABSTYPE
 171       cerr << "Added abstract type to ST: " << T->getDescription() << endl;
 172 #endif
 173     }
 174   }
 175 }
 176
 177 // This function is called when one of the types in the type plane are refined
 178 void SymbolTable::refineAbstractType(const DerivedType *OldType,
 179                                      const Type *NewType) {
 180   if (OldType == NewType && OldType->isAbstract())
 181     return;  // Noop, don't waste time dinking around
 182
 183   // Search to see if we have any values of the type oldtype.  If so, we need to
 184   // move them into the newtype plane...
 185   iterator TPI = find(OldType);
 186   if (OldType != NewType && TPI != end()) {
 187     // Get a handle to the new type plane...
 188     iterator NewTypeIt = find(NewType);
 189     if (NewTypeIt == super::end()) {      // If no plane exists, add one
 190       NewTypeIt = super::insert(make_pair(NewType, VarMap())).first;
 191
 192       if (NewType->isAbstract()) {
 193         cast<DerivedType>(NewType)->addAbstractTypeUser(this);
 194 #if DEBUG_ABSTYPE
 195         cerr << "[Added] refined to abstype: "<<NewType->getDescription()<<endl;
 196 #endif
 197     }
 198   }
 199
 200     VarMap &NewPlane = NewTypeIt->second;
 201     VarMap &OldPlane = TPI->second;
 202     while (!OldPlane.empty()) {
 203       pair<const string, Value*> V = *OldPlane.begin();
 204
 205       // Check to see if there is already a value in the symbol table that this
 206       // would collide with.
 207       type_iterator TI = NewPlane.find(V.first);
 208       if (TI != NewPlane.end() && TI->second == V.second) {
 209         // No action
 210
 211       } else if (TI != NewPlane.end()) {
 212         // The only thing we are allowing for now is two method prototypes being
 213         // folded into one.
 214         //
 215         Method *ExistM = dyn_cast<Method>(TI->second);
 216         Method *NewM = dyn_cast<Method>(V.second);
 217
 218         if (ExistM && NewM && ExistM->isExternal() && NewM->isExternal()) {
 219           // Ok we have two external methods.  Make all uses of the new one
 220           // use the old one...
 221           //
 222           NewM->replaceAllUsesWith(ExistM);
 223
 224           // Now we just convert it to an unnamed method... which won't get
 225           // added to our symbol table.  The problem is that if we call
 226           // setName on the method that it will try to remove itself from
 227           // the symbol table and die... because it's not in the symtab
 228           // right now.  To fix this, we have an internally consistent flag
 229           // that turns remove into a noop.  Thus the name will get null'd
 230           // out, but the symbol table won't get upset.
 231           //
 232           InternallyInconsistent = true;
 233
 234           // Remove newM from the symtab
 235           NewM->setName("");
 236           InternallyInconsistent = false;
 237
 238           // Now we can remove this method from the module entirely...
 239           NewM->getParent()->getMethodList().remove(NewM);
 240           delete NewM;
 241
 242         } else {
 243           assert(0 && "Two ploanes folded together with overlapping "
 244                  "value names!");
 245         }
 246       } else {
 247         insertEntry(V.first, NewType, V.second);
 248
 249       }
 250       // Remove the item from the old type plane
 251       OldPlane.erase(OldPlane.begin());
 252     }
 253
 254     // Ok, now we are not referencing the type anymore... take me off your user
 255     // list please!
 256 #if DEBUG_ABSTYPE
 257     cerr << "Removing type " << OldType->getDescription() << endl;
 258 #endif
 259     OldType->removeAbstractTypeUser(this);
 260
 261     // Remove the plane that is no longer used
 262     erase(TPI);
 263   } else if (TPI != end()) {
 264     assert(OldType == NewType);
 265 #if DEBUG_ABSTYPE
 266     cerr << "Removing SELF type " << OldType->getDescription() << endl;
 267 #endif
 268     OldType->removeAbstractTypeUser(this);
 269   }
 270
 271   TPI = find(Type::TypeTy);
 272   assert(TPI != end() &&"Type plane not in symbol table but we contain types!");
 273
 274   // Loop over all of the types in the symbol table, replacing any references to
 275   // OldType with references to NewType.  Note that there may be multiple
 276   // occurances, and although we only need to remove one at a time, it's faster
 277   // to remove them all in one pass.
 278   //
 279   VarMap &TyPlane = TPI->second;
 280   for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I)
 281     if (I->second == (Value*)OldType) {  // FIXME when Types aren't const.
 282 #if DEBUG_ABSTYPE
 283       cerr << "Removing type " << OldType->getDescription() << endl;
 284 #endif
 285       OldType->removeAbstractTypeUser(this);
 286
 287       I->second = (Value*)NewType;  // TODO FIXME when types aren't const
 288       if (NewType->isAbstract()) {
 289 #if DEBUG_ABSTYPE
 290         cerr << "Added type " << NewType->getDescription() << endl;
 291 #endif
 292         cast<const DerivedType>(NewType)->addAbstractTypeUser(this);
 293       }
 294     }
 295 }
 296
 297
 298 #ifndef NDEBUG
 299 #include "llvm/Assembly/Writer.h"
 300 #include <algorithm>
 301
 302 static void DumpVal(const pair<const string, Value *> &V) {
 303   cout << "  '" << V.first << "' = " << V.second << endl;
 304 }
 305
 306 static void DumpPlane(const pair<const Type *, map<const string, Value *> >&P) {
 307   cout << "  Plane: " << P.first << endl;
 308   for_each(P.second.begin(), P.second.end(), DumpVal);
 309 }
 310
 311 void SymbolTable::dump() const {
 312   cout << "Symbol table dump:\n";
 313   for_each(begin(), end(), DumpPlane);
 314
 315   if (ParentSymTab) {
 316     cout << "Parent ";
 317     ParentSymTab->dump();
 318   }
 319 }
 320
 321 #endif