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