LLVM  6.0.0svn
ModuleSummaryIndex.h
Go to the documentation of this file.
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/ArrayRef.h"
20 #include "llvm/ADT/DenseMap.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/ADT/StringRef.h"
26 #include "llvm/IR/GlobalValue.h"
27 #include "llvm/IR/Module.h"
28 #include <algorithm>
29 #include <array>
30 #include <cassert>
31 #include <cstddef>
32 #include <cstdint>
33 #include <map>
34 #include <memory>
35 #include <set>
36 #include <string>
37 #include <utility>
38 #include <vector>
39 
40 namespace llvm {
41 
42 namespace yaml {
43 
44 template <typename T> struct MappingTraits;
45 
46 } // end namespace yaml
47 
48 /// \brief Class to accumulate and hold information about a callee.
49 struct CalleeInfo {
50  enum class HotnessType : uint8_t {
51  Unknown = 0,
52  Cold = 1,
53  None = 2,
54  Hot = 3,
55  Critical = 4
56  };
58 
59  CalleeInfo() = default;
60  explicit CalleeInfo(HotnessType Hotness) : Hotness(Hotness) {}
61 
62  void updateHotness(const HotnessType OtherHotness) {
63  Hotness = std::max(Hotness, OtherHotness);
64  }
65 };
66 
67 class GlobalValueSummary;
68 
69 using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>;
70 
72  /// The GlobalValue corresponding to this summary. This is only used in
73  /// per-module summaries.
74  const GlobalValue *GV = nullptr;
75 
76  /// List of global value summary structures for a particular value held
77  /// in the GlobalValueMap. Requires a vector in the case of multiple
78  /// COMDAT values of the same name.
80 };
81 
82 /// Map from global value GUID to corresponding summary structures. Use a
83 /// std::map rather than a DenseMap so that pointers to the map's value_type
84 /// (which are used by ValueInfo) are not invalidated by insertion. Also it will
85 /// likely incur less overhead, as the value type is not very small and the size
86 /// of the map is unknown, resulting in inefficiencies due to repeated
87 /// insertions and resizing.
89  std::map<GlobalValue::GUID, GlobalValueSummaryInfo>;
90 
91 /// Struct that holds a reference to a particular GUID in a global value
92 /// summary.
93 struct ValueInfo {
94  const GlobalValueSummaryMapTy::value_type *Ref = nullptr;
95 
96  ValueInfo() = default;
97  ValueInfo(const GlobalValueSummaryMapTy::value_type *Ref) : Ref(Ref) {}
98 
99  operator bool() const { return Ref; }
100 
101  GlobalValue::GUID getGUID() const { return Ref->first; }
102  const GlobalValue *getValue() const { return Ref->second.GV; }
103 
105  return Ref->second.SummaryList;
106  }
107 };
108 
109 template <> struct DenseMapInfo<ValueInfo> {
110  static inline ValueInfo getEmptyKey() {
111  return ValueInfo((GlobalValueSummaryMapTy::value_type *)-1);
112  }
113 
114  static inline ValueInfo getTombstoneKey() {
115  return ValueInfo((GlobalValueSummaryMapTy::value_type *)-2);
116  }
117 
118  static bool isEqual(ValueInfo L, ValueInfo R) { return L.Ref == R.Ref; }
119  static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.Ref; }
120 };
121 
122 /// \brief Function and variable summary information to aid decisions and
123 /// implementation of importing.
125 public:
126  /// \brief Sububclass discriminator (for dyn_cast<> et al.)
127  enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
128 
129  /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
130  struct GVFlags {
131  /// \brief The linkage type of the associated global value.
132  ///
133  /// One use is to flag values that have local linkage types and need to
134  /// have module identifier appended before placing into the combined
135  /// index, to disambiguate from other values with the same name.
136  /// In the future this will be used to update and optimize linkage
137  /// types based on global summary-based analysis.
138  unsigned Linkage : 4;
139 
140  /// Indicate if the global value cannot be imported (e.g. it cannot
141  /// be renamed or references something that can't be renamed).
142  unsigned NotEligibleToImport : 1;
143 
144  /// In per-module summary, indicate that the global value must be considered
145  /// a live root for index-based liveness analysis. Used for special LLVM
146  /// values such as llvm.global_ctors that the linker does not know about.
147  ///
148  /// In combined summary, indicate that the global value is live.
149  unsigned Live : 1;
150 
151  /// Indicates that the linker resolved the symbol to a definition from
152  /// within the same linkage unit.
153  unsigned DSOLocal : 1;
154 
155  /// Convenience Constructors
157  bool NotEligibleToImport, bool Live, bool IsLocal)
158  : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport),
159  Live(Live), DSOLocal(IsLocal) {}
160  };
161 
162 private:
163  /// Kind of summary for use in dyn_cast<> et al.
165 
166  GVFlags Flags;
167 
168  /// This is the hash of the name of the symbol in the original file. It is
169  /// identical to the GUID for global symbols, but differs for local since the
170  /// GUID includes the module level id in the hash.
171  GlobalValue::GUID OriginalName = 0;
172 
173  /// \brief Path of module IR containing value's definition, used to locate
174  /// module during importing.
175  ///
176  /// This is only used during parsing of the combined index, or when
177  /// parsing the per-module index for creation of the combined summary index,
178  /// not during writing of the per-module index which doesn't contain a
179  /// module path string table.
180  StringRef ModulePath;
181 
182  /// List of values referenced by this global value's definition
183  /// (either by the initializer of a global variable, or referenced
184  /// from within a function). This does not include functions called, which
185  /// are listed in the derived FunctionSummary object.
186  std::vector<ValueInfo> RefEdgeList;
187 
188  bool isLive() const { return Flags.Live; }
189 
190 protected:
191  GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
192  : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {
193  assert((K != AliasKind || Refs.empty()) &&
194  "Expect no references for AliasSummary");
195  }
196 
197 public:
198  virtual ~GlobalValueSummary() = default;
199 
200  /// Returns the hash of the original name, it is identical to the GUID for
201  /// externally visible symbols, but not for local ones.
202  GlobalValue::GUID getOriginalName() { return OriginalName; }
203 
204  /// Initialize the original name hash in this summary.
205  void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
206 
207  /// Which kind of summary subclass this is.
208  SummaryKind getSummaryKind() const { return Kind; }
209 
210  /// Set the path to the module containing this function, for use in
211  /// the combined index.
212  void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
213 
214  /// Get the path to the module containing this function.
215  StringRef modulePath() const { return ModulePath; }
216 
217  /// Get the flags for this GlobalValue (see \p struct GVFlags).
218  GVFlags flags() { return Flags; }
219 
220  /// Return linkage type recorded for this global value.
222  return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
223  }
224 
225  /// Sets the linkage to the value determined by global summary-based
226  /// optimization. Will be applied in the ThinLTO backends.
228  Flags.Linkage = Linkage;
229  }
230 
231  /// Return true if this global value can't be imported.
232  bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
233 
234  void setLive(bool Live) { Flags.Live = Live; }
235 
236  void setDSOLocal(bool Local) { Flags.DSOLocal = Local; }
237 
238  bool isDSOLocal() const { return Flags.DSOLocal; }
239 
240  /// Flag that this global value cannot be imported.
242 
243  /// Return the list of values referenced by this global value definition.
244  ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
245 
246  /// If this is an alias summary, returns the summary of the aliased object (a
247  /// global variable or function), otherwise returns itself.
248  GlobalValueSummary *getBaseObject();
249 
250  friend class ModuleSummaryIndex;
251  friend void computeDeadSymbols(class ModuleSummaryIndex &,
253 };
254 
255 /// \brief Alias summary information.
257  GlobalValueSummary *AliaseeSummary;
258 
259 public:
261  : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}) {}
262 
263  /// Check if this is an alias summary.
264  static bool classof(const GlobalValueSummary *GVS) {
265  return GVS->getSummaryKind() == AliasKind;
266  }
267 
268  void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
269 
271  assert(AliaseeSummary && "Unexpected missing aliasee summary");
272  return *AliaseeSummary;
273  }
274 
276  return const_cast<GlobalValueSummary &>(
277  static_cast<const AliasSummary *>(this)->getAliasee());
278  }
279 };
280 
282  if (auto *AS = dyn_cast<AliasSummary>(this))
283  return &AS->getAliasee();
284  return this;
285 }
286 
287 /// \brief Function summary information to aid decisions and implementation of
288 /// importing.
290 public:
291  /// <CalleeValueInfo, CalleeInfo> call edge pair.
292  using EdgeTy = std::pair<ValueInfo, CalleeInfo>;
293 
294  /// An "identifier" for a virtual function. This contains the type identifier
295  /// represented as a GUID and the offset from the address point to the virtual
296  /// function pointer, where "address point" is as defined in the Itanium ABI:
297  /// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
298  struct VFuncId {
300  uint64_t Offset;
301  };
302 
303  /// A specification for a virtual function call with all constant integer
304  /// arguments. This is used to perform virtual constant propagation on the
305  /// summary.
306  struct ConstVCall {
308  std::vector<uint64_t> Args;
309  };
310 
311  /// Function attribute flags. Used to track if a function accesses memory,
312  /// recurses or aliases.
313  struct FFlags {
314  unsigned ReadNone : 1;
315  unsigned ReadOnly : 1;
316  unsigned NoRecurse : 1;
317  unsigned ReturnDoesNotAlias : 1;
318  };
319 
320 private:
321  /// Number of instructions (ignoring debug instructions, e.g.) computed
322  /// during the initial compile step when the summary index is first built.
323  unsigned InstCount;
324 
325  /// Function attribute flags. Used to track if a function accesses memory,
326  /// recurses or aliases.
327  FFlags FunFlags;
328 
329  /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
330  std::vector<EdgeTy> CallGraphEdgeList;
331 
332  /// All type identifier related information. Because these fields are
333  /// relatively uncommon we only allocate space for them if necessary.
334  struct TypeIdInfo {
335  /// List of type identifiers used by this function in llvm.type.test
336  /// intrinsics other than by an llvm.assume intrinsic, represented as GUIDs.
337  std::vector<GlobalValue::GUID> TypeTests;
338 
339  /// List of virtual calls made by this function using (respectively)
340  /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do
341  /// not have all constant integer arguments.
342  std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
343 
344  /// List of virtual calls made by this function using (respectively)
345  /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with
346  /// all constant integer arguments.
347  std::vector<ConstVCall> TypeTestAssumeConstVCalls,
348  TypeCheckedLoadConstVCalls;
349  };
350 
351  std::unique_ptr<TypeIdInfo> TIdInfo;
352 
353 public:
354  FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
355  std::vector<ValueInfo> Refs, std::vector<EdgeTy> CGEdges,
356  std::vector<GlobalValue::GUID> TypeTests,
357  std::vector<VFuncId> TypeTestAssumeVCalls,
358  std::vector<VFuncId> TypeCheckedLoadVCalls,
359  std::vector<ConstVCall> TypeTestAssumeConstVCalls,
360  std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
361  : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
362  InstCount(NumInsts), FunFlags(FunFlags),
363  CallGraphEdgeList(std::move(CGEdges)) {
364  if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
365  !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
366  !TypeCheckedLoadConstVCalls.empty())
367  TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
368  std::move(TypeTests), std::move(TypeTestAssumeVCalls),
369  std::move(TypeCheckedLoadVCalls),
370  std::move(TypeTestAssumeConstVCalls),
371  std::move(TypeCheckedLoadConstVCalls)});
372  }
373 
374  /// Check if this is a function summary.
375  static bool classof(const GlobalValueSummary *GVS) {
376  return GVS->getSummaryKind() == FunctionKind;
377  }
378 
379  /// Get function attribute flags.
380  FFlags &fflags() { return FunFlags; }
381 
382  /// Get the instruction count recorded for this function.
383  unsigned instCount() const { return InstCount; }
384 
385  /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
386  ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
387 
388  /// Returns the list of type identifiers used by this function in
389  /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
390  /// represented as GUIDs.
392  if (TIdInfo)
393  return TIdInfo->TypeTests;
394  return {};
395  }
396 
397  /// Returns the list of virtual calls made by this function using
398  /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
399  /// integer arguments.
401  if (TIdInfo)
402  return TIdInfo->TypeTestAssumeVCalls;
403  return {};
404  }
405 
406  /// Returns the list of virtual calls made by this function using
407  /// llvm.type.checked.load intrinsics that do not have all constant integer
408  /// arguments.
410  if (TIdInfo)
411  return TIdInfo->TypeCheckedLoadVCalls;
412  return {};
413  }
414 
415  /// Returns the list of virtual calls made by this function using
416  /// llvm.assume(llvm.type.test) intrinsics with all constant integer
417  /// arguments.
419  if (TIdInfo)
420  return TIdInfo->TypeTestAssumeConstVCalls;
421  return {};
422  }
423 
424  /// Returns the list of virtual calls made by this function using
425  /// llvm.type.checked.load intrinsics with all constant integer arguments.
427  if (TIdInfo)
428  return TIdInfo->TypeCheckedLoadConstVCalls;
429  return {};
430  }
431 
432  /// Add a type test to the summary. This is used by WholeProgramDevirt if we
433  /// were unable to devirtualize a checked call.
435  if (!TIdInfo)
436  TIdInfo = llvm::make_unique<TypeIdInfo>();
437  TIdInfo->TypeTests.push_back(Guid);
438  }
439 };
440 
441 template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
442  static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
443 
445  return {0, uint64_t(-2)};
446  }
447 
449  return L.GUID == R.GUID && L.Offset == R.Offset;
450  }
451 
452  static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
453 };
454 
455 template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
457  return {{0, uint64_t(-1)}, {}};
458  }
459 
461  return {{0, uint64_t(-2)}, {}};
462  }
463 
467  L.Args == R.Args;
468  }
469 
471  return I.VFunc.GUID;
472  }
473 };
474 
475 /// \brief Global variable summary information to aid decisions and
476 /// implementation of importing.
477 ///
478 /// Currently this doesn't add anything to the base \p GlobalValueSummary,
479 /// but is a placeholder as additional info may be added to the summary
480 /// for variables.
482 
483 public:
484  GlobalVarSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
485  : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)) {}
486 
487  /// Check if this is a global variable summary.
488  static bool classof(const GlobalValueSummary *GVS) {
489  return GVS->getSummaryKind() == GlobalVarKind;
490  }
491 };
492 
494  /// Specifies which kind of type check we should emit for this byte array.
495  /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
496  /// details on each kind of check; the enumerators are described with
497  /// reference to that document.
498  enum Kind {
499  Unsat, ///< Unsatisfiable type (i.e. no global has this type metadata)
500  ByteArray, ///< Test a byte array (first example)
501  Inline, ///< Inlined bit vector ("Short Inline Bit Vectors")
502  Single, ///< Single element (last example in "Short Inline Bit Vectors")
503  AllOnes, ///< All-ones bit vector ("Eliminating Bit Vector Checks for
504  /// All-Ones Bit Vectors")
505  } TheKind = Unsat;
506 
507  /// Range of size-1 expressed as a bit width. For example, if the size is in
508  /// range [1,256], this number will be 8. This helps generate the most compact
509  /// instruction sequences.
510  unsigned SizeM1BitWidth = 0;
511 
512  // The following fields are only used if the target does not support the use
513  // of absolute symbols to store constants. Their meanings are the same as the
514  // corresponding fields in LowerTypeTestsModule::TypeIdLowering in
515  // LowerTypeTests.cpp.
516 
517  uint64_t AlignLog2 = 0;
518  uint64_t SizeM1 = 0;
519  uint8_t BitMask = 0;
520  uint64_t InlineBits = 0;
521 };
522 
524  enum Kind {
525  Indir, ///< Just do a regular virtual call
526  SingleImpl, ///< Single implementation devirtualization
527  } TheKind = Indir;
528 
529  std::string SingleImplName;
530 
531  struct ByArg {
532  enum Kind {
533  Indir, ///< Just do a regular virtual call
534  UniformRetVal, ///< Uniform return value optimization
535  UniqueRetVal, ///< Unique return value optimization
536  VirtualConstProp, ///< Virtual constant propagation
537  } TheKind = Indir;
538 
539  /// Additional information for the resolution:
540  /// - UniformRetVal: the uniform return value.
541  /// - UniqueRetVal: the return value associated with the unique vtable (0 or
542  /// 1).
543  uint64_t Info = 0;
544 
545  // The following fields are only used if the target does not support the use
546  // of absolute symbols to store constants.
547 
548  uint32_t Byte = 0;
550  };
551 
552  /// Resolutions for calls with all constant integer arguments (excluding the
553  /// first argument, "this"), where the key is the argument vector.
554  std::map<std::vector<uint64_t>, ByArg> ResByArg;
555 };
556 
559 
560  /// Mapping from byte offset to whole-program devirt resolution for that
561  /// (typeid, byte offset) pair.
562  std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
563 };
564 
565 /// 160 bits SHA1
566 using ModuleHash = std::array<uint32_t, 5>;
567 
568 /// Type used for iterating through the global value summary map.
569 using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
570 using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
571 
572 /// String table to hold/own module path strings, which additionally holds the
573 /// module ID assigned to each module during the plugin step, as well as a hash
574 /// of the module. The StringMap makes a copy of and owns inserted strings.
576 
577 /// Map of global value GUID to its summary, used to identify values defined in
578 /// a particular module, and provide efficient access to their summary.
580 
581 /// Class to hold module path string table and global value map,
582 /// and encapsulate methods for operating on them.
584 private:
585  /// Map from value name to list of summary instances for values of that
586  /// name (may be duplicates in the COMDAT case, e.g.).
587  GlobalValueSummaryMapTy GlobalValueMap;
588 
589  /// Holds strings for combined index, mapping to the corresponding module ID.
590  ModulePathStringTableTy ModulePathStringTable;
591 
592  /// Mapping from type identifiers to summary information for that type
593  /// identifier.
594  // FIXME: Add bitcode read/write support for this field.
595  std::map<std::string, TypeIdSummary> TypeIdMap;
596 
597  /// Mapping from original ID to GUID. If original ID can map to multiple
598  /// GUIDs, it will be mapped to 0.
599  std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
600 
601  /// Indicates that summary-based GlobalValue GC has run, and values with
602  /// GVFlags::Live==false are really dead. Otherwise, all values must be
603  /// considered live.
604  bool WithGlobalValueDeadStripping = false;
605 
606  std::set<std::string> CfiFunctionDefs;
607  std::set<std::string> CfiFunctionDecls;
608 
609  // YAML I/O support.
611 
612  GlobalValueSummaryMapTy::value_type *
613  getOrInsertValuePtr(GlobalValue::GUID GUID) {
614  return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo{}).first;
615  }
616 
617 public:
618  gvsummary_iterator begin() { return GlobalValueMap.begin(); }
619  const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
620  gvsummary_iterator end() { return GlobalValueMap.end(); }
621  const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
622  size_t size() const { return GlobalValueMap.size(); }
623 
625  return WithGlobalValueDeadStripping;
626  }
628  WithGlobalValueDeadStripping = true;
629  }
630 
631  bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
632  return !WithGlobalValueDeadStripping || GVS->isLive();
633  }
634  bool isGUIDLive(GlobalValue::GUID GUID) const;
635 
636  /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
638  auto I = GlobalValueMap.find(GUID);
639  return ValueInfo(I == GlobalValueMap.end() ? nullptr : &*I);
640  }
641 
642  /// Return a ValueInfo for \p GUID.
644  return ValueInfo(getOrInsertValuePtr(GUID));
645  }
646 
647  /// Return a ValueInfo for \p GV and mark it as belonging to GV.
649  auto VP = getOrInsertValuePtr(GV->getGUID());
650  VP->second.GV = GV;
651  return ValueInfo(VP);
652  }
653 
654  /// Return the GUID for \p OriginalId in the OidGuidMap.
656  const auto I = OidGuidMap.find(OriginalID);
657  return I == OidGuidMap.end() ? 0 : I->second;
658  }
659 
660  std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; }
661  const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; }
662 
663  std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; }
664  const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; }
665 
666  /// Add a global value summary for a value of the given name.
668  std::unique_ptr<GlobalValueSummary> Summary) {
669  addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
670  std::move(Summary));
671  }
672 
673  /// Add a global value summary for the given ValueInfo.
675  std::unique_ptr<GlobalValueSummary> Summary) {
676  addOriginalName(VI.getGUID(), Summary->getOriginalName());
677  // Here we have a notionally const VI, but the value it points to is owned
678  // by the non-const *this.
679  const_cast<GlobalValueSummaryMapTy::value_type *>(VI.Ref)
680  ->second.SummaryList.push_back(std::move(Summary));
681  }
682 
683  /// Add an original name for the value of the given GUID.
685  GlobalValue::GUID OrigGUID) {
686  if (OrigGUID == 0 || ValueGUID == OrigGUID)
687  return;
688  if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
689  OidGuidMap[OrigGUID] = 0;
690  else
691  OidGuidMap[OrigGUID] = ValueGUID;
692  }
693 
694  /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
695  /// not found.
697  StringRef ModuleId) const {
698  auto CalleeInfo = getValueInfo(ValueGUID);
699  if (!CalleeInfo) {
700  return nullptr; // This function does not have a summary
701  }
702  auto Summary =
703  llvm::find_if(CalleeInfo.getSummaryList(),
704  [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
705  return Summary->modulePath() == ModuleId;
706  });
707  if (Summary == CalleeInfo.getSummaryList().end())
708  return nullptr;
709  return Summary->get();
710  }
711 
712  /// Returns the first GlobalValueSummary for \p GV, asserting that there
713  /// is only one if \p PerModuleIndex.
715  bool PerModuleIndex = true) const {
716  assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
717  return getGlobalValueSummary(GlobalValue::getGUID(GV.getName()),
718  PerModuleIndex);
719  }
720 
721  /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
722  /// there
723  /// is only one if \p PerModuleIndex.
724  GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
725  bool PerModuleIndex = true) const;
726 
727  /// Table of modules, containing module hash and id.
729  return ModulePathStringTable;
730  }
731 
732  /// Table of modules, containing hash and id.
734  return ModulePathStringTable;
735  }
736 
737  /// Get the module ID recorded for the given module path.
738  uint64_t getModuleId(const StringRef ModPath) const {
739  return ModulePathStringTable.lookup(ModPath).first;
740  }
741 
742  /// Get the module SHA1 hash recorded for the given module path.
743  const ModuleHash &getModuleHash(const StringRef ModPath) const {
744  auto It = ModulePathStringTable.find(ModPath);
745  assert(It != ModulePathStringTable.end() && "Module not registered");
746  return It->second.second;
747  }
748 
749  /// Convenience method for creating a promoted global name
750  /// for the given value name of a local, and its original module's ID.
751  static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
752  SmallString<256> NewName(Name);
753  NewName += ".llvm.";
754  NewName += utostr((uint64_t(ModHash[0]) << 32) |
755  ModHash[1]); // Take the first 64 bits
756  return NewName.str();
757  }
758 
759  /// Helper to obtain the unpromoted name for a global value (or the original
760  /// name if not promoted).
762  std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
763  return Pair.first;
764  }
765 
767 
768  /// Add a new module with the given \p Hash, mapped to the given \p
769  /// ModID, and return a reference to the module.
770  ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
771  ModuleHash Hash = ModuleHash{{0}}) {
772  return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first;
773  }
774 
775  /// Check if the given Module has any functions available for exporting
776  /// in the index. We consider any module present in the ModulePathStringTable
777  /// to have exported functions.
778  bool hasExportedFunctions(const Module &M) const {
779  return ModulePathStringTable.count(M.getModuleIdentifier());
780  }
781 
782  const std::map<std::string, TypeIdSummary> &typeIds() const {
783  return TypeIdMap;
784  }
785 
786  /// This accessor should only be used when exporting because it can mutate the
787  /// map.
789  return TypeIdMap[TypeId];
790  }
791 
792  /// This returns either a pointer to the type id summary (if present in the
793  /// summary map) or null (if not present). This may be used when importing.
794  const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const {
795  auto I = TypeIdMap.find(TypeId);
796  if (I == TypeIdMap.end())
797  return nullptr;
798  return &I->second;
799  }
800 
801  /// Collect for the given module the list of function it defines
802  /// (GUID -> Summary).
803  void collectDefinedFunctionsForModule(StringRef ModulePath,
804  GVSummaryMapTy &GVSummaryMap) const;
805 
806  /// Collect for each module the list of Summaries it defines (GUID ->
807  /// Summary).
808  void collectDefinedGVSummariesPerModule(
809  StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const;
810 };
811 
812 } // end namespace llvm
813 
814 #endif // LLVM_IR_MODULESUMMARYINDEX_H
static FunctionSummary::ConstVCall getEmptyKey()
const NoneType None
Definition: None.h:24
void computeDeadSymbols(ModuleSummaryIndex &Index, const DenseSet< GlobalValue::GUID > &GUIDPreservedSymbols)
Compute all the symbols that are "dead": i.e these that can&#39;t be reached in the graph from any of the...
unsigned Live
In per-module summary, indicate that the global value must be considered a live root for index-based ...
const GlobalValueSummaryMapTy::value_type * Ref
void setNotEligibleToImport()
Flag that this global value cannot be imported.
static bool classof(const GlobalValueSummary *GVS)
Check if this is an alias summary.
static FunctionSummary::ConstVCall getTombstoneKey()
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
std::vector< std::unique_ptr< GlobalValueSummary > > GlobalValueSummaryList
uint64_t GUID
Declare a type to represent a global unique identifier for a global value.
Definition: GlobalValue.h:483
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
Definition: StringMap.h:126
ValueInfo getValueInfo(GlobalValue::GUID GUID) const
Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
unsigned Linkage
The linkage type of the associated global value.
const GlobalValueSummary & getAliasee() const
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
GlobalValueSummary * findSummaryInModule(GlobalValue::GUID ValueGUID, StringRef ModuleId) const
Find the summary for global GUID in module ModuleId, or nullptr if not found.
GlobalValueSummary * getGlobalValueSummary(const GlobalValue &GV, bool PerModuleIndex=true) const
Returns the first GlobalValueSummary for GV, asserting that there is only one if PerModuleIndex.
const GlobalValue * getValue() const
ArrayRef< VFuncId > type_test_assume_vcalls() const
Returns the list of virtual calls made by this function using llvm.assume(llvm.type.test) intrinsics that do not have all constant integer arguments.
Global variable summary information to aid decisions and implementation of importing.
Unsatisfiable type (i.e. no global has this type metadata)
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
void addTypeTest(GlobalValue::GUID Guid)
Add a type test to the summary.
ArrayRef< ValueInfo > refs() const
Return the list of values referenced by this global value definition.
ValueInfo(const GlobalValueSummaryMapTy::value_type *Ref)
GlobalValueSummaryMapTy::iterator gvsummary_iterator
iterator find(StringRef Key)
Definition: StringMap.h:337
const StringMap< std::pair< uint64_t, ModuleHash > > & modulePaths() const
Table of modules, containing module hash and id.
GlobalValue::LinkageTypes linkage() const
Return linkage type recorded for this global value.
static StringRef getOriginalNameBeforePromote(StringRef Name)
Helper to obtain the unpromoted name for a global value (or the original name if not promoted)...
unsigned second
const std::set< std::string > & cfiFunctionDecls() const
bool isGlobalValueLive(const GlobalValueSummary *GVS) const
FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags, std::vector< ValueInfo > Refs, std::vector< EdgeTy > CGEdges, std::vector< GlobalValue::GUID > TypeTests, std::vector< VFuncId > TypeTestAssumeVCalls, std::vector< VFuncId > TypeCheckedLoadVCalls, std::vector< ConstVCall > TypeTestAssumeConstVCalls, std::vector< ConstVCall > TypeCheckedLoadConstVCalls)
Kind
Specifies which kind of type check we should emit for this byte array.
static unsigned getHashValue(ValueInfo I)
const TypeIdSummary * getTypeIdSummary(StringRef TypeId) const
This returns either a pointer to the type id summary (if present in the summary map) or null (if not ...
std::map< uint64_t, WholeProgramDevirtResolution > WPDRes
Mapping from byte offset to whole-program devirt resolution for that (typeid, byte offset) pair...
StringMap< std::pair< uint64_t, ModuleHash > > & modulePaths()
Table of modules, containing hash and id.
TypeTestResolution TTRes
GlobalValue::GUID getOriginalName()
Returns the hash of the original name, it is identical to the GUID for externally visible symbols...
bool hasExportedFunctions(const Module &M) const
Check if the given Module has any functions available for exporting in the index. ...
void addOriginalName(GlobalValue::GUID ValueGUID, GlobalValue::GUID OrigGUID)
Add an original name for the value of the given GUID.
static bool isEqual(ValueInfo L, ValueInfo R)
unsigned NotEligibleToImport
Indicate if the global value cannot be imported (e.g.
GlobalValue::GUID getGUID() const
Definition: BitVector.h:920
static unsigned getHashValue(FunctionSummary::VFuncId I)
GVFlags flags()
Get the flags for this GlobalValue (see struct GVFlags).
const_gvsummary_iterator begin() const
static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash)
Convenience method for creating a promoted global name for the given value name of a local...
static bool isLive(const MachineInstr &MI, const LivePhysRegs &LiveRegs, const TargetRegisterInfo *TRI, unsigned Reg)
Check if register Reg is live after the MI.
std::array< uint32_t, 5 > ModuleHash
160 bits SHA1
Just do a regular virtual call.
std::map< GlobalValue::GUID, GlobalValueSummaryInfo > GlobalValueSummaryMapTy
Map from global value GUID to corresponding summary structures.
ArrayRef< GlobalValue::GUID > type_tests() const
Returns the list of type identifiers used by this function in llvm.type.test intrinsics other than by...
StringRef str() const
Explicit conversion to StringRef.
Definition: SmallString.h:267
ArrayRef< ConstVCall > type_checked_load_const_vcalls() const
Returns the list of virtual calls made by this function using llvm.type.checked.load intrinsics with ...
const std::map< std::string, TypeIdSummary > & typeIds() const
This class should be specialized by any type that needs to be converted to/from a YAML mapping...
static bool isEqual(const Function &Caller, const Function &Callee)
ArrayRef< VFuncId > type_checked_load_vcalls() const
Returns the list of virtual calls made by this function using llvm.type.checked.load intrinsics that ...
std::pair< ValueInfo, CalleeInfo > EdgeTy
<CalleeValueInfo, CalleeInfo> call edge pair.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
TypeIdSummary & getOrInsertTypeIdSummary(StringRef TypeId)
This accessor should only be used when exporting because it can mutate the map.
ModulePathStringTableTy::value_type ModuleInfo
Class to hold module path string table and global value map, and encapsulate methods for operating on...
ArrayRef< std::unique_ptr< GlobalValueSummary > > getSummaryList() const
static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R)
CalleeInfo(HotnessType Hotness)
static unsigned getHashValue(FunctionSummary::ConstVCall I)
GlobalValueSummaryMapTy::const_iterator const_gvsummary_iterator
Type used for iterating through the global value summary map.
static FunctionSummary::VFuncId getEmptyKey()
GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const
Return the GUID for OriginalId in the OidGuidMap.
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:363
bool hasName() const
Definition: Value.h:251
static bool classof(const GlobalValueSummary *GVS)
Check if this is a global variable summary.
SummaryKind getSummaryKind() const
Which kind of summary subclass this is.
const std::set< std::string > & cfiFunctionDefs() const
unsigned instCount() const
Get the instruction count recorded for this function.
Class to accumulate and hold information about a callee.
Single element (last example in "Short Inline Bit Vectors")
const ModuleHash & getModuleHash(const StringRef ModPath) const
Get the module SHA1 hash recorded for the given module path.
ValueTy lookup(StringRef Key) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: StringMap.h:351
ValueInfo getOrInsertValueInfo(const GlobalValue *GV)
Return a ValueInfo for GV and mark it as belonging to GV.
Function and variable summary information to aid decisions and implementation of importing.
static GUID getGUID(StringRef GlobalName)
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:487
const_gvsummary_iterator end() const
const AMDGPUAS & AS
const std::string & getModuleIdentifier() const
Get the module identifier which is, essentially, the name of the module.
Definition: Module.h:208
void addGlobalValueSummary(StringRef ValueName, std::unique_ptr< GlobalValueSummary > Summary)
Add a global value summary for a value of the given name.
unsigned first
An "identifier" for a virtual function.
ArrayRef< ConstVCall > type_test_assume_const_vcalls() const
Returns the list of virtual calls made by this function using llvm.assume(llvm.type.test) intrinsics with all constant integer arguments.
void addGlobalValueSummary(ValueInfo VI, std::unique_ptr< GlobalValueSummary > Summary)
Add a global value summary for the given ValueInfo.
Struct that holds a reference to a particular GUID in a global value summary.
void updateHotness(const HotnessType OtherHotness)
ModuleInfo * addModule(StringRef ModPath, uint64_t ModId, ModuleHash Hash=ModuleHash{{0}})
Add a new module with the given Hash, mapped to the given ModID, and return a reference to the module...
static bool classof(const GlobalValueSummary *GVS)
Check if this is a function summary.
GlobalValueSummary * getBaseObject()
If this is an alias summary, returns the summary of the aliased object (a global variable or function...
Module.h This file contains the declarations for the Module class.
LLVM_NODISCARD std::pair< StringRef, StringRef > split(char Separator) const
Split into two substrings around the first occurrence of a separator character.
Definition: StringRef.h:727
Single implementation devirtualization.
uint64_t getModuleId(const StringRef ModPath) const
Get the module ID recorded for the given module path.
Alias summary information.
std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:174
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:370
A specification for a virtual function call with all constant integer arguments.
LinkageTypes
An enumeration for the kinds of linkage for global values.
Definition: GlobalValue.h:48
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:491
SummaryKind
Sububclass discriminator (for dyn_cast<> et al.)
ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID)
Return a ValueInfo for GUID.
bool withGlobalValueDeadStripping() const
GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector< ValueInfo > Refs)
std::set< std::string > & cfiFunctionDefs()
Test a byte array (first example)
GlobalVarSummary(GVFlags Flags, std::vector< ValueInfo > Refs)
std::map< std::vector< uint64_t >, ByArg > ResByArg
Resolutions for calls with all constant integer arguments (excluding the first argument, "this"), where the key is the argument vector.
StringRef modulePath() const
Get the path to the module containing this function.
void setLinkage(GlobalValue::LinkageTypes Linkage)
Sets the linkage to the value determined by global summary-based optimization.
unsigned DSOLocal
Indicates that the linker resolved the symbol to a definition from within the same linkage unit...
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
#define I(x, y, z)
Definition: MD5.cpp:58
GVFlags(GlobalValue::LinkageTypes Linkage, bool NotEligibleToImport, bool Live, bool IsLocal)
Convenience Constructors.
ArrayRef< EdgeTy > calls() const
Return the list of <CalleeValueInfo, CalleeInfo> pairs.
void setOriginalName(GlobalValue::GUID Name)
Initialize the original name hash in this summary.
Function attribute flags.
Inlined bit vector ("Short Inline Bit Vectors")
Function summary information to aid decisions and implementation of importing.
GlobalValueSummary & getAliasee()
void setModulePath(StringRef ModPath)
Set the path to the module containing this function, for use in the combined index.
const unsigned Kind
bool notEligibleToImport() const
Return true if this global value can&#39;t be imported.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::set< std::string > & cfiFunctionDecls()
static FunctionSummary::VFuncId getTombstoneKey()
gvsummary_iterator end()
void setAliasee(GlobalValueSummary *Aliasee)
Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
gvsummary_iterator begin()
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
AliasSummary(GVFlags Flags)
static bool isEqual(FunctionSummary::ConstVCall L, FunctionSummary::ConstVCall R)
auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:795
FFlags & fflags()
Get function attribute flags.
iterator end()
Definition: StringMap.h:322
GlobalValueSummaryList SummaryList
List of global value summary structures for a particular value held in the GlobalValueMap.