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: @@ -172,6 +174,8 @@ /// are listed in the derived FunctionSummary object. std::vector RefEdgeList; + bool isLive() const { return Flags.Live; } + protected: GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector Refs) : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {} @@ -213,19 +217,17 @@ /// 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; } - - /// 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; } /// Return the list of values referenced by this global value definition. ArrayRef refs() const { return RefEdgeList; } + + friend class ModuleSummaryIndex; + friend void computeDeadSymbols(class ModuleSummaryIndex &, + const DenseSet &); }; /// \brief Alias summary information. @@ -535,6 +537,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 WithGlobalValueDeadStripping = false; + // YAML I/O support. friend yaml::MappingTraits; @@ -550,6 +557,17 @@ const_gvsummary_iterator end() const { return GlobalValueMap.end(); } size_t size() const { return GlobalValueMap.size(); } + bool withGlobalValueDeadStripping() const { + return WithGlobalValueDeadStripping; + } + void setWithGlobalValueDeadStripping() { + WithGlobalValueDeadStripping = true; + } + + bool isGlobalValueLive(const GlobalValueSummary *GVS) const { + return !WithGlobalValueDeadStripping || 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 @@ -930,6 +930,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()) @@ -973,11 +984,10 @@ GlobalValue::dropLLVMManglingEscape(Res.second.IRName))); } - auto DeadSymbols = - computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols); + 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,82 +412,86 @@ #endif } -DenseSet llvm::computeDeadSymbols( - const ModuleSummaryIndex &Index, +void llvm::computeDeadSymbols( + ModuleSummaryIndex &Index, const DenseSet &GUIDPreservedSymbols) { + assert(!Index.withGlobalValueDeadStripping()); if (!ComputeDead) - return DenseSet(); + return; if (GUIDPreservedSymbols.empty()) // Don't do anything when nothing is live, this is friendly with tests. - return DenseSet(); - DenseSet LiveSymbols; + return; + unsigned LiveSymbols = 0; SmallVector Worklist; Worklist.reserve(GUIDPreservedSymbols.size() * 2); + // Make value live and add it to the worklist. + auto makeLiveRoot = [&](ValueInfo VI) { + for (auto &S : VI.getSummaryList()) + S->setLive(true); + Worklist.push_back(VI); + ++LiveSymbols; + }; + // 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 makeLive = [&](ValueInfo VI) { + bool Changed = false; + for (auto &S : VI.getSummaryList()) + if (!S->isLive()) { + Changed = true; + S->setLive(true); + } + if (Changed) { + ++LiveSymbols; + Worklist.push_back(VI); + } + }; + for (auto GUID : GUIDPreservedSymbols) { ValueInfo VI = Index.getValueInfo(GUID); if (!VI) continue; DEBUG(dbgs() << "Live root: " << VI.getGUID() << "\n"); - LiveSymbols.insert(VI); - Worklist.push_back(VI); + makeLiveRoot(VI); } + // Add values flagged in the index as live roots to the worklist. for (const auto &Entry : Index) { bool IsLiveRoot = llvm::any_of( Entry.second.SummaryList, [&](const std::unique_ptr &Summary) { - return Summary->liveRoot(); + return Summary->isLive(); }); if (!IsLiveRoot) continue; DEBUG(dbgs() << "Live root (summary): " << Entry.first << "\n"); - Worklist.push_back(ValueInfo(&Entry)); + makeLiveRoot(ValueInfo(&Entry)); } while (!Worklist.empty()) { auto VI = Worklist.pop_back_val(); - // FIXME: we should only make the prevailing copy live here for (auto &Summary : VI.getSummaryList()) { - for (auto Ref : Summary->refs()) { - if (LiveSymbols.insert(Ref).second) { - DEBUG(dbgs() << "Marking live (ref): " << Ref.getGUID() << "\n"); - Worklist.push_back(Ref); - } - } - if (auto *FS = dyn_cast(Summary.get())) { - for (auto Call : FS->calls()) { - if (LiveSymbols.insert(Call.first).second) { - DEBUG(dbgs() << "Marking live (call): " << Call.first.getGUID() - << "\n"); - Worklist.push_back(Call.first); - } - } - } + + for (auto Ref : Summary->refs()) + makeLive(Ref); + if (auto *FS = dyn_cast(Summary.get())) + for (auto Call : FS->calls()) + makeLive(Call.first); if (auto *AS = dyn_cast(Summary.get())) { auto AliaseeGUID = AS->getAliasee().getOriginalName(); ValueInfo AliaseeVI = Index.getValueInfo(AliaseeGUID); - if (AliaseeVI && LiveSymbols.insert(AliaseeVI).second) { - DEBUG(dbgs() << "Marking live (alias): " << AliaseeGUID << "\n"); - Worklist.push_back(AliaseeVI); - } + if (AliaseeVI) + makeLive(AliaseeVI); } } } - DenseSet DeadSymbols; - DeadSymbols.reserve( - std::min(Index.size(), Index.size() - LiveSymbols.size())); - for (auto &Entry : Index) { - if (!LiveSymbols.count(ValueInfo(&Entry))) { - DEBUG(dbgs() << "Marking dead: " << Entry.first << "\n"); - DeadSymbols.insert(Entry.first); - } - } - DEBUG(dbgs() << LiveSymbols.size() << " symbols Live, and " - << DeadSymbols.size() << " symbols Dead \n"); - NumDeadSymbols += DeadSymbols.size(); - NumLiveSymbols += LiveSymbols.size(); - return DeadSymbols; + Index.setWithGlobalValueDeadStripping(); + + unsigned DeadSymbols = Index.size() - LiveSymbols; + DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols + << " symbols Dead \n"); + NumDeadSymbols += DeadSymbols; + NumLiveSymbols += LiveSymbols; } /// Compute the set of summaries needed for a ThinLTO backend compilation of