X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FSymbolTable.cpp;h=3ac8ddfc6ad2c5e26a8ca81ff6b579773b77ba5c;hb=59bcce5ae52afff2ba4840bfa630b20e8ff4ddb2;hp=5a365dd330d480ad958453d828518421b3dfbd8e;hpb=ad217a4ca29eacbd66e9ff5528ec8af379bc52d8;p=oota-llvm.git diff --git a/lib/VMCore/SymbolTable.cpp b/lib/VMCore/SymbolTable.cpp index 5a365dd330d..3ac8ddfc6ad 100644 --- a/lib/VMCore/SymbolTable.cpp +++ b/lib/VMCore/SymbolTable.cpp @@ -1,4 +1,12 @@ -//===-- SymbolTable.cpp - Implement the SymbolTable class -------------------=// +//===-- SymbolTable.cpp - Implement the SymbolTable class -----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and revised by Reid +// Spencer. It is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// // // This file implements the SymbolTable class for the VMCore library. // @@ -7,39 +15,37 @@ #include "llvm/SymbolTable.h" #include "llvm/DerivedTypes.h" #include "llvm/Module.h" -#include "Support/StringExtras.h" +#include "llvm/ADT/StringExtras.h" #include +#include + +using namespace llvm; #define DEBUG_SYMBOL_TABLE 0 #define DEBUG_ABSTYPE 0 SymbolTable::~SymbolTable() { // 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); - } + for (type_iterator TI = tmap.begin(), TE = tmap.end(); TI != TE; ++TI) { + if (TI->second->isAbstract()) // If abstract, drop the reference... + cast(TI->second)->removeAbstractTypeUser(this); } - // TODO: FIXME: BIG ONE: This doesn't unreference abstract types for the planes - // that could still have entries! + // 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)) { - std::cerr << "Value still in symbol table! Type = '" - << i->first->getDescription() << "' Name = '" - << I->first << "'\n"; - LeftoverValues = false; + for (plane_iterator PI = pmap.begin(); PI != pmap.end(); ++PI) { + for (value_iterator VI = PI->second.begin(); VI != PI->second.end(); ++VI) + if (!isa(VI->second) ) { + std::cerr << "Value still in symbol table! Type = '" + << PI->first->getDescription() << "' Name = '" + << VI->first << "'\n"; + LeftoverValues = false; } } - + assert(LeftoverValues && "Values remain in symbol table!"); #endif } @@ -49,118 +55,153 @@ SymbolTable::~SymbolTable() { // the specified type. // std::string SymbolTable::getUniqueName(const Type *Ty, - const std::string &BaseName) { - iterator I = find(Ty); - if (I == end()) return BaseName; + const std::string &BaseName) const { + // Find the plane + plane_const_iterator PI = pmap.find(Ty); + if (PI == pmap.end()) return BaseName; std::string TryName = BaseName; - unsigned Counter = 0; - type_iterator End = I->second.end(); + const ValueMap& vmap = PI->second; + value_const_iterator End = vmap.end(); - while (I->second.find(TryName) != End) // Loop until we find unoccupied - TryName = BaseName + utostr(++Counter); // Name in the symbol table + // See if the name exists + while (vmap.find(TryName) != End) // Loop until we find a free + TryName = BaseName + utostr(++LastUnique); // name in the symbol table return TryName; } - -// lookup - Returns null on failure... -Value *SymbolTable::lookup(const Type *Ty, const std::string &Name) { - iterator I = find(Ty); - if (I != end()) { // We have symbols in that plane... - type_iterator J = I->second.find(Name); - if (J != I->second.end()) // and the name is in our hash table... - return J->second; +// lookup a value - Returns null on failure... +Value *SymbolTable::lookup(const Type *Ty, const std::string &Name) const { + plane_const_iterator PI = pmap.find(Ty); + if (PI != pmap.end()) { // We have symbols in that plane. + value_const_iterator VI = PI->second.find(Name); + if (VI != PI->second.end()) // and the name is in our hash table. + return VI->second; } + return 0; +} + +// lookup a type by name - returns null on failure +Type* SymbolTable::lookupType(const std::string& Name) const { + type_const_iterator TI = tmap.find(Name); + if (TI != tmap.end()) + return const_cast(TI->second); return 0; } +/// changeName - Given a value with a non-empty name, remove its existing entry +/// from the symbol table and insert a new one for Name. This is equivalent to +/// doing "remove(V), V->Name = Name, insert(V)", but is faster, and will not +/// temporarily remove the symbol table plane if V is the last value in the +/// symtab with that name (which could invalidate iterators to that plane). +void SymbolTable::changeName(Value *V, const std::string &name) { + assert(!V->getName().empty() && !name.empty() && V->getName() != name && + "Illegal use of this method!"); + + plane_iterator PI = pmap.find(V->getType()); + assert(PI != pmap.end() && "Value doesn't have an entry in this table?"); + ValueMap &VM = PI->second; + + value_iterator VI = VM.find(V->getName()); + assert(VI != VM.end() && "Value does have an entry in this table?"); + + // Remove the old entry. + VM.erase(VI); + + // See if we can insert the new name. + VI = VM.lower_bound(name); + + // Is there a naming conflict? + if (VI != VM.end() && VI->first == name) { + V->Name = getUniqueName(V->getType(), name); + VM.insert(make_pair(V->Name, V)); + } else { + V->Name = name; + VM.insert(VI, make_pair(name, V)); + } +} + +// Remove a value void SymbolTable::remove(Value *N) { assert(N->hasName() && "Value doesn't have name!"); - 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())); -} + plane_iterator PI = pmap.find(N->getType()); + assert(PI != pmap.end() && + "Trying to remove a value that doesn't have a type plane yet!"); + ValueMap &VM = PI->second; + value_iterator Entry = VM.find(N->getName()); + assert(Entry != VM.end() && "Invalid entry to remove!"); -// 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 *Result = Entry->second; - const Type *Ty = Result->getType(); #if DEBUG_SYMBOL_TABLE dump(); - std::cerr << " Removing Value: " << Result->getName() << "\n"; + std::cerr << " Removing Value: " << Entry->second->getName() << "\n"; #endif // Remove the value from the plane... - Plane->second.erase(Entry); + VM.erase(Entry); // If the plane is empty, remove it now! - if (Plane->second.empty()) { + if (VM.empty()) { // If the plane represented an abstract type that we were interested in, // unlink ourselves from this plane. // - if (Plane->first->isAbstract()) { + if (N->getType()->isAbstract()) { #if DEBUG_ABSTYPE std::cerr << "Plane Empty: Removing type: " - << Plane->first->getDescription() << "\n"; + << N->getType()->getDescription() << "\n"; #endif - cast(Plane->first)->removeAbstractTypeUser(this); + cast(N->getType())->removeAbstractTypeUser(this); } - erase(Plane); + pmap.erase(PI); } +} + +// remove - Remove a type from the symbol table... +Type* SymbolTable::remove(type_iterator Entry) { + assert(Entry != tmap.end() && "Invalid entry to remove!"); + + const Type* Result = Entry->second; + +#if DEBUG_SYMBOL_TABLE + dump(); + std::cerr << " Removing Value: " << Result->getName() << "\n"; +#endif + + tmap.erase(Entry); // 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 (Result->isAbstract()) { #if DEBUG_ABSTYPE - std::cerr << "Removing abs type from symtab" << T->getDescription()<<"\n"; + std::cerr << "Removing abstract type from symtab" << Result->getDescription()<<"\n"; #endif - cast(T)->removeAbstractTypeUser(this); - } + cast(Result)->removeAbstractTypeUser(this); } - return Result; + return const_cast(Result); } -// insertEntry - Insert a value into the symbol table with the specified -// name... -// + +// insertEntry - Insert a value into the symbol table with the specified name. void SymbolTable::insertEntry(const std::string &Name, const Type *VTy, Value *V) { - - // Check to see if there is a naming conflict. If so, rename this value! - if (lookup(VTy, Name)) { - std::string UniqueName = getUniqueName(VTy, Name); - assert(InternallyInconsistent == false && "Infinite loop inserting entry!"); - InternallyInconsistent = true; - V->setName(UniqueName, this); - InternallyInconsistent = false; - return; - } + plane_iterator PI = pmap.find(VTy); // Plane iterator + value_iterator VI; // Actual value iterator + ValueMap *VM; // The plane we care about. #if DEBUG_SYMBOL_TABLE dump(); - std::cerr << " Inserting definition: " << Name << ": " + std::cerr << " Inserting definition: " << Name << ": " << VTy->getDescription() << "\n"; #endif - iterator I = find(VTy); - if (I == end()) { // Not in collection yet... insert dummy entry + if (PI == pmap.end()) { // Not in collection yet... insert dummy entry // 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?"); + VM = &pmap.insert(make_pair(VTy, ValueMap())).first->second; + VI = VM->end(); // 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 @@ -173,37 +214,92 @@ void SymbolTable::insertEntry(const std::string &Name, const Type *VTy, << "\n"; #endif } + + } else { + // Check to see if there is a naming conflict. If so, rename this value! + VM = &PI->second; + VI = VM->lower_bound(Name); + if (VI != VM->end() && VI->first == Name) { + V->Name = getUniqueName(VTy, Name); + VM->insert(make_pair(V->Name, V)); + return; + } } - I->second.insert(make_pair(Name, V)); + VM->insert(VI, make_pair(Name, V)); +} + + +// insertEntry - Insert a value into the symbol table with the specified +// name... +// +void SymbolTable::insert(const std::string& Name, const Type* T) { + assert(T && "Can't insert null type into symbol table!"); + + // Check to see if there is a naming conflict. If so, rename this type! + std::string UniqueName = Name; + if (lookupType(Name)) + UniqueName = getUniqueName(T, Name); + +#if DEBUG_SYMBOL_TABLE + dump(); + std::cerr << " Inserting type: " << UniqueName << ": " + << T->getDescription() << "\n"; +#endif + + // Insert the tmap entry + tmap.insert(make_pair(UniqueName, T)); // 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 (T->isAbstract()) { + cast(T)->addAbstractTypeUser(this); #if DEBUG_ABSTYPE - std::cerr << "Added abstract type to ST: " << T->getDescription() << "\n"; + std::cerr << "Added abstract type to ST: " << T->getDescription() << "\n"; #endif + } +} + +// Strip the symbol table of its names. +bool SymbolTable::strip() { + bool RemovedSymbol = false; + for (plane_iterator I = pmap.begin(); I != pmap.end();) { + // Removing items from the plane can cause the plane itself to get deleted. + // If this happens, make sure we incremented our plane iterator already! + ValueMap &Plane = (I++)->second; + value_iterator B = Plane.begin(), Bend = Plane.end(); + while (B != Bend) { // Found nonempty type plane! + Value *V = B->second; + ++B; + if (!isa(V) || cast(V)->hasInternalLinkage()) { + // Set name to "", removing from symbol table! + V->setName(""); + RemovedSymbol = true; + } } } + + for (type_iterator TI = tmap.begin(); TI != tmap.end(); ) { + remove(TI++); + RemovedSymbol = true; + } + + return RemovedSymbol; } + // 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 + const Type *NewType) { - // Search to see if we have any values of the type oldtype. If so, we need to + // 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()) { + plane_iterator PI = pmap.find(OldType); + if (PI != pmap.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; - + plane_iterator NewTypeIt = pmap.find(NewType); + if (NewTypeIt == pmap.end()) { // If no plane exists, add one + NewTypeIt = pmap.insert(make_pair(NewType, ValueMap())).first; + if (NewType->isAbstract()) { cast(NewType)->addAbstractTypeUser(this); #if DEBUG_ABSTYPE @@ -213,22 +309,22 @@ void SymbolTable::refineAbstractType(const DerivedType *OldType, } } - VarMap &NewPlane = NewTypeIt->second; - VarMap &OldPlane = TPI->second; + ValueMap &NewPlane = NewTypeIt->second; + ValueMap &OldPlane = PI->second; while (!OldPlane.empty()) { std::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) { + value_iterator VI = NewPlane.find(V.first); + if (VI != NewPlane.end() && VI->second == V.second) { // No action - } else if (TI != NewPlane.end()) { + } else if (VI != NewPlane.end()) { // The only thing we are allowing for now is two external global values // folded into one. // - GlobalValue *ExistGV = dyn_cast(TI->second); + GlobalValue *ExistGV = dyn_cast(VI->second); GlobalValue *NewGV = dyn_cast(V.second); if (ExistGV && NewGV) { @@ -242,22 +338,10 @@ void SymbolTable::refineAbstractType(const DerivedType *OldType, // Ok we have two external global values. Make all uses of the new // one use the old one... NewGV->uncheckedReplaceAllUsesWith(ExistGV); - - // 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 - NewGV->setName(""); - InternallyInconsistent = false; + + // Update NewGV's name, we're about the remove it from the symbol + // table. + NewGV->Name = ""; // Now we can remove this global from the module entirely... Module *M = NewGV->getParent(); @@ -266,10 +350,16 @@ void SymbolTable::refineAbstractType(const DerivedType *OldType, else M->getGlobalList().remove(cast(NewGV)); delete NewGV; + } else { + // If they are not global values, they must be just random values who + // happen to conflict now that types have been resolved. If this is + // the case, reinsert the value into the new plane, allowing it to get + // renamed. + assert(V.second->getType() == NewType &&"Type resolution is broken!"); + insert(V.second); } } else { insertEntry(V.first, NewType, V.second); - } // Remove the item from the old type plane OldPlane.erase(OldPlane.begin()); @@ -283,56 +373,74 @@ void SymbolTable::refineAbstractType(const DerivedType *OldType, OldType->removeAbstractTypeUser(this); // Remove the plane that is no longer used - erase(TPI); - } else if (TPI != end()) { - assert(OldType == NewType); -#if DEBUG_ABSTYPE - std::cerr << "Removing SELF type " << OldType->getDescription() << "\n"; -#endif - OldType->removeAbstractTypeUser(this); + pmap.erase(PI); } - 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. + // 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 + // occurrences, and although we only need to remove one at a time, it's + // faster to remove them all in one pass. + // + for (type_iterator I = type_begin(), E = type_end(); I != E; ++I) { + if (I->second == (Type*)OldType) { // FIXME when Types aren't const. #if DEBUG_ABSTYPE - std::cerr << "Removing type " << OldType->getDescription() << "\n"; + std::cerr << "Removing type " << OldType->getDescription() << "\n"; #endif - OldType->removeAbstractTypeUser(this); - - I->second = (Value*)NewType; // TODO FIXME when types aren't const - if (NewType->isAbstract()) { + OldType->removeAbstractTypeUser(this); + + I->second = (Type*)NewType; // TODO FIXME when types aren't const + if (NewType->isAbstract()) { #if DEBUG_ABSTYPE - std::cerr << "Added type " << NewType->getDescription() << "\n"; + std::cerr << "Added type " << NewType->getDescription() << "\n"; #endif - cast(NewType)->addAbstractTypeUser(this); - } + cast(NewType)->addAbstractTypeUser(this); } + } } } + +// Handle situation where type becomes Concreate from Abstract +void SymbolTable::typeBecameConcrete(const DerivedType *AbsTy) { + plane_iterator PI = pmap.find(AbsTy); + + // If there are any values in the symbol table of this type, then the type + // plane is a use of the abstract type which must be dropped. + if (PI != pmap.end()) + AbsTy->removeAbstractTypeUser(this); + + // Loop over all of the types in the symbol table, dropping any abstract + // type user entries for AbsTy which occur because there are names for the + // type. + for (type_iterator TI = type_begin(), TE = type_end(); TI != TE; ++TI) + if (TI->second == (Type*)AbsTy) // FIXME when Types aren't const. + AbsTy->removeAbstractTypeUser(this); +} + static void DumpVal(const std::pair &V) { - std::cout << " '" << V.first << "' = "; + std::cerr << " '" << V.first << "' = "; V.second->dump(); - std::cout << "\n"; + std::cerr << "\n"; } static void DumpPlane(const std::pair >&P){ - std::cout << " Plane: "; P.first->dump(); - std::cout << "\n"; + std::cerr << "\n"; for_each(P.second.begin(), P.second.end(), DumpVal); } +static void DumpTypes(const std::pair& T ) { + std::cerr << " '" << T.first << "' = "; + T.second->dump(); + std::cerr << "\n"; +} + void SymbolTable::dump() const { - std::cout << "Symbol table dump:\n"; - for_each(begin(), end(), DumpPlane); + std::cerr << "Symbol table dump:\n Plane:"; + for_each(pmap.begin(), pmap.end(), DumpPlane); + std::cerr << " Types: "; + for_each(tmap.begin(), tmap.end(), DumpTypes); } + +// vim: sw=2 ai