Index: include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- include/llvm/IR/ModuleSummaryIndex.h +++ include/llvm/IR/ModuleSummaryIndex.h @@ -134,16 +134,18 @@ /// be renamed or references something that can't be renamed). unsigned NotEligibleToImport : 1; - /// Indicate that the global value must be considered a live root for - /// index-based liveness analysis. Used for special LLVM values such as - /// llvm.global_ctors that the linker does not know about. - unsigned LiveRoot : 1; + /// In per-module summary, indicate that the global value must be considered + /// a live root for index-based liveness analysis. Used for special LLVM + /// values such as llvm.global_ctors that the linker does not know about. + /// + /// In combined summary, indicate that the global value is live. + unsigned Live : 1; /// Convenience Constructors explicit GVFlags(GlobalValue::LinkageTypes Linkage, - bool NotEligibleToImport, bool LiveRoot) + bool NotEligibleToImport, bool Live) : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport), - LiveRoot(LiveRoot) {} + Live(Live) {} }; private: @@ -213,13 +215,9 @@ /// Return true if this global value can't be imported. bool notEligibleToImport() const { return Flags.NotEligibleToImport; } - /// Return true if this global value must be considered a root for live - /// value analysis on the index. - bool liveRoot() const { return Flags.LiveRoot; } + bool isLive() const { return Flags.Live; } - /// Flag that this global value must be considered a root for live - /// value analysis on the index. - void setLiveRoot() { Flags.LiveRoot = true; } + void setLive(bool Live) { Flags.Live = Live; } /// Flag that this global value cannot be imported. void setNotEligibleToImport() { Flags.NotEligibleToImport = true; } @@ -535,6 +533,11 @@ /// GUIDs, it will be mapped to 0. std::map OidGuidMap; + /// Indicates that summary-based GlobalValue GC has run, and values with + /// GVFlags::Live==false are really dead. Otherwise, all values must be + /// considered live. + bool WithGlobalValueGc = false; + // YAML I/O support. friend yaml::MappingTraits; @@ -550,6 +553,13 @@ const_gvsummary_iterator end() const { return GlobalValueMap.end(); } size_t size() const { return GlobalValueMap.size(); } + bool withGlobalValueGc() const { return WithGlobalValueGc; } + void setWithGlobalValueGc() { WithGlobalValueGc = true; } + + bool isGlobalValueLive(const GlobalValueSummary *GVS) const { + return !WithGlobalValueGc || GVS->isLive(); + } + /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo(). ValueInfo getValueInfo(GlobalValue::GUID GUID) const { auto I = GlobalValueMap.find(GUID); Index: include/llvm/Transforms/IPO/FunctionImport.h =================================================================== --- include/llvm/Transforms/IPO/FunctionImport.h +++ include/llvm/Transforms/IPO/FunctionImport.h @@ -81,15 +81,11 @@ /// \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 DeadSymbols (optional) contains a list of GUID that are deemed "dead" and -/// will be ignored for the purpose of importing. void ComputeCrossModuleImport( const ModuleSummaryIndex &Index, const StringMap &ModuleToDefinedGVSummaries, StringMap &ImportLists, - StringMap &ExportLists, - const DenseSet *DeadSymbols = nullptr); + StringMap &ExportLists); /// Compute all the imports for the given module using the Index. /// @@ -102,9 +98,9 @@ /// 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. -DenseSet -computeDeadSymbols(const ModuleSummaryIndex &Index, - const DenseSet &GUIDPreservedSymbols); +void computeDeadSymbols( + ModuleSummaryIndex &Index, + const DenseSet &GUIDPreservedSymbols); /// Compute the set of summaries needed for a ThinLTO backend compilation of /// \p ModulePath. Index: lib/Analysis/ModuleSummaryAnalysis.cpp =================================================================== --- lib/Analysis/ModuleSummaryAnalysis.cpp +++ lib/Analysis/ModuleSummaryAnalysis.cpp @@ -275,7 +275,7 @@ // FIXME: refactor this to use the same code that inliner is using. F.isVarArg(); GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport, - /* LiveRoot = */ false); + /* Live = */ false); auto FuncSummary = llvm::make_unique( Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(), TypeTests.takeVector(), TypeTestAssumeVCalls.takeVector(), @@ -295,7 +295,7 @@ findRefEdges(Index, &V, RefEdges, Visited); bool NonRenamableLocal = isNonRenamableLocal(V); GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal, - /* LiveRoot = */ false); + /* Live = */ false); auto GVarSummary = llvm::make_unique(Flags, RefEdges.takeVector()); if (NonRenamableLocal) @@ -308,7 +308,7 @@ DenseSet &CantBePromoted) { bool NonRenamableLocal = isNonRenamableLocal(A); GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal, - /* LiveRoot = */ false); + /* Live = */ false); auto AS = llvm::make_unique(Flags, ArrayRef{}); auto *Aliasee = A.getBaseObject(); auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee); @@ -323,7 +323,7 @@ static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) { if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name))) for (auto &Summary : VI.getSummaryList()) - Summary->setLiveRoot(); + Summary->setLive(true); } ModuleSummaryIndex llvm::buildModuleSummaryIndex( @@ -423,8 +423,8 @@ return; assert(GV->isDeclaration() && "Def in module asm already has definition"); GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage, - /* NotEligibleToImport */ true, - /* LiveRoot */ true); + /* NotEligibleToImport = */ true, + /* Live = */ true); CantBePromoted.insert(GlobalValue::getGUID(Name)); // Create the appropriate summary type. if (isa(GV)) { Index: lib/Bitcode/Reader/BitcodeReader.cpp =================================================================== --- lib/Bitcode/Reader/BitcodeReader.cpp +++ lib/Bitcode/Reader/BitcodeReader.cpp @@ -865,11 +865,11 @@ auto Linkage = GlobalValue::LinkageTypes(RawFlags & 0xF); // 4 bits RawFlags = RawFlags >> 4; bool NotEligibleToImport = (RawFlags & 0x1) || Version < 3; - // The LiveRoot flag wasn't introduced until version 3. For dead stripping + // The Live flag wasn't introduced until version 3. For dead stripping // to work correctly on earlier versions, we must conservatively treat all // values as live. - bool LiveRoot = (RawFlags & 0x2) || Version < 3; - return GlobalValueSummary::GVFlags(Linkage, NotEligibleToImport, LiveRoot); + bool Live = (RawFlags & 0x2) || Version < 3; + return GlobalValueSummary::GVFlags(Linkage, NotEligibleToImport, Live); } static GlobalValue::VisibilityTypes getDecodedVisibility(unsigned Val) { Index: lib/Bitcode/Writer/BitcodeWriter.cpp =================================================================== --- lib/Bitcode/Writer/BitcodeWriter.cpp +++ lib/Bitcode/Writer/BitcodeWriter.cpp @@ -872,7 +872,7 @@ uint64_t RawFlags = 0; RawFlags |= Flags.NotEligibleToImport; // bool - RawFlags |= (Flags.LiveRoot << 1); + RawFlags |= (Flags.Live << 1); // Linkage don't need to be remapped at that time for the summary. Any future // change to the getEncodedLinkage() function will need to be taken into // account here as well. Index: lib/LTO/LTO.cpp =================================================================== --- lib/LTO/LTO.cpp +++ lib/LTO/LTO.cpp @@ -621,6 +621,19 @@ } Error LTO::run(AddStreamFn AddStream, NativeObjectCache Cache) { + // Compute "dead" symbols, we don't want to import/export these! + DenseSet GUIDPreservedSymbols; + for (auto &Res : GlobalResolutions) { + if (Res.second.VisibleOutsideThinLTO && + // 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))); + } + + computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols); + // Save the status of having a regularLTO combined module, as // this is needed for generating the ThinLTO Task ID, and // the CombinedModule will be moved at the end of runRegularLTO. @@ -930,6 +943,17 @@ }; } +static bool IsLiveByGUID(const ModuleSummaryIndex &Index, + GlobalValue::GUID GUID) { + auto VI = Index.getValueInfo(GUID); + if (!VI) + return false; + for (auto &I : VI.getSummaryList()) + if (Index.isGlobalValueLive(I.get())) + return true; + return false; +} + Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache, bool HasRegularLTO) { if (ThinLTO.ModuleMap.empty()) @@ -962,22 +986,8 @@ StringMap> ResolvedODR; if (Conf.OptLevel > 0) { - // Compute "dead" symbols, we don't want to import/export these! - DenseSet GUIDPreservedSymbols; - for (auto &Res : GlobalResolutions) { - if (Res.second.VisibleOutsideThinLTO && - // 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))); - } - - auto DeadSymbols = - computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols); - ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries, - ImportLists, ExportLists, &DeadSymbols); + ImportLists, ExportLists); std::set ExportedGUIDs; for (auto &Res : GlobalResolutions) { @@ -992,7 +1002,7 @@ auto GUID = GlobalValue::getGUID( GlobalValue::dropLLVMManglingEscape(Res.second.IRName)); // Mark exported unless index-based analysis determined it to be dead. - if (!DeadSymbols.count(GUID)) + if (IsLiveByGUID(ThinLTO.CombinedIndex, GUID)) ExportedGUIDs.insert(GUID); } Index: lib/LTO/ThinLTOCodeGenerator.cpp =================================================================== --- lib/LTO/ThinLTOCodeGenerator.cpp +++ lib/LTO/ThinLTOCodeGenerator.cpp @@ -628,13 +628,13 @@ PreservedSymbols, Triple(TheModule.getTargetTriple())); // Compute "dead" symbols, we don't want to import/export these! - auto DeadSymbols = computeDeadSymbols(Index, GUIDPreservedSymbols); + computeDeadSymbols(Index, GUIDPreservedSymbols); // Generate import/export list StringMap ImportLists(ModuleCount); StringMap ExportLists(ModuleCount); ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists, - ExportLists, &DeadSymbols); + ExportLists); // Resolve LinkOnce/Weak symbols. StringMap> ResolvedODR; @@ -673,13 +673,13 @@ PreservedSymbols, Triple(TheModule.getTargetTriple())); // Compute "dead" symbols, we don't want to import/export these! - auto DeadSymbols = computeDeadSymbols(Index, GUIDPreservedSymbols); + computeDeadSymbols(Index, GUIDPreservedSymbols); // Generate import/export list StringMap ImportLists(ModuleCount); StringMap ExportLists(ModuleCount); ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists, - ExportLists, &DeadSymbols); + ExportLists); auto &ImportList = ImportLists[TheModule.getModuleIdentifier()]; crossImportIntoModule(TheModule, Index, ModuleMap, ImportList); @@ -750,13 +750,13 @@ Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries); // Compute "dead" symbols, we don't want to import/export these! - auto DeadSymbols = computeDeadSymbols(Index, GUIDPreservedSymbols); + computeDeadSymbols(Index, GUIDPreservedSymbols); // Generate import/export list StringMap ImportLists(ModuleCount); StringMap ExportLists(ModuleCount); ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists, - ExportLists, &DeadSymbols); + ExportLists); auto &ExportList = ExportLists[ModuleIdentifier]; // Be friendly and don't nuke totally the module when the client didn't @@ -902,14 +902,14 @@ computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple); // Compute "dead" symbols, we don't want to import/export these! - auto DeadSymbols = computeDeadSymbols(*Index, GUIDPreservedSymbols); + computeDeadSymbols(*Index, GUIDPreservedSymbols); // Collect the import/export lists for all modules from the call-graph in the // combined index. StringMap ImportLists(ModuleCount); StringMap ExportLists(ModuleCount); ComputeCrossModuleImport(*Index, ModuleToDefinedGVSummaries, ImportLists, - ExportLists, &DeadSymbols); + ExportLists); // We use a std::map here to be able to have a defined ordering when // producing a hash for the cache entry. Index: lib/Transforms/IPO/FunctionImport.cpp =================================================================== --- lib/Transforms/IPO/FunctionImport.cpp +++ lib/Transforms/IPO/FunctionImport.cpp @@ -292,8 +292,7 @@ static void ComputeImportForModule( const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index, FunctionImporter::ImportMapTy &ImportList, - StringMap *ExportLists = nullptr, - const DenseSet *DeadSymbols = nullptr) { + StringMap *ExportLists = nullptr) { // 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; @@ -301,7 +300,7 @@ // Populate the worklist with the import for the functions in the current // module for (auto &GVSummary : DefinedGVSummaries) { - if (DeadSymbols && DeadSymbols->count(GVSummary.first)) { + if (!Index.isGlobalValueLive(GVSummary.second)) { DEBUG(dbgs() << "Ignores Dead GUID: " << GVSummary.first << "\n"); continue; } @@ -344,15 +343,14 @@ const ModuleSummaryIndex &Index, const StringMap &ModuleToDefinedGVSummaries, StringMap &ImportLists, - StringMap &ExportLists, - const DenseSet *DeadSymbols) { + StringMap &ExportLists) { // For each module that has function defined, compute the import/export lists. for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) { auto &ImportList = ImportLists[DefinedGVSummaries.first()]; DEBUG(dbgs() << "Computing import for Module '" << DefinedGVSummaries.first() << "'\n"); ComputeImportForModule(DefinedGVSummaries.second, Index, ImportList, - &ExportLists, DeadSymbols); + &ExportLists); } // When computing imports we added all GUIDs referenced by anything @@ -414,14 +412,15 @@ #endif } -DenseSet llvm::computeDeadSymbols( - const ModuleSummaryIndex &Index, +void llvm::computeDeadSymbols( + ModuleSummaryIndex &Index, const DenseSet &GUIDPreservedSymbols) { + assert(!Index.withGlobalValueGc()); if (!ComputeDead) - return DenseSet(); + return; if (GUIDPreservedSymbols.empty()) // Don't do anything when nothing is live, this is friendly with tests. - return DenseSet(); + return; DenseSet LiveSymbols; SmallVector Worklist; Worklist.reserve(GUIDPreservedSymbols.size() * 2); @@ -438,7 +437,7 @@ bool IsLiveRoot = llvm::any_of( Entry.second.SummaryList, [&](const std::unique_ptr &Summary) { - return Summary->liveRoot(); + return Summary->isLive(); }); if (!IsLiveRoot) continue; @@ -476,20 +475,21 @@ } } } - DenseSet DeadSymbols; - DeadSymbols.reserve( - std::min(Index.size(), Index.size() - LiveSymbols.size())); + unsigned NewDeadSymbols = 0; for (auto &Entry : Index) { - if (!LiveSymbols.count(ValueInfo(&Entry))) { + bool isLive = LiveSymbols.count(ValueInfo(&Entry)); + if (!isLive) { DEBUG(dbgs() << "Marking dead: " << Entry.first << "\n"); - DeadSymbols.insert(Entry.first); + ++NewDeadSymbols; } + for (auto &S : Entry.second.SummaryList) + S->setLive(isLive); } - DEBUG(dbgs() << LiveSymbols.size() << " symbols Live, and " - << DeadSymbols.size() << " symbols Dead \n"); - NumDeadSymbols += DeadSymbols.size(); + Index.setWithGlobalValueGc(); + DEBUG(dbgs() << LiveSymbols.size() << " symbols Live, and " << NewDeadSymbols + << " symbols Dead \n"); + NumDeadSymbols += NewDeadSymbols; NumLiveSymbols += LiveSymbols.size(); - return DeadSymbols; } /// Compute the set of summaries needed for a ThinLTO backend compilation of Index: test/ThinLTO/X86/deadstrip.ll =================================================================== --- test/ThinLTO/X86/deadstrip.ll +++ test/ThinLTO/X86/deadstrip.ll @@ -22,6 +22,20 @@ ; RUN: llvm-dis < %t.out.1.3.import.bc | FileCheck %s --check-prefix=CHECK2 ; RUN: llvm-nm %t.out.1 | FileCheck %s --check-prefix=CHECK2-NM +; RUN: llvm-bcanalyzer -dump %t.out.index.bc | FileCheck %s --check-prefix=COMBINED +; Live, NotEligibleForImport, Internal +; COMBINED-DAG: