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