X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FSymbolTable.cpp;h=6d09c7d5669803f6bbde739236faf0314bcf0efe;hb=ad333484ea5ae976b83e35ccd3f6cfa6e71290e2;hp=214f41f169e6bd301c897a46e8e33384a93d8eb6;hpb=20554f11d0410496bc5c49744e0d45c71a1a3955;p=oota-llvm.git diff --git a/lib/VMCore/SymbolTable.cpp b/lib/VMCore/SymbolTable.cpp index 214f41f169e..6d09c7d5669 100644 --- a/lib/VMCore/SymbolTable.cpp +++ b/lib/VMCore/SymbolTable.cpp @@ -5,45 +5,51 @@ //===----------------------------------------------------------------------===// #include "llvm/SymbolTable.h" +#include "llvm/DerivedTypes.h" +#include "llvm/Module.h" #include "llvm/InstrTypes.h" -#include "llvm/Tools/StringExtras.h" -#ifndef NDEBUG -#include "llvm/BasicBlock.h" // Required for assertions to work. -#include "llvm/Type.h" -#endif +#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() { -#ifndef NDEBUG // Only do this in -g mode... - bool Good = true; - for (iterator i = begin(); i != end(); i++) { - if (i->second.begin() != i->second.end()) { - for (type_iterator I = i->second.begin(); I != i->second.end(); I++) - cerr << "Value still in symbol table! Type = " << i->first->getName() - << " Name = " << I->first << endl; - Good = false; + // Drop all abstract type references in the type plane... + iterator TyPlane = find(Type::TypeTy); + if (TyPlane != end()) { + VarMap &TyP = TyPlane->second; + for (VarMap::iterator I = TyP.begin(), E = TyP.end(); I != E; ++I) { + const Type *Ty = cast(I->second); + if (Ty->isAbstract()) // If abstract, drop the reference... + cast(Ty)->removeAbstractTypeUser(this); } } - assert(Good && "Values remain in symbol table!"); -#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()); -} + // TODO: FIXME: BIG ONE: This doesn't unreference abstract types for the planes + // that could still have entries! - -// 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?"); +#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)) { + cerr << "Value still in symbol table! Type = '" + << i->first->getDescription() << "' Name = '" + << I->first << "'\n"; + LeftoverValues = false; + } } - - return I->second.find(Name); + + assert(LeftoverValues && "Values remain in symbol table!"); +#endif } // getUniqueName - Given a base name, return a string that is either equal to @@ -66,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); @@ -74,52 +80,268 @@ 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... + 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); + } - find(Result->getType())->second.erase(It); + 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 DEBUG_ABSTYPE + cerr << "Removing abs type from symtab" << T->getDescription() << "\n"; +#endif + cast(T)->removeAbstractTypeUser(this); + } + } return Result; } -void SymbolTable::insert(Value *N) { - assert(N->hasName() && "Value must be named to go into symbol table!"); +// insertEntry - Insert a value into the symbol table with the specified +// name... +// +void SymbolTable::insertEntry(const string &Name, const Type *VTy, Value *V) { - // TODO: The typeverifier should catch this when its implemented - if (lookup(N->getType(), N->getName())) { - cerr << "SymbolTable WARNING: Name already in symbol table: '" - << N->getName() << "'\n"; - abort(); // TODO: REMOVE THIS + // 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: " << N->getName() << ": " - << N->getType()->getName() << endl; + dump(); + cerr << " Inserting definition: " << Name << ": " + << VTy->getDescription() << "\n"; #endif - iterator I = find(N->getType()); + iterator I = find(VTy); if (I == end()) { // Not in collection yet... insert dummy entry - (*this)[N->getType()] = VarMap(); - I = find(N->getType()); + // Insert a new empty element. I points to the new elements. + I = super::insert(make_pair(VTy, VarMap())).first; assert(I != end() && "How did insert fail?"); + + // Check to see if the type is abstract. If so, it might be refined in the + // future, which would cause the plane of the old type to get merged into + // a new type plane. + // + 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)); + + // 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()) { + 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 && 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 (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(); + + // Check to see if there is already a value in the symbol table that this + // would collide with. + type_iterator TI = NewPlane.find(V.first); + if (TI != NewPlane.end() && TI->second == V.second) { + // No action + + } else if (TI != NewPlane.end()) { + // The only thing we are allowing for now is two method prototypes being + // folded into one. + // + 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); + + } + // Remove the item from the old type plane + OldPlane.erase(OldPlane.begin()); + } + + // 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); + 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); + } + } } +} - I->second.insert(make_pair(N->getName(), N)); +static void DumpVal(const pair &V) { + std::cout << " '" << V.first << "' = "; + V.second->dump(); + std::cout << "\n"; } +static void DumpPlane(const pair >&P) { + std::cout << " Plane: "; + P.first->dump(); + std::cout << "\n"; + for_each(P.second.begin(), P.second.end(), DumpVal); +} + +void SymbolTable::dump() const { + std::cout << "Symbol table dump:\n"; + for_each(begin(), end(), DumpPlane); + + if (ParentSymTab) { + std::cout << "Parent "; + ParentSymTab->dump(); + } +}