Index: include/llvm/LTO/LTO.h =================================================================== --- include/llvm/LTO/LTO.h +++ include/llvm/LTO/LTO.h @@ -369,6 +369,12 @@ ModuleSummaryIndex CombinedIndex; MapVector ModuleMap; DenseMap PrevailingModuleForGUID; + /// Performs a stable topological sort of the ModuleMap that ensures + /// modules with prevailing weak symbols are ordered before any modules + /// containing non-prevailing weak defs of those symbols. + void sortModuleMap( + function_ref + isPrevailing); } ThinLTO; // The global resolution for a particular (mangled) symbol name. This is in Index: lib/LTO/LTO.cpp =================================================================== --- lib/LTO/LTO.cpp +++ lib/LTO/LTO.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "llvm/LTO/LTO.h" +#include "llvm/ADT/PriorityQueue.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Bitcode/BitcodeReader.h" @@ -832,6 +833,135 @@ }; } +// Sort the ModuleMap before launching the backends. This is necessary +// to ensure that the linker is provided the resulting object files in +// an order where objects containing prevailing copies of weak symbols are +// before any that contain non-prevailing copies of those weak symbols. +// This ensures that the final native link selects the same copy as +// prevailing. This issue occurs when the weak definitions are in static +// libraries, where the linker may select an object listed later in the +// archive (and therefore its weak symbols as the prevailing copies) and +// later select an object listed earlier in the archive (whose copies of +// the same weak symbols would then be non-prevailing). Because the linker +// (e.g. gold) does not provide this ordering to the plugin (the plugin +// only has the original ordering of the objects in the library which is +// the order the plugin originally saw them), we need to correct the +// ModuleMap ordering. +// +// We can compute a partial ordering by consulting the combined index +// to find weak symbols that have multiple copies, and recording that +// the prevailing copy's module must be before all other non-prevailing copies' +// modules. Because this is only a partial ordering, we need to do a +// topological sort. Here we do a stable topological sort, to ensure the +// rest of the modules stay in their original order. +void LTO::ThinLTOState::sortModuleMap( + function_ref + isPrevailing) { + // First collect maps of modules with prevailing symbols to any modules + // containing non-prevailing copies of those symbols, and vice versa. + std::map> PrevailingToNonPrevailingMods; + std::map> NonPrevailingToPrevailingMods; + for (auto &I : CombinedIndex) { + // Only need to look at weak symbols with more than one copy. + if (I.second.size() == 1) + continue; + // Local symbols can have multiple copies in certain circumstances + // (same named local in same named source files each compiled in + // their own directory without the relative path). However, the + // index is formed by prepending the source file name and therefore + // the list will only contain local symbols, so we can skip it. + if (GlobalValue::isLocalLinkage(I.second[0]->linkage())) + continue; + assert(GlobalValue::isWeakForLinker(I.second[0]->linkage()) && + "Index contains multiple copies of non-weak symbols"); + + // Find the module with the prevailing copy + StringRef PrevailingMod; + for (auto &S : I.second) { + if (!isPrevailing(I.first, S.get())) + continue; + PrevailingMod = S->modulePath(); + } + // None of the copies in the ThinLTO objects are prevailing, no need + // to reorder them. + if (PrevailingMod.empty()) + continue; + + // Now add to the map entries for the prevailing and non-prevailing + // modules to identify the relative ordering. + std::set &NonPrevailingMods = PrevailingToNonPrevailingMods[PrevailingMod]; + for (auto &S : I.second) { + if (isPrevailing(I.first, S.get())) + continue; + assert(!PrevailingToNonPrevailingMods[S->modulePath()].count(PrevailingMod) && "Unexpected circular dependence of modules with prevailing copies"); + NonPrevailingMods.insert(S->modulePath()); + NonPrevailingToPrevailingMods[S->modulePath()].insert(PrevailingMod); + } + } + +#if 0 + errs() << "Before sort\n"; + for (auto &ModPair : ModuleMap) + errs() << ModPair.first << "\n"; +#endif + + // Next construct a priority queue where the priority is the inverse of + // the original ordering in the ModuleMap (this is to ensure the ordering + // is stable). A Module is entered in the queue when all modules containing + // prevailing copies of its weak symbols have been sorted. + struct CompareOrigPosition { + bool operator()(const std::pair &A, + const std::pair &B) const { + return A.second > B.second; + } + }; + PriorityQueue, std::vector>, CompareOrigPosition> Ready; + + unsigned Pos = 0; + DenseMap OrigPositionMap; + + // Initialize the priority queue with modules that don't have any + // non-prevailing weak symbols. + for (auto &ModPair : ModuleMap) { + if (!NonPrevailingToPrevailingMods.count(ModPair.first)) + Ready.push(std::make_pair(ModPair.first, ++Pos)); + else + // FIXME: Could avoid this if we add an operator< to MapVector + OrigPositionMap[ModPair.first] = ++Pos; + } + + // Now process the queue, adding any ready modules in their original + // ordering to the new ModuleMap. + MapVector NewModuleMap; + //errs() << "After sort\n"; + while (!Ready.empty()) { + StringRef ModPath; + std::tie(ModPath, std::ignore) = Ready.top(); + Ready.pop(); + //errs() << ModPath << "\n"; + auto MMI = ModuleMap.find(ModPath); + assert(MMI != ModuleMap.end() && "Module missing from ModuleMap"); + NewModuleMap.insert({ModPath, MMI->second}); + + // Now remove this module from the dependent sets for non-prevailing + // modules. If any of those ends up with an empty dependent set (all + // prevailing modules for its weak symbols are empty), then add them + // to the ready queue. + auto NonPrevailingMods = PrevailingToNonPrevailingMods.find(ModPath); + if (NonPrevailingMods == PrevailingToNonPrevailingMods.end()) + continue; + for (auto &NonPrevailingMod : NonPrevailingMods->second) { + auto &PrevailingMods = NonPrevailingToPrevailingMods[NonPrevailingMod]; + assert(PrevailingMods.count(ModPath) && "Expected to find prevailing module in set for non-prevailing modules"); + PrevailingMods.erase(ModPath); + if (!PrevailingMods.size()) + Ready.push(std::make_pair(NonPrevailingMod, OrigPositionMap[NonPrevailingMod])); + } + } + + ModuleMap.swap(NewModuleMap); +} + Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache, bool HasRegularLTO) { if (ThinLTO.ModuleMap.empty()) @@ -876,6 +1006,11 @@ ThinLTO.ModuleMap.size()); StringMap> ResolvedODR; + auto isPrevailing = [&](GlobalValue::GUID GUID, + const GlobalValueSummary *S) { + return ThinLTO.PrevailingModuleForGUID[GUID] == S->modulePath(); + }; + if (Conf.OptLevel > 0) { ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries, ImportLists, ExportLists, &DeadSymbols); @@ -896,10 +1031,6 @@ ExportedGUIDs.insert(GlobalValue::getGUID(Res.second.IRName)); } - auto isPrevailing = [&](GlobalValue::GUID GUID, - const GlobalValueSummary *S) { - return ThinLTO.PrevailingModuleForGUID[GUID] == S->modulePath(); - }; auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) { const auto &ExportList = ExportLists.find(ModuleIdentifier); return (ExportList != ExportLists.end() && @@ -918,6 +1049,8 @@ recordNewLinkage); } + ThinLTO.sortModuleMap(isPrevailing); + std::unique_ptr BackendProc = ThinLTO.Backend(Conf, ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries, AddStream, Cache); Index: test/tools/gold/X86/Inputs/thinlto_weak_library1.ll =================================================================== --- /dev/null +++ test/tools/gold/X86/Inputs/thinlto_weak_library1.ll @@ -0,0 +1,16 @@ +; ModuleID = 'thinlto_weak_library1.c' +source_filename = "thinlto_weak_library1.c" +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: nounwind uwtable +define weak i32 @f() local_unnamed_addr { +entry: + ret i32 1 +} + +; Function Attrs: norecurse nounwind readnone uwtable +define void @test1() local_unnamed_addr { +entry: + ret void +} Index: test/tools/gold/X86/Inputs/thinlto_weak_library2.ll =================================================================== --- /dev/null +++ test/tools/gold/X86/Inputs/thinlto_weak_library2.ll @@ -0,0 +1,20 @@ +; ModuleID = 'thinlto_weak_library2.c' +source_filename = "thinlto_weak_library2.c" +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: nounwind uwtable +define weak i32 @f() local_unnamed_addr { +entry: + ret i32 2 +} + +; Function Attrs: nounwind uwtable +define void @test2() local_unnamed_addr { +entry: + tail call void (...) @test1() + tail call i32 @f() + ret void +} + +declare void @test1(...) local_unnamed_addr Index: test/tools/gold/X86/thinlto_weak_library.ll =================================================================== --- /dev/null +++ test/tools/gold/X86/thinlto_weak_library.ll @@ -0,0 +1,54 @@ +; Test to ensure that ThinLTO sorts the modules before passing to the +; final native link based on the linker's determination of which +; object within a static library contains the prevailing def of a symbol. + +; First generate bitcode with a module summary index for each file +; RUN: opt -module-summary %s -o %t.o +; RUN: opt -module-summary %p/Inputs/thinlto_weak_library1.ll -o %t2.o +; RUN: opt -module-summary %p/Inputs/thinlto_weak_library2.ll -o %t3.o + +; Although the objects are ordered "%t2.o %t3.o" in the library, the +; linker selects %t3.o first since it satisfies a strong reference from +; %t.o. It later selects %t2.o based on the strong ref from %t3.o. +; Therefore, %t3.o's copy of @f is prevailing, and we need to link +; %t3.o before %t2.o in the final native link. +; RUN: %gold -plugin %llvmshlibdir/LLVMgold.so \ +; RUN: --plugin-opt=thinlto \ +; RUN: -m elf_x86_64 \ +; RUN: -o %t4 \ +; RUN: %t.o \ +; RUN: --start-lib %t2.o %t3.o --end-lib + +; Make sure linker selected the copy from thinlto_weak_library2.ll (%t3.o) +; RUN: llvm-objdump -d %t4 | FileCheck %s +; CHECK: f: +; CHECK-NEXT: $2, + +; Now check the distributed case, where the objects should be emitted +; into %t5 in the correct order. +; RUN: %gold -plugin %llvmshlibdir/LLVMgold.so \ +; RUN: --plugin-opt=thinlto \ +; RUN: --plugin-opt=thinlto-index-only=%t5 \ +; RUN: -m elf_x86_64 \ +; RUN: -o %t4 \ +; RUN: %t.o \ +; RUN: --start-lib %t2.o %t3.o --end-lib + +; RUN: cat %t5 | FileCheck %s --check-prefix=OBJECTLIST +; OBJECTLIST: thinlto_weak_library.ll.tmp.o +; OBJECTLIST-NEXT: thinlto_weak_library.ll.tmp3.o +; OBJECTLIST-NEXT: thinlto_weak_library.ll.tmp2.o + +; ModuleID = 'thinlto_weak_library.c' +source_filename = "thinlto_weak_library.c" +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: nounwind uwtable +define i32 @main() local_unnamed_addr { +entry: + tail call void (...) @test2() + ret i32 0 +} + +declare void @test2(...) local_unnamed_addr