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  ValueInfo AliaseeValueInfo;
384 
385  /// This is the Aliasee in the same module as alias (could get from VI, trades
386  /// memory for time). Note that this pointer may be null (and the value info
387  /// empty) when we have a distributed index where the alias is being imported
388  /// (as a copy of the aliasee), but the aliasee is not.
389  GlobalValueSummary *AliaseeSummary;
390 
391 public:
393  : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}),
394  AliaseeSummary(nullptr) {}
395 
396  /// Check if this is an alias summary.
397  static bool classof(const GlobalValueSummary *GVS) {
398  return GVS->getSummaryKind() == AliasKind;
399  }
400 
401  void setAliasee(ValueInfo &AliaseeVI, GlobalValueSummary *Aliasee) {
402  AliaseeValueInfo = AliaseeVI;
403  AliaseeSummary = Aliasee;
404  }
405 
406  bool hasAliasee() const {
407  assert(!!AliaseeSummary == (AliaseeValueInfo &&
408  !AliaseeValueInfo.getSummaryList().empty()) &&
409  "Expect to have both aliasee summary and summary list or neither");
410  return !!AliaseeSummary;
411  }
412 
414  assert(AliaseeSummary && "Unexpected missing aliasee summary");
415  return *AliaseeSummary;
416  }
417 
419  return const_cast<GlobalValueSummary &>(
420  static_cast<const AliasSummary *>(this)->getAliasee());
421  }
423  assert(AliaseeValueInfo && "Unexpected missing aliasee");
424  return AliaseeValueInfo;
425  }
427  assert(AliaseeValueInfo && "Unexpected missing aliasee");
428  return AliaseeValueInfo.getGUID();
429  }
430 };
431 
433  if (auto *AS = dyn_cast<AliasSummary>(this))
434  return &AS->getAliasee();
435  return this;
436 }
437 
439  if (auto *AS = dyn_cast<AliasSummary>(this))
440  return &AS->getAliasee();
441  return this;
442 }
443 
444 /// Function summary information to aid decisions and implementation of
445 /// importing.
447 public:
448  /// <CalleeValueInfo, CalleeInfo> call edge pair.
449  using EdgeTy = std::pair<ValueInfo, CalleeInfo>;
450 
451  /// Types for -force-summary-edges-cold debugging option.
452  enum ForceSummaryHotnessType : unsigned {
455  FSHT_All
456  };
457 
458  /// An "identifier" for a virtual function. This contains the type identifier
459  /// represented as a GUID and the offset from the address point to the virtual
460  /// function pointer, where "address point" is as defined in the Itanium ABI:
461  /// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
462  struct VFuncId {
464  uint64_t Offset;
465  };
466 
467  /// A specification for a virtual function call with all constant integer
468  /// arguments. This is used to perform virtual constant propagation on the
469  /// summary.
470  struct ConstVCall {
472  std::vector<uint64_t> Args;
473  };
474 
475  /// All type identifier related information. Because these fields are
476  /// relatively uncommon we only allocate space for them if necessary.
477  struct TypeIdInfo {
478  /// List of type identifiers used by this function in llvm.type.test
479  /// intrinsics referenced by something other than an llvm.assume intrinsic,
480  /// represented as GUIDs.
481  std::vector<GlobalValue::GUID> TypeTests;
482 
483  /// List of virtual calls made by this function using (respectively)
484  /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do
485  /// not have all constant integer arguments.
486  std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
487 
488  /// List of virtual calls made by this function using (respectively)
489  /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with
490  /// all constant integer arguments.
491  std::vector<ConstVCall> TypeTestAssumeConstVCalls,
492  TypeCheckedLoadConstVCalls;
493  };
494 
495  /// Flags specific to function summaries.
496  struct FFlags {
497  // Function attribute flags. Used to track if a function accesses memory,
498  // recurses or aliases.
499  unsigned ReadNone : 1;
500  unsigned ReadOnly : 1;
501  unsigned NoRecurse : 1;
502  unsigned ReturnDoesNotAlias : 1;
503 
504  // Indicate if the global value cannot be inlined.
505  unsigned NoInline : 1;
506  };
507 
508  /// Create an empty FunctionSummary (with specified call edges).
509  /// Used to represent external nodes and the dummy root node.
510  static FunctionSummary
511  makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) {
512  return FunctionSummary(
514  GlobalValue::LinkageTypes::AvailableExternallyLinkage,
515  /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false),
516  /*InsCount=*/0, FunctionSummary::FFlags{}, /*EntryCount=*/0,
517  std::vector<ValueInfo>(), std::move(Edges),
518  std::vector<GlobalValue::GUID>(),
519  std::vector<FunctionSummary::VFuncId>(),
520  std::vector<FunctionSummary::VFuncId>(),
521  std::vector<FunctionSummary::ConstVCall>(),
522  std::vector<FunctionSummary::ConstVCall>());
523  }
524 
525  /// A dummy node to reference external functions that aren't in the index
527 
528 private:
529  /// Number of instructions (ignoring debug instructions, e.g.) computed
530  /// during the initial compile step when the summary index is first built.
531  unsigned InstCount;
532 
533  /// Function summary specific flags.
534  FFlags FunFlags;
535 
536  /// The synthesized entry count of the function.
537  /// This is only populated during ThinLink phase and remains unused while
538  /// generating per-module summaries.
539  uint64_t EntryCount = 0;
540 
541  /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
542  std::vector<EdgeTy> CallGraphEdgeList;
543 
544  std::unique_ptr<TypeIdInfo> TIdInfo;
545 
546 public:
547  FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
548  uint64_t EntryCount, std::vector<ValueInfo> Refs,
549  std::vector<EdgeTy> CGEdges,
550  std::vector<GlobalValue::GUID> TypeTests,
551  std::vector<VFuncId> TypeTestAssumeVCalls,
552  std::vector<VFuncId> TypeCheckedLoadVCalls,
553  std::vector<ConstVCall> TypeTestAssumeConstVCalls,
554  std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
555  : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
556  InstCount(NumInsts), FunFlags(FunFlags), EntryCount(EntryCount),
557  CallGraphEdgeList(std::move(CGEdges)) {
558  if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
559  !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
560  !TypeCheckedLoadConstVCalls.empty())
561  TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
562  std::move(TypeTests), std::move(TypeTestAssumeVCalls),
563  std::move(TypeCheckedLoadVCalls),
564  std::move(TypeTestAssumeConstVCalls),
565  std::move(TypeCheckedLoadConstVCalls)});
566  }
567  // Gets the number of immutable refs in RefEdgeList
568  unsigned immutableRefCount() const;
569 
570  /// Check if this is a function summary.
571  static bool classof(const GlobalValueSummary *GVS) {
572  return GVS->getSummaryKind() == FunctionKind;
573  }
574 
575  /// Get function summary flags.
576  FFlags fflags() const { return FunFlags; }
577 
578  /// Get the instruction count recorded for this function.
579  unsigned instCount() const { return InstCount; }
580 
581  /// Get the synthetic entry count for this function.
582  uint64_t entryCount() const { return EntryCount; }
583 
584  /// Set the synthetic entry count for this function.
585  void setEntryCount(uint64_t EC) { EntryCount = EC; }
586 
587  /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
588  ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
589 
590  /// Returns the list of type identifiers used by this function in
591  /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
592  /// represented as GUIDs.
594  if (TIdInfo)
595  return TIdInfo->TypeTests;
596  return {};
597  }
598 
599  /// Returns the list of virtual calls made by this function using
600  /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
601  /// integer arguments.
603  if (TIdInfo)
604  return TIdInfo->TypeTestAssumeVCalls;
605  return {};
606  }
607 
608  /// Returns the list of virtual calls made by this function using
609  /// llvm.type.checked.load intrinsics that do not have all constant integer
610  /// arguments.
612  if (TIdInfo)
613  return TIdInfo->TypeCheckedLoadVCalls;
614  return {};
615  }
616 
617  /// Returns the list of virtual calls made by this function using
618  /// llvm.assume(llvm.type.test) intrinsics with all constant integer
619  /// arguments.
621  if (TIdInfo)
622  return TIdInfo->TypeTestAssumeConstVCalls;
623  return {};
624  }
625 
626  /// Returns the list of virtual calls made by this function using
627  /// llvm.type.checked.load intrinsics with all constant integer arguments.
629  if (TIdInfo)
630  return TIdInfo->TypeCheckedLoadConstVCalls;
631  return {};
632  }
633 
634  /// Add a type test to the summary. This is used by WholeProgramDevirt if we
635  /// were unable to devirtualize a checked call.
637  if (!TIdInfo)
638  TIdInfo = llvm::make_unique<TypeIdInfo>();
639  TIdInfo->TypeTests.push_back(Guid);
640  }
641 
642  const TypeIdInfo *getTypeIdInfo() const { return TIdInfo.get(); };
643 
644  friend struct GraphTraits<ValueInfo>;
645 };
646 
647 template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
648  static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
649 
651  return {0, uint64_t(-2)};
652  }
653 
655  return L.GUID == R.GUID && L.Offset == R.Offset;
656  }
657 
658  static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
659 };
660 
661 template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
663  return {{0, uint64_t(-1)}, {}};
664  }
665 
667  return {{0, uint64_t(-2)}, {}};
668  }
669 
673  L.Args == R.Args;
674  }
675 
677  return I.VFunc.GUID;
678  }
679 };
680 
681 /// Global variable summary information to aid decisions and
682 /// implementation of importing.
683 ///
684 /// Global variable summary has extra flag, telling if it is
685 /// modified during the program run or not. This affects ThinLTO
686 /// internalization
688 public:
689  struct GVarFlags {
690  GVarFlags(bool ReadOnly = false) : ReadOnly(ReadOnly) {}
691 
692  unsigned ReadOnly : 1;
693  } VarFlags;
694 
696  std::vector<ValueInfo> Refs)
697  : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)),
698  VarFlags(VarFlags) {}
699 
700  /// Check if this is a global variable summary.
701  static bool classof(const GlobalValueSummary *GVS) {
702  return GVS->getSummaryKind() == GlobalVarKind;
703  }
704 
705  GVarFlags varflags() const { return VarFlags; }
706  void setReadOnly(bool RO) { VarFlags.ReadOnly = RO; }
707  bool isReadOnly() const { return VarFlags.ReadOnly; }
708 };
709 
711  /// Specifies which kind of type check we should emit for this byte array.
712  /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
713  /// details on each kind of check; the enumerators are described with
714  /// reference to that document.
715  enum Kind {
716  Unsat, ///< Unsatisfiable type (i.e. no global has this type metadata)
717  ByteArray, ///< Test a byte array (first example)
718  Inline, ///< Inlined bit vector ("Short Inline Bit Vectors")
719  Single, ///< Single element (last example in "Short Inline Bit Vectors")
720  AllOnes, ///< All-ones bit vector ("Eliminating Bit Vector Checks for
721  /// All-Ones Bit Vectors")
722  } TheKind = Unsat;
723 
724  /// Range of size-1 expressed as a bit width. For example, if the size is in
725  /// range [1,256], this number will be 8. This helps generate the most compact
726  /// instruction sequences.
727  unsigned SizeM1BitWidth = 0;
728 
729  // The following fields are only used if the target does not support the use
730  // of absolute symbols to store constants. Their meanings are the same as the
731  // corresponding fields in LowerTypeTestsModule::TypeIdLowering in
732  // LowerTypeTests.cpp.
733 
734  uint64_t AlignLog2 = 0;
735  uint64_t SizeM1 = 0;
736  uint8_t BitMask = 0;
737  uint64_t InlineBits = 0;
738 };
739 
741  enum Kind {
742  Indir, ///< Just do a regular virtual call
743  SingleImpl, ///< Single implementation devirtualization
744  BranchFunnel, ///< When retpoline mitigation is enabled, use a branch funnel
745  ///< that is defined in the merged module. Otherwise same as
746  ///< Indir.
747  } TheKind = Indir;
748 
749  std::string SingleImplName;
750 
751  struct ByArg {
752  enum Kind {
753  Indir, ///< Just do a regular virtual call
754  UniformRetVal, ///< Uniform return value optimization
755  UniqueRetVal, ///< Unique return value optimization
756  VirtualConstProp, ///< Virtual constant propagation
757  } TheKind = Indir;
758 
759  /// Additional information for the resolution:
760  /// - UniformRetVal: the uniform return value.
761  /// - UniqueRetVal: the return value associated with the unique vtable (0 or
762  /// 1).
763  uint64_t Info = 0;
764 
765  // The following fields are only used if the target does not support the use
766  // of absolute symbols to store constants.
767 
768  uint32_t Byte = 0;
770  };
771 
772  /// Resolutions for calls with all constant integer arguments (excluding the
773  /// first argument, "this"), where the key is the argument vector.
774  std::map<std::vector<uint64_t>, ByArg> ResByArg;
775 };
776 
779 
780  /// Mapping from byte offset to whole-program devirt resolution for that
781  /// (typeid, byte offset) pair.
782  std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
783 };
784 
785 /// 160 bits SHA1
786 using ModuleHash = std::array<uint32_t, 5>;
787 
788 /// Type used for iterating through the global value summary map.
789 using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
790 using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
791 
792 /// String table to hold/own module path strings, which additionally holds the
793 /// module ID assigned to each module during the plugin step, as well as a hash
794 /// of the module. The StringMap makes a copy of and owns inserted strings.
796 
797 /// Map of global value GUID to its summary, used to identify values defined in
798 /// a particular module, and provide efficient access to their summary.
800 
801 /// Map of a type GUID to type id string and summary (multimap used
802 /// in case of GUID conflicts).
803 using TypeIdSummaryMapTy =
804  std::multimap<GlobalValue::GUID, std::pair<std::string, TypeIdSummary>>;
805 
806 /// Class to hold module path string table and global value map,
807 /// and encapsulate methods for operating on them.
809 private:
810  /// Map from value name to list of summary instances for values of that
811  /// name (may be duplicates in the COMDAT case, e.g.).
812  GlobalValueSummaryMapTy GlobalValueMap;
813 
814  /// Holds strings for combined index, mapping to the corresponding module ID.
815  ModulePathStringTableTy ModulePathStringTable;
816 
817  /// Mapping from type identifier GUIDs to type identifier and its summary
818  /// information.
819  TypeIdSummaryMapTy TypeIdMap;
820 
821  /// Mapping from original ID to GUID. If original ID can map to multiple
822  /// GUIDs, it will be mapped to 0.
823  std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
824 
825  /// Indicates that summary-based GlobalValue GC has run, and values with
826  /// GVFlags::Live==false are really dead. Otherwise, all values must be
827  /// considered live.
828  bool WithGlobalValueDeadStripping = false;
829 
830  /// Indicates that summary-based synthetic entry count propagation has run
831  bool HasSyntheticEntryCounts = false;
832 
833  /// Indicates that distributed backend should skip compilation of the
834  /// module. Flag is suppose to be set by distributed ThinLTO indexing
835  /// when it detected that the module is not needed during the final
836  /// linking. As result distributed backend should just output a minimal
837  /// valid object file.
838  bool SkipModuleByDistributedBackend = false;
839 
840  /// If true then we're performing analysis of IR module, or parsing along with
841  /// the IR from assembly. The value of 'false' means we're reading summary
842  /// from BC or YAML source. Affects the type of value stored in NameOrGV
843  /// union.
844  bool HaveGVs;
845 
846  // True if the index was created for a module compiled with -fsplit-lto-unit.
847  bool EnableSplitLTOUnit;
848 
849  // True if some of the modules were compiled with -fsplit-lto-unit and
850  // some were not. Set when the combined index is created during the thin link.
851  bool PartiallySplitLTOUnits = false;
852 
853  std::set<std::string> CfiFunctionDefs;
854  std::set<std::string> CfiFunctionDecls;
855 
856  // Used in cases where we want to record the name of a global, but
857  // don't have the string owned elsewhere (e.g. the Strtab on a module).
858  StringSaver Saver;
859  BumpPtrAllocator Alloc;
860 
861  // YAML I/O support.
863 
864  GlobalValueSummaryMapTy::value_type *
865  getOrInsertValuePtr(GlobalValue::GUID GUID) {
866  return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs))
867  .first;
868  }
869 
870 public:
871  // See HaveGVs variable comment.
872  ModuleSummaryIndex(bool HaveGVs, bool EnableSplitLTOUnit = false)
873  : HaveGVs(HaveGVs), EnableSplitLTOUnit(EnableSplitLTOUnit), Saver(Alloc) {
874  }
875 
876  bool haveGVs() const { return HaveGVs; }
877 
878  gvsummary_iterator begin() { return GlobalValueMap.begin(); }
879  const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
880  gvsummary_iterator end() { return GlobalValueMap.end(); }
881  const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
882  size_t size() const { return GlobalValueMap.size(); }
883 
884  /// Convenience function for doing a DFS on a ValueInfo. Marks the function in
885  /// the FunctionHasParent map.
886  static void discoverNodes(ValueInfo V,
887  std::map<ValueInfo, bool> &FunctionHasParent) {
888  if (!V.getSummaryList().size())
889  return; // skip external functions that don't have summaries
890 
891  // Mark discovered if we haven't yet
892  auto S = FunctionHasParent.emplace(V, false);
893 
894  // Stop if we've already discovered this node
895  if (!S.second)
896  return;
897 
898  FunctionSummary *F =
899  dyn_cast<FunctionSummary>(V.getSummaryList().front().get());
900  assert(F != nullptr && "Expected FunctionSummary node");
901 
902  for (auto &C : F->calls()) {
903  // Insert node if necessary
904  auto S = FunctionHasParent.emplace(C.first, true);
905 
906  // Skip nodes that we're sure have parents
907  if (!S.second && S.first->second)
908  continue;
909 
910  if (S.second)
911  discoverNodes(C.first, FunctionHasParent);
912  else
913  S.first->second = true;
914  }
915  }
916 
917  // Calculate the callgraph root
919  // Functions that have a parent will be marked in FunctionHasParent pair.
920  // Once we've marked all functions, the functions in the map that are false
921  // have no parent (so they're the roots)
922  std::map<ValueInfo, bool> FunctionHasParent;
923 
924  for (auto &S : *this) {
925  // Skip external functions
926  if (!S.second.SummaryList.size() ||
927  !isa<FunctionSummary>(S.second.SummaryList.front().get()))
928  continue;
929  discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent);
930  }
931 
932  std::vector<FunctionSummary::EdgeTy> Edges;
933  // create edges to all roots in the Index
934  for (auto &P : FunctionHasParent) {
935  if (P.second)
936  continue; // skip over non-root nodes
937  Edges.push_back(std::make_pair(P.first, CalleeInfo{}));
938  }
939  if (Edges.empty()) {
940  // Failed to find root - return an empty node
942  }
943  auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
944  return CallGraphRoot;
945  }
946 
948  return WithGlobalValueDeadStripping;
949  }
951  WithGlobalValueDeadStripping = true;
952  }
953 
954  bool hasSyntheticEntryCounts() const { return HasSyntheticEntryCounts; }
955  void setHasSyntheticEntryCounts() { HasSyntheticEntryCounts = true; }
956 
958  return SkipModuleByDistributedBackend;
959  }
961  SkipModuleByDistributedBackend = true;
962  }
963 
964  bool enableSplitLTOUnit() const { return EnableSplitLTOUnit; }
965  void setEnableSplitLTOUnit() { EnableSplitLTOUnit = true; }
966 
967  bool partiallySplitLTOUnits() const { return PartiallySplitLTOUnits; }
968  void setPartiallySplitLTOUnits() { PartiallySplitLTOUnits = true; }
969 
970  bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
971  return !WithGlobalValueDeadStripping || GVS->isLive();
972  }
973  bool isGUIDLive(GlobalValue::GUID GUID) const;
974 
975  /// Return a ValueInfo for the index value_type (convenient when iterating
976  /// index).
977  ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const {
978  return ValueInfo(HaveGVs, &R);
979  }
980 
981  /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
982  ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
983  auto I = GlobalValueMap.find(GUID);
984  return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I);
985  }
986 
987  /// Return a ValueInfo for \p GUID.
989  return ValueInfo(HaveGVs, getOrInsertValuePtr(GUID));
990  }
991 
992  // Save a string in the Index. Use before passing Name to
993  // getOrInsertValueInfo when the string isn't owned elsewhere (e.g. on the
994  // module's Strtab).
995  StringRef saveString(StringRef String) { return Saver.save(String); }
996 
997  /// Return a ValueInfo for \p GUID setting value \p Name.
999  assert(!HaveGVs);
1000  auto VP = getOrInsertValuePtr(GUID);
1001  VP->second.U.Name = Name;
1002  return ValueInfo(HaveGVs, VP);
1003  }
1004 
1005  /// Return a ValueInfo for \p GV and mark it as belonging to GV.
1006  ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
1007  assert(HaveGVs);
1008  auto VP = getOrInsertValuePtr(GV->getGUID());
1009  VP->second.U.GV = GV;
1010  return ValueInfo(HaveGVs, VP);
1011  }
1012 
1013  /// Return the GUID for \p OriginalId in the OidGuidMap.
1015  const auto I = OidGuidMap.find(OriginalID);
1016  return I == OidGuidMap.end() ? 0 : I->second;
1017  }
1018 
1019  std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; }
1020  const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; }
1021 
1022  std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; }
1023  const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; }
1024 
1025  /// Add a global value summary for a value.
1027  std::unique_ptr<GlobalValueSummary> Summary) {
1028  addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary));
1029  }
1030 
1031  /// Add a global value summary for a value of the given name.
1033  std::unique_ptr<GlobalValueSummary> Summary) {
1034  addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
1035  std::move(Summary));
1036  }
1037 
1038  /// Add a global value summary for the given ValueInfo.
1039  void addGlobalValueSummary(ValueInfo VI,
1040  std::unique_ptr<GlobalValueSummary> Summary) {
1041  addOriginalName(VI.getGUID(), Summary->getOriginalName());
1042  // Here we have a notionally const VI, but the value it points to is owned
1043  // by the non-const *this.
1044  const_cast<GlobalValueSummaryMapTy::value_type *>(VI.getRef())
1045  ->second.SummaryList.push_back(std::move(Summary));
1046  }
1047 
1048  /// Add an original name for the value of the given GUID.
1050  GlobalValue::GUID OrigGUID) {
1051  if (OrigGUID == 0 || ValueGUID == OrigGUID)
1052  return;
1053  if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
1054  OidGuidMap[OrigGUID] = 0;
1055  else
1056  OidGuidMap[OrigGUID] = ValueGUID;
1057  }
1058 
1059  /// Find the summary for ValueInfo \p VI in module \p ModuleId, or nullptr if
1060  /// not found.
1061  GlobalValueSummary *findSummaryInModule(ValueInfo VI, StringRef ModuleId) const {
1062  auto SummaryList = VI.getSummaryList();
1063  auto Summary =
1064  llvm::find_if(SummaryList,
1065  [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
1066  return Summary->modulePath() == ModuleId;
1067  });
1068  if (Summary == SummaryList.end())
1069  return nullptr;
1070  return Summary->get();
1071  }
1072 
1073  /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
1074  /// not found.
1076  StringRef ModuleId) const {
1077  auto CalleeInfo = getValueInfo(ValueGUID);
1078  if (!CalleeInfo)
1079  return nullptr; // This function does not have a summary
1080  return findSummaryInModule(CalleeInfo, ModuleId);
1081  }
1082 
1083  /// Returns the first GlobalValueSummary for \p GV, asserting that there
1084  /// is only one if \p PerModuleIndex.
1086  bool PerModuleIndex = true) const {
1087  assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
1088  return getGlobalValueSummary(GV.getGUID(), PerModuleIndex);
1089  }
1090 
1091  /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
1092  /// there
1093  /// is only one if \p PerModuleIndex.
1094  GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
1095  bool PerModuleIndex = true) const;
1096 
1097  /// Table of modules, containing module hash and id.
1099  return ModulePathStringTable;
1100  }
1101 
1102  /// Table of modules, containing hash and id.
1104  return ModulePathStringTable;
1105  }
1106 
1107  /// Get the module ID recorded for the given module path.
1108  uint64_t getModuleId(const StringRef ModPath) const {
1109  return ModulePathStringTable.lookup(ModPath).first;
1110  }
1111 
1112  /// Get the module SHA1 hash recorded for the given module path.
1113  const ModuleHash &getModuleHash(const StringRef ModPath) const {
1114  auto It = ModulePathStringTable.find(ModPath);
1115  assert(It != ModulePathStringTable.end() && "Module not registered");
1116  return It->second.second;
1117  }
1118 
1119  /// Convenience method for creating a promoted global name
1120  /// for the given value name of a local, and its original module's ID.
1121  static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
1122  SmallString<256> NewName(Name);
1123  NewName += ".llvm.";
1124  NewName += utostr((uint64_t(ModHash[0]) << 32) |
1125  ModHash[1]); // Take the first 64 bits
1126  return NewName.str();
1127  }
1128 
1129  /// Helper to obtain the unpromoted name for a global value (or the original
1130  /// name if not promoted).
1132  std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
1133  return Pair.first;
1134  }
1135 
1137 
1138  /// Add a new module with the given \p Hash, mapped to the given \p
1139  /// ModID, and return a reference to the module.
1140  ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
1141  ModuleHash Hash = ModuleHash{{0}}) {
1142  return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first;
1143  }
1144 
1145  /// Return module entry for module with the given \p ModPath.
1146  ModuleInfo *getModule(StringRef ModPath) {
1147  auto It = ModulePathStringTable.find(ModPath);
1148  assert(It != ModulePathStringTable.end() && "Module not registered");
1149  return &*It;
1150  }
1151 
1152  /// Check if the given Module has any functions available for exporting
1153  /// in the index. We consider any module present in the ModulePathStringTable
1154  /// to have exported functions.
1155  bool hasExportedFunctions(const Module &M) const {
1156  return ModulePathStringTable.count(M.getModuleIdentifier());
1157  }
1158 
1159  const TypeIdSummaryMapTy &typeIds() const { return TypeIdMap; }
1160 
1161  /// Return an existing or new TypeIdSummary entry for \p TypeId.
1162  /// This accessor can mutate the map and therefore should not be used in
1163  /// the ThinLTO backends.
1165  auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1166  for (auto It = TidIter.first; It != TidIter.second; ++It)
1167  if (It->second.first == TypeId)
1168  return It->second.second;
1169  auto It = TypeIdMap.insert(
1170  {GlobalValue::getGUID(TypeId), {TypeId, TypeIdSummary()}});
1171  return It->second.second;
1172  }
1173 
1174  /// This returns either a pointer to the type id summary (if present in the
1175  /// summary map) or null (if not present). This may be used when importing.
1177  auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1178  for (auto It = TidIter.first; It != TidIter.second; ++It)
1179  if (It->second.first == TypeId)
1180  return &It->second.second;
1181  return nullptr;
1182  }
1183 
1184  /// Collect for the given module the list of functions it defines
1185  /// (GUID -> Summary).
1186  void collectDefinedFunctionsForModule(StringRef ModulePath,
1187  GVSummaryMapTy &GVSummaryMap) const;
1188 
1189  /// Collect for each module the list of Summaries it defines (GUID ->
1190  /// Summary).
1191  template <class Map>
1192  void
1193  collectDefinedGVSummariesPerModule(Map &ModuleToDefinedGVSummaries) const {
1194  for (auto &GlobalList : *this) {
1195  auto GUID = GlobalList.first;
1196  for (auto &Summary : GlobalList.second.SummaryList) {
1197  ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
1198  }
1199  }
1200  }
1201 
1202  /// Print to an output stream.
1203  void print(raw_ostream &OS, bool IsForDebug = false) const;
1204 
1205  /// Dump to stderr (for debugging).
1206  void dump() const;
1207 
1208  /// Export summary to dot file for GraphViz.
1209  void exportToDot(raw_ostream& OS) const;
1210 
1211  /// Print out strongly connected components for debugging.
1212  void dumpSCCs(raw_ostream &OS);
1213 
1214  /// Analyze index and detect unmodified globals
1215  void propagateConstants(const DenseSet<GlobalValue::GUID> &PreservedSymbols);
1216 };
1217 
1218 /// GraphTraits definition to build SCC for the index
1219 template <> struct GraphTraits<ValueInfo> {
1220  typedef ValueInfo NodeRef;
1222 
1224  return P.first;
1225  }
1226  using ChildIteratorType =
1228  decltype(&valueInfoFromEdge)>;
1229 
1230  using ChildEdgeIteratorType = std::vector<FunctionSummary::EdgeTy>::iterator;
1231 
1232  static NodeRef getEntryNode(ValueInfo V) { return V; }
1233 
1234  static ChildIteratorType child_begin(NodeRef N) {
1235  if (!N.getSummaryList().size()) // handle external function
1236  return ChildIteratorType(
1237  FunctionSummary::ExternalNode.CallGraphEdgeList.begin(),
1238  &valueInfoFromEdge);
1239  FunctionSummary *F =
1240  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1241  return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge);
1242  }
1243 
1244  static ChildIteratorType child_end(NodeRef N) {
1245  if (!N.getSummaryList().size()) // handle external function
1246  return ChildIteratorType(
1247  FunctionSummary::ExternalNode.CallGraphEdgeList.end(),
1248  &valueInfoFromEdge);
1249  FunctionSummary *F =
1250  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1251  return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge);
1252  }
1253 
1255  if (!N.getSummaryList().size()) // handle external function
1256  return FunctionSummary::ExternalNode.CallGraphEdgeList.begin();
1257 
1258  FunctionSummary *F =
1259  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1260  return F->CallGraphEdgeList.begin();
1261  }
1262 
1264  if (!N.getSummaryList().size()) // handle external function
1265  return FunctionSummary::ExternalNode.CallGraphEdgeList.end();
1266 
1267  FunctionSummary *F =
1268  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1269  return F->CallGraphEdgeList.end();
1270  }
1271 
1272  static NodeRef edge_dest(EdgeRef E) { return E.first; }
1273 };
1274 
1275 template <>
1278  std::unique_ptr<GlobalValueSummary> Root =
1279  make_unique<FunctionSummary>(I->calculateCallGraphRoot());
1281  G.SummaryList.push_back(std::move(Root));
1282  static auto P =
1283  GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G));
1284  return ValueInfo(I->haveGVs(), &P);
1285  }
1286 };
1287 
1288 static inline bool canImportGlobalVar(GlobalValueSummary *S) {
1289  assert(isa<GlobalVarSummary>(S->getBaseObject()));
1290 
1291  // We don't import GV with references, because it can result
1292  // in promotion of local variables in the source module.
1294  !S->notEligibleToImport() && S->refs().empty();
1295 }
1296 } // end namespace llvm
1297 
1298 #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:97
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:65
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
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)
GlobalValue::GUID getAliaseeGUID() const
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: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:696
Single implementation devirtualization.
ValueInfo getAliaseeVI() const
ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name)
Return a ValueInfo for GUID setting value Name.
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
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.
void setAliasee(ValueInfo &AliaseeVI, GlobalValueSummary *Aliasee)
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:332
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.
GlobalValueSummary * findSummaryInModule(ValueInfo VI, StringRef ModuleId) const
Find the summary for ValueInfo VI in module ModuleId, or nullptr if not found.
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
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 collectDefinedGVSummariesPerModule(Map &ModuleToDefinedGVSummaries) const
Collect for each module the list of Summaries it defines (GUID -> Summary).
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()
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()
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.