1 //===- llvm/Transforms/IPO/FunctionImport.h - ThinLTO importing -*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H 10 #define LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H 11 12 #include "llvm/ADT/DenseSet.h" 13 #include "llvm/ADT/StringMap.h" 14 #include "llvm/ADT/StringRef.h" 15 #include "llvm/IR/GlobalValue.h" 16 #include "llvm/IR/ModuleSummaryIndex.h" 17 #include "llvm/IR/PassManager.h" 18 #include "llvm/Support/Error.h" 19 #include <functional> 20 #include <map> 21 #include <memory> 22 #include <string> 23 #include <system_error> 24 #include <unordered_set> 25 #include <utility> 26 27 namespace llvm { 28 29 class Module; 30 31 /// The function importer is automatically importing function from other modules 32 /// based on the provided summary informations. 33 class FunctionImporter { 34 public: 35 /// Set of functions to import from a source module. Each entry is a set 36 /// containing all the GUIDs of all functions to import for a source module. 37 using FunctionsToImportTy = std::unordered_set<GlobalValue::GUID>; 38 39 /// The different reasons selectCallee will chose not to import a 40 /// candidate. 41 enum ImportFailureReason { 42 None, 43 // We can encounter a global variable instead of a function in rare 44 // situations with SamplePGO. See comments where this failure type is 45 // set for more details. 46 GlobalVar, 47 // Found to be globally dead, so we don't bother importing. 48 NotLive, 49 // Instruction count over the current threshold. 50 TooLarge, 51 // Don't import something with interposable linkage as we can't inline it 52 // anyway. 53 InterposableLinkage, 54 // Generally we won't end up failing due to this reason, as we expect 55 // to find at least one summary for the GUID that is global or a local 56 // in the referenced module for direct calls. 57 LocalLinkageNotInModule, 58 // This corresponds to the NotEligibleToImport being set on the summary, 59 // which can happen in a few different cases (e.g. local that can't be 60 // renamed or promoted because it is referenced on a llvm*.used variable). 61 NotEligible, 62 // This corresponds to NoInline being set on the function summary, 63 // which will happen if it is known that the inliner will not be able 64 // to inline the function (e.g. it is marked with a NoInline attribute). 65 NoInline 66 }; 67 68 /// Information optionally tracked for candidates the importer decided 69 /// not to import. Used for optional stat printing. 70 struct ImportFailureInfo { 71 // The ValueInfo corresponding to the candidate. We save an index hash 72 // table lookup for each GUID by stashing this here. 73 ValueInfo VI; 74 // The maximum call edge hotness for all failed imports of this candidate. 75 CalleeInfo::HotnessType MaxHotness; 76 // most recent reason for failing to import (doesn't necessarily correspond 77 // to the attempt with the maximum hotness). 78 ImportFailureReason Reason; 79 // The number of times we tried to import candidate but failed. 80 unsigned Attempts; 81 ImportFailureInfo(ValueInfo VI, CalleeInfo::HotnessType MaxHotness, 82 ImportFailureReason Reason, unsigned Attempts) 83 : VI(VI), MaxHotness(MaxHotness), Reason(Reason), Attempts(Attempts) {} 84 }; 85 86 /// Map of callee GUID considered for import into a given module to a pair 87 /// consisting of the largest threshold applied when deciding whether to 88 /// import it and, if we decided to import, a pointer to the summary instance 89 /// imported. If we decided not to import, the summary will be nullptr. 90 using ImportThresholdsTy = 91 DenseMap<GlobalValue::GUID, 92 std::tuple<unsigned, const GlobalValueSummary *, 93 std::unique_ptr<ImportFailureInfo>>>; 94 95 /// The map contains an entry for every module to import from, the key being 96 /// the module identifier to pass to the ModuleLoader. The value is the set of 97 /// functions to import. 98 using ImportMapTy = StringMap<FunctionsToImportTy>; 99 100 /// The set contains an entry for every global value the module exports. 101 using ExportSetTy = DenseSet<ValueInfo>; 102 103 /// A function of this type is used to load modules referenced by the index. 104 using ModuleLoaderTy = 105 std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)>; 106 107 /// Create a Function Importer. 108 FunctionImporter(const ModuleSummaryIndex &Index, ModuleLoaderTy ModuleLoader, 109 bool ClearDSOLocalOnDeclarations) 110 : Index(Index), ModuleLoader(std::move(ModuleLoader)), 111 ClearDSOLocalOnDeclarations(ClearDSOLocalOnDeclarations) {} 112 113 /// Import functions in Module \p M based on the supplied import list. 114 Expected<bool> importFunctions(Module &M, const ImportMapTy &ImportList); 115 116 private: 117 /// The summaries index used to trigger importing. 118 const ModuleSummaryIndex &Index; 119 120 /// Factory function to load a Module for a given identifier 121 ModuleLoaderTy ModuleLoader; 122 123 /// See the comment of ClearDSOLocalOnDeclarations in 124 /// Utils/FunctionImportUtils.h. 125 bool ClearDSOLocalOnDeclarations; 126 }; 127 128 /// The function importing pass 129 class FunctionImportPass : public PassInfoMixin<FunctionImportPass> { 130 public: 131 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 132 }; 133 134 /// Compute all the imports and exports for every module in the Index. 135 /// 136 /// \p ModuleToDefinedGVSummaries contains for each Module a map 137 /// (GUID -> Summary) for every global defined in the module. 138 /// 139 /// \p ImportLists will be populated with an entry for every Module we are 140 /// importing into. This entry is itself a map that can be passed to 141 /// FunctionImporter::importFunctions() above (see description there). 142 /// 143 /// \p ExportLists contains for each Module the set of globals (GUID) that will 144 /// be imported by another module, or referenced by such a function. I.e. this 145 /// is the set of globals that need to be promoted/renamed appropriately. 146 void ComputeCrossModuleImport( 147 const ModuleSummaryIndex &Index, 148 const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries, 149 StringMap<FunctionImporter::ImportMapTy> &ImportLists, 150 StringMap<FunctionImporter::ExportSetTy> &ExportLists); 151 152 /// Compute all the imports for the given module using the Index. 153 /// 154 /// \p ImportList will be populated with a map that can be passed to 155 /// FunctionImporter::importFunctions() above (see description there). 156 void ComputeCrossModuleImportForModule( 157 StringRef ModulePath, const ModuleSummaryIndex &Index, 158 FunctionImporter::ImportMapTy &ImportList); 159 160 /// Mark all external summaries in \p Index for import into the given module. 161 /// Used for distributed builds using a distributed index. 162 /// 163 /// \p ImportList will be populated with a map that can be passed to 164 /// FunctionImporter::importFunctions() above (see description there). 165 void ComputeCrossModuleImportForModuleFromIndex( 166 StringRef ModulePath, const ModuleSummaryIndex &Index, 167 FunctionImporter::ImportMapTy &ImportList); 168 169 /// PrevailingType enum used as a return type of callback passed 170 /// to computeDeadSymbols. Yes and No values used when status explicitly 171 /// set by symbols resolution, otherwise status is Unknown. 172 enum class PrevailingType { Yes, No, Unknown }; 173 174 /// Compute all the symbols that are "dead": i.e these that can't be reached 175 /// in the graph from any of the given symbols listed in 176 /// \p GUIDPreservedSymbols. Non-prevailing symbols are symbols without a 177 /// prevailing copy anywhere in IR and are normally dead, \p isPrevailing 178 /// predicate returns status of symbol. 179 void computeDeadSymbols( 180 ModuleSummaryIndex &Index, 181 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols, 182 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing); 183 184 /// Compute dead symbols and run constant propagation in combined index 185 /// after that. 186 void computeDeadSymbolsWithConstProp( 187 ModuleSummaryIndex &Index, 188 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols, 189 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing, 190 bool ImportEnabled); 191 192 /// Converts value \p GV to declaration, or replaces with a declaration if 193 /// it is an alias. Returns true if converted, false if replaced. 194 bool convertToDeclaration(GlobalValue &GV); 195 196 /// Compute the set of summaries needed for a ThinLTO backend compilation of 197 /// \p ModulePath. 198 // 199 /// This includes summaries from that module (in case any global summary based 200 /// optimizations were recorded) and from any definitions in other modules that 201 /// should be imported. 202 // 203 /// \p ModuleToSummariesForIndex will be populated with the needed summaries 204 /// from each required module path. Use a std::map instead of StringMap to get 205 /// stable order for bitcode emission. 206 void gatherImportedSummariesForModule( 207 StringRef ModulePath, 208 const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries, 209 const FunctionImporter::ImportMapTy &ImportList, 210 std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex); 211 212 /// Emit into \p OutputFilename the files module \p ModulePath will import from. 213 std::error_code EmitImportsFiles( 214 StringRef ModulePath, StringRef OutputFilename, 215 const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex); 216 217 /// Resolve prevailing symbol linkages and constrain visibility (1. CanAutoHide, 218 /// 2. consider visibility from other definitions for ELF) in \p TheModule based 219 /// on the information recorded in the summaries during global summary-based 220 /// analysis. 221 void thinLTOResolvePrevailingInModule(Module &TheModule, 222 const GVSummaryMapTy &DefinedGlobals); 223 224 /// Internalize \p TheModule based on the information recorded in the summaries 225 /// during global summary-based analysis. 226 void thinLTOInternalizeModule(Module &TheModule, 227 const GVSummaryMapTy &DefinedGlobals); 228 229 } // end namespace llvm 230 231 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H 232