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