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 using namespace llvm;
  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<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         std::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 std::string SymbolTable::getUniqueName(const Type *Ty,
  60                                        const std::string &BaseName) {
  61   iterator I = find(Ty);
  62   if (I == end()) return BaseName;
  63
  64   std::string TryName = BaseName;
  65   type_iterator End = I->second.end();
  66
  67   while (I->second.find(TryName) != End)       // Loop until we find a free
  68     TryName = BaseName + utostr(++LastUnique); // 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) const {
  76   const_iterator I = find(Ty);
  77   if (I != end()) {                      // We have symbols in that plane...
  78     type_const_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         } else {
 274           // If they are not global values, they must be just random values who
 275           // happen to conflict now that types have been resolved.  If this is
 276           // the case, reinsert the value into the new plane, allowing it to get
 277           // renamed.
 278           assert(V.second->getType() == NewType &&"Type resolution is broken!");
 279           insert(V.second);
 280         }
 281       } else {
 282         insertEntry(V.first, NewType, V.second);
 283
 284       }
 285       // Remove the item from the old type plane
 286       OldPlane.erase(OldPlane.begin());
 287     }
 288
 289     // Ok, now we are not referencing the type anymore... take me off your user
 290     // list please!
 291 #if DEBUG_ABSTYPE
 292     std::cerr << "Removing type " << OldType->getDescription() << "\n";
 293 #endif
 294     OldType->removeAbstractTypeUser(this);
 295
 296     // Remove the plane that is no longer used
 297     erase(TPI);
 298   }
 299
 300   TPI = find(Type::TypeTy);
 301   if (TPI != end()) {
 302     // Loop over all of the types in the symbol table, replacing any references
 303     // to OldType with references to NewType.  Note that there may be multiple
 304     // occurrences, and although we only need to remove one at a time, it's
 305     // faster to remove them all in one pass.
 306     //
 307     VarMap &TyPlane = TPI->second;
 308     for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I)
 309       if (I->second == (Value*)OldType) {  // FIXME when Types aren't const.
 310 #if DEBUG_ABSTYPE
 311         std::cerr << "Removing type " << OldType->getDescription() << "\n";
 312 #endif
 313         OldType->removeAbstractTypeUser(this);
 314
 315         I->second = (Value*)NewType;  // TODO FIXME when types aren't const
 316         if (NewType->isAbstract()) {
 317 #if DEBUG_ABSTYPE
 318           std::cerr << "Added type " << NewType->getDescription() << "\n";
 319 #endif
 320           cast<DerivedType>(NewType)->addAbstractTypeUser(this);
 321         }
 322       }
 323   }
 324 }
 325
 326 void SymbolTable::typeBecameConcrete(const DerivedType *AbsTy) {
 327   iterator TPI = find(AbsTy);
 328
 329   // If there are any values in the symbol table of this type, then the type
 330   // plan is a use of the abstract type which must be dropped.
 331   if (TPI != end())
 332     AbsTy->removeAbstractTypeUser(this);
 333
 334   TPI = find(Type::TypeTy);
 335   if (TPI != end()) {
 336     // Loop over all of the types in the symbol table, dropping any abstract
 337     // type user entries for AbsTy which occur because there are names for the
 338     // type.
 339     //
 340     VarMap &TyPlane = TPI->second;
 341     for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I)
 342       if (I->second == (Value*)AbsTy)   // FIXME when Types aren't const.
 343         AbsTy->removeAbstractTypeUser(this);
 344   }
 345 }
 346
 347 static void DumpVal(const std::pair<const std::string, Value *> &V) {
 348   std::cout << "  '" << V.first << "' = ";
 349   V.second->dump();
 350   std::cout << "\n";
 351 }
 352
 353 static void DumpPlane(const std::pair<const Type *,
 354                                       std::map<const std::string, Value *> >&P){
 355   std::cout << "  Plane: ";
 356   P.first->dump();
 357   std::cout << "\n";
 358   for_each(P.second.begin(), P.second.end(), DumpVal);
 359 }
 360
 361 void SymbolTable::dump() const {
 362   std::cout << "Symbol table dump:\n";
 363   for_each(begin(), end(), DumpPlane);
 364 }