X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FBitcode%2FWriter%2FValueEnumerator.cpp;h=24b077bbcefe3db6d7fd0638516d7e3dc3480669;hb=0a7fb6f94a32e03af8db830e3218c84bcdc3b108;hp=09b6c470802b97a7197c537d9cd5e31714f6a894;hpb=9b9c19509fc7eb63f023915aaad063ebe1953d15;p=oota-llvm.git diff --git a/lib/Bitcode/Writer/ValueEnumerator.cpp b/lib/Bitcode/Writer/ValueEnumerator.cpp index 09b6c470802..24b077bbcef 100644 --- a/lib/Bitcode/Writer/ValueEnumerator.cpp +++ b/lib/Bitcode/Writer/ValueEnumerator.cpp @@ -15,6 +15,7 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/IR/Constants.h" +#include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Module.h" @@ -45,6 +46,11 @@ struct OrderMap { std::pair lookup(const Value *V) const { return IDs.lookup(V); } + void index(const Value *V) { + // Explicitly sequence get-size and insert-value operations to avoid UB. + unsigned ID = IDs.size() + 1; + IDs[V].first = ID; + } }; } @@ -59,11 +65,11 @@ static void orderValue(const Value *V, OrderMap &OM) { orderValue(Op, OM); // Note: we cannot cache this lookup above, since inserting into the map - // changes the map's size, and thus affects the ID. - OM[V].first = OM.size() + 1; + // changes the map's size, and thus affects the other IDs. + OM.index(V); } -static OrderMap orderModule(const Module *M) { +static OrderMap orderModule(const Module &M) { // This needs to match the order used by ValueEnumerator::ValueEnumerator() // and ValueEnumerator::incorporateFunction(). OrderMap OM; @@ -73,14 +79,21 @@ static OrderMap orderModule(const Module *M) { // directly in predictValueUseListOrderImpl(), just assign IDs to // initializers of GlobalValues before GlobalValues themselves to model this // implicitly. - for (const GlobalVariable &G : M->globals()) + for (const GlobalVariable &G : M.globals()) if (G.hasInitializer()) - orderValue(G.getInitializer(), OM); - for (const GlobalAlias &A : M->aliases()) - orderValue(A.getAliasee(), OM); - for (const Function &F : *M) + if (!isa(G.getInitializer())) + orderValue(G.getInitializer(), OM); + for (const GlobalAlias &A : M.aliases()) + if (!isa(A.getAliasee())) + orderValue(A.getAliasee(), OM); + for (const Function &F : M) { if (F.hasPrefixData()) - orderValue(F.getPrefixData(), OM); + if (!isa(F.getPrefixData())) + orderValue(F.getPrefixData(), OM); + if (F.hasPrologueData()) + if (!isa(F.getPrologueData())) + orderValue(F.getPrologueData(), OM); + } OM.LastGlobalConstantID = OM.size(); // Initializers of GlobalValues are processed in @@ -91,15 +104,15 @@ static OrderMap orderModule(const Module *M) { // Since GlobalValues never reference each other directly (just through // initializers), their relative IDs only matter for determining order of // uses in their initializers. - for (const Function &F : *M) + for (const Function &F : M) orderValue(&F, OM); - for (const GlobalAlias &A : M->aliases()) + for (const GlobalAlias &A : M.aliases()) orderValue(&A, OM); - for (const GlobalVariable &G : M->globals()) + for (const GlobalVariable &G : M.globals()) orderValue(&G, OM); OM.LastGlobalValueID = OM.size(); - for (const Function &F : *M) { + for (const Function &F : M) { if (F.isDeclaration()) continue; // Here we need to match the union of ValueEnumerator::incorporateFunction() @@ -158,13 +171,13 @@ static void predictValueUseListOrderImpl(const Value *V, const Function *F, // If ID is 4, then expect: 7 6 5 1 2 3. if (LID < RID) { - if (RID < ID) + if (RID <= ID) if (!IsGlobalValue) // GlobalValue uses don't get reversed. return true; return false; } if (RID < LID) { - if (LID < ID) + if (LID <= ID) if (!IsGlobalValue) // GlobalValue uses don't get reversed. return false; return true; @@ -172,7 +185,7 @@ static void predictValueUseListOrderImpl(const Value *V, const Function *F, // LID and RID are equal, so we have different operands of the same user. // Assume operands are added in order for all instructions. - if (LID < ID) + if (LID <= ID) if (!IsGlobalValue) // GlobalValue uses don't get reversed. return LU->getOperandNo() < RU->getOperandNo(); return LU->getOperandNo() > RU->getOperandNo(); @@ -206,13 +219,13 @@ static void predictValueUseListOrder(const Value *V, const Function *F, // Recursive descent into constants. if (const Constant *C = dyn_cast(V)) - if (C->getNumOperands() && !isa(C)) + if (C->getNumOperands()) // Visit GlobalValues. for (const Value *Op : C->operands()) - if (isa(Op) && !isa(Op)) + if (isa(Op)) // Visit GlobalValues. predictValueUseListOrder(Op, F, OM, Stack); } -static UseListOrderStack predictUseListOrder(const Module *M) { +static UseListOrderStack predictUseListOrder(const Module &M) { OrderMap OM = orderModule(M); // Use-list orders need to be serialized after all the users have been added @@ -225,7 +238,7 @@ static UseListOrderStack predictUseListOrder(const Module *M) { // We want to visit the functions backward now so we can list function-local // constants in the last Function they're used in. Module-level constants // have already been visited above. - for (auto I = M->rbegin(), E = M->rend(); I != E; ++I) { + for (auto I = M.rbegin(), E = M.rend(); I != E; ++I) { const Function &F = *I; if (F.isDeclaration()) continue; @@ -236,8 +249,7 @@ static UseListOrderStack predictUseListOrder(const Module *M) { for (const BasicBlock &BB : F) for (const Instruction &I : BB) for (const Value *Op : I.operands()) - if ((isa(*Op) && !isa(*Op)) || - isa(*Op)) + if (isa(*Op) || isa(*Op)) // Visit GlobalValues. predictValueUseListOrder(Op, &F, OM, Stack); for (const BasicBlock &BB : F) for (const Instruction &I : BB) @@ -246,20 +258,23 @@ static UseListOrderStack predictUseListOrder(const Module *M) { // Visit globals last, since the module-level use-list block will be seen // before the function bodies are processed. - for (const GlobalVariable &G : M->globals()) + for (const GlobalVariable &G : M.globals()) predictValueUseListOrder(&G, nullptr, OM, Stack); - for (const Function &F : *M) + for (const Function &F : M) predictValueUseListOrder(&F, nullptr, OM, Stack); - for (const GlobalAlias &A : M->aliases()) + for (const GlobalAlias &A : M.aliases()) predictValueUseListOrder(&A, nullptr, OM, Stack); - for (const GlobalVariable &G : M->globals()) + for (const GlobalVariable &G : M.globals()) if (G.hasInitializer()) predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack); - for (const GlobalAlias &A : M->aliases()) + for (const GlobalAlias &A : M.aliases()) predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack); - for (const Function &F : *M) + for (const Function &F : M) { if (F.hasPrefixData()) predictValueUseListOrder(F.getPrefixData(), nullptr, OM, Stack); + if (F.hasPrologueData()) + predictValueUseListOrder(F.getPrologueData(), nullptr, OM, Stack); + } return Stack; } @@ -268,25 +283,24 @@ static bool isIntOrIntVectorValue(const std::pair &V) { return V.first->getType()->isIntOrIntVectorTy(); } -/// ValueEnumerator - Enumerate module-level information. -ValueEnumerator::ValueEnumerator(const Module *M) { +ValueEnumerator::ValueEnumerator(const Module &M) + : HasMDString(false), HasMDLocation(false), HasGenericDebugNode(false) { if (shouldPreserveBitcodeUseListOrder()) UseListOrders = predictUseListOrder(M); // Enumerate the global variables. - for (Module::const_global_iterator I = M->global_begin(), - - E = M->global_end(); I != E; ++I) + for (Module::const_global_iterator I = M.global_begin(), E = M.global_end(); + I != E; ++I) EnumerateValue(I); // Enumerate the functions. - for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) { + for (Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I) { EnumerateValue(I); EnumerateAttributes(cast(I)->getAttributes()); } // Enumerate the aliases. - for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); + for (Module::const_alias_iterator I = M.alias_begin(), E = M.alias_end(); I != E; ++I) EnumerateValue(I); @@ -294,41 +308,58 @@ ValueEnumerator::ValueEnumerator(const Module *M) { unsigned FirstConstant = Values.size(); // Enumerate the global variable initializers. - for (Module::const_global_iterator I = M->global_begin(), - E = M->global_end(); I != E; ++I) + for (Module::const_global_iterator I = M.global_begin(), E = M.global_end(); + I != E; ++I) if (I->hasInitializer()) EnumerateValue(I->getInitializer()); // Enumerate the aliasees. - for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); + for (Module::const_alias_iterator I = M.alias_begin(), E = M.alias_end(); I != E; ++I) EnumerateValue(I->getAliasee()); // Enumerate the prefix data constants. - for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) + for (Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I) if (I->hasPrefixData()) EnumerateValue(I->getPrefixData()); + // Enumerate the prologue data constants. + for (Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I) + if (I->hasPrologueData()) + EnumerateValue(I->getPrologueData()); + + // Enumerate the metadata type. + // + // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode + // only encodes the metadata type when it's used as a value. + EnumerateType(Type::getMetadataTy(M.getContext())); + // 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()); + EnumerateValueSymbolTable(M.getValueSymbolTable()); EnumerateNamedMetadata(M); - SmallVector, 8> MDs; + SmallVector, 8> MDs; // Enumerate types used by function bodies and argument lists. - for (const Function &F : *M) { + 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); + auto *MD = dyn_cast(&Op); + if (!MD) { + EnumerateOperandType(Op); + continue; + } + + // Local metadata is enumerated during function-incorporation. + if (isa(MD->getMetadata())) + continue; + + EnumerateMetadata(MD->getMetadata()); } EnumerateType(I.getType()); if (const CallInst *CI = dyn_cast(&I)) @@ -372,11 +403,8 @@ void ValueEnumerator::setInstructionID(const Instruction *I) { } unsigned ValueEnumerator::getValueID(const Value *V) const { - if (isa(V) || isa(V)) { - ValueMapType::const_iterator I = MDValueMap.find(V); - assert(I != MDValueMap.end() && "Value not in slotcalculator!"); - return I->second-1; - } + if (auto *MD = dyn_cast(V)) + return getMetadataID(MD->getMetadata()); ValueMapType::const_iterator I = ValueMap.find(V); assert(I != ValueMap.end() && "Value not in slotcalculator!"); @@ -419,6 +447,18 @@ void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map, } } +void ValueEnumerator::print(raw_ostream &OS, const MetadataMapType &Map, + const char *Name) const { + + OS << "Map Name: " << Name << "\n"; + OS << "Size: " << Map.size() << "\n"; + for (auto I = Map.begin(), E = Map.end(); I != E; ++I) { + const Metadata *MD = I->first; + OS << "Metadata: slot = " << I->second << "\n"; + MD->print(OS); + } +} + /// OptimizeConstants - Reorder constant pool for denser encoding. void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { if (CstStart == CstEnd || CstStart+1 == CstEnd) return; @@ -458,11 +498,12 @@ void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { EnumerateValue(VI->getValue()); } -/// 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) +/// 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); } @@ -475,84 +516,63 @@ void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) { /// 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())); + Metadata *MD = N->getOperand(i); + if (!MD) + continue; + assert(!isa(MD) && "MDNodes cannot be function-local"); + EnumerateMetadata(MD); } } -void ValueEnumerator::EnumerateMetadata(const Value *MD) { - assert((isa(MD) || isa(MD)) && "Invalid metadata kind"); - - // Enumerate the type of this value. - EnumerateType(MD->getType()); +void ValueEnumerator::EnumerateMetadata(const Metadata *MD) { + assert( + (isa(MD) || isa(MD) || isa(MD)) && + "Invalid metadata kind"); - const MDNode *N = dyn_cast(MD); + // Insert a dummy ID to block the co-recursive call to + // EnumerateMDNodeOperands() from re-visiting MD in a cyclic graph. + // + // Return early if there's already an ID. + if (!MDValueMap.insert(std::make_pair(MD, 0)).second) + return; - // In the module-level pass, skip function-local nodes themselves, but - // do walk their operands. - if (N && N->isFunctionLocal() && N->getFunction()) { + // Visit operands first to minimize RAUW. + if (auto *N = dyn_cast(MD)) EnumerateMDNodeOperands(N); - return; - } + else if (auto *C = dyn_cast(MD)) + EnumerateValue(C->getValue()); - // Check to see if it's already in! - unsigned &MDValueID = MDValueMap[MD]; - if (MDValueID) { - // Increment use count. - MDValues[MDValueID-1].second++; - return; - } - MDValues.push_back(std::make_pair(MD, 1U)); - MDValueID = MDValues.size(); + HasMDString |= isa(MD); + HasMDLocation |= isa(MD); + HasGenericDebugNode |= isa(MD); - // Enumerate all non-function-local operands. - if (N) - EnumerateMDNodeOperands(N); + // Replace the dummy ID inserted above with the correct one. MDValueMap may + // have changed by inserting operands, so we need a fresh lookup here. + MDs.push_back(MD); + MDValueMap[MD] = MDs.size(); } /// 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(N->getType()); - +/// information reachable from the metadata. +void ValueEnumerator::EnumerateFunctionLocalMetadata( + const LocalAsMetadata *Local) { // Check to see if it's already in! - unsigned &MDValueID = MDValueMap[N]; - if (MDValueID) { - // Increment use count. - MDValues[MDValueID-1].second++; + unsigned &MDValueID = MDValueMap[Local]; + if (MDValueID) return; - } - 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); - } - // Also, collect all function-local MDNodes for easy access. - FunctionLocalMDs.push_back(N); + MDs.push_back(Local); + MDValueID = MDs.size(); + + EnumerateValue(Local->getValue()); + + // Also, collect all function-local metadata for easy access. + FunctionLocalMDs.push_back(Local); } void ValueEnumerator::EnumerateValue(const Value *V) { assert(!V->getType()->isVoidTy() && "Can't insert void values!"); - assert(!isa(V) && !isa(V) && - "EnumerateValue doesn't handle Metadata!"); + assert(!isa(V) && "EnumerateValue doesn't handle Metadata!"); // Check to see if it's already in! unsigned &ValueID = ValueMap[V]; @@ -616,9 +636,8 @@ void ValueEnumerator::EnumerateType(Type *Ty) { // 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); + for (Type *SubTy : Ty->subtypes()) + EnumerateType(SubTy); // Refresh the TypeID pointer in case the table rehashed. TypeID = &TypeMap[Ty]; @@ -642,30 +661,35 @@ void ValueEnumerator::EnumerateType(Type *Ty) { 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. - if (ValueMap.count(V)) return; + if (auto *MD = dyn_cast(V)) { + assert(!isa(MD->getMetadata()) && + "Function-local metadata should be left for later"); - // This constant may have operands, make sure to enumerate the types in - // them. - for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { - const Value *Op = C->getOperand(i); + EnumerateMetadata(MD->getMetadata()); + return; + } - // Don't enumerate basic blocks here, this happens as operands to - // blockaddress. - if (isa(Op)) continue; + const Constant *C = dyn_cast(V); + if (!C) + return; - EnumerateOperandType(Op); - } + // If this constant is already enumerated, ignore it, we know its type must + // be enumerated. + if (ValueMap.count(C)) + return; - if (const MDNode *N = dyn_cast(V)) { - for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) - if (Value *Elem = N->getOperand(i)) - EnumerateOperandType(Elem); - } - } else if (isa(V) || isa(V)) - EnumerateMetadata(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 Value *Op = C->getOperand(i); + + // Don't enumerate basic blocks here, this happens as operands to + // blockaddress. + if (isa(Op)) + continue; + + EnumerateOperandType(Op); + } } void ValueEnumerator::EnumerateAttributes(AttributeSet PAL) { @@ -693,7 +717,7 @@ void ValueEnumerator::EnumerateAttributes(AttributeSet PAL) { void ValueEnumerator::incorporateFunction(const Function &F) { InstructionCount = 0; NumModuleValues = Values.size(); - NumModuleMDValues = MDValues.size(); + NumModuleMDs = MDs.size(); // Adding function arguments to the value table. for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); @@ -724,24 +748,16 @@ void ValueEnumerator::incorporateFunction(const Function &F) { FirstInstID = Values.size(); - SmallVector FnLocalMDVector; + 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) { 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()) + if (auto *MD = dyn_cast(&*OI)) + if (auto *Local = dyn_cast(MD->getMetadata())) // 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); + FnLocalMDVector.push_back(Local); } if (!I->getType()->isVoidTy()) @@ -758,13 +774,13 @@ 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 = NumModuleMDs, e = MDs.size(); i != e; ++i) + MDValueMap.erase(MDs[i]); for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) ValueMap.erase(BasicBlocks[i]); Values.resize(NumModuleValues); - MDValues.resize(NumModuleMDValues); + MDs.resize(NumModuleMDs); BasicBlocks.clear(); FunctionLocalMDs.clear(); } @@ -787,4 +803,3 @@ unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const { IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs); return getGlobalBasicBlockID(BB); } -