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 namespace llvm {
  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<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         std::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 std::string SymbolTable::getUniqueName(const Type *Ty,
  61                                        const std::string &BaseName) {
  62   iterator I = find(Ty);
  63   if (I == end()) return BaseName;
  64
  65   std::string TryName = BaseName;
  66   type_iterator End = I->second.end();
  67
  68   while (I->second.find(TryName) != End)       // Loop until we find a free
  69     TryName = BaseName + utostr(++LastUnique); // 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 std::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 0;
  85 }
  86
  87 void SymbolTable::remove(Value *N) {
  88   assert(N->hasName() && "Value doesn't have name!");
  89   if (InternallyInconsistent) return;
  90
  91   iterator I = find(N->getType());
  92   assert(I != end() &&
  93          "Trying to remove a type that doesn't have a plane yet!");
  94   removeEntry(I, I->second.find(N->getName()));
  95 }
  96
  97 // removeEntry - Remove a value from the symbol table...
  98 //
  99 Value *SymbolTable::removeEntry(iterator Plane, type_iterator Entry) {
 100   if (InternallyInconsistent) return 0;
 101   assert(Plane != super::end() &&
 102          Entry != Plane->second.end() && "Invalid entry to remove!");
 103
 104   Value *Result = Entry->second;
 105   const Type *Ty = Result->getType();
 106 #if DEBUG_SYMBOL_TABLE
 107   dump();
 108   std::cerr << " Removing Value: " << Result->getName() << "\n";
 109 #endif
 110
 111   // Remove the value from the plane...
 112   Plane->second.erase(Entry);
 113
 114   // If the plane is empty, remove it now!
 115   if (Plane->second.empty()) {
 116     // If the plane represented an abstract type that we were interested in,
 117     // unlink ourselves from this plane.
 118     //
 119     if (Plane->first->isAbstract()) {
 120 #if DEBUG_ABSTYPE
 121       std::cerr << "Plane Empty: Removing type: "
 122                 << Plane->first->getDescription() << "\n";
 123 #endif
 124       cast<DerivedType>(Plane->first)->removeAbstractTypeUser(this);
 125     }
 126
 127     erase(Plane);
 128   }
 129
 130   // If we are removing an abstract type, remove the symbol table from it's use
 131   // list...
 132   if (Ty == Type::TypeTy) {
 133     const Type *T = cast<Type>(Result);
 134     if (T->isAbstract()) {
 135 #if DEBUG_ABSTYPE
 136       std::cerr << "Removing abs type from symtab" << T->getDescription()<<"\n";
 137 #endif
 138       cast<DerivedType>(T)->removeAbstractTypeUser(this);
 139     }
 140   }
 141
 142   return Result;
 143 }
 144
 145 // insertEntry - Insert a value into the symbol table with the specified
 146 // name...
 147 //
 148 void SymbolTable::insertEntry(const std::string &Name, const Type *VTy,
 149                               Value *V) {
 150
 151   // Check to see if there is a naming conflict.  If so, rename this value!
 152   if (lookup(VTy, Name)) {
 153     std::string UniqueName = getUniqueName(VTy, Name);
 154     assert(InternallyInconsistent == false && "Infinite loop inserting entry!");
 155     InternallyInconsistent = true;
 156     V->setName(UniqueName, this);
 157     InternallyInconsistent = false;
 158     return;
 159   }
 160
 161 #if DEBUG_SYMBOL_TABLE
 162   dump();
 163   std::cerr << " Inserting definition: " << Name << ": "
 164             << VTy->getDescription() << "\n";
 165 #endif
 166
 167   iterator I = find(VTy);
 168   if (I == end()) {      // Not in collection yet... insert dummy entry
 169     // Insert a new empty element.  I points to the new elements.
 170     I = super::insert(make_pair(VTy, VarMap())).first;
 171     assert(I != end() && "How did insert fail?");
 172
 173     // Check to see if the type is abstract.  If so, it might be refined in the
 174     // future, which would cause the plane of the old type to get merged into
 175     // a new type plane.
 176     //
 177     if (VTy->isAbstract()) {
 178       cast<DerivedType>(VTy)->addAbstractTypeUser(this);
 179 #if DEBUG_ABSTYPE
 180       std::cerr << "Added abstract type value: " << VTy->getDescription()
 181                 << "\n";
 182 #endif
 183     }
 184   }
 185
 186   I->second.insert(make_pair(Name, V));
 187
 188   // If we are adding an abstract type, add the symbol table to it's use list.
 189   if (VTy == Type::TypeTy) {
 190     const Type *T = cast<Type>(V);
 191     if (T->isAbstract()) {
 192       cast<DerivedType>(T)->addAbstractTypeUser(this);
 193 #if DEBUG_ABSTYPE
 194       std::cerr << "Added abstract type to ST: " << T->getDescription() << "\n";
 195 #endif
 196     }
 197   }
 198 }
 199
 200 // This function is called when one of the types in the type plane are refined
 201 void SymbolTable::refineAbstractType(const DerivedType *OldType,
 202                                      const Type *NewType) {
 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 (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         std::cerr << "[Added] refined to abstype: " << NewType->getDescription()
 216                   << "\n";
 217 #endif
 218       }
 219     }
 220
 221     VarMap &NewPlane = NewTypeIt->second;
 222     VarMap &OldPlane = TPI->second;
 223     while (!OldPlane.empty()) {
 224       std::pair<const std::string, Value*> V = *OldPlane.begin();
 225
 226       // Check to see if there is already a value in the symbol table that this
 227       // would collide with.
 228       type_iterator TI = NewPlane.find(V.first);
 229       if (TI != NewPlane.end() && TI->second == V.second) {
 230         // No action
 231
 232       } else if (TI != NewPlane.end()) {
 233         // The only thing we are allowing for now is two external global values
 234         // folded into one.
 235         //
 236         GlobalValue *ExistGV = dyn_cast<GlobalValue>(TI->second);
 237         GlobalValue *NewGV = dyn_cast<GlobalValue>(V.second);
 238
 239         if (ExistGV && NewGV) {
 240           assert((ExistGV->isExternal() || NewGV->isExternal()) &&
 241                  "Two planes folded together with overlapping value names!");
 242
 243           // Make sure that ExistGV is the one we want to keep!
 244           if (!NewGV->isExternal())
 245             std::swap(NewGV, ExistGV);
 246
 247           // Ok we have two external global values.  Make all uses of the new
 248           // one use the old one...
 249           NewGV->uncheckedReplaceAllUsesWith(ExistGV);
 250
 251           // Now we just convert it to an unnamed method... which won't get
 252           // added to our symbol table.  The problem is that if we call
 253           // setName on the method that it will try to remove itself from
 254           // the symbol table and die... because it's not in the symtab
 255           // right now.  To fix this, we have an internally consistent flag
 256           // that turns remove into a noop.  Thus the name will get null'd
 257           // out, but the symbol table won't get upset.
 258           //
 259           assert(InternallyInconsistent == false &&
 260                  "Symbol table already inconsistent!");
 261           InternallyInconsistent = true;
 262
 263           // Remove newM from the symtab
 264           NewGV->setName("");
 265           InternallyInconsistent = false;
 266
 267           // Now we can remove this global from the module entirely...
 268           Module *M = NewGV->getParent();
 269           if (Function *F = dyn_cast<Function>(NewGV))
 270             M->getFunctionList().remove(F);
 271           else
 272             M->getGlobalList().remove(cast<GlobalVariable>(NewGV));
 273           delete NewGV;
 274         } else {
 275           // If they are not global values, they must be just random values who
 276           // happen to conflict now that types have been resolved.  If this is
 277           // the case, reinsert the value into the new plane, allowing it to get
 278           // renamed.
 279           assert(V.second->getType() == NewType &&"Type resolution is broken!");
 280           insert(V.second);
 281         }
 282       } else {
 283         insertEntry(V.first, NewType, V.second);
 284
 285       }
 286       // Remove the item from the old type plane
 287       OldPlane.erase(OldPlane.begin());
 288     }
 289
 290     // Ok, now we are not referencing the type anymore... take me off your user
 291     // list please!
 292 #if DEBUG_ABSTYPE
 293     std::cerr << "Removing type " << OldType->getDescription() << "\n";
 294 #endif
 295     OldType->removeAbstractTypeUser(this);
 296
 297     // Remove the plane that is no longer used
 298     erase(TPI);
 299   }
 300
 301   TPI = find(Type::TypeTy);
 302   if (TPI != end()) {
 303     // Loop over all of the types in the symbol table, replacing any references
 304     // to OldType with references to NewType.  Note that there may be multiple
 305     // occurrences, and although we only need to remove one at a time, it's
 306     // faster to remove them all in one pass.
 307     //
 308     VarMap &TyPlane = TPI->second;
 309     for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I)
 310       if (I->second == (Value*)OldType) {  // FIXME when Types aren't const.
 311 #if DEBUG_ABSTYPE
 312         std::cerr << "Removing type " << OldType->getDescription() << "\n";
 313 #endif
 314         OldType->removeAbstractTypeUser(this);
 315
 316         I->second = (Value*)NewType;  // TODO FIXME when types aren't const
 317         if (NewType->isAbstract()) {
 318 #if DEBUG_ABSTYPE
 319           std::cerr << "Added type " << NewType->getDescription() << "\n";
 320 #endif
 321           cast<DerivedType>(NewType)->addAbstractTypeUser(this);
 322         }
 323       }
 324   }
 325 }
 326
 327 void SymbolTable::typeBecameConcrete(const DerivedType *AbsTy) {
 328   iterator TPI = find(AbsTy);
 329
 330   // If there are any values in the symbol table of this type, then the type
 331   // plan is a use of the abstract type which must be dropped.
 332   if (TPI != end())
 333     AbsTy->removeAbstractTypeUser(this);
 334
 335   TPI = find(Type::TypeTy);
 336   if (TPI != end()) {
 337     // Loop over all of the types in the symbol table, dropping any abstract
 338     // type user entries for AbsTy which occur because there are names for the
 339     // type.
 340     //
 341     VarMap &TyPlane = TPI->second;
 342     for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I)
 343       if (I->second == (Value*)AbsTy)   // FIXME when Types aren't const.
 344         AbsTy->removeAbstractTypeUser(this);
 345   }
 346 }
 347
 348 static void DumpVal(const std::pair<const std::string, Value *> &V) {
 349   std::cout << "  '" << V.first << "' = ";
 350   V.second->dump();
 351   std::cout << "\n";
 352 }
 353
 354 static void DumpPlane(const std::pair<const Type *,
 355                                       std::map<const std::string, Value *> >&P){
 356   std::cout << "  Plane: ";
 357   P.first->dump();
 358   std::cout << "\n";
 359   for_each(P.second.begin(), P.second.end(), DumpVal);
 360 }
 361
 362 void SymbolTable::dump() const {
 363   std::cout << "Symbol table dump:\n";
 364   for_each(begin(), end(), DumpPlane);
 365 }
 366
 367 } // End llvm namespace