LLVM  8.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/ADT/TinyPtrVector.h"
27 #include "llvm/IR/GlobalValue.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/Support/Allocator.h"
33 #include <algorithm>
34 #include <array>
35 #include <cassert>
36 #include <cstddef>
37 #include <cstdint>
38 #include <map>
39 #include <memory>
40 #include <set>
41 #include <string>
42 #include <utility>
43 #include <vector>
44 
45 namespace llvm {
46 
47 namespace yaml {
48 
49 template <typename T> struct MappingTraits;
50 
51 } // end namespace yaml
52 
53 /// Class to accumulate and hold information about a callee.
54 struct CalleeInfo {
55  enum class HotnessType : uint8_t {
56  Unknown = 0,
57  Cold = 1,
58  None = 2,
59  Hot = 3,
60  Critical = 4
61  };
62 
63  // The size of the bit-field might need to be adjusted if more values are
64  // added to HotnessType enum.
66 
67  /// The value stored in RelBlockFreq has to be interpreted as the digits of
68  /// a scaled number with a scale of \p -ScaleShift.
70  static constexpr int32_t ScaleShift = 8;
71  static constexpr uint64_t MaxRelBlockFreq = (1 << 29) - 1;
72 
74  : Hotness(static_cast<uint32_t>(HotnessType::Unknown)), RelBlockFreq(0) {}
75  explicit CalleeInfo(HotnessType Hotness, uint64_t RelBF)
76  : Hotness(static_cast<uint32_t>(Hotness)), RelBlockFreq(RelBF) {}
77 
78  void updateHotness(const HotnessType OtherHotness) {
79  Hotness = std::max(Hotness, static_cast<uint32_t>(OtherHotness));
80  }
81 
82  HotnessType getHotness() const { return HotnessType(Hotness); }
83 
84  /// Update \p RelBlockFreq from \p BlockFreq and \p EntryFreq
85  ///
86  /// BlockFreq is divided by EntryFreq and added to RelBlockFreq. To represent
87  /// fractional values, the result is represented as a fixed point number with
88  /// scale of -ScaleShift.
89  void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq) {
90  if (EntryFreq == 0)
91  return;
93  Scaled64 Temp(BlockFreq, ScaleShift);
94  Temp /= Scaled64::get(EntryFreq);
95 
96  uint64_t Sum =
97  SaturatingAdd<uint64_t>(Temp.toInt<uint64_t>(), RelBlockFreq);
98  Sum = std::min(Sum, uint64_t(MaxRelBlockFreq));
99  RelBlockFreq = static_cast<uint32_t>(Sum);
100  }
101 };
102 
103 inline const char *getHotnessName(CalleeInfo::HotnessType HT) {
104  switch (HT) {
106  return "unknown";
108  return "cold";
110  return "none";
112  return "hot";
114  return "critical";
115  }
116  llvm_unreachable("invalid hotness");
117 }
118 
119 class GlobalValueSummary;
120 
121 using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>;
122 
124  union NameOrGV {
125  NameOrGV(bool HaveGVs) {
126  if (HaveGVs)
127  GV = nullptr;
128  else
129  Name = "";
130  }
131 
132  /// The GlobalValue corresponding to this summary. This is only used in
133  /// per-module summaries and when the IR is available. E.g. when module
134  /// analysis is being run, or when parsing both the IR and the summary
135  /// from assembly.
136  const GlobalValue *GV;
137 
138  /// Summary string representation. This StringRef points to BC module
139  /// string table and is valid until module data is stored in memory.
140  /// This is guaranteed to happen until runThinLTOBackend function is
141  /// called, so it is safe to use this field during thin link. This field
142  /// is only valid if summary index was loaded from BC file.
144  } U;
145 
146  GlobalValueSummaryInfo(bool HaveGVs) : U(HaveGVs) {}
147 
148  /// List of global value summary structures for a particular value held
149  /// in the GlobalValueMap. Requires a vector in the case of multiple
150  /// COMDAT values of the same name.
152 };
153 
154 /// Map from global value GUID to corresponding summary structures. Use a
155 /// std::map rather than a DenseMap so that pointers to the map's value_type
156 /// (which are used by ValueInfo) are not invalidated by insertion. Also it will
157 /// likely incur less overhead, as the value type is not very small and the size
158 /// of the map is unknown, resulting in inefficiencies due to repeated
159 /// insertions and resizing.
161  std::map<GlobalValue::GUID, GlobalValueSummaryInfo>;
162 
163 /// Struct that holds a reference to a particular GUID in a global value
164 /// summary.
165 struct ValueInfo {
168 
169  ValueInfo() = default;
170  ValueInfo(bool HaveGVs, const GlobalValueSummaryMapTy::value_type *R) {
171  RefAndFlags.setPointer(R);
172  RefAndFlags.setInt(HaveGVs);
173  }
174 
175  operator bool() const { return getRef(); }
176 
177  GlobalValue::GUID getGUID() const { return getRef()->first; }
178  const GlobalValue *getValue() const {
179  assert(haveGVs());
180  return getRef()->second.U.GV;
181  }
182 
184  return getRef()->second.SummaryList;
185  }
186 
187  StringRef name() const {
188  return haveGVs() ? getRef()->second.U.GV->getName()
189  : getRef()->second.U.Name;
190  }
191 
192  bool haveGVs() const { return RefAndFlags.getInt() & 0x1; }
193  bool isReadOnly() const { return RefAndFlags.getInt() & 0x2; }
194  void setReadOnly() { RefAndFlags.setInt(RefAndFlags.getInt() | 0x2); }
195 
196  const GlobalValueSummaryMapTy::value_type *getRef() const {
197  return RefAndFlags.getPointer();
198  }
199 
200  bool isDSOLocal() const;
201 };
202 
204  OS << VI.getGUID();
205  if (!VI.name().empty())
206  OS << " (" << VI.name() << ")";
207  return OS;
208 }
209 
210 inline bool operator==(const ValueInfo &A, const ValueInfo &B) {
211  assert(A.getRef() && B.getRef() &&
212  "Need ValueInfo with non-null Ref for comparison");
213  return A.getRef() == B.getRef();
214 }
215 
216 inline bool operator!=(const ValueInfo &A, const ValueInfo &B) {
217  assert(A.getRef() && B.getRef() &&
218  "Need ValueInfo with non-null Ref for comparison");
219  return A.getRef() != B.getRef();
220 }
221 
222 inline bool operator<(const ValueInfo &A, const ValueInfo &B) {
223  assert(A.getRef() && B.getRef() &&
224  "Need ValueInfo with non-null Ref to compare GUIDs");
225  return A.getGUID() < B.getGUID();
226 }
227 
228 template <> struct DenseMapInfo<ValueInfo> {
229  static inline ValueInfo getEmptyKey() {
230  return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8);
231  }
232 
233  static inline ValueInfo getTombstoneKey() {
234  return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-16);
235  }
236 
237  static inline bool isSpecialKey(ValueInfo V) {
238  return V == getTombstoneKey() || V == getEmptyKey();
239  }
240 
241  static bool isEqual(ValueInfo L, ValueInfo R) {
242  // We are not supposed to mix ValueInfo(s) with different HaveGVs flag
243  // in a same container.
244  assert(isSpecialKey(L) || isSpecialKey(R) || (L.haveGVs() == R.haveGVs()));
245  return L.getRef() == R.getRef();
246  }
247  static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); }
248 };
249 
250 /// Function and variable summary information to aid decisions and
251 /// implementation of importing.
253 public:
254  /// Sububclass discriminator (for dyn_cast<> et al.)
255  enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
256 
257  /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
258  struct GVFlags {
259  /// The linkage type of the associated global value.
260  ///
261  /// One use is to flag values that have local linkage types and need to
262  /// have module identifier appended before placing into the combined
263  /// index, to disambiguate from other values with the same name.
264  /// In the future this will be used to update and optimize linkage
265  /// types based on global summary-based analysis.
266  unsigned Linkage : 4;
267 
268  /// Indicate if the global value cannot be imported (e.g. it cannot
269  /// be renamed or references something that can't be renamed).
270  unsigned NotEligibleToImport : 1;
271 
272  /// In per-module summary, indicate that the global value must be considered
273  /// a live root for index-based liveness analysis. Used for special LLVM
274  /// values such as llvm.global_ctors that the linker does not know about.
275  ///
276  /// In combined summary, indicate that the global value is live.
277  unsigned Live : 1;
278 
279  /// Indicates that the linker resolved the symbol to a definition from
280  /// within the same linkage unit.
281  unsigned DSOLocal : 1;
282 
283  /// Convenience Constructors
285  bool NotEligibleToImport, bool Live, bool IsLocal)
286  : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport),
287  Live(Live), DSOLocal(IsLocal) {}
288  };
289 
290 private:
291  /// Kind of summary for use in dyn_cast<> et al.
293 
294  GVFlags Flags;
295 
296  /// This is the hash of the name of the symbol in the original file. It is
297  /// identical to the GUID for global symbols, but differs for local since the
298  /// GUID includes the module level id in the hash.
299  GlobalValue::GUID OriginalName = 0;
300 
301  /// Path of module IR containing value's definition, used to locate
302  /// module during importing.
303  ///
304  /// This is only used during parsing of the combined index, or when
305  /// parsing the per-module index for creation of the combined summary index,
306  /// not during writing of the per-module index which doesn't contain a
307  /// module path string table.
308  StringRef ModulePath;
309 
310  /// List of values referenced by this global value's definition
311  /// (either by the initializer of a global variable, or referenced
312  /// from within a function). This does not include functions called, which
313  /// are listed in the derived FunctionSummary object.
314  std::vector<ValueInfo> RefEdgeList;
315 
316 protected:
317  GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
318  : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {
319  assert((K != AliasKind || Refs.empty()) &&
320  "Expect no references for AliasSummary");
321  }
322 
323 public:
324  virtual ~GlobalValueSummary() = default;
325 
326  /// Returns the hash of the original name, it is identical to the GUID for
327  /// externally visible symbols, but not for local ones.
328  GlobalValue::GUID getOriginalName() const { return OriginalName; }
329 
330  /// Initialize the original name hash in this summary.
331  void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
332 
333  /// Which kind of summary subclass this is.
334  SummaryKind getSummaryKind() const { return Kind; }
335 
336  /// Set the path to the module containing this function, for use in
337  /// the combined index.
338  void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
339 
340  /// Get the path to the module containing this function.
341  StringRef modulePath() const { return ModulePath; }
342 
343  /// Get the flags for this GlobalValue (see \p struct GVFlags).
344  GVFlags flags() const { return Flags; }
345 
346  /// Return linkage type recorded for this global value.
348  return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
349  }
350 
351  /// Sets the linkage to the value determined by global summary-based
352  /// optimization. Will be applied in the ThinLTO backends.
354  Flags.Linkage = Linkage;
355  }
356 
357  /// Return true if this global value can't be imported.
358  bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
359 
360  bool isLive() const { return Flags.Live; }
361 
362  void setLive(bool Live) { Flags.Live = Live; }
363 
364  void setDSOLocal(bool Local) { Flags.DSOLocal = Local; }
365 
366  bool isDSOLocal() const { return Flags.DSOLocal; }
367 
368  /// Flag that this global value cannot be imported.
370 
371  /// Return the list of values referenced by this global value definition.
372  ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
373 
374  /// If this is an alias summary, returns the summary of the aliased object (a
375  /// global variable or function), otherwise returns itself.
376  GlobalValueSummary *getBaseObject();
377  const GlobalValueSummary *getBaseObject() const;
378 
379  friend class ModuleSummaryIndex;
380 };
381 
382 /// Alias summary information.
384  GlobalValueSummary *AliaseeSummary;
385  // AliaseeGUID is only set and accessed when we are building a combined index
386  // via the BitcodeReader.
387  GlobalValue::GUID AliaseeGUID;
388 
389 public:
391  : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}),
392  AliaseeSummary(nullptr), AliaseeGUID(0) {}
393 
394  /// Check if this is an alias summary.
395  static bool classof(const GlobalValueSummary *GVS) {
396  return GVS->getSummaryKind() == AliasKind;
397  }
398 
399  void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
400  void setAliaseeGUID(GlobalValue::GUID GUID) { AliaseeGUID = GUID; }
401 
402  bool hasAliasee() const { return !!AliaseeSummary; }
403 
405  assert(AliaseeSummary && "Unexpected missing aliasee summary");
406  return *AliaseeSummary;
407  }
408 
410  return const_cast<GlobalValueSummary &>(
411  static_cast<const AliasSummary *>(this)->getAliasee());
412  }
413  bool hasAliaseeGUID() const { return AliaseeGUID != 0; }
415  assert(AliaseeGUID && "Unexpected missing aliasee GUID");
416  return AliaseeGUID;
417  }
418 };
419 
421  if (auto *AS = dyn_cast<AliasSummary>(this))
422  return &AS->getAliasee();
423  return this;
424 }
425 
427  if (auto *AS = dyn_cast<AliasSummary>(this))
428  return &AS->getAliasee();
429  return this;
430 }
431 
432 /// Function summary information to aid decisions and implementation of
433 /// importing.
435 public:
436  /// <CalleeValueInfo, CalleeInfo> call edge pair.
437  using EdgeTy = std::pair<ValueInfo, CalleeInfo>;
438 
439  /// Types for -force-summary-edges-cold debugging option.
440  enum ForceSummaryHotnessType : unsigned {
443  FSHT_All
444  };
445 
446  /// An "identifier" for a virtual function. This contains the type identifier
447  /// represented as a GUID and the offset from the address point to the virtual
448  /// function pointer, where "address point" is as defined in the Itanium ABI:
449  /// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
450  struct VFuncId {
452  uint64_t Offset;
453  };
454 
455  /// A specification for a virtual function call with all constant integer
456  /// arguments. This is used to perform virtual constant propagation on the
457  /// summary.
458  struct ConstVCall {
460  std::vector<uint64_t> Args;
461  };
462 
463  /// All type identifier related information. Because these fields are
464  /// relatively uncommon we only allocate space for them if necessary.
465  struct TypeIdInfo {
466  /// List of type identifiers used by this function in llvm.type.test
467  /// intrinsics referenced by something other than an llvm.assume intrinsic,
468  /// represented as GUIDs.
469  std::vector<GlobalValue::GUID> TypeTests;
470 
471  /// List of virtual calls made by this function using (respectively)
472  /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do
473  /// not have all constant integer arguments.
474  std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
475 
476  /// List of virtual calls made by this function using (respectively)
477  /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with
478  /// all constant integer arguments.
479  std::vector<ConstVCall> TypeTestAssumeConstVCalls,
480  TypeCheckedLoadConstVCalls;
481  };
482 
483  /// Flags specific to function summaries.
484  struct FFlags {
485  // Function attribute flags. Used to track if a function accesses memory,
486  // recurses or aliases.
487  unsigned ReadNone : 1;
488  unsigned ReadOnly : 1;
489  unsigned NoRecurse : 1;
490  unsigned ReturnDoesNotAlias : 1;
491 
492  // Indicate if the global value cannot be inlined.
493  unsigned NoInline : 1;
494  };
495 
496  /// Create an empty FunctionSummary (with specified call edges).
497  /// Used to represent external nodes and the dummy root node.
498  static FunctionSummary
499  makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) {
500  return FunctionSummary(
502  GlobalValue::LinkageTypes::AvailableExternallyLinkage,
503  /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false),
504  /*InsCount=*/0, FunctionSummary::FFlags{}, /*EntryCount=*/0,
505  std::vector<ValueInfo>(), std::move(Edges),
506  std::vector<GlobalValue::GUID>(),
507  std::vector<FunctionSummary::VFuncId>(),
508  std::vector<FunctionSummary::VFuncId>(),
509  std::vector<FunctionSummary::ConstVCall>(),
510  std::vector<FunctionSummary::ConstVCall>());
511  }
512 
513  /// A dummy node to reference external functions that aren't in the index
515 
516 private:
517  /// Number of instructions (ignoring debug instructions, e.g.) computed
518  /// during the initial compile step when the summary index is first built.
519  unsigned InstCount;
520 
521  /// Function summary specific flags.
522  FFlags FunFlags;
523 
524  /// The synthesized entry count of the function.
525  /// This is only populated during ThinLink phase and remains unused while
526  /// generating per-module summaries.
527  uint64_t EntryCount = 0;
528 
529  /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
530  std::vector<EdgeTy> CallGraphEdgeList;
531 
532  std::unique_ptr<TypeIdInfo> TIdInfo;
533 
534 public:
535  FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
536  uint64_t EntryCount, std::vector<ValueInfo> Refs,
537  std::vector<EdgeTy> CGEdges,
538  std::vector<GlobalValue::GUID> TypeTests,
539  std::vector<VFuncId> TypeTestAssumeVCalls,
540  std::vector<VFuncId> TypeCheckedLoadVCalls,
541  std::vector<ConstVCall> TypeTestAssumeConstVCalls,
542  std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
543  : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
544  InstCount(NumInsts), FunFlags(FunFlags), EntryCount(EntryCount),
545  CallGraphEdgeList(std::move(CGEdges)) {
546  if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
547  !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
548  !TypeCheckedLoadConstVCalls.empty())
549  TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
550  std::move(TypeTests), std::move(TypeTestAssumeVCalls),
551  std::move(TypeCheckedLoadVCalls),
552  std::move(TypeTestAssumeConstVCalls),
553  std::move(TypeCheckedLoadConstVCalls)});
554  }
555  // Gets the number of immutable refs in RefEdgeList
556  unsigned immutableRefCount() const;
557 
558  /// Check if this is a function summary.
559  static bool classof(const GlobalValueSummary *GVS) {
560  return GVS->getSummaryKind() == FunctionKind;
561  }
562 
563  /// Get function summary flags.
564  FFlags fflags() const { return FunFlags; }
565 
566  /// Get the instruction count recorded for this function.
567  unsigned instCount() const { return InstCount; }
568 
569  /// Get the synthetic entry count for this function.
570  uint64_t entryCount() const { return EntryCount; }
571 
572  /// Set the synthetic entry count for this function.
573  void setEntryCount(uint64_t EC) { EntryCount = EC; }
574 
575  /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
576  ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
577 
578  /// Returns the list of type identifiers used by this function in
579  /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
580  /// represented as GUIDs.
582  if (TIdInfo)
583  return TIdInfo->TypeTests;
584  return {};
585  }
586 
587  /// Returns the list of virtual calls made by this function using
588  /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
589  /// integer arguments.
591  if (TIdInfo)
592  return TIdInfo->TypeTestAssumeVCalls;
593  return {};
594  }
595 
596  /// Returns the list of virtual calls made by this function using
597  /// llvm.type.checked.load intrinsics that do not have all constant integer
598  /// arguments.
600  if (TIdInfo)
601  return TIdInfo->TypeCheckedLoadVCalls;
602  return {};
603  }
604 
605  /// Returns the list of virtual calls made by this function using
606  /// llvm.assume(llvm.type.test) intrinsics with all constant integer
607  /// arguments.
609  if (TIdInfo)
610  return TIdInfo->TypeTestAssumeConstVCalls;
611  return {};
612  }
613 
614  /// Returns the list of virtual calls made by this function using
615  /// llvm.type.checked.load intrinsics with all constant integer arguments.
617  if (TIdInfo)
618  return TIdInfo->TypeCheckedLoadConstVCalls;
619  return {};
620  }
621 
622  /// Add a type test to the summary. This is used by WholeProgramDevirt if we
623  /// were unable to devirtualize a checked call.
625  if (!TIdInfo)
626  TIdInfo = llvm::make_unique<TypeIdInfo>();
627  TIdInfo->TypeTests.push_back(Guid);
628  }
629 
630  const TypeIdInfo *getTypeIdInfo() const { return TIdInfo.get(); };
631 
632  friend struct GraphTraits<ValueInfo>;
633 };
634 
635 template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
636  static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
637 
639  return {0, uint64_t(-2)};
640  }
641 
643  return L.GUID == R.GUID && L.Offset == R.Offset;
644  }
645 
646  static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
647 };
648 
649 template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
651  return {{0, uint64_t(-1)}, {}};
652  }
653 
655  return {{0, uint64_t(-2)}, {}};
656  }
657 
661  L.Args == R.Args;
662  }
663 
665  return I.VFunc.GUID;
666  }
667 };
668 
669 /// Global variable summary information to aid decisions and
670 /// implementation of importing.
671 ///
672 /// Global variable summary has extra flag, telling if it is
673 /// modified during the program run or not. This affects ThinLTO
674 /// internalization
676 public:
677  struct GVarFlags {
678  GVarFlags(bool ReadOnly = false) : ReadOnly(ReadOnly) {}
679 
680  unsigned ReadOnly : 1;
681  } VarFlags;
682 
684  std::vector<ValueInfo> Refs)
685  : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)),
686  VarFlags(VarFlags) {}
687 
688  /// Check if this is a global variable summary.
689  static bool classof(const GlobalValueSummary *GVS) {
690  return GVS->getSummaryKind() == GlobalVarKind;
691  }
692 
693  GVarFlags varflags() const { return VarFlags; }
694  void setReadOnly(bool RO) { VarFlags.ReadOnly = RO; }
695  bool isReadOnly() const { return VarFlags.ReadOnly; }
696 };
697 
699  /// Specifies which kind of type check we should emit for this byte array.
700  /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
701  /// details on each kind of check; the enumerators are described with
702  /// reference to that document.
703  enum Kind {
704  Unsat, ///< Unsatisfiable type (i.e. no global has this type metadata)
705  ByteArray, ///< Test a byte array (first example)
706  Inline, ///< Inlined bit vector ("Short Inline Bit Vectors")
707  Single, ///< Single element (last example in "Short Inline Bit Vectors")
708  AllOnes, ///< All-ones bit vector ("Eliminating Bit Vector Checks for
709  /// All-Ones Bit Vectors")
710  } TheKind = Unsat;
711 
712  /// Range of size-1 expressed as a bit width. For example, if the size is in
713  /// range [1,256], this number will be 8. This helps generate the most compact
714  /// instruction sequences.
715  unsigned SizeM1BitWidth = 0;
716 
717  // The following fields are only used if the target does not support the use
718  // of absolute symbols to store constants. Their meanings are the same as the
719  // corresponding fields in LowerTypeTestsModule::TypeIdLowering in
720  // LowerTypeTests.cpp.
721 
722  uint64_t AlignLog2 = 0;
723  uint64_t SizeM1 = 0;
724  uint8_t BitMask = 0;
725  uint64_t InlineBits = 0;
726 };
727 
729  enum Kind {
730  Indir, ///< Just do a regular virtual call
731  SingleImpl, ///< Single implementation devirtualization
732  BranchFunnel, ///< When retpoline mitigation is enabled, use a branch funnel
733  ///< that is defined in the merged module. Otherwise same as
734  ///< Indir.
735  } TheKind = Indir;
736 
737  std::string SingleImplName;
738 
739  struct ByArg {
740  enum Kind {
741  Indir, ///< Just do a regular virtual call
742  UniformRetVal, ///< Uniform return value optimization
743  UniqueRetVal, ///< Unique return value optimization
744  VirtualConstProp, ///< Virtual constant propagation
745  } TheKind = Indir;
746 
747  /// Additional information for the resolution:
748  /// - UniformRetVal: the uniform return value.
749  /// - UniqueRetVal: the return value associated with the unique vtable (0 or
750  /// 1).
751  uint64_t Info = 0;
752 
753  // The following fields are only used if the target does not support the use
754  // of absolute symbols to store constants.
755 
756  uint32_t Byte = 0;
758  };
759 
760  /// Resolutions for calls with all constant integer arguments (excluding the
761  /// first argument, "this"), where the key is the argument vector.
762  std::map<std::vector<uint64_t>, ByArg> ResByArg;
763 };
764 
767 
768  /// Mapping from byte offset to whole-program devirt resolution for that
769  /// (typeid, byte offset) pair.
770  std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
771 };
772 
773 /// 160 bits SHA1
774 using ModuleHash = std::array<uint32_t, 5>;
775 
776 /// Type used for iterating through the global value summary map.
777 using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
778 using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
779 
780 /// String table to hold/own module path strings, which additionally holds the
781 /// module ID assigned to each module during the plugin step, as well as a hash
782 /// of the module. The StringMap makes a copy of and owns inserted strings.
784 
785 /// Map of global value GUID to its summary, used to identify values defined in
786 /// a particular module, and provide efficient access to their summary.
788 
789 /// Map of a type GUID to type id string and summary (multimap used
790 /// in case of GUID conflicts).
791 using TypeIdSummaryMapTy =
792  std::multimap<GlobalValue::GUID, std::pair<std::string, TypeIdSummary>>;
793 
794 /// Class to hold module path string table and global value map,
795 /// and encapsulate methods for operating on them.
797 private:
798  /// Map from value name to list of summary instances for values of that
799  /// name (may be duplicates in the COMDAT case, e.g.).
800  GlobalValueSummaryMapTy GlobalValueMap;
801 
802  /// Holds strings for combined index, mapping to the corresponding module ID.
803  ModulePathStringTableTy ModulePathStringTable;
804 
805  /// Mapping from type identifier GUIDs to type identifier and its summary
806  /// information.
807  TypeIdSummaryMapTy TypeIdMap;
808 
809  /// Mapping from original ID to GUID. If original ID can map to multiple
810  /// GUIDs, it will be mapped to 0.
811  std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
812 
813  /// Indicates that summary-based GlobalValue GC has run, and values with
814  /// GVFlags::Live==false are really dead. Otherwise, all values must be
815  /// considered live.
816  bool WithGlobalValueDeadStripping = false;
817 
818  /// Indicates that summary-based synthetic entry count propagation has run
819  bool HasSyntheticEntryCounts = false;
820 
821  /// Indicates that distributed backend should skip compilation of the
822  /// module. Flag is suppose to be set by distributed ThinLTO indexing
823  /// when it detected that the module is not needed during the final
824  /// linking. As result distributed backend should just output a minimal
825  /// valid object file.
826  bool SkipModuleByDistributedBackend = false;
827 
828  /// If true then we're performing analysis of IR module, or parsing along with
829  /// the IR from assembly. The value of 'false' means we're reading summary
830  /// from BC or YAML source. Affects the type of value stored in NameOrGV
831  /// union.
832  bool HaveGVs;
833 
834  std::set<std::string> CfiFunctionDefs;
835  std::set<std::string> CfiFunctionDecls;
836 
837  // Used in cases where we want to record the name of a global, but
838  // don't have the string owned elsewhere (e.g. the Strtab on a module).
839  StringSaver Saver;
840  BumpPtrAllocator Alloc;
841 
842  // YAML I/O support.
844 
845  GlobalValueSummaryMapTy::value_type *
846  getOrInsertValuePtr(GlobalValue::GUID GUID) {
847  return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs))
848  .first;
849  }
850 
851 public:
852  // See HaveGVs variable comment.
853  ModuleSummaryIndex(bool HaveGVs) : HaveGVs(HaveGVs), Saver(Alloc) {}
854 
855  bool haveGVs() const { return HaveGVs; }
856 
857  gvsummary_iterator begin() { return GlobalValueMap.begin(); }
858  const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
859  gvsummary_iterator end() { return GlobalValueMap.end(); }
860  const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
861  size_t size() const { return GlobalValueMap.size(); }
862 
863  /// Convenience function for doing a DFS on a ValueInfo. Marks the function in
864  /// the FunctionHasParent map.
865  static void discoverNodes(ValueInfo V,
866  std::map<ValueInfo, bool> &FunctionHasParent) {
867  if (!V.getSummaryList().size())
868  return; // skip external functions that don't have summaries
869 
870  // Mark discovered if we haven't yet
871  auto S = FunctionHasParent.emplace(V, false);
872 
873  // Stop if we've already discovered this node
874  if (!S.second)
875  return;
876 
877  FunctionSummary *F =
878  dyn_cast<FunctionSummary>(V.getSummaryList().front().get());
879  assert(F != nullptr && "Expected FunctionSummary node");
880 
881  for (auto &C : F->calls()) {
882  // Insert node if necessary
883  auto S = FunctionHasParent.emplace(C.first, true);
884 
885  // Skip nodes that we're sure have parents
886  if (!S.second && S.first->second)
887  continue;
888 
889  if (S.second)
890  discoverNodes(C.first, FunctionHasParent);
891  else
892  S.first->second = true;
893  }
894  }
895 
896  // Calculate the callgraph root
898  // Functions that have a parent will be marked in FunctionHasParent pair.
899  // Once we've marked all functions, the functions in the map that are false
900  // have no parent (so they're the roots)
901  std::map<ValueInfo, bool> FunctionHasParent;
902 
903  for (auto &S : *this) {
904  // Skip external functions
905  if (!S.second.SummaryList.size() ||
906  !isa<FunctionSummary>(S.second.SummaryList.front().get()))
907  continue;
908  discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent);
909  }
910 
911  std::vector<FunctionSummary::EdgeTy> Edges;
912  // create edges to all roots in the Index
913  for (auto &P : FunctionHasParent) {
914  if (P.second)
915  continue; // skip over non-root nodes
916  Edges.push_back(std::make_pair(P.first, CalleeInfo{}));
917  }
918  if (Edges.empty()) {
919  // Failed to find root - return an empty node
921  }
922  auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
923  return CallGraphRoot;
924  }
925 
927  return WithGlobalValueDeadStripping;
928  }
930  WithGlobalValueDeadStripping = true;
931  }
932 
933  bool hasSyntheticEntryCounts() const { return HasSyntheticEntryCounts; }
934  void setHasSyntheticEntryCounts() { HasSyntheticEntryCounts = true; }
935 
937  return SkipModuleByDistributedBackend;
938  }
940  SkipModuleByDistributedBackend = true;
941  }
942 
943  bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
944  return !WithGlobalValueDeadStripping || GVS->isLive();
945  }
946  bool isGUIDLive(GlobalValue::GUID GUID) const;
947 
948  /// Return a ValueInfo for the index value_type (convenient when iterating
949  /// index).
950  ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const {
951  return ValueInfo(HaveGVs, &R);
952  }
953 
954  /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
955  ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
956  auto I = GlobalValueMap.find(GUID);
957  return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I);
958  }
959 
960  /// Return a ValueInfo for \p GUID.
962  return ValueInfo(HaveGVs, getOrInsertValuePtr(GUID));
963  }
964 
965  // Save a string in the Index. Use before passing Name to
966  // getOrInsertValueInfo when the string isn't owned elsewhere (e.g. on the
967  // module's Strtab).
968  StringRef saveString(StringRef String) { return Saver.save(String); }
969 
970  /// Return a ValueInfo for \p GUID setting value \p Name.
972  assert(!HaveGVs);
973  auto VP = getOrInsertValuePtr(GUID);
974  VP->second.U.Name = Name;
975  return ValueInfo(HaveGVs, VP);
976  }
977 
978  /// Return a ValueInfo for \p GV and mark it as belonging to GV.
979  ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
980  assert(HaveGVs);
981  auto VP = getOrInsertValuePtr(GV->getGUID());
982  VP->second.U.GV = GV;
983  return ValueInfo(HaveGVs, VP);
984  }
985 
986  /// Return the GUID for \p OriginalId in the OidGuidMap.
988  const auto I = OidGuidMap.find(OriginalID);
989  return I == OidGuidMap.end() ? 0 : I->second;
990  }
991 
992  std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; }
993  const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; }
994 
995  std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; }
996  const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; }
997 
998  /// Add a global value summary for a value.
1000  std::unique_ptr<GlobalValueSummary> Summary) {
1001  addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary));
1002  }
1003 
1004  /// Add a global value summary for a value of the given name.
1006  std::unique_ptr<GlobalValueSummary> Summary) {
1007  addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
1008  std::move(Summary));
1009  }
1010 
1011  /// Add a global value summary for the given ValueInfo.
1012  void addGlobalValueSummary(ValueInfo VI,
1013  std::unique_ptr<GlobalValueSummary> Summary) {
1014  addOriginalName(VI.getGUID(), Summary->getOriginalName());
1015  // Here we have a notionally const VI, but the value it points to is owned
1016  // by the non-const *this.
1017  const_cast<GlobalValueSummaryMapTy::value_type *>(VI.getRef())
1018  ->second.SummaryList.push_back(std::move(Summary));
1019  }
1020 
1021  /// Add an original name for the value of the given GUID.
1023  GlobalValue::GUID OrigGUID) {
1024  if (OrigGUID == 0 || ValueGUID == OrigGUID)
1025  return;
1026  if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
1027  OidGuidMap[OrigGUID] = 0;
1028  else
1029  OidGuidMap[OrigGUID] = ValueGUID;
1030  }
1031 
1032  /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
1033  /// not found.
1035  StringRef ModuleId) const {
1036  auto CalleeInfo = getValueInfo(ValueGUID);
1037  if (!CalleeInfo) {
1038  return nullptr; // This function does not have a summary
1039  }
1040  auto Summary =
1041  llvm::find_if(CalleeInfo.getSummaryList(),
1042  [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
1043  return Summary->modulePath() == ModuleId;
1044  });
1045  if (Summary == CalleeInfo.getSummaryList().end())
1046  return nullptr;
1047  return Summary->get();
1048  }
1049 
1050  /// Returns the first GlobalValueSummary for \p GV, asserting that there
1051  /// is only one if \p PerModuleIndex.
1053  bool PerModuleIndex = true) const {
1054  assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
1055  return getGlobalValueSummary(GV.getGUID(), PerModuleIndex);
1056  }
1057 
1058  /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
1059  /// there
1060  /// is only one if \p PerModuleIndex.
1061  GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
1062  bool PerModuleIndex = true) const;
1063 
1064  /// Table of modules, containing module hash and id.
1066  return ModulePathStringTable;
1067  }
1068 
1069  /// Table of modules, containing hash and id.
1071  return ModulePathStringTable;
1072  }
1073 
1074  /// Get the module ID recorded for the given module path.
1075  uint64_t getModuleId(const StringRef ModPath) const {
1076  return ModulePathStringTable.lookup(ModPath).first;
1077  }
1078 
1079  /// Get the module SHA1 hash recorded for the given module path.
1080  const ModuleHash &getModuleHash(const StringRef ModPath) const {
1081  auto It = ModulePathStringTable.find(ModPath);
1082  assert(It != ModulePathStringTable.end() && "Module not registered");
1083  return It->second.second;
1084  }
1085 
1086  /// Convenience method for creating a promoted global name
1087  /// for the given value name of a local, and its original module's ID.
1088  static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
1089  SmallString<256> NewName(Name);
1090  NewName += ".llvm.";
1091  NewName += utostr((uint64_t(ModHash[0]) << 32) |
1092  ModHash[1]); // Take the first 64 bits
1093  return NewName.str();
1094  }
1095 
1096  /// Helper to obtain the unpromoted name for a global value (or the original
1097  /// name if not promoted).
1099  std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
1100  return Pair.first;
1101  }
1102 
1104 
1105  /// Add a new module with the given \p Hash, mapped to the given \p
1106  /// ModID, and return a reference to the module.
1107  ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
1108  ModuleHash Hash = ModuleHash{{0}}) {
1109  return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first;
1110  }
1111 
1112  /// Return module entry for module with the given \p ModPath.
1113  ModuleInfo *getModule(StringRef ModPath) {
1114  auto It = ModulePathStringTable.find(ModPath);
1115  assert(It != ModulePathStringTable.end() && "Module not registered");
1116  return &*It;
1117  }
1118 
1119  /// Check if the given Module has any functions available for exporting
1120  /// in the index. We consider any module present in the ModulePathStringTable
1121  /// to have exported functions.
1122  bool hasExportedFunctions(const Module &M) const {
1123  return ModulePathStringTable.count(M.getModuleIdentifier());
1124  }
1125 
1126  const TypeIdSummaryMapTy &typeIds() const { return TypeIdMap; }
1127 
1128  /// Return an existing or new TypeIdSummary entry for \p TypeId.
1129  /// This accessor can mutate the map and therefore should not be used in
1130  /// the ThinLTO backends.
1132  auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1133  for (auto It = TidIter.first; It != TidIter.second; ++It)
1134  if (It->second.first == TypeId)
1135  return It->second.second;
1136  auto It = TypeIdMap.insert(
1137  {GlobalValue::getGUID(TypeId), {TypeId, TypeIdSummary()}});
1138  return It->second.second;
1139  }
1140 
1141  /// This returns either a pointer to the type id summary (if present in the
1142  /// summary map) or null (if not present). This may be used when importing.
1144  auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1145  for (auto It = TidIter.first; It != TidIter.second; ++It)
1146  if (It->second.first == TypeId)
1147  return &It->second.second;
1148  return nullptr;
1149  }
1150 
1151  /// Collect for the given module the list of functions it defines
1152  /// (GUID -> Summary).
1153  void collectDefinedFunctionsForModule(StringRef ModulePath,
1154  GVSummaryMapTy &GVSummaryMap) const;
1155 
1156  /// Collect for each module the list of Summaries it defines (GUID ->
1157  /// Summary).
1158  void collectDefinedGVSummariesPerModule(
1159  StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const;
1160 
1161  /// Print to an output stream.
1162  void print(raw_ostream &OS, bool IsForDebug = false) const;
1163 
1164  /// Dump to stderr (for debugging).
1165  void dump() const;
1166 
1167  /// Export summary to dot file for GraphViz.
1168  void exportToDot(raw_ostream& OS) const;
1169 
1170  /// Print out strongly connected components for debugging.
1171  void dumpSCCs(raw_ostream &OS);
1172 
1173  /// Analyze index and detect unmodified globals
1174  void propagateConstants(const DenseSet<GlobalValue::GUID> &PreservedSymbols);
1175 };
1176 
1177 /// GraphTraits definition to build SCC for the index
1178 template <> struct GraphTraits<ValueInfo> {
1179  typedef ValueInfo NodeRef;
1181 
1183  return P.first;
1184  }
1185  using ChildIteratorType =
1187  decltype(&valueInfoFromEdge)>;
1188 
1189  using ChildEdgeIteratorType = std::vector<FunctionSummary::EdgeTy>::iterator;
1190 
1191  static NodeRef getEntryNode(ValueInfo V) { return V; }
1192 
1193  static ChildIteratorType child_begin(NodeRef N) {
1194  if (!N.getSummaryList().size()) // handle external function
1195  return ChildIteratorType(
1196  FunctionSummary::ExternalNode.CallGraphEdgeList.begin(),
1197  &valueInfoFromEdge);
1198  FunctionSummary *F =
1199  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1200  return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge);
1201  }
1202 
1203  static ChildIteratorType child_end(NodeRef N) {
1204  if (!N.getSummaryList().size()) // handle external function
1205  return ChildIteratorType(
1206  FunctionSummary::ExternalNode.CallGraphEdgeList.end(),
1207  &valueInfoFromEdge);
1208  FunctionSummary *F =
1209  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1210  return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge);
1211  }
1212 
1214  if (!N.getSummaryList().size()) // handle external function
1215  return FunctionSummary::ExternalNode.CallGraphEdgeList.begin();
1216 
1217  FunctionSummary *F =
1218  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1219  return F->CallGraphEdgeList.begin();
1220  }
1221 
1223  if (!N.getSummaryList().size()) // handle external function
1224  return FunctionSummary::ExternalNode.CallGraphEdgeList.end();
1225 
1226  FunctionSummary *F =
1227  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1228  return F->CallGraphEdgeList.end();
1229  }
1230 
1231  static NodeRef edge_dest(EdgeRef E) { return E.first; }
1232 };
1233 
1234 template <>
1237  std::unique_ptr<GlobalValueSummary> Root =
1238  make_unique<FunctionSummary>(I->calculateCallGraphRoot());
1240  G.SummaryList.push_back(std::move(Root));
1241  static auto P =
1242  GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G));
1243  return ValueInfo(I->haveGVs(), &P);
1244  }
1245 };
1246 
1247 static inline bool canImportGlobalVar(GlobalValueSummary *S) {
1248  assert(isa<GlobalVarSummary>(S->getBaseObject()));
1249 
1250  // We don't import GV with references, because it can result
1251  // in promotion of local variables in the source module.
1253  !S->notEligibleToImport() && S->refs().empty();
1254 }
1255 } // end namespace llvm
1256 
1257 #endif // LLVM_IR_MODULESUMMARYINDEX_H
static FunctionSummary::ConstVCall getEmptyKey()
static bool isInterposableLinkage(LinkageTypes Linkage)
Whether the definition of this global may be replaced by something non-equivalent at link time...
Definition: GlobalValue.h:337
const NoneType None
Definition: None.h:24
uint64_t CallInst * C
unsigned Live
In per-module summary, indicate that the global value must be considered a live root for index-based ...
void setNotEligibleToImport()
Flag that this global value cannot be imported.
static bool classof(const GlobalValueSummary *GVS)
Check if this is an alias summary.
bool operator==(const BinaryRef &LHS, const BinaryRef &RHS)
Definition: YAML.h:99
static FunctionSummary::ConstVCall getTombstoneKey()
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
bool haveGVs() const
PointerIntPair< const GlobalValueSummaryMapTy::value_type *, 2, int > RefAndFlags
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:493
This class represents lattice values for constants.
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
StringRef Name
Summary string representation.
std::multimap< GlobalValue::GUID, std::pair< std::string, TypeIdSummary > > TypeIdSummaryMapTy
Map of a type GUID to type id string and summary (multimap used in case of GUID conflicts).
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
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:250
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.
static void discoverNodes(ValueInfo V, std::map< ValueInfo, bool > &FunctionHasParent)
Convenience function for doing a DFS on a ValueInfo.
GlobalValueSummaryMapTy::iterator gvsummary_iterator
iterator find(StringRef Key)
Definition: StringMap.h:333
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.
std::vector< VFuncId > TypeTestAssumeVCalls
List of virtual calls made by this function using (respectively) llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do not have all constant integer arguments.
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
F(f)
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.
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
TypeTestResolution TTRes
bool hasExportedFunctions(const Module &M) const
Check if the given Module has any functions available for exporting in the index. ...
static bool isSpecialKey(ValueInfo V)
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)
const GlobalValue * GV
The GlobalValue corresponding to this summary.
uint32_t RelBlockFreq
The value stored in RelBlockFreq has to be interpreted as the digits of a scaled number with a scale ...
unsigned NotEligibleToImport
Indicate if the global value cannot be imported (e.g.
GlobalValue::GUID getGUID() const
bool skipModuleByDistributedBackend() const
amdgpu Simplify well known AMD library false Value Value const Twine & Name
Definition: BitVector.h:938
ModuleInfo * getModule(StringRef ModPath)
Return module entry for module with the given ModPath.
static unsigned getHashValue(FunctionSummary::VFuncId I)
StringRef saveString(StringRef String)
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...
const TypeIdSummaryMapTy & typeIds() const
std::array< uint32_t, 5 > ModuleHash
160 bits SHA1
Just do a regular virtual call.
static bool canImportGlobalVar(GlobalValueSummary *S)
std::map< GlobalValue::GUID, GlobalValueSummaryInfo > GlobalValueSummaryMapTy
Map from global value GUID to corresponding summary structures.
bool hasAliaseeGUID() const
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 ...
static NodeRef getEntryNode(ValueInfo V)
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.
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:133
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
TypeIdSummary & getOrInsertTypeIdSummary(StringRef TypeId)
Return an existing or new TypeIdSummary entry for TypeId.
ModulePathStringTableTy::value_type ModuleInfo
Class to hold module path string table and global value map, and encapsulate methods for operating on...
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
ArrayRef< std::unique_ptr< GlobalValueSummary > > getSummaryList() const
static ChildEdgeIteratorType child_edge_end(NodeRef N)
static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R)
ForceSummaryHotnessType
Types for -force-summary-edges-cold debugging option.
static unsigned getHashValue(FunctionSummary::ConstVCall I)
GlobalValueSummaryMapTy::const_iterator const_gvsummary_iterator
Type used for iterating through the global value summary map.
#define P(N)
static FunctionSummary::VFuncId getEmptyKey()
GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const
Return the GUID for OriginalId in the OidGuidMap.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:359
bool hasName() const
Definition: Value.h:251
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:141
static bool classof(const GlobalValueSummary *GVS)
Check if this is a global variable summary.
ValueInfo(bool HaveGVs, const GlobalValueSummaryMapTy::value_type *R)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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.
CalleeInfo(HotnessType Hotness, uint64_t RelBF)
Class to accumulate and hold information about a callee.
Single element (last example in "Short Inline Bit Vectors")
StringRef name() const
GlobalVarSummary(GVFlags Flags, GVarFlags VarFlags, std::vector< ValueInfo > Refs)
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
uint64_t entryCount() const
Get the synthetic entry count for this function.
const ModuleHash & getModuleHash(const StringRef ModPath) const
Get the module SHA1 hash recorded for the given module path.
GlobalValue::GUID getOriginalName() const
Returns the hash of the original name, it is identical to the GUID for externally visible symbols...
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:347
ValueInfo getOrInsertValueInfo(const GlobalValue *GV)
Return a ValueInfo for GV and mark it as belonging to GV.
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1208
All type identifier related information.
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:497
std::vector< FunctionSummary::EdgeTy >::iterator ChildEdgeIteratorType
const_gvsummary_iterator end() const
const std::string & getModuleIdentifier() const
Get the module identifier which is, essentially, the name of the module.
Definition: Module.h:210
GVFlags flags() const
Get the flags for this GlobalValue (see struct GVFlags).
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
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.
HotnessType getHotness() const
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.
const char * getHotnessName(CalleeInfo::HotnessType HT)
GlobalValueSummary * getBaseObject()
If this is an alias summary, returns the summary of the aliased object (a global variable or function...
static ChildIteratorType child_end(NodeRef N)
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.
ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name)
Return a ValueInfo for GUID setting value Name.
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
uint64_t getModuleId(const StringRef ModPath) const
Get the module ID recorded for the given module path.
Alias summary information.
static NodeRef getEntryNode(ModuleSummaryIndex *I)
bool isReadOnly() const
std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:224
FunctionSummary::EdgeTy & EdgeRef
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:366
static FunctionSummary makeDummyFunctionSummary(std::vector< FunctionSummary::EdgeTy > Edges)
Create an empty FunctionSummary (with specified call edges).
StringRef save(const char *S)
Definition: StringSaver.h:29
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:501
SummaryKind
Sububclass discriminator (for dyn_cast<> et al.)
ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const
Return a ValueInfo for the index value_type (convenient when iterating index).
ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID)
Return a ValueInfo for GUID.
bool withGlobalValueDeadStripping() const
FFlags fflags() const
Get function summary flags.
GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector< ValueInfo > Refs)
std::set< std::string > & cfiFunctionDefs()
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1969
Test a byte array (first example)
Saves strings in the provided stable storage and returns a StringRef with a stable character pointer...
Definition: StringSaver.h:22
FunctionSummary calculateCallGraphRoot()
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...
void addGlobalValueSummary(const GlobalValue &GV, std::unique_ptr< GlobalValueSummary > Summary)
Add a global value summary for a value.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
GVFlags(GlobalValue::LinkageTypes Linkage, bool NotEligibleToImport, bool Live, bool IsLocal)
Convenience Constructors.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
ArrayRef< EdgeTy > calls() const
Return the list of <CalleeValueInfo, CalleeInfo> pairs.
void setOriginalName(GlobalValue::GUID Name)
Initialize the original name hash in this summary.
static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P)
Flags specific to function summaries.
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.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2039
const unsigned Kind
bool notEligibleToImport() const
Return true if this global value can&#39;t be imported.
FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags, uint64_t EntryCount, 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)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::set< std::string > & cfiFunctionDecls()
void setAliaseeGUID(GlobalValue::GUID GUID)
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
void setEntryCount(uint64_t EC)
Set the synthetic entry count for this function.
ScaledNumber< uint64_t > Scaled64
static FunctionSummary::VFuncId getTombstoneKey()
static ChildIteratorType child_begin(NodeRef N)
gvsummary_iterator end()
void setAliasee(GlobalValueSummary *Aliasee)
GVarFlags varflags() const
Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
gvsummary_iterator begin()
const GlobalValue::GUID & getAliaseeGUID() const
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
const GlobalValueSummaryMapTy::value_type * getRef() const
AliasSummary(GVFlags Flags)
static bool isEqual(FunctionSummary::ConstVCall L, FunctionSummary::ConstVCall R)
GraphTraits definition to build SCC for the index.
static NodeRef edge_dest(EdgeRef E)
void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq)
Update RelBlockFreq from BlockFreq and EntryFreq.
iterator end()
Definition: StringMap.h:318
GlobalValueSummaryList SummaryList
List of global value summary structures for a particular value held in the GlobalValueMap.
std::vector< GlobalValue::GUID > TypeTests
List of type identifiers used by this function in llvm.type.test intrinsics referenced by something o...
static FunctionSummary ExternalNode
A dummy node to reference external functions that aren&#39;t in the index.
std::vector< ConstVCall > TypeTestAssumeConstVCalls
List of virtual calls made by this function using (respectively) llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with all constant integer arguments.