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