LLVM 20.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/MapVector.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 <memory>
21#include <system_error>
22#include <utility>
23
24namespace llvm {
25
26class Module;
27
28/// The function importer is automatically importing function from other modules
29/// based on the provided summary informations.
31public:
32 /// The different reasons selectCallee will chose not to import a
33 /// candidate.
35 None,
36 // We can encounter a global variable instead of a function in rare
37 // situations with SamplePGO. See comments where this failure type is
38 // set for more details.
40 // Found to be globally dead, so we don't bother importing.
41 NotLive,
42 // Instruction count over the current threshold.
44 // Don't import something with interposable linkage as we can't inline it
45 // anyway.
47 // Generally we won't end up failing due to this reason, as we expect
48 // to find at least one summary for the GUID that is global or a local
49 // in the referenced module for direct calls.
51 // This corresponds to the NotEligibleToImport being set on the summary,
52 // which can happen in a few different cases (e.g. local that can't be
53 // renamed or promoted because it is referenced on a llvm*.used variable).
55 // This corresponds to NoInline being set on the function summary,
56 // which will happen if it is known that the inliner will not be able
57 // to inline the function (e.g. it is marked with a NoInline attribute).
59 };
60
61 /// Information optionally tracked for candidates the importer decided
62 /// not to import. Used for optional stat printing.
64 // The ValueInfo corresponding to the candidate. We save an index hash
65 // table lookup for each GUID by stashing this here.
67 // The maximum call edge hotness for all failed imports of this candidate.
69 // most recent reason for failing to import (doesn't necessarily correspond
70 // to the attempt with the maximum hotness).
72 // The number of times we tried to import candidate but failed.
73 unsigned Attempts;
77 };
78
79 /// Map of callee GUID considered for import into a given module to a pair
80 /// consisting of the largest threshold applied when deciding whether to
81 /// import it and, if we decided to import, a pointer to the summary instance
82 /// imported. If we decided not to import, the summary will be nullptr.
85 std::tuple<unsigned, const GlobalValueSummary *,
86 std::unique_ptr<ImportFailureInfo>>>;
87
88 // Issues import IDs. Each ID uniquely corresponds to a tuple of
89 // (FromModule, GUID, Definition/Declaration).
90 //
91 // The import IDs make the import list space efficient by referring to each
92 // import with a 32-bit integer ID while maintaining a central table that maps
93 // those integer IDs to tuples of (FromModule, GUID, Def/Decl).
94 //
95 // In one large application, a pair of (FromModule, GUID) is mentioned in
96 // import lists more than 50 times on average across all destination modules.
97 // Mentioning the 32-byte tuple:
98 //
99 // std::tuple<StringRef, GlobalValue::GUID, GlobalValueSummary::ImportKind>
100 //
101 // 50 times by value in various import lists would be costly. We can reduce
102 // the memory footprint of import lists by placing one copy in a central table
103 // and referring to it with 32-bit integer IDs.
104 //
105 // To save space within the central table, we only store pairs of
106 // (FromModule, GUID) in the central table. In the actual 32-bit integer ID,
107 // the top 31 bits index into the central table while the bottom 1 bit
108 // indicates whether an ID is for GlobalValueSummary::Declaration or
109 // GlobalValueSummary::Definition.
111 public:
113
114 ImportIDTable() = default;
115
116 // Something is wrong with the application logic if we need to make a copy
117 // of this and potentially make a fork.
118 ImportIDTable(const ImportIDTable &) = delete;
120
121 // Create a pair of import IDs [Def, Decl] for a given pair of FromModule
122 // and GUID.
123 std::pair<ImportIDTy, ImportIDTy> createImportIDs(StringRef FromModule,
124 GlobalValue::GUID GUID) {
125 auto Key = std::make_pair(FromModule, GUID);
126 auto InsertResult = TheTable.try_emplace(Key, TheTable.size());
127 return makeIDPair(InsertResult.first->second);
128 }
129
130 // Get a pair of previously created import IDs [Def, Decl] for a given pair
131 // of FromModule and GUID. Returns std::nullopt if not available.
132 std::optional<std::pair<ImportIDTy, ImportIDTy>>
134 auto Key = std::make_pair(FromModule, GUID);
135 auto It = TheTable.find(Key);
136 if (It != TheTable.end())
137 return makeIDPair(It->second);
138 return std::nullopt;
139 }
140
141 // Return a tuple of [FromModule, GUID, Def/Decl] that a given ImportID
142 // corresponds to.
143 std::tuple<StringRef, GlobalValue::GUID, GlobalValueSummary::ImportKind>
144 lookup(ImportIDTy ImportID) const {
146 (ImportID & 1) ? GlobalValueSummary::Declaration
148 auto It = TheTable.begin() + (ImportID >> 1);
149 StringRef FromModule = It->first.first;
150 GlobalValue::GUID GUID = It->first.second;
151 return std::make_tuple(FromModule, GUID, Kind);
152 }
153
154 // The same as lookup above. Useful for map_iterator.
155 std::tuple<StringRef, GlobalValue::GUID, GlobalValueSummary::ImportKind>
157 return lookup(ImportID);
158 }
159
160 private:
161 // Make a pair of import IDs [Def, Decl] from an index into TheTable.
162 static std::pair<ImportIDTy, ImportIDTy> makeIDPair(ImportIDTy Index) {
163 ImportIDTy Def = Index << 1;
164 ImportIDTy Decl = Def | 1;
165 return std::make_pair(Def, Decl);
166 }
167
169 };
170
171 // Forward-declare SortedImportList for ImportMapTy.
172 class SortedImportList;
173
174 /// The map maintains the list of imports. Conceptually, it is a collection
175 /// of tuples of the form:
176 ///
177 /// (The name of the source module, GUID, Definition/Declaration)
178 ///
179 /// The name of the source module is the module identifier to pass to the
180 /// ModuleLoader. The module identifier strings must be owned elsewhere,
181 /// typically by the in-memory ModuleSummaryIndex the importing decisions are
182 /// made from (the module path for each summary is owned by the index's module
183 /// path string table).
185 public:
187 // No change was made to the list of imports or whether each import should
188 // be imported as a declaration or definition.
189 NoChange,
190 // Successfully added the given GUID to be imported as a definition. There
191 // was no existing entry with the same GUID as a declaration.
192 Inserted,
193 // An existing with the given GUID was changed to a definition.
195 };
196
197 ImportMapTy() = delete;
198 ImportMapTy(ImportIDTable &IDs) : IDs(IDs) {}
199
200 // Add the given GUID to ImportList as a definition. If the same GUID has
201 // been added as a declaration previously, that entry is overridden.
203 GlobalValue::GUID GUID);
204
205 // Add the given GUID to ImportList as a declaration. If the same GUID has
206 // been added as a definition previously, that entry takes precedence, and
207 // no change is made.
208 void maybeAddDeclaration(StringRef FromModule, GlobalValue::GUID GUID);
209
210 void addGUID(StringRef FromModule, GlobalValue::GUID GUID,
212 if (ImportKind == GlobalValueSummary::Definition)
213 addDefinition(FromModule, GUID);
214 else
215 maybeAddDeclaration(FromModule, GUID);
216 }
217
218 // Return the list of source modules sorted in the ascending alphabetical
219 // order.
221
222 std::optional<GlobalValueSummary::ImportKind>
223 getImportType(StringRef FromModule, GlobalValue::GUID GUID) const;
224
225 // Iterate over the import list. The caller gets tuples of FromModule,
226 // GUID, and ImportKind instead of import IDs. std::cref below prevents
227 // map_iterator from deep-copying IDs.
228 auto begin() const { return map_iterator(Imports.begin(), std::cref(IDs)); }
229 auto end() const { return map_iterator(Imports.end(), std::cref(IDs)); }
230
231 friend class SortedImportList;
232
233 private:
234 ImportIDTable &IDs;
236 };
237
238 // A read-only copy of ImportMapTy with its contents sorted according to the
239 // given comparison function.
241 public:
244 bool(const std::pair<StringRef, GlobalValue::GUID> &,
245 const std::pair<StringRef, GlobalValue::GUID> &)>
246 Comp)
247 : IDs(ImportMap.IDs), Imports(iterator_range(ImportMap.Imports)) {
250 auto Lookup = [&](ImportIDTable::ImportIDTy Id)
251 -> std::pair<StringRef, GlobalValue::GUID> {
252 auto Tuple = IDs.lookup(Id);
253 return std::make_pair(std::get<0>(Tuple), std::get<1>(Tuple));
254 };
255 return Comp(Lookup(L), Lookup(R));
256 });
257 }
258
259 // Iterate over the import list. The caller gets tuples of FromModule,
260 // GUID, and ImportKind instead of import IDs. std::cref below prevents
261 // map_iterator from deep-copying IDs.
262 auto begin() const { return map_iterator(Imports.begin(), std::cref(IDs)); }
263 auto end() const { return map_iterator(Imports.end(), std::cref(IDs)); }
264
265 private:
266 const ImportIDTable &IDs;
268 };
269
270 // A map from destination modules to lists of imports.
272 public:
273 ImportListsTy() : EmptyList(ImportIDs) {}
274 ImportListsTy(size_t Size) : EmptyList(ImportIDs), ListsImpl(Size) {}
275
277 return ListsImpl.try_emplace(DestMod, ImportIDs).first->second;
278 }
279
280 const ImportMapTy &lookup(StringRef DestMod) const {
281 auto It = ListsImpl.find(DestMod);
282 if (It != ListsImpl.end())
283 return It->second;
284 return EmptyList;
285 }
286
287 size_t size() const { return ListsImpl.size(); }
288
290 const_iterator begin() const { return ListsImpl.begin(); }
291 const_iterator end() const { return ListsImpl.end(); }
292
293 private:
294 ImportMapTy EmptyList;
296 ImportIDTable ImportIDs;
297 };
298
299 /// The set contains an entry for every global value that the module exports.
300 /// Depending on the user context, this container is allowed to contain
301 /// definitions, declarations or a mix of both.
303
304 /// A function of this type is used to load modules referenced by the index.
306 std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)>;
307
308 /// Create a Function Importer.
310 bool ClearDSOLocalOnDeclarations)
311 : Index(Index), ModuleLoader(std::move(ModuleLoader)),
312 ClearDSOLocalOnDeclarations(ClearDSOLocalOnDeclarations) {}
313
314 /// Import functions in Module \p M based on the supplied import list.
315 Expected<bool> importFunctions(Module &M, const ImportMapTy &ImportList);
316
317private:
318 /// The summaries index used to trigger importing.
319 const ModuleSummaryIndex &Index;
320
321 /// Factory function to load a Module for a given identifier
322 ModuleLoaderTy ModuleLoader;
323
324 /// See the comment of ClearDSOLocalOnDeclarations in
325 /// Utils/FunctionImportUtils.h.
326 bool ClearDSOLocalOnDeclarations;
327};
328
329/// The function importing pass
330class FunctionImportPass : public PassInfoMixin<FunctionImportPass> {
331public:
333};
334
335/// Compute all the imports and exports for every module in the Index.
336///
337/// \p ModuleToDefinedGVSummaries contains for each Module a map
338/// (GUID -> Summary) for every global defined in the module.
339///
340/// \p isPrevailing is a callback that will be called with a global value's GUID
341/// and summary and should return whether the module corresponding to the
342/// summary contains the linker-prevailing copy of that value.
343///
344/// \p ImportLists will be populated with an entry for every Module we are
345/// importing into. This entry is itself a map that can be passed to
346/// FunctionImporter::importFunctions() above (see description there).
347///
348/// \p ExportLists contains for each Module the set of globals (GUID) that will
349/// be imported by another module, or referenced by such a function. I.e. this
350/// is the set of globals that need to be promoted/renamed appropriately.
351///
352/// The module identifier strings that are the keys of the above two maps
353/// are owned by the in-memory ModuleSummaryIndex the importing decisions
354/// are made from (the module path for each summary is owned by the index's
355/// module path string table).
358 const DenseMap<StringRef, GVSummaryMapTy> &ModuleToDefinedGVSummaries,
360 isPrevailing,
363
364/// PrevailingType enum used as a return type of callback passed
365/// to computeDeadSymbolsAndUpdateIndirectCalls. Yes and No values used when
366/// status explicitly set by symbols resolution, otherwise status is Unknown.
367enum class PrevailingType { Yes, No, Unknown };
368
369/// Update call edges for indirect calls to local functions added from
370/// SamplePGO when needed. Normally this is done during
371/// computeDeadSymbolsAndUpdateIndirectCalls, but can be called standalone
372/// when that is not called (e.g. during testing).
373void updateIndirectCalls(ModuleSummaryIndex &Index);
374
375/// Compute all the symbols that are "dead": i.e these that can't be reached
376/// in the graph from any of the given symbols listed in
377/// \p GUIDPreservedSymbols. Non-prevailing symbols are symbols without a
378/// prevailing copy anywhere in IR and are normally dead, \p isPrevailing
379/// predicate returns status of symbol.
380/// Also update call edges for indirect calls to local functions added from
381/// SamplePGO when needed.
383 ModuleSummaryIndex &Index,
384 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
385 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing);
386
387/// Compute dead symbols and run constant propagation in combined index
388/// after that.
390 ModuleSummaryIndex &Index,
391 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
392 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing,
393 bool ImportEnabled);
394
395/// Converts value \p GV to declaration, or replaces with a declaration if
396/// it is an alias. Returns true if converted, false if replaced.
397bool convertToDeclaration(GlobalValue &GV);
398
399/// Compute the set of summaries needed for a ThinLTO backend compilation of
400/// \p ModulePath.
401//
402/// This includes summaries from that module (in case any global summary based
403/// optimizations were recorded) and from any definitions in other modules that
404/// should be imported.
405//
406/// \p ModuleToSummariesForIndex will be populated with the needed summaries
407/// from each required module path. Use a std::map instead of StringMap to get
408/// stable order for bitcode emission.
409///
410/// \p DecSummaries will be popluated with the subset of of summary pointers
411/// that have 'declaration' import type among all summaries the module need.
413 StringRef ModulePath,
414 const DenseMap<StringRef, GVSummaryMapTy> &ModuleToDefinedGVSummaries,
415 const FunctionImporter::ImportMapTy &ImportList,
416 ModuleToSummariesForIndexTy &ModuleToSummariesForIndex,
417 GVSummaryPtrSet &DecSummaries);
418
419/// Emit into \p OutputFilename the files module \p ModulePath will import from.
420Error EmitImportsFiles(
421 StringRef ModulePath, StringRef OutputFilename,
422 const ModuleToSummariesForIndexTy &ModuleToSummariesForIndex);
423
424/// Based on the information recorded in the summaries during global
425/// summary-based analysis:
426/// 1. Resolve prevailing symbol linkages and constrain visibility (CanAutoHide
427/// and consider visibility from other definitions for ELF) in \p TheModule
428/// 2. (optional) Apply propagated function attributes to \p TheModule if
429/// PropagateAttrs is true
430void thinLTOFinalizeInModule(Module &TheModule,
431 const GVSummaryMapTy &DefinedGlobals,
432 bool PropagateAttrs);
433
434/// Internalize \p TheModule based on the information recorded in the summaries
435/// during global summary-based analysis.
436void thinLTOInternalizeModule(Module &TheModule,
437 const GVSummaryMapTy &DefinedGlobals);
438
439} // end namespace llvm
440
441#endif // LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H
This file defines the DenseSet and SmallDenseSet classes.
uint32_t Index
uint64_t Size
This header defines various interfaces for pass management in LLVM.
Machine Check Debug Module
static cl::opt< std::string > OutputFilename("o", cl::desc("Output filename"), cl::value_desc("filename"), cl::init("-"))
This file implements a map that provides insertion order iteration.
static cl::opt< bool > PropagateAttrs("propagate-attrs", cl::init(true), cl::Hidden, cl::desc("Propagate attributes in index"))
ModuleSummaryIndex.h This file contains the declarations the classes that hold the module index and s...
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
Implements a dense probed hash-table based set.
Definition: DenseSet.h:278
Tagged union holding either a T or a Error.
Definition: Error.h:481
The function importing pass.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
std::pair< ImportIDTy, ImportIDTy > createImportIDs(StringRef FromModule, GlobalValue::GUID GUID)
ImportIDTable(const ImportIDTable &)=delete
ImportIDTable & operator=(const ImportIDTable &)=delete
std::tuple< StringRef, GlobalValue::GUID, GlobalValueSummary::ImportKind > lookup(ImportIDTy ImportID) const
std::optional< std::pair< ImportIDTy, ImportIDTy > > getImportIDs(StringRef FromModule, GlobalValue::GUID GUID)
std::tuple< StringRef, GlobalValue::GUID, GlobalValueSummary::ImportKind > operator()(ImportIDTable::ImportIDTy ImportID) const
const ImportMapTy & lookup(StringRef DestMod) const
ImportMapTy & operator[](StringRef DestMod)
The map maintains the list of imports.
AddDefinitionStatus addDefinition(StringRef FromModule, GlobalValue::GUID GUID)
void addGUID(StringRef FromModule, GlobalValue::GUID GUID, GlobalValueSummary::ImportKind ImportKind)
SmallVector< StringRef, 0 > getSourceModules() const
std::optional< GlobalValueSummary::ImportKind > getImportType(StringRef FromModule, GlobalValue::GUID GUID) const
void maybeAddDeclaration(StringRef FromModule, GlobalValue::GUID GUID)
SortedImportList(const ImportMapTy &ImportMap, llvm::function_ref< bool(const std::pair< StringRef, GlobalValue::GUID > &, const std::pair< StringRef, GlobalValue::GUID > &)> Comp)
The function importer is automatically importing function from other modules based on the provided su...
Expected< bool > importFunctions(Module &M, const ImportMapTy &ImportList)
Import functions in Module M based on the supplied import list.
FunctionImporter(const ModuleSummaryIndex &Index, ModuleLoaderTy ModuleLoader, bool ClearDSOLocalOnDeclarations)
Create a Function Importer.
ImportFailureReason
The different reasons selectCallee will chose not to import a candidate.
std::function< Expected< std::unique_ptr< Module > >(StringRef Identifier)> ModuleLoaderTy
A function of this type is used to load modules referenced by the index.
Function and variable summary information to aid decisions and implementation of importing.
uint64_t GUID
Declare a type to represent a global unique identifier for a global value.
Definition: GlobalValue.h:587
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
Class to hold module path string table and global value map, and encapsulate methods for operating on...
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:51
An efficient, type-erasing, non-owning reference to a callable.
A range adaptor for a pair of iterators.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
mapped_iterator< ItTy, FuncTy > map_iterator(ItTy I, FuncTy F)
Definition: STLExtras.h:372
bool convertToDeclaration(GlobalValue &GV)
Converts value GV to declaration, or replaces with a declaration if it is an alias.
void ComputeCrossModuleImport(const ModuleSummaryIndex &Index, const DenseMap< StringRef, GVSummaryMapTy > &ModuleToDefinedGVSummaries, function_ref< bool(GlobalValue::GUID, const GlobalValueSummary *)> isPrevailing, FunctionImporter::ImportListsTy &ImportLists, DenseMap< StringRef, FunctionImporter::ExportSetTy > &ExportLists)
Compute all the imports and exports for every module in the Index.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1664
void computeDeadSymbolsAndUpdateIndirectCalls(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...
void updateIndirectCalls(ModuleSummaryIndex &Index)
Update call edges for indirect calls to local functions added from SamplePGO when needed.
void thinLTOInternalizeModule(Module &TheModule, const GVSummaryMapTy &DefinedGlobals)
Internalize TheModule based on the information recorded in the summaries during global summary-based ...
std::unordered_set< GlobalValueSummary * > GVSummaryPtrSet
A set of global value summary pointers.
void gatherImportedSummariesForModule(StringRef ModulePath, const DenseMap< StringRef, GVSummaryMapTy > &ModuleToDefinedGVSummaries, const FunctionImporter::ImportMapTy &ImportList, ModuleToSummariesForIndexTy &ModuleToSummariesForIndex, GVSummaryPtrSet &DecSummaries)
Compute the set of summaries needed for a ThinLTO backend compilation of ModulePath.
std::map< std::string, GVSummaryMapTy, std::less<> > ModuleToSummariesForIndexTy
Map of a module name to the GUIDs and summaries we will import from that module.
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:1873
PrevailingType
PrevailingType enum used as a return type of callback passed to computeDeadSymbolsAndUpdateIndirectCa...
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.
Error EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename, const ModuleToSummariesForIndexTy &ModuleToSummariesForIndex)
Emit into OutputFilename the files module ModulePath will import from.
DenseMap< GlobalValue::GUID, GlobalValueSummary * > GVSummaryMapTy
Map of global value GUID to its summary, used to identify values defined in a particular module,...
void thinLTOFinalizeInModule(Module &TheModule, const GVSummaryMapTy &DefinedGlobals, bool PropagateAttrs)
Based on the information recorded in the summaries during global summary-based analysis:
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
Information optionally tracked for candidates the importer decided not to import.
ImportFailureInfo(ValueInfo VI, CalleeInfo::HotnessType MaxHotness, ImportFailureReason Reason, unsigned Attempts)
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69
Struct that holds a reference to a particular GUID in a global value summary.