Index: include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- include/llvm/IR/ModuleSummaryIndex.h +++ include/llvm/IR/ModuleSummaryIndex.h @@ -466,6 +466,12 @@ void collectDefinedFunctionsForModule( StringRef ModulePath, std::map &FunctionInfoMap) const; + + /// Collect for each module the list of Summaries it defines (GUID -> + /// Summary). + void collectDefinedGVSummariesPerModule( + StringMap> & + ModuleToDefinedGVSummaries) const; }; } // End llvm namespace Index: include/llvm/Transforms/IPO/FunctionImport.h =================================================================== --- include/llvm/Transforms/IPO/FunctionImport.h +++ include/llvm/Transforms/IPO/FunctionImport.h @@ -19,6 +19,7 @@ namespace llvm { class LLVMContext; +class GlobalValueSummary; class Module; class ModuleSummaryIndex; @@ -59,6 +60,9 @@ /// Compute all the imports and exports for every module in the Index. /// +/// \p ModuleToDefinedGVSummaries contains for each Module a map +/// (GUID -> Summary) for every global defined in the module. +/// /// \p ImportLists will be populated with an entry for every Module we are /// importing into. This entry is itself a map that can be passed to /// FunctionImporter::importFunctions() above (see description there). @@ -68,6 +72,8 @@ /// is the set of globals that need to be promoted/renamed appropriately. void ComputeCrossModuleImport( const ModuleSummaryIndex &Index, + const StringMap> & + ModuleToDefinedGVSummaries, StringMap &ImportLists, StringMap &ExportLists); Index: lib/IR/ModuleSummaryIndex.cpp =================================================================== --- lib/IR/ModuleSummaryIndex.cpp +++ lib/IR/ModuleSummaryIndex.cpp @@ -89,6 +89,19 @@ } } +// Collect for each module the list of function it defines (GUID -> Summary). +void ModuleSummaryIndex::collectDefinedGVSummariesPerModule( + StringMap> & + Module2FunctionInfoMap) const { + for (auto &GlobalList : *this) { + auto GUID = GlobalList.first; + for (auto &GlobInfo : GlobalList.second) { + auto *Summary = GlobInfo->summary(); + Module2FunctionInfoMap[Summary->modulePath()][GUID] = Summary; + } + } +} + GlobalValueInfo * ModuleSummaryIndex::getGlobalValueInfo(uint64_t ValueGUID, bool PerModuleIndex) const { Index: lib/LTO/ThinLTOCodeGenerator.cpp =================================================================== --- lib/LTO/ThinLTOCodeGenerator.cpp +++ lib/LTO/ThinLTOCodeGenerator.cpp @@ -30,6 +30,7 @@ #include "llvm/Linker/Linker.h" #include "llvm/MC/SubtargetFeature.h" #include "llvm/Object/ModuleSummaryIndexObjectFile.h" +#include "llvm/Support/Debug.h" #include "llvm/Support/SourceMgr.h" #include "llvm/Support/TargetRegistry.h" #include "llvm/Support/ThreadPool.h" @@ -42,6 +43,8 @@ using namespace llvm; +#define DEBUG_TYPE "thinlto" + namespace llvm { // Flags -discard-value-names, defined in LTOCodeGenerator.cpp extern cl::opt LTODiscardValueNames; @@ -119,24 +122,15 @@ return true; } -static void ResolveODR(GlobalValue &GV, const ModuleSummaryIndex &Index, - StringRef ModulePath) { - if (GV.isDeclaration()) - return; - +static GlobalValue::LinkageTypes ResolveODR(const ModuleSummaryIndex &Index, + StringRef ModuleIdentifier, + GlobalValue::GUID GUID, + const GlobalValueSummary &GV) { auto HasMultipleCopies = [&](const GlobalValueInfoList &GVInfo) { return GVInfo.size() > 1; }; - auto getGVInfo = [&](GlobalValue &GV) -> const GlobalValueInfoList *{ - auto GUID = Function::getGlobalIdentifier(GV.getName(), GV.getLinkage(), - ModulePath); - auto It = Index.findGlobalValueInfoList(GV.getName()); - if (It == Index.end()) - return nullptr; - return &It->second; - }; - - switch (GV.getLinkage()) { + auto OriginalLinkage = GV.linkage(); + switch (OriginalLinkage) { case GlobalValue::ExternalLinkage: case GlobalValue::AvailableExternallyLinkage: case GlobalValue::AppendingLinkage: @@ -149,20 +143,19 @@ break; case GlobalValue::LinkOnceODRLinkage: case GlobalValue::WeakODRLinkage: { - auto *GVInfo = getGVInfo(GV); - if (!GVInfo) - break; + auto &GVInfo = Index.findGlobalValueInfoList(GUID)->second; // We need to emit only one of these, the first module will keep // it, but turned into a weak while the others will drop it. - if (!HasMultipleCopies(*GVInfo)) + if (!HasMultipleCopies(GVInfo)) break; - if (IsFirstDefinitionForLinker(*GVInfo, Index, ModulePath)) - GV.setLinkage(GlobalValue::WeakODRLinkage); + if (IsFirstDefinitionForLinker(GVInfo, Index, ModuleIdentifier)) + return GlobalValue::WeakODRLinkage; else - GV.setLinkage(GlobalValue::AvailableExternallyLinkage); + return GlobalValue::AvailableExternallyLinkage; break; } } + return OriginalLinkage; } /// Resolve LinkOnceODR and WeakODR. @@ -171,8 +164,11 @@ /// current module. However there is a chance that another module is still /// referencing them because of the import. We make sure we always emit at least /// one copy. -static void ResolveODR(Module &TheModule, - const ModuleSummaryIndex &Index) { +static void ResolveODR( + const ModuleSummaryIndex &Index, + const std::map &DefinedGlobals, + StringRef ModuleIdentifier, + DenseMap &ResolvedODR) { if (Index.modulePaths().size() == 1) // Nothing to do if we don't have multiple modules return; @@ -180,20 +176,42 @@ // We won't optimize the globals that are referenced by an alias for now // Ideally we should turn the alias into a global and duplicate the definition // when needed. - DenseSet GlobalInvolvedWithAlias; - for (auto &GA : TheModule.aliases()) { - auto *GO = GA.getBaseObject(); - if (auto *GV = dyn_cast(GO)) - GlobalInvolvedWithAlias.insert(GV); + DenseSet GlobalInvolvedWithAlias; + for (auto &GA : DefinedGlobals) { + if (auto AS = dyn_cast(GA.second)) + GlobalInvolvedWithAlias.insert(&AS->getAliasee()); + } + + for (auto &GV : DefinedGlobals) { + if (GlobalInvolvedWithAlias.count(GV.second)) + continue; + auto NewLinkage = ResolveODR(Index, ModuleIdentifier, GV.first, *GV.second); + if (NewLinkage != GV.second->linkage()) { + ResolvedODR[GV.first] = NewLinkage; + } } +} + +/// Fixup linkage, see ResolveODR() above. +void fixupODR( + Module &TheModule, + const DenseMap &ResolvedODR) { // Process functions and global now for (auto &GV : TheModule) { - if (!GlobalInvolvedWithAlias.count(&GV)) - ResolveODR(GV, Index, TheModule.getModuleIdentifier()); + auto NewLinkage = ResolvedODR.find(GV.getGUID()); + if (NewLinkage == ResolvedODR.end()) + continue; + DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from " + << GV.getLinkage() << " to " << NewLinkage->second << "\n"); + GV.setLinkage(NewLinkage->second); } for (auto &GV : TheModule.globals()) { - if (!GlobalInvolvedWithAlias.count(&GV)) - ResolveODR(GV, Index, TheModule.getModuleIdentifier()); + auto NewLinkage = ResolvedODR.find(GV.getGUID()); + if (NewLinkage == ResolvedODR.end()) + continue; + DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from " + << GV.getLinkage() << " to " << NewLinkage->second << "\n"); + GV.setLinkage(NewLinkage->second); } } @@ -291,13 +309,13 @@ return make_unique(std::move(OutputBuffer)); } -static std::unique_ptr -ProcessThinLTOModule(Module &TheModule, const ModuleSummaryIndex &Index, - StringMap &ModuleMap, TargetMachine &TM, - const FunctionImporter::ImportMapTy &ImportList, - ThinLTOCodeGenerator::CachingOptions CacheOptions, - bool DisableCodeGen, StringRef SaveTempsDir, - unsigned count) { +static std::unique_ptr ProcessThinLTOModule( + Module &TheModule, const ModuleSummaryIndex &Index, + StringMap &ModuleMap, TargetMachine &TM, + const FunctionImporter::ImportMapTy &ImportList, + DenseMap &ResolvedODR, + ThinLTOCodeGenerator::CachingOptions CacheOptions, bool DisableCodeGen, + StringRef SaveTempsDir, unsigned count) { // Save temps: after IPO. saveTempBitcode(TheModule, SaveTempsDir, count, ".1.IPO.bc"); @@ -311,7 +329,7 @@ // Resolve the LinkOnce/Weak ODR, trying to turn them into // "available_externally" when possible. // This is a compile-time optimization. - ResolveODR(TheModule, Index); + fixupODR(TheModule, ResolvedODR); // Save temps: after promotion. saveTempBitcode(TheModule, SaveTempsDir, count, ".2.promoted.bc"); @@ -435,10 +453,19 @@ */ void ThinLTOCodeGenerator::promote(Module &TheModule, ModuleSummaryIndex &Index) { + auto ModuleIdentifier = TheModule.getModuleIdentifier(); + // Collect for each module the list of function it defines (GUID -> Summary). + StringMap> + ModuleToDefinedGVSummaries; + Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries); // Resolve the LinkOnceODR, trying to turn them into "available_externally" // where possible. - ResolveODR(TheModule, Index); + // This is a compile-time optimization. + DenseMap ResolvedODR; + ResolveODR(Index, ModuleToDefinedGVSummaries[ModuleIdentifier], + ModuleIdentifier, ResolvedODR); + fixupODR(TheModule, ResolvedODR); promoteModule(TheModule, Index); } @@ -449,12 +476,18 @@ void ThinLTOCodeGenerator::crossModuleImport(Module &TheModule, ModuleSummaryIndex &Index) { auto ModuleMap = generateModuleMap(Modules); + auto ModuleCount = Index.modulePaths().size(); + + // Collect for each module the list of function it defines (GUID -> Summary). + StringMap> + ModuleToDefinedGVSummaries(ModuleCount); + Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries); // Generate import/export list - auto ModuleCount = Index.modulePaths().size(); StringMap ImportLists(ModuleCount); StringMap ExportLists(ModuleCount); - ComputeCrossModuleImport(Index, ImportLists, ExportLists); + ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists, + ExportLists); auto &ImportList = ImportLists[TheModule.getModuleIdentifier()]; crossImportIntoModule(TheModule, Index, ModuleMap, ImportList); @@ -522,11 +555,17 @@ auto ModuleMap = generateModuleMap(Modules); auto ModuleCount = Modules.size(); + // Collect for each module the list of function it defines (GUID -> Summary). + StringMap> + ModuleToDefinedGVSummaries(ModuleCount); + Index->collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries); + // Collect the import/export lists for all modules from the call-graph in the // combined index. StringMap ImportLists(ModuleCount); StringMap ExportLists(ModuleCount); - ComputeCrossModuleImport(*Index, ImportLists, ExportLists); + ComputeCrossModuleImport(*Index, ModuleToDefinedGVSummaries, ImportLists, + ExportLists); // Parallel optimizer + codegen { @@ -536,6 +575,11 @@ Pool.async([&](int count) { LLVMContext Context; Context.setDiscardValueNames(LTODiscardValueNames); + auto ModuleIdentifier = ModuleBuffer.getBufferIdentifier(); + + DenseMap ResolvedODR; + ResolveODR(*Index, ModuleToDefinedGVSummaries[ModuleIdentifier], + ModuleIdentifier, ResolvedODR); // Parse module now auto TheModule = loadModuleFromBuffer(ModuleBuffer, Context, false); @@ -545,10 +589,10 @@ saveTempBitcode(*TheModule, SaveTempsDir, count, ".0.original.bc"); } - auto &ImportList = ImportLists[TheModule->getModuleIdentifier()]; + auto &ImportList = ImportLists[ModuleIdentifier]; ProducedBinaries[count] = ProcessThinLTOModule( *TheModule, *Index, ModuleMap, *TMBuilder.create(), ImportList, - CacheOptions, DisableCodeGen, SaveTempsDir, count); + ResolvedODR, CacheOptions, DisableCodeGen, SaveTempsDir, count); }, count); count++; } Index: lib/Transforms/IPO/FunctionImport.cpp =================================================================== --- lib/Transforms/IPO/FunctionImport.cpp +++ lib/Transforms/IPO/FunctionImport.cpp @@ -143,7 +143,7 @@ static void computeImportForFunction( const FunctionSummary &Summary, const ModuleSummaryIndex &Index, unsigned Threshold, - const std::map &DefinedFunctions, + const std::map &DefinedGVSummaries, SmallVectorImpl &Worklist, FunctionImporter::ImportMapTy &ImportsForModule, StringMap *ExportLists = nullptr) { @@ -151,7 +151,7 @@ auto GUID = Edge.first.getGUID(); DEBUG(dbgs() << " edge -> " << GUID << " Threshold:" << Threshold << "\n"); - if (DefinedFunctions.count(GUID)) { + if (DefinedGVSummaries.count(GUID)) { DEBUG(dbgs() << "ignored! Target already in destination module.\n"); continue; } @@ -212,7 +212,7 @@ /// as well as the list of "exports", i.e. the list of symbols referenced from /// another module (that may require promotion). static void ComputeImportForModule( - const std::map &DefinedFunctions, + const std::map &DefinedGVSummaries, const ModuleSummaryIndex &Index, FunctionImporter::ImportMapTy &ImportsForModule, StringMap *ExportLists = nullptr) { @@ -222,14 +222,17 @@ // Populate the worklist with the import for the functions in the current // module - for (auto &FuncInfo : DefinedFunctions) { - auto *Summary = FuncInfo.second; + for (auto &GVInfo : DefinedGVSummaries) { + auto *Summary = GVInfo.second; if (auto *AS = dyn_cast(Summary)) Summary = &AS->getAliasee(); - auto *FuncSummary = cast(Summary); - DEBUG(dbgs() << "Initalize import for " << FuncInfo.first << "\n"); + auto *FuncSummary = dyn_cast(Summary); + if (!FuncSummary) + // Skip import for global variables + continue; + DEBUG(dbgs() << "Initalize import for " << GVInfo.first << "\n"); computeImportForFunction(*FuncSummary, Index, ImportInstrLimit, - DefinedFunctions, Worklist, ImportsForModule, + DefinedGVSummaries, Worklist, ImportsForModule, ExportLists); } @@ -242,7 +245,7 @@ // Adjust the threshold Threshold = Threshold * ImportInstrFactor; - computeImportForFunction(*Summary, Index, Threshold, DefinedFunctions, + computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries, Worklist, ImportsForModule, ExportLists); } } @@ -252,38 +255,16 @@ /// Compute all the import and export for every module using the Index. void llvm::ComputeCrossModuleImport( const ModuleSummaryIndex &Index, + const StringMap> & + ModuleToDefinedGVSummaries, StringMap &ImportLists, StringMap &ExportLists) { - auto ModuleCount = Index.modulePaths().size(); - - // Collect for each module the list of function it defines. - // GUID -> Summary - StringMap> - Module2FunctionInfoMap(ModuleCount); - - for (auto &GlobalList : Index) { - auto GUID = GlobalList.first; - for (auto &GlobInfo : GlobalList.second) { - auto *Summary = GlobInfo->summary(); - if (isa(Summary)) - /// Ignore global variable, focus on functions - continue; - if (auto *AS = dyn_cast(Summary)) - if (isa(&AS->getAliasee())) - /// Ignore alias to global variable, focus on functions - continue; - DEBUG(dbgs() << "Adding definition: Module '" << Summary->modulePath() - << "' defines '" << GUID << "'\n"); - Module2FunctionInfoMap[Summary->modulePath()][GUID] = Summary; - } - } - // For each module that has function defined, compute the import/export lists. - for (auto &DefinedFunctions : Module2FunctionInfoMap) { - auto &ImportsForModule = ImportLists[DefinedFunctions.first()]; - DEBUG(dbgs() << "Computing import for Module '" << DefinedFunctions.first() - << "'\n"); - ComputeImportForModule(DefinedFunctions.second, Index, ImportsForModule, + for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) { + auto &ImportsForModule = ImportLists[DefinedGVSummaries.first()]; + DEBUG(dbgs() << "Computing import for Module '" + << DefinedGVSummaries.first() << "'\n"); + ComputeImportForModule(DefinedGVSummaries.second, Index, ImportsForModule, &ExportLists); }