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

source code of llvm/include/llvm/IR/ModuleSummaryIndex.h