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