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