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  /// Checks if all copies are eligible for auto-hiding (have flag set).
202  bool canAutoHide() const;
203 };
204 
206  OS << VI.getGUID();
207  if (!VI.name().empty())
208  OS << " (" << VI.name() << ")";
209  return OS;
210 }
211 
212 inline bool operator==(const ValueInfo &A, const ValueInfo &B) {
213  assert(A.getRef() && B.getRef() &&
214  "Need ValueInfo with non-null Ref for comparison");
215  return A.getRef() == B.getRef();
216 }
217 
218 inline bool operator!=(const ValueInfo &A, const ValueInfo &B) {
219  assert(A.getRef() && B.getRef() &&
220  "Need ValueInfo with non-null Ref for comparison");
221  return A.getRef() != B.getRef();
222 }
223 
224 inline bool operator<(const ValueInfo &A, const ValueInfo &B) {
225  assert(A.getRef() && B.getRef() &&
226  "Need ValueInfo with non-null Ref to compare GUIDs");
227  return A.getGUID() < B.getGUID();
228 }
229 
230 template <> struct DenseMapInfo<ValueInfo> {
231  static inline ValueInfo getEmptyKey() {
232  return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8);
233  }
234 
235  static inline ValueInfo getTombstoneKey() {
236  return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-16);
237  }
238 
239  static inline bool isSpecialKey(ValueInfo V) {
240  return V == getTombstoneKey() || V == getEmptyKey();
241  }
242 
243  static bool isEqual(ValueInfo L, ValueInfo R) {
244  // We are not supposed to mix ValueInfo(s) with different HaveGVs flag
245  // in a same container.
246  assert(isSpecialKey(L) || isSpecialKey(R) || (L.haveGVs() == R.haveGVs()));
247  return L.getRef() == R.getRef();
248  }
249  static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); }
250 };
251 
252 /// Function and variable summary information to aid decisions and
253 /// implementation of importing.
255 public:
256  /// Sububclass discriminator (for dyn_cast<> et al.)
257  enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
258 
259  /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
260  struct GVFlags {
261  /// The linkage type of the associated global value.
262  ///
263  /// One use is to flag values that have local linkage types and need to
264  /// have module identifier appended before placing into the combined
265  /// index, to disambiguate from other values with the same name.
266  /// In the future this will be used to update and optimize linkage
267  /// types based on global summary-based analysis.
268  unsigned Linkage : 4;
269 
270  /// Indicate if the global value cannot be imported (e.g. it cannot
271  /// be renamed or references something that can't be renamed).
272  unsigned NotEligibleToImport : 1;
273 
274  /// In per-module summary, indicate that the global value must be considered
275  /// a live root for index-based liveness analysis. Used for special LLVM
276  /// values such as llvm.global_ctors that the linker does not know about.
277  ///
278  /// In combined summary, indicate that the global value is live.
279  unsigned Live : 1;
280 
281  /// Indicates that the linker resolved the symbol to a definition from
282  /// within the same linkage unit.
283  unsigned DSOLocal : 1;
284 
285  /// In the per-module summary, indicates that the global value is
286  /// linkonce_odr and global unnamed addr (so eligible for auto-hiding
287  /// via hidden visibility). In the combined summary, indicates that the
288  /// prevailing linkonce_odr copy can be auto-hidden via hidden visibility
289  /// when it is upgraded to weak_odr in the backend. This is legal when
290  /// all copies are eligible for auto-hiding (i.e. all copies were
291  /// linkonce_odr global unnamed addr. If any copy is not (e.g. it was
292  /// originally weak_odr, we cannot auto-hide the prevailing copy as it
293  /// means the symbol was externally visible.
294  unsigned CanAutoHide : 1;
295 
296  /// Convenience Constructors
298  bool NotEligibleToImport, bool Live, bool IsLocal,
299  bool CanAutoHide)
300  : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport),
301  Live(Live), DSOLocal(IsLocal), CanAutoHide(CanAutoHide) {}
302  };
303 
304 private:
305  /// Kind of summary for use in dyn_cast<> et al.
307 
308  GVFlags Flags;
309 
310  /// This is the hash of the name of the symbol in the original file. It is
311  /// identical to the GUID for global symbols, but differs for local since the
312  /// GUID includes the module level id in the hash.
313  GlobalValue::GUID OriginalName = 0;
314 
315  /// Path of module IR containing value's definition, used to locate
316  /// module during importing.
317  ///
318  /// This is only used during parsing of the combined index, or when
319  /// parsing the per-module index for creation of the combined summary index,
320  /// not during writing of the per-module index which doesn't contain a
321  /// module path string table.
322  StringRef ModulePath;
323 
324  /// List of values referenced by this global value's definition
325  /// (either by the initializer of a global variable, or referenced
326  /// from within a function). This does not include functions called, which
327  /// are listed in the derived FunctionSummary object.
328  std::vector<ValueInfo> RefEdgeList;
329 
330 protected:
331  GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
332  : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {
333  assert((K != AliasKind || Refs.empty()) &&
334  "Expect no references for AliasSummary");
335  }
336 
337 public:
338  virtual ~GlobalValueSummary() = default;
339 
340  /// Returns the hash of the original name, it is identical to the GUID for
341  /// externally visible symbols, but not for local ones.
342  GlobalValue::GUID getOriginalName() const { return OriginalName; }
343 
344  /// Initialize the original name hash in this summary.
345  void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
346 
347  /// Which kind of summary subclass this is.
348  SummaryKind getSummaryKind() const { return Kind; }
349 
350  /// Set the path to the module containing this function, for use in
351  /// the combined index.
352  void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
353 
354  /// Get the path to the module containing this function.
355  StringRef modulePath() const { return ModulePath; }
356 
357  /// Get the flags for this GlobalValue (see \p struct GVFlags).
358  GVFlags flags() const { return Flags; }
359 
360  /// Return linkage type recorded for this global value.
362  return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
363  }
364 
365  /// Sets the linkage to the value determined by global summary-based
366  /// optimization. Will be applied in the ThinLTO backends.
368  Flags.Linkage = Linkage;
369  }
370 
371  /// Return true if this global value can't be imported.
372  bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
373 
374  bool isLive() const { return Flags.Live; }
375 
376  void setLive(bool Live) { Flags.Live = Live; }
377 
378  void setDSOLocal(bool Local) { Flags.DSOLocal = Local; }
379 
380  bool isDSOLocal() const { return Flags.DSOLocal; }
381 
382  void setCanAutoHide(bool CanAutoHide) { Flags.CanAutoHide = CanAutoHide; }
383 
384  bool canAutoHide() const { return Flags.CanAutoHide; }
385 
386  /// Flag that this global value cannot be imported.
388 
389  /// Return the list of values referenced by this global value definition.
390  ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
391 
392  /// If this is an alias summary, returns the summary of the aliased object (a
393  /// global variable or function), otherwise returns itself.
394  GlobalValueSummary *getBaseObject();
395  const GlobalValueSummary *getBaseObject() const;
396 
397  friend class ModuleSummaryIndex;
398 };
399 
400 /// Alias summary information.
402  ValueInfo AliaseeValueInfo;
403 
404  /// This is the Aliasee in the same module as alias (could get from VI, trades
405  /// memory for time). Note that this pointer may be null (and the value info
406  /// empty) when we have a distributed index where the alias is being imported
407  /// (as a copy of the aliasee), but the aliasee is not.
408  GlobalValueSummary *AliaseeSummary;
409 
410 public:
412  : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}),
413  AliaseeSummary(nullptr) {}
414 
415  /// Check if this is an alias summary.
416  static bool classof(const GlobalValueSummary *GVS) {
417  return GVS->getSummaryKind() == AliasKind;
418  }
419 
420  void setAliasee(ValueInfo &AliaseeVI, GlobalValueSummary *Aliasee) {
421  AliaseeValueInfo = AliaseeVI;
422  AliaseeSummary = Aliasee;
423  }
424 
425  bool hasAliasee() const {
426  assert(!!AliaseeSummary == (AliaseeValueInfo &&
427  !AliaseeValueInfo.getSummaryList().empty()) &&
428  "Expect to have both aliasee summary and summary list or neither");
429  return !!AliaseeSummary;
430  }
431 
433  assert(AliaseeSummary && "Unexpected missing aliasee summary");
434  return *AliaseeSummary;
435  }
436 
438  return const_cast<GlobalValueSummary &>(
439  static_cast<const AliasSummary *>(this)->getAliasee());
440  }
442  assert(AliaseeValueInfo && "Unexpected missing aliasee");
443  return AliaseeValueInfo;
444  }
446  assert(AliaseeValueInfo && "Unexpected missing aliasee");
447  return AliaseeValueInfo.getGUID();
448  }
449 };
450 
452  if (auto *AS = dyn_cast<AliasSummary>(this))
453  return &AS->getAliasee();
454  return this;
455 }
456 
458  if (auto *AS = dyn_cast<AliasSummary>(this))
459  return &AS->getAliasee();
460  return this;
461 }
462 
463 /// Function summary information to aid decisions and implementation of
464 /// importing.
466 public:
467  /// <CalleeValueInfo, CalleeInfo> call edge pair.
468  using EdgeTy = std::pair<ValueInfo, CalleeInfo>;
469 
470  /// Types for -force-summary-edges-cold debugging option.
471  enum ForceSummaryHotnessType : unsigned {
474  FSHT_All
475  };
476 
477  /// An "identifier" for a virtual function. This contains the type identifier
478  /// represented as a GUID and the offset from the address point to the virtual
479  /// function pointer, where "address point" is as defined in the Itanium ABI:
480  /// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
481  struct VFuncId {
483  uint64_t Offset;
484  };
485 
486  /// A specification for a virtual function call with all constant integer
487  /// arguments. This is used to perform virtual constant propagation on the
488  /// summary.
489  struct ConstVCall {
491  std::vector<uint64_t> Args;
492  };
493 
494  /// All type identifier related information. Because these fields are
495  /// relatively uncommon we only allocate space for them if necessary.
496  struct TypeIdInfo {
497  /// List of type identifiers used by this function in llvm.type.test
498  /// intrinsics referenced by something other than an llvm.assume intrinsic,
499  /// represented as GUIDs.
500  std::vector<GlobalValue::GUID> TypeTests;
501 
502  /// List of virtual calls made by this function using (respectively)
503  /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do
504  /// not have all constant integer arguments.
505  std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
506 
507  /// List of virtual calls made by this function using (respectively)
508  /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with
509  /// all constant integer arguments.
510  std::vector<ConstVCall> TypeTestAssumeConstVCalls,
511  TypeCheckedLoadConstVCalls;
512  };
513 
514  /// Flags specific to function summaries.
515  struct FFlags {
516  // Function attribute flags. Used to track if a function accesses memory,
517  // recurses or aliases.
518  unsigned ReadNone : 1;
519  unsigned ReadOnly : 1;
520  unsigned NoRecurse : 1;
521  unsigned ReturnDoesNotAlias : 1;
522 
523  // Indicate if the global value cannot be inlined.
524  unsigned NoInline : 1;
525  };
526 
527  /// Create an empty FunctionSummary (with specified call edges).
528  /// Used to represent external nodes and the dummy root node.
529  static FunctionSummary
530  makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) {
531  return FunctionSummary(
533  GlobalValue::LinkageTypes::AvailableExternallyLinkage,
534  /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false,
535  /*CanAutoHide=*/false),
536  /*InsCount=*/0, FunctionSummary::FFlags{}, /*EntryCount=*/0,
537  std::vector<ValueInfo>(), std::move(Edges),
538  std::vector<GlobalValue::GUID>(),
539  std::vector<FunctionSummary::VFuncId>(),
540  std::vector<FunctionSummary::VFuncId>(),
541  std::vector<FunctionSummary::ConstVCall>(),
542  std::vector<FunctionSummary::ConstVCall>());
543  }
544 
545  /// A dummy node to reference external functions that aren't in the index
547 
548 private:
549  /// Number of instructions (ignoring debug instructions, e.g.) computed
550  /// during the initial compile step when the summary index is first built.
551  unsigned InstCount;
552 
553  /// Function summary specific flags.
554  FFlags FunFlags;
555 
556  /// The synthesized entry count of the function.
557  /// This is only populated during ThinLink phase and remains unused while
558  /// generating per-module summaries.
559  uint64_t EntryCount = 0;
560 
561  /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
562  std::vector<EdgeTy> CallGraphEdgeList;
563 
564  std::unique_ptr<TypeIdInfo> TIdInfo;
565 
566 public:
567  FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
568  uint64_t EntryCount, std::vector<ValueInfo> Refs,
569  std::vector<EdgeTy> CGEdges,
570  std::vector<GlobalValue::GUID> TypeTests,
571  std::vector<VFuncId> TypeTestAssumeVCalls,
572  std::vector<VFuncId> TypeCheckedLoadVCalls,
573  std::vector<ConstVCall> TypeTestAssumeConstVCalls,
574  std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
575  : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
576  InstCount(NumInsts), FunFlags(FunFlags), EntryCount(EntryCount),
577  CallGraphEdgeList(std::move(CGEdges)) {
578  if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
579  !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
580  !TypeCheckedLoadConstVCalls.empty())
581  TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
582  std::move(TypeTests), std::move(TypeTestAssumeVCalls),
583  std::move(TypeCheckedLoadVCalls),
584  std::move(TypeTestAssumeConstVCalls),
585  std::move(TypeCheckedLoadConstVCalls)});
586  }
587  // Gets the number of immutable refs in RefEdgeList
588  unsigned immutableRefCount() const;
589 
590  /// Check if this is a function summary.
591  static bool classof(const GlobalValueSummary *GVS) {
592  return GVS->getSummaryKind() == FunctionKind;
593  }
594 
595  /// Get function summary flags.
596  FFlags fflags() const { return FunFlags; }
597 
598  /// Get the instruction count recorded for this function.
599  unsigned instCount() const { return InstCount; }
600 
601  /// Get the synthetic entry count for this function.
602  uint64_t entryCount() const { return EntryCount; }
603 
604  /// Set the synthetic entry count for this function.
605  void setEntryCount(uint64_t EC) { EntryCount = EC; }
606 
607  /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
608  ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
609 
610  /// Returns the list of type identifiers used by this function in
611  /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
612  /// represented as GUIDs.
614  if (TIdInfo)
615  return TIdInfo->TypeTests;
616  return {};
617  }
618 
619  /// Returns the list of virtual calls made by this function using
620  /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
621  /// integer arguments.
623  if (TIdInfo)
624  return TIdInfo->TypeTestAssumeVCalls;
625  return {};
626  }
627 
628  /// Returns the list of virtual calls made by this function using
629  /// llvm.type.checked.load intrinsics that do not have all constant integer
630  /// arguments.
632  if (TIdInfo)
633  return TIdInfo->TypeCheckedLoadVCalls;
634  return {};
635  }
636 
637  /// Returns the list of virtual calls made by this function using
638  /// llvm.assume(llvm.type.test) intrinsics with all constant integer
639  /// arguments.
641  if (TIdInfo)
642  return TIdInfo->TypeTestAssumeConstVCalls;
643  return {};
644  }
645 
646  /// Returns the list of virtual calls made by this function using
647  /// llvm.type.checked.load intrinsics with all constant integer arguments.
649  if (TIdInfo)
650  return TIdInfo->TypeCheckedLoadConstVCalls;
651  return {};
652  }
653 
654  /// Add a type test to the summary. This is used by WholeProgramDevirt if we
655  /// were unable to devirtualize a checked call.
657  if (!TIdInfo)
658  TIdInfo = llvm::make_unique<TypeIdInfo>();
659  TIdInfo->TypeTests.push_back(Guid);
660  }
661 
662  const TypeIdInfo *getTypeIdInfo() const { return TIdInfo.get(); };
663 
664  friend struct GraphTraits<ValueInfo>;
665 };
666 
667 template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
668  static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
669 
671  return {0, uint64_t(-2)};
672  }
673 
675  return L.GUID == R.GUID && L.Offset == R.Offset;
676  }
677 
678  static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
679 };
680 
681 template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
683  return {{0, uint64_t(-1)}, {}};
684  }
685 
687  return {{0, uint64_t(-2)}, {}};
688  }
689 
693  L.Args == R.Args;
694  }
695 
697  return I.VFunc.GUID;
698  }
699 };
700 
701 /// Global variable summary information to aid decisions and
702 /// implementation of importing.
703 ///
704 /// Global variable summary has extra flag, telling if it is
705 /// modified during the program run or not. This affects ThinLTO
706 /// internalization
708 public:
709  struct GVarFlags {
710  GVarFlags(bool ReadOnly = false) : ReadOnly(ReadOnly) {}
711 
712  unsigned ReadOnly : 1;
713  } VarFlags;
714 
716  std::vector<ValueInfo> Refs)
717  : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)),
718  VarFlags(VarFlags) {}
719 
720  /// Check if this is a global variable summary.
721  static bool classof(const GlobalValueSummary *GVS) {
722  return GVS->getSummaryKind() == GlobalVarKind;
723  }
724 
725  GVarFlags varflags() const { return VarFlags; }
726  void setReadOnly(bool RO) { VarFlags.ReadOnly = RO; }
727  bool isReadOnly() const { return VarFlags.ReadOnly; }
728 };
729 
731  /// Specifies which kind of type check we should emit for this byte array.
732  /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
733  /// details on each kind of check; the enumerators are described with
734  /// reference to that document.
735  enum Kind {
736  Unsat, ///< Unsatisfiable type (i.e. no global has this type metadata)
737  ByteArray, ///< Test a byte array (first example)
738  Inline, ///< Inlined bit vector ("Short Inline Bit Vectors")
739  Single, ///< Single element (last example in "Short Inline Bit Vectors")
740  AllOnes, ///< All-ones bit vector ("Eliminating Bit Vector Checks for
741  /// All-Ones Bit Vectors")
742  } TheKind = Unsat;
743 
744  /// Range of size-1 expressed as a bit width. For example, if the size is in
745  /// range [1,256], this number will be 8. This helps generate the most compact
746  /// instruction sequences.
747  unsigned SizeM1BitWidth = 0;
748 
749  // The following fields are only used if the target does not support the use
750  // of absolute symbols to store constants. Their meanings are the same as the
751  // corresponding fields in LowerTypeTestsModule::TypeIdLowering in
752  // LowerTypeTests.cpp.
753 
754  uint64_t AlignLog2 = 0;
755  uint64_t SizeM1 = 0;
756  uint8_t BitMask = 0;
757  uint64_t InlineBits = 0;
758 };
759 
761  enum Kind {
762  Indir, ///< Just do a regular virtual call
763  SingleImpl, ///< Single implementation devirtualization
764  BranchFunnel, ///< When retpoline mitigation is enabled, use a branch funnel
765  ///< that is defined in the merged module. Otherwise same as
766  ///< Indir.
767  } TheKind = Indir;
768 
769  std::string SingleImplName;
770 
771  struct ByArg {
772  enum Kind {
773  Indir, ///< Just do a regular virtual call
774  UniformRetVal, ///< Uniform return value optimization
775  UniqueRetVal, ///< Unique return value optimization
776  VirtualConstProp, ///< Virtual constant propagation
777  } TheKind = Indir;
778 
779  /// Additional information for the resolution:
780  /// - UniformRetVal: the uniform return value.
781  /// - UniqueRetVal: the return value associated with the unique vtable (0 or
782  /// 1).
783  uint64_t Info = 0;
784 
785  // The following fields are only used if the target does not support the use
786  // of absolute symbols to store constants.
787 
788  uint32_t Byte = 0;
790  };
791 
792  /// Resolutions for calls with all constant integer arguments (excluding the
793  /// first argument, "this"), where the key is the argument vector.
794  std::map<std::vector<uint64_t>, ByArg> ResByArg;
795 };
796 
799 
800  /// Mapping from byte offset to whole-program devirt resolution for that
801  /// (typeid, byte offset) pair.
802  std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
803 };
804 
805 /// 160 bits SHA1
806 using ModuleHash = std::array<uint32_t, 5>;
807 
808 /// Type used for iterating through the global value summary map.
809 using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
810 using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
811 
812 /// String table to hold/own module path strings, which additionally holds the
813 /// module ID assigned to each module during the plugin step, as well as a hash
814 /// of the module. The StringMap makes a copy of and owns inserted strings.
816 
817 /// Map of global value GUID to its summary, used to identify values defined in
818 /// a particular module, and provide efficient access to their summary.
820 
821 /// Map of a type GUID to type id string and summary (multimap used
822 /// in case of GUID conflicts).
823 using TypeIdSummaryMapTy =
824  std::multimap<GlobalValue::GUID, std::pair<std::string, TypeIdSummary>>;
825 
826 /// Class to hold module path string table and global value map,
827 /// and encapsulate methods for operating on them.
829 private:
830  /// Map from value name to list of summary instances for values of that
831  /// name (may be duplicates in the COMDAT case, e.g.).
832  GlobalValueSummaryMapTy GlobalValueMap;
833 
834  /// Holds strings for combined index, mapping to the corresponding module ID.
835  ModulePathStringTableTy ModulePathStringTable;
836 
837  /// Mapping from type identifier GUIDs to type identifier and its summary
838  /// information.
839  TypeIdSummaryMapTy TypeIdMap;
840 
841  /// Mapping from original ID to GUID. If original ID can map to multiple
842  /// GUIDs, it will be mapped to 0.
843  std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
844 
845  /// Indicates that summary-based GlobalValue GC has run, and values with
846  /// GVFlags::Live==false are really dead. Otherwise, all values must be
847  /// considered live.
848  bool WithGlobalValueDeadStripping = false;
849 
850  /// Indicates that summary-based synthetic entry count propagation has run
851  bool HasSyntheticEntryCounts = false;
852 
853  /// Indicates that distributed backend should skip compilation of the
854  /// module. Flag is suppose to be set by distributed ThinLTO indexing
855  /// when it detected that the module is not needed during the final
856  /// linking. As result distributed backend should just output a minimal
857  /// valid object file.
858  bool SkipModuleByDistributedBackend = false;
859 
860  /// If true then we're performing analysis of IR module, or parsing along with
861  /// the IR from assembly. The value of 'false' means we're reading summary
862  /// from BC or YAML source. Affects the type of value stored in NameOrGV
863  /// union.
864  bool HaveGVs;
865 
866  // True if the index was created for a module compiled with -fsplit-lto-unit.
867  bool EnableSplitLTOUnit;
868 
869  // True if some of the modules were compiled with -fsplit-lto-unit and
870  // some were not. Set when the combined index is created during the thin link.
871  bool PartiallySplitLTOUnits = false;
872 
873  std::set<std::string> CfiFunctionDefs;
874  std::set<std::string> CfiFunctionDecls;
875 
876  // Used in cases where we want to record the name of a global, but
877  // don't have the string owned elsewhere (e.g. the Strtab on a module).
878  StringSaver Saver;
879  BumpPtrAllocator Alloc;
880 
881  // YAML I/O support.
883 
884  GlobalValueSummaryMapTy::value_type *
885  getOrInsertValuePtr(GlobalValue::GUID GUID) {
886  return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs))
887  .first;
888  }
889 
890 public:
891  // See HaveGVs variable comment.
892  ModuleSummaryIndex(bool HaveGVs, bool EnableSplitLTOUnit = false)
893  : HaveGVs(HaveGVs), EnableSplitLTOUnit(EnableSplitLTOUnit), Saver(Alloc) {
894  }
895 
896  bool haveGVs() const { return HaveGVs; }
897 
898  gvsummary_iterator begin() { return GlobalValueMap.begin(); }
899  const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
900  gvsummary_iterator end() { return GlobalValueMap.end(); }
901  const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
902  size_t size() const { return GlobalValueMap.size(); }
903 
904  /// Convenience function for doing a DFS on a ValueInfo. Marks the function in
905  /// the FunctionHasParent map.
906  static void discoverNodes(ValueInfo V,
907  std::map<ValueInfo, bool> &FunctionHasParent) {
908  if (!V.getSummaryList().size())
909  return; // skip external functions that don't have summaries
910 
911  // Mark discovered if we haven't yet
912  auto S = FunctionHasParent.emplace(V, false);
913 
914  // Stop if we've already discovered this node
915  if (!S.second)
916  return;
917 
918  FunctionSummary *F =
919  dyn_cast<FunctionSummary>(V.getSummaryList().front().get());
920  assert(F != nullptr && "Expected FunctionSummary node");
921 
922  for (auto &C : F->calls()) {
923  // Insert node if necessary
924  auto S = FunctionHasParent.emplace(C.first, true);
925 
926  // Skip nodes that we're sure have parents
927  if (!S.second && S.first->second)
928  continue;
929 
930  if (S.second)
931  discoverNodes(C.first, FunctionHasParent);
932  else
933  S.first->second = true;
934  }
935  }
936 
937  // Calculate the callgraph root
939  // Functions that have a parent will be marked in FunctionHasParent pair.
940  // Once we've marked all functions, the functions in the map that are false
941  // have no parent (so they're the roots)
942  std::map<ValueInfo, bool> FunctionHasParent;
943 
944  for (auto &S : *this) {
945  // Skip external functions
946  if (!S.second.SummaryList.size() ||
947  !isa<FunctionSummary>(S.second.SummaryList.front().get()))
948  continue;
949  discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent);
950  }
951 
952  std::vector<FunctionSummary::EdgeTy> Edges;
953  // create edges to all roots in the Index
954  for (auto &P : FunctionHasParent) {
955  if (P.second)
956  continue; // skip over non-root nodes
957  Edges.push_back(std::make_pair(P.first, CalleeInfo{}));
958  }
959  if (Edges.empty()) {
960  // Failed to find root - return an empty node
962  }
963  auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
964  return CallGraphRoot;
965  }
966 
968  return WithGlobalValueDeadStripping;
969  }
971  WithGlobalValueDeadStripping = true;
972  }
973 
974  bool hasSyntheticEntryCounts() const { return HasSyntheticEntryCounts; }
975  void setHasSyntheticEntryCounts() { HasSyntheticEntryCounts = true; }
976 
978  return SkipModuleByDistributedBackend;
979  }
981  SkipModuleByDistributedBackend = true;
982  }
983 
984  bool enableSplitLTOUnit() const { return EnableSplitLTOUnit; }
985  void setEnableSplitLTOUnit() { EnableSplitLTOUnit = true; }
986 
987  bool partiallySplitLTOUnits() const { return PartiallySplitLTOUnits; }
988  void setPartiallySplitLTOUnits() { PartiallySplitLTOUnits = true; }
989 
990  bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
991  return !WithGlobalValueDeadStripping || GVS->isLive();
992  }
993  bool isGUIDLive(GlobalValue::GUID GUID) const;
994 
995  /// Return a ValueInfo for the index value_type (convenient when iterating
996  /// index).
997  ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const {
998  return ValueInfo(HaveGVs, &R);
999  }
1000 
1001  /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
1002  ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
1003  auto I = GlobalValueMap.find(GUID);
1004  return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I);
1005  }
1006 
1007  /// Return a ValueInfo for \p GUID.
1009  return ValueInfo(HaveGVs, getOrInsertValuePtr(GUID));
1010  }
1011 
1012  // Save a string in the Index. Use before passing Name to
1013  // getOrInsertValueInfo when the string isn't owned elsewhere (e.g. on the
1014  // module's Strtab).
1015  StringRef saveString(StringRef String) { return Saver.save(String); }
1016 
1017  /// Return a ValueInfo for \p GUID setting value \p Name.
1019  assert(!HaveGVs);
1020  auto VP = getOrInsertValuePtr(GUID);
1021  VP->second.U.Name = Name;
1022  return ValueInfo(HaveGVs, VP);
1023  }
1024 
1025  /// Return a ValueInfo for \p GV and mark it as belonging to GV.
1026  ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
1027  assert(HaveGVs);
1028  auto VP = getOrInsertValuePtr(GV->getGUID());
1029  VP->second.U.GV = GV;
1030  return ValueInfo(HaveGVs, VP);
1031  }
1032 
1033  /// Return the GUID for \p OriginalId in the OidGuidMap.
1035  const auto I = OidGuidMap.find(OriginalID);
1036  return I == OidGuidMap.end() ? 0 : I->second;
1037  }
1038 
1039  std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; }
1040  const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; }
1041 
1042  std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; }
1043  const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; }
1044 
1045  /// Add a global value summary for a value.
1047  std::unique_ptr<GlobalValueSummary> Summary) {
1048  addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary));
1049  }
1050 
1051  /// Add a global value summary for a value of the given name.
1053  std::unique_ptr<GlobalValueSummary> Summary) {
1054  addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
1055  std::move(Summary));
1056  }
1057 
1058  /// Add a global value summary for the given ValueInfo.
1059  void addGlobalValueSummary(ValueInfo VI,
1060  std::unique_ptr<GlobalValueSummary> Summary) {
1061  addOriginalName(VI.getGUID(), Summary->getOriginalName());
1062  // Here we have a notionally const VI, but the value it points to is owned
1063  // by the non-const *this.
1064  const_cast<GlobalValueSummaryMapTy::value_type *>(VI.getRef())
1065  ->second.SummaryList.push_back(std::move(Summary));
1066  }
1067 
1068  /// Add an original name for the value of the given GUID.
1070  GlobalValue::GUID OrigGUID) {
1071  if (OrigGUID == 0 || ValueGUID == OrigGUID)
1072  return;
1073  if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
1074  OidGuidMap[OrigGUID] = 0;
1075  else
1076  OidGuidMap[OrigGUID] = ValueGUID;
1077  }
1078 
1079  /// Find the summary for ValueInfo \p VI in module \p ModuleId, or nullptr if
1080  /// not found.
1081  GlobalValueSummary *findSummaryInModule(ValueInfo VI, StringRef ModuleId) const {
1082  auto SummaryList = VI.getSummaryList();
1083  auto Summary =
1084  llvm::find_if(SummaryList,
1085  [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
1086  return Summary->modulePath() == ModuleId;
1087  });
1088  if (Summary == SummaryList.end())
1089  return nullptr;
1090  return Summary->get();
1091  }
1092 
1093  /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
1094  /// not found.
1096  StringRef ModuleId) const {
1097  auto CalleeInfo = getValueInfo(ValueGUID);
1098  if (!CalleeInfo)
1099  return nullptr; // This function does not have a summary
1100  return findSummaryInModule(CalleeInfo, ModuleId);
1101  }
1102 
1103  /// Returns the first GlobalValueSummary for \p GV, asserting that there
1104  /// is only one if \p PerModuleIndex.
1106  bool PerModuleIndex = true) const {
1107  assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
1108  return getGlobalValueSummary(GV.getGUID(), PerModuleIndex);
1109  }
1110 
1111  /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
1112  /// there
1113  /// is only one if \p PerModuleIndex.
1114  GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
1115  bool PerModuleIndex = true) const;
1116 
1117  /// Table of modules, containing module hash and id.
1119  return ModulePathStringTable;
1120  }
1121 
1122  /// Table of modules, containing hash and id.
1124  return ModulePathStringTable;
1125  }
1126 
1127  /// Get the module ID recorded for the given module path.
1128  uint64_t getModuleId(const StringRef ModPath) const {
1129  return ModulePathStringTable.lookup(ModPath).first;
1130  }
1131 
1132  /// Get the module SHA1 hash recorded for the given module path.
1133  const ModuleHash &getModuleHash(const StringRef ModPath) const {
1134  auto It = ModulePathStringTable.find(ModPath);
1135  assert(It != ModulePathStringTable.end() && "Module not registered");
1136  return It->second.second;
1137  }
1138 
1139  /// Convenience method for creating a promoted global name
1140  /// for the given value name of a local, and its original module's ID.
1141  static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
1142  SmallString<256> NewName(Name);
1143  NewName += ".llvm.";
1144  NewName += utostr((uint64_t(ModHash[0]) << 32) |
1145  ModHash[1]); // Take the first 64 bits
1146  return NewName.str();
1147  }
1148 
1149  /// Helper to obtain the unpromoted name for a global value (or the original
1150  /// name if not promoted).
1152  std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
1153  return Pair.first;
1154  }
1155 
1157 
1158  /// Add a new module with the given \p Hash, mapped to the given \p
1159  /// ModID, and return a reference to the module.
1160  ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
1161  ModuleHash Hash = ModuleHash{{0}}) {
1162  return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first;
1163  }
1164 
1165  /// Return module entry for module with the given \p ModPath.
1166  ModuleInfo *getModule(StringRef ModPath) {
1167  auto It = ModulePathStringTable.find(ModPath);
1168  assert(It != ModulePathStringTable.end() && "Module not registered");
1169  return &*It;
1170  }
1171 
1172  /// Check if the given Module has any functions available for exporting
1173  /// in the index. We consider any module present in the ModulePathStringTable
1174  /// to have exported functions.
1175  bool hasExportedFunctions(const Module &M) const {
1176  return ModulePathStringTable.count(M.getModuleIdentifier());
1177  }
1178 
1179  const TypeIdSummaryMapTy &typeIds() const { return TypeIdMap; }
1180 
1181  /// Return an existing or new TypeIdSummary entry for \p TypeId.
1182  /// This accessor can mutate the map and therefore should not be used in
1183  /// the ThinLTO backends.
1185  auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1186  for (auto It = TidIter.first; It != TidIter.second; ++It)
1187  if (It->second.first == TypeId)
1188  return It->second.second;
1189  auto It = TypeIdMap.insert(
1190  {GlobalValue::getGUID(TypeId), {TypeId, TypeIdSummary()}});
1191  return It->second.second;
1192  }
1193 
1194  /// This returns either a pointer to the type id summary (if present in the
1195  /// summary map) or null (if not present). This may be used when importing.
1197  auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1198  for (auto It = TidIter.first; It != TidIter.second; ++It)
1199  if (It->second.first == TypeId)
1200  return &It->second.second;
1201  return nullptr;
1202  }
1203 
1204  /// Collect for the given module the list of functions it defines
1205  /// (GUID -> Summary).
1206  void collectDefinedFunctionsForModule(StringRef ModulePath,
1207  GVSummaryMapTy &GVSummaryMap) const;
1208 
1209  /// Collect for each module the list of Summaries it defines (GUID ->
1210  /// Summary).
1211  template <class Map>
1212  void
1213  collectDefinedGVSummariesPerModule(Map &ModuleToDefinedGVSummaries) const {
1214  for (auto &GlobalList : *this) {
1215  auto GUID = GlobalList.first;
1216  for (auto &Summary : GlobalList.second.SummaryList) {
1217  ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
1218  }
1219  }
1220  }
1221 
1222  /// Print to an output stream.
1223  void print(raw_ostream &OS, bool IsForDebug = false) const;
1224 
1225  /// Dump to stderr (for debugging).
1226  void dump() const;
1227 
1228  /// Export summary to dot file for GraphViz.
1229  void exportToDot(raw_ostream& OS) const;
1230 
1231  /// Print out strongly connected components for debugging.
1232  void dumpSCCs(raw_ostream &OS);
1233 
1234  /// Analyze index and detect unmodified globals
1235  void propagateConstants(const DenseSet<GlobalValue::GUID> &PreservedSymbols);
1236 };
1237 
1238 /// GraphTraits definition to build SCC for the index
1239 template <> struct GraphTraits<ValueInfo> {
1240  typedef ValueInfo NodeRef;
1242 
1244  return P.first;
1245  }
1246  using ChildIteratorType =
1248  decltype(&valueInfoFromEdge)>;
1249 
1250  using ChildEdgeIteratorType = std::vector<FunctionSummary::EdgeTy>::iterator;
1251 
1252  static NodeRef getEntryNode(ValueInfo V) { return V; }
1253 
1254  static ChildIteratorType child_begin(NodeRef N) {
1255  if (!N.getSummaryList().size()) // handle external function
1256  return ChildIteratorType(
1257  FunctionSummary::ExternalNode.CallGraphEdgeList.begin(),
1258  &valueInfoFromEdge);
1259  FunctionSummary *F =
1260  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1261  return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge);
1262  }
1263 
1264  static ChildIteratorType child_end(NodeRef N) {
1265  if (!N.getSummaryList().size()) // handle external function
1266  return ChildIteratorType(
1267  FunctionSummary::ExternalNode.CallGraphEdgeList.end(),
1268  &valueInfoFromEdge);
1269  FunctionSummary *F =
1270  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1271  return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge);
1272  }
1273 
1275  if (!N.getSummaryList().size()) // handle external function
1276  return FunctionSummary::ExternalNode.CallGraphEdgeList.begin();
1277 
1278  FunctionSummary *F =
1279  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1280  return F->CallGraphEdgeList.begin();
1281  }
1282 
1284  if (!N.getSummaryList().size()) // handle external function
1285  return FunctionSummary::ExternalNode.CallGraphEdgeList.end();
1286 
1287  FunctionSummary *F =
1288  cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1289  return F->CallGraphEdgeList.end();
1290  }
1291 
1292  static NodeRef edge_dest(EdgeRef E) { return E.first; }
1293 };
1294 
1295 template <>
1298  std::unique_ptr<GlobalValueSummary> Root =
1299  make_unique<FunctionSummary>(I->calculateCallGraphRoot());
1301  G.SummaryList.push_back(std::move(Root));
1302  static auto P =
1303  GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G));
1304  return ValueInfo(I->haveGVs(), &P);
1305  }
1306 };
1307 
1308 static inline bool canImportGlobalVar(GlobalValueSummary *S) {
1309  assert(isa<GlobalVarSummary>(S->getBaseObject()));
1310 
1311  // We don't import GV with references, because it can result
1312  // in promotion of local variables in the source module.
1314  !S->notEligibleToImport() && S->refs().empty();
1315 }
1316 } // end namespace llvm
1317 
1318 #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:346
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:502
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)
void setCanAutoHide(bool CanAutoHide)
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:1220
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:506
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:370
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:510
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.
unsigned CanAutoHide
In the per-module summary, indicates that the global value is linkonce_odr and global unnamed addr (s...
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
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()
GVFlags(GlobalValue::LinkageTypes Linkage, bool NotEligibleToImport, bool Live, bool IsLocal, bool CanAutoHide)
Convenience Constructors.
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:343
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.