From 1d501e8f46ccea5efa8bdb2833f6b4fc2f48f047 Mon Sep 17 00:00:00 2001 From: "Duncan P. N. Exon Smith" Date: Tue, 29 Jul 2014 23:06:14 +0000 Subject: [PATCH] UseListOrder: Order GlobalValue uses after initializers To avoid unnecessary forward references, the reader doesn't process initializers of `GlobalValue`s until after the constant pool has been processed, and then in reverse order. Model this when predicting use-list order. This gets two more Bitcode tests passing with `llvm-uselistorder`. Part of PR5680. llvm-svn: 214242 --- llvm/lib/Bitcode/Writer/ValueEnumerator.cpp | 69 +++++++++++++++++----- .../local-linkage-default-visibility.3.4.ll | 1 + llvm/test/Bitcode/old-aliases.ll | 1 + 3 files changed, 57 insertions(+), 14 deletions(-) diff --git a/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp b/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp index 5624e02..09b6c47 100644 --- a/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp +++ b/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp @@ -28,6 +28,17 @@ using namespace llvm; namespace { 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]; } @@ -44,7 +55,7 @@ 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 @@ -57,12 +68,11 @@ static OrderMap orderModule(const Module *M) { // and ValueEnumerator::incorporateFunction(). OrderMap OM; - for (const GlobalVariable &G : M->globals()) - orderValue(&G, OM); - for (const Function &F : *M) - orderValue(&F, OM); - for (const GlobalAlias &A : M->aliases()) - orderValue(&A, 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()) if (G.hasInitializer()) orderValue(G.getInitializer(), OM); @@ -71,6 +81,23 @@ static OrderMap orderModule(const Module *M) { for (const Function &F : *M) if (F.hasPrefixData()) 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()) + orderValue(&G, OM); + OM.LastGlobalValueID = OM.size(); for (const Function &F : *M) { if (F.isDeclaration()) @@ -110,8 +137,8 @@ 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) @@ -119,22 +146,36 @@ static void predictValueUseListOrderImpl(const Value *V, const Function *F, 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 (!IsGlobalValue) // GlobalValue uses don't get reversed. + return true; return false; } if (RID < LID) { if (LID < ID) - return false; + 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( diff --git a/llvm/test/Bitcode/local-linkage-default-visibility.3.4.ll b/llvm/test/Bitcode/local-linkage-default-visibility.3.4.ll index 45a7b12..c1a9fbe 100644 --- a/llvm/test/Bitcode/local-linkage-default-visibility.3.4.ll +++ b/llvm/test/Bitcode/local-linkage-default-visibility.3.4.ll @@ -1,4 +1,5 @@ ; RUN: llvm-dis < %s.bc | FileCheck %s +; RUN: llvm-uselistorder < %s.bc -preserve-bc-use-list-order -num-shuffles=5 ; local-linkage-default-visibility.3.4.ll.bc was generated by passing this file ; to llvm-as-3.4. The test checks that LLVM upgrades visibility of symbols diff --git a/llvm/test/Bitcode/old-aliases.ll b/llvm/test/Bitcode/old-aliases.ll index 7a0eea2..13b6d3e 100644 --- a/llvm/test/Bitcode/old-aliases.ll +++ b/llvm/test/Bitcode/old-aliases.ll @@ -1,4 +1,5 @@ ; RUN: llvm-dis < %s.bc | FileCheck %s +; RUN: llvm-uselistorder < %s.bc -preserve-bc-use-list-order -num-shuffles=5 ; old-aliases.bc consist of this file assembled with an old llvm-as (3.5 trunk) ; from when aliases contained a ConstantExpr. -- 2.7.4