• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- llvm/ModuleSummaryIndex.h - Module Summary Index --------*- 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 /// @file
11 /// ModuleSummaryIndex.h This file contains the declarations the classes that
12 ///  hold the module index and summary for function importing.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_IR_MODULESUMMARYINDEX_H
17 #define LLVM_IR_MODULESUMMARYINDEX_H
18 
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"
26 
27 #include <array>
28 
29 namespace llvm {
30 
31 /// \brief Class to accumulate and hold information about a callee.
32 struct CalleeInfo {
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;
CalleeInfoCalleeInfo38   CalleeInfo() : CallsiteCount(0), ProfileCount(0) {}
CalleeInfoCalleeInfo39   CalleeInfo(unsigned CallsiteCount, uint64_t ProfileCount)
40       : CallsiteCount(CallsiteCount), ProfileCount(ProfileCount) {}
41   CalleeInfo &operator+=(uint64_t RHSProfileCount) {
42     CallsiteCount++;
43     ProfileCount += RHSProfileCount;
44     return *this;
45   }
46 };
47 
48 /// Struct to hold value either by GUID or Value*, depending on whether this
49 /// is a combined or per-module index, respectively.
50 struct ValueInfo {
51   /// The value representation used in this instance.
52   enum ValueInfoKind {
53     VI_GUID,
54     VI_Value,
55   };
56 
57   /// Union of the two possible value types.
58   union ValueUnion {
59     GlobalValue::GUID Id;
60     const Value *V;
ValueUnion(GlobalValue::GUID Id)61     ValueUnion(GlobalValue::GUID Id) : Id(Id) {}
ValueUnion(const Value * V)62     ValueUnion(const Value *V) : V(V) {}
63   };
64 
65   /// The value being represented.
66   ValueUnion TheValue;
67   /// The value representation.
68   ValueInfoKind Kind;
69   /// Constructor for a GUID value
TheValueValueInfo70   ValueInfo(GlobalValue::GUID Id = 0) : TheValue(Id), Kind(VI_GUID) {}
71   /// Constructor for a Value* value
ValueInfoValueInfo72   ValueInfo(const Value *V) : TheValue(V), Kind(VI_Value) {}
73   /// Accessor for GUID value
getGUIDValueInfo74   GlobalValue::GUID getGUID() const {
75     assert(Kind == VI_GUID && "Not a GUID type");
76     return TheValue.Id;
77   }
78   /// Accessor for Value* value
getValueValueInfo79   const Value *getValue() const {
80     assert(Kind == VI_Value && "Not a Value type");
81     return TheValue.V;
82   }
83 };
84 
85 /// \brief Function and variable summary information to aid decisions and
86 /// implementation of importing.
87 class GlobalValueSummary {
88 public:
89   /// \brief Sububclass discriminator (for dyn_cast<> et al.)
90   enum SummaryKind { AliasKind, FunctionKind, GlobalVarKind };
91 
92   /// Group flags (Linkage, hasSection, isOptSize, etc.) as a bitfield.
93   struct GVFlags {
94     /// \brief The linkage type of the associated global value.
95     ///
96     /// One use is to flag values that have local linkage types and need to
97     /// have module identifier appended before placing into the combined
98     /// index, to disambiguate from other values with the same name.
99     /// In the future this will be used to update and optimize linkage
100     /// types based on global summary-based analysis.
101     unsigned Linkage : 4;
102 
103     /// Indicate if the global value is located in a specific section.
104     unsigned HasSection : 1;
105 
106     /// Convenience Constructors
GVFlagsGVFlags107     explicit GVFlags(GlobalValue::LinkageTypes Linkage, bool HasSection)
108         : Linkage(Linkage), HasSection(HasSection) {}
GVFlagsGVFlags109     GVFlags(const GlobalValue &GV)
110         : Linkage(GV.getLinkage()), HasSection(GV.hasSection()) {}
111   };
112 
113 private:
114   /// Kind of summary for use in dyn_cast<> et al.
115   SummaryKind Kind;
116 
117   /// This is the hash of the name of the symbol in the original file. It is
118   /// identical to the GUID for global symbols, but differs for local since the
119   /// GUID includes the module level id in the hash.
120   GlobalValue::GUID OriginalName;
121 
122   /// \brief Path of module IR containing value's definition, used to locate
123   /// module during importing.
124   ///
125   /// This is only used during parsing of the combined index, or when
126   /// parsing the per-module index for creation of the combined summary index,
127   /// not during writing of the per-module index which doesn't contain a
128   /// module path string table.
129   StringRef ModulePath;
130 
131   GVFlags Flags;
132 
133   /// List of values referenced by this global value's definition
134   /// (either by the initializer of a global variable, or referenced
135   /// from within a function). This does not include functions called, which
136   /// are listed in the derived FunctionSummary object.
137   std::vector<ValueInfo> RefEdgeList;
138 
139 protected:
140   /// GlobalValueSummary constructor.
GlobalValueSummary(SummaryKind K,GVFlags Flags)141   GlobalValueSummary(SummaryKind K, GVFlags Flags) : Kind(K), Flags(Flags) {}
142 
143 public:
144   virtual ~GlobalValueSummary() = default;
145 
146   /// Returns the hash of the original name, it is identical to the GUID for
147   /// externally visible symbols, but not for local ones.
getOriginalName()148   GlobalValue::GUID getOriginalName() { return OriginalName; }
149 
150   /// Initialize the original name hash in this summary.
setOriginalName(GlobalValue::GUID Name)151   void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
152 
153   /// Which kind of summary subclass this is.
getSummaryKind()154   SummaryKind getSummaryKind() const { return Kind; }
155 
156   /// Set the path to the module containing this function, for use in
157   /// the combined index.
setModulePath(StringRef ModPath)158   void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
159 
160   /// Get the path to the module containing this function.
modulePath()161   StringRef modulePath() const { return ModulePath; }
162 
163   /// Get the flags for this GlobalValue (see \p struct GVFlags).
flags()164   GVFlags flags() { return Flags; }
165 
166   /// Return linkage type recorded for this global value.
linkage()167   GlobalValue::LinkageTypes linkage() const {
168     return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
169   }
170 
171   /// Sets the linkage to the value determined by global summary-based
172   /// optimization. Will be applied in the ThinLTO backends.
setLinkage(GlobalValue::LinkageTypes Linkage)173   void setLinkage(GlobalValue::LinkageTypes Linkage) {
174     Flags.Linkage = Linkage;
175   }
176 
177   /// Return true if this summary is for a GlobalValue that needs promotion
178   /// to be referenced from another module.
needsRenaming()179   bool needsRenaming() const { return GlobalValue::isLocalLinkage(linkage()); }
180 
181   /// Return true if this global value is located in a specific section.
hasSection()182   bool hasSection() const { return Flags.HasSection; }
183 
184   /// Record a reference from this global value to the global value identified
185   /// by \p RefGUID.
addRefEdge(GlobalValue::GUID RefGUID)186   void addRefEdge(GlobalValue::GUID RefGUID) { RefEdgeList.push_back(RefGUID); }
187 
188   /// Record a reference from this global value to the global value identified
189   /// by \p RefV.
addRefEdge(const Value * RefV)190   void addRefEdge(const Value *RefV) { RefEdgeList.push_back(RefV); }
191 
192   /// Record a reference from this global value to each global value identified
193   /// in \p RefEdges.
addRefEdges(DenseSet<const Value * > & RefEdges)194   void addRefEdges(DenseSet<const Value *> &RefEdges) {
195     for (auto &RI : RefEdges)
196       addRefEdge(RI);
197   }
198 
199   /// Return the list of values referenced by this global value definition.
refs()200   std::vector<ValueInfo> &refs() { return RefEdgeList; }
refs()201   const std::vector<ValueInfo> &refs() const { return RefEdgeList; }
202 };
203 
204 /// \brief Alias summary information.
205 class AliasSummary : public GlobalValueSummary {
206   GlobalValueSummary *AliaseeSummary;
207 
208 public:
209   /// Summary constructors.
AliasSummary(GVFlags Flags)210   AliasSummary(GVFlags Flags) : GlobalValueSummary(AliasKind, Flags) {}
211 
212   /// Check if this is an alias summary.
classof(const GlobalValueSummary * GVS)213   static bool classof(const GlobalValueSummary *GVS) {
214     return GVS->getSummaryKind() == AliasKind;
215   }
216 
setAliasee(GlobalValueSummary * Aliasee)217   void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
218 
getAliasee()219   const GlobalValueSummary &getAliasee() const {
220     return const_cast<AliasSummary *>(this)->getAliasee();
221   }
222 
getAliasee()223   GlobalValueSummary &getAliasee() {
224     assert(AliaseeSummary && "Unexpected missing aliasee summary");
225     return *AliaseeSummary;
226   }
227 };
228 
229 /// \brief Function summary information to aid decisions and implementation of
230 /// importing.
231 class FunctionSummary : public GlobalValueSummary {
232 public:
233   /// <CalleeValueInfo, CalleeInfo> call edge pair.
234   typedef std::pair<ValueInfo, CalleeInfo> EdgeTy;
235 
236 private:
237   /// Number of instructions (ignoring debug instructions, e.g.) computed
238   /// during the initial compile step when the summary index is first built.
239   unsigned InstCount;
240 
241   /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
242   std::vector<EdgeTy> CallGraphEdgeList;
243 
244 public:
245   /// Summary constructors.
FunctionSummary(GVFlags Flags,unsigned NumInsts)246   FunctionSummary(GVFlags Flags, unsigned NumInsts)
247       : GlobalValueSummary(FunctionKind, Flags), InstCount(NumInsts) {}
248 
249   /// Check if this is a function summary.
classof(const GlobalValueSummary * GVS)250   static bool classof(const GlobalValueSummary *GVS) {
251     return GVS->getSummaryKind() == FunctionKind;
252   }
253 
254   /// Get the instruction count recorded for this function.
instCount()255   unsigned instCount() const { return InstCount; }
256 
257   /// Record a call graph edge from this function to the function identified
258   /// by \p CalleeGUID, with \p CalleeInfo including the cumulative profile
259   /// count (across all calls from this function) or 0 if no PGO.
addCallGraphEdge(GlobalValue::GUID CalleeGUID,CalleeInfo Info)260   void addCallGraphEdge(GlobalValue::GUID CalleeGUID, CalleeInfo Info) {
261     CallGraphEdgeList.push_back(std::make_pair(CalleeGUID, Info));
262   }
263 
264   /// Record a call graph edge from this function to the function identified
265   /// by \p CalleeV, with \p CalleeInfo including the cumulative profile
266   /// count (across all calls from this function) or 0 if no PGO.
addCallGraphEdge(const Value * CalleeV,CalleeInfo Info)267   void addCallGraphEdge(const Value *CalleeV, CalleeInfo Info) {
268     CallGraphEdgeList.push_back(std::make_pair(CalleeV, Info));
269   }
270 
271   /// Record a call graph edge from this function to each function recorded
272   /// in \p CallGraphEdges.
addCallGraphEdges(DenseMap<const Value *,CalleeInfo> & CallGraphEdges)273   void addCallGraphEdges(DenseMap<const Value *, CalleeInfo> &CallGraphEdges) {
274     for (auto &EI : CallGraphEdges)
275       addCallGraphEdge(EI.first, EI.second);
276   }
277 
278   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
calls()279   std::vector<EdgeTy> &calls() { return CallGraphEdgeList; }
calls()280   const std::vector<EdgeTy> &calls() const { return CallGraphEdgeList; }
281 };
282 
283 /// \brief Global variable summary information to aid decisions and
284 /// implementation of importing.
285 ///
286 /// Currently this doesn't add anything to the base \p GlobalValueSummary,
287 /// but is a placeholder as additional info may be added to the summary
288 /// for variables.
289 class GlobalVarSummary : public GlobalValueSummary {
290 
291 public:
292   /// Summary constructors.
GlobalVarSummary(GVFlags Flags)293   GlobalVarSummary(GVFlags Flags) : GlobalValueSummary(GlobalVarKind, Flags) {}
294 
295   /// Check if this is a global variable summary.
classof(const GlobalValueSummary * GVS)296   static bool classof(const GlobalValueSummary *GVS) {
297     return GVS->getSummaryKind() == GlobalVarKind;
298   }
299 };
300 
301 /// 160 bits SHA1
302 typedef std::array<uint32_t, 5> ModuleHash;
303 
304 /// List of global value summary structures for a particular value held
305 /// in the GlobalValueMap. Requires a vector in the case of multiple
306 /// COMDAT values of the same name.
307 typedef std::vector<std::unique_ptr<GlobalValueSummary>> GlobalValueSummaryList;
308 
309 /// Map from global value GUID to corresponding summary structures.
310 /// Use a std::map rather than a DenseMap since it will likely incur
311 /// less overhead, as the value type is not very small and the size
312 /// of the map is unknown, resulting in inefficiencies due to repeated
313 /// insertions and resizing.
314 typedef std::map<GlobalValue::GUID, GlobalValueSummaryList>
315     GlobalValueSummaryMapTy;
316 
317 /// Type used for iterating through the global value summary map.
318 typedef GlobalValueSummaryMapTy::const_iterator const_gvsummary_iterator;
319 typedef GlobalValueSummaryMapTy::iterator gvsummary_iterator;
320 
321 /// String table to hold/own module path strings, which additionally holds the
322 /// module ID assigned to each module during the plugin step, as well as a hash
323 /// of the module. The StringMap makes a copy of and owns inserted strings.
324 typedef StringMap<std::pair<uint64_t, ModuleHash>> ModulePathStringTableTy;
325 
326 /// Map of global value GUID to its summary, used to identify values defined in
327 /// a particular module, and provide efficient access to their summary.
328 typedef std::map<GlobalValue::GUID, GlobalValueSummary *> GVSummaryMapTy;
329 
330 /// Class to hold module path string table and global value map,
331 /// and encapsulate methods for operating on them.
332 class ModuleSummaryIndex {
333 private:
334   /// Map from value name to list of summary instances for values of that
335   /// name (may be duplicates in the COMDAT case, e.g.).
336   GlobalValueSummaryMapTy GlobalValueMap;
337 
338   /// Holds strings for combined index, mapping to the corresponding module ID.
339   ModulePathStringTableTy ModulePathStringTable;
340 
341 public:
342   ModuleSummaryIndex() = default;
343 
344   // Disable the copy constructor and assignment operators, so
345   // no unexpected copying/moving occurs.
346   ModuleSummaryIndex(const ModuleSummaryIndex &) = delete;
347   void operator=(const ModuleSummaryIndex &) = delete;
348 
begin()349   gvsummary_iterator begin() { return GlobalValueMap.begin(); }
begin()350   const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
end()351   gvsummary_iterator end() { return GlobalValueMap.end(); }
end()352   const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
353 
354   /// Get the list of global value summary objects for a given value name.
getGlobalValueSummaryList(StringRef ValueName)355   const GlobalValueSummaryList &getGlobalValueSummaryList(StringRef ValueName) {
356     return GlobalValueMap[GlobalValue::getGUID(ValueName)];
357   }
358 
359   /// Get the list of global value summary objects for a given value name.
360   const const_gvsummary_iterator
findGlobalValueSummaryList(StringRef ValueName)361   findGlobalValueSummaryList(StringRef ValueName) const {
362     return GlobalValueMap.find(GlobalValue::getGUID(ValueName));
363   }
364 
365   /// Get the list of global value summary objects for a given value GUID.
366   const const_gvsummary_iterator
findGlobalValueSummaryList(GlobalValue::GUID ValueGUID)367   findGlobalValueSummaryList(GlobalValue::GUID ValueGUID) const {
368     return GlobalValueMap.find(ValueGUID);
369   }
370 
371   /// Add a global value summary for a value of the given name.
addGlobalValueSummary(StringRef ValueName,std::unique_ptr<GlobalValueSummary> Summary)372   void addGlobalValueSummary(StringRef ValueName,
373                              std::unique_ptr<GlobalValueSummary> Summary) {
374     GlobalValueMap[GlobalValue::getGUID(ValueName)].push_back(
375         std::move(Summary));
376   }
377 
378   /// Add a global value summary for a value of the given GUID.
addGlobalValueSummary(GlobalValue::GUID ValueGUID,std::unique_ptr<GlobalValueSummary> Summary)379   void addGlobalValueSummary(GlobalValue::GUID ValueGUID,
380                              std::unique_ptr<GlobalValueSummary> Summary) {
381     GlobalValueMap[ValueGUID].push_back(std::move(Summary));
382   }
383 
384   /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
385   /// not found.
findSummaryInModule(GlobalValue::GUID ValueGUID,StringRef ModuleId)386   GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
387                                           StringRef ModuleId) const {
388     auto CalleeInfoList = findGlobalValueSummaryList(ValueGUID);
389     if (CalleeInfoList == end()) {
390       return nullptr; // This function does not have a summary
391     }
392     auto Summary =
393         llvm::find_if(CalleeInfoList->second,
394                       [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
395                         return Summary->modulePath() == ModuleId;
396                       });
397     if (Summary == CalleeInfoList->second.end())
398       return nullptr;
399     return Summary->get();
400   }
401 
402   /// Returns the first GlobalValueSummary for \p GV, asserting that there
403   /// is only one if \p PerModuleIndex.
404   GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
405                                             bool PerModuleIndex = true) const {
406     assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
407     return getGlobalValueSummary(GlobalValue::getGUID(GV.getName()),
408                                  PerModuleIndex);
409   }
410 
411   /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
412   /// there
413   /// is only one if \p PerModuleIndex.
414   GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
415                                             bool PerModuleIndex = true) const;
416 
417   /// Table of modules, containing module hash and id.
modulePaths()418   const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
419     return ModulePathStringTable;
420   }
421 
422   /// Table of modules, containing hash and id.
modulePaths()423   StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
424     return ModulePathStringTable;
425   }
426 
427   /// Get the module ID recorded for the given module path.
getModuleId(const StringRef ModPath)428   uint64_t getModuleId(const StringRef ModPath) const {
429     return ModulePathStringTable.lookup(ModPath).first;
430   }
431 
432   /// Get the module SHA1 hash recorded for the given module path.
getModuleHash(const StringRef ModPath)433   const ModuleHash &getModuleHash(const StringRef ModPath) const {
434     auto It = ModulePathStringTable.find(ModPath);
435     assert(It != ModulePathStringTable.end() && "Module not registered");
436     return It->second.second;
437   }
438 
439   /// Add the given per-module index into this module index/summary,
440   /// assigning it the given module ID. Each module merged in should have
441   /// a unique ID, necessary for consistent renaming of promoted
442   /// static (local) variables.
443   void mergeFrom(std::unique_ptr<ModuleSummaryIndex> Other,
444                  uint64_t NextModuleId);
445 
446   /// Convenience method for creating a promoted global name
447   /// for the given value name of a local, and its original module's ID.
getGlobalNameForLocal(StringRef Name,ModuleHash ModHash)448   static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
449     SmallString<256> NewName(Name);
450     NewName += ".llvm.";
451     NewName += utohexstr(ModHash[0]); // Take the first 32 bits
452     return NewName.str();
453   }
454 
455   /// Helper to obtain the unpromoted name for a global value (or the original
456   /// name if not promoted).
getOriginalNameBeforePromote(StringRef Name)457   static StringRef getOriginalNameBeforePromote(StringRef Name) {
458     std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
459     return Pair.first;
460   }
461 
462   /// Add a new module path with the given \p Hash, mapped to the given \p
463   /// ModID, and return an iterator to the entry in the index.
464   ModulePathStringTableTy::iterator
465   addModulePath(StringRef ModPath, uint64_t ModId,
466                 ModuleHash Hash = ModuleHash{{0}}) {
467     return ModulePathStringTable.insert(std::make_pair(
468                                             ModPath,
469                                             std::make_pair(ModId, Hash))).first;
470   }
471 
472   /// Check if the given Module has any functions available for exporting
473   /// in the index. We consider any module present in the ModulePathStringTable
474   /// to have exported functions.
hasExportedFunctions(const Module & M)475   bool hasExportedFunctions(const Module &M) const {
476     return ModulePathStringTable.count(M.getModuleIdentifier());
477   }
478 
479   /// Remove entries in the GlobalValueMap that have empty summaries due to the
480   /// eager nature of map entry creation during VST parsing. These would
481   /// also be suppressed during combined index generation in mergeFrom(),
482   /// but if there was only one module or this was the first module we might
483   /// not invoke mergeFrom.
484   void removeEmptySummaryEntries();
485 
486   /// Collect for the given module the list of function it defines
487   /// (GUID -> Summary).
488   void collectDefinedFunctionsForModule(StringRef ModulePath,
489                                         GVSummaryMapTy &GVSummaryMap) const;
490 
491   /// Collect for each module the list of Summaries it defines (GUID ->
492   /// Summary).
493   void collectDefinedGVSummariesPerModule(
494       StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const;
495 };
496 
497 } // End llvm namespace
498 
499 #endif
500