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