X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FBitcode%2FWriter%2FValueEnumerator.cpp;h=1430fad88accdbf1f92ab09d7c99c30e4e36c8ee;hp=d840d4ae9fe9f869d7e3c55d9bd5d06452d43ae9;hb=17cb4cb5a37dddf858629ea0181179acaf8c695f;hpb=837e04a8bf13712a4a8ae279daab65a048b21f7d diff --git a/lib/Bitcode/Writer/ValueEnumerator.cpp b/lib/Bitcode/Writer/ValueEnumerator.cpp index d840d4ae9fe..1430fad88ac 100644 --- a/lib/Bitcode/Writer/ValueEnumerator.cpp +++ b/lib/Bitcode/Writer/ValueEnumerator.cpp @@ -12,37 +12,25 @@ //===----------------------------------------------------------------------===// #include "ValueEnumerator.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/LLVMContext.h" -#include "llvm/Metadata.h" -#include "llvm/Module.h" -#include "llvm/TypeSymbolTable.h" -#include "llvm/ValueSymbolTable.h" -#include "llvm/Instructions.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/UseListOrder.h" +#include "llvm/IR/ValueSymbolTable.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include using namespace llvm; -static bool isSingleValueType(const std::pair &P) { - return P.first->isSingleValueType(); -} - -static bool isIntegerValue(const std::pair &V) { - return isa(V.first->getType()); -} - -static bool CompareByFrequency(const std::pair &P1, - const std::pair &P2) { - return P1.second > P2.second; +static bool isIntOrIntVectorValue(const std::pair &V) { + return V.first->getType()->isIntOrIntVectorTy(); } /// ValueEnumerator - Enumerate module-level information. ValueEnumerator::ValueEnumerator(const Module *M) { - InstructionCount = 0; - // Enumerate the global variables. for (Module::const_global_iterator I = M->global_begin(), E = M->global_end(); I != E; ++I) @@ -73,64 +61,67 @@ ValueEnumerator::ValueEnumerator(const Module *M) { I != E; ++I) EnumerateValue(I->getAliasee()); - // Enumerate types used by the type symbol table. - EnumerateTypeSymbolTable(M->getTypeSymbolTable()); + // Enumerate the prefix data constants. + for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) + if (I->hasPrefixData()) + EnumerateValue(I->getPrefixData()); - // Insert constants that are named at module level into the slot pool so that - // the module symbol table can refer to them... + // Insert constants and metadata that are named at module level into the slot + // pool so that the module symbol table can refer to them... EnumerateValueSymbolTable(M->getValueSymbolTable()); + EnumerateNamedMetadata(M); + + SmallVector, 8> MDs; // Enumerate types used by function bodies and argument lists. - for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) { - - for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); - I != E; ++I) - EnumerateType(I->getType()); - - MetadataContext &TheMetadata = F->getContext().getMetadata(); - typedef SmallVector >, 2> MDMapTy; - MDMapTy MDs; - for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){ - for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); - OI != E; ++OI) - EnumerateOperandType(*OI); - EnumerateType(I->getType()); - if (const CallInst *CI = dyn_cast(I)) + for (const Function &F : *M) { + for (const Argument &A : F.args()) + EnumerateType(A.getType()); + + for (const BasicBlock &BB : F) + for (const Instruction &I : BB) { + for (const Use &Op : I.operands()) { + if (MDNode *MD = dyn_cast(&Op)) + if (MD->isFunctionLocal() && MD->getFunction()) + // These will get enumerated during function-incorporation. + continue; + EnumerateOperandType(Op); + } + EnumerateType(I.getType()); + if (const CallInst *CI = dyn_cast(&I)) EnumerateAttributes(CI->getAttributes()); - else if (const InvokeInst *II = dyn_cast(I)) + else if (const InvokeInst *II = dyn_cast(&I)) EnumerateAttributes(II->getAttributes()); // Enumerate metadata attached with this instruction. MDs.clear(); - TheMetadata.getMDs(I, MDs); - for (MDMapTy::const_iterator MI = MDs.begin(), ME = MDs.end(); MI != ME; - ++MI) - EnumerateMetadata(MI->second); + I.getAllMetadataOtherThanDebugLoc(MDs); + for (unsigned i = 0, e = MDs.size(); i != e; ++i) + EnumerateMetadata(MDs[i].second); + + if (!I.getDebugLoc().isUnknown()) { + MDNode *Scope, *IA; + I.getDebugLoc().getScopeAndInlinedAt(Scope, IA, I.getContext()); + if (Scope) EnumerateMetadata(Scope); + if (IA) EnumerateMetadata(IA); + } } } // Optimize constant ordering. OptimizeConstants(FirstConstant, Values.size()); - - // Sort the type table by frequency so that most commonly used types are early - // in the table (have low bit-width). - std::stable_sort(Types.begin(), Types.end(), CompareByFrequency); - - // Partition the Type ID's so that the single-value types occur before the - // aggregate types. This allows the aggregate types to be dropped from the - // type table after parsing the global variable initializers. - std::partition(Types.begin(), Types.end(), isSingleValueType); - - // Now that we rearranged the type table, rebuild TypeMap. - for (unsigned i = 0, e = Types.size(); i != e; ++i) - TypeMap[Types[i].first] = i+1; } unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const { InstructionMapType::const_iterator I = InstructionMap.find(Inst); - assert (I != InstructionMap.end() && "Instruction is not mapped!"); - return I->second; + assert(I != InstructionMap.end() && "Instruction is not mapped!"); + return I->second; +} + +unsigned ValueEnumerator::getComdatID(const Comdat *C) const { + unsigned ComdatID = Comdats.idFor(C); + assert(ComdatID && "Comdat not found!"); + return ComdatID; } void ValueEnumerator::setInstructionID(const Instruction *I) { @@ -138,7 +129,7 @@ void ValueEnumerator::setInstructionID(const Instruction *I) { } unsigned ValueEnumerator::getValueID(const Value *V) const { - if (isa(V)) { + if (isa(V) || isa(V)) { ValueMapType::const_iterator I = MDValueMap.find(V); assert(I != MDValueMap.end() && "Value not in slotcalculator!"); return I->second-1; @@ -149,34 +140,66 @@ unsigned ValueEnumerator::getValueID(const Value *V) const { return I->second-1; } -// Optimize constant ordering. -namespace { - struct CstSortPredicate { - ValueEnumerator &VE; - explicit CstSortPredicate(ValueEnumerator &ve) : VE(ve) {} - bool operator()(const std::pair &LHS, - const std::pair &RHS) { - // Sort by plane. - if (LHS.first->getType() != RHS.first->getType()) - return VE.getTypeID(LHS.first->getType()) < - VE.getTypeID(RHS.first->getType()); - // Then by frequency. - return LHS.second > RHS.second; +void ValueEnumerator::dump() const { + print(dbgs(), ValueMap, "Default"); + dbgs() << '\n'; + print(dbgs(), MDValueMap, "MetaData"); + dbgs() << '\n'; +} + +void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map, + const char *Name) const { + + OS << "Map Name: " << Name << "\n"; + OS << "Size: " << Map.size() << "\n"; + for (ValueMapType::const_iterator I = Map.begin(), + E = Map.end(); I != E; ++I) { + + const Value *V = I->first; + if (V->hasName()) + OS << "Value: " << V->getName(); + else + OS << "Value: [null]\n"; + V->dump(); + + OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):"; + for (const Use &U : V->uses()) { + if (&U != &*V->use_begin()) + OS << ","; + if(U->hasName()) + OS << " " << U->getName(); + else + OS << " [null]"; + } - }; + OS << "\n\n"; + } } /// OptimizeConstants - Reorder constant pool for denser encoding. void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { if (CstStart == CstEnd || CstStart+1 == CstEnd) return; - CstSortPredicate P(*this); - std::stable_sort(Values.begin()+CstStart, Values.begin()+CstEnd, P); + if (shouldPreserveBitcodeUseListOrder()) + // Optimizing constants makes the use-list order difficult to predict. + // Disable it for now when trying to preserve the order. + return; - // Ensure that integer constants are at the start of the constant pool. This - // is important so that GEP structure indices come before gep constant exprs. + std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd, + [this](const std::pair &LHS, + const std::pair &RHS) { + // Sort by plane. + if (LHS.first->getType() != RHS.first->getType()) + return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType()); + // Then by frequency. + return LHS.second > RHS.second; + }); + + // Ensure that integer and vector of integer constants are at the start of the + // constant pool. This is important so that GEP structure indices come before + // gep constant exprs. std::partition(Values.begin()+CstStart, Values.begin()+CstEnd, - isIntegerValue); + isIntOrIntVectorValue); // Rebuild the modified portion of ValueMap. for (; CstStart != CstEnd; ++CstStart) @@ -184,14 +207,6 @@ void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { } -/// EnumerateTypeSymbolTable - Insert all of the types in the specified symbol -/// table. -void ValueEnumerator::EnumerateTypeSymbolTable(const TypeSymbolTable &TST) { - for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end(); - TI != TE; ++TI) - EnumerateType(TI->second); -} - /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol /// table into the values table. void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { @@ -200,7 +215,48 @@ void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { EnumerateValue(VI->getValue()); } -void ValueEnumerator::EnumerateMetadata(const MetadataBase *MD) { +/// EnumerateNamedMetadata - Insert all of the values referenced by +/// named metadata in the specified module. +void ValueEnumerator::EnumerateNamedMetadata(const Module *M) { + for (Module::const_named_metadata_iterator I = M->named_metadata_begin(), + E = M->named_metadata_end(); I != E; ++I) + EnumerateNamedMDNode(I); +} + +void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) { + for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) + EnumerateMetadata(MD->getOperand(i)); +} + +/// EnumerateMDNodeOperands - Enumerate all non-function-local values +/// and types referenced by the given MDNode. +void ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) { + for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { + if (Value *V = N->getOperand(i)) { + if (isa(V) || isa(V)) + EnumerateMetadata(V); + else if (!isa(V) && !isa(V)) + EnumerateValue(V); + } else + EnumerateType(Type::getVoidTy(N->getContext())); + } +} + +void ValueEnumerator::EnumerateMetadata(const Value *MD) { + assert((isa(MD) || isa(MD)) && "Invalid metadata kind"); + + // Enumerate the type of this value. + EnumerateType(MD->getType()); + + const MDNode *N = dyn_cast(MD); + + // In the module-level pass, skip function-local nodes themselves, but + // do walk their operands. + if (N && N->isFunctionLocal() && N->getFunction()) { + EnumerateMDNodeOperands(N); + return; + } + // Check to see if it's already in! unsigned &MDValueID = MDValueMap[MD]; if (MDValueID) { @@ -208,44 +264,52 @@ void ValueEnumerator::EnumerateMetadata(const MetadataBase *MD) { MDValues[MDValueID-1].second++; return; } + MDValues.push_back(std::make_pair(MD, 1U)); + MDValueID = MDValues.size(); + + // Enumerate all non-function-local operands. + if (N) + EnumerateMDNodeOperands(N); +} + +/// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata +/// information reachable from the given MDNode. +void ValueEnumerator::EnumerateFunctionLocalMetadata(const MDNode *N) { + assert(N->isFunctionLocal() && N->getFunction() && + "EnumerateFunctionLocalMetadata called on non-function-local mdnode!"); // Enumerate the type of this value. - EnumerateType(MD->getType()); + EnumerateType(N->getType()); - if (const MDNode *N = dyn_cast(MD)) { - MDValues.push_back(std::make_pair(MD, 1U)); - MDValueMap[MD] = MDValues.size(); - MDValueID = MDValues.size(); - for (unsigned i = 0, e = N->getNumElements(); i != e; ++i) { - if (Value *V = N->getElement(i)) - EnumerateValue(V); - else - EnumerateType(Type::getVoidTy(MD->getContext())); - } + // Check to see if it's already in! + unsigned &MDValueID = MDValueMap[N]; + if (MDValueID) { + // Increment use count. + MDValues[MDValueID-1].second++; return; } - - if (const NamedMDNode *N = dyn_cast(MD)) { - for(NamedMDNode::const_elem_iterator I = N->elem_begin(), - E = N->elem_end(); I != E; ++I) { - MetadataBase *M = *I; - EnumerateValue(M); + MDValues.push_back(std::make_pair(N, 1U)); + MDValueID = MDValues.size(); + + // To incoroporate function-local information visit all function-local + // MDNodes and all function-local values they reference. + for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) + if (Value *V = N->getOperand(i)) { + if (MDNode *O = dyn_cast(V)) { + if (O->isFunctionLocal() && O->getFunction()) + EnumerateFunctionLocalMetadata(O); + } else if (isa(V) || isa(V)) + EnumerateValue(V); } - MDValues.push_back(std::make_pair(MD, 1U)); - MDValueMap[MD] = Values.size(); - return; - } - // Add the value. - MDValues.push_back(std::make_pair(MD, 1U)); - MDValueID = MDValues.size(); + // Also, collect all function-local MDNodes for easy access. + FunctionLocalMDs.push_back(N); } void ValueEnumerator::EnumerateValue(const Value *V) { - assert(V->getType() != Type::getVoidTy(V->getContext()) && - "Can't insert void values!"); - if (const MetadataBase *MB = dyn_cast(V)) - return EnumerateMetadata(MB); + assert(!V->getType()->isVoidTy() && "Can't insert void values!"); + assert(!isa(V) && !isa(V) && + "EnumerateValue doesn't handle Metadata!"); // Check to see if it's already in! unsigned &ValueID = ValueMap[V]; @@ -255,16 +319,16 @@ void ValueEnumerator::EnumerateValue(const Value *V) { return; } + if (auto *GO = dyn_cast(V)) + if (const Comdat *C = GO->getComdat()) + Comdats.insert(C); + // Enumerate the type of this value. EnumerateType(V->getType()); if (const Constant *C = dyn_cast(V)) { if (isa(C)) { // Initializers for globals are handled explicitly elsewhere. - } else if (isa(C) && cast(C)->isString()) { - // Do not enumerate the initializers for an array of simple characters. - // The initializers just polute the value table, and we emit the strings - // specially. } else if (C->getNumOperands()) { // If a constant has operands, enumerate them. This makes sure that if a // constant has uses (for example an array of const ints), that they are @@ -293,29 +357,48 @@ void ValueEnumerator::EnumerateValue(const Value *V) { } -void ValueEnumerator::EnumerateType(const Type *Ty) { - unsigned &TypeID = TypeMap[Ty]; +void ValueEnumerator::EnumerateType(Type *Ty) { + unsigned *TypeID = &TypeMap[Ty]; - if (TypeID) { - // If we've already seen this type, just increase its occurrence count. - Types[TypeID-1].second++; + // We've already seen this type. + if (*TypeID) return; - } - // First time we saw this type, add it. - Types.push_back(std::make_pair(Ty, 1U)); - TypeID = Types.size(); + // If it is a non-anonymous struct, mark the type as being visited so that we + // don't recursively visit it. This is safe because we allow forward + // references of these in the bitcode reader. + if (StructType *STy = dyn_cast(Ty)) + if (!STy->isLiteral()) + *TypeID = ~0U; - // Enumerate subtypes. + // Enumerate all of the subtypes before we enumerate this type. This ensures + // that the type will be enumerated in an order that can be directly built. for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); I != E; ++I) EnumerateType(*I); + + // Refresh the TypeID pointer in case the table rehashed. + TypeID = &TypeMap[Ty]; + + // Check to see if we got the pointer another way. This can happen when + // enumerating recursive types that hit the base case deeper than they start. + // + // If this is actually a struct that we are treating as forward ref'able, + // then emit the definition now that all of its contents are available. + if (*TypeID && *TypeID != ~0U) + return; + + // Add this type now that its contents are all happily enumerated. + Types.push_back(Ty); + + *TypeID = Types.size(); } // Enumerate the types for the specified value. If the value is a constant, // walk through it, enumerating the types of the constant. void ValueEnumerator::EnumerateOperandType(const Value *V) { EnumerateType(V->getType()); + if (const Constant *C = dyn_cast(V)) { // If this constant is already enumerated, ignore it, we know its type must // be enumerated. @@ -324,42 +407,54 @@ void ValueEnumerator::EnumerateOperandType(const Value *V) { // This constant may have operands, make sure to enumerate the types in // them. for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { - const User *Op = C->getOperand(i); - + const Value *Op = C->getOperand(i); + // Don't enumerate basic blocks here, this happens as operands to // blockaddress. if (isa(Op)) continue; - - EnumerateOperandType(cast(Op)); + + EnumerateOperandType(Op); } if (const MDNode *N = dyn_cast(V)) { - for (unsigned i = 0, e = N->getNumElements(); i != e; ++i) - if (Value *Elem = N->getElement(i)) + for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) + if (Value *Elem = N->getOperand(i)) EnumerateOperandType(Elem); } } else if (isa(V) || isa(V)) - EnumerateValue(V); + EnumerateMetadata(V); } -void ValueEnumerator::EnumerateAttributes(const AttrListPtr &PAL) { +void ValueEnumerator::EnumerateAttributes(AttributeSet PAL) { if (PAL.isEmpty()) return; // null is always 0. + // Do a lookup. - unsigned &Entry = AttributeMap[PAL.getRawPointer()]; + unsigned &Entry = AttributeMap[PAL]; if (Entry == 0) { // Never saw this before, add it. - Attributes.push_back(PAL); - Entry = Attributes.size(); + Attribute.push_back(PAL); + Entry = Attribute.size(); } -} + // Do lookups for all attribute groups. + for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) { + AttributeSet AS = PAL.getSlotAttributes(i); + unsigned &Entry = AttributeGroupMap[AS]; + if (Entry == 0) { + AttributeGroups.push_back(AS); + Entry = AttributeGroups.size(); + } + } +} void ValueEnumerator::incorporateFunction(const Function &F) { + InstructionCount = 0; NumModuleValues = Values.size(); + NumModuleMDValues = MDValues.size(); // Adding function arguments to the value table. - for(Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); - I != E; ++I) + for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); + I != E; ++I) EnumerateValue(I); FirstFuncConstantID = Values.size(); @@ -386,24 +481,49 @@ void ValueEnumerator::incorporateFunction(const Function &F) { FirstInstID = Values.size(); + SmallVector FnLocalMDVector; // Add all of the instructions. for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) { - if (I->getType() != Type::getVoidTy(F.getContext())) + for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); + OI != E; ++OI) { + if (MDNode *MD = dyn_cast(*OI)) + if (MD->isFunctionLocal() && MD->getFunction()) + // Enumerate metadata after the instructions they might refer to. + FnLocalMDVector.push_back(MD); + } + + SmallVector, 8> MDs; + I->getAllMetadataOtherThanDebugLoc(MDs); + for (unsigned i = 0, e = MDs.size(); i != e; ++i) { + MDNode *N = MDs[i].second; + if (N->isFunctionLocal() && N->getFunction()) + FnLocalMDVector.push_back(N); + } + + if (!I->getType()->isVoidTy()) EnumerateValue(I); } } + + // Add all of the function-local metadata. + for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) + EnumerateFunctionLocalMetadata(FnLocalMDVector[i]); } void ValueEnumerator::purgeFunction() { /// Remove purged values from the ValueMap. for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i) ValueMap.erase(Values[i].first); + for (unsigned i = NumModuleMDValues, e = MDValues.size(); i != e; ++i) + MDValueMap.erase(MDValues[i].first); for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) ValueMap.erase(BasicBlocks[i]); Values.resize(NumModuleValues); + MDValues.resize(NumModuleMDValues); BasicBlocks.clear(); + FunctionLocalMDs.clear(); } static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,