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