X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FSymbolTable.cpp;h=6d09c7d5669803f6bbde739236faf0314bcf0efe;hb=f6ffcb6b713c259992b68d6b328f1b806775b9fb;hp=1275d087917f04dd050251d49a999e9387eb9ee1;hpb=c895294762d6cb46181d473a32e9249ef042a747;p=oota-llvm.git diff --git a/lib/VMCore/SymbolTable.cpp b/lib/VMCore/SymbolTable.cpp index 1275d087917..6d09c7d5669 100644 --- a/lib/VMCore/SymbolTable.cpp +++ b/lib/VMCore/SymbolTable.cpp @@ -5,10 +5,21 @@ //===----------------------------------------------------------------------===// #include "llvm/SymbolTable.h" -#include "llvm/InstrTypes.h" -#include "llvm/Support/StringExtras.h" #include "llvm/DerivedTypes.h" -#include "llvm/Method.h" +#include "llvm/Module.h" +#include "llvm/InstrTypes.h" +#include "Support/StringExtras.h" +#include +#include + +using std::string; +using std::pair; +using std::make_pair; +using std::map; +using std::cerr; + +#define DEBUG_SYMBOL_TABLE 0 +#define DEBUG_ABSTYPE 0 SymbolTable::~SymbolTable() { // Drop all abstract type references in the type plane... @@ -21,13 +32,18 @@ SymbolTable::~SymbolTable() { cast(Ty)->removeAbstractTypeUser(this); } } + + // TODO: FIXME: BIG ONE: This doesn't unreference abstract types for the planes + // that could still have entries! + #ifndef NDEBUG // Only do this in -g mode... bool LeftoverValues = true; for (iterator i = begin(); i != end(); ++i) { for (type_iterator I = i->second.begin(); I != i->second.end(); ++I) - if (!isa(I->second) && !isa(I->second)) { + if (!isa(I->second) && !isa(I->second)) { cerr << "Value still in symbol table! Type = '" - << i->first->getDescription() << "' Name = '" << I->first << "'\n"; + << i->first->getDescription() << "' Name = '" + << I->first << "'\n"; LeftoverValues = false; } } @@ -36,25 +52,6 @@ SymbolTable::~SymbolTable() { #endif } -SymbolTable::type_iterator SymbolTable::type_find(const Value *D) { - assert(D->hasName() && "type_find(Value*) only works on named nodes!"); - return type_find(D->getType(), D->getName()); -} - - -// find - returns end(Ty->getIDNumber()) on failure... -SymbolTable::type_iterator SymbolTable::type_find(const Type *Ty, - const string &Name) { - iterator I = find(Ty); - if (I == end()) { // Not in collection yet... insert dummy entry - (*this)[Ty] = VarMap(); - I = find(Ty); - assert(I != end() && "How did insert fail?"); - } - - return I->second.find(Name); -} - // getUniqueName - Given a base name, return a string that is either equal to // it (or derived from it) that does not already occur in the symbol table for // the specified type. @@ -75,7 +72,7 @@ string SymbolTable::getUniqueName(const Type *Ty, const string &BaseName) { // lookup - Returns null on failure... -Value *SymbolTable::lookup(const Type *Ty, const string &Name) { +Value *SymbolTable::localLookup(const Type *Ty, const string &Name) { iterator I = find(Ty); if (I != end()) { // We have symbols in that plane... type_iterator J = I->second.find(Name); @@ -83,35 +80,69 @@ Value *SymbolTable::lookup(const Type *Ty, const string &Name) { return J->second; } + return 0; +} + +// lookup - Returns null on failure... +Value *SymbolTable::lookup(const Type *Ty, const string &Name) { + Value *LV = localLookup(Ty, Name); + if (LV) return LV; return ParentSymTab ? ParentSymTab->lookup(Ty, Name) : 0; } void SymbolTable::remove(Value *N) { assert(N->hasName() && "Value doesn't have name!"); - assert(type_find(N) != type_end(N->getType()) && - "Value not in symbol table!"); - type_remove(type_find(N)); -} + if (InternallyInconsistent) return; + iterator I = find(N->getType()); + assert(I != end() && + "Trying to remove a type that doesn't have a plane yet!"); + removeEntry(I, I->second.find(N->getName())); +} -#define DEBUG_SYMBOL_TABLE 0 +// removeEntry - Remove a value from the symbol table... +// +Value *SymbolTable::removeEntry(iterator Plane, type_iterator Entry) { + if (InternallyInconsistent) return 0; + assert(Plane != super::end() && + Entry != Plane->second.end() && "Invalid entry to remove!"); -Value *SymbolTable::type_remove(const type_iterator &It) { - Value *Result = It->second; + Value *Result = Entry->second; const Type *Ty = Result->getType(); #if DEBUG_SYMBOL_TABLE - cerr << this << " Removing Value: " << Result->getName() << endl; + dump(); + std::cerr << " Removing Value: " << Result->getName() << "\n"; #endif // Remove the value from the plane... - find(Ty)->second.erase(It); + Plane->second.erase(Entry); + + // If the plane is empty, remove it now! + if (Plane->second.empty()) { + // If the plane represented an abstract type that we were interested in, + // unlink ourselves from this plane. + // + if (Plane->first->isAbstract()) { +#if DEBUG_ABSTYPE + cerr << "Plane Empty: Removing type: " << Plane->first->getDescription() + << "\n"; +#endif + cast(Plane->first)->removeAbstractTypeUser(this); + } + + erase(Plane); + } // If we are removing an abstract type, remove the symbol table from it's use // list... if (Ty == Type::TypeTy) { const Type *T = cast(Result); - if (T->isAbstract()) + if (T->isAbstract()) { +#if DEBUG_ABSTYPE + cerr << "Removing abs type from symtab" << T->getDescription() << "\n"; +#endif cast(T)->removeAbstractTypeUser(this); + } } return Result; @@ -121,13 +152,21 @@ Value *SymbolTable::type_remove(const type_iterator &It) { // name... // void SymbolTable::insertEntry(const string &Name, const Type *VTy, Value *V) { - // TODO: The typeverifier should catch this when its implemented - assert(lookup(VTy, Name) == 0 && - "SymbolTable::insertEntry - Name already in symbol table!"); + + // Check to see if there is a naming conflict. If so, rename this value! + if (localLookup(VTy, Name)) { + string UniqueName = getUniqueName(VTy, Name); + assert(InternallyInconsistent == false && "Infinite loop inserting entry!"); + InternallyInconsistent = true; + V->setName(UniqueName, this); + InternallyInconsistent = false; + return; + } #if DEBUG_SYMBOL_TABLE - cerr << this << " Inserting definition: " << Name << ": " - << VTy->getDescription() << endl; + dump(); + cerr << " Inserting definition: " << Name << ": " + << VTy->getDescription() << "\n"; #endif iterator I = find(VTy); @@ -140,8 +179,12 @@ void SymbolTable::insertEntry(const string &Name, const Type *VTy, Value *V) { // future, which would cause the plane of the old type to get merged into // a new type plane. // - if (VTy->isAbstract()) + if (VTy->isAbstract()) { cast(VTy)->addAbstractTypeUser(this); +#if DEBUG_ABSTYPE + cerr << "Added abstract type value: " << VTy->getDescription() << "\n"; +#endif + } } I->second.insert(make_pair(Name, V)); @@ -149,27 +192,39 @@ void SymbolTable::insertEntry(const string &Name, const Type *VTy, Value *V) { // If we are adding an abstract type, add the symbol table to it's use list. if (VTy == Type::TypeTy) { const Type *T = cast(V); - if (T->isAbstract()) + if (T->isAbstract()) { cast(T)->addAbstractTypeUser(this); +#if DEBUG_ABSTYPE + cerr << "Added abstract type to ST: " << T->getDescription() << "\n"; +#endif + } } } // This function is called when one of the types in the type plane are refined void SymbolTable::refineAbstractType(const DerivedType *OldType, const Type *NewType) { - if (OldType == NewType) return; // Noop, don't waste time dinking around - - // Get a handle to the new type plane... - iterator NewTypeIt = find(NewType); - if (NewTypeIt == super::end()) // If no plane exists, add one - NewTypeIt = super::insert(make_pair(NewType, VarMap())).first; - - VarMap &NewPlane = NewTypeIt->second; + if (OldType == NewType && OldType->isAbstract()) + return; // Noop, don't waste time dinking around // Search to see if we have any values of the type oldtype. If so, we need to // move them into the newtype plane... iterator TPI = find(OldType); - if (TPI != end()) { + if (OldType != NewType && TPI != end()) { + // Get a handle to the new type plane... + iterator NewTypeIt = find(NewType); + if (NewTypeIt == super::end()) { // If no plane exists, add one + NewTypeIt = super::insert(make_pair(NewType, VarMap())).first; + + if (NewType->isAbstract()) { + cast(NewType)->addAbstractTypeUser(this); +#if DEBUG_ABSTYPE + cerr << "[Added] refined to abstype: "<getDescription()<<"\n"; +#endif + } + } + + VarMap &NewPlane = NewTypeIt->second; VarMap &OldPlane = TPI->second; while (!OldPlane.empty()) { pair V = *OldPlane.begin(); @@ -184,37 +239,39 @@ void SymbolTable::refineAbstractType(const DerivedType *OldType, // The only thing we are allowing for now is two method prototypes being // folded into one. // - if (Method *ExistM = dyn_cast(TI->second)) - if (Method *NewM = dyn_cast(V.second)) - if (ExistM->isExternal() && NewM->isExternal()) { - // Ok we have two external methods. Make all uses of the new one - // use the old one... - // - NewM->replaceAllUsesWith(ExistM); - - // Now we just convert it to an unnamed method... which won't get - // added to our symbol table. The problem is that if we call - // setName on the method that it will try to remove itself from - // the symbol table and die... because it's not in the symtab - // right now. To fix this, we temporarily insert it (by setting - // TI's entry to the old value. Then after it is removed, we - // restore ExistM into the symbol table. - // - if (NewM->getType() == NewType) { - TI->second = NewM; // Add newM to the symtab - - // Remove newM from the symtab - NewM->setName(""); - - // Readd ExistM to the symbol table.... - NewPlane.insert(make_pair(V.first, ExistM)); - } else { - NewM->setName(""); - } - continue; - } - assert(0 && "Two ploanes folded together with overlapping " - "value names!"); + Function *ExistM = dyn_cast(TI->second); + Function *NewM = dyn_cast(V.second); + + if (ExistM && NewM && ExistM->isExternal() && NewM->isExternal()) { + // Ok we have two external methods. Make all uses of the new one + // use the old one... + // + NewM->replaceAllUsesWith(ExistM); + + // Now we just convert it to an unnamed method... which won't get + // added to our symbol table. The problem is that if we call + // setName on the method that it will try to remove itself from + // the symbol table and die... because it's not in the symtab + // right now. To fix this, we have an internally consistent flag + // that turns remove into a noop. Thus the name will get null'd + // out, but the symbol table won't get upset. + // + assert(InternallyInconsistent == false && + "Symbol table already inconsistent!"); + InternallyInconsistent = true; + + // Remove newM from the symtab + NewM->setName(""); + InternallyInconsistent = false; + + // Now we can remove this method from the module entirely... + NewM->getParent()->getFunctionList().remove(NewM); + delete NewM; + + } else { + assert(0 && "Two ploanes folded together with overlapping " + "value names!"); + } } else { insertEntry(V.first, NewType, V.second); @@ -225,49 +282,66 @@ void SymbolTable::refineAbstractType(const DerivedType *OldType, // Ok, now we are not referencing the type anymore... take me off your user // list please! +#if DEBUG_ABSTYPE + cerr << "Removing type " << OldType->getDescription() << "\n"; +#endif + OldType->removeAbstractTypeUser(this); + + // Remove the plane that is no longer used + erase(TPI); + } else if (TPI != end()) { + assert(OldType == NewType); +#if DEBUG_ABSTYPE + cerr << "Removing SELF type " << OldType->getDescription() << "\n"; +#endif OldType->removeAbstractTypeUser(this); } TPI = find(Type::TypeTy); - assert(TPI != end() &&"Type plane not in symbol table but we contain types!"); - - // Loop over all of the types in the symbol table, replacing any references to - // OldType with references to NewType. Note that there may be multiple - // occurances, and although we only need to remove one at a time, it's faster - // to remove them all in one pass. - // - VarMap &TyPlane = TPI->second; - for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I) - if (I->second == (Value*)OldType) { // FIXME when Types aren't const. - OldType->removeAbstractTypeUser(this); - I->second = (Value*)NewType; // TODO FIXME when types aren't const - if (NewType->isAbstract()) - cast(NewType)->addAbstractTypeUser(this); - } + if (TPI != end()) { + // Loop over all of the types in the symbol table, replacing any references + // to OldType with references to NewType. Note that there may be multiple + // occurances, and although we only need to remove one at a time, it's + // faster to remove them all in one pass. + // + VarMap &TyPlane = TPI->second; + for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I) + if (I->second == (Value*)OldType) { // FIXME when Types aren't const. +#if DEBUG_ABSTYPE + cerr << "Removing type " << OldType->getDescription() << "\n"; +#endif + OldType->removeAbstractTypeUser(this); + + I->second = (Value*)NewType; // TODO FIXME when types aren't const + if (NewType->isAbstract()) { +#if DEBUG_ABSTYPE + cerr << "Added type " << NewType->getDescription() << "\n"; +#endif + cast(NewType)->addAbstractTypeUser(this); + } + } + } } - -#ifndef NDEBUG -#include "llvm/Assembly/Writer.h" -#include - static void DumpVal(const pair &V) { - cout << " '%" << V.first << "' = " << V.second << endl; + std::cout << " '" << V.first << "' = "; + V.second->dump(); + std::cout << "\n"; } static void DumpPlane(const pair >&P) { - cout << " Plane: " << P.first << endl; + std::cout << " Plane: "; + P.first->dump(); + std::cout << "\n"; for_each(P.second.begin(), P.second.end(), DumpVal); } void SymbolTable::dump() const { - cout << "Symbol table dump:\n"; + std::cout << "Symbol table dump:\n"; for_each(begin(), end(), DumpPlane); if (ParentSymTab) { - cout << "Parent "; + std::cout << "Parent "; ParentSymTab->dump(); } } - -#endif