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