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

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