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/StringRef.h" 14 #include "llvm/IR/GlobalValue.h" 15 #include "llvm/IR/ModuleSummaryIndex.h" 16 #include "llvm/IR/PassManager.h" 17 #include "llvm/Support/Error.h" 18 #include <functional> 19 #include <map> 20 #include <memory> 21 #include <string> 22 #include <system_error> 23 #include <unordered_map> 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 /// The functions to import from a source module and their import type. 36 /// Note we choose unordered_map over (Small)DenseMap. The number of imports 37 /// from a source module could be small but DenseMap size grows to 64 quickly 38 /// and not memory efficient (see 39 /// https://llvm.org/docs/ProgrammersManual.html#llvm-adt-densemap-h) 40 using FunctionsToImportTy = 41 std::unordered_map<GlobalValue::GUID, GlobalValueSummary::ImportKind>; 42 43 /// The different reasons selectCallee will chose not to import a 44 /// candidate. 45 enum ImportFailureReason { 46 None, 47 // We can encounter a global variable instead of a function in rare 48 // situations with SamplePGO. See comments where this failure type is 49 // set for more details. 50 GlobalVar, 51 // Found to be globally dead, so we don't bother importing. 52 NotLive, 53 // Instruction count over the current threshold. 54 TooLarge, 55 // Don't import something with interposable linkage as we can't inline it 56 // anyway. 57 InterposableLinkage, 58 // Generally we won't end up failing due to this reason, as we expect 59 // to find at least one summary for the GUID that is global or a local 60 // in the referenced module for direct calls. 61 LocalLinkageNotInModule, 62 // This corresponds to the NotEligibleToImport being set on the summary, 63 // which can happen in a few different cases (e.g. local that can't be 64 // renamed or promoted because it is referenced on a llvm*.used variable). 65 NotEligible, 66 // This corresponds to NoInline being set on the function summary, 67 // which will happen if it is known that the inliner will not be able 68 // to inline the function (e.g. it is marked with a NoInline attribute). 69 NoInline 70 }; 71 72 /// Information optionally tracked for candidates the importer decided 73 /// not to import. Used for optional stat printing. 74 struct ImportFailureInfo { 75 // The ValueInfo corresponding to the candidate. We save an index hash 76 // table lookup for each GUID by stashing this here. 77 ValueInfo VI; 78 // The maximum call edge hotness for all failed imports of this candidate. 79 CalleeInfo::HotnessType MaxHotness; 80 // most recent reason for failing to import (doesn't necessarily correspond 81 // to the attempt with the maximum hotness). 82 ImportFailureReason Reason; 83 // The number of times we tried to import candidate but failed. 84 unsigned Attempts; ImportFailureInfoImportFailureInfo85 ImportFailureInfo(ValueInfo VI, CalleeInfo::HotnessType MaxHotness, 86 ImportFailureReason Reason, unsigned Attempts) 87 : VI(VI), MaxHotness(MaxHotness), Reason(Reason), Attempts(Attempts) {} 88 }; 89 90 /// Map of callee GUID considered for import into a given module to a pair 91 /// consisting of the largest threshold applied when deciding whether to 92 /// import it and, if we decided to import, a pointer to the summary instance 93 /// imported. If we decided not to import, the summary will be nullptr. 94 using ImportThresholdsTy = 95 DenseMap<GlobalValue::GUID, 96 std::tuple<unsigned, const GlobalValueSummary *, 97 std::unique_ptr<ImportFailureInfo>>>; 98 99 /// The map contains an entry for every module to import from, the key being 100 /// the module identifier to pass to the ModuleLoader. The value is the set of 101 /// functions to import. The module identifier strings must be owned 102 /// elsewhere, typically by the in-memory ModuleSummaryIndex the importing 103 /// decisions are made from (the module path for each summary is owned by the 104 /// index's module path string table). 105 using ImportMapTy = DenseMap<StringRef, FunctionsToImportTy>; 106 107 /// The set contains an entry for every global value that the module exports. 108 /// Depending on the user context, this container is allowed to contain 109 /// definitions, declarations or a mix of both. 110 using ExportSetTy = DenseSet<ValueInfo>; 111 112 /// A function of this type is used to load modules referenced by the index. 113 using ModuleLoaderTy = 114 std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)>; 115 116 /// Create a Function Importer. FunctionImporter(const ModuleSummaryIndex & Index,ModuleLoaderTy ModuleLoader,bool ClearDSOLocalOnDeclarations)117 FunctionImporter(const ModuleSummaryIndex &Index, ModuleLoaderTy ModuleLoader, 118 bool ClearDSOLocalOnDeclarations) 119 : Index(Index), ModuleLoader(std::move(ModuleLoader)), 120 ClearDSOLocalOnDeclarations(ClearDSOLocalOnDeclarations) {} 121 122 /// Import functions in Module \p M based on the supplied import list. 123 Expected<bool> importFunctions(Module &M, const ImportMapTy &ImportList); 124 125 private: 126 /// The summaries index used to trigger importing. 127 const ModuleSummaryIndex &Index; 128 129 /// Factory function to load a Module for a given identifier 130 ModuleLoaderTy ModuleLoader; 131 132 /// See the comment of ClearDSOLocalOnDeclarations in 133 /// Utils/FunctionImportUtils.h. 134 bool ClearDSOLocalOnDeclarations; 135 }; 136 137 /// The function importing pass 138 class FunctionImportPass : public PassInfoMixin<FunctionImportPass> { 139 public: 140 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 141 }; 142 143 /// Compute all the imports and exports for every module in the Index. 144 /// 145 /// \p ModuleToDefinedGVSummaries contains for each Module a map 146 /// (GUID -> Summary) for every global defined in the module. 147 /// 148 /// \p isPrevailing is a callback that will be called with a global value's GUID 149 /// and summary and should return whether the module corresponding to the 150 /// summary contains the linker-prevailing copy of that value. 151 /// 152 /// \p ImportLists will be populated with an entry for every Module we are 153 /// importing into. This entry is itself a map that can be passed to 154 /// FunctionImporter::importFunctions() above (see description there). 155 /// 156 /// \p ExportLists contains for each Module the set of globals (GUID) that will 157 /// be imported by another module, or referenced by such a function. I.e. this 158 /// is the set of globals that need to be promoted/renamed appropriately. 159 /// 160 /// The module identifier strings that are the keys of the above two maps 161 /// are owned by the in-memory ModuleSummaryIndex the importing decisions 162 /// are made from (the module path for each summary is owned by the index's 163 /// module path string table). 164 void ComputeCrossModuleImport( 165 const ModuleSummaryIndex &Index, 166 const DenseMap<StringRef, GVSummaryMapTy> &ModuleToDefinedGVSummaries, 167 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)> 168 isPrevailing, 169 DenseMap<StringRef, FunctionImporter::ImportMapTy> &ImportLists, 170 DenseMap<StringRef, FunctionImporter::ExportSetTy> &ExportLists); 171 172 /// PrevailingType enum used as a return type of callback passed 173 /// to computeDeadSymbolsAndUpdateIndirectCalls. Yes and No values used when 174 /// status explicitly set by symbols resolution, otherwise status is Unknown. 175 enum class PrevailingType { Yes, No, Unknown }; 176 177 /// Update call edges for indirect calls to local functions added from 178 /// SamplePGO when needed. Normally this is done during 179 /// computeDeadSymbolsAndUpdateIndirectCalls, but can be called standalone 180 /// when that is not called (e.g. during testing). 181 void updateIndirectCalls(ModuleSummaryIndex &Index); 182 183 /// Compute all the symbols that are "dead": i.e these that can't be reached 184 /// in the graph from any of the given symbols listed in 185 /// \p GUIDPreservedSymbols. Non-prevailing symbols are symbols without a 186 /// prevailing copy anywhere in IR and are normally dead, \p isPrevailing 187 /// predicate returns status of symbol. 188 /// Also update call edges for indirect calls to local functions added from 189 /// SamplePGO when needed. 190 void computeDeadSymbolsAndUpdateIndirectCalls( 191 ModuleSummaryIndex &Index, 192 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols, 193 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing); 194 195 /// Compute dead symbols and run constant propagation in combined index 196 /// after that. 197 void computeDeadSymbolsWithConstProp( 198 ModuleSummaryIndex &Index, 199 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols, 200 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing, 201 bool ImportEnabled); 202 203 /// Converts value \p GV to declaration, or replaces with a declaration if 204 /// it is an alias. Returns true if converted, false if replaced. 205 bool convertToDeclaration(GlobalValue &GV); 206 207 /// Compute the set of summaries needed for a ThinLTO backend compilation of 208 /// \p ModulePath. 209 // 210 /// This includes summaries from that module (in case any global summary based 211 /// optimizations were recorded) and from any definitions in other modules that 212 /// should be imported. 213 // 214 /// \p ModuleToSummariesForIndex will be populated with the needed summaries 215 /// from each required module path. Use a std::map instead of StringMap to get 216 /// stable order for bitcode emission. 217 /// 218 /// \p DecSummaries will be popluated with the subset of of summary pointers 219 /// that have 'declaration' import type among all summaries the module need. 220 void gatherImportedSummariesForModule( 221 StringRef ModulePath, 222 const DenseMap<StringRef, GVSummaryMapTy> &ModuleToDefinedGVSummaries, 223 const FunctionImporter::ImportMapTy &ImportList, 224 std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex, 225 GVSummaryPtrSet &DecSummaries); 226 227 /// Emit into \p OutputFilename the files module \p ModulePath will import from. 228 std::error_code EmitImportsFiles( 229 StringRef ModulePath, StringRef OutputFilename, 230 const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex); 231 232 /// Based on the information recorded in the summaries during global 233 /// summary-based analysis: 234 /// 1. Resolve prevailing symbol linkages and constrain visibility (CanAutoHide 235 /// and consider visibility from other definitions for ELF) in \p TheModule 236 /// 2. (optional) Apply propagated function attributes to \p TheModule if 237 /// PropagateAttrs is true 238 void thinLTOFinalizeInModule(Module &TheModule, 239 const GVSummaryMapTy &DefinedGlobals, 240 bool PropagateAttrs); 241 242 /// Internalize \p TheModule based on the information recorded in the summaries 243 /// during global summary-based analysis. 244 void thinLTOInternalizeModule(Module &TheModule, 245 const GVSummaryMapTy &DefinedGlobals); 246 247 } // end namespace llvm 248 249 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H 250