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