Index: include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- include/llvm/IR/ModuleSummaryIndex.h +++ include/llvm/IR/ModuleSummaryIndex.h @@ -250,7 +250,8 @@ friend class ModuleSummaryIndex; friend void computeDeadSymbols(class ModuleSummaryIndex &, - const DenseSet &); + const DenseSet &, + function_ref); }; /// \brief Alias summary information. Index: include/llvm/Transforms/IPO/FunctionImport.h =================================================================== --- include/llvm/Transforms/IPO/FunctionImport.h +++ include/llvm/Transforms/IPO/FunctionImport.h @@ -109,10 +109,14 @@ /// Compute all the symbols that are "dead": i.e these that can't be reached /// in the graph from any of the given symbols listed in -/// \p GUIDPreservedSymbols. -void computeDeadSymbols( - ModuleSummaryIndex &Index, - const DenseSet &GUIDPreservedSymbols); +/// \p GUIDPreservedSymbols. Non-prevailing symbols are normally "dead", +/// \p isPrevaling predicate is used to check if symbol is prevailing. +void computeDeadSymbols(ModuleSummaryIndex &Index, + const DenseSet &GUIDPreservedSymbols, + function_ref isPrevaling); + +/// Converts value \p GV to declaration. +void convertToDeclaration(GlobalValue &GV); /// Compute the set of summaries needed for a ThinLTO backend compilation of /// \p ModulePath. Index: lib/LTO/LTO.cpp =================================================================== --- lib/LTO/LTO.cpp +++ lib/LTO/LTO.cpp @@ -745,16 +745,24 @@ Error LTO::run(AddStreamFn AddStream, NativeObjectCache Cache) { // Compute "dead" symbols, we don't want to import/export these! DenseSet GUIDPreservedSymbols; + DenseSet GUIDPrevailingSymbols; for (auto &Res : GlobalResolutions) { - if (Res.second.VisibleOutsideSummary && - // IRName will be defined if we have seen the prevailing copy of - // this value. If not, no need to preserve any ThinLTO copies. - !Res.second.IRName.empty()) - GUIDPreservedSymbols.insert(GlobalValue::getGUID( - GlobalValue::dropLLVMManglingEscape(Res.second.IRName))); + // IRName will be defined if we have seen the prevailing copy of + // this value. If not, no need to preserve any ThinLTO copies. + if (Res.second.IRName.empty()) + continue; + + GlobalValue::GUID G = GlobalValue::getGUID( + GlobalValue::dropLLVMManglingEscape(Res.second.IRName)); + GUIDPrevailingSymbols.insert(G); + if (Res.second.VisibleOutsideSummary) + GUIDPreservedSymbols.insert(G); } - computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols); + auto isPrevailing = [&](GlobalValue::GUID G) { + return GUIDPrevailingSymbols.count(G); + }; + computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols, isPrevailing); if (auto E = runRegularLTO(AddStream)) return E; Index: lib/LTO/LTOBackend.cpp =================================================================== --- lib/LTO/LTOBackend.cpp +++ lib/LTO/LTOBackend.cpp @@ -393,6 +393,17 @@ return Error::success(); } +static void dropDeadSymbols(Module &Mod, const GVSummaryMapTy &DefinedGlobals, + const ModuleSummaryIndex &Index) { + for (auto &GV : Mod) { + auto It = DefinedGlobals.find(GV.getGUID()); + if (It == DefinedGlobals.end()) + continue; + if (!Index.isGlobalValueLive(It->second)) + convertToDeclaration(GV); + } +} + Error lto::thinBackend(Config &Conf, unsigned Task, AddStreamFn AddStream, Module &Mod, const ModuleSummaryIndex &CombinedIndex, const FunctionImporter::ImportMapTy &ImportList, @@ -414,6 +425,8 @@ renameModuleForThinLTO(Mod, CombinedIndex); + dropDeadSymbols(Mod, DefinedGlobals, CombinedIndex); + thinLTOResolveWeakForLinkerModule(Mod, DefinedGlobals); if (Conf.PostPromoteModuleHook && !Conf.PostPromoteModuleHook(Task, Mod)) Index: lib/LTO/ThinLTOCodeGenerator.cpp =================================================================== --- lib/LTO/ThinLTOCodeGenerator.cpp +++ lib/LTO/ThinLTOCodeGenerator.cpp @@ -621,6 +621,13 @@ thinLTOInternalizeAndPromoteInIndex(Index, isExported); } +static void markLive(ModuleSummaryIndex &Index, + const DenseSet &GUIDPreservedSymbols) { + // If there is at least one symbol, it means it is prevailing. + auto isPrevailing = [&](GlobalValue::GUID G) { return true; }; + computeDeadSymbols(Index, GUIDPreservedSymbols, isPrevailing); +} + /** * Perform promotion and renaming of exported internal functions. * Index is updated to reflect linkage changes from weak resolution. @@ -639,7 +646,7 @@ PreservedSymbols, Triple(TheModule.getTargetTriple())); // Compute "dead" symbols, we don't want to import/export these! - computeDeadSymbols(Index, GUIDPreservedSymbols); + markLive(Index, GUIDPreservedSymbols); // Generate import/export list StringMap ImportLists(ModuleCount); @@ -678,7 +685,7 @@ PreservedSymbols, Triple(TheModule.getTargetTriple())); // Compute "dead" symbols, we don't want to import/export these! - computeDeadSymbols(Index, GUIDPreservedSymbols); + markLive(Index, GUIDPreservedSymbols); // Generate import/export list StringMap ImportLists(ModuleCount); @@ -755,7 +762,7 @@ Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries); // Compute "dead" symbols, we don't want to import/export these! - computeDeadSymbols(Index, GUIDPreservedSymbols); + markLive(Index, GUIDPreservedSymbols); // Generate import/export list StringMap ImportLists(ModuleCount); @@ -901,7 +908,7 @@ computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple); // Compute "dead" symbols, we don't want to import/export these! - computeDeadSymbols(*Index, GUIDPreservedSymbols); + markLive(*Index, GUIDPreservedSymbols); // Collect the import/export lists for all modules from the call-graph in the // combined index. Index: lib/Transforms/IPO/FunctionImport.cpp =================================================================== --- lib/Transforms/IPO/FunctionImport.cpp +++ lib/Transforms/IPO/FunctionImport.cpp @@ -178,8 +178,11 @@ // filtered out. if (GVSummary->getSummaryKind() == GlobalValueSummary::GlobalVarKind) return false; + + // There is no point in importing these, we can't inline them if (GlobalValue::isInterposableLinkage(GVSummary->linkage())) - // There is no point in importing these, we can't inline them + return false; + if (!Index.isGlobalValueLive(GVSummary)) return false; auto *Summary = cast(GVSummary->getBaseObject()); @@ -494,7 +497,8 @@ void llvm::computeDeadSymbols( ModuleSummaryIndex &Index, - const DenseSet &GUIDPreservedSymbols) { + const DenseSet &GUIDPreservedSymbols, + function_ref isPrevaling) { assert(!Index.withGlobalValueDeadStripping()); if (!ComputeDead) return; @@ -502,29 +506,32 @@ // Don't do anything when nothing is live, this is friendly with tests. return; unsigned LiveSymbols = 0; - SmallVector Worklist; + + SmallVector, 128> Worklist; Worklist.reserve(GUIDPreservedSymbols.size() * 2); - for (auto GUID : GUIDPreservedSymbols) { - ValueInfo VI = Index.getValueInfo(GUID); - if (!VI) - continue; - for (auto &S : VI.getSummaryList()) - S->setLive(true); - } // Add values flagged in the index as live roots to the worklist. for (const auto &Entry : Index) for (auto &S : Entry.second.SummaryList) if (S->isLive()) { DEBUG(dbgs() << "Live root: " << Entry.first << "\n"); - Worklist.push_back(ValueInfo(&Entry)); + Worklist.push_back({ValueInfo(&Entry), true}); ++LiveSymbols; break; } + for (auto GUID : GUIDPreservedSymbols) { + ValueInfo VI = Index.getValueInfo(GUID); + if (!VI) + continue; + for (const std::unique_ptr &S : VI.getSummaryList()) + S->setLive(true); + ++LiveSymbols; + Worklist.push_back({VI, false}); + } + // Make value live and add it to the worklist if it was not live before. - // FIXME: we should only make the prevailing copy live here - auto visit = [&](ValueInfo VI) { + auto Visit = [&](ValueInfo VI, bool IsLiveRoot) { // FIXME: If we knew which edges were created for indirect call profiles, // we could skip them here. Any that are live should be reached via // other edges, e.g. reference edges. Otherwise, using a profile collected @@ -536,24 +543,33 @@ VI = updateValueInfoForIndirectCalls(Index, VI); if (!VI) return; + if (!IsLiveRoot && !isPrevaling(VI.getGUID())) + return; for (auto &S : VI.getSummaryList()) if (S->isLive()) return; for (auto &S : VI.getSummaryList()) S->setLive(true); ++LiveSymbols; - Worklist.push_back(VI); + Worklist.push_back({VI, IsLiveRoot}); }; - while (!Worklist.empty()) { - auto VI = Worklist.pop_back_val(); + while (!Worklist.empty()) { + ValueInfo VI; + bool IsLiveRoot; + std::tie(VI, IsLiveRoot) = Worklist.pop_back_val(); + for (auto &Summary : VI.getSummaryList()) { GlobalValueSummary *Base = Summary->getBaseObject(); + // Set base value live in case it is an alias. + if (auto *AS = dyn_cast(Summary.get())) + Base->setLive(true); + for (auto Ref : Base->refs()) - visit(Ref); + Visit(Ref, IsLiveRoot); if (auto *FS = dyn_cast(Base)) for (auto Call : FS->calls()) - visit(Call.first); + Visit(Call.first, IsLiveRoot); } } Index.setWithGlobalValueDeadStripping(); @@ -602,26 +618,26 @@ return std::error_code(); } +void llvm::convertToDeclaration(GlobalValue &GV) { + DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName() << "\n"); + if (Function *F = dyn_cast(&GV)) { + F->deleteBody(); + F->clearMetadata(); + } else if (GlobalVariable *V = dyn_cast(&GV)) { + V->setInitializer(nullptr); + V->setLinkage(GlobalValue::ExternalLinkage); + V->clearMetadata(); + } else + // For now we don't resolve or drop aliases. Once we do we'll + // need to add support here for creating either a function or + // variable declaration, and return the new GlobalValue* for + // the caller to use. + llvm_unreachable("Expected function or variable"); +} + /// Fixup WeakForLinker linkages in \p TheModule based on summary analysis. void llvm::thinLTOResolveWeakForLinkerModule( Module &TheModule, const GVSummaryMapTy &DefinedGlobals) { - auto ConvertToDeclaration = [](GlobalValue &GV) { - DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName() << "\n"); - if (Function *F = dyn_cast(&GV)) { - F->deleteBody(); - F->clearMetadata(); - } else if (GlobalVariable *V = dyn_cast(&GV)) { - V->setInitializer(nullptr); - V->setLinkage(GlobalValue::ExternalLinkage); - V->clearMetadata(); - } else - // For now we don't resolve or drop aliases. Once we do we'll - // need to add support here for creating either a function or - // variable declaration, and return the new GlobalValue* for - // the caller to use. - llvm_unreachable("Expected function or variable"); - }; - auto updateLinkage = [&](GlobalValue &GV) { // See if the global summary analysis computed a new resolved linkage. const auto &GS = DefinedGlobals.find(GV.getGUID()); @@ -652,7 +668,7 @@ // the definition in that case. if (GlobalValue::isAvailableExternallyLinkage(NewLinkage) && GlobalValue::isInterposableLinkage(GV.getLinkage())) - ConvertToDeclaration(GV); + convertToDeclaration(GV); else { DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from " << GV.getLinkage() << " to " << NewLinkage << "\n"); Index: test/LTO/Resolution/X86/Inputs/not-prevailing.ll =================================================================== --- test/LTO/Resolution/X86/Inputs/not-prevailing.ll +++ test/LTO/Resolution/X86/Inputs/not-prevailing.ll @@ -0,0 +1,6 @@ +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define void @bar() { + ret void +} Index: test/LTO/Resolution/X86/not-prevailing.ll =================================================================== --- test/LTO/Resolution/X86/not-prevailing.ll +++ test/LTO/Resolution/X86/not-prevailing.ll @@ -0,0 +1,37 @@ +; RUN: opt -module-summary %s -o %t1.o +; RUN: opt -module-summary -o %t2.o %S/Inputs/not-prevailing.ll +; RUN: llvm-lto2 run -o %t3.o %t1.o %t2.o -r %t1.o,foo,x -r %t1.o,zed,px -r %t1.o,bar,x \ +; RUN: -r %t2.o,bar,x -save-temps + +; Check that 'foo' and 'bar' were not inlined. +; CHECK: zed: +; CHECK-NEXT: {{.*}} pushq %rbx +; CHECK-NEXT: {{.*}} callq 0 +; CHECK-NEXT: {{.*}} movl %eax, %ebx +; CHECK-NEXT: {{.*}} callq 0 +; CHECK-NEXT: {{.*}} movl %ebx, %eax +; CHECK-NEXT: {{.*}} popq %rbx +; CHECK-NEXT: {{.*}} retq + +; RUN: llvm-objdump -d %t3.o.1 | FileCheck %s +; RUN: llvm-readelf --symbols %t3.o.1 | FileCheck %s --check-prefix=SYMBOLS + +; Check that 'foo' and 'bar' produced as undefined. +; SYMBOLS: NOTYPE GLOBAL DEFAULT UND bar +; SYMBOLS: NOTYPE GLOBAL DEFAULT UND foo +; SYMBOLS: FUNC GLOBAL DEFAULT 2 zed + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define weak i32 @foo() { + ret i32 65 +} + +declare void @bar() + +define i32 @zed() { + %1 = tail call i32 @foo() + call void @bar() + ret i32 %1 +}