From 3cbca2055adb7f0ccedac3a01c5ca799c635a2bf Mon Sep 17 00:00:00 2001 From: "Duncan P. N. Exon Smith" Date: Wed, 30 Jul 2014 01:22:16 +0000 Subject: [PATCH] Reapply "UseListOrder: Order GlobalValue uses after initializers" This reverts commit r214249, reapplying r214242 and r214243, now that r214270 has fixed the UB. llvm-svn: 214271 --- llvm/lib/Bitcode/Writer/ValueEnumerator.cpp | 69 +++++++++++++++++----- .../local-linkage-default-visibility.3.4.ll | 1 + llvm/test/Bitcode/old-aliases.ll | 1 + llvm/test/Bitcode/use-list-order.ll | 14 +++++ 4 files changed, 71 insertions(+), 14 deletions(-) diff --git a/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp b/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp index 144e8fb..c05d6ae 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]; } @@ -49,7 +60,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 @@ -62,12 +73,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); @@ -76,6 +86,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()) @@ -115,8 +142,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) @@ -124,22 +151,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. diff --git a/llvm/test/Bitcode/use-list-order.ll b/llvm/test/Bitcode/use-list-order.ll index ac7307b..33cc13e 100644 --- a/llvm/test/Bitcode/use-list-order.ll +++ b/llvm/test/Bitcode/use-list-order.ll @@ -3,6 +3,20 @@ @a = global [4 x i1] [i1 0, i1 1, i1 0, i1 1] @b = alias i1* getelementptr ([4 x i1]* @a, i64 0, i64 2) +; Check use-list order of constants used by globals. +@glob1 = global i5 7 +@glob2 = global i5 7 +@glob3 = global i5 7 + +; Check use-list order between variables and aliases. +@target = global i3 zeroinitializer +@alias1 = alias i3* @target +@alias2 = alias i3* @target +@alias3 = alias i3* @target +@var1 = global i3* @target +@var2 = global i3* @target +@var3 = global i3* @target + define i64 @f(i64 %f) { entry: %sum = add i64 %f, 0 -- 2.7.4