Index: include/llvm/Transforms/IPO/FunctionImport.h =================================================================== --- include/llvm/Transforms/IPO/FunctionImport.h +++ include/llvm/Transforms/IPO/FunctionImport.h @@ -75,11 +75,20 @@ /// \p ExportLists contains for each Module the set of globals (GUID) that will /// be imported by another module, or referenced by such a function. I.e. this /// is the set of globals that need to be promoted/renamed appropriately. +/// +/// \p PreventBackwardsModuleRefs should be set to true if we need to +/// conservatively prevent creating a reference to a promoted/renamed local +/// in a module earlier on the link line (by preventing import of any +/// multiply defined weak linkage function that references such a local). +/// It is used in the case when the ThinLTO backends will be a separate process, +/// and the subsequent final native object link might select a different copy as +/// prevailing. void ComputeCrossModuleImport( const ModuleSummaryIndex &Index, const StringMap &ModuleToDefinedGVSummaries, StringMap &ImportLists, - StringMap &ExportLists); + StringMap &ExportLists, + bool PreventBackwardsModuleRefs = false); /// Compute all the imports for the given module using the Index. /// Index: lib/Transforms/IPO/FunctionImport.cpp =================================================================== --- lib/Transforms/IPO/FunctionImport.cpp +++ lib/Transforms/IPO/FunctionImport.cpp @@ -151,6 +151,44 @@ return true; } +// Return true if there are multiple copies of the candidate callee, +// and it references a local value needing renaming. This is used +// when we need to conservatively prevent any backwards references, since +// we don't know which copies of the multiply defined callee are after +// the importing function, and promoted locals are renamed based on the +// module hash of the selected copy. (Note we can't simply selecte the +// last copy which might result in different behavior in the non-odr case.) +static bool mightIntroduceBackwardsModuleRef( + const ModuleSummaryIndex &Index, + const GlobalValueSummaryList &CalleeSummaryList, + const GlobalValueSummary *S) { + auto needsRenaming = [&](GlobalValue::GUID GUID) { + auto Summaries = Index.findGlobalValueSummaryList(GUID); + if (Summaries == Index.end()) + return false; + if (Summaries->second.size() != 1) + // If there are multiple globals with this GUID, then we know it is + // not a local symbol, and will not need renaming. + return false; + return Summaries->second.begin()->get()->needsRenaming(); + }; + + if (CalleeSummaryList.size() > 1) { + if (llvm::any_of(S->refs(), [&](const ValueInfo &VI) { + return needsRenaming(VI.getGUID()); + })) + return true; + if (auto *FuncSummary = dyn_cast(S)) { + if (llvm::any_of(FuncSummary->calls(), + [&](const FunctionSummary::EdgeTy &Edge) { + return needsRenaming(Edge.first.getGUID()); + })) + return true; + } + } + return false; +} + /// Given a list of possible callee implementation for a call site, select one /// that fits the \p Threshold. /// @@ -164,7 +202,7 @@ static const GlobalValueSummary * selectCallee(const ModuleSummaryIndex &Index, const GlobalValueSummaryList &CalleeSummaryList, - unsigned Threshold) { + unsigned Threshold, bool PreventBackwardsModuleRefs) { auto It = llvm::find_if( CalleeSummaryList, [&](const std::unique_ptr &SummaryPtr) { @@ -196,18 +234,25 @@ if (It == CalleeSummaryList.end()) return nullptr; - return cast(It->get()); + const GlobalValueSummary *S = cast(It->get()); + if (PreventBackwardsModuleRefs && + mightIntroduceBackwardsModuleRef(Index, CalleeSummaryList, S)) + return nullptr; + + return S; } /// Return the summary for the function \p GUID that fits the \p Threshold, or /// null if there's no match. static const GlobalValueSummary *selectCallee(GlobalValue::GUID GUID, unsigned Threshold, - const ModuleSummaryIndex &Index) { + const ModuleSummaryIndex &Index, + bool PreventBackwardsModuleRefs) { auto CalleeSummaryList = Index.findGlobalValueSummaryList(GUID); if (CalleeSummaryList == Index.end()) return nullptr; // This function does not have a summary - return selectCallee(Index, CalleeSummaryList->second, Threshold); + return selectCallee(Index, CalleeSummaryList->second, Threshold, + PreventBackwardsModuleRefs); } /// Mark the global \p GUID as export by module \p ExportModulePath if found in @@ -262,12 +307,14 @@ /// Compute the list of functions to import for a given caller. Mark these /// imported functions and the symbols they reference in their source module as /// exported from their source module. -static void computeImportForFunction( - const FunctionSummary &Summary, const ModuleSummaryIndex &Index, - unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries, - SmallVectorImpl &Worklist, - FunctionImporter::ImportMapTy &ImportsForModule, - StringMap *ExportLists = nullptr) { +static void +computeImportForFunction(const FunctionSummary &Summary, + const ModuleSummaryIndex &Index, unsigned Threshold, + const GVSummaryMapTy &DefinedGVSummaries, + SmallVectorImpl &Worklist, + FunctionImporter::ImportMapTy &ImportsForModule, + StringMap *ExportLists, + bool PreventBackwardsModuleRefs) { for (auto &Edge : Summary.calls()) { auto GUID = Edge.first.getGUID(); DEBUG(dbgs() << " edge -> " << GUID << " Threshold:" << Threshold << "\n"); @@ -277,7 +324,8 @@ continue; } - auto *CalleeSummary = selectCallee(GUID, Threshold, Index); + auto *CalleeSummary = + selectCallee(GUID, Threshold, Index, PreventBackwardsModuleRefs); if (!CalleeSummary) { DEBUG(dbgs() << "ignored! No qualifying callee with summary found.\n"); continue; @@ -336,7 +384,8 @@ static void ComputeImportForModule( const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index, FunctionImporter::ImportMapTy &ImportsForModule, - StringMap *ExportLists = nullptr) { + StringMap *ExportLists = nullptr, + bool PreventBackwardsModuleRefs = false) { // Worklist contains the list of function imported in this module, for which // we will analyse the callees and may import further down the callgraph. SmallVector Worklist; @@ -354,7 +403,7 @@ DEBUG(dbgs() << "Initalize import for " << GVSummary.first << "\n"); computeImportForFunction(*FuncSummary, Index, ImportInstrLimit, DefinedGVSummaries, Worklist, ImportsForModule, - ExportLists); + ExportLists, PreventBackwardsModuleRefs); } while (!Worklist.empty()) { @@ -367,7 +416,8 @@ Threshold = Threshold * ImportInstrFactor; computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries, - Worklist, ImportsForModule, ExportLists); + Worklist, ImportsForModule, ExportLists, + PreventBackwardsModuleRefs); } } @@ -378,14 +428,15 @@ const ModuleSummaryIndex &Index, const StringMap &ModuleToDefinedGVSummaries, StringMap &ImportLists, - StringMap &ExportLists) { + StringMap &ExportLists, + bool PreventBackwardsModuleRefs) { // For each module that has function defined, compute the import/export lists. for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) { auto &ImportsForModule = ImportLists[DefinedGVSummaries.first()]; DEBUG(dbgs() << "Computing import for Module '" << DefinedGVSummaries.first() << "'\n"); ComputeImportForModule(DefinedGVSummaries.second, Index, ImportsForModule, - &ExportLists); + &ExportLists, PreventBackwardsModuleRefs); } #ifndef NDEBUG Index: test/tools/gold/X86/Inputs/thinlto_preventbackwardsref-1.ll =================================================================== --- /dev/null +++ test/tools/gold/X86/Inputs/thinlto_preventbackwardsref-1.ll @@ -0,0 +1,23 @@ +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define void @foobar() { +entry: + ret void +} + +define void @baz() { +entry: + call void @f() + ret void +} + +@z = internal global i32 0, align 4 +@w = external global i32, align 4 + +define linkonce_odr void @f() { +entry: + %0 = load i32, i32* @z, align 4 + store i32 %0, i32* @w, align 4 + ret void +} Index: test/tools/gold/X86/Inputs/thinlto_preventbackwardsref-2.ll =================================================================== --- /dev/null +++ test/tools/gold/X86/Inputs/thinlto_preventbackwardsref-2.ll @@ -0,0 +1,19 @@ +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define linkonce_odr void @x() { + ret void +} + +define void @bar() { +entry: + call void @x() + call void @x() + call void @x() + call void @x() + call void @x() + call void (...) @f() + ret void +} + +declare void @f(...) Index: test/tools/gold/X86/Inputs/thinlto_preventbackwardsref-3.ll =================================================================== --- /dev/null +++ test/tools/gold/X86/Inputs/thinlto_preventbackwardsref-3.ll @@ -0,0 +1,12 @@ +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +@z = internal global i32 0, align 4 +@w = external global i32, align 4 + +define linkonce_odr void @f() { +entry: + %0 = load i32, i32* @z, align 4 + store i32 %0, i32* @w, align 4 + ret void +} Index: test/tools/gold/X86/thinlto_preventbackwardsref.ll =================================================================== --- /dev/null +++ test/tools/gold/X86/thinlto_preventbackwardsref.ll @@ -0,0 +1,96 @@ +; This test ensures that we don't import any multiply-defined weak symbol +; that references a local needing renaming when we have separate ThinLTO +; backend processes, and therefore multiple invocations of the gold linker +; (the ThinLink and then the final native object link). Specifically, when +; linking within --start-lib/--end-lib which treats the final object files as +; being in separate libraries, we can run into trouble if the prevailing +; linkonce from the first link is no longer selected by the linker after +; importing/inlining, and we don't have a strong (forward) reference causing +; the linker to pull in the renamed local from that library in the final link. +; This is needed to avoid undefined references in the final link. See the +; comments before the two link steps that describe this scenario. + +; First generate bitcode with a module summary index for each file +; RUN: opt -module-hash -module-summary %s -o %t.o +; RUN: opt -module-hash -module-summary %p/Inputs/thinlto_preventbackwardsref-1.ll -o %t2.o +; RUN: opt -module-hash -module-summary %p/Inputs/thinlto_preventbackwardsref-2.ll -o %t3.o +; RUN: opt -module-hash -module-summary %p/Inputs/thinlto_preventbackwardsref-3.ll -o %t4.o + +; Next do the ThinLink step, specifying thinlto-index-only so that the gold +; plugin exits after generating individual indexes. Also, that flag should +; be used indicate to the importer that we should not import any multiply +; defined weak (including linkonce) symbol referencing a local which will +; be renamed. +; Also, -import-instr-limit=4 is used to prevent importing of some of +; the functions, chiefly bar() which references and would like to import +; the linkonce f() which references a local z. +; Finally, although it doesn't impact the ThinLink step, we use +; --start-lib/--end-lib to match the final link step further down, +; where we want archive library linking behavior. +; Note that because at this point there is a strong reference from +; %t.o to %t2.o (foobar), all symbols from %t2.o are selected +; including the linkonce symbols, and therefore the %t2.o copy of f() +; is prevailing. At this point the %t4.o copy of f() is preempted. +; RUN: %gold -plugin %llvmshlibdir/LLVMgold.so \ +; RUN: --plugin-opt=thinlto \ +; RUN: --plugin-opt=thinlto-index-only \ +; RUN: --plugin-opt=-import-instr-limit=4 \ +; RUN: -o %t5 \ +; RUN: %t.o \ +; RUN: --start-lib %t2.o --end-lib \ +; RUN: --start-lib %t3.o --end-lib \ +; RUN: --start-lib %t4.o --end-lib + +; Simulate the separate ThinLTO backend processes which will do promotion +; (including the weak resolutions), function importing, followed by the +; optimization pipeline including inlining. +; RUN: llvm-lto -thinlto-action=promote -thinlto-index %t.o.thinlto.bc %t.o -o - | llvm-lto -thinlto-action=import -thinlto-index %t.o.thinlto.bc -thinlto-module-id=%t.o - -o - | opt -O2 -o %t.opt.bc +; RUN: llvm-lto -thinlto-action=promote -thinlto-index %t2.o.thinlto.bc %t2.o -o - | llvm-lto -thinlto-action=import -thinlto-index %t2.o.thinlto.bc -thinlto-module-id=%t2.o - -o - | opt -O2 -o %t2.opt.bc +; RUN: llvm-lto -thinlto-action=promote -thinlto-index %t3.o.thinlto.bc %t3.o -o - | llvm-lto -thinlto-action=import -thinlto-index %t3.o.thinlto.bc -thinlto-module-id=%t3.o - -o - | opt -O2 -o %t3.opt.bc +; RUN: llvm-lto -thinlto-action=promote -thinlto-index %t4.o.thinlto.bc %t4.o -o - | llvm-lto -thinlto-action=import -thinlto-index %t4.o.thinlto.bc -thinlto-module-id=%t4.o - -o - | opt -O2 -o %t4.opt.bc + +; The use of f() should not have been imported, since it has multiple copies +; and contains a reference to a local requiring renaming on export (@z). +; RUN: llvm-dis %t3.opt.bc -o - | FileCheck %s --check-prefix=CHECK-OBJ +; CHECK-OBJ: declare void @f(...) + +; Generate native object files for the final link +; RUN: llc %t.opt.bc -filetype=obj -o %t.opt.o +; RUN: llc %t2.opt.bc -filetype=obj -o %t2.opt.o +; RUN: llc %t3.opt.bc -filetype=obj -o %t3.opt.o +; RUN: llc %t4.opt.bc -filetype=obj -o %t4.opt.o + +; Final link. Here the --start-lib/--end-lib provoke archive library linking +; behavior. The relevant effect of this is that the reference of f() in +; %t3.opt.o will not be resolved to the definition in the earlier %t2.opt.o +; library, which no longer is selected as prevailing (since the only strong +; reference to the %t2.opt.o library was inlined into %t.opt.o). Therefore, +; the promoted/renamed copy of z from %t.opt.o is no longer linked in, and +; we would end up with an undefined reference if we had imported f() into +; %t3.opt.o and referenced that copy of the promoted z. Note that the +; gold-plugin does not know whether --start-lib/--end-lib were used. +; RUN: %gold \ +; RUN: -o %t6 \ +; RUN: %t.opt.o \ +; RUN: --start-lib %t2.opt.o --end-lib \ +; RUN: --start-lib %t3.opt.o --end-lib \ +; RUN: --start-lib %t4.opt.o --end-lib + +; Sanity check that bar() is defined in the final binary. +; RUN: llvm-nm %t6 | FileCheck %s --check-prefix=CHECK-FINAL +; CHECK-FINAL: T bar + +@w = global i32 0, align 4 + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define i32 @main() { +entry: + call void (...) @foobar() + call void (...) @bar() + ret i32 0 +} + +declare void @bar(...) +declare void @foobar(...) Index: tools/gold/gold-plugin.cpp =================================================================== --- tools/gold/gold-plugin.cpp +++ tools/gold/gold-plugin.cpp @@ -1370,8 +1370,57 @@ StringMap ImportLists(NextModuleId); StringMap ExportLists(NextModuleId); - ComputeCrossModuleImport(CombinedIndex, ModuleToDefinedGVSummaries, - ImportLists, ExportLists); + + // Note that in several places below we are conservative in the + // thinlto_index_only case, where there will be a separate link process to + // link the native objects. Specifically this is because we don't know + // whether the object files were from archive libraries (potentially formed + // via --start-lib/--end-lib pairs). This is because symbols are not selected + // out of (archive) libraries unless there is a strong reference to a symbol + // defined in it. When there are multiple copies of a symbol with weak + // linkage, and the ThinLink step selects one as prevailing because there + // is a strong reference to something in the library, if the strong reference + // goes away after importing and inlining the final native link will + // no longer link in any symbols from that object. Therefore, we must + // be very careful to ensure that there is always a forward reference + // to external symbols in the thinlto_index_only case. This has several + // implications below: + // + // 1) Avoid backwards references to promoted local symbols. + // Normally for the --start-lib/--end-lib link to succeed, external + // symbol references from the library must be forward (i.e. satisfied by + // an object file later on the link line. However, this could be violated + // by importing of multiply-defined (weak linkage) symbols that reference + // promoted local values. This is because we may decide to import the + // weak linkage function from a module that was earlier on the link line, + // and any referenced locals will be promoted and renamed using that + // module's hash. Therefore, pass true for PreventBackwardsModuleRefs + // in the call to ComputeCrossModuleImport below to ensure we + // conservatively prevent introducing such backwards references (by + // preventing an import of a multiply defined symbol that references a + // local needing renaming). + // FIXME: This could also be addressed by force-importing the renamed + // local in this case, and ensuring that the imported copy has + // local linkage (once internalization is enabled in the + // thinlto_index_only case). + // + // 2) Prevent elimination of non-prevailing copies of weak symbols. + // Since as noted above the ThinLink prevailing copy may no longer + // be pulled in by the final native link if all strong references + // go away after importing/inlining, we need to ensure that non-prevailing + // copies stick around. When the non-prevailing copy is exported, we + // preserve it by converting to weak (via the isExported check in + // isPrevailing below). When it isn't exported, we preserve it for + // any remaining references in the same module by passing true + // for PreserveNonPrevailing in the call to + // thinLTOResolveWeakForLinkerInIndex below to prevent their conversion + // to available_externally. + + // See comments above for when we need to pass true for + // PreventBackwardsModuleRefs. + ComputeCrossModuleImport( + CombinedIndex, ModuleToDefinedGVSummaries, ImportLists, ExportLists, + /* PreventBackwardsModuleRefs = */ options::thinlto_index_only); // Callback for internalization, to prevent internalization of symbols // that were not candidates initially, and those that are being imported @@ -1387,24 +1436,12 @@ const auto &Prevailing = PrevailingCopy.find(GUID); assert(Prevailing != PrevailingCopy.end()); return Prevailing->second == S || - // See comments below for why we conservatively return true for + // See comments above for why we conservatively return true for // exported symbols under thinlto_index_only. (options::thinlto_index_only && isExported(S->modulePath(), GUID)); }; - // Since we don't know whether the object files were from archive - // libraries (potentially formed via --start-lib/--end-lib pairs), - // we must conservatively ensure that linkonce/weak symbols are - // preserved even when they are not prevailing in the thinlto_index_only - // case. In that case there will be a separate link process to link the - // native objects, and depending on the intervening importing/inlining - // the current prevailing copy may no longer be selected out of its - // library. This is because symbols are not selected out of (archive) - // libraries unless there is a strong reference to a symbol defined in it, - // and that strong reference may go away after importing. - // Therefore, we pass true for PreserveNonPrevailing when we have - // thinlto_index_only, and also conservatively return true for - // exported symbols from isPrevailing above. + // See comments above for when we need to pass true for PreserveNonPrevailing. thinLTOResolveWeakForLinkerInIndex( CombinedIndex, isPrevailing, [](StringRef ModuleIdentifier, GlobalValue::GUID GUID,