xref: /netbsd-src/external/apache2/llvm/dist/llvm/include/llvm/IR/ModuleSummaryIndex.h (revision 82d56013d7b633d116a93943de88e08335357a7c)
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/ConstantRange.h"
27 #include "llvm/IR/GlobalValue.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/Support/Allocator.h"
30 #include "llvm/Support/MathExtras.h"
31 #include "llvm/Support/ScaledNumber.h"
32 #include "llvm/Support/StringSaver.h"
33 #include "llvm/Support/raw_ostream.h"
34 #include <algorithm>
35 #include <array>
36 #include <cassert>
37 #include <cstddef>
38 #include <cstdint>
39 #include <map>
40 #include <memory>
41 #include <set>
42 #include <string>
43 #include <utility>
44 #include <vector>
45 
46 namespace llvm {
47 
48 namespace yaml {
49 
50 template <typename T> struct MappingTraits;
51 
52 } // end namespace yaml
53 
54 /// Class to accumulate and hold information about a callee.
55 struct CalleeInfo {
56   enum class HotnessType : uint8_t {
57     Unknown = 0,
58     Cold = 1,
59     None = 2,
60     Hot = 3,
61     Critical = 4
62   };
63 
64   // The size of the bit-field might need to be adjusted if more values are
65   // added to HotnessType enum.
66   uint32_t Hotness : 3;
67 
68   /// The value stored in RelBlockFreq has to be interpreted as the digits of
69   /// a scaled number with a scale of \p -ScaleShift.
70   uint32_t RelBlockFreq : 29;
71   static constexpr int32_t ScaleShift = 8;
72   static constexpr uint64_t MaxRelBlockFreq = (1 << 29) - 1;
73 
CalleeInfoCalleeInfo74   CalleeInfo()
75       : Hotness(static_cast<uint32_t>(HotnessType::Unknown)), RelBlockFreq(0) {}
CalleeInfoCalleeInfo76   explicit CalleeInfo(HotnessType Hotness, uint64_t RelBF)
77       : Hotness(static_cast<uint32_t>(Hotness)), RelBlockFreq(RelBF) {}
78 
updateHotnessCalleeInfo79   void updateHotness(const HotnessType OtherHotness) {
80     Hotness = std::max(Hotness, static_cast<uint32_t>(OtherHotness));
81   }
82 
getHotnessCalleeInfo83   HotnessType getHotness() const { return HotnessType(Hotness); }
84 
85   /// Update \p RelBlockFreq from \p BlockFreq and \p EntryFreq
86   ///
87   /// BlockFreq is divided by EntryFreq and added to RelBlockFreq. To represent
88   /// fractional values, the result is represented as a fixed point number with
89   /// scale of -ScaleShift.
updateRelBlockFreqCalleeInfo90   void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq) {
91     if (EntryFreq == 0)
92       return;
93     using Scaled64 = ScaledNumber<uint64_t>;
94     Scaled64 Temp(BlockFreq, ScaleShift);
95     Temp /= Scaled64::get(EntryFreq);
96 
97     uint64_t Sum =
98         SaturatingAdd<uint64_t>(Temp.toInt<uint64_t>(), RelBlockFreq);
99     Sum = std::min(Sum, uint64_t(MaxRelBlockFreq));
100     RelBlockFreq = static_cast<uint32_t>(Sum);
101   }
102 };
103 
getHotnessName(CalleeInfo::HotnessType HT)104 inline const char *getHotnessName(CalleeInfo::HotnessType HT) {
105   switch (HT) {
106   case CalleeInfo::HotnessType::Unknown:
107     return "unknown";
108   case CalleeInfo::HotnessType::Cold:
109     return "cold";
110   case CalleeInfo::HotnessType::None:
111     return "none";
112   case CalleeInfo::HotnessType::Hot:
113     return "hot";
114   case CalleeInfo::HotnessType::Critical:
115     return "critical";
116   }
117   llvm_unreachable("invalid hotness");
118 }
119 
120 class GlobalValueSummary;
121 
122 using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>;
123 
124 struct alignas(8) GlobalValueSummaryInfo {
125   union NameOrGV {
NameOrGV(bool HaveGVs)126     NameOrGV(bool HaveGVs) {
127       if (HaveGVs)
128         GV = nullptr;
129       else
130         Name = "";
131     }
132 
133     /// The GlobalValue corresponding to this summary. This is only used in
134     /// per-module summaries and when the IR is available. E.g. when module
135     /// analysis is being run, or when parsing both the IR and the summary
136     /// from assembly.
137     const GlobalValue *GV;
138 
139     /// Summary string representation. This StringRef points to BC module
140     /// string table and is valid until module data is stored in memory.
141     /// This is guaranteed to happen until runThinLTOBackend function is
142     /// called, so it is safe to use this field during thin link. This field
143     /// is only valid if summary index was loaded from BC file.
144     StringRef Name;
145   } U;
146 
GlobalValueSummaryInfoGlobalValueSummaryInfo147   GlobalValueSummaryInfo(bool HaveGVs) : U(HaveGVs) {}
148 
149   /// List of global value summary structures for a particular value held
150   /// in the GlobalValueMap. Requires a vector in the case of multiple
151   /// COMDAT values of the same name.
152   GlobalValueSummaryList SummaryList;
153 };
154 
155 /// Map from global value GUID to corresponding summary structures. Use a
156 /// std::map rather than a DenseMap so that pointers to the map's value_type
157 /// (which are used by ValueInfo) are not invalidated by insertion. Also it will
158 /// likely incur less overhead, as the value type is not very small and the size
159 /// of the map is unknown, resulting in inefficiencies due to repeated
160 /// insertions and resizing.
161 using GlobalValueSummaryMapTy =
162     std::map<GlobalValue::GUID, GlobalValueSummaryInfo>;
163 
164 /// Struct that holds a reference to a particular GUID in a global value
165 /// summary.
166 struct ValueInfo {
167   enum Flags { HaveGV = 1, ReadOnly = 2, WriteOnly = 4 };
168   PointerIntPair<const GlobalValueSummaryMapTy::value_type *, 3, int>
169       RefAndFlags;
170 
171   ValueInfo() = default;
ValueInfoValueInfo172   ValueInfo(bool HaveGVs, const GlobalValueSummaryMapTy::value_type *R) {
173     RefAndFlags.setPointer(R);
174     RefAndFlags.setInt(HaveGVs);
175   }
176 
177   explicit operator bool() const { return getRef(); }
178 
getGUIDValueInfo179   GlobalValue::GUID getGUID() const { return getRef()->first; }
getValueValueInfo180   const GlobalValue *getValue() const {
181     assert(haveGVs());
182     return getRef()->second.U.GV;
183   }
184 
getSummaryListValueInfo185   ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const {
186     return getRef()->second.SummaryList;
187   }
188 
nameValueInfo189   StringRef name() const {
190     return haveGVs() ? getRef()->second.U.GV->getName()
191                      : getRef()->second.U.Name;
192   }
193 
haveGVsValueInfo194   bool haveGVs() const { return RefAndFlags.getInt() & HaveGV; }
isReadOnlyValueInfo195   bool isReadOnly() const {
196     assert(isValidAccessSpecifier());
197     return RefAndFlags.getInt() & ReadOnly;
198   }
isWriteOnlyValueInfo199   bool isWriteOnly() const {
200     assert(isValidAccessSpecifier());
201     return RefAndFlags.getInt() & WriteOnly;
202   }
getAccessSpecifierValueInfo203   unsigned getAccessSpecifier() const {
204     assert(isValidAccessSpecifier());
205     return RefAndFlags.getInt() & (ReadOnly | WriteOnly);
206   }
isValidAccessSpecifierValueInfo207   bool isValidAccessSpecifier() const {
208     unsigned BadAccessMask = ReadOnly | WriteOnly;
209     return (RefAndFlags.getInt() & BadAccessMask) != BadAccessMask;
210   }
setReadOnlyValueInfo211   void setReadOnly() {
212     // We expect ro/wo attribute to set only once during
213     // ValueInfo lifetime.
214     assert(getAccessSpecifier() == 0);
215     RefAndFlags.setInt(RefAndFlags.getInt() | ReadOnly);
216   }
setWriteOnlyValueInfo217   void setWriteOnly() {
218     assert(getAccessSpecifier() == 0);
219     RefAndFlags.setInt(RefAndFlags.getInt() | WriteOnly);
220   }
221 
getRefValueInfo222   const GlobalValueSummaryMapTy::value_type *getRef() const {
223     return RefAndFlags.getPointer();
224   }
225 
226   /// Returns the most constraining visibility among summaries. The
227   /// visibilities, ordered from least to most constraining, are: default,
228   /// protected and hidden.
229   GlobalValue::VisibilityTypes getELFVisibility() const;
230 
231   /// Checks if all summaries are DSO local (have the flag set). When DSOLocal
232   /// propagation has been done, set the parameter to enable fast check.
233   bool isDSOLocal(bool WithDSOLocalPropagation = false) const;
234 
235   /// Checks if all copies are eligible for auto-hiding (have flag set).
236   bool canAutoHide() const;
237 };
238 
239 inline raw_ostream &operator<<(raw_ostream &OS, const ValueInfo &VI) {
240   OS << VI.getGUID();
241   if (!VI.name().empty())
242     OS << " (" << VI.name() << ")";
243   return OS;
244 }
245 
246 inline bool operator==(const ValueInfo &A, const ValueInfo &B) {
247   assert(A.getRef() && B.getRef() &&
248          "Need ValueInfo with non-null Ref for comparison");
249   return A.getRef() == B.getRef();
250 }
251 
252 inline bool operator!=(const ValueInfo &A, const ValueInfo &B) {
253   assert(A.getRef() && B.getRef() &&
254          "Need ValueInfo with non-null Ref for comparison");
255   return A.getRef() != B.getRef();
256 }
257 
258 inline bool operator<(const ValueInfo &A, const ValueInfo &B) {
259   assert(A.getRef() && B.getRef() &&
260          "Need ValueInfo with non-null Ref to compare GUIDs");
261   return A.getGUID() < B.getGUID();
262 }
263 
264 template <> struct DenseMapInfo<ValueInfo> {
265   static inline ValueInfo getEmptyKey() {
266     return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8);
267   }
268 
269   static inline ValueInfo getTombstoneKey() {
270     return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-16);
271   }
272 
273   static inline bool isSpecialKey(ValueInfo V) {
274     return V == getTombstoneKey() || V == getEmptyKey();
275   }
276 
277   static bool isEqual(ValueInfo L, ValueInfo R) {
278     // We are not supposed to mix ValueInfo(s) with different HaveGVs flag
279     // in a same container.
280     assert(isSpecialKey(L) || isSpecialKey(R) || (L.haveGVs() == R.haveGVs()));
281     return L.getRef() == R.getRef();
282   }
283   static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); }
284 };
285 
286 /// Function and variable summary information to aid decisions and
287 /// implementation of importing.
288 class GlobalValueSummary {
289 public:
290   /// Sububclass discriminator (for dyn_cast<> et al.)
291   enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
292 
293   /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
294   struct GVFlags {
295     /// The linkage type of the associated global value.
296     ///
297     /// One use is to flag values that have local linkage types and need to
298     /// have module identifier appended before placing into the combined
299     /// index, to disambiguate from other values with the same name.
300     /// In the future this will be used to update and optimize linkage
301     /// types based on global summary-based analysis.
302     unsigned Linkage : 4;
303 
304     /// Indicates the visibility.
305     unsigned Visibility : 2;
306 
307     /// Indicate if the global value cannot be imported (e.g. it cannot
308     /// be renamed or references something that can't be renamed).
309     unsigned NotEligibleToImport : 1;
310 
311     /// In per-module summary, indicate that the global value must be considered
312     /// a live root for index-based liveness analysis. Used for special LLVM
313     /// values such as llvm.global_ctors that the linker does not know about.
314     ///
315     /// In combined summary, indicate that the global value is live.
316     unsigned Live : 1;
317 
318     /// Indicates that the linker resolved the symbol to a definition from
319     /// within the same linkage unit.
320     unsigned DSOLocal : 1;
321 
322     /// In the per-module summary, indicates that the global value is
323     /// linkonce_odr and global unnamed addr (so eligible for auto-hiding
324     /// via hidden visibility). In the combined summary, indicates that the
325     /// prevailing linkonce_odr copy can be auto-hidden via hidden visibility
326     /// when it is upgraded to weak_odr in the backend. This is legal when
327     /// all copies are eligible for auto-hiding (i.e. all copies were
328     /// linkonce_odr global unnamed addr. If any copy is not (e.g. it was
329     /// originally weak_odr, we cannot auto-hide the prevailing copy as it
330     /// means the symbol was externally visible.
331     unsigned CanAutoHide : 1;
332 
333     /// Convenience Constructors
334     explicit GVFlags(GlobalValue::LinkageTypes Linkage,
335                      GlobalValue::VisibilityTypes Visibility,
336                      bool NotEligibleToImport, bool Live, bool IsLocal,
337                      bool CanAutoHide)
338         : Linkage(Linkage), Visibility(Visibility),
339           NotEligibleToImport(NotEligibleToImport), Live(Live),
340           DSOLocal(IsLocal), CanAutoHide(CanAutoHide) {}
341   };
342 
343 private:
344   /// Kind of summary for use in dyn_cast<> et al.
345   SummaryKind Kind;
346 
347   GVFlags Flags;
348 
349   /// This is the hash of the name of the symbol in the original file. It is
350   /// identical to the GUID for global symbols, but differs for local since the
351   /// GUID includes the module level id in the hash.
352   GlobalValue::GUID OriginalName = 0;
353 
354   /// Path of module IR containing value's definition, used to locate
355   /// module during importing.
356   ///
357   /// This is only used during parsing of the combined index, or when
358   /// parsing the per-module index for creation of the combined summary index,
359   /// not during writing of the per-module index which doesn't contain a
360   /// module path string table.
361   StringRef ModulePath;
362 
363   /// List of values referenced by this global value's definition
364   /// (either by the initializer of a global variable, or referenced
365   /// from within a function). This does not include functions called, which
366   /// are listed in the derived FunctionSummary object.
367   std::vector<ValueInfo> RefEdgeList;
368 
369 protected:
370   GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
371       : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {
372     assert((K != AliasKind || Refs.empty()) &&
373            "Expect no references for AliasSummary");
374   }
375 
376 public:
377   virtual ~GlobalValueSummary() = default;
378 
379   /// Returns the hash of the original name, it is identical to the GUID for
380   /// externally visible symbols, but not for local ones.
381   GlobalValue::GUID getOriginalName() const { return OriginalName; }
382 
383   /// Initialize the original name hash in this summary.
384   void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
385 
386   /// Which kind of summary subclass this is.
387   SummaryKind getSummaryKind() const { return Kind; }
388 
389   /// Set the path to the module containing this function, for use in
390   /// the combined index.
391   void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
392 
393   /// Get the path to the module containing this function.
394   StringRef modulePath() const { return ModulePath; }
395 
396   /// Get the flags for this GlobalValue (see \p struct GVFlags).
397   GVFlags flags() const { return Flags; }
398 
399   /// Return linkage type recorded for this global value.
400   GlobalValue::LinkageTypes linkage() const {
401     return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
402   }
403 
404   /// Sets the linkage to the value determined by global summary-based
405   /// optimization. Will be applied in the ThinLTO backends.
406   void setLinkage(GlobalValue::LinkageTypes Linkage) {
407     Flags.Linkage = Linkage;
408   }
409 
410   /// Return true if this global value can't be imported.
411   bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
412 
413   bool isLive() const { return Flags.Live; }
414 
415   void setLive(bool Live) { Flags.Live = Live; }
416 
417   void setDSOLocal(bool Local) { Flags.DSOLocal = Local; }
418 
419   bool isDSOLocal() const { return Flags.DSOLocal; }
420 
421   void setCanAutoHide(bool CanAutoHide) { Flags.CanAutoHide = CanAutoHide; }
422 
423   bool canAutoHide() const { return Flags.CanAutoHide; }
424 
425   GlobalValue::VisibilityTypes getVisibility() const {
426     return (GlobalValue::VisibilityTypes)Flags.Visibility;
427   }
428   void setVisibility(GlobalValue::VisibilityTypes Vis) {
429     Flags.Visibility = (unsigned)Vis;
430   }
431 
432   /// Flag that this global value cannot be imported.
433   void setNotEligibleToImport() { Flags.NotEligibleToImport = true; }
434 
435   /// Return the list of values referenced by this global value definition.
436   ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
437 
438   /// If this is an alias summary, returns the summary of the aliased object (a
439   /// global variable or function), otherwise returns itself.
440   GlobalValueSummary *getBaseObject();
441   const GlobalValueSummary *getBaseObject() const;
442 
443   friend class ModuleSummaryIndex;
444 };
445 
446 /// Alias summary information.
447 class AliasSummary : public GlobalValueSummary {
448   ValueInfo AliaseeValueInfo;
449 
450   /// This is the Aliasee in the same module as alias (could get from VI, trades
451   /// memory for time). Note that this pointer may be null (and the value info
452   /// empty) when we have a distributed index where the alias is being imported
453   /// (as a copy of the aliasee), but the aliasee is not.
454   GlobalValueSummary *AliaseeSummary;
455 
456 public:
457   AliasSummary(GVFlags Flags)
458       : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}),
459         AliaseeSummary(nullptr) {}
460 
461   /// Check if this is an alias summary.
462   static bool classof(const GlobalValueSummary *GVS) {
463     return GVS->getSummaryKind() == AliasKind;
464   }
465 
466   void setAliasee(ValueInfo &AliaseeVI, GlobalValueSummary *Aliasee) {
467     AliaseeValueInfo = AliaseeVI;
468     AliaseeSummary = Aliasee;
469   }
470 
471   bool hasAliasee() const {
472     assert(!!AliaseeSummary == (AliaseeValueInfo &&
473                                 !AliaseeValueInfo.getSummaryList().empty()) &&
474            "Expect to have both aliasee summary and summary list or neither");
475     return !!AliaseeSummary;
476   }
477 
478   const GlobalValueSummary &getAliasee() const {
479     assert(AliaseeSummary && "Unexpected missing aliasee summary");
480     return *AliaseeSummary;
481   }
482 
483   GlobalValueSummary &getAliasee() {
484     return const_cast<GlobalValueSummary &>(
485                          static_cast<const AliasSummary *>(this)->getAliasee());
486   }
487   ValueInfo getAliaseeVI() const {
488     assert(AliaseeValueInfo && "Unexpected missing aliasee");
489     return AliaseeValueInfo;
490   }
491   GlobalValue::GUID getAliaseeGUID() const {
492     assert(AliaseeValueInfo && "Unexpected missing aliasee");
493     return AliaseeValueInfo.getGUID();
494   }
495 };
496 
497 const inline GlobalValueSummary *GlobalValueSummary::getBaseObject() const {
498   if (auto *AS = dyn_cast<AliasSummary>(this))
499     return &AS->getAliasee();
500   return this;
501 }
502 
503 inline GlobalValueSummary *GlobalValueSummary::getBaseObject() {
504   if (auto *AS = dyn_cast<AliasSummary>(this))
505     return &AS->getAliasee();
506   return this;
507 }
508 
509 /// Function summary information to aid decisions and implementation of
510 /// importing.
511 class FunctionSummary : public GlobalValueSummary {
512 public:
513   /// <CalleeValueInfo, CalleeInfo> call edge pair.
514   using EdgeTy = std::pair<ValueInfo, CalleeInfo>;
515 
516   /// Types for -force-summary-edges-cold debugging option.
517   enum ForceSummaryHotnessType : unsigned {
518     FSHT_None,
519     FSHT_AllNonCritical,
520     FSHT_All
521   };
522 
523   /// An "identifier" for a virtual function. This contains the type identifier
524   /// represented as a GUID and the offset from the address point to the virtual
525   /// function pointer, where "address point" is as defined in the Itanium ABI:
526   /// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
527   struct VFuncId {
528     GlobalValue::GUID GUID;
529     uint64_t Offset;
530   };
531 
532   /// A specification for a virtual function call with all constant integer
533   /// arguments. This is used to perform virtual constant propagation on the
534   /// summary.
535   struct ConstVCall {
536     VFuncId VFunc;
537     std::vector<uint64_t> Args;
538   };
539 
540   /// All type identifier related information. Because these fields are
541   /// relatively uncommon we only allocate space for them if necessary.
542   struct TypeIdInfo {
543     /// List of type identifiers used by this function in llvm.type.test
544     /// intrinsics referenced by something other than an llvm.assume intrinsic,
545     /// represented as GUIDs.
546     std::vector<GlobalValue::GUID> TypeTests;
547 
548     /// List of virtual calls made by this function using (respectively)
549     /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do
550     /// not have all constant integer arguments.
551     std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
552 
553     /// List of virtual calls made by this function using (respectively)
554     /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with
555     /// all constant integer arguments.
556     std::vector<ConstVCall> TypeTestAssumeConstVCalls,
557         TypeCheckedLoadConstVCalls;
558   };
559 
560   /// Flags specific to function summaries.
561   struct FFlags {
562     // Function attribute flags. Used to track if a function accesses memory,
563     // recurses or aliases.
564     unsigned ReadNone : 1;
565     unsigned ReadOnly : 1;
566     unsigned NoRecurse : 1;
567     unsigned ReturnDoesNotAlias : 1;
568 
569     // Indicate if the global value cannot be inlined.
570     unsigned NoInline : 1;
571     // Indicate if function should be always inlined.
572     unsigned AlwaysInline : 1;
573   };
574 
575   /// Describes the uses of a parameter by the function.
576   struct ParamAccess {
577     static constexpr uint32_t RangeWidth = 64;
578 
579     /// Describes the use of a value in a call instruction, specifying the
580     /// call's target, the value's parameter number, and the possible range of
581     /// offsets from the beginning of the value that are passed.
582     struct Call {
583       uint64_t ParamNo = 0;
584       ValueInfo Callee;
585       ConstantRange Offsets{/*BitWidth=*/RangeWidth, /*isFullSet=*/true};
586 
587       Call() = default;
588       Call(uint64_t ParamNo, ValueInfo Callee, const ConstantRange &Offsets)
589           : ParamNo(ParamNo), Callee(Callee), Offsets(Offsets) {}
590     };
591 
592     uint64_t ParamNo = 0;
593     /// The range contains byte offsets from the parameter pointer which
594     /// accessed by the function. In the per-module summary, it only includes
595     /// accesses made by the function instructions. In the combined summary, it
596     /// also includes accesses by nested function calls.
597     ConstantRange Use{/*BitWidth=*/RangeWidth, /*isFullSet=*/true};
598     /// In the per-module summary, it summarizes the byte offset applied to each
599     /// pointer parameter before passing to each corresponding callee.
600     /// In the combined summary, it's empty and information is propagated by
601     /// inter-procedural analysis and applied to the Use field.
602     std::vector<Call> Calls;
603 
604     ParamAccess() = default;
605     ParamAccess(uint64_t ParamNo, const ConstantRange &Use)
606         : ParamNo(ParamNo), Use(Use) {}
607   };
608 
609   /// Create an empty FunctionSummary (with specified call edges).
610   /// Used to represent external nodes and the dummy root node.
611   static FunctionSummary
612   makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) {
613     return FunctionSummary(
614         FunctionSummary::GVFlags(
615             GlobalValue::LinkageTypes::AvailableExternallyLinkage,
616             GlobalValue::DefaultVisibility,
617             /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false,
618             /*CanAutoHide=*/false),
619         /*NumInsts=*/0, FunctionSummary::FFlags{}, /*EntryCount=*/0,
620         std::vector<ValueInfo>(), std::move(Edges),
621         std::vector<GlobalValue::GUID>(),
622         std::vector<FunctionSummary::VFuncId>(),
623         std::vector<FunctionSummary::VFuncId>(),
624         std::vector<FunctionSummary::ConstVCall>(),
625         std::vector<FunctionSummary::ConstVCall>(),
626         std::vector<FunctionSummary::ParamAccess>());
627   }
628 
629   /// A dummy node to reference external functions that aren't in the index
630   static FunctionSummary ExternalNode;
631 
632 private:
633   /// Number of instructions (ignoring debug instructions, e.g.) computed
634   /// during the initial compile step when the summary index is first built.
635   unsigned InstCount;
636 
637   /// Function summary specific flags.
638   FFlags FunFlags;
639 
640   /// The synthesized entry count of the function.
641   /// This is only populated during ThinLink phase and remains unused while
642   /// generating per-module summaries.
643   uint64_t EntryCount = 0;
644 
645   /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
646   std::vector<EdgeTy> CallGraphEdgeList;
647 
648   std::unique_ptr<TypeIdInfo> TIdInfo;
649 
650   /// Uses for every parameter to this function.
651   using ParamAccessesTy = std::vector<ParamAccess>;
652   std::unique_ptr<ParamAccessesTy> ParamAccesses;
653 
654 public:
655   FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
656                   uint64_t EntryCount, std::vector<ValueInfo> Refs,
657                   std::vector<EdgeTy> CGEdges,
658                   std::vector<GlobalValue::GUID> TypeTests,
659                   std::vector<VFuncId> TypeTestAssumeVCalls,
660                   std::vector<VFuncId> TypeCheckedLoadVCalls,
661                   std::vector<ConstVCall> TypeTestAssumeConstVCalls,
662                   std::vector<ConstVCall> TypeCheckedLoadConstVCalls,
663                   std::vector<ParamAccess> Params)
664       : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
665         InstCount(NumInsts), FunFlags(FunFlags), EntryCount(EntryCount),
666         CallGraphEdgeList(std::move(CGEdges)) {
667     if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
668         !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
669         !TypeCheckedLoadConstVCalls.empty())
670       TIdInfo = std::make_unique<TypeIdInfo>(
671           TypeIdInfo{std::move(TypeTests), std::move(TypeTestAssumeVCalls),
672                      std::move(TypeCheckedLoadVCalls),
673                      std::move(TypeTestAssumeConstVCalls),
674                      std::move(TypeCheckedLoadConstVCalls)});
675     if (!Params.empty())
676       ParamAccesses = std::make_unique<ParamAccessesTy>(std::move(Params));
677   }
678   // Gets the number of readonly and writeonly refs in RefEdgeList
679   std::pair<unsigned, unsigned> specialRefCounts() const;
680 
681   /// Check if this is a function summary.
682   static bool classof(const GlobalValueSummary *GVS) {
683     return GVS->getSummaryKind() == FunctionKind;
684   }
685 
686   /// Get function summary flags.
687   FFlags fflags() const { return FunFlags; }
688 
689   /// Get the instruction count recorded for this function.
690   unsigned instCount() const { return InstCount; }
691 
692   /// Get the synthetic entry count for this function.
693   uint64_t entryCount() const { return EntryCount; }
694 
695   /// Set the synthetic entry count for this function.
696   void setEntryCount(uint64_t EC) { EntryCount = EC; }
697 
698   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
699   ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
700 
701   void addCall(EdgeTy E) { CallGraphEdgeList.push_back(E); }
702 
703   /// Returns the list of type identifiers used by this function in
704   /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
705   /// represented as GUIDs.
706   ArrayRef<GlobalValue::GUID> type_tests() const {
707     if (TIdInfo)
708       return TIdInfo->TypeTests;
709     return {};
710   }
711 
712   /// Returns the list of virtual calls made by this function using
713   /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
714   /// integer arguments.
715   ArrayRef<VFuncId> type_test_assume_vcalls() const {
716     if (TIdInfo)
717       return TIdInfo->TypeTestAssumeVCalls;
718     return {};
719   }
720 
721   /// Returns the list of virtual calls made by this function using
722   /// llvm.type.checked.load intrinsics that do not have all constant integer
723   /// arguments.
724   ArrayRef<VFuncId> type_checked_load_vcalls() const {
725     if (TIdInfo)
726       return TIdInfo->TypeCheckedLoadVCalls;
727     return {};
728   }
729 
730   /// Returns the list of virtual calls made by this function using
731   /// llvm.assume(llvm.type.test) intrinsics with all constant integer
732   /// arguments.
733   ArrayRef<ConstVCall> type_test_assume_const_vcalls() const {
734     if (TIdInfo)
735       return TIdInfo->TypeTestAssumeConstVCalls;
736     return {};
737   }
738 
739   /// Returns the list of virtual calls made by this function using
740   /// llvm.type.checked.load intrinsics with all constant integer arguments.
741   ArrayRef<ConstVCall> type_checked_load_const_vcalls() const {
742     if (TIdInfo)
743       return TIdInfo->TypeCheckedLoadConstVCalls;
744     return {};
745   }
746 
747   /// Returns the list of known uses of pointer parameters.
748   ArrayRef<ParamAccess> paramAccesses() const {
749     if (ParamAccesses)
750       return *ParamAccesses;
751     return {};
752   }
753 
754   /// Sets the list of known uses of pointer parameters.
755   void setParamAccesses(std::vector<ParamAccess> NewParams) {
756     if (NewParams.empty())
757       ParamAccesses.reset();
758     else if (ParamAccesses)
759       *ParamAccesses = std::move(NewParams);
760     else
761       ParamAccesses = std::make_unique<ParamAccessesTy>(std::move(NewParams));
762   }
763 
764   /// Add a type test to the summary. This is used by WholeProgramDevirt if we
765   /// were unable to devirtualize a checked call.
766   void addTypeTest(GlobalValue::GUID Guid) {
767     if (!TIdInfo)
768       TIdInfo = std::make_unique<TypeIdInfo>();
769     TIdInfo->TypeTests.push_back(Guid);
770   }
771 
772   const TypeIdInfo *getTypeIdInfo() const { return TIdInfo.get(); };
773 
774   friend struct GraphTraits<ValueInfo>;
775 };
776 
777 template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
778   static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
779 
780   static FunctionSummary::VFuncId getTombstoneKey() {
781     return {0, uint64_t(-2)};
782   }
783 
784   static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R) {
785     return L.GUID == R.GUID && L.Offset == R.Offset;
786   }
787 
788   static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
789 };
790 
791 template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
792   static FunctionSummary::ConstVCall getEmptyKey() {
793     return {{0, uint64_t(-1)}, {}};
794   }
795 
796   static FunctionSummary::ConstVCall getTombstoneKey() {
797     return {{0, uint64_t(-2)}, {}};
798   }
799 
800   static bool isEqual(FunctionSummary::ConstVCall L,
801                       FunctionSummary::ConstVCall R) {
802     return DenseMapInfo<FunctionSummary::VFuncId>::isEqual(L.VFunc, R.VFunc) &&
803            L.Args == R.Args;
804   }
805 
806   static unsigned getHashValue(FunctionSummary::ConstVCall I) {
807     return I.VFunc.GUID;
808   }
809 };
810 
811 /// The ValueInfo and offset for a function within a vtable definition
812 /// initializer array.
813 struct VirtFuncOffset {
814   VirtFuncOffset(ValueInfo VI, uint64_t Offset)
815       : FuncVI(VI), VTableOffset(Offset) {}
816 
817   ValueInfo FuncVI;
818   uint64_t VTableOffset;
819 };
820 /// List of functions referenced by a particular vtable definition.
821 using VTableFuncList = std::vector<VirtFuncOffset>;
822 
823 /// Global variable summary information to aid decisions and
824 /// implementation of importing.
825 ///
826 /// Global variable summary has two extra flag, telling if it is
827 /// readonly or writeonly. Both readonly and writeonly variables
828 /// can be optimized in the backed: readonly variables can be
829 /// const-folded, while writeonly vars can be completely eliminated
830 /// together with corresponding stores. We let both things happen
831 /// by means of internalizing such variables after ThinLTO import.
832 class GlobalVarSummary : public GlobalValueSummary {
833 private:
834   /// For vtable definitions this holds the list of functions and
835   /// their corresponding offsets within the initializer array.
836   std::unique_ptr<VTableFuncList> VTableFuncs;
837 
838 public:
839   struct GVarFlags {
840     GVarFlags(bool ReadOnly, bool WriteOnly, bool Constant,
841               GlobalObject::VCallVisibility Vis)
842         : MaybeReadOnly(ReadOnly), MaybeWriteOnly(WriteOnly),
843           Constant(Constant), VCallVisibility(Vis) {}
844 
845     // If true indicates that this global variable might be accessed
846     // purely by non-volatile load instructions. This in turn means
847     // it can be internalized in source and destination modules during
848     // thin LTO import because it neither modified nor its address
849     // is taken.
850     unsigned MaybeReadOnly : 1;
851     // If true indicates that variable is possibly only written to, so
852     // its value isn't loaded and its address isn't taken anywhere.
853     // False, when 'Constant' attribute is set.
854     unsigned MaybeWriteOnly : 1;
855     // Indicates that value is a compile-time constant. Global variable
856     // can be 'Constant' while not being 'ReadOnly' on several occasions:
857     // - it is volatile, (e.g mapped device address)
858     // - its address is taken, meaning that unlike 'ReadOnly' vars we can't
859     //   internalize it.
860     // Constant variables are always imported thus giving compiler an
861     // opportunity to make some extra optimizations. Readonly constants
862     // are also internalized.
863     unsigned Constant : 1;
864     // Set from metadata on vtable definitions during the module summary
865     // analysis.
866     unsigned VCallVisibility : 2;
867   } VarFlags;
868 
869   GlobalVarSummary(GVFlags Flags, GVarFlags VarFlags,
870                    std::vector<ValueInfo> Refs)
871       : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)),
872         VarFlags(VarFlags) {}
873 
874   /// Check if this is a global variable summary.
875   static bool classof(const GlobalValueSummary *GVS) {
876     return GVS->getSummaryKind() == GlobalVarKind;
877   }
878 
879   GVarFlags varflags() const { return VarFlags; }
880   void setReadOnly(bool RO) { VarFlags.MaybeReadOnly = RO; }
881   void setWriteOnly(bool WO) { VarFlags.MaybeWriteOnly = WO; }
882   bool maybeReadOnly() const { return VarFlags.MaybeReadOnly; }
883   bool maybeWriteOnly() const { return VarFlags.MaybeWriteOnly; }
884   bool isConstant() const { return VarFlags.Constant; }
885   void setVCallVisibility(GlobalObject::VCallVisibility Vis) {
886     VarFlags.VCallVisibility = Vis;
887   }
888   GlobalObject::VCallVisibility getVCallVisibility() const {
889     return (GlobalObject::VCallVisibility)VarFlags.VCallVisibility;
890   }
891 
892   void setVTableFuncs(VTableFuncList Funcs) {
893     assert(!VTableFuncs);
894     VTableFuncs = std::make_unique<VTableFuncList>(std::move(Funcs));
895   }
896 
897   ArrayRef<VirtFuncOffset> vTableFuncs() const {
898     if (VTableFuncs)
899       return *VTableFuncs;
900     return {};
901   }
902 };
903 
904 struct TypeTestResolution {
905   /// Specifies which kind of type check we should emit for this byte array.
906   /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
907   /// details on each kind of check; the enumerators are described with
908   /// reference to that document.
909   enum Kind {
910     Unsat,     ///< Unsatisfiable type (i.e. no global has this type metadata)
911     ByteArray, ///< Test a byte array (first example)
912     Inline,    ///< Inlined bit vector ("Short Inline Bit Vectors")
913     Single,    ///< Single element (last example in "Short Inline Bit Vectors")
914     AllOnes,   ///< All-ones bit vector ("Eliminating Bit Vector Checks for
915                ///  All-Ones Bit Vectors")
916     Unknown,   ///< Unknown (analysis not performed, don't lower)
917   } TheKind = Unknown;
918 
919   /// Range of size-1 expressed as a bit width. For example, if the size is in
920   /// range [1,256], this number will be 8. This helps generate the most compact
921   /// instruction sequences.
922   unsigned SizeM1BitWidth = 0;
923 
924   // The following fields are only used if the target does not support the use
925   // of absolute symbols to store constants. Their meanings are the same as the
926   // corresponding fields in LowerTypeTestsModule::TypeIdLowering in
927   // LowerTypeTests.cpp.
928 
929   uint64_t AlignLog2 = 0;
930   uint64_t SizeM1 = 0;
931   uint8_t BitMask = 0;
932   uint64_t InlineBits = 0;
933 };
934 
935 struct WholeProgramDevirtResolution {
936   enum Kind {
937     Indir,        ///< Just do a regular virtual call
938     SingleImpl,   ///< Single implementation devirtualization
939     BranchFunnel, ///< When retpoline mitigation is enabled, use a branch funnel
940                   ///< that is defined in the merged module. Otherwise same as
941                   ///< Indir.
942   } TheKind = Indir;
943 
944   std::string SingleImplName;
945 
946   struct ByArg {
947     enum Kind {
948       Indir,            ///< Just do a regular virtual call
949       UniformRetVal,    ///< Uniform return value optimization
950       UniqueRetVal,     ///< Unique return value optimization
951       VirtualConstProp, ///< Virtual constant propagation
952     } TheKind = Indir;
953 
954     /// Additional information for the resolution:
955     /// - UniformRetVal: the uniform return value.
956     /// - UniqueRetVal: the return value associated with the unique vtable (0 or
957     ///   1).
958     uint64_t Info = 0;
959 
960     // The following fields are only used if the target does not support the use
961     // of absolute symbols to store constants.
962 
963     uint32_t Byte = 0;
964     uint32_t Bit = 0;
965   };
966 
967   /// Resolutions for calls with all constant integer arguments (excluding the
968   /// first argument, "this"), where the key is the argument vector.
969   std::map<std::vector<uint64_t>, ByArg> ResByArg;
970 };
971 
972 struct TypeIdSummary {
973   TypeTestResolution TTRes;
974 
975   /// Mapping from byte offset to whole-program devirt resolution for that
976   /// (typeid, byte offset) pair.
977   std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
978 };
979 
980 /// 160 bits SHA1
981 using ModuleHash = std::array<uint32_t, 5>;
982 
983 /// Type used for iterating through the global value summary map.
984 using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
985 using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
986 
987 /// String table to hold/own module path strings, which additionally holds the
988 /// module ID assigned to each module during the plugin step, as well as a hash
989 /// of the module. The StringMap makes a copy of and owns inserted strings.
990 using ModulePathStringTableTy = StringMap<std::pair<uint64_t, ModuleHash>>;
991 
992 /// Map of global value GUID to its summary, used to identify values defined in
993 /// a particular module, and provide efficient access to their summary.
994 using GVSummaryMapTy = DenseMap<GlobalValue::GUID, GlobalValueSummary *>;
995 
996 /// Map of a type GUID to type id string and summary (multimap used
997 /// in case of GUID conflicts).
998 using TypeIdSummaryMapTy =
999     std::multimap<GlobalValue::GUID, std::pair<std::string, TypeIdSummary>>;
1000 
1001 /// The following data structures summarize type metadata information.
1002 /// For type metadata overview see https://llvm.org/docs/TypeMetadata.html.
1003 /// Each type metadata includes both the type identifier and the offset of
1004 /// the address point of the type (the address held by objects of that type
1005 /// which may not be the beginning of the virtual table). Vtable definitions
1006 /// are decorated with type metadata for the types they are compatible with.
1007 ///
1008 /// Holds information about vtable definitions decorated with type metadata:
1009 /// the vtable definition value and its address point offset in a type
1010 /// identifier metadata it is decorated (compatible) with.
1011 struct TypeIdOffsetVtableInfo {
1012   TypeIdOffsetVtableInfo(uint64_t Offset, ValueInfo VI)
1013       : AddressPointOffset(Offset), VTableVI(VI) {}
1014 
1015   uint64_t AddressPointOffset;
1016   ValueInfo VTableVI;
1017 };
1018 /// List of vtable definitions decorated by a particular type identifier,
1019 /// and their corresponding offsets in that type identifier's metadata.
1020 /// Note that each type identifier may be compatible with multiple vtables, due
1021 /// to inheritance, which is why this is a vector.
1022 using TypeIdCompatibleVtableInfo = std::vector<TypeIdOffsetVtableInfo>;
1023 
1024 /// Class to hold module path string table and global value map,
1025 /// and encapsulate methods for operating on them.
1026 class ModuleSummaryIndex {
1027 private:
1028   /// Map from value name to list of summary instances for values of that
1029   /// name (may be duplicates in the COMDAT case, e.g.).
1030   GlobalValueSummaryMapTy GlobalValueMap;
1031 
1032   /// Holds strings for combined index, mapping to the corresponding module ID.
1033   ModulePathStringTableTy ModulePathStringTable;
1034 
1035   /// Mapping from type identifier GUIDs to type identifier and its summary
1036   /// information. Produced by thin link.
1037   TypeIdSummaryMapTy TypeIdMap;
1038 
1039   /// Mapping from type identifier to information about vtables decorated
1040   /// with that type identifier's metadata. Produced by per module summary
1041   /// analysis and consumed by thin link. For more information, see description
1042   /// above where TypeIdCompatibleVtableInfo is defined.
1043   std::map<std::string, TypeIdCompatibleVtableInfo, std::less<>>
1044       TypeIdCompatibleVtableMap;
1045 
1046   /// Mapping from original ID to GUID. If original ID can map to multiple
1047   /// GUIDs, it will be mapped to 0.
1048   std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
1049 
1050   /// Indicates that summary-based GlobalValue GC has run, and values with
1051   /// GVFlags::Live==false are really dead. Otherwise, all values must be
1052   /// considered live.
1053   bool WithGlobalValueDeadStripping = false;
1054 
1055   /// Indicates that summary-based attribute propagation has run and
1056   /// GVarFlags::MaybeReadonly / GVarFlags::MaybeWriteonly are really
1057   /// read/write only.
1058   bool WithAttributePropagation = false;
1059 
1060   /// Indicates that summary-based DSOLocal propagation has run and the flag in
1061   /// every summary of a GV is synchronized.
1062   bool WithDSOLocalPropagation = false;
1063 
1064   /// Indicates that summary-based synthetic entry count propagation has run
1065   bool HasSyntheticEntryCounts = false;
1066 
1067   /// Indicates that distributed backend should skip compilation of the
1068   /// module. Flag is suppose to be set by distributed ThinLTO indexing
1069   /// when it detected that the module is not needed during the final
1070   /// linking. As result distributed backend should just output a minimal
1071   /// valid object file.
1072   bool SkipModuleByDistributedBackend = false;
1073 
1074   /// If true then we're performing analysis of IR module, or parsing along with
1075   /// the IR from assembly. The value of 'false' means we're reading summary
1076   /// from BC or YAML source. Affects the type of value stored in NameOrGV
1077   /// union.
1078   bool HaveGVs;
1079 
1080   // True if the index was created for a module compiled with -fsplit-lto-unit.
1081   bool EnableSplitLTOUnit;
1082 
1083   // True if some of the modules were compiled with -fsplit-lto-unit and
1084   // some were not. Set when the combined index is created during the thin link.
1085   bool PartiallySplitLTOUnits = false;
1086 
1087   /// True if some of the FunctionSummary contains a ParamAccess.
1088   bool HasParamAccess = false;
1089 
1090   std::set<std::string> CfiFunctionDefs;
1091   std::set<std::string> CfiFunctionDecls;
1092 
1093   // Used in cases where we want to record the name of a global, but
1094   // don't have the string owned elsewhere (e.g. the Strtab on a module).
1095   StringSaver Saver;
1096   BumpPtrAllocator Alloc;
1097 
1098   // The total number of basic blocks in the module in the per-module summary or
1099   // the total number of basic blocks in the LTO unit in the combined index.
1100   uint64_t BlockCount;
1101 
1102   // YAML I/O support.
1103   friend yaml::MappingTraits<ModuleSummaryIndex>;
1104 
1105   GlobalValueSummaryMapTy::value_type *
1106   getOrInsertValuePtr(GlobalValue::GUID GUID) {
1107     return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs))
1108                  .first;
1109   }
1110 
1111 public:
1112   // See HaveGVs variable comment.
1113   ModuleSummaryIndex(bool HaveGVs, bool EnableSplitLTOUnit = false)
1114       : HaveGVs(HaveGVs), EnableSplitLTOUnit(EnableSplitLTOUnit), Saver(Alloc),
1115         BlockCount(0) {}
1116 
1117   // Current version for the module summary in bitcode files.
1118   // The BitcodeSummaryVersion should be bumped whenever we introduce changes
1119   // in the way some record are interpreted, like flags for instance.
1120   // Note that incrementing this may require changes in both BitcodeReader.cpp
1121   // and BitcodeWriter.cpp.
1122   static constexpr uint64_t BitcodeSummaryVersion = 9;
1123 
1124   // Regular LTO module name for ASM writer
1125   static constexpr const char *getRegularLTOModuleName() {
1126     return "[Regular LTO]";
1127   }
1128 
1129   bool haveGVs() const { return HaveGVs; }
1130 
1131   uint64_t getFlags() const;
1132   void setFlags(uint64_t Flags);
1133 
1134   uint64_t getBlockCount() const { return BlockCount; }
1135   void addBlockCount(uint64_t C) { BlockCount += C; }
1136   void setBlockCount(uint64_t C) { BlockCount = C; }
1137 
1138   gvsummary_iterator begin() { return GlobalValueMap.begin(); }
1139   const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
1140   gvsummary_iterator end() { return GlobalValueMap.end(); }
1141   const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
1142   size_t size() const { return GlobalValueMap.size(); }
1143 
1144   /// Convenience function for doing a DFS on a ValueInfo. Marks the function in
1145   /// the FunctionHasParent map.
1146   static void discoverNodes(ValueInfo V,
1147                             std::map<ValueInfo, bool> &FunctionHasParent) {
1148     if (!V.getSummaryList().size())
1149       return; // skip external functions that don't have summaries
1150 
1151     // Mark discovered if we haven't yet
1152     auto S = FunctionHasParent.emplace(V, false);
1153 
1154     // Stop if we've already discovered this node
1155     if (!S.second)
1156       return;
1157 
1158     FunctionSummary *F =
1159         dyn_cast<FunctionSummary>(V.getSummaryList().front().get());
1160     assert(F != nullptr && "Expected FunctionSummary node");
1161 
1162     for (auto &C : F->calls()) {
1163       // Insert node if necessary
1164       auto S = FunctionHasParent.emplace(C.first, true);
1165 
1166       // Skip nodes that we're sure have parents
1167       if (!S.second && S.first->second)
1168         continue;
1169 
1170       if (S.second)
1171         discoverNodes(C.first, FunctionHasParent);
1172       else
1173         S.first->second = true;
1174     }
1175   }
1176 
1177   // Calculate the callgraph root
1178   FunctionSummary calculateCallGraphRoot() {
1179     // Functions that have a parent will be marked in FunctionHasParent pair.
1180     // Once we've marked all functions, the functions in the map that are false
1181     // have no parent (so they're the roots)
1182     std::map<ValueInfo, bool> FunctionHasParent;
1183 
1184     for (auto &S : *this) {
1185       // Skip external functions
1186       if (!S.second.SummaryList.size() ||
1187           !isa<FunctionSummary>(S.second.SummaryList.front().get()))
1188         continue;
1189       discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent);
1190     }
1191 
1192     std::vector<FunctionSummary::EdgeTy> Edges;
1193     // create edges to all roots in the Index
1194     for (auto &P : FunctionHasParent) {
1195       if (P.second)
1196         continue; // skip over non-root nodes
1197       Edges.push_back(std::make_pair(P.first, CalleeInfo{}));
1198     }
1199     if (Edges.empty()) {
1200       // Failed to find root - return an empty node
1201       return FunctionSummary::makeDummyFunctionSummary({});
1202     }
1203     auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
1204     return CallGraphRoot;
1205   }
1206 
1207   bool withGlobalValueDeadStripping() const {
1208     return WithGlobalValueDeadStripping;
1209   }
1210   void setWithGlobalValueDeadStripping() {
1211     WithGlobalValueDeadStripping = true;
1212   }
1213 
1214   bool withAttributePropagation() const { return WithAttributePropagation; }
1215   void setWithAttributePropagation() {
1216     WithAttributePropagation = true;
1217   }
1218 
1219   bool withDSOLocalPropagation() const { return WithDSOLocalPropagation; }
1220   void setWithDSOLocalPropagation() { WithDSOLocalPropagation = true; }
1221 
1222   bool isReadOnly(const GlobalVarSummary *GVS) const {
1223     return WithAttributePropagation && GVS->maybeReadOnly();
1224   }
1225   bool isWriteOnly(const GlobalVarSummary *GVS) const {
1226     return WithAttributePropagation && GVS->maybeWriteOnly();
1227   }
1228 
1229   bool hasSyntheticEntryCounts() const { return HasSyntheticEntryCounts; }
1230   void setHasSyntheticEntryCounts() { HasSyntheticEntryCounts = true; }
1231 
1232   bool skipModuleByDistributedBackend() const {
1233     return SkipModuleByDistributedBackend;
1234   }
1235   void setSkipModuleByDistributedBackend() {
1236     SkipModuleByDistributedBackend = true;
1237   }
1238 
1239   bool enableSplitLTOUnit() const { return EnableSplitLTOUnit; }
1240   void setEnableSplitLTOUnit() { EnableSplitLTOUnit = true; }
1241 
1242   bool partiallySplitLTOUnits() const { return PartiallySplitLTOUnits; }
1243   void setPartiallySplitLTOUnits() { PartiallySplitLTOUnits = true; }
1244 
1245   bool hasParamAccess() const { return HasParamAccess; }
1246 
1247   bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
1248     return !WithGlobalValueDeadStripping || GVS->isLive();
1249   }
1250   bool isGUIDLive(GlobalValue::GUID GUID) const;
1251 
1252   /// Return a ValueInfo for the index value_type (convenient when iterating
1253   /// index).
1254   ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const {
1255     return ValueInfo(HaveGVs, &R);
1256   }
1257 
1258   /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
1259   ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
1260     auto I = GlobalValueMap.find(GUID);
1261     return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I);
1262   }
1263 
1264   /// Return a ValueInfo for \p GUID.
1265   ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) {
1266     return ValueInfo(HaveGVs, getOrInsertValuePtr(GUID));
1267   }
1268 
1269   // Save a string in the Index. Use before passing Name to
1270   // getOrInsertValueInfo when the string isn't owned elsewhere (e.g. on the
1271   // module's Strtab).
1272   StringRef saveString(StringRef String) { return Saver.save(String); }
1273 
1274   /// Return a ValueInfo for \p GUID setting value \p Name.
1275   ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name) {
1276     assert(!HaveGVs);
1277     auto VP = getOrInsertValuePtr(GUID);
1278     VP->second.U.Name = Name;
1279     return ValueInfo(HaveGVs, VP);
1280   }
1281 
1282   /// Return a ValueInfo for \p GV and mark it as belonging to GV.
1283   ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
1284     assert(HaveGVs);
1285     auto VP = getOrInsertValuePtr(GV->getGUID());
1286     VP->second.U.GV = GV;
1287     return ValueInfo(HaveGVs, VP);
1288   }
1289 
1290   /// Return the GUID for \p OriginalId in the OidGuidMap.
1291   GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const {
1292     const auto I = OidGuidMap.find(OriginalID);
1293     return I == OidGuidMap.end() ? 0 : I->second;
1294   }
1295 
1296   std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; }
1297   const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; }
1298 
1299   std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; }
1300   const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; }
1301 
1302   /// Add a global value summary for a value.
1303   void addGlobalValueSummary(const GlobalValue &GV,
1304                              std::unique_ptr<GlobalValueSummary> Summary) {
1305     addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary));
1306   }
1307 
1308   /// Add a global value summary for a value of the given name.
1309   void addGlobalValueSummary(StringRef ValueName,
1310                              std::unique_ptr<GlobalValueSummary> Summary) {
1311     addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
1312                           std::move(Summary));
1313   }
1314 
1315   /// Add a global value summary for the given ValueInfo.
1316   void addGlobalValueSummary(ValueInfo VI,
1317                              std::unique_ptr<GlobalValueSummary> Summary) {
1318     if (const FunctionSummary *FS = dyn_cast<FunctionSummary>(Summary.get()))
1319       HasParamAccess |= !FS->paramAccesses().empty();
1320     addOriginalName(VI.getGUID(), Summary->getOriginalName());
1321     // Here we have a notionally const VI, but the value it points to is owned
1322     // by the non-const *this.
1323     const_cast<GlobalValueSummaryMapTy::value_type *>(VI.getRef())
1324         ->second.SummaryList.push_back(std::move(Summary));
1325   }
1326 
1327   /// Add an original name for the value of the given GUID.
1328   void addOriginalName(GlobalValue::GUID ValueGUID,
1329                        GlobalValue::GUID OrigGUID) {
1330     if (OrigGUID == 0 || ValueGUID == OrigGUID)
1331       return;
1332     if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
1333       OidGuidMap[OrigGUID] = 0;
1334     else
1335       OidGuidMap[OrigGUID] = ValueGUID;
1336   }
1337 
1338   /// Find the summary for ValueInfo \p VI in module \p ModuleId, or nullptr if
1339   /// not found.
1340   GlobalValueSummary *findSummaryInModule(ValueInfo VI, StringRef ModuleId) const {
1341     auto SummaryList = VI.getSummaryList();
1342     auto Summary =
1343         llvm::find_if(SummaryList,
1344                       [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
1345                         return Summary->modulePath() == ModuleId;
1346                       });
1347     if (Summary == SummaryList.end())
1348       return nullptr;
1349     return Summary->get();
1350   }
1351 
1352   /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
1353   /// not found.
1354   GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
1355                                           StringRef ModuleId) const {
1356     auto CalleeInfo = getValueInfo(ValueGUID);
1357     if (!CalleeInfo)
1358       return nullptr; // This function does not have a summary
1359     return findSummaryInModule(CalleeInfo, ModuleId);
1360   }
1361 
1362   /// Returns the first GlobalValueSummary for \p GV, asserting that there
1363   /// is only one if \p PerModuleIndex.
1364   GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
1365                                             bool PerModuleIndex = true) const {
1366     assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
1367     return getGlobalValueSummary(GV.getGUID(), PerModuleIndex);
1368   }
1369 
1370   /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
1371   /// there
1372   /// is only one if \p PerModuleIndex.
1373   GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
1374                                             bool PerModuleIndex = true) const;
1375 
1376   /// Table of modules, containing module hash and id.
1377   const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
1378     return ModulePathStringTable;
1379   }
1380 
1381   /// Table of modules, containing hash and id.
1382   StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
1383     return ModulePathStringTable;
1384   }
1385 
1386   /// Get the module ID recorded for the given module path.
1387   uint64_t getModuleId(const StringRef ModPath) const {
1388     return ModulePathStringTable.lookup(ModPath).first;
1389   }
1390 
1391   /// Get the module SHA1 hash recorded for the given module path.
1392   const ModuleHash &getModuleHash(const StringRef ModPath) const {
1393     auto It = ModulePathStringTable.find(ModPath);
1394     assert(It != ModulePathStringTable.end() && "Module not registered");
1395     return It->second.second;
1396   }
1397 
1398   /// Convenience method for creating a promoted global name
1399   /// for the given value name of a local, and its original module's ID.
1400   static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
1401     SmallString<256> NewName(Name);
1402     NewName += ".llvm.";
1403     NewName += utostr((uint64_t(ModHash[0]) << 32) |
1404                       ModHash[1]); // Take the first 64 bits
1405     return std::string(NewName.str());
1406   }
1407 
1408   /// Helper to obtain the unpromoted name for a global value (or the original
1409   /// name if not promoted). Split off the rightmost ".llvm.${hash}" suffix,
1410   /// because it is possible in certain clients (not clang at the moment) for
1411   /// two rounds of ThinLTO optimization and therefore promotion to occur.
1412   static StringRef getOriginalNameBeforePromote(StringRef Name) {
1413     std::pair<StringRef, StringRef> Pair = Name.rsplit(".llvm.");
1414     return Pair.first;
1415   }
1416 
1417   typedef ModulePathStringTableTy::value_type ModuleInfo;
1418 
1419   /// Add a new module with the given \p Hash, mapped to the given \p
1420   /// ModID, and return a reference to the module.
1421   ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
1422                         ModuleHash Hash = ModuleHash{{0}}) {
1423     return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first;
1424   }
1425 
1426   /// Return module entry for module with the given \p ModPath.
1427   ModuleInfo *getModule(StringRef ModPath) {
1428     auto It = ModulePathStringTable.find(ModPath);
1429     assert(It != ModulePathStringTable.end() && "Module not registered");
1430     return &*It;
1431   }
1432 
1433   /// Check if the given Module has any functions available for exporting
1434   /// in the index. We consider any module present in the ModulePathStringTable
1435   /// to have exported functions.
1436   bool hasExportedFunctions(const Module &M) const {
1437     return ModulePathStringTable.count(M.getModuleIdentifier());
1438   }
1439 
1440   const TypeIdSummaryMapTy &typeIds() const { return TypeIdMap; }
1441 
1442   /// Return an existing or new TypeIdSummary entry for \p TypeId.
1443   /// This accessor can mutate the map and therefore should not be used in
1444   /// the ThinLTO backends.
1445   TypeIdSummary &getOrInsertTypeIdSummary(StringRef TypeId) {
1446     auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1447     for (auto It = TidIter.first; It != TidIter.second; ++It)
1448       if (It->second.first == TypeId)
1449         return It->second.second;
1450     auto It = TypeIdMap.insert(
1451         {GlobalValue::getGUID(TypeId), {std::string(TypeId), TypeIdSummary()}});
1452     return It->second.second;
1453   }
1454 
1455   /// This returns either a pointer to the type id summary (if present in the
1456   /// summary map) or null (if not present). This may be used when importing.
1457   const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const {
1458     auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1459     for (auto It = TidIter.first; It != TidIter.second; ++It)
1460       if (It->second.first == TypeId)
1461         return &It->second.second;
1462     return nullptr;
1463   }
1464 
1465   TypeIdSummary *getTypeIdSummary(StringRef TypeId) {
1466     return const_cast<TypeIdSummary *>(
1467         static_cast<const ModuleSummaryIndex *>(this)->getTypeIdSummary(
1468             TypeId));
1469   }
1470 
1471   const auto &typeIdCompatibleVtableMap() const {
1472     return TypeIdCompatibleVtableMap;
1473   }
1474 
1475   /// Return an existing or new TypeIdCompatibleVtableMap entry for \p TypeId.
1476   /// This accessor can mutate the map and therefore should not be used in
1477   /// the ThinLTO backends.
1478   TypeIdCompatibleVtableInfo &
1479   getOrInsertTypeIdCompatibleVtableSummary(StringRef TypeId) {
1480     return TypeIdCompatibleVtableMap[std::string(TypeId)];
1481   }
1482 
1483   /// For the given \p TypeId, this returns the TypeIdCompatibleVtableMap
1484   /// entry if present in the summary map. This may be used when importing.
1485   Optional<TypeIdCompatibleVtableInfo>
1486   getTypeIdCompatibleVtableSummary(StringRef TypeId) const {
1487     auto I = TypeIdCompatibleVtableMap.find(TypeId);
1488     if (I == TypeIdCompatibleVtableMap.end())
1489       return None;
1490     return I->second;
1491   }
1492 
1493   /// Collect for the given module the list of functions it defines
1494   /// (GUID -> Summary).
1495   void collectDefinedFunctionsForModule(StringRef ModulePath,
1496                                         GVSummaryMapTy &GVSummaryMap) const;
1497 
1498   /// Collect for each module the list of Summaries it defines (GUID ->
1499   /// Summary).
1500   template <class Map>
1501   void
1502   collectDefinedGVSummariesPerModule(Map &ModuleToDefinedGVSummaries) const {
1503     for (auto &GlobalList : *this) {
1504       auto GUID = GlobalList.first;
1505       for (auto &Summary : GlobalList.second.SummaryList) {
1506         ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
1507       }
1508     }
1509   }
1510 
1511   /// Print to an output stream.
1512   void print(raw_ostream &OS, bool IsForDebug = false) const;
1513 
1514   /// Dump to stderr (for debugging).
1515   void dump() const;
1516 
1517   /// Export summary to dot file for GraphViz.
1518   void
1519   exportToDot(raw_ostream &OS,
1520               const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) const;
1521 
1522   /// Print out strongly connected components for debugging.
1523   void dumpSCCs(raw_ostream &OS);
1524 
1525   /// Do the access attribute and DSOLocal propagation in combined index.
1526   void propagateAttributes(const DenseSet<GlobalValue::GUID> &PreservedSymbols);
1527 
1528   /// Checks if we can import global variable from another module.
1529   bool canImportGlobalVar(GlobalValueSummary *S, bool AnalyzeRefs) const;
1530 };
1531 
1532 /// GraphTraits definition to build SCC for the index
1533 template <> struct GraphTraits<ValueInfo> {
1534   typedef ValueInfo NodeRef;
1535   using EdgeRef = FunctionSummary::EdgeTy &;
1536 
1537   static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) {
1538     return P.first;
1539   }
1540   using ChildIteratorType =
1541       mapped_iterator<std::vector<FunctionSummary::EdgeTy>::iterator,
1542                       decltype(&valueInfoFromEdge)>;
1543 
1544   using ChildEdgeIteratorType = std::vector<FunctionSummary::EdgeTy>::iterator;
1545 
1546   static NodeRef getEntryNode(ValueInfo V) { return V; }
1547 
1548   static ChildIteratorType child_begin(NodeRef N) {
1549     if (!N.getSummaryList().size()) // handle external function
1550       return ChildIteratorType(
1551           FunctionSummary::ExternalNode.CallGraphEdgeList.begin(),
1552           &valueInfoFromEdge);
1553     FunctionSummary *F =
1554         cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1555     return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge);
1556   }
1557 
1558   static ChildIteratorType child_end(NodeRef N) {
1559     if (!N.getSummaryList().size()) // handle external function
1560       return ChildIteratorType(
1561           FunctionSummary::ExternalNode.CallGraphEdgeList.end(),
1562           &valueInfoFromEdge);
1563     FunctionSummary *F =
1564         cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1565     return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge);
1566   }
1567 
1568   static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
1569     if (!N.getSummaryList().size()) // handle external function
1570       return FunctionSummary::ExternalNode.CallGraphEdgeList.begin();
1571 
1572     FunctionSummary *F =
1573         cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1574     return F->CallGraphEdgeList.begin();
1575   }
1576 
1577   static ChildEdgeIteratorType child_edge_end(NodeRef N) {
1578     if (!N.getSummaryList().size()) // handle external function
1579       return FunctionSummary::ExternalNode.CallGraphEdgeList.end();
1580 
1581     FunctionSummary *F =
1582         cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1583     return F->CallGraphEdgeList.end();
1584   }
1585 
1586   static NodeRef edge_dest(EdgeRef E) { return E.first; }
1587 };
1588 
1589 template <>
1590 struct GraphTraits<ModuleSummaryIndex *> : public GraphTraits<ValueInfo> {
1591   static NodeRef getEntryNode(ModuleSummaryIndex *I) {
1592     std::unique_ptr<GlobalValueSummary> Root =
1593         std::make_unique<FunctionSummary>(I->calculateCallGraphRoot());
1594     GlobalValueSummaryInfo G(I->haveGVs());
1595     G.SummaryList.push_back(std::move(Root));
1596     static auto P =
1597         GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G));
1598     return ValueInfo(I->haveGVs(), &P);
1599   }
1600 };
1601 } // end namespace llvm
1602 
1603 #endif // LLVM_IR_MODULESUMMARYINDEX_H
1604