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