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