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