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