X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FBitcode%2FWriter%2FValueEnumerator.cpp;h=c14591acc8adc3c03bd670a1569bef2e0a36e412;hp=0421332e5305b68ef8b45b18a9f608d4a46785aa;hb=cb3866e72e98ce77080deffd008b1d8e9b7d5301;hpb=bd24fe8c7e8038fe53accad67c480875f87df2a8 diff --git a/lib/Bitcode/Writer/ValueEnumerator.cpp b/lib/Bitcode/Writer/ValueEnumerator.cpp index 0421332e530..c14591acc8a 100644 --- a/lib/Bitcode/Writer/ValueEnumerator.cpp +++ b/lib/Bitcode/Writer/ValueEnumerator.cpp @@ -26,7 +26,31 @@ using namespace llvm; namespace { -typedef DenseMap> OrderMap; +struct OrderMap { + DenseMap> IDs; + unsigned LastGlobalConstantID; + unsigned LastGlobalValueID; + + OrderMap() : LastGlobalConstantID(0), LastGlobalValueID(0) {} + + bool isGlobalConstant(unsigned ID) const { + return ID <= LastGlobalConstantID; + } + bool isGlobalValue(unsigned ID) const { + return ID <= LastGlobalValueID && !isGlobalConstant(ID); + } + + unsigned size() const { return IDs.size(); } + std::pair &operator[](const Value *V) { return IDs[V]; } + 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; + } +}; } static void orderValue(const Value *V, OrderMap &OM) { @@ -36,12 +60,12 @@ static void orderValue(const Value *V, OrderMap &OM) { if (const Constant *C = dyn_cast(V)) if (C->getNumOperands() && !isa(C)) for (const Value *Op : C->operands()) - if (!isa(Op)) + if (!isa(Op) && !isa(Op)) 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) { @@ -49,20 +73,39 @@ static OrderMap orderModule(const Module *M) { // and ValueEnumerator::incorporateFunction(). OrderMap OM; + // In the reader, initializers of GlobalValues are set *after* all the + // globals have been read. Rather than awkwardly modeling this behaviour + // directly in predictValueUseListOrderImpl(), just assign IDs to + // initializers of GlobalValues before GlobalValues themselves to model this + // implicitly. for (const GlobalVariable &G : M->globals()) - orderValue(&G, OM); + if (G.hasInitializer()) + 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()) + if (!isa(F.getPrefixData())) + orderValue(F.getPrefixData(), OM); + OM.LastGlobalConstantID = OM.size(); + + // Initializers of GlobalValues are processed in + // BitcodeReader::ResolveGlobalAndAliasInits(). Match the order there rather + // than ValueEnumerator, and match the code in predictValueUseListOrderImpl() + // by giving IDs in reverse order. + // + // 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) orderValue(&F, OM); for (const GlobalAlias &A : M->aliases()) orderValue(&A, OM); 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 (F.hasPrefixData()) - orderValue(F.getPrefixData(), OM); + orderValue(&G, OM); + OM.LastGlobalValueID = OM.size(); for (const Function &F : *M) { if (F.isDeclaration()) @@ -102,28 +145,45 @@ static void predictValueUseListOrderImpl(const Value *V, const Function *F, // We may have lost some users. return; - std::sort(List.begin(), List.end(), - [&OM, ID](const Entry &L, const Entry &R) { + bool IsGlobalValue = OM.isGlobalValue(ID); + std::sort(List.begin(), List.end(), [&](const Entry &L, const Entry &R) { const Use *LU = L.first; const Use *RU = R.first; + if (LU == RU) + return false; + auto LID = OM.lookup(LU->getUser()).first; auto RID = OM.lookup(RU->getUser()).first; + + // Global values are processed in reverse order. + // + // Moreover, initializers of GlobalValues are set *after* all the globals + // have been read (despite having earlier IDs). Rather than awkwardly + // modeling this behaviour here, orderModule() has assigned IDs to + // initializers of GlobalValues before GlobalValues themselves. + if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID)) + return LID < RID; + // If ID is 4, then expect: 7 6 5 1 2 3. if (LID < RID) { - if (RID < ID) - return true; + if (RID <= ID) + if (!IsGlobalValue) // GlobalValue uses don't get reversed. + return true; return false; } if (RID < LID) { - if (LID < ID) - return false; + if (LID <= ID) + if (!IsGlobalValue) // GlobalValue uses don't get reversed. + return false; return true; } + // LID and RID are equal, so we have different operands of the same user. // Assume operands are added in order for all instructions. - if (LU->getOperandNo() < RU->getOperandNo()) - return LID < ID; - return ID < LID; + if (LID <= ID) + if (!IsGlobalValue) // GlobalValue uses don't get reversed. + return LU->getOperandNo() < RU->getOperandNo(); + return LU->getOperandNo() > RU->getOperandNo(); }); if (std::is_sorted( @@ -133,12 +193,10 @@ static void predictValueUseListOrderImpl(const Value *V, const Function *F, return; // Store the shuffle. - UseListOrder O; - O.V = V; - O.F = F; - for (auto &I : List) - O.Shuffle.push_back(I.second); - Stack.push_back(O); + Stack.emplace_back(V, F, List.size()); + assert(List.size() == Stack.back().Shuffle.size() && "Wrong size"); + for (size_t I = 0, E = List.size(); I != E; ++I) + Stack.back().Shuffle[I] = List[I].second; } static void predictValueUseListOrder(const Value *V, const Function *F, @@ -156,9 +214,9 @@ 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); } @@ -186,8 +244,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) @@ -438,31 +495,31 @@ void ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) { void ValueEnumerator::EnumerateMetadata(const Value *MD) { assert((isa(MD) || isa(MD)) && "Invalid metadata kind"); - // Enumerate the type of this value. - EnumerateType(MD->getType()); - + // Skip function-local nodes themselves, but walk their operands. 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) { - // Increment use count. - MDValues[MDValueID-1].second++; + // 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; - } - MDValues.push_back(std::make_pair(MD, 1U)); - MDValueID = MDValues.size(); - // Enumerate all non-function-local operands. + // Enumerate the type of this value. + EnumerateType(MD->getType()); + + // Visit operands first to minimize RAUW. 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. + MDValues.push_back(MD); + MDValueMap[MD] = MDValues.size(); } /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata @@ -476,12 +533,10 @@ void ValueEnumerator::EnumerateFunctionLocalMetadata(const MDNode *N) { // Check to see if it's already in! unsigned &MDValueID = MDValueMap[N]; - if (MDValueID) { - // Increment use count. - MDValues[MDValueID-1].second++; + if (MDValueID) return; - } - MDValues.push_back(std::make_pair(N, 1U)); + + MDValues.push_back(N); MDValueID = MDValues.size(); // To incoroporate function-local information visit all function-local @@ -709,7 +764,7 @@ void ValueEnumerator::purgeFunction() { 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); + MDValueMap.erase(MDValues[i]); for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) ValueMap.erase(BasicBlocks[i]);