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