1 //===- llvm/ModuleSummaryIndex.h - Module Summary Index ---------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
10 /// ModuleSummaryIndex.h This file contains the declarations the classes that
11 /// hold the module index and summary for function importing.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_IR_MODULESUMMARYINDEX_H
16 #define LLVM_IR_MODULESUMMARYINDEX_H
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallString.h"
22 #include "llvm/ADT/StringExtras.h"
23 #include "llvm/ADT/StringMap.h"
24 #include "llvm/ADT/StringRef.h"
25 #include "llvm/ADT/TinyPtrVector.h"
26 #include "llvm/IR/GlobalValue.h"
27 #include "llvm/IR/Module.h"
28 #include "llvm/Support/Allocator.h"
29 #include "llvm/Support/MathExtras.h"
30 #include "llvm/Support/ScaledNumber.h"
31 #include "llvm/Support/StringSaver.h"
48 template <typename T> struct MappingTraits;
50 } // end namespace yaml
52 /// Class to accumulate and hold information about a callee.
54 enum class HotnessType : uint8_t {
62 // The size of the bit-field might need to be adjusted if more values are
63 // added to HotnessType enum.
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;
73 : Hotness(static_cast<uint32_t>(HotnessType::Unknown)), RelBlockFreq(0) {}
74 explicit CalleeInfo(HotnessType Hotness, uint64_t RelBF)
75 : Hotness(static_cast<uint32_t>(Hotness)), RelBlockFreq(RelBF) {}
77 void updateHotness(const HotnessType OtherHotness) {
78 Hotness = std::max(Hotness, static_cast<uint32_t>(OtherHotness));
81 HotnessType getHotness() const { return HotnessType(Hotness); }
83 /// Update \p RelBlockFreq from \p BlockFreq and \p EntryFreq
85 /// BlockFreq is divided by EntryFreq and added to RelBlockFreq. To represent
86 /// fractional values, the result is represented as a fixed point number with
87 /// scale of -ScaleShift.
88 void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq) {
91 using Scaled64 = ScaledNumber<uint64_t>;
92 Scaled64 Temp(BlockFreq, ScaleShift);
93 Temp /= Scaled64::get(EntryFreq);
96 SaturatingAdd<uint64_t>(Temp.toInt<uint64_t>(), RelBlockFreq);
97 Sum = std::min(Sum, uint64_t(MaxRelBlockFreq));
98 RelBlockFreq = static_cast<uint32_t>(Sum);
102 inline const char *getHotnessName(CalleeInfo::HotnessType HT) {
104 case CalleeInfo::HotnessType::Unknown:
106 case CalleeInfo::HotnessType::Cold:
108 case CalleeInfo::HotnessType::None:
110 case CalleeInfo::HotnessType::Hot:
112 case CalleeInfo::HotnessType::Critical:
115 llvm_unreachable("invalid hotness");
118 class GlobalValueSummary;
120 using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>;
122 struct LLVM_ALIGNAS(8) GlobalValueSummaryInfo {
124 NameOrGV(bool HaveGVs) {
131 /// The GlobalValue corresponding to this summary. This is only used in
132 /// per-module summaries and when the IR is available. E.g. when module
133 /// analysis is being run, or when parsing both the IR and the summary
135 const GlobalValue *GV;
137 /// Summary string representation. This StringRef points to BC module
138 /// string table and is valid until module data is stored in memory.
139 /// This is guaranteed to happen until runThinLTOBackend function is
140 /// called, so it is safe to use this field during thin link. This field
141 /// is only valid if summary index was loaded from BC file.
145 GlobalValueSummaryInfo(bool HaveGVs) : U(HaveGVs) {}
147 /// List of global value summary structures for a particular value held
148 /// in the GlobalValueMap. Requires a vector in the case of multiple
149 /// COMDAT values of the same name.
150 GlobalValueSummaryList SummaryList;
153 /// Map from global value GUID to corresponding summary structures. Use a
154 /// std::map rather than a DenseMap so that pointers to the map's value_type
155 /// (which are used by ValueInfo) are not invalidated by insertion. Also it will
156 /// likely incur less overhead, as the value type is not very small and the size
157 /// of the map is unknown, resulting in inefficiencies due to repeated
158 /// insertions and resizing.
159 using GlobalValueSummaryMapTy =
160 std::map<GlobalValue::GUID, GlobalValueSummaryInfo>;
162 /// Struct that holds a reference to a particular GUID in a global value
165 enum Flags { HaveGV = 1, ReadOnly = 2, WriteOnly = 4 };
166 PointerIntPair<const GlobalValueSummaryMapTy::value_type *, 3, int>
169 ValueInfo() = default;
170 ValueInfo(bool HaveGVs, const GlobalValueSummaryMapTy::value_type *R) {
171 RefAndFlags.setPointer(R);
172 RefAndFlags.setInt(HaveGVs);
175 operator bool() const { return getRef(); }
177 GlobalValue::GUID getGUID() const { return getRef()->first; }
178 const GlobalValue *getValue() const {
180 return getRef()->second.U.GV;
183 ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const {
184 return getRef()->second.SummaryList;
187 StringRef name() const {
188 return haveGVs() ? getRef()->second.U.GV->getName()
189 : getRef()->second.U.Name;
192 bool haveGVs() const { return RefAndFlags.getInt() & HaveGV; }
193 bool isReadOnly() const {
194 assert(isValidAccessSpecifier());
195 return RefAndFlags.getInt() & ReadOnly;
197 bool isWriteOnly() const {
198 assert(isValidAccessSpecifier());
199 return RefAndFlags.getInt() & WriteOnly;
201 unsigned getAccessSpecifier() const {
202 assert(isValidAccessSpecifier());
203 return RefAndFlags.getInt() & (ReadOnly | WriteOnly);
205 bool isValidAccessSpecifier() const {
206 unsigned BadAccessMask = ReadOnly | WriteOnly;
207 return (RefAndFlags.getInt() & BadAccessMask) != BadAccessMask;
210 // We expect ro/wo attribute to set only once during
211 // ValueInfo lifetime.
212 assert(getAccessSpecifier() == 0);
213 RefAndFlags.setInt(RefAndFlags.getInt() | ReadOnly);
215 void setWriteOnly() {
216 assert(getAccessSpecifier() == 0);
217 RefAndFlags.setInt(RefAndFlags.getInt() | WriteOnly);
220 const GlobalValueSummaryMapTy::value_type *getRef() const {
221 return RefAndFlags.getPointer();
224 bool isDSOLocal() const;
226 /// Checks if all copies are eligible for auto-hiding (have flag set).
227 bool canAutoHide() const;
230 inline raw_ostream &operator<<(raw_ostream &OS, const ValueInfo &VI) {
232 if (!VI.name().empty())
233 OS << " (" << VI.name() << ")";
237 inline bool operator==(const ValueInfo &A, const ValueInfo &B) {
238 assert(A.getRef() && B.getRef() &&
239 "Need ValueInfo with non-null Ref for comparison");
240 return A.getRef() == B.getRef();
243 inline bool operator!=(const ValueInfo &A, const ValueInfo &B) {
244 assert(A.getRef() && B.getRef() &&
245 "Need ValueInfo with non-null Ref for comparison");
246 return A.getRef() != B.getRef();
249 inline bool operator<(const ValueInfo &A, const ValueInfo &B) {
250 assert(A.getRef() && B.getRef() &&
251 "Need ValueInfo with non-null Ref to compare GUIDs");
252 return A.getGUID() < B.getGUID();
255 template <> struct DenseMapInfo<ValueInfo> {
256 static inline ValueInfo getEmptyKey() {
257 return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8);
260 static inline ValueInfo getTombstoneKey() {
261 return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-16);
264 static inline bool isSpecialKey(ValueInfo V) {
265 return V == getTombstoneKey() || V == getEmptyKey();
268 static bool isEqual(ValueInfo L, ValueInfo R) {
269 // We are not supposed to mix ValueInfo(s) with different HaveGVs flag
270 // in a same container.
271 assert(isSpecialKey(L) || isSpecialKey(R) || (L.haveGVs() == R.haveGVs()));
272 return L.getRef() == R.getRef();
274 static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); }
277 /// Function and variable summary information to aid decisions and
278 /// implementation of importing.
279 class GlobalValueSummary {
281 /// Sububclass discriminator (for dyn_cast<> et al.)
282 enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
284 /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
286 /// The linkage type of the associated global value.
288 /// One use is to flag values that have local linkage types and need to
289 /// have module identifier appended before placing into the combined
290 /// index, to disambiguate from other values with the same name.
291 /// In the future this will be used to update and optimize linkage
292 /// types based on global summary-based analysis.
293 unsigned Linkage : 4;
295 /// Indicate if the global value cannot be imported (e.g. it cannot
296 /// be renamed or references something that can't be renamed).
297 unsigned NotEligibleToImport : 1;
299 /// In per-module summary, indicate that the global value must be considered
300 /// a live root for index-based liveness analysis. Used for special LLVM
301 /// values such as llvm.global_ctors that the linker does not know about.
303 /// In combined summary, indicate that the global value is live.
306 /// Indicates that the linker resolved the symbol to a definition from
307 /// within the same linkage unit.
308 unsigned DSOLocal : 1;
310 /// In the per-module summary, indicates that the global value is
311 /// linkonce_odr and global unnamed addr (so eligible for auto-hiding
312 /// via hidden visibility). In the combined summary, indicates that the
313 /// prevailing linkonce_odr copy can be auto-hidden via hidden visibility
314 /// when it is upgraded to weak_odr in the backend. This is legal when
315 /// all copies are eligible for auto-hiding (i.e. all copies were
316 /// linkonce_odr global unnamed addr. If any copy is not (e.g. it was
317 /// originally weak_odr, we cannot auto-hide the prevailing copy as it
318 /// means the symbol was externally visible.
319 unsigned CanAutoHide : 1;
321 /// Convenience Constructors
322 explicit GVFlags(GlobalValue::LinkageTypes Linkage,
323 bool NotEligibleToImport, bool Live, bool IsLocal,
325 : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport),
326 Live(Live), DSOLocal(IsLocal), CanAutoHide(CanAutoHide) {}
330 /// Kind of summary for use in dyn_cast<> et al.
335 /// This is the hash of the name of the symbol in the original file. It is
336 /// identical to the GUID for global symbols, but differs for local since the
337 /// GUID includes the module level id in the hash.
338 GlobalValue::GUID OriginalName = 0;
340 /// Path of module IR containing value's definition, used to locate
341 /// module during importing.
343 /// This is only used during parsing of the combined index, or when
344 /// parsing the per-module index for creation of the combined summary index,
345 /// not during writing of the per-module index which doesn't contain a
346 /// module path string table.
347 StringRef ModulePath;
349 /// List of values referenced by this global value's definition
350 /// (either by the initializer of a global variable, or referenced
351 /// from within a function). This does not include functions called, which
352 /// are listed in the derived FunctionSummary object.
353 std::vector<ValueInfo> RefEdgeList;
356 GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
357 : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {
358 assert((K != AliasKind || Refs.empty()) &&
359 "Expect no references for AliasSummary");
363 virtual ~GlobalValueSummary() = default;
365 /// Returns the hash of the original name, it is identical to the GUID for
366 /// externally visible symbols, but not for local ones.
367 GlobalValue::GUID getOriginalName() const { return OriginalName; }
369 /// Initialize the original name hash in this summary.
370 void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
372 /// Which kind of summary subclass this is.
373 SummaryKind getSummaryKind() const { return Kind; }
375 /// Set the path to the module containing this function, for use in
376 /// the combined index.
377 void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
379 /// Get the path to the module containing this function.
380 StringRef modulePath() const { return ModulePath; }
382 /// Get the flags for this GlobalValue (see \p struct GVFlags).
383 GVFlags flags() const { return Flags; }
385 /// Return linkage type recorded for this global value.
386 GlobalValue::LinkageTypes linkage() const {
387 return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
390 /// Sets the linkage to the value determined by global summary-based
391 /// optimization. Will be applied in the ThinLTO backends.
392 void setLinkage(GlobalValue::LinkageTypes Linkage) {
393 Flags.Linkage = Linkage;
396 /// Return true if this global value can't be imported.
397 bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
399 bool isLive() const { return Flags.Live; }
401 void setLive(bool Live) { Flags.Live = Live; }
403 void setDSOLocal(bool Local) { Flags.DSOLocal = Local; }
405 bool isDSOLocal() const { return Flags.DSOLocal; }
407 void setCanAutoHide(bool CanAutoHide) { Flags.CanAutoHide = CanAutoHide; }
409 bool canAutoHide() const { return Flags.CanAutoHide; }
411 /// Flag that this global value cannot be imported.
412 void setNotEligibleToImport() { Flags.NotEligibleToImport = true; }
414 /// Return the list of values referenced by this global value definition.
415 ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
417 /// If this is an alias summary, returns the summary of the aliased object (a
418 /// global variable or function), otherwise returns itself.
419 GlobalValueSummary *getBaseObject();
420 const GlobalValueSummary *getBaseObject() const;
422 friend class ModuleSummaryIndex;
425 /// Alias summary information.
426 class AliasSummary : public GlobalValueSummary {
427 ValueInfo AliaseeValueInfo;
429 /// This is the Aliasee in the same module as alias (could get from VI, trades
430 /// memory for time). Note that this pointer may be null (and the value info
431 /// empty) when we have a distributed index where the alias is being imported
432 /// (as a copy of the aliasee), but the aliasee is not.
433 GlobalValueSummary *AliaseeSummary;
436 AliasSummary(GVFlags Flags)
437 : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}),
438 AliaseeSummary(nullptr) {}
440 /// Check if this is an alias summary.
441 static bool classof(const GlobalValueSummary *GVS) {
442 return GVS->getSummaryKind() == AliasKind;
445 void setAliasee(ValueInfo &AliaseeVI, GlobalValueSummary *Aliasee) {
446 AliaseeValueInfo = AliaseeVI;
447 AliaseeSummary = Aliasee;
450 bool hasAliasee() const {
451 assert(!!AliaseeSummary == (AliaseeValueInfo &&
452 !AliaseeValueInfo.getSummaryList().empty()) &&
453 "Expect to have both aliasee summary and summary list or neither");
454 return !!AliaseeSummary;
457 const GlobalValueSummary &getAliasee() const {
458 assert(AliaseeSummary && "Unexpected missing aliasee summary");
459 return *AliaseeSummary;
462 GlobalValueSummary &getAliasee() {
463 return const_cast<GlobalValueSummary &>(
464 static_cast<const AliasSummary *>(this)->getAliasee());
466 ValueInfo getAliaseeVI() const {
467 assert(AliaseeValueInfo && "Unexpected missing aliasee");
468 return AliaseeValueInfo;
470 GlobalValue::GUID getAliaseeGUID() const {
471 assert(AliaseeValueInfo && "Unexpected missing aliasee");
472 return AliaseeValueInfo.getGUID();
476 const inline GlobalValueSummary *GlobalValueSummary::getBaseObject() const {
477 if (auto *AS = dyn_cast<AliasSummary>(this))
478 return &AS->getAliasee();
482 inline GlobalValueSummary *GlobalValueSummary::getBaseObject() {
483 if (auto *AS = dyn_cast<AliasSummary>(this))
484 return &AS->getAliasee();
488 /// Function summary information to aid decisions and implementation of
490 class FunctionSummary : public GlobalValueSummary {
492 /// <CalleeValueInfo, CalleeInfo> call edge pair.
493 using EdgeTy = std::pair<ValueInfo, CalleeInfo>;
495 /// Types for -force-summary-edges-cold debugging option.
496 enum ForceSummaryHotnessType : unsigned {
502 /// An "identifier" for a virtual function. This contains the type identifier
503 /// represented as a GUID and the offset from the address point to the virtual
504 /// function pointer, where "address point" is as defined in the Itanium ABI:
505 /// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
507 GlobalValue::GUID GUID;
511 /// A specification for a virtual function call with all constant integer
512 /// arguments. This is used to perform virtual constant propagation on the
516 std::vector<uint64_t> Args;
519 /// All type identifier related information. Because these fields are
520 /// relatively uncommon we only allocate space for them if necessary.
522 /// List of type identifiers used by this function in llvm.type.test
523 /// intrinsics referenced by something other than an llvm.assume intrinsic,
524 /// represented as GUIDs.
525 std::vector<GlobalValue::GUID> TypeTests;
527 /// List of virtual calls made by this function using (respectively)
528 /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do
529 /// not have all constant integer arguments.
530 std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
532 /// List of virtual calls made by this function using (respectively)
533 /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with
534 /// all constant integer arguments.
535 std::vector<ConstVCall> TypeTestAssumeConstVCalls,
536 TypeCheckedLoadConstVCalls;
539 /// Flags specific to function summaries.
541 // Function attribute flags. Used to track if a function accesses memory,
542 // recurses or aliases.
543 unsigned ReadNone : 1;
544 unsigned ReadOnly : 1;
545 unsigned NoRecurse : 1;
546 unsigned ReturnDoesNotAlias : 1;
548 // Indicate if the global value cannot be inlined.
549 unsigned NoInline : 1;
552 /// Create an empty FunctionSummary (with specified call edges).
553 /// Used to represent external nodes and the dummy root node.
554 static FunctionSummary
555 makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) {
556 return FunctionSummary(
557 FunctionSummary::GVFlags(
558 GlobalValue::LinkageTypes::AvailableExternallyLinkage,
559 /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false,
560 /*CanAutoHide=*/false),
561 /*InsCount=*/0, FunctionSummary::FFlags{}, /*EntryCount=*/0,
562 std::vector<ValueInfo>(), std::move(Edges),
563 std::vector<GlobalValue::GUID>(),
564 std::vector<FunctionSummary::VFuncId>(),
565 std::vector<FunctionSummary::VFuncId>(),
566 std::vector<FunctionSummary::ConstVCall>(),
567 std::vector<FunctionSummary::ConstVCall>());
570 /// A dummy node to reference external functions that aren't in the index
571 static FunctionSummary ExternalNode;
574 /// Number of instructions (ignoring debug instructions, e.g.) computed
575 /// during the initial compile step when the summary index is first built.
578 /// Function summary specific flags.
581 /// The synthesized entry count of the function.
582 /// This is only populated during ThinLink phase and remains unused while
583 /// generating per-module summaries.
584 uint64_t EntryCount = 0;
586 /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
587 std::vector<EdgeTy> CallGraphEdgeList;
589 std::unique_ptr<TypeIdInfo> TIdInfo;
592 FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
593 uint64_t EntryCount, std::vector<ValueInfo> Refs,
594 std::vector<EdgeTy> CGEdges,
595 std::vector<GlobalValue::GUID> TypeTests,
596 std::vector<VFuncId> TypeTestAssumeVCalls,
597 std::vector<VFuncId> TypeCheckedLoadVCalls,
598 std::vector<ConstVCall> TypeTestAssumeConstVCalls,
599 std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
600 : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
601 InstCount(NumInsts), FunFlags(FunFlags), EntryCount(EntryCount),
602 CallGraphEdgeList(std::move(CGEdges)) {
603 if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
604 !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
605 !TypeCheckedLoadConstVCalls.empty())
606 TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
607 std::move(TypeTests), std::move(TypeTestAssumeVCalls),
608 std::move(TypeCheckedLoadVCalls),
609 std::move(TypeTestAssumeConstVCalls),
610 std::move(TypeCheckedLoadConstVCalls)});
612 // Gets the number of readonly and writeonly refs in RefEdgeList
613 std::pair<unsigned, unsigned> specialRefCounts() const;
615 /// Check if this is a function summary.
616 static bool classof(const GlobalValueSummary *GVS) {
617 return GVS->getSummaryKind() == FunctionKind;
620 /// Get function summary flags.
621 FFlags fflags() const { return FunFlags; }
623 /// Get the instruction count recorded for this function.
624 unsigned instCount() const { return InstCount; }
626 /// Get the synthetic entry count for this function.
627 uint64_t entryCount() const { return EntryCount; }
629 /// Set the synthetic entry count for this function.
630 void setEntryCount(uint64_t EC) { EntryCount = EC; }
632 /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
633 ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
635 /// Returns the list of type identifiers used by this function in
636 /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
637 /// represented as GUIDs.
638 ArrayRef<GlobalValue::GUID> type_tests() const {
640 return TIdInfo->TypeTests;
644 /// Returns the list of virtual calls made by this function using
645 /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
646 /// integer arguments.
647 ArrayRef<VFuncId> type_test_assume_vcalls() const {
649 return TIdInfo->TypeTestAssumeVCalls;
653 /// Returns the list of virtual calls made by this function using
654 /// llvm.type.checked.load intrinsics that do not have all constant integer
656 ArrayRef<VFuncId> type_checked_load_vcalls() const {
658 return TIdInfo->TypeCheckedLoadVCalls;
662 /// Returns the list of virtual calls made by this function using
663 /// llvm.assume(llvm.type.test) intrinsics with all constant integer
665 ArrayRef<ConstVCall> type_test_assume_const_vcalls() const {
667 return TIdInfo->TypeTestAssumeConstVCalls;
671 /// Returns the list of virtual calls made by this function using
672 /// llvm.type.checked.load intrinsics with all constant integer arguments.
673 ArrayRef<ConstVCall> type_checked_load_const_vcalls() const {
675 return TIdInfo->TypeCheckedLoadConstVCalls;
679 /// Add a type test to the summary. This is used by WholeProgramDevirt if we
680 /// were unable to devirtualize a checked call.
681 void addTypeTest(GlobalValue::GUID Guid) {
683 TIdInfo = llvm::make_unique<TypeIdInfo>();
684 TIdInfo->TypeTests.push_back(Guid);
687 const TypeIdInfo *getTypeIdInfo() const { return TIdInfo.get(); };
689 friend struct GraphTraits<ValueInfo>;
692 template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
693 static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
695 static FunctionSummary::VFuncId getTombstoneKey() {
696 return {0, uint64_t(-2)};
699 static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R) {
700 return L.GUID == R.GUID && L.Offset == R.Offset;
703 static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
706 template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
707 static FunctionSummary::ConstVCall getEmptyKey() {
708 return {{0, uint64_t(-1)}, {}};
711 static FunctionSummary::ConstVCall getTombstoneKey() {
712 return {{0, uint64_t(-2)}, {}};
715 static bool isEqual(FunctionSummary::ConstVCall L,
716 FunctionSummary::ConstVCall R) {
717 return DenseMapInfo<FunctionSummary::VFuncId>::isEqual(L.VFunc, R.VFunc) &&
721 static unsigned getHashValue(FunctionSummary::ConstVCall I) {
726 /// The ValueInfo and offset for a function within a vtable definition
727 /// initializer array.
728 struct VirtFuncOffset {
729 VirtFuncOffset(ValueInfo VI, uint64_t Offset)
730 : FuncVI(VI), VTableOffset(Offset) {}
733 uint64_t VTableOffset;
735 /// List of functions referenced by a particular vtable definition.
736 using VTableFuncList = std::vector<VirtFuncOffset>;
738 /// Global variable summary information to aid decisions and
739 /// implementation of importing.
741 /// Global variable summary has two extra flag, telling if it is
742 /// readonly or writeonly. Both readonly and writeonly variables
743 /// can be optimized in the backed: readonly variables can be
744 /// const-folded, while writeonly vars can be completely eliminated
745 /// together with corresponding stores. We let both things happen
746 /// by means of internalizing such variables after ThinLTO import.
747 class GlobalVarSummary : public GlobalValueSummary {
749 /// For vtable definitions this holds the list of functions and
750 /// their corresponding offsets within the initializer array.
751 std::unique_ptr<VTableFuncList> VTableFuncs;
755 GVarFlags(bool ReadOnly, bool WriteOnly)
756 : MaybeReadOnly(ReadOnly), MaybeWriteOnly(WriteOnly) {}
758 // In permodule summaries both MaybeReadOnly and MaybeWriteOnly
759 // bits are set, because attribute propagation occurs later on
761 unsigned MaybeReadOnly : 1;
762 unsigned MaybeWriteOnly : 1;
765 GlobalVarSummary(GVFlags Flags, GVarFlags VarFlags,
766 std::vector<ValueInfo> Refs)
767 : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)),
768 VarFlags(VarFlags) {}
770 /// Check if this is a global variable summary.
771 static bool classof(const GlobalValueSummary *GVS) {
772 return GVS->getSummaryKind() == GlobalVarKind;
775 GVarFlags varflags() const { return VarFlags; }
776 void setReadOnly(bool RO) { VarFlags.MaybeReadOnly = RO; }
777 void setWriteOnly(bool WO) { VarFlags.MaybeWriteOnly = WO; }
778 bool maybeReadOnly() const { return VarFlags.MaybeReadOnly; }
779 bool maybeWriteOnly() const { return VarFlags.MaybeWriteOnly; }
781 void setVTableFuncs(VTableFuncList Funcs) {
782 assert(!VTableFuncs);
783 VTableFuncs = llvm::make_unique<VTableFuncList>(std::move(Funcs));
786 ArrayRef<VirtFuncOffset> vTableFuncs() const {
793 struct TypeTestResolution {
794 /// Specifies which kind of type check we should emit for this byte array.
795 /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
796 /// details on each kind of check; the enumerators are described with
797 /// reference to that document.
799 Unsat, ///< Unsatisfiable type (i.e. no global has this type metadata)
800 ByteArray, ///< Test a byte array (first example)
801 Inline, ///< Inlined bit vector ("Short Inline Bit Vectors")
802 Single, ///< Single element (last example in "Short Inline Bit Vectors")
803 AllOnes, ///< All-ones bit vector ("Eliminating Bit Vector Checks for
804 /// All-Ones Bit Vectors")
807 /// Range of size-1 expressed as a bit width. For example, if the size is in
808 /// range [1,256], this number will be 8. This helps generate the most compact
809 /// instruction sequences.
810 unsigned SizeM1BitWidth = 0;
812 // The following fields are only used if the target does not support the use
813 // of absolute symbols to store constants. Their meanings are the same as the
814 // corresponding fields in LowerTypeTestsModule::TypeIdLowering in
815 // LowerTypeTests.cpp.
817 uint64_t AlignLog2 = 0;
820 uint64_t InlineBits = 0;
823 struct WholeProgramDevirtResolution {
825 Indir, ///< Just do a regular virtual call
826 SingleImpl, ///< Single implementation devirtualization
827 BranchFunnel, ///< When retpoline mitigation is enabled, use a branch funnel
828 ///< that is defined in the merged module. Otherwise same as
832 std::string SingleImplName;
836 Indir, ///< Just do a regular virtual call
837 UniformRetVal, ///< Uniform return value optimization
838 UniqueRetVal, ///< Unique return value optimization
839 VirtualConstProp, ///< Virtual constant propagation
842 /// Additional information for the resolution:
843 /// - UniformRetVal: the uniform return value.
844 /// - UniqueRetVal: the return value associated with the unique vtable (0 or
848 // The following fields are only used if the target does not support the use
849 // of absolute symbols to store constants.
855 /// Resolutions for calls with all constant integer arguments (excluding the
856 /// first argument, "this"), where the key is the argument vector.
857 std::map<std::vector<uint64_t>, ByArg> ResByArg;
860 struct TypeIdSummary {
861 TypeTestResolution TTRes;
863 /// Mapping from byte offset to whole-program devirt resolution for that
864 /// (typeid, byte offset) pair.
865 std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
869 using ModuleHash = std::array<uint32_t, 5>;
871 /// Type used for iterating through the global value summary map.
872 using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
873 using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
875 /// String table to hold/own module path strings, which additionally holds the
876 /// module ID assigned to each module during the plugin step, as well as a hash
877 /// of the module. The StringMap makes a copy of and owns inserted strings.
878 using ModulePathStringTableTy = StringMap<std::pair<uint64_t, ModuleHash>>;
880 /// Map of global value GUID to its summary, used to identify values defined in
881 /// a particular module, and provide efficient access to their summary.
882 using GVSummaryMapTy = DenseMap<GlobalValue::GUID, GlobalValueSummary *>;
884 /// Map of a type GUID to type id string and summary (multimap used
885 /// in case of GUID conflicts).
886 using TypeIdSummaryMapTy =
887 std::multimap<GlobalValue::GUID, std::pair<std::string, TypeIdSummary>>;
889 /// The following data structures summarize type metadata information.
890 /// For type metadata overview see https://llvm.org/docs/TypeMetadata.html.
891 /// Each type metadata includes both the type identifier and the offset of
892 /// the address point of the type (the address held by objects of that type
893 /// which may not be the beginning of the virtual table). Vtable definitions
894 /// are decorated with type metadata for the types they are compatible with.
896 /// Holds information about vtable definitions decorated with type metadata:
897 /// the vtable definition value and its address point offset in a type
898 /// identifier metadata it is decorated (compatible) with.
899 struct TypeIdOffsetVtableInfo {
900 TypeIdOffsetVtableInfo(uint64_t Offset, ValueInfo VI)
901 : AddressPointOffset(Offset), VTableVI(VI) {}
903 uint64_t AddressPointOffset;
906 /// List of vtable definitions decorated by a particular type identifier,
907 /// and their corresponding offsets in that type identifier's metadata.
908 /// Note that each type identifier may be compatible with multiple vtables, due
909 /// to inheritance, which is why this is a vector.
910 using TypeIdCompatibleVtableInfo = std::vector<TypeIdOffsetVtableInfo>;
912 /// Class to hold module path string table and global value map,
913 /// and encapsulate methods for operating on them.
914 class ModuleSummaryIndex {
916 /// Map from value name to list of summary instances for values of that
917 /// name (may be duplicates in the COMDAT case, e.g.).
918 GlobalValueSummaryMapTy GlobalValueMap;
920 /// Holds strings for combined index, mapping to the corresponding module ID.
921 ModulePathStringTableTy ModulePathStringTable;
923 /// Mapping from type identifier GUIDs to type identifier and its summary
924 /// information. Produced by thin link.
925 TypeIdSummaryMapTy TypeIdMap;
927 /// Mapping from type identifier to information about vtables decorated
928 /// with that type identifier's metadata. Produced by per module summary
929 /// analysis and consumed by thin link. For more information, see description
930 /// above where TypeIdCompatibleVtableInfo is defined.
931 std::map<std::string, TypeIdCompatibleVtableInfo> TypeIdCompatibleVtableMap;
933 /// Mapping from original ID to GUID. If original ID can map to multiple
934 /// GUIDs, it will be mapped to 0.
935 std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
937 /// Indicates that summary-based GlobalValue GC has run, and values with
938 /// GVFlags::Live==false are really dead. Otherwise, all values must be
940 bool WithGlobalValueDeadStripping = false;
942 /// Indicates that summary-based synthetic entry count propagation has run
943 bool HasSyntheticEntryCounts = false;
945 /// Indicates that distributed backend should skip compilation of the
946 /// module. Flag is suppose to be set by distributed ThinLTO indexing
947 /// when it detected that the module is not needed during the final
948 /// linking. As result distributed backend should just output a minimal
949 /// valid object file.
950 bool SkipModuleByDistributedBackend = false;
952 /// If true then we're performing analysis of IR module, or parsing along with
953 /// the IR from assembly. The value of 'false' means we're reading summary
954 /// from BC or YAML source. Affects the type of value stored in NameOrGV
958 // True if the index was created for a module compiled with -fsplit-lto-unit.
959 bool EnableSplitLTOUnit;
961 // True if some of the modules were compiled with -fsplit-lto-unit and
962 // some were not. Set when the combined index is created during the thin link.
963 bool PartiallySplitLTOUnits = false;
965 std::set<std::string> CfiFunctionDefs;
966 std::set<std::string> CfiFunctionDecls;
968 // Used in cases where we want to record the name of a global, but
969 // don't have the string owned elsewhere (e.g. the Strtab on a module).
971 BumpPtrAllocator Alloc;
974 friend yaml::MappingTraits<ModuleSummaryIndex>;
976 GlobalValueSummaryMapTy::value_type *
977 getOrInsertValuePtr(GlobalValue::GUID GUID) {
978 return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs))
983 // See HaveGVs variable comment.
984 ModuleSummaryIndex(bool HaveGVs, bool EnableSplitLTOUnit = false)
985 : HaveGVs(HaveGVs), EnableSplitLTOUnit(EnableSplitLTOUnit), Saver(Alloc) {
988 bool haveGVs() const { return HaveGVs; }
990 gvsummary_iterator begin() { return GlobalValueMap.begin(); }
991 const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
992 gvsummary_iterator end() { return GlobalValueMap.end(); }
993 const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
994 size_t size() const { return GlobalValueMap.size(); }
996 /// Convenience function for doing a DFS on a ValueInfo. Marks the function in
997 /// the FunctionHasParent map.
998 static void discoverNodes(ValueInfo V,
999 std::map<ValueInfo, bool> &FunctionHasParent) {
1000 if (!V.getSummaryList().size())
1001 return; // skip external functions that don't have summaries
1003 // Mark discovered if we haven't yet
1004 auto S = FunctionHasParent.emplace(V, false);
1006 // Stop if we've already discovered this node
1010 FunctionSummary *F =
1011 dyn_cast<FunctionSummary>(V.getSummaryList().front().get());
1012 assert(F != nullptr && "Expected FunctionSummary node");
1014 for (auto &C : F->calls()) {
1015 // Insert node if necessary
1016 auto S = FunctionHasParent.emplace(C.first, true);
1018 // Skip nodes that we're sure have parents
1019 if (!S.second && S.first->second)
1023 discoverNodes(C.first, FunctionHasParent);
1025 S.first->second = true;
1029 // Calculate the callgraph root
1030 FunctionSummary calculateCallGraphRoot() {
1031 // Functions that have a parent will be marked in FunctionHasParent pair.
1032 // Once we've marked all functions, the functions in the map that are false
1033 // have no parent (so they're the roots)
1034 std::map<ValueInfo, bool> FunctionHasParent;
1036 for (auto &S : *this) {
1037 // Skip external functions
1038 if (!S.second.SummaryList.size() ||
1039 !isa<FunctionSummary>(S.second.SummaryList.front().get()))
1041 discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent);
1044 std::vector<FunctionSummary::EdgeTy> Edges;
1045 // create edges to all roots in the Index
1046 for (auto &P : FunctionHasParent) {
1048 continue; // skip over non-root nodes
1049 Edges.push_back(std::make_pair(P.first, CalleeInfo{}));
1051 if (Edges.empty()) {
1052 // Failed to find root - return an empty node
1053 return FunctionSummary::makeDummyFunctionSummary({});
1055 auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
1056 return CallGraphRoot;
1059 bool withGlobalValueDeadStripping() const {
1060 return WithGlobalValueDeadStripping;
1062 void setWithGlobalValueDeadStripping() {
1063 WithGlobalValueDeadStripping = true;
1066 bool hasSyntheticEntryCounts() const { return HasSyntheticEntryCounts; }
1067 void setHasSyntheticEntryCounts() { HasSyntheticEntryCounts = true; }
1069 bool skipModuleByDistributedBackend() const {
1070 return SkipModuleByDistributedBackend;
1072 void setSkipModuleByDistributedBackend() {
1073 SkipModuleByDistributedBackend = true;
1076 bool enableSplitLTOUnit() const { return EnableSplitLTOUnit; }
1077 void setEnableSplitLTOUnit() { EnableSplitLTOUnit = true; }
1079 bool partiallySplitLTOUnits() const { return PartiallySplitLTOUnits; }
1080 void setPartiallySplitLTOUnits() { PartiallySplitLTOUnits = true; }
1082 bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
1083 return !WithGlobalValueDeadStripping || GVS->isLive();
1085 bool isGUIDLive(GlobalValue::GUID GUID) const;
1087 /// Return a ValueInfo for the index value_type (convenient when iterating
1089 ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const {
1090 return ValueInfo(HaveGVs, &R);
1093 /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
1094 ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
1095 auto I = GlobalValueMap.find(GUID);
1096 return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I);
1099 /// Return a ValueInfo for \p GUID.
1100 ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) {
1101 return ValueInfo(HaveGVs, getOrInsertValuePtr(GUID));
1104 // Save a string in the Index. Use before passing Name to
1105 // getOrInsertValueInfo when the string isn't owned elsewhere (e.g. on the
1106 // module's Strtab).
1107 StringRef saveString(StringRef String) { return Saver.save(String); }
1109 /// Return a ValueInfo for \p GUID setting value \p Name.
1110 ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name) {
1112 auto VP = getOrInsertValuePtr(GUID);
1113 VP->second.U.Name = Name;
1114 return ValueInfo(HaveGVs, VP);
1117 /// Return a ValueInfo for \p GV and mark it as belonging to GV.
1118 ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
1120 auto VP = getOrInsertValuePtr(GV->getGUID());
1121 VP->second.U.GV = GV;
1122 return ValueInfo(HaveGVs, VP);
1125 /// Return the GUID for \p OriginalId in the OidGuidMap.
1126 GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const {
1127 const auto I = OidGuidMap.find(OriginalID);
1128 return I == OidGuidMap.end() ? 0 : I->second;
1131 std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; }
1132 const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; }
1134 std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; }
1135 const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; }
1137 /// Add a global value summary for a value.
1138 void addGlobalValueSummary(const GlobalValue &GV,
1139 std::unique_ptr<GlobalValueSummary> Summary) {
1140 addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary));
1143 /// Add a global value summary for a value of the given name.
1144 void addGlobalValueSummary(StringRef ValueName,
1145 std::unique_ptr<GlobalValueSummary> Summary) {
1146 addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
1147 std::move(Summary));
1150 /// Add a global value summary for the given ValueInfo.
1151 void addGlobalValueSummary(ValueInfo VI,
1152 std::unique_ptr<GlobalValueSummary> Summary) {
1153 addOriginalName(VI.getGUID(), Summary->getOriginalName());
1154 // Here we have a notionally const VI, but the value it points to is owned
1155 // by the non-const *this.
1156 const_cast<GlobalValueSummaryMapTy::value_type *>(VI.getRef())
1157 ->second.SummaryList.push_back(std::move(Summary));
1160 /// Add an original name for the value of the given GUID.
1161 void addOriginalName(GlobalValue::GUID ValueGUID,
1162 GlobalValue::GUID OrigGUID) {
1163 if (OrigGUID == 0 || ValueGUID == OrigGUID)
1165 if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
1166 OidGuidMap[OrigGUID] = 0;
1168 OidGuidMap[OrigGUID] = ValueGUID;
1171 /// Find the summary for ValueInfo \p VI in module \p ModuleId, or nullptr if
1173 GlobalValueSummary *findSummaryInModule(ValueInfo VI, StringRef ModuleId) const {
1174 auto SummaryList = VI.getSummaryList();
1176 llvm::find_if(SummaryList,
1177 [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
1178 return Summary->modulePath() == ModuleId;
1180 if (Summary == SummaryList.end())
1182 return Summary->get();
1185 /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
1187 GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
1188 StringRef ModuleId) const {
1189 auto CalleeInfo = getValueInfo(ValueGUID);
1191 return nullptr; // This function does not have a summary
1192 return findSummaryInModule(CalleeInfo, ModuleId);
1195 /// Returns the first GlobalValueSummary for \p GV, asserting that there
1196 /// is only one if \p PerModuleIndex.
1197 GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
1198 bool PerModuleIndex = true) const {
1199 assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
1200 return getGlobalValueSummary(GV.getGUID(), PerModuleIndex);
1203 /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
1205 /// is only one if \p PerModuleIndex.
1206 GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
1207 bool PerModuleIndex = true) const;
1209 /// Table of modules, containing module hash and id.
1210 const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
1211 return ModulePathStringTable;
1214 /// Table of modules, containing hash and id.
1215 StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
1216 return ModulePathStringTable;
1219 /// Get the module ID recorded for the given module path.
1220 uint64_t getModuleId(const StringRef ModPath) const {
1221 return ModulePathStringTable.lookup(ModPath).first;
1224 /// Get the module SHA1 hash recorded for the given module path.
1225 const ModuleHash &getModuleHash(const StringRef ModPath) const {
1226 auto It = ModulePathStringTable.find(ModPath);
1227 assert(It != ModulePathStringTable.end() && "Module not registered");
1228 return It->second.second;
1231 /// Convenience method for creating a promoted global name
1232 /// for the given value name of a local, and its original module's ID.
1233 static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
1234 SmallString<256> NewName(Name);
1235 NewName += ".llvm.";
1236 NewName += utostr((uint64_t(ModHash[0]) << 32) |
1237 ModHash[1]); // Take the first 64 bits
1238 return NewName.str();
1241 /// Helper to obtain the unpromoted name for a global value (or the original
1242 /// name if not promoted).
1243 static StringRef getOriginalNameBeforePromote(StringRef Name) {
1244 std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
1248 typedef ModulePathStringTableTy::value_type ModuleInfo;
1250 /// Add a new module with the given \p Hash, mapped to the given \p
1251 /// ModID, and return a reference to the module.
1252 ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
1253 ModuleHash Hash = ModuleHash{{0}}) {
1254 return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first;
1257 /// Return module entry for module with the given \p ModPath.
1258 ModuleInfo *getModule(StringRef ModPath) {
1259 auto It = ModulePathStringTable.find(ModPath);
1260 assert(It != ModulePathStringTable.end() && "Module not registered");
1264 /// Check if the given Module has any functions available for exporting
1265 /// in the index. We consider any module present in the ModulePathStringTable
1266 /// to have exported functions.
1267 bool hasExportedFunctions(const Module &M) const {
1268 return ModulePathStringTable.count(M.getModuleIdentifier());
1271 const TypeIdSummaryMapTy &typeIds() const { return TypeIdMap; }
1273 /// Return an existing or new TypeIdSummary entry for \p TypeId.
1274 /// This accessor can mutate the map and therefore should not be used in
1275 /// the ThinLTO backends.
1276 TypeIdSummary &getOrInsertTypeIdSummary(StringRef TypeId) {
1277 auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1278 for (auto It = TidIter.first; It != TidIter.second; ++It)
1279 if (It->second.first == TypeId)
1280 return It->second.second;
1281 auto It = TypeIdMap.insert(
1282 {GlobalValue::getGUID(TypeId), {TypeId, TypeIdSummary()}});
1283 return It->second.second;
1286 /// This returns either a pointer to the type id summary (if present in the
1287 /// summary map) or null (if not present). This may be used when importing.
1288 const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const {
1289 auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1290 for (auto It = TidIter.first; It != TidIter.second; ++It)
1291 if (It->second.first == TypeId)
1292 return &It->second.second;
1296 const std::map<std::string, TypeIdCompatibleVtableInfo> &
1297 typeIdCompatibleVtableMap() const {
1298 return TypeIdCompatibleVtableMap;
1301 /// Return an existing or new TypeIdCompatibleVtableMap entry for \p TypeId.
1302 /// This accessor can mutate the map and therefore should not be used in
1303 /// the ThinLTO backends.
1304 TypeIdCompatibleVtableInfo &
1305 getOrInsertTypeIdCompatibleVtableSummary(StringRef TypeId) {
1306 return TypeIdCompatibleVtableMap[TypeId];
1309 /// For the given \p TypeId, this returns the TypeIdCompatibleVtableMap
1310 /// entry if present in the summary map. This may be used when importing.
1311 Optional<TypeIdCompatibleVtableInfo>
1312 getTypeIdCompatibleVtableSummary(StringRef TypeId) const {
1313 auto I = TypeIdCompatibleVtableMap.find(TypeId);
1314 if (I == TypeIdCompatibleVtableMap.end())
1319 /// Collect for the given module the list of functions it defines
1320 /// (GUID -> Summary).
1321 void collectDefinedFunctionsForModule(StringRef ModulePath,
1322 GVSummaryMapTy &GVSummaryMap) const;
1324 /// Collect for each module the list of Summaries it defines (GUID ->
1326 template <class Map>
1328 collectDefinedGVSummariesPerModule(Map &ModuleToDefinedGVSummaries) const {
1329 for (auto &GlobalList : *this) {
1330 auto GUID = GlobalList.first;
1331 for (auto &Summary : GlobalList.second.SummaryList) {
1332 ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
1337 /// Print to an output stream.
1338 void print(raw_ostream &OS, bool IsForDebug = false) const;
1340 /// Dump to stderr (for debugging).
1343 /// Export summary to dot file for GraphViz.
1344 void exportToDot(raw_ostream& OS) const;
1346 /// Print out strongly connected components for debugging.
1347 void dumpSCCs(raw_ostream &OS);
1349 /// Analyze index and detect unmodified globals
1350 void propagateAttributes(const DenseSet<GlobalValue::GUID> &PreservedSymbols);
1353 /// GraphTraits definition to build SCC for the index
1354 template <> struct GraphTraits<ValueInfo> {
1355 typedef ValueInfo NodeRef;
1356 using EdgeRef = FunctionSummary::EdgeTy &;
1358 static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) {
1361 using ChildIteratorType =
1362 mapped_iterator<std::vector<FunctionSummary::EdgeTy>::iterator,
1363 decltype(&valueInfoFromEdge)>;
1365 using ChildEdgeIteratorType = std::vector<FunctionSummary::EdgeTy>::iterator;
1367 static NodeRef getEntryNode(ValueInfo V) { return V; }
1369 static ChildIteratorType child_begin(NodeRef N) {
1370 if (!N.getSummaryList().size()) // handle external function
1371 return ChildIteratorType(
1372 FunctionSummary::ExternalNode.CallGraphEdgeList.begin(),
1373 &valueInfoFromEdge);
1374 FunctionSummary *F =
1375 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1376 return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge);
1379 static ChildIteratorType child_end(NodeRef N) {
1380 if (!N.getSummaryList().size()) // handle external function
1381 return ChildIteratorType(
1382 FunctionSummary::ExternalNode.CallGraphEdgeList.end(),
1383 &valueInfoFromEdge);
1384 FunctionSummary *F =
1385 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1386 return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge);
1389 static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
1390 if (!N.getSummaryList().size()) // handle external function
1391 return FunctionSummary::ExternalNode.CallGraphEdgeList.begin();
1393 FunctionSummary *F =
1394 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1395 return F->CallGraphEdgeList.begin();
1398 static ChildEdgeIteratorType child_edge_end(NodeRef N) {
1399 if (!N.getSummaryList().size()) // handle external function
1400 return FunctionSummary::ExternalNode.CallGraphEdgeList.end();
1402 FunctionSummary *F =
1403 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1404 return F->CallGraphEdgeList.end();
1407 static NodeRef edge_dest(EdgeRef E) { return E.first; }
1411 struct GraphTraits<ModuleSummaryIndex *> : public GraphTraits<ValueInfo> {
1412 static NodeRef getEntryNode(ModuleSummaryIndex *I) {
1413 std::unique_ptr<GlobalValueSummary> Root =
1414 make_unique<FunctionSummary>(I->calculateCallGraphRoot());
1415 GlobalValueSummaryInfo G(I->haveGVs());
1416 G.SummaryList.push_back(std::move(Root));
1418 GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G));
1419 return ValueInfo(I->haveGVs(), &P);
1423 static inline bool canImportGlobalVar(GlobalValueSummary *S) {
1424 assert(isa<GlobalVarSummary>(S->getBaseObject()));
1426 // We don't import GV with references, because it can result
1427 // in promotion of local variables in the source module.
1428 return !GlobalValue::isInterposableLinkage(S->linkage()) &&
1429 !S->notEligibleToImport() && S->refs().empty();
1431 } // end namespace llvm
1433 #endif // LLVM_IR_MODULESUMMARYINDEX_H