X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FSlotCalculator.cpp;h=f0a549e81cc8d6e5a2e8bde0e908ec03ffe8ff79;hb=1c28b42310b183a141fa3b40d07a6cfbdb97ee02;hp=d96f829cb4fc98fd95e52e1dc52ed535580bdb5f;hpb=3fa0bc4408486327411da7fff2c5c55d8c0a3dd4;p=oota-llvm.git diff --git a/lib/VMCore/SlotCalculator.cpp b/lib/VMCore/SlotCalculator.cpp index d96f829cb4f..f0a549e81cc 100644 --- a/lib/VMCore/SlotCalculator.cpp +++ b/lib/VMCore/SlotCalculator.cpp @@ -9,14 +9,22 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/SlotCalculator.h" -#include "llvm/ConstantPool.h" -#include "llvm/Method.h" +#include "llvm/SlotCalculator.h" +#include "llvm/Analysis/ConstantsScanner.h" #include "llvm/Module.h" -#include "llvm/BasicBlock.h" -#include "llvm/ConstPoolVals.h" #include "llvm/iOther.h" +#include "llvm/Constant.h" #include "llvm/DerivedTypes.h" +#include "llvm/SymbolTable.h" +#include "Support/DepthFirstIterator.h" +#include "Support/STLExtras.h" +#include + +#if 0 +#define SC_DEBUG(X) cerr << X +#else +#define SC_DEBUG(X) +#endif SlotCalculator::SlotCalculator(const Module *M, bool IgnoreNamed) { IgnoreNamedNodes = IgnoreNamed; @@ -27,16 +35,14 @@ SlotCalculator::SlotCalculator(const Module *M, bool IgnoreNamed) { // for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) { assert(Type::getPrimitiveType((Type::PrimitiveID)i)); - insertVal(Type::getPrimitiveType((Type::PrimitiveID)i)); + insertVal(Type::getPrimitiveType((Type::PrimitiveID)i), true); } if (M == 0) return; // Empty table... - - bool Result = processModule(M); - assert(Result == false && "Error in processModule!"); + processModule(); } -SlotCalculator::SlotCalculator(const Method *M, bool IgnoreNamed) { +SlotCalculator::SlotCalculator(const Function *M, bool IgnoreNamed) { IgnoreNamedNodes = IgnoreNamed; TheModule = M ? M->getParent() : 0; @@ -45,48 +51,168 @@ SlotCalculator::SlotCalculator(const Method *M, bool IgnoreNamed) { // for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) { assert(Type::getPrimitiveType((Type::PrimitiveID)i)); - insertVal(Type::getPrimitiveType((Type::PrimitiveID)i)); + insertVal(Type::getPrimitiveType((Type::PrimitiveID)i), true); } if (TheModule == 0) return; // Empty table... - bool Result = processModule(TheModule); - assert(Result == false && "Error in processModule!"); + processModule(); // Process module level stuff + incorporateFunction(M); // Start out in incorporated state +} + + +// processModule - Process all of the module level function declarations and +// types that are available. +// +void SlotCalculator::processModule() { + SC_DEBUG("begin processModule!\n"); + + // Add all of the constants that the global variables might refer to first. + // + for (Module::const_giterator I = TheModule->gbegin(), E = TheModule->gend(); + I != E; ++I) { + if (I->hasInitializer()) + insertValue(I->getInitializer()); + } + + // Add all of the global variables to the value table... + // + for(Module::const_giterator I = TheModule->gbegin(), E = TheModule->gend(); + I != E; ++I) + insertValue(I); + + // Scavenge the types out of the functions, then add the functions themselves + // to the value table... + // + for(Module::const_iterator I = TheModule->begin(), E = TheModule->end(); + I != E; ++I) + insertValue(I); + + // Insert constants that are named at module level into the slot pool so that + // the module symbol table can refer to them... + // + if (TheModule->hasSymbolTable() && !IgnoreNamedNodes) { + SC_DEBUG("Inserting SymbolTable values:\n"); + processSymbolTable(TheModule->getSymbolTable()); + } + + SC_DEBUG("end processModule!\n"); +} - incorporateMethod(M); +// processSymbolTable - Insert all of the values in the specified symbol table +// into the values table... +// +void SlotCalculator::processSymbolTable(const SymbolTable *ST) { + for (SymbolTable::const_iterator I = ST->begin(), E = ST->end(); I != E; ++I) + for (SymbolTable::type_const_iterator TI = I->second.begin(), + TE = I->second.end(); TI != TE; ++TI) + insertValue(TI->second); } -void SlotCalculator::incorporateMethod(const Method *M) { +void SlotCalculator::processSymbolTableConstants(const SymbolTable *ST) { + for (SymbolTable::const_iterator I = ST->begin(), E = ST->end(); I != E; ++I) + for (SymbolTable::type_const_iterator TI = I->second.begin(), + TE = I->second.end(); TI != TE; ++TI) + if (isa(TI->second)) + insertValue(TI->second); +} + + +void SlotCalculator::incorporateFunction(const Function *M) { assert(ModuleLevel.size() == 0 && "Module already incorporated!"); - // Save the Table state before we process the method... - for (unsigned i = 0; i < Table.size(); ++i) { + SC_DEBUG("begin processFunction!\n"); + + // Save the Table state before we process the function... + for (unsigned i = 0; i < Table.size(); ++i) ModuleLevel.push_back(Table[i].size()); + + SC_DEBUG("Inserting function arguments\n"); + + // Iterate over function arguments, adding them to the value table... + for(Function::const_aiterator I = M->abegin(), E = M->aend(); I != E; ++I) + insertValue(I); + + // Iterate over all of the instructions in the function, looking for constant + // values that are referenced. Add these to the value pools before any + // nonconstant values. This will be turned into the constant pool for the + // bytecode writer. + // + if (!IgnoreNamedNodes) { // Assembly writer does not need this! + SC_DEBUG("Inserting function constants:\n"; + for (constant_iterator I = constant_begin(M), E = constant_end(M); + I != E; ++I) { + cerr << " " << *I->getType() + << " " << *I << "\n"; + }); + + // Emit all of the constants that are being used by the instructions in the + // function... + for_each(constant_begin(M), constant_end(M), + bind_obj(this, &SlotCalculator::insertValue)); + + // If there is a symbol table, it is possible that the user has names for + // constants that are not being used. In this case, we will have problems + // if we don't emit the constants now, because otherwise we will get + // symboltable references to constants not in the output. Scan for these + // constants now. + // + if (M->hasSymbolTable()) + processSymbolTableConstants(M->getSymbolTable()); } - // Process the method to incorporate its values into our table - processMethod(M); + SC_DEBUG("Inserting Labels:\n"); + + // Iterate over basic blocks, adding them to the value table... + for (Function::const_iterator I = M->begin(), E = M->end(); I != E; ++I) + insertValue(I); + /* for_each(M->begin(), M->end(), + bind_obj(this, &SlotCalculator::insertValue));*/ + + SC_DEBUG("Inserting Instructions:\n"); + + // Add all of the instructions to the type planes... + for_each(inst_begin(M), inst_end(M), + bind_obj(this, &SlotCalculator::insertValue)); + + if (M->hasSymbolTable() && !IgnoreNamedNodes) { + SC_DEBUG("Inserting SymbolTable values:\n"); + processSymbolTable(M->getSymbolTable()); + } + + SC_DEBUG("end processFunction!\n"); } -void SlotCalculator::purgeMethod() { +void SlotCalculator::purgeFunction() { assert(ModuleLevel.size() != 0 && "Module not incorporated!"); unsigned NumModuleTypes = ModuleLevel.size(); + SC_DEBUG("begin purgeFunction!\n"); + // First, remove values from existing type planes for (unsigned i = 0; i < NumModuleTypes; ++i) { - unsigned ModuleSize = ModuleLevel[i]; // Size of plane before method came - while (Table[i].size() != ModuleSize) { - NodeMap.erase(NodeMap.find(Table[i].back())); // Erase from nodemap - Table[i].pop_back(); // Shrink plane + unsigned ModuleSize = ModuleLevel[i]; // Size of plane before function came + TypePlane &CurPlane = Table[i]; + //SC_DEBUG("Processing Plane " <::iterator NI = + NodeMap.find(CurPlane.back()); + assert(NI != NodeMap.end() && "Node not in nodemap?"); + NodeMap.erase(NI); // Erase from nodemap + CurPlane.pop_back(); // Shrink plane } } // We don't need this state anymore, free it up. ModuleLevel.clear(); - // Next, remove any type planes defined by the method... + // Next, remove any type planes defined by the function... while (NumModuleTypes != Table.size()) { TypePlane &Plane = Table.back(); + SC_DEBUG("Removing Plane " << (Table.size()-1) << " of size " + << Plane.size() << endl); while (Plane.size()) { NodeMap.erase(NodeMap.find(Plane.back())); // Erase from nodemap Plane.pop_back(); // Shrink plane @@ -94,101 +220,127 @@ void SlotCalculator::purgeMethod() { Table.pop_back(); // Nuke the plane, we don't like it. } -} -bool SlotCalculator::processConstant(const ConstPoolVal *CPV) { - //cerr << "Inserting constant: '" << CPV->getStrValue() << endl; - insertVal(CPV); - return false; + SC_DEBUG("end purgeFunction!\n"); } -// processType - This callback occurs when an derived type is discovered -// at the class level. This activity occurs when processing a constant pool. -// -bool SlotCalculator::processType(const Type *Ty) { - //cerr << "processType: " << Ty->getName() << endl; - // TODO: Don't leak memory!!! Free this in the dtor! - insertVal(new ConstPoolType(Ty)); - return false; +int SlotCalculator::getValSlot(const Value *D) const { + std::map::const_iterator I = NodeMap.find(D); + if (I == NodeMap.end()) return -1; + + return (int)I->second; } -bool SlotCalculator::visitMethod(const Method *M) { - //cerr << "visitMethod: '" << M->getType()->getName() << "'\n"; - insertVal(M); - return false; -} -bool SlotCalculator::processMethodArgument(const MethodArgument *MA) { - insertVal(MA); - return false; -} +int SlotCalculator::insertValue(const Value *D) { + if (isa(D) || isa(D)) { + const User *U = cast(D); + // This makes sure that if a constant has uses (for example an array + // of const ints), that they are inserted also. Same for global variable + // initializers. + // + for(User::const_op_iterator I = U->op_begin(), E = U->op_end(); I != E; ++I) + if (!isa(*I)) // Don't chain insert global values + insertValue(*I); + } -bool SlotCalculator::processBasicBlock(const BasicBlock *BB) { - insertVal(BB); - ModuleAnalyzer::processBasicBlock(BB); // Lets visit the instructions too! - return false; + int SlotNo = getValSlot(D); // Check to see if it's already in! + if (SlotNo != -1) return SlotNo; + return insertVal(D); } -bool SlotCalculator::processInstruction(const Instruction *I) { - insertVal(I); - return false; -} -int SlotCalculator::getValSlot(const Value *D) const { - map::const_iterator I = NodeMap.find(D); - if (I == NodeMap.end()) return -1; - - return (int)I->second; -} - -void SlotCalculator::insertVal(const Value *D) { - if (D == 0) return; +int SlotCalculator::insertVal(const Value *D, bool dontIgnore) { + assert(D && "Can't insert a null value!"); + assert(getValSlot(D) == -1 && "Value is already in the table!"); // If this node does not contribute to a plane, or if the node has a - // name and we don't want names, then ignore the silly node... + // name and we don't want names, then ignore the silly node... Note that types + // do need slot numbers so that we can keep track of where other values land. // - if (D->getType() == Type::VoidTy || (IgnoreNamedNodes && D->hasName())) - return; + if (!dontIgnore) // Don't ignore nonignorables! + if (D->getType() == Type::VoidTy || // Ignore void type nodes + (IgnoreNamedNodes && // Ignore named and constants + (D->hasName() || isa(D)) && !isa(D))) { + SC_DEBUG("ignored value " << D << endl); + return -1; // We do need types unconditionally though + } + + // If it's a type, make sure that all subtypes of the type are included... + if (const Type *TheTy = dyn_cast(D)) { + + // Insert the current type before any subtypes. This is important because + // recursive types elements are inserted in a bottom up order. Changing + // this here can break things. For example: + // + // global { \2 * } { { \2 }* null } + // + int ResultSlot; + if ((ResultSlot = getValSlot(TheTy)) == -1) { + ResultSlot = doInsertVal(TheTy); + SC_DEBUG(" Inserted type: " << TheTy->getDescription() << " slot=" << + ResultSlot << endl); + } + + // Loop over any contained types in the definition... in reverse depth first + // order. This assures that all of the leafs of a type are output before + // the type itself is. This also assures us that we will not hit infinite + // recursion on recursive types... + // + for (df_iterator I = df_begin(TheTy, true), + E = df_end(TheTy); I != E; ++I) + if (*I != TheTy) { + // If we haven't seen this sub type before, add it to our type table! + const Type *SubTy = *I; + if (getValSlot(SubTy) == -1) { + SC_DEBUG(" Inserting subtype: " << SubTy->getDescription() << endl); + int Slot = doInsertVal(SubTy); + SC_DEBUG(" Inserted subtype: " << SubTy->getDescription() << + " slot=" << Slot << endl); + } + } + return ResultSlot; + } + + // Okay, everything is happy, actually insert the silly value now... + return doInsertVal(D); +} + +// doInsertVal - This is a small helper function to be called only be insertVal. +// +int SlotCalculator::doInsertVal(const Value *D) { const Type *Typ = D->getType(); - unsigned Ty = Typ->getPrimitiveID(); + unsigned Ty; + + // Used for debugging DefSlot=-1 assertion... + //if (Typ == Type::TypeTy) + // cerr << "Inserting type '" << cast(D)->getDescription() << "'!\n"; + if (Typ->isDerivedType()) { int DefSlot = getValSlot(Typ); if (DefSlot == -1) { // Have we already entered this type? - // This can happen if a type is first seen in an instruction. For - // example, if you say 'malloc uint', this defines a type 'uint*' that - // may be undefined at this point. - // - cerr << "SHOULDN'T HAPPEN Adding Type ba: " << Typ->getName() << endl; - assert(0 && "Shouldn't this be taken care of by processType!?!?!"); - // Nope... add this to the Type plane now! - insertVal(Typ); - - DefSlot = getValSlot(Typ); - assert(DefSlot >= 0 && "Type didn't get inserted correctly!"); + // Nope, this is the first we have seen the type, process it. + DefSlot = insertVal(Typ, true); + assert(DefSlot != -1 && "ProcessType returned -1 for a type?"); } Ty = (unsigned)DefSlot; + } else { + Ty = Typ->getPrimitiveID(); } if (Table.size() <= Ty) // Make sure we have the type plane allocated... Table.resize(Ty+1, TypePlane()); // Insert node into table and NodeMap... - NodeMap[D] = Table[Ty].size(); - - if (Typ == Type::TypeTy && !D->isType()) { - // If it's a type constant, add the Type also - - // All Type instances should be constant types! - const ConstPoolType *CPT = (const ConstPoolType*)D->castConstantAsserting(); - int Slot = getValSlot(CPT->getValue()); - if (Slot == -1) { - // Only add if it's not already here! - NodeMap[CPT->getValue()] = Table[Ty].size(); - } else if (!CPT->hasName()) { // If the type has no name... - NodeMap[D] = (unsigned)Slot; // Don't readd type, merge. - return; - } - } + unsigned DestSlot = NodeMap[D] = Table[Ty].size(); Table[Ty].push_back(D); + + SC_DEBUG(" Inserting value [" << Ty << "] = " << D << " slot=" << + DestSlot << " ["); + // G = Global, C = Constant, T = Type, F = Function, o = other + SC_DEBUG((isa(D) ? "G" : (isa(D) ? "C" : + (isa(D) ? "T" : (isa(D) ? "F" : "o"))))); + SC_DEBUG("]\n"); + return (int)DestSlot; }