1//===- llvm/ModuleSummaryIndex.h - Module Summary Index ---------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10/// @file
11/// ModuleSummaryIndex.h This file contains the declarations the classes that
12/// hold the module index and summary for function importing.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_IR_MODULESUMMARYINDEX_H
17#define LLVM_IR_MODULESUMMARYINDEX_H
18
19#include "llvm/ADT/ArrayRef.h"
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/SmallString.h"
23#include "llvm/ADT/StringExtras.h"
24#include "llvm/ADT/StringMap.h"
25#include "llvm/ADT/StringRef.h"
26#include "llvm/ADT/TinyPtrVector.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 <algorithm>
34#include <array>
35#include <cassert>
36#include <cstddef>
37#include <cstdint>
38#include <map>
39#include <memory>
40#include <set>
41#include <string>
42#include <utility>
43#include <vector>
44
45namespace llvm {
46
47namespace yaml {
48
49template <typename T> struct MappingTraits;
50
51} // end namespace yaml
52
53/// Class to accumulate and hold information about a callee.
54struct CalleeInfo {
55 enum class HotnessType : uint8_t {
56 Unknown = 0,
57 Cold = 1,
58 None = 2,
59 Hot = 3,
60 Critical = 4
61 };
62
63 // The size of the bit-field might need to be adjusted if more values are
64 // added to HotnessType enum.
65 uint32_t Hotness : 3;
66
67 /// The value stored in RelBlockFreq has to be interpreted as the digits of
68 /// a scaled number with a scale of \p -ScaleShift.
69 uint32_t RelBlockFreq : 29;
70 static constexpr int32_t ScaleShift = 8;
71 static constexpr uint64_t MaxRelBlockFreq = (1 << 29) - 1;
72
73 CalleeInfo()
74 : Hotness(static_cast<uint32_t>(HotnessType::Unknown)), RelBlockFreq(0) {}
75 explicit CalleeInfo(HotnessType Hotness, uint64_t RelBF)
76 : Hotness(static_cast<uint32_t>(Hotness)), RelBlockFreq(RelBF) {}
77
78 void updateHotness(const HotnessType OtherHotness) {
79 Hotness = std::max(Hotness, static_cast<uint32_t>(OtherHotness));
80 }
81
82 HotnessType getHotness() const { return HotnessType(Hotness); }
83
84 /// Update \p RelBlockFreq from \p BlockFreq and \p EntryFreq
85 ///
86 /// BlockFreq is divided by EntryFreq and added to RelBlockFreq. To represent
87 /// fractional values, the result is represented as a fixed point number with
88 /// scale of -ScaleShift.
89 void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq) {
90 if (EntryFreq == 0)
91 return;
92 using Scaled64 = ScaledNumber<uint64_t>;
93 Scaled64 Temp(BlockFreq, ScaleShift);
94 Temp /= Scaled64::get(EntryFreq);
95
96 uint64_t Sum =
97 SaturatingAdd<uint64_t>(Temp.toInt<uint64_t>(), RelBlockFreq);
98 Sum = std::min(Sum, uint64_t(MaxRelBlockFreq));
99 RelBlockFreq = static_cast<uint32_t>(Sum);
100 }
101};
102
103inline const char *getHotnessName(CalleeInfo::HotnessType HT) {
104 switch (HT) {
105 case CalleeInfo::HotnessType::Unknown:
106 return "unknown";
107 case CalleeInfo::HotnessType::Cold:
108 return "cold";
109 case CalleeInfo::HotnessType::None:
110 return "none";
111 case CalleeInfo::HotnessType::Hot:
112 return "hot";
113 case CalleeInfo::HotnessType::Critical:
114 return "critical";
115 }
116 llvm_unreachable("invalid hotness");
117}
118
119class GlobalValueSummary;
120
121using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>;
122
123struct GlobalValueSummaryInfo {
124 union NameOrGV {
125 NameOrGV(bool HaveGVs) {
126 if (HaveGVs)
127 GV = nullptr;
128 else
129 Name = "";
130 }
131
132 /// The GlobalValue corresponding to this summary. This is only used in
133 /// per-module summaries and when the IR is available. E.g. when module
134 /// analysis is being run, or when parsing both the IR and the summary
135 /// from assembly.
136 const GlobalValue *GV;
137
138 /// Summary string representation. This StringRef points to BC module
139 /// string table and is valid until module data is stored in memory.
140 /// This is guaranteed to happen until runThinLTOBackend function is
141 /// called, so it is safe to use this field during thin link. This field
142 /// is only valid if summary index was loaded from BC file.
143 StringRef Name;
144 } U;
145
146 GlobalValueSummaryInfo(bool HaveGVs) : U(HaveGVs) {}
147
148 /// List of global value summary structures for a particular value held
149 /// in the GlobalValueMap. Requires a vector in the case of multiple
150 /// COMDAT values of the same name.
151 GlobalValueSummaryList SummaryList;
152};
153
154/// Map from global value GUID to corresponding summary structures. Use a
155/// std::map rather than a DenseMap so that pointers to the map's value_type
156/// (which are used by ValueInfo) are not invalidated by insertion. Also it will
157/// likely incur less overhead, as the value type is not very small and the size
158/// of the map is unknown, resulting in inefficiencies due to repeated
159/// insertions and resizing.
160using GlobalValueSummaryMapTy =
161 std::map<GlobalValue::GUID, GlobalValueSummaryInfo>;
162
163/// Struct that holds a reference to a particular GUID in a global value
164/// summary.
165struct ValueInfo {
166 PointerIntPair<const GlobalValueSummaryMapTy::value_type *, 2, int>
167 RefAndFlags;
168
169 ValueInfo() = default;
170 ValueInfo(bool HaveGVs, const GlobalValueSummaryMapTy::value_type *R) {
171 RefAndFlags.setPointer(R);
172 RefAndFlags.setInt(HaveGVs);
173 }
174
175 operator bool() const { return getRef(); }
176
177 GlobalValue::GUID getGUID() const { return getRef()->first; }
178 const GlobalValue *getValue() const {
179 assert(haveGVs());
180 return getRef()->second.U.GV;
181 }
182
183 ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const {
184 return getRef()->second.SummaryList;
185 }
186
187 StringRef name() const {
188 return haveGVs() ? getRef()->second.U.GV->getName()
189 : getRef()->second.U.Name;
190 }
191
192 bool haveGVs() const { return RefAndFlags.getInt() & 0x1; }
193 bool isReadOnly() const { return RefAndFlags.getInt() & 0x2; }
194 void setReadOnly() { RefAndFlags.setInt(RefAndFlags.getInt() | 0x2); }
195
196 const GlobalValueSummaryMapTy::value_type *getRef() const {
197 return RefAndFlags.getPointer();
198 }
199
200 bool isDSOLocal() const;
201};
202
203inline raw_ostream &operator<<(raw_ostream &OS, const ValueInfo &VI) {
204 OS << VI.getGUID();
205 if (!VI.name().empty())
206 OS << " (" << VI.name() << ")";
207 return OS;
208}
209
210inline bool operator==(const ValueInfo &A, const ValueInfo &B) {
211 assert(A.getRef() && B.getRef() &&
212 "Need ValueInfo with non-null Ref for comparison");
213 return A.getRef() == B.getRef();
214}
215
216inline bool operator!=(const ValueInfo &A, const ValueInfo &B) {
217 assert(A.getRef() && B.getRef() &&
218 "Need ValueInfo with non-null Ref for comparison");
219 return A.getRef() != B.getRef();
220}
221
222inline bool operator<(const ValueInfo &A, const ValueInfo &B) {
223 assert(A.getRef() && B.getRef() &&
224 "Need ValueInfo with non-null Ref to compare GUIDs");
225 return A.getGUID() < B.getGUID();
226}
227
228template <> struct DenseMapInfo<ValueInfo> {
229 static inline ValueInfo getEmptyKey() {
230 return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8);
231 }
232
233 static inline ValueInfo getTombstoneKey() {
234 return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-16);
235 }
236
237 static inline bool isSpecialKey(ValueInfo V) {
238 return V == getTombstoneKey() || V == getEmptyKey();
239 }
240
241 static bool isEqual(ValueInfo L, ValueInfo R) {
242 // We are not supposed to mix ValueInfo(s) with different HaveGVs flag
243 // in a same container.
244 assert(isSpecialKey(L) || isSpecialKey(R) || (L.haveGVs() == R.haveGVs()));
245 return L.getRef() == R.getRef();
246 }
247 static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); }
248};
249
250/// Function and variable summary information to aid decisions and
251/// implementation of importing.
252class GlobalValueSummary {
253public:
254 /// Sububclass discriminator (for dyn_cast<> et al.)
255 enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
256
257 /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
258 struct GVFlags {
259 /// The linkage type of the associated global value.
260 ///
261 /// One use is to flag values that have local linkage types and need to
262 /// have module identifier appended before placing into the combined
263 /// index, to disambiguate from other values with the same name.
264 /// In the future this will be used to update and optimize linkage
265 /// types based on global summary-based analysis.
266 unsigned Linkage : 4;
267
268 /// Indicate if the global value cannot be imported (e.g. it cannot
269 /// be renamed or references something that can't be renamed).
270 unsigned NotEligibleToImport : 1;
271
272 /// In per-module summary, indicate that the global value must be considered
273 /// a live root for index-based liveness analysis. Used for special LLVM
274 /// values such as llvm.global_ctors that the linker does not know about.
275 ///
276 /// In combined summary, indicate that the global value is live.
277 unsigned Live : 1;
278
279 /// Indicates that the linker resolved the symbol to a definition from
280 /// within the same linkage unit.
281 unsigned DSOLocal : 1;
282
283 /// Convenience Constructors
284 explicit GVFlags(GlobalValue::LinkageTypes Linkage,
285 bool NotEligibleToImport, bool Live, bool IsLocal)
286 : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport),
287 Live(Live), DSOLocal(IsLocal) {}
288 };
289
290private:
291 /// Kind of summary for use in dyn_cast<> et al.
292 SummaryKind Kind;
293
294 GVFlags Flags;
295
296 /// This is the hash of the name of the symbol in the original file. It is
297 /// identical to the GUID for global symbols, but differs for local since the
298 /// GUID includes the module level id in the hash.
299 GlobalValue::GUID OriginalName = 0;
300
301 /// Path of module IR containing value's definition, used to locate
302 /// module during importing.
303 ///
304 /// This is only used during parsing of the combined index, or when
305 /// parsing the per-module index for creation of the combined summary index,
306 /// not during writing of the per-module index which doesn't contain a
307 /// module path string table.
308 StringRef ModulePath;
309
310 /// List of values referenced by this global value's definition
311 /// (either by the initializer of a global variable, or referenced
312 /// from within a function). This does not include functions called, which
313 /// are listed in the derived FunctionSummary object.
314 std::vector<ValueInfo> RefEdgeList;
315
316protected:
317 GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
318 : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {
319 assert((K != AliasKind || Refs.empty()) &&
320 "Expect no references for AliasSummary");
321 }
322
323public:
324 virtual ~GlobalValueSummary() = default;
325
326 /// Returns the hash of the original name, it is identical to the GUID for
327 /// externally visible symbols, but not for local ones.
328 GlobalValue::GUID getOriginalName() const { return OriginalName; }
329
330 /// Initialize the original name hash in this summary.
331 void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
332
333 /// Which kind of summary subclass this is.
334 SummaryKind getSummaryKind() const { return Kind; }
335
336 /// Set the path to the module containing this function, for use in
337 /// the combined index.
338 void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
339
340 /// Get the path to the module containing this function.
341 StringRef modulePath() const { return ModulePath; }
342
343 /// Get the flags for this GlobalValue (see \p struct GVFlags).
344 GVFlags flags() const { return Flags; }
345
346 /// Return linkage type recorded for this global value.
347 GlobalValue::LinkageTypes linkage() const {
348 return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
349 }
350
351 /// Sets the linkage to the value determined by global summary-based
352 /// optimization. Will be applied in the ThinLTO backends.
353 void setLinkage(GlobalValue::LinkageTypes Linkage) {
354 Flags.Linkage = Linkage;
355 }
356
357 /// Return true if this global value can't be imported.
358 bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
359
360 bool isLive() const { return Flags.Live; }
361
362 void setLive(bool Live) { Flags.Live = Live; }
363
364 void setDSOLocal(bool Local) { Flags.DSOLocal = Local; }
365
366 bool isDSOLocal() const { return Flags.DSOLocal; }
367
368 /// Flag that this global value cannot be imported.
369 void setNotEligibleToImport() { Flags.NotEligibleToImport = true; }
370
371 /// Return the list of values referenced by this global value definition.
372 ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
373
374 /// If this is an alias summary, returns the summary of the aliased object (a
375 /// global variable or function), otherwise returns itself.
376 GlobalValueSummary *getBaseObject();
377 const GlobalValueSummary *getBaseObject() const;
378
379 friend class ModuleSummaryIndex;
380};
381
382/// Alias summary information.
383class AliasSummary : public GlobalValueSummary {
384 GlobalValueSummary *AliaseeSummary;
385 // AliaseeGUID is only set and accessed when we are building a combined index
386 // via the BitcodeReader.
387 GlobalValue::GUID AliaseeGUID;
388
389public:
390 AliasSummary(GVFlags Flags)
391 : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}),
392 AliaseeSummary(nullptr), AliaseeGUID(0) {}
393
394 /// Check if this is an alias summary.
395 static bool classof(const GlobalValueSummary *GVS) {
396 return GVS->getSummaryKind() == AliasKind;
397 }
398
399 void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
400 void setAliaseeGUID(GlobalValue::GUID GUID) { AliaseeGUID = GUID; }
401
402 bool hasAliasee() const { return !!AliaseeSummary; }
403
404 const GlobalValueSummary &getAliasee() const {
405 assert(AliaseeSummary && "Unexpected missing aliasee summary");
406 return *AliaseeSummary;
407 }
408
409 GlobalValueSummary &getAliasee() {
410 return const_cast<GlobalValueSummary &>(
411 static_cast<const AliasSummary *>(this)->getAliasee());
412 }
413 bool hasAliaseeGUID() const { return AliaseeGUID != 0; }
414 const GlobalValue::GUID &getAliaseeGUID() const {
415 assert(AliaseeGUID && "Unexpected missing aliasee GUID");
416 return AliaseeGUID;
417 }
418};
419
420const inline GlobalValueSummary *GlobalValueSummary::getBaseObject() const {
421 if (auto *AS = dyn_cast<AliasSummary>(this))
422 return &AS->getAliasee();
423 return this;
424}
425
426inline GlobalValueSummary *GlobalValueSummary::getBaseObject() {
427 if (auto *AS = dyn_cast<AliasSummary>(this))
428 return &AS->getAliasee();
429 return this;
430}
431
432/// Function summary information to aid decisions and implementation of
433/// importing.
434class FunctionSummary : public GlobalValueSummary {
435public:
436 /// <CalleeValueInfo, CalleeInfo> call edge pair.
437 using EdgeTy = std::pair<ValueInfo, CalleeInfo>;
438
439 /// Types for -force-summary-edges-cold debugging option.
440 enum ForceSummaryHotnessType : unsigned {
441 FSHT_None,
442 FSHT_AllNonCritical,
443 FSHT_All
444 };
445
446 /// An "identifier" for a virtual function. This contains the type identifier
447 /// represented as a GUID and the offset from the address point to the virtual
448 /// function pointer, where "address point" is as defined in the Itanium ABI:
449 /// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
450 struct VFuncId {
451 GlobalValue::GUID GUID;
452 uint64_t Offset;
453 };
454
455 /// A specification for a virtual function call with all constant integer
456 /// arguments. This is used to perform virtual constant propagation on the
457 /// summary.
458 struct ConstVCall {
459 VFuncId VFunc;
460 std::vector<uint64_t> Args;
461 };
462
463 /// All type identifier related information. Because these fields are
464 /// relatively uncommon we only allocate space for them if necessary.
465 struct TypeIdInfo {
466 /// List of type identifiers used by this function in llvm.type.test
467 /// intrinsics referenced by something other than an llvm.assume intrinsic,
468 /// represented as GUIDs.
469 std::vector<GlobalValue::GUID> TypeTests;
470
471 /// List of virtual calls made by this function using (respectively)
472 /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do
473 /// not have all constant integer arguments.
474 std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
475
476 /// List of virtual calls made by this function using (respectively)
477 /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with
478 /// all constant integer arguments.
479 std::vector<ConstVCall> TypeTestAssumeConstVCalls,
480 TypeCheckedLoadConstVCalls;
481 };
482
483 /// Flags specific to function summaries.
484 struct FFlags {
485 // Function attribute flags. Used to track if a function accesses memory,
486 // recurses or aliases.
487 unsigned ReadNone : 1;
488 unsigned ReadOnly : 1;
489 unsigned NoRecurse : 1;
490 unsigned ReturnDoesNotAlias : 1;
491
492 // Indicate if the global value cannot be inlined.
493 unsigned NoInline : 1;
494 };
495
496 /// Create an empty FunctionSummary (with specified call edges).
497 /// Used to represent external nodes and the dummy root node.
498 static FunctionSummary
499 makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) {
500 return FunctionSummary(
501 FunctionSummary::GVFlags(
502 GlobalValue::LinkageTypes::AvailableExternallyLinkage,
503 /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false),
504 /*InsCount=*/0, FunctionSummary::FFlags{}, /*EntryCount=*/0,
505 std::vector<ValueInfo>(), std::move(Edges),
506 std::vector<GlobalValue::GUID>(),
507 std::vector<FunctionSummary::VFuncId>(),
508 std::vector<FunctionSummary::VFuncId>(),
509 std::vector<FunctionSummary::ConstVCall>(),
510 std::vector<FunctionSummary::ConstVCall>());
511 }
512
513 /// A dummy node to reference external functions that aren't in the index
514 static FunctionSummary ExternalNode;
515
516private:
517 /// Number of instructions (ignoring debug instructions, e.g.) computed
518 /// during the initial compile step when the summary index is first built.
519 unsigned InstCount;
520
521 /// Function summary specific flags.
522 FFlags FunFlags;
523
524 /// The synthesized entry count of the function.
525 /// This is only populated during ThinLink phase and remains unused while
526 /// generating per-module summaries.
527 uint64_t EntryCount = 0;
528
529 /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
530 std::vector<EdgeTy> CallGraphEdgeList;
531
532 std::unique_ptr<TypeIdInfo> TIdInfo;
533
534public:
535 FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
536 uint64_t EntryCount, std::vector<ValueInfo> Refs,
537 std::vector<EdgeTy> CGEdges,
538 std::vector<GlobalValue::GUID> TypeTests,
539 std::vector<VFuncId> TypeTestAssumeVCalls,
540 std::vector<VFuncId> TypeCheckedLoadVCalls,
541 std::vector<ConstVCall> TypeTestAssumeConstVCalls,
542 std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
543 : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
544 InstCount(NumInsts), FunFlags(FunFlags), EntryCount(EntryCount),
545 CallGraphEdgeList(std::move(CGEdges)) {
546 if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
547 !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
548 !TypeCheckedLoadConstVCalls.empty())
549 TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
550 std::move(TypeTests), std::move(TypeTestAssumeVCalls),
551 std::move(TypeCheckedLoadVCalls),
552 std::move(TypeTestAssumeConstVCalls),
553 std::move(TypeCheckedLoadConstVCalls)});
554 }
555 // Gets the number of immutable refs in RefEdgeList
556 unsigned immutableRefCount() const;
557
558 /// Check if this is a function summary.
559 static bool classof(const GlobalValueSummary *GVS) {
560 return GVS->getSummaryKind() == FunctionKind;
561 }
562
563 /// Get function summary flags.
564 FFlags fflags() const { return FunFlags; }
565
566 /// Get the instruction count recorded for this function.
567 unsigned instCount() const { return InstCount; }
568
569 /// Get the synthetic entry count for this function.
570 uint64_t entryCount() const { return EntryCount; }
571
572 /// Set the synthetic entry count for this function.
573 void setEntryCount(uint64_t EC) { EntryCount = EC; }
574
575 /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
576 ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
577
578 /// Returns the list of type identifiers used by this function in
579 /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
580 /// represented as GUIDs.
581 ArrayRef<GlobalValue::GUID> type_tests() const {
582 if (TIdInfo)
583 return TIdInfo->TypeTests;
584 return {};
585 }
586
587 /// Returns the list of virtual calls made by this function using
588 /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
589 /// integer arguments.
590 ArrayRef<VFuncId> type_test_assume_vcalls() const {
591 if (TIdInfo)
592 return TIdInfo->TypeTestAssumeVCalls;
593 return {};
594 }
595
596 /// Returns the list of virtual calls made by this function using
597 /// llvm.type.checked.load intrinsics that do not have all constant integer
598 /// arguments.
599 ArrayRef<VFuncId> type_checked_load_vcalls() const {
600 if (TIdInfo)
601 return TIdInfo->TypeCheckedLoadVCalls;
602 return {};
603 }
604
605 /// Returns the list of virtual calls made by this function using
606 /// llvm.assume(llvm.type.test) intrinsics with all constant integer
607 /// arguments.
608 ArrayRef<ConstVCall> type_test_assume_const_vcalls() const {
609 if (TIdInfo)
610 return TIdInfo->TypeTestAssumeConstVCalls;
611 return {};
612 }
613
614 /// Returns the list of virtual calls made by this function using
615 /// llvm.type.checked.load intrinsics with all constant integer arguments.
616 ArrayRef<ConstVCall> type_checked_load_const_vcalls() const {
617 if (TIdInfo)
618 return TIdInfo->TypeCheckedLoadConstVCalls;
619 return {};
620 }
621
622 /// Add a type test to the summary. This is used by WholeProgramDevirt if we
623 /// were unable to devirtualize a checked call.
624 void addTypeTest(GlobalValue::GUID Guid) {
625 if (!TIdInfo)
626 TIdInfo = llvm::make_unique<TypeIdInfo>();
627 TIdInfo->TypeTests.push_back(Guid);
628 }
629
630 const TypeIdInfo *getTypeIdInfo() const { return TIdInfo.get(); };
631
632 friend struct GraphTraits<ValueInfo>;
633};
634
635template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
636 static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
637
638 static FunctionSummary::VFuncId getTombstoneKey() {
639 return {0, uint64_t(-2)};
640 }
641
642 static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R) {
643 return L.GUID == R.GUID && L.Offset == R.Offset;
644 }
645
646 static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
647};
648
649template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
650 static FunctionSummary::ConstVCall getEmptyKey() {
651 return {{0, uint64_t(-1)}, {}};
652 }
653
654 static FunctionSummary::ConstVCall getTombstoneKey() {
655 return {{0, uint64_t(-2)}, {}};
656 }
657
658 static bool isEqual(FunctionSummary::ConstVCall L,
659 FunctionSummary::ConstVCall R) {
660 return DenseMapInfo<FunctionSummary::VFuncId>::isEqual(L.VFunc, R.VFunc) &&
661 L.Args == R.Args;
662 }
663
664 static unsigned getHashValue(FunctionSummary::ConstVCall I) {
665 return I.VFunc.GUID;
666 }
667};
668
669/// Global variable summary information to aid decisions and
670/// implementation of importing.
671///
672/// Global variable summary has extra flag, telling if it is
673/// modified during the program run or not. This affects ThinLTO
674/// internalization
675class GlobalVarSummary : public GlobalValueSummary {
676public:
677 struct GVarFlags {
678 GVarFlags(bool ReadOnly = false) : ReadOnly(ReadOnly) {}
679
680 unsigned ReadOnly : 1;
681 } VarFlags;
682
683 GlobalVarSummary(GVFlags Flags, GVarFlags VarFlags,
684 std::vector<ValueInfo> Refs)
685 : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)),
686 VarFlags(VarFlags) {}
687
688 /// Check if this is a global variable summary.
689 static bool classof(const GlobalValueSummary *GVS) {
690 return GVS->getSummaryKind() == GlobalVarKind;
691 }
692
693 GVarFlags varflags() const { return VarFlags; }
694 void setReadOnly(bool RO) { VarFlags.ReadOnly = RO; }
695 bool isReadOnly() const { return VarFlags.ReadOnly; }
696};
697
698struct TypeTestResolution {
699 /// Specifies which kind of type check we should emit for this byte array.
700 /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
701 /// details on each kind of check; the enumerators are described with
702 /// reference to that document.
703 enum Kind {
704 Unsat, ///< Unsatisfiable type (i.e. no global has this type metadata)
705 ByteArray, ///< Test a byte array (first example)
706 Inline, ///< Inlined bit vector ("Short Inline Bit Vectors")
707 Single, ///< Single element (last example in "Short Inline Bit Vectors")
708 AllOnes, ///< All-ones bit vector ("Eliminating Bit Vector Checks for
709 /// All-Ones Bit Vectors")
710 } TheKind = Unsat;
711
712 /// Range of size-1 expressed as a bit width. For example, if the size is in
713 /// range [1,256], this number will be 8. This helps generate the most compact
714 /// instruction sequences.
715 unsigned SizeM1BitWidth = 0;
716
717 // The following fields are only used if the target does not support the use
718 // of absolute symbols to store constants. Their meanings are the same as the
719 // corresponding fields in LowerTypeTestsModule::TypeIdLowering in
720 // LowerTypeTests.cpp.
721
722 uint64_t AlignLog2 = 0;
723 uint64_t SizeM1 = 0;
724 uint8_t BitMask = 0;
725 uint64_t InlineBits = 0;
726};
727
728struct WholeProgramDevirtResolution {
729 enum Kind {
730 Indir, ///< Just do a regular virtual call
731 SingleImpl, ///< Single implementation devirtualization
732 BranchFunnel, ///< When retpoline mitigation is enabled, use a branch funnel
733 ///< that is defined in the merged module. Otherwise same as
734 ///< Indir.
735 } TheKind = Indir;
736
737 std::string SingleImplName;
738
739 struct ByArg {
740 enum Kind {
741 Indir, ///< Just do a regular virtual call
742 UniformRetVal, ///< Uniform return value optimization
743 UniqueRetVal, ///< Unique return value optimization
744 VirtualConstProp, ///< Virtual constant propagation
745 } TheKind = Indir;
746
747 /// Additional information for the resolution:
748 /// - UniformRetVal: the uniform return value.
749 /// - UniqueRetVal: the return value associated with the unique vtable (0 or
750 /// 1).
751 uint64_t Info = 0;
752
753 // The following fields are only used if the target does not support the use
754 // of absolute symbols to store constants.
755
756 uint32_t Byte = 0;
757 uint32_t Bit = 0;
758 };
759
760 /// Resolutions for calls with all constant integer arguments (excluding the
761 /// first argument, "this"), where the key is the argument vector.
762 std::map<std::vector<uint64_t>, ByArg> ResByArg;
763};
764
765struct TypeIdSummary {
766 TypeTestResolution TTRes;
767
768 /// Mapping from byte offset to whole-program devirt resolution for that
769 /// (typeid, byte offset) pair.
770 std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
771};
772
773/// 160 bits SHA1
774using ModuleHash = std::array<uint32_t, 5>;
775
776/// Type used for iterating through the global value summary map.
777using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
778using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
779
780/// String table to hold/own module path strings, which additionally holds the
781/// module ID assigned to each module during the plugin step, as well as a hash
782/// of the module. The StringMap makes a copy of and owns inserted strings.
783using ModulePathStringTableTy = StringMap<std::pair<uint64_t, ModuleHash>>;
784
785/// Map of global value GUID to its summary, used to identify values defined in
786/// a particular module, and provide efficient access to their summary.
787using GVSummaryMapTy = DenseMap<GlobalValue::GUID, GlobalValueSummary *>;
788
789/// Map of a type GUID to type id string and summary (multimap used
790/// in case of GUID conflicts).
791using TypeIdSummaryMapTy =
792 std::multimap<GlobalValue::GUID, std::pair<std::string, TypeIdSummary>>;
793
794/// Class to hold module path string table and global value map,
795/// and encapsulate methods for operating on them.
796class ModuleSummaryIndex {
797private:
798 /// Map from value name to list of summary instances for values of that
799 /// name (may be duplicates in the COMDAT case, e.g.).
800 GlobalValueSummaryMapTy GlobalValueMap;
801
802 /// Holds strings for combined index, mapping to the corresponding module ID.
803 ModulePathStringTableTy ModulePathStringTable;
804
805 /// Mapping from type identifier GUIDs to type identifier and its summary
806 /// information.
807 TypeIdSummaryMapTy TypeIdMap;
808
809 /// Mapping from original ID to GUID. If original ID can map to multiple
810 /// GUIDs, it will be mapped to 0.
811 std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
812
813 /// Indicates that summary-based GlobalValue GC has run, and values with
814 /// GVFlags::Live==false are really dead. Otherwise, all values must be
815 /// considered live.
816 bool WithGlobalValueDeadStripping = false;
817
818 /// Indicates that summary-based synthetic entry count propagation has run
819 bool HasSyntheticEntryCounts = false;
820
821 /// Indicates that distributed backend should skip compilation of the
822 /// module. Flag is suppose to be set by distributed ThinLTO indexing
823 /// when it detected that the module is not needed during the final
824 /// linking. As result distributed backend should just output a minimal
825 /// valid object file.
826 bool SkipModuleByDistributedBackend = false;
827
828 /// If true then we're performing analysis of IR module, or parsing along with
829 /// the IR from assembly. The value of 'false' means we're reading summary
830 /// from BC or YAML source. Affects the type of value stored in NameOrGV
831 /// union.
832 bool HaveGVs;
833
834 // True if the index was created for a module compiled with -fsplit-lto-unit.
835 bool EnableSplitLTOUnit;
836
837 // True if some of the modules were compiled with -fsplit-lto-unit and
838 // some were not. Set when the combined index is created during the thin link.
839 bool PartiallySplitLTOUnits = false;
840
841 std::set<std::string> CfiFunctionDefs;
842 std::set<std::string> CfiFunctionDecls;
843
844 // Used in cases where we want to record the name of a global, but
845 // don't have the string owned elsewhere (e.g. the Strtab on a module).
846 StringSaver Saver;
847 BumpPtrAllocator Alloc;
848
849 // YAML I/O support.
850 friend yaml::MappingTraits<ModuleSummaryIndex>;
851
852 GlobalValueSummaryMapTy::value_type *
853 getOrInsertValuePtr(GlobalValue::GUID GUID) {
854 return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs))
855 .first;
856 }
857
858public:
859 // See HaveGVs variable comment.
860 ModuleSummaryIndex(bool HaveGVs, bool EnableSplitLTOUnit = false)
861 : HaveGVs(HaveGVs), EnableSplitLTOUnit(EnableSplitLTOUnit), Saver(Alloc) {
862 }
863
864 bool haveGVs() const { return HaveGVs; }
865
866 gvsummary_iterator begin() { return GlobalValueMap.begin(); }
867 const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
868 gvsummary_iterator end() { return GlobalValueMap.end(); }
869 const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
870 size_t size() const { return GlobalValueMap.size(); }
871
872 /// Convenience function for doing a DFS on a ValueInfo. Marks the function in
873 /// the FunctionHasParent map.
874 static void discoverNodes(ValueInfo V,
875 std::map<ValueInfo, bool> &FunctionHasParent) {
876 if (!V.getSummaryList().size())
877 return; // skip external functions that don't have summaries
878
879 // Mark discovered if we haven't yet
880 auto S = FunctionHasParent.emplace(V, false);
881
882 // Stop if we've already discovered this node
883 if (!S.second)
884 return;
885
886 FunctionSummary *F =
887 dyn_cast<FunctionSummary>(V.getSummaryList().front().get());
888 assert(F != nullptr && "Expected FunctionSummary node");
889
890 for (auto &C : F->calls()) {
891 // Insert node if necessary
892 auto S = FunctionHasParent.emplace(C.first, true);
893
894 // Skip nodes that we're sure have parents
895 if (!S.second && S.first->second)
896 continue;
897
898 if (S.second)
899 discoverNodes(C.first, FunctionHasParent);
900 else
901 S.first->second = true;
902 }
903 }
904
905 // Calculate the callgraph root
906 FunctionSummary calculateCallGraphRoot() {
907 // Functions that have a parent will be marked in FunctionHasParent pair.
908 // Once we've marked all functions, the functions in the map that are false
909 // have no parent (so they're the roots)
910 std::map<ValueInfo, bool> FunctionHasParent;
911
912 for (auto &S : *this) {
913 // Skip external functions
914 if (!S.second.SummaryList.size() ||
915 !isa<FunctionSummary>(S.second.SummaryList.front().get()))
916 continue;
917 discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent);
918 }
919
920 std::vector<FunctionSummary::EdgeTy> Edges;
921 // create edges to all roots in the Index
922 for (auto &P : FunctionHasParent) {
923 if (P.second)
924 continue; // skip over non-root nodes
925 Edges.push_back(std::make_pair(P.first, CalleeInfo{}));
926 }
927 if (Edges.empty()) {
928 // Failed to find root - return an empty node
929 return FunctionSummary::makeDummyFunctionSummary({});
930 }
931 auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
932 return CallGraphRoot;
933 }
934
935 bool withGlobalValueDeadStripping() const {
936 return WithGlobalValueDeadStripping;
937 }
938 void setWithGlobalValueDeadStripping() {
939 WithGlobalValueDeadStripping = true;
940 }
941
942 bool hasSyntheticEntryCounts() const { return HasSyntheticEntryCounts; }
943 void setHasSyntheticEntryCounts() { HasSyntheticEntryCounts = true; }
944
945 bool skipModuleByDistributedBackend() const {
946 return SkipModuleByDistributedBackend;
947 }
948 void setSkipModuleByDistributedBackend() {
949 SkipModuleByDistributedBackend = true;
950 }
951
952 bool enableSplitLTOUnit() const { return EnableSplitLTOUnit; }
953 void setEnableSplitLTOUnit() { EnableSplitLTOUnit = true; }
954
955 bool partiallySplitLTOUnits() const { return PartiallySplitLTOUnits; }
956 void setPartiallySplitLTOUnits() { PartiallySplitLTOUnits = true; }
957
958 bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
959 return !WithGlobalValueDeadStripping || GVS->isLive();
960 }
961 bool isGUIDLive(GlobalValue::GUID GUID) const;
962
963 /// Return a ValueInfo for the index value_type (convenient when iterating
964 /// index).
965 ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const {
966 return ValueInfo(HaveGVs, &R);
967 }
968
969 /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
970 ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
971 auto I = GlobalValueMap.find(GUID);
972 return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I);
973 }
974
975 /// Return a ValueInfo for \p GUID.
976 ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) {
977 return ValueInfo(HaveGVs, getOrInsertValuePtr(GUID));
978 }
979
980 // Save a string in the Index. Use before passing Name to
981 // getOrInsertValueInfo when the string isn't owned elsewhere (e.g. on the
982 // module's Strtab).
983 StringRef saveString(StringRef String) { return Saver.save(String); }
984
985 /// Return a ValueInfo for \p GUID setting value \p Name.
986 ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name) {
987 assert(!HaveGVs);
988 auto VP = getOrInsertValuePtr(GUID);
989 VP->second.U.Name = Name;
990 return ValueInfo(HaveGVs, VP);
991 }
992
993 /// Return a ValueInfo for \p GV and mark it as belonging to GV.
994 ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
995 assert(HaveGVs);
996 auto VP = getOrInsertValuePtr(GV->getGUID());
997 VP->second.U.GV = GV;
998 return ValueInfo(HaveGVs, VP);
999 }
1000
1001 /// Return the GUID for \p OriginalId in the OidGuidMap.
1002 GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const {
1003 const auto I = OidGuidMap.find(OriginalID);
1004 return I == OidGuidMap.end() ? 0 : I->second;
1005 }
1006
1007 std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; }
1008 const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; }
1009
1010 std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; }
1011 const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; }
1012
1013 /// Add a global value summary for a value.
1014 void addGlobalValueSummary(const GlobalValue &GV,
1015 std::unique_ptr<GlobalValueSummary> Summary) {
1016 addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary));
1017 }
1018
1019 /// Add a global value summary for a value of the given name.
1020 void addGlobalValueSummary(StringRef ValueName,
1021 std::unique_ptr<GlobalValueSummary> Summary) {
1022 addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
1023 std::move(Summary));
1024 }
1025
1026 /// Add a global value summary for the given ValueInfo.
1027 void addGlobalValueSummary(ValueInfo VI,
1028 std::unique_ptr<GlobalValueSummary> Summary) {
1029 addOriginalName(VI.getGUID(), Summary->getOriginalName());
1030 // Here we have a notionally const VI, but the value it points to is owned
1031 // by the non-const *this.
1032 const_cast<GlobalValueSummaryMapTy::value_type *>(VI.getRef())
1033 ->second.SummaryList.push_back(std::move(Summary));
1034 }
1035
1036 /// Add an original name for the value of the given GUID.
1037 void addOriginalName(GlobalValue::GUID ValueGUID,
1038 GlobalValue::GUID OrigGUID) {
1039 if (OrigGUID == 0 || ValueGUID == OrigGUID)
1040 return;
1041 if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
1042 OidGuidMap[OrigGUID] = 0;
1043 else
1044 OidGuidMap[OrigGUID] = ValueGUID;
1045 }
1046
1047 /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
1048 /// not found.
1049 GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
1050 StringRef ModuleId) const {
1051 auto CalleeInfo = getValueInfo(ValueGUID);
1052 if (!CalleeInfo) {
1053 return nullptr; // This function does not have a summary
1054 }
1055 auto Summary =
1056 llvm::find_if(CalleeInfo.getSummaryList(),
1057 [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
1058 return Summary->modulePath() == ModuleId;
1059 });
1060 if (Summary == CalleeInfo.getSummaryList().end())
1061 return nullptr;
1062 return Summary->get();
1063 }
1064
1065 /// Returns the first GlobalValueSummary for \p GV, asserting that there
1066 /// is only one if \p PerModuleIndex.
1067 GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
1068 bool PerModuleIndex = true) const {
1069 assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
1070 return getGlobalValueSummary(GV.getGUID(), PerModuleIndex);
1071 }
1072
1073 /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
1074 /// there
1075 /// is only one if \p PerModuleIndex.
1076 GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
1077 bool PerModuleIndex = true) const;
1078
1079 /// Table of modules, containing module hash and id.
1080 const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
1081 return ModulePathStringTable;
1082 }
1083
1084 /// Table of modules, containing hash and id.
1085 StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
1086 return ModulePathStringTable;
1087 }
1088
1089 /// Get the module ID recorded for the given module path.
1090 uint64_t getModuleId(const StringRef ModPath) const {
1091 return ModulePathStringTable.lookup(ModPath).first;
1092 }
1093
1094 /// Get the module SHA1 hash recorded for the given module path.
1095 const ModuleHash &getModuleHash(const StringRef ModPath) const {
1096 auto It = ModulePathStringTable.find(ModPath);
1097 assert(It != ModulePathStringTable.end() && "Module not registered");
1098 return It->second.second;
1099 }
1100
1101 /// Convenience method for creating a promoted global name
1102 /// for the given value name of a local, and its original module's ID.
1103 static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
1104 SmallString<256> NewName(Name);
1105 NewName += ".llvm.";
1106 NewName += utostr((uint64_t(ModHash[0]) << 32) |
1107 ModHash[1]); // Take the first 64 bits
1108 return NewName.str();
1109 }
1110
1111 /// Helper to obtain the unpromoted name for a global value (or the original
1112 /// name if not promoted).
1113 static StringRef getOriginalNameBeforePromote(StringRef Name) {
1114 std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
1115 return Pair.first;
1116 }
1117
1118 typedef ModulePathStringTableTy::value_type ModuleInfo;
1119
1120 /// Add a new module with the given \p Hash, mapped to the given \p
1121 /// ModID, and return a reference to the module.
1122 ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
1123 ModuleHash Hash = ModuleHash{{0}}) {
1124 return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first;
1125 }
1126
1127 /// Return module entry for module with the given \p ModPath.
1128 ModuleInfo *getModule(StringRef ModPath) {
1129 auto It = ModulePathStringTable.find(ModPath);
1130 assert(It != ModulePathStringTable.end() && "Module not registered");
1131 return &*It;
1132 }
1133
1134 /// Check if the given Module has any functions available for exporting
1135 /// in the index. We consider any module present in the ModulePathStringTable
1136 /// to have exported functions.
1137 bool hasExportedFunctions(const Module &M) const {
1138 return ModulePathStringTable.count(M.getModuleIdentifier());
1139 }
1140
1141 const TypeIdSummaryMapTy &typeIds() const { return TypeIdMap; }
1142
1143 /// Return an existing or new TypeIdSummary entry for \p TypeId.
1144 /// This accessor can mutate the map and therefore should not be used in
1145 /// the ThinLTO backends.
1146 TypeIdSummary &getOrInsertTypeIdSummary(StringRef TypeId) {
1147 auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1148 for (auto It = TidIter.first; It != TidIter.second; ++It)
1149 if (It->second.first == TypeId)
1150 return It->second.second;
1151 auto It = TypeIdMap.insert(
1152 {GlobalValue::getGUID(TypeId), {TypeId, TypeIdSummary()}});
1153 return It->second.second;
1154 }
1155
1156 /// This returns either a pointer to the type id summary (if present in the
1157 /// summary map) or null (if not present). This may be used when importing.
1158 const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const {
1159 auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1160 for (auto It = TidIter.first; It != TidIter.second; ++It)
1161 if (It->second.first == TypeId)
1162 return &It->second.second;
1163 return nullptr;
1164 }
1165
1166 /// Collect for the given module the list of functions it defines
1167 /// (GUID -> Summary).
1168 void collectDefinedFunctionsForModule(StringRef ModulePath,
1169 GVSummaryMapTy &GVSummaryMap) const;
1170
1171 /// Collect for each module the list of Summaries it defines (GUID ->
1172 /// Summary).
1173 void collectDefinedGVSummariesPerModule(
1174 StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const;
1175
1176 /// Print to an output stream.
1177 void print(raw_ostream &OS, bool IsForDebug = false) const;
1178
1179 /// Dump to stderr (for debugging).
1180 void dump() const;
1181
1182 /// Export summary to dot file for GraphViz.
1183 void exportToDot(raw_ostream& OS) const;
1184
1185 /// Print out strongly connected components for debugging.
1186 void dumpSCCs(raw_ostream &OS);
1187
1188 /// Analyze index and detect unmodified globals
1189 void propagateConstants(const DenseSet<GlobalValue::GUID> &PreservedSymbols);
1190};
1191
1192/// GraphTraits definition to build SCC for the index
1193template <> struct GraphTraits<ValueInfo> {
1194 typedef ValueInfo NodeRef;
1195 using EdgeRef = FunctionSummary::EdgeTy &;
1196
1197 static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) {
1198 return P.first;
1199 }
1200 using ChildIteratorType =
1201 mapped_iterator<std::vector<FunctionSummary::EdgeTy>::iterator,
1202 decltype(&valueInfoFromEdge)>;
1203
1204 using ChildEdgeIteratorType = std::vector<FunctionSummary::EdgeTy>::iterator;
1205
1206 static NodeRef getEntryNode(ValueInfo V) { return V; }
1207
1208 static ChildIteratorType child_begin(NodeRef N) {
1209 if (!N.getSummaryList().size()) // handle external function
1210 return ChildIteratorType(
1211 FunctionSummary::ExternalNode.CallGraphEdgeList.begin(),
1212 &valueInfoFromEdge);
1213 FunctionSummary *F =
1214 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1215 return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge);
1216 }
1217
1218 static ChildIteratorType child_end(NodeRef N) {
1219 if (!N.getSummaryList().size()) // handle external function
1220 return ChildIteratorType(
1221 FunctionSummary::ExternalNode.CallGraphEdgeList.end(),
1222 &valueInfoFromEdge);
1223 FunctionSummary *F =
1224 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1225 return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge);
1226 }
1227
1228 static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
1229 if (!N.getSummaryList().size()) // handle external function
1230 return FunctionSummary::ExternalNode.CallGraphEdgeList.begin();
1231
1232 FunctionSummary *F =
1233 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1234 return F->CallGraphEdgeList.begin();
1235 }
1236
1237 static ChildEdgeIteratorType child_edge_end(NodeRef N) {
1238 if (!N.getSummaryList().size()) // handle external function
1239 return FunctionSummary::ExternalNode.CallGraphEdgeList.end();
1240
1241 FunctionSummary *F =
1242 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1243 return F->CallGraphEdgeList.end();
1244 }
1245
1246 static NodeRef edge_dest(EdgeRef E) { return E.first; }
1247};
1248
1249template <>
1250struct GraphTraits<ModuleSummaryIndex *> : public GraphTraits<ValueInfo> {
1251 static NodeRef getEntryNode(ModuleSummaryIndex *I) {
1252 std::unique_ptr<GlobalValueSummary> Root =
1253 make_unique<FunctionSummary>(I->calculateCallGraphRoot());
1254 GlobalValueSummaryInfo G(I->haveGVs());
1255 G.SummaryList.push_back(std::move(Root));
1256 static auto P =
1257 GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G));
1258 return ValueInfo(I->haveGVs(), &P);
1259 }
1260};
1261
1262static inline bool canImportGlobalVar(GlobalValueSummary *S) {
1263 assert(isa<GlobalVarSummary>(S->getBaseObject()));
1264
1265 // We don't import GV with references, because it can result
1266 // in promotion of local variables in the source module.
1267 return !GlobalValue::isInterposableLinkage(S->linkage()) &&
1268 !S->notEligibleToImport() && S->refs().empty();
1269}
1270} // end namespace llvm
1271
1272#endif // LLVM_IR_MODULESUMMARYINDEX_H
1273