Index: llvm/include/llvm/ADT/ilist.h =================================================================== --- llvm/include/llvm/ADT/ilist.h +++ llvm/include/llvm/ADT/ilist.h @@ -163,7 +163,7 @@ /// ilist_sentinel, which holds pointers to the first and last nodes in the /// list. template -class iplist_impl : public TraitsT, IntrusiveListT { +class iplist_impl : public TraitsT, public IntrusiveListT { typedef IntrusiveListT base_list_type; public: Index: llvm/include/llvm/ADT/simple_ilist.h =================================================================== --- llvm/include/llvm/ADT/simple_ilist.h +++ llvm/include/llvm/ADT/simple_ilist.h @@ -9,6 +9,7 @@ #ifndef LLVM_ADT_SIMPLE_ILIST_H #define LLVM_ADT_SIMPLE_ILIST_H +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/ilist_base.h" #include "llvm/ADT/ilist_iterator.h" #include "llvm/ADT/ilist_node.h" @@ -262,6 +263,11 @@ ///@{ void sort() { sort(std::less()); } template void sort(Compare comp); + + /// Reorder the items in the list based on the input map table. + template + void sort(simple_ilist &RHS, DenseMap &DM, iterator First, + iterator Last, Compare comp); ///@} }; @@ -309,6 +315,41 @@ merge(RHS, comp); } +// Reorder the items in the list based on the input map table. +template +template +void simple_ilist::sort(simple_ilist &SourceList, + DenseMap &DM, + iterator First, iterator Last, + Compare comp) { + // Vacuously sorted. + if (empty() || std::next(begin()) == end()) + return; + + DenseMap PointerMap; + iterator Begin = First; + while (Begin != Last) { + PointerMap[&*Begin] = Begin; + ++Begin; + } + + simple_ilist ShuffleList; + for (auto &G : SourceList) { + if (DM.count(&G)) { + auto Dest = DM[&G]; + if (PointerMap.count(Dest)) { + auto It = PointerMap[Dest]; + It++; + ShuffleList.splice(ShuffleList.end(), *this, PointerMap[Dest], It); + } + } + } + + iterator LE = end(); + iterator RI = ShuffleList.begin(), RE = ShuffleList.end(); + splice(LE, ShuffleList, RI, RE); +} + } // end namespace llvm #endif // LLVM_ADT_SIMPLE_ILIST_H Index: llvm/lib/Linker/IRMover.cpp =================================================================== --- llvm/lib/Linker/IRMover.cpp +++ llvm/lib/Linker/IRMover.cpp @@ -435,6 +435,10 @@ ValueMapper Mapper; unsigned IndirectSymbolMCID; + /// The map table which maps the old global in the SrcM to the new global + /// in the DstM. + DenseMap OldToNewSymbolTable; + /// Handles cloning of a global values from the source module into /// the destination module, including setting the attributes and visibility. GlobalValue *copyGlobalValueProto(const GlobalValue *SGV, bool ForDefinition); @@ -1423,6 +1427,8 @@ DstM.getDataLayoutStr() + "'\n"); } + OldToNewSymbolTable.clear(); + // Copy the target triple from the source to dest if the dest's is empty. if (DstM.getTargetTriple().empty() && !SrcM->getTargetTriple().empty()) DstM.setTargetTriple(SrcM->getTargetTriple()); @@ -1442,6 +1448,9 @@ // Loop over all of the linked values to compute type mappings. computeTypeMapping(); + Module::GlobalListType &Globals = DstM.getGlobalList(); + unsigned OldSize = Globals.size(); + std::reverse(Worklist.begin(), Worklist.end()); while (!Worklist.empty()) { GlobalValue *GV = Worklist.back(); @@ -1487,6 +1496,28 @@ }); } + // Build the map table to store the mapping between the old globals in + // the source module to the new globals in the destination module. + for (GlobalVariable &GV : SrcM->globals()) { + if (GV.hasAppendingLinkage()) + continue; + auto NewGV = Mapper.mapValue(GV); + if (NewGV) { + NewGV = NewGV->stripPointerCasts(); + if (isa(NewGV)) + OldToNewSymbolTable[&GV] = cast(NewGV); + } + } + + // Advance the pointer to the first newly added element. + auto Begin = Globals.begin(); + std::advance(Begin, OldSize); + + // Reorder the newly added globals based on the map table. + Globals.sort(SrcM->getGlobalList(), OldToNewSymbolTable, Begin, Globals.end(), + nullptr); + + // Merge the module flags into the DstM module. return linkModuleFlagsMetadata(); } Index: llvm/test/Linker/Inputs/globalorder-2.ll =================================================================== --- /dev/null +++ llvm/test/Linker/Inputs/globalorder-2.ll @@ -0,0 +1,14 @@ +@var5 = internal global i32 0, align 4 +@var6 = internal global i32 0, align 4 +@var7 = global i32* @var5, align 4 +@var8 = global i32* @var6, align 4 + +define i32 @foo2() { +entry: + %0 = load i32*, i32** @var7, align 4 + %1 = load i32, i32* %0, align 4 + %2 = load i32*, i32** @var8, align 4 + %3 = load i32, i32* %2, align 4 + %add = add nsw i32 %3, %1 + ret i32 %add +} Index: llvm/test/Linker/comdat14.ll =================================================================== --- llvm/test/Linker/comdat14.ll +++ llvm/test/Linker/comdat14.ll @@ -5,5 +5,5 @@ @v = global i32 0, comdat ($c) ; CHECK: @v = global i32 0, comdat($c) -; CHECK: @v2 = external dllexport global i32 ; CHECK: @v3 = external global i32 +; CHECK: @v2 = external dllexport global i32 Index: llvm/test/Linker/ctors.ll =================================================================== --- llvm/test/Linker/ctors.ll +++ llvm/test/Linker/ctors.ll @@ -6,12 +6,12 @@ ; Test the bitcode writer too. It used to crash. ; RUN: llvm-link %s %p/Inputs/ctors.ll -o %t.bc +; ALL: @llvm.global_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @f, i8* @v }] @v = weak global i8 0 ; CHECK1: @v = weak global i8 0 ; CHECK2: @v = weak global i8 1 @llvm.global_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @f, i8* @v }] -; ALL: @llvm.global_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @f, i8* @v }] define weak void @f() { ret void Index: llvm/test/Linker/globalorder.ll =================================================================== --- /dev/null +++ llvm/test/Linker/globalorder.ll @@ -0,0 +1,27 @@ +; Test the order of global variables during llvm-link + +; RUN: llvm-link %s %S/Inputs/globalorder-2.ll -o %t.bc +; RUN: llvm-dis -o - %t.bc | FileCheck %s + +@var1 = internal global i32 0, align 4 +@var2 = internal global i32 0, align 4 +@var3 = global i32* @var1, align 4 +@var4 = global i32* @var2, align 4 + +define i32 @foo() { +entry: + %0 = load i32*, i32** @var3, align 4 + %1 = load i32, i32* %0, align 4 + %2 = load i32*, i32** @var4, align 4 + %3 = load i32, i32* %2, align 4 + %add = add nsw i32 %3, %1 + ret i32 %add +} +; CHECK: @var1 = +; CHECK-NEXT: @var2 = +; CHECK-NEXT: @var3 = +; CHECK-NEXT: @var4 = +; CHECK-NEXT: @var5 = +; CHECK-NEXT: @var6 = +; CHECK-NEXT: @var7 = +; CHECK-NEXT: @var8 = Index: llvm/test/Linker/link-flags.ll =================================================================== --- llvm/test/Linker/link-flags.ll +++ llvm/test/Linker/link-flags.ll @@ -9,8 +9,8 @@ CU-LABEL:@U = global i32 6 CI-LABEL:@U = internal global i32 6 CN-NOT:@U -DI-LABEL: @Y = global i8 42 DI-LABEL: @llvm.used = appending global [2 x i8*] [i8* @Y, i8* bitcast (i64 ()* @foo to i8*)], section "llvm.metadata" +DI-LABEL: @Y = global i8 42 B-LABEL: define void @bar() { Index: llvm/test/Linker/metadata-attach.ll =================================================================== --- llvm/test/Linker/metadata-attach.ll +++ llvm/test/Linker/metadata-attach.ll @@ -6,8 +6,8 @@ ; CHECK-LINKED1: @g1 = global i32 0, !attach !0{{$}} @g1 = global i32 0, !attach !0 -; CHECK: @g3 = weak global i32 1, !attach !0{{$}} ; CHECK: @g2 = external global i32, !attach !0{{$}} +; CHECK: @g3 = weak global i32 1, !attach !0{{$}} ; CHECK-LINKED1: @g2 = global i32 1, !attach !1{{$}} @g2 = external global i32, !attach !0 Index: llvm/test/ThinLTO/X86/import-constant.ll =================================================================== --- llvm/test/ThinLTO/X86/import-constant.ll +++ llvm/test/ThinLTO/X86/import-constant.ll @@ -28,9 +28,9 @@ ; PROMOTE: @_ZL3Obj.llvm.{{.*}} = hidden constant %struct.S { i32 4, i32 8, i32* @val } ; @outer is a write-only variable, so it's been converted to zeroinitializer. -; IMPORT: @outer = internal local_unnamed_addr global %struct.Q zeroinitializer +; IMPORT: @val = available_externally global i32 42 ; IMPORT-NEXT: @_ZL3Obj.llvm.{{.*}} = available_externally hidden constant %struct.S { i32 4, i32 8, i32* @val } -; IMPORT-NEXT: @val = available_externally global i32 42 +; IMPORT-NEXT: @outer = internal local_unnamed_addr global %struct.Q zeroinitializer ; OPT: @outer = internal unnamed_addr global %struct.Q zeroinitializer @@ -39,8 +39,8 @@ ; OPT-NEXT: store %struct.S* null, %struct.S** getelementptr inbounds (%struct.Q, %struct.Q* @outer, i64 0, i32 0) ; OPT-NEXT: ret i32 12 -; NOREFS: @outer = internal local_unnamed_addr global %struct.Q zeroinitializer -; NOREFS-NEXT: @_ZL3Obj.llvm.{{.*}} = external hidden constant %struct.S +; NOREFS: @_ZL3Obj.llvm.{{.*}} = external hidden constant %struct.S +; NOREFS-NEXT: @outer = internal local_unnamed_addr global %struct.Q zeroinitializer target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"