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 "llvm/InstrTypes.h"
  11 #include "Support/StringExtras.h"
  12 #include <iostream>
  13 #include <algorithm>
  14
  15 using std::string;
  16 using std::pair;
  17 using std::make_pair;
  18 using std::map;
  19 using std::cerr;
  20
  21 #define DEBUG_SYMBOL_TABLE 0
  22 #define DEBUG_ABSTYPE 0
  23
  24 SymbolTable::~SymbolTable() {
  25   // Drop all abstract type references in the type plane...
  26   iterator TyPlane = find(Type::TypeTy);
  27   if (TyPlane != end()) {
  28     VarMap &TyP = TyPlane->second;
  29     for (VarMap::iterator I = TyP.begin(), E = TyP.end(); I != E; ++I) {
  30       const Type *Ty = cast<const Type>(I->second);
  31       if (Ty->isAbstract())   // If abstract, drop the reference...
  32         cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
  33     }
  34   }
  35
  36  // TODO: FIXME: BIG ONE: This doesn't unreference abstract types for the planes
  37  // that could still have entries!
  38
  39 #ifndef NDEBUG   // Only do this in -g mode...
  40   bool LeftoverValues = true;
  41   for (iterator i = begin(); i != end(); ++i) {
  42     for (type_iterator I = i->second.begin(); I != i->second.end(); ++I)
  43       if (!isa<Constant>(I->second) && !isa<Type>(I->second)) {
  44         cerr << "Value still in symbol table! Type = '"
  45              << i->first->getDescription() << "' Name = '"
  46              << I->first << "'\n";
  47         LeftoverValues = false;
  48       }
  49   }
  50
  51   assert(LeftoverValues && "Values remain in symbol table!");
  52 #endif
  53 }
  54
  55 // getUniqueName - Given a base name, return a string that is either equal to
  56 // it (or derived from it) that does not already occur in the symbol table for
  57 // the specified type.
  58 //
  59 string SymbolTable::getUniqueName(const Type *Ty, const string &BaseName) {
  60   iterator I = find(Ty);
  61   if (I == end()) return BaseName;
  62
  63   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 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       cerr << "Plane Empty: Removing type: " << Plane->first->getDescription()
 121            << "\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<const Type>(Result);
 133     if (T->isAbstract()) {
 134 #if DEBUG_ABSTYPE
 135       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 string &Name, const Type *VTy, Value *V) {
 148
 149   // Check to see if there is a naming conflict.  If so, rename this value!
 150   if (lookup(VTy, Name)) {
 151     string UniqueName = getUniqueName(VTy, Name);
 152     assert(InternallyInconsistent == false && "Infinite loop inserting entry!");
 153     InternallyInconsistent = true;
 154     V->setName(UniqueName, this);
 155     InternallyInconsistent = false;
 156     return;
 157   }
 158
 159 #if DEBUG_SYMBOL_TABLE
 160   dump();
 161   cerr << " Inserting definition: " << Name << ": "
 162        << VTy->getDescription() << "\n";
 163 #endif
 164
 165   iterator I = find(VTy);
 166   if (I == end()) {      // Not in collection yet... insert dummy entry
 167     // Insert a new empty element.  I points to the new elements.
 168     I = super::insert(make_pair(VTy, VarMap())).first;
 169     assert(I != end() && "How did insert fail?");
 170
 171     // Check to see if the type is abstract.  If so, it might be refined in the
 172     // future, which would cause the plane of the old type to get merged into
 173     // a new type plane.
 174     //
 175     if (VTy->isAbstract()) {
 176       cast<DerivedType>(VTy)->addAbstractTypeUser(this);
 177 #if DEBUG_ABSTYPE
 178       cerr << "Added abstract type value: " << VTy->getDescription() << "\n";
 179 #endif
 180     }
 181   }
 182
 183   I->second.insert(make_pair(Name, V));
 184
 185   // If we are adding an abstract type, add the symbol table to it's use list.
 186   if (VTy == Type::TypeTy) {
 187     const Type *T = cast<const Type>(V);
 188     if (T->isAbstract()) {
 189       cast<DerivedType>(T)->addAbstractTypeUser(this);
 190 #if DEBUG_ABSTYPE
 191       cerr << "Added abstract type to ST: " << T->getDescription() << "\n";
 192 #endif
 193     }
 194   }
 195 }
 196
 197 // This function is called when one of the types in the type plane are refined
 198 void SymbolTable::refineAbstractType(const DerivedType *OldType,
 199                                      const Type *NewType) {
 200   if (OldType == NewType && OldType->isAbstract())
 201     return;  // Noop, don't waste time dinking around
 202
 203   // Search to see if we have any values of the type oldtype.  If so, we need to
 204   // move them into the newtype plane...
 205   iterator TPI = find(OldType);
 206   if (OldType != NewType && TPI != end()) {
 207     // Get a handle to the new type plane...
 208     iterator NewTypeIt = find(NewType);
 209     if (NewTypeIt == super::end()) {      // If no plane exists, add one
 210       NewTypeIt = super::insert(make_pair(NewType, VarMap())).first;
 211
 212       if (NewType->isAbstract()) {
 213         cast<DerivedType>(NewType)->addAbstractTypeUser(this);
 214 #if DEBUG_ABSTYPE
 215         cerr << "[Added] refined to abstype: "<<NewType->getDescription()<<"\n";
 216 #endif
 217       }
 218     }
 219
 220     VarMap &NewPlane = NewTypeIt->second;
 221     VarMap &OldPlane = TPI->second;
 222     while (!OldPlane.empty()) {
 223       pair<const 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 && ExistGV->isExternal() && NewGV->isExternal()) {
 239           // Ok we have two external global values.  Make all uses of the new
 240           // one use the old one...
 241           //
 242           assert(ExistGV->use_empty() && "No uses allowed on untyped value!");
 243           //NewGV->replaceAllUsesWith(ExistGV);
 244
 245           // Now we just convert it to an unnamed method... which won't get
 246           // added to our symbol table.  The problem is that if we call
 247           // setName on the method that it will try to remove itself from
 248           // the symbol table and die... because it's not in the symtab
 249           // right now.  To fix this, we have an internally consistent flag
 250           // that turns remove into a noop.  Thus the name will get null'd
 251           // out, but the symbol table won't get upset.
 252           //
 253           assert(InternallyInconsistent == false &&
 254                  "Symbol table already inconsistent!");
 255           InternallyInconsistent = true;
 256
 257           // Remove newM from the symtab
 258           NewGV->setName("");
 259           InternallyInconsistent = false;
 260
 261           // Now we can remove this global from the module entirely...
 262           Module *M = NewGV->getParent();
 263           if (Function *F = dyn_cast<Function>(NewGV))
 264             M->getFunctionList().remove(F);
 265           else
 266             M->getGlobalList().remove(cast<GlobalVariable>(NewGV));
 267           delete NewGV;
 268
 269         } else {
 270           assert(0 && "Two planes folded together with overlapping "
 271                  "value names!");
 272         }
 273       } else {
 274         insertEntry(V.first, NewType, V.second);
 275
 276       }
 277       // Remove the item from the old type plane
 278       OldPlane.erase(OldPlane.begin());
 279     }
 280
 281     // Ok, now we are not referencing the type anymore... take me off your user
 282     // list please!
 283 #if DEBUG_ABSTYPE
 284     cerr << "Removing type " << OldType->getDescription() << "\n";
 285 #endif
 286     OldType->removeAbstractTypeUser(this);
 287
 288     // Remove the plane that is no longer used
 289     erase(TPI);
 290   } else if (TPI != end()) {
 291     assert(OldType == NewType);
 292 #if DEBUG_ABSTYPE
 293     cerr << "Removing SELF type " << OldType->getDescription() << "\n";
 294 #endif
 295     OldType->removeAbstractTypeUser(this);
 296   }
 297
 298   TPI = find(Type::TypeTy);
 299   if (TPI != end()) {
 300     // Loop over all of the types in the symbol table, replacing any references
 301     // to OldType with references to NewType.  Note that there may be multiple
 302     // occurances, and although we only need to remove one at a time, it's
 303     // faster to remove them all in one pass.
 304     //
 305     VarMap &TyPlane = TPI->second;
 306     for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I)
 307       if (I->second == (Value*)OldType) {  // FIXME when Types aren't const.
 308 #if DEBUG_ABSTYPE
 309         cerr << "Removing type " << OldType->getDescription() << "\n";
 310 #endif
 311         OldType->removeAbstractTypeUser(this);
 312
 313         I->second = (Value*)NewType;  // TODO FIXME when types aren't const
 314         if (NewType->isAbstract()) {
 315 #if DEBUG_ABSTYPE
 316           cerr << "Added type " << NewType->getDescription() << "\n";
 317 #endif
 318           cast<const DerivedType>(NewType)->addAbstractTypeUser(this);
 319         }
 320       }
 321   }
 322 }
 323
 324 static void DumpVal(const pair<const string, Value *> &V) {
 325   std::cout << "  '" << V.first << "' = ";
 326   V.second->dump();
 327   std::cout << "\n";
 328 }
 329
 330 static void DumpPlane(const pair<const Type *, map<const string, Value *> >&P) {
 331   std::cout << "  Plane: ";
 332   P.first->dump();
 333   std::cout << "\n";
 334   for_each(P.second.begin(), P.second.end(), DumpVal);
 335 }
 336
 337 void SymbolTable::dump() const {
 338   std::cout << "Symbol table dump:\n";
 339   for_each(begin(), end(), DumpPlane);
 340 }