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