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