LLVM  13.0.0git
FunctionImport.h
Go to the documentation of this file.
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"
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.
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.
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.
47  // Found to be globally dead, so we don't bother importing.
49  // Instruction count over the current threshold.
51  // Don't import something with interposable linkage as we can't inline it
52  // anyway.
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.
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).
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).
66  };
67 
68  /// Information optionally tracked for candidates the importer decided
69  /// not to import. Used for optional stat printing.
71  // The ValueInfo corresponding to the candidate. We save an index hash
72  // table lookup for each GUID by stashing this here.
74  // The maximum call edge hotness for all failed imports of this candidate.
76  // most recent reason for failing to import (doesn't necessarily correspond
77  // to the attempt with the maximum hotness).
79  // The number of times we tried to import candidate but failed.
80  unsigned 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 =
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.
99 
100  /// The set contains an entry for every global value the module exports.
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.
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:
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.
147  const ModuleSummaryIndex &Index,
148  const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
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).
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).
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.
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.
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.
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
llvm::FunctionImporter::None
@ None
Definition: FunctionImport.h:42
llvm::GlobalValue::GUID
uint64_t GUID
Declare a type to represent a global unique identifier for a global value.
Definition: GlobalValue.h:503
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::FunctionImporter::FunctionsToImportTy
std::unordered_set< GlobalValue::GUID > FunctionsToImportTy
Set of functions to import from a source module.
Definition: FunctionImport.h:37
llvm::FunctionImporter::FunctionImporter
FunctionImporter(const ModuleSummaryIndex &Index, ModuleLoaderTy ModuleLoader, bool ClearDSOLocalOnDeclarations)
Create a Function Importer.
Definition: FunctionImport.h:108
llvm
Definition: AllocatorList.h:23
llvm::FunctionImporter::ImportThresholdsTy
DenseMap< GlobalValue::GUID, std::tuple< unsigned, const GlobalValueSummary *, std::unique_ptr< ImportFailureInfo > >> ImportThresholdsTy
Map of callee GUID considered for import into a given module to a pair consisting of the largest thre...
Definition: FunctionImport.h:93
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::thinLTOInternalizeModule
void thinLTOInternalizeModule(Module &TheModule, const GVSummaryMapTy &DefinedGlobals)
Internalize TheModule based on the information recorded in the summaries during global summary-based ...
Definition: FunctionImport.cpp:1116
llvm::FunctionImporter::InterposableLinkage
@ InterposableLinkage
Definition: FunctionImport.h:53
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
StringRef.h
Error.h
llvm::FunctionImporter::LocalLinkageNotInModule
@ LocalLinkageNotInModule
Definition: FunctionImport.h:57
llvm::FunctionImporter
The function importer is automatically importing function from other modules based on the provided su...
Definition: FunctionImport.h:33
llvm::Expected
Tagged union holding either a T or a Error.
Definition: APFloat.h:42
llvm::FunctionImporter::ImportFailureInfo
Information optionally tracked for candidates the importer decided not to import.
Definition: FunctionImport.h:70
llvm::gatherImportedSummariesForModule
void gatherImportedSummariesForModule(StringRef ModulePath, const StringMap< GVSummaryMapTy > &ModuleToDefinedGVSummaries, const FunctionImporter::ImportMapTy &ImportList, std::map< std::string, GVSummaryMapTy > &ModuleToSummariesForIndex)
Compute the set of summaries needed for a ThinLTO backend compilation of ModulePath.
Definition: FunctionImport.cpp:968
llvm::EmitImportsFiles
std::error_code EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename, const std::map< std::string, GVSummaryMapTy > &ModuleToSummariesForIndex)
Emit into OutputFilename the files module ModulePath will import from.
Definition: FunctionImport.cpp:992
ModuleSummaryIndex.h
llvm::FunctionImporter::importFunctions
Expected< bool > importFunctions(Module &M, const ImportMapTy &ImportList)
Import functions in Module M based on the supplied import list.
Definition: FunctionImport.cpp:1183
llvm::GlobalValueSummary
Function and variable summary information to aid decisions and implementation of importing.
Definition: ModuleSummaryIndex.h:288
GlobalValue.h
llvm::FunctionImporter::NotLive
@ NotLive
Definition: FunctionImport.h:48
llvm::PrevailingType
PrevailingType
PrevailingType enum used as a return type of callback passed to computeDeadSymbols.
Definition: FunctionImport.h:172
llvm::FunctionImporter::NotEligible
@ NotEligible
Definition: FunctionImport.h:61
DenseSet.h
llvm::CalleeInfo::HotnessType
HotnessType
Definition: ModuleSummaryIndex.h:56
llvm::ComputeCrossModuleImportForModule
void ComputeCrossModuleImportForModule(StringRef ModulePath, const ModuleSummaryIndex &Index, FunctionImporter::ImportMapTy &ImportList)
Compute all the imports for the given module using the Index.
Definition: FunctionImport.cpp:799
StringMap.h
llvm::FunctionImporter::ImportFailureInfo::Reason
ImportFailureReason Reason
Definition: FunctionImport.h:78
llvm::FunctionImporter::GlobalVar
@ GlobalVar
Definition: FunctionImport.h:46
llvm::StringMap
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:108
llvm::ValueInfo
Struct that holds a reference to a particular GUID in a global value summary.
Definition: ModuleSummaryIndex.h:166
llvm::convertToDeclaration
bool convertToDeclaration(GlobalValue &GV)
Converts value GV to declaration, or replaces with a declaration if it is an alias.
Definition: FunctionImport.cpp:1008
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::FunctionImporter::ImportFailureInfo::MaxHotness
CalleeInfo::HotnessType MaxHotness
Definition: FunctionImport.h:75
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::computeDeadSymbolsWithConstProp
void computeDeadSymbolsWithConstProp(ModuleSummaryIndex &Index, const DenseSet< GlobalValue::GUID > &GUIDPreservedSymbols, function_ref< PrevailingType(GlobalValue::GUID)> isPrevailing, bool ImportEnabled)
Compute dead symbols and run constant propagation in combined index after that.
Definition: FunctionImport.cpp:956
llvm::DenseMap
Definition: DenseMap.h:714
llvm::FunctionImporter::NoInline
@ NoInline
Definition: FunctionImport.h:65
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1540
llvm::FunctionImporter::TooLarge
@ TooLarge
Definition: FunctionImport.h:50
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::PrevailingType::Unknown
@ Unknown
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::GVSummaryMapTy
DenseMap< GlobalValue::GUID, GlobalValueSummary * > GVSummaryMapTy
Map of global value GUID to its summary, used to identify values defined in a particular module,...
Definition: ModuleSummaryIndex.h:994
llvm::FunctionImporter::ImportMapTy
StringMap< FunctionsToImportTy > ImportMapTy
The map contains an entry for every module to import from, the key being the module identifier to pas...
Definition: FunctionImport.h:98
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::FunctionImporter::ImportFailureInfo::VI
ValueInfo VI
Definition: FunctionImport.h:73
llvm::thinLTOResolvePrevailingInModule
void thinLTOResolvePrevailingInModule(Module &TheModule, const GVSummaryMapTy &DefinedGlobals)
Resolve prevailing symbol linkages and constrain visibility (1.
Definition: FunctionImport.cpp:1043
llvm::FunctionImporter::ImportFailureInfo::Attempts
unsigned Attempts
Definition: FunctionImport.h:80
llvm::ComputeCrossModuleImportForModuleFromIndex
void ComputeCrossModuleImportForModuleFromIndex(StringRef ModulePath, const ModuleSummaryIndex &Index, FunctionImporter::ImportMapTy &ImportList)
Mark all external summaries in Index for import into the given module.
Definition: FunctionImport.cpp:818
std
Definition: BitVector.h:838
llvm::FunctionImporter::ImportFailureReason
ImportFailureReason
The different reasons selectCallee will chose not to import a candidate.
Definition: FunctionImport.h:41
llvm::FunctionImporter::ImportFailureInfo::ImportFailureInfo
ImportFailureInfo(ValueInfo VI, CalleeInfo::HotnessType MaxHotness, ImportFailureReason Reason, unsigned Attempts)
Definition: FunctionImport.h:81
llvm::computeDeadSymbols
void computeDeadSymbols(ModuleSummaryIndex &Index, const DenseSet< GlobalValue::GUID > &GUIDPreservedSymbols, function_ref< PrevailingType(GlobalValue::GUID)> isPrevailing)
Compute all the symbols that are "dead": i.e these that can't be reached in the graph from any of the...
Definition: FunctionImport.cpp:842
PassManager.h
llvm::PrevailingType::Yes
@ Yes
llvm::PrevailingType::No
@ No
llvm::FunctionImportPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: FunctionImport.cpp:1411
OutputFilename
static cl::opt< std::string > OutputFilename("o", cl::desc("Output filename"), cl::value_desc("filename"), cl::init("-"))
llvm::ModuleSummaryIndex
Class to hold module path string table and global value map, and encapsulate methods for operating on...
Definition: ModuleSummaryIndex.h:1026
llvm::FunctionImporter::ModuleLoaderTy
std::function< Expected< std::unique_ptr< Module > >(StringRef Identifier)> ModuleLoaderTy
A function of this type is used to load modules referenced by the index.
Definition: FunctionImport.h:105
llvm::ComputeCrossModuleImport
void ComputeCrossModuleImport(const ModuleSummaryIndex &Index, const StringMap< GVSummaryMapTy > &ModuleToDefinedGVSummaries, StringMap< FunctionImporter::ImportMapTy > &ImportLists, StringMap< FunctionImporter::ExportSetTy > &ExportLists)
Compute all the imports and exports for every module in the Index.
Definition: FunctionImport.cpp:691
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionImportPass
The function importing pass.
Definition: FunctionImport.h:129