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/InstrTypes.h"
   9 #include "llvm/Support/StringExtras.h"
  10 #include "llvm/DerivedTypes.h"
  11 #ifndef NDEBUG
  12 #include "llvm/BasicBlock.h"   // Required for assertions to work.
  13 #include "llvm/Type.h"
  14 #endif
  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 = I->second->castTypeAsserting();
  23       if (Ty->isAbstract())   // If abstract, drop the reference...
  24         Ty->castDerivedTypeAsserting()->removeAbstractTypeUser(this);
  25     }
  26   }
  27 #ifndef NDEBUG   // Only do this in -g mode...
  28   bool LeftoverValues = true;
  29   for (iterator i = begin(); i != end(); ++i) {
  30     for (type_iterator I = i->second.begin(); I != i->second.end(); ++I)
  31       if (!I->second->isConstant() && !I->second->isType()) {
  32         cerr << "Value still in symbol table! Type = '"
  33              << i->first->getDescription() << "' Name = '" << I->first << "'\n";
  34         LeftoverValues = false;
  35       }
  36   }
  37
  38   assert(LeftoverValues && "Values remain in symbol table!");
  39 #endif
  40 }
  41
  42 SymbolTable::type_iterator SymbolTable::type_find(const Value *D) {
  43   assert(D->hasName() && "type_find(Value*) only works on named nodes!");
  44   return type_find(D->getType(), D->getName());
  45 }
  46
  47
  48 // find - returns end(Ty->getIDNumber()) on failure...
  49 SymbolTable::type_iterator SymbolTable::type_find(const Type *Ty,
  50                                                   const string &Name) {
  51   iterator I = find(Ty);
  52   if (I == end()) {      // Not in collection yet... insert dummy entry
  53     (*this)[Ty] = VarMap();
  54     I = find(Ty);
  55     assert(I != end() && "How did insert fail?");
  56   }
  57
  58   return I->second.find(Name);
  59 }
  60
  61 // getUniqueName - Given a base name, return a string that is either equal to
  62 // it (or derived from it) that does not already occur in the symbol table for
  63 // the specified type.
  64 //
  65 string SymbolTable::getUniqueName(const Type *Ty, const string &BaseName) {
  66   iterator I = find(Ty);
  67   if (I == end()) return BaseName;
  68
  69   string TryName = BaseName;
  70   unsigned Counter = 0;
  71   type_iterator End = I->second.end();
  72
  73   while (I->second.find(TryName) != End)     // Loop until we find unoccupied
  74     TryName = BaseName + utostr(++Counter);  // Name in the symbol table
  75   return TryName;
  76 }
  77
  78
  79
  80 // lookup - Returns null on failure...
  81 Value *SymbolTable::lookup(const Type *Ty, const string &Name) {
  82   iterator I = find(Ty);
  83   if (I != end()) {                      // We have symbols in that plane...
  84     type_iterator J = I->second.find(Name);
  85     if (J != I->second.end())            // and the name is in our hash table...
  86       return J->second;
  87   }
  88
  89   return ParentSymTab ? ParentSymTab->lookup(Ty, Name) : 0;
  90 }
  91
  92 void SymbolTable::remove(Value *N) {
  93   assert(N->hasName() && "Value doesn't have name!");
  94   assert(type_find(N) != type_end(N->getType()) &&
  95          "Value not in symbol table!");
  96   type_remove(type_find(N));
  97 }
  98
  99
 100 #define DEBUG_SYMBOL_TABLE 0
 101
 102 Value *SymbolTable::type_remove(const type_iterator &It) {
 103   Value *Result = It->second;
 104   const Type *Ty = Result->getType();
 105 #if DEBUG_SYMBOL_TABLE
 106   cerr << this << " Removing Value: " << Result->getName() << endl;
 107 #endif
 108
 109   // Remove the value from the plane...
 110   find(Ty)->second.erase(It);
 111
 112   // If we are removing an abstract type, remove the symbol table from it's use
 113   // list...
 114   if (Ty == Type::TypeTy) {
 115     const Type *T = Result->castTypeAsserting();
 116     if (T->isAbstract())
 117       T->castDerivedTypeAsserting()->removeAbstractTypeUser(this);
 118   }
 119
 120   return Result;
 121 }
 122
 123 // insertEntry - Insert a value into the symbol table with the specified
 124 // name...
 125 //
 126 void SymbolTable::insertEntry(const string &Name, Value *V) {
 127   const Type *VTy = V->getType();
 128
 129   // TODO: The typeverifier should catch this when its implemented
 130   if (lookup(VTy, Name)) {
 131     cerr << "SymbolTable ERROR: Name already in symbol table: '"
 132          << Name << "' for type '" << VTy->getDescription() << "'\n";
 133     abort();  // TODO: REMOVE THIS
 134   }
 135
 136 #if DEBUG_SYMBOL_TABLE
 137   cerr << this << " Inserting definition: " << Name << ": "
 138        << VTy->getDescription() << endl;
 139 #endif
 140
 141   iterator I = find(VTy);
 142   if (I == end()) {      // Not in collection yet... insert dummy entry
 143     (*this)[VTy] = VarMap();
 144     I = find(VTy);
 145     assert(I != end() && "How did insert fail?");
 146   }
 147
 148   I->second.insert(make_pair(Name, V));
 149
 150   // If we are adding an abstract type, add the symbol table to it's use list.
 151   if (VTy == Type::TypeTy) {
 152     const Type *T = V->castTypeAsserting();
 153     if (T->isAbstract())
 154       T->castDerivedTypeAsserting()->addAbstractTypeUser(this);
 155   }
 156 }
 157
 158 // This function is called when one of the types in the type plane are refined
 159 void SymbolTable::refineAbstractType(const DerivedType *OldType,
 160                                      const Type *NewType) {
 161   if (OldType == NewType) return;  // Noop, don't waste time dinking around
 162
 163   iterator TPI = find(Type::TypeTy);
 164   assert(TPI != end() &&"Type plane not in symbol table but we contain types!");
 165
 166   // Loop over all of the types in the symbol table, replacing any references to
 167   // OldType with references to NewType.  Note that there may be multiple
 168   // occurances, and although we only need to remove one at a time, it's faster
 169   // to remove them all in one pass.
 170   //
 171   VarMap &TyPlane = TPI->second;
 172   for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I)
 173     if (I->second == (Value*)OldType) {  // FIXME when Types aren't const.
 174       OldType->removeAbstractTypeUser(this);
 175       I->second = (Value*)NewType;  // TODO FIXME when types aren't const
 176       if (NewType->isAbstract())
 177         NewType->castDerivedTypeAsserting()->addAbstractTypeUser(this);
 178     }
 179 }