lib/VMCore/SymbolTable.cpp

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