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