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