1 //===-- llvm/ModuleSummaryIndex.h - Module Summary Index --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// ModuleSummaryIndex.h This file contains the declarations the classes that
12 /// hold the module index and summary for function importing.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_IR_MODULESUMMARYINDEX_H
17 #define LLVM_IR_MODULESUMMARYINDEX_H
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/DenseSet.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SmallString.h"
23 #include "llvm/ADT/StringExtras.h"
24 #include "llvm/ADT/StringMap.h"
25 #include "llvm/IR/Module.h"
31 /// \brief Class to accumulate and hold information about a callee.
33 /// The static number of callsites calling corresponding function.
34 unsigned CallsiteCount;
35 /// The cumulative profile count of calls to corresponding function
36 /// (if using PGO, otherwise 0).
37 uint64_t ProfileCount;
38 CalleeInfo() : CallsiteCount(0), ProfileCount(0) {}
39 CalleeInfo(unsigned CallsiteCount, uint64_t ProfileCount)
40 : CallsiteCount(CallsiteCount), ProfileCount(ProfileCount) {}
41 CalleeInfo &operator+=(uint64_t RHSProfileCount) {
43 ProfileCount += RHSProfileCount;
48 /// Struct to hold value either by GUID or Value*, depending on whether this
49 /// is a combined or per-module index, respectively.
51 /// The value representation used in this instance.
57 /// Union of the two possible value types.
61 ValueUnion(GlobalValue::GUID Id) : Id(Id) {}
62 ValueUnion(const Value *V) : V(V) {}
65 /// The value being represented.
67 /// The value representation.
69 /// Constructor for a GUID value
70 ValueInfo(GlobalValue::GUID Id = 0) : TheValue(Id), Kind(VI_GUID) {}
71 /// Constructor for a Value* value
72 ValueInfo(const Value *V) : TheValue(V), Kind(VI_Value) {}
73 /// Accessor for GUID value
74 GlobalValue::GUID getGUID() const {
75 assert(Kind == VI_GUID && "Not a GUID type");
78 /// Accessor for Value* value
79 const Value *getValue() const {
80 assert(Kind == VI_Value && "Not a Value type");
83 bool isGUID() const { return Kind == VI_GUID; }
86 /// \brief Function and variable summary information to aid decisions and
87 /// implementation of importing.
88 class GlobalValueSummary {
90 /// \brief Sububclass discriminator (for dyn_cast<> et al.)
91 enum SummaryKind { AliasKind, FunctionKind, GlobalVarKind };
93 /// Group flags (Linkage, hasSection, isOptSize, etc.) as a bitfield.
95 /// \brief The linkage type of the associated global value.
97 /// One use is to flag values that have local linkage types and need to
98 /// have module identifier appended before placing into the combined
99 /// index, to disambiguate from other values with the same name.
100 /// In the future this will be used to update and optimize linkage
101 /// types based on global summary-based analysis.
102 unsigned Linkage : 4;
104 /// Indicate if the global value is located in a specific section.
105 unsigned HasSection : 1;
107 /// Convenience Constructors
108 explicit GVFlags(GlobalValue::LinkageTypes Linkage, bool HasSection)
109 : Linkage(Linkage), HasSection(HasSection) {}
110 GVFlags(const GlobalValue &GV)
111 : Linkage(GV.getLinkage()), HasSection(GV.hasSection()) {}
115 /// Kind of summary for use in dyn_cast<> et al.
118 /// This is the hash of the name of the symbol in the original file. It is
119 /// identical to the GUID for global symbols, but differs for local since the
120 /// GUID includes the module level id in the hash.
121 GlobalValue::GUID OriginalName;
123 /// \brief Path of module IR containing value's definition, used to locate
124 /// module during importing.
126 /// This is only used during parsing of the combined index, or when
127 /// parsing the per-module index for creation of the combined summary index,
128 /// not during writing of the per-module index which doesn't contain a
129 /// module path string table.
130 StringRef ModulePath;
134 /// List of values referenced by this global value's definition
135 /// (either by the initializer of a global variable, or referenced
136 /// from within a function). This does not include functions called, which
137 /// are listed in the derived FunctionSummary object.
138 std::vector<ValueInfo> RefEdgeList;
141 /// GlobalValueSummary constructor.
142 GlobalValueSummary(SummaryKind K, GVFlags Flags) : Kind(K), Flags(Flags) {}
145 virtual ~GlobalValueSummary() = default;
147 /// Returns the hash of the original name, it is identical to the GUID for
148 /// externally visible symbols, but not for local ones.
149 GlobalValue::GUID getOriginalName() { return OriginalName; }
151 /// Initialize the original name hash in this summary.
152 void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
154 /// Which kind of summary subclass this is.
155 SummaryKind getSummaryKind() const { return Kind; }
157 /// Set the path to the module containing this function, for use in
158 /// the combined index.
159 void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
161 /// Get the path to the module containing this function.
162 StringRef modulePath() const { return ModulePath; }
164 /// Get the flags for this GlobalValue (see \p struct GVFlags).
165 GVFlags flags() { return Flags; }
167 /// Return linkage type recorded for this global value.
168 GlobalValue::LinkageTypes linkage() const {
169 return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
172 /// Sets the linkage to the value determined by global summary-based
173 /// optimization. Will be applied in the ThinLTO backends.
174 void setLinkage(GlobalValue::LinkageTypes Linkage) {
175 Flags.Linkage = Linkage;
178 /// Return true if this summary is for a GlobalValue that needs promotion
179 /// to be referenced from another module.
180 bool needsRenaming() const { return GlobalValue::isLocalLinkage(linkage()); }
182 /// Return true if this global value is located in a specific section.
183 bool hasSection() const { return Flags.HasSection; }
185 /// Record a reference from this global value to the global value identified
187 void addRefEdge(GlobalValue::GUID RefGUID) { RefEdgeList.push_back(RefGUID); }
189 /// Record a reference from this global value to the global value identified
191 void addRefEdge(const Value *RefV) { RefEdgeList.push_back(RefV); }
193 /// Record a reference from this global value to each global value identified
195 void addRefEdges(DenseSet<const Value *> &RefEdges) {
196 for (auto &RI : RefEdges)
200 /// Return the list of values referenced by this global value definition.
201 std::vector<ValueInfo> &refs() { return RefEdgeList; }
202 const std::vector<ValueInfo> &refs() const { return RefEdgeList; }
205 /// \brief Alias summary information.
206 class AliasSummary : public GlobalValueSummary {
207 GlobalValueSummary *AliaseeSummary;
210 /// Summary constructors.
211 AliasSummary(GVFlags Flags) : GlobalValueSummary(AliasKind, Flags) {}
213 /// Check if this is an alias summary.
214 static bool classof(const GlobalValueSummary *GVS) {
215 return GVS->getSummaryKind() == AliasKind;
218 void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
220 const GlobalValueSummary &getAliasee() const {
221 return const_cast<AliasSummary *>(this)->getAliasee();
224 GlobalValueSummary &getAliasee() {
225 assert(AliaseeSummary && "Unexpected missing aliasee summary");
226 return *AliaseeSummary;
230 /// \brief Function summary information to aid decisions and implementation of
232 class FunctionSummary : public GlobalValueSummary {
234 /// <CalleeValueInfo, CalleeInfo> call edge pair.
235 typedef std::pair<ValueInfo, CalleeInfo> EdgeTy;
238 /// Number of instructions (ignoring debug instructions, e.g.) computed
239 /// during the initial compile step when the summary index is first built.
242 /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
243 std::vector<EdgeTy> CallGraphEdgeList;
246 /// Summary constructors.
247 FunctionSummary(GVFlags Flags, unsigned NumInsts)
248 : GlobalValueSummary(FunctionKind, Flags), InstCount(NumInsts) {}
250 /// Check if this is a function summary.
251 static bool classof(const GlobalValueSummary *GVS) {
252 return GVS->getSummaryKind() == FunctionKind;
255 /// Get the instruction count recorded for this function.
256 unsigned instCount() const { return InstCount; }
258 /// Record a call graph edge from this function to the function identified
259 /// by \p CalleeGUID, with \p CalleeInfo including the cumulative profile
260 /// count (across all calls from this function) or 0 if no PGO.
261 void addCallGraphEdge(GlobalValue::GUID CalleeGUID, CalleeInfo Info) {
262 CallGraphEdgeList.push_back(std::make_pair(CalleeGUID, Info));
265 /// Record a call graph edge from this function to each function GUID recorded
266 /// in \p CallGraphEdges.
268 addCallGraphEdges(DenseMap<GlobalValue::GUID, CalleeInfo> &CallGraphEdges) {
269 for (auto &EI : CallGraphEdges)
270 addCallGraphEdge(EI.first, EI.second);
273 /// Record a call graph edge from this function to the function identified
274 /// by \p CalleeV, with \p CalleeInfo including the cumulative profile
275 /// count (across all calls from this function) or 0 if no PGO.
276 void addCallGraphEdge(const Value *CalleeV, CalleeInfo Info) {
277 CallGraphEdgeList.push_back(std::make_pair(CalleeV, Info));
280 /// Record a call graph edge from this function to each function recorded
281 /// in \p CallGraphEdges.
282 void addCallGraphEdges(DenseMap<const Value *, CalleeInfo> &CallGraphEdges) {
283 for (auto &EI : CallGraphEdges)
284 addCallGraphEdge(EI.first, EI.second);
287 /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
288 std::vector<EdgeTy> &calls() { return CallGraphEdgeList; }
289 const std::vector<EdgeTy> &calls() const { return CallGraphEdgeList; }
292 /// \brief Global variable summary information to aid decisions and
293 /// implementation of importing.
295 /// Currently this doesn't add anything to the base \p GlobalValueSummary,
296 /// but is a placeholder as additional info may be added to the summary
298 class GlobalVarSummary : public GlobalValueSummary {
301 /// Summary constructors.
302 GlobalVarSummary(GVFlags Flags) : GlobalValueSummary(GlobalVarKind, Flags) {}
304 /// Check if this is a global variable summary.
305 static bool classof(const GlobalValueSummary *GVS) {
306 return GVS->getSummaryKind() == GlobalVarKind;
311 typedef std::array<uint32_t, 5> ModuleHash;
313 /// List of global value summary structures for a particular value held
314 /// in the GlobalValueMap. Requires a vector in the case of multiple
315 /// COMDAT values of the same name.
316 typedef std::vector<std::unique_ptr<GlobalValueSummary>> GlobalValueSummaryList;
318 /// Map from global value GUID to corresponding summary structures.
319 /// Use a std::map rather than a DenseMap since it will likely incur
320 /// less overhead, as the value type is not very small and the size
321 /// of the map is unknown, resulting in inefficiencies due to repeated
322 /// insertions and resizing.
323 typedef std::map<GlobalValue::GUID, GlobalValueSummaryList>
324 GlobalValueSummaryMapTy;
326 /// Type used for iterating through the global value summary map.
327 typedef GlobalValueSummaryMapTy::const_iterator const_gvsummary_iterator;
328 typedef GlobalValueSummaryMapTy::iterator gvsummary_iterator;
330 /// String table to hold/own module path strings, which additionally holds the
331 /// module ID assigned to each module during the plugin step, as well as a hash
332 /// of the module. The StringMap makes a copy of and owns inserted strings.
333 typedef StringMap<std::pair<uint64_t, ModuleHash>> ModulePathStringTableTy;
335 /// Map of global value GUID to its summary, used to identify values defined in
336 /// a particular module, and provide efficient access to their summary.
337 typedef std::map<GlobalValue::GUID, GlobalValueSummary *> GVSummaryMapTy;
339 /// Class to hold module path string table and global value map,
340 /// and encapsulate methods for operating on them.
341 class ModuleSummaryIndex {
343 /// Map from value name to list of summary instances for values of that
344 /// name (may be duplicates in the COMDAT case, e.g.).
345 GlobalValueSummaryMapTy GlobalValueMap;
347 /// Holds strings for combined index, mapping to the corresponding module ID.
348 ModulePathStringTableTy ModulePathStringTable;
351 ModuleSummaryIndex() = default;
353 // Disable the copy constructor and assignment operators, so
354 // no unexpected copying/moving occurs.
355 ModuleSummaryIndex(const ModuleSummaryIndex &) = delete;
356 void operator=(const ModuleSummaryIndex &) = delete;
358 gvsummary_iterator begin() { return GlobalValueMap.begin(); }
359 const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
360 gvsummary_iterator end() { return GlobalValueMap.end(); }
361 const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
363 /// Get the list of global value summary objects for a given value name.
364 const GlobalValueSummaryList &getGlobalValueSummaryList(StringRef ValueName) {
365 return GlobalValueMap[GlobalValue::getGUID(ValueName)];
368 /// Get the list of global value summary objects for a given value name.
369 const const_gvsummary_iterator
370 findGlobalValueSummaryList(StringRef ValueName) const {
371 return GlobalValueMap.find(GlobalValue::getGUID(ValueName));
374 /// Get the list of global value summary objects for a given value GUID.
375 const const_gvsummary_iterator
376 findGlobalValueSummaryList(GlobalValue::GUID ValueGUID) const {
377 return GlobalValueMap.find(ValueGUID);
380 /// Add a global value summary for a value of the given name.
381 void addGlobalValueSummary(StringRef ValueName,
382 std::unique_ptr<GlobalValueSummary> Summary) {
383 GlobalValueMap[GlobalValue::getGUID(ValueName)].push_back(
387 /// Add a global value summary for a value of the given GUID.
388 void addGlobalValueSummary(GlobalValue::GUID ValueGUID,
389 std::unique_ptr<GlobalValueSummary> Summary) {
390 GlobalValueMap[ValueGUID].push_back(std::move(Summary));
393 /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
395 GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
396 StringRef ModuleId) const {
397 auto CalleeInfoList = findGlobalValueSummaryList(ValueGUID);
398 if (CalleeInfoList == end()) {
399 return nullptr; // This function does not have a summary
402 llvm::find_if(CalleeInfoList->second,
403 [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
404 return Summary->modulePath() == ModuleId;
406 if (Summary == CalleeInfoList->second.end())
408 return Summary->get();
411 /// Returns the first GlobalValueSummary for \p GV, asserting that there
412 /// is only one if \p PerModuleIndex.
413 GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
414 bool PerModuleIndex = true) const {
415 assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
416 return getGlobalValueSummary(GlobalValue::getGUID(GV.getName()),
420 /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
422 /// is only one if \p PerModuleIndex.
423 GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
424 bool PerModuleIndex = true) const;
426 /// Table of modules, containing module hash and id.
427 const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
428 return ModulePathStringTable;
431 /// Table of modules, containing hash and id.
432 StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
433 return ModulePathStringTable;
436 /// Get the module ID recorded for the given module path.
437 uint64_t getModuleId(const StringRef ModPath) const {
438 return ModulePathStringTable.lookup(ModPath).first;
441 /// Get the module SHA1 hash recorded for the given module path.
442 const ModuleHash &getModuleHash(const StringRef ModPath) const {
443 auto It = ModulePathStringTable.find(ModPath);
444 assert(It != ModulePathStringTable.end() && "Module not registered");
445 return It->second.second;
448 /// Add the given per-module index into this module index/summary,
449 /// assigning it the given module ID. Each module merged in should have
450 /// a unique ID, necessary for consistent renaming of promoted
451 /// static (local) variables.
452 void mergeFrom(std::unique_ptr<ModuleSummaryIndex> Other,
453 uint64_t NextModuleId);
455 /// Convenience method for creating a promoted global name
456 /// for the given value name of a local, and its original module's ID.
457 static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
458 SmallString<256> NewName(Name);
460 NewName += utohexstr(ModHash[0]); // Take the first 32 bits
461 return NewName.str();
464 /// Helper to obtain the unpromoted name for a global value (or the original
465 /// name if not promoted).
466 static StringRef getOriginalNameBeforePromote(StringRef Name) {
467 std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
471 /// Add a new module path with the given \p Hash, mapped to the given \p
472 /// ModID, and return an iterator to the entry in the index.
473 ModulePathStringTableTy::iterator
474 addModulePath(StringRef ModPath, uint64_t ModId,
475 ModuleHash Hash = ModuleHash{{0}}) {
476 return ModulePathStringTable.insert(std::make_pair(
478 std::make_pair(ModId, Hash))).first;
481 /// Check if the given Module has any functions available for exporting
482 /// in the index. We consider any module present in the ModulePathStringTable
483 /// to have exported functions.
484 bool hasExportedFunctions(const Module &M) const {
485 return ModulePathStringTable.count(M.getModuleIdentifier());
488 /// Remove entries in the GlobalValueMap that have empty summaries due to the
489 /// eager nature of map entry creation during VST parsing. These would
490 /// also be suppressed during combined index generation in mergeFrom(),
491 /// but if there was only one module or this was the first module we might
492 /// not invoke mergeFrom.
493 void removeEmptySummaryEntries();
495 /// Collect for the given module the list of function it defines
496 /// (GUID -> Summary).
497 void collectDefinedFunctionsForModule(StringRef ModulePath,
498 GVSummaryMapTy &GVSummaryMap) const;
500 /// Collect for each module the list of Summaries it defines (GUID ->
502 void collectDefinedGVSummariesPerModule(
503 StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const;
506 } // End llvm namespace