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 we have whole program visibility. 1126 bool WithWholeProgramVisibility = false; 1127 1128 /// Indicates that summary-based synthetic entry count propagation has run 1129 bool HasSyntheticEntryCounts = false; 1130 1131 /// Indicates that distributed backend should skip compilation of the 1132 /// module. Flag is suppose to be set by distributed ThinLTO indexing 1133 /// when it detected that the module is not needed during the final 1134 /// linking. As result distributed backend should just output a minimal 1135 /// valid object file. 1136 bool SkipModuleByDistributedBackend = false; 1137 1138 /// If true then we're performing analysis of IR module, or parsing along with 1139 /// the IR from assembly. The value of 'false' means we're reading summary 1140 /// from BC or YAML source. Affects the type of value stored in NameOrGV 1141 /// union. 1142 bool HaveGVs; 1143 1144 // True if the index was created for a module compiled with -fsplit-lto-unit. 1145 bool EnableSplitLTOUnit; 1146 1147 // True if some of the modules were compiled with -fsplit-lto-unit and 1148 // some were not. Set when the combined index is created during the thin link. 1149 bool PartiallySplitLTOUnits = false; 1150 1151 /// True if some of the FunctionSummary contains a ParamAccess. 1152 bool HasParamAccess = false; 1153 1154 std::set<std::string> CfiFunctionDefs; 1155 std::set<std::string> CfiFunctionDecls; 1156 1157 // Used in cases where we want to record the name of a global, but 1158 // don't have the string owned elsewhere (e.g. the Strtab on a module). 1159 BumpPtrAllocator Alloc; 1160 StringSaver Saver; 1161 1162 // The total number of basic blocks in the module in the per-module summary or 1163 // the total number of basic blocks in the LTO unit in the combined index. 1164 uint64_t BlockCount; 1165 1166 // YAML I/O support. 1167 friend yaml::MappingTraits<ModuleSummaryIndex>; 1168 1169 GlobalValueSummaryMapTy::value_type * 1170 getOrInsertValuePtr(GlobalValue::GUID GUID) { 1171 return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs)) 1172 .first; 1173 } 1174 1175 public: 1176 // See HaveGVs variable comment. 1177 ModuleSummaryIndex(bool HaveGVs, bool EnableSplitLTOUnit = false) 1178 : HaveGVs(HaveGVs), EnableSplitLTOUnit(EnableSplitLTOUnit), Saver(Alloc), 1179 BlockCount(0) {} 1180 1181 // Current version for the module summary in bitcode files. 1182 // The BitcodeSummaryVersion should be bumped whenever we introduce changes 1183 // in the way some record are interpreted, like flags for instance. 1184 // Note that incrementing this may require changes in both BitcodeReader.cpp 1185 // and BitcodeWriter.cpp. 1186 static constexpr uint64_t BitcodeSummaryVersion = 9; 1187 1188 // Regular LTO module name for ASM writer 1189 static constexpr const char *getRegularLTOModuleName() { 1190 return "[Regular LTO]"; 1191 } 1192 1193 bool haveGVs() const { return HaveGVs; } 1194 1195 uint64_t getFlags() const; 1196 void setFlags(uint64_t Flags); 1197 1198 uint64_t getBlockCount() const { return BlockCount; } 1199 void addBlockCount(uint64_t C) { BlockCount += C; } 1200 void setBlockCount(uint64_t C) { BlockCount = C; } 1201 1202 gvsummary_iterator begin() { return GlobalValueMap.begin(); } 1203 const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); } 1204 gvsummary_iterator end() { return GlobalValueMap.end(); } 1205 const_gvsummary_iterator end() const { return GlobalValueMap.end(); } 1206 size_t size() const { return GlobalValueMap.size(); } 1207 1208 /// Convenience function for doing a DFS on a ValueInfo. Marks the function in 1209 /// the FunctionHasParent map. 1210 static void discoverNodes(ValueInfo V, 1211 std::map<ValueInfo, bool> &FunctionHasParent) { 1212 if (!V.getSummaryList().size()) 1213 return; // skip external functions that don't have summaries 1214 1215 // Mark discovered if we haven't yet 1216 auto S = FunctionHasParent.emplace(V, false); 1217 1218 // Stop if we've already discovered this node 1219 if (!S.second) 1220 return; 1221 1222 FunctionSummary *F = 1223 dyn_cast<FunctionSummary>(V.getSummaryList().front().get()); 1224 assert(F != nullptr && "Expected FunctionSummary node"); 1225 1226 for (auto &C : F->calls()) { 1227 // Insert node if necessary 1228 auto S = FunctionHasParent.emplace(C.first, true); 1229 1230 // Skip nodes that we're sure have parents 1231 if (!S.second && S.first->second) 1232 continue; 1233 1234 if (S.second) 1235 discoverNodes(C.first, FunctionHasParent); 1236 else 1237 S.first->second = true; 1238 } 1239 } 1240 1241 // Calculate the callgraph root 1242 FunctionSummary calculateCallGraphRoot() { 1243 // Functions that have a parent will be marked in FunctionHasParent pair. 1244 // Once we've marked all functions, the functions in the map that are false 1245 // have no parent (so they're the roots) 1246 std::map<ValueInfo, bool> FunctionHasParent; 1247 1248 for (auto &S : *this) { 1249 // Skip external functions 1250 if (!S.second.SummaryList.size() || 1251 !isa<FunctionSummary>(S.second.SummaryList.front().get())) 1252 continue; 1253 discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent); 1254 } 1255 1256 std::vector<FunctionSummary::EdgeTy> Edges; 1257 // create edges to all roots in the Index 1258 for (auto &P : FunctionHasParent) { 1259 if (P.second) 1260 continue; // skip over non-root nodes 1261 Edges.push_back(std::make_pair(P.first, CalleeInfo{})); 1262 } 1263 if (Edges.empty()) { 1264 // Failed to find root - return an empty node 1265 return FunctionSummary::makeDummyFunctionSummary({}); 1266 } 1267 auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges); 1268 return CallGraphRoot; 1269 } 1270 1271 bool withGlobalValueDeadStripping() const { 1272 return WithGlobalValueDeadStripping; 1273 } 1274 void setWithGlobalValueDeadStripping() { 1275 WithGlobalValueDeadStripping = true; 1276 } 1277 1278 bool withAttributePropagation() const { return WithAttributePropagation; } 1279 void setWithAttributePropagation() { 1280 WithAttributePropagation = true; 1281 } 1282 1283 bool withDSOLocalPropagation() const { return WithDSOLocalPropagation; } 1284 void setWithDSOLocalPropagation() { WithDSOLocalPropagation = true; } 1285 1286 bool withWholeProgramVisibility() const { return WithWholeProgramVisibility; } 1287 void setWithWholeProgramVisibility() { WithWholeProgramVisibility = true; } 1288 1289 bool isReadOnly(const GlobalVarSummary *GVS) const { 1290 return WithAttributePropagation && GVS->maybeReadOnly(); 1291 } 1292 bool isWriteOnly(const GlobalVarSummary *GVS) const { 1293 return WithAttributePropagation && GVS->maybeWriteOnly(); 1294 } 1295 1296 bool hasSyntheticEntryCounts() const { return HasSyntheticEntryCounts; } 1297 void setHasSyntheticEntryCounts() { HasSyntheticEntryCounts = true; } 1298 1299 bool skipModuleByDistributedBackend() const { 1300 return SkipModuleByDistributedBackend; 1301 } 1302 void setSkipModuleByDistributedBackend() { 1303 SkipModuleByDistributedBackend = true; 1304 } 1305 1306 bool enableSplitLTOUnit() const { return EnableSplitLTOUnit; } 1307 void setEnableSplitLTOUnit() { EnableSplitLTOUnit = true; } 1308 1309 bool partiallySplitLTOUnits() const { return PartiallySplitLTOUnits; } 1310 void setPartiallySplitLTOUnits() { PartiallySplitLTOUnits = true; } 1311 1312 bool hasParamAccess() const { return HasParamAccess; } 1313 1314 bool isGlobalValueLive(const GlobalValueSummary *GVS) const { 1315 return !WithGlobalValueDeadStripping || GVS->isLive(); 1316 } 1317 bool isGUIDLive(GlobalValue::GUID GUID) const; 1318 1319 /// Return a ValueInfo for the index value_type (convenient when iterating 1320 /// index). 1321 ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const { 1322 return ValueInfo(HaveGVs, &R); 1323 } 1324 1325 /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo(). 1326 ValueInfo getValueInfo(GlobalValue::GUID GUID) const { 1327 auto I = GlobalValueMap.find(GUID); 1328 return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I); 1329 } 1330 1331 /// Return a ValueInfo for \p GUID. 1332 ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) { 1333 return ValueInfo(HaveGVs, getOrInsertValuePtr(GUID)); 1334 } 1335 1336 // Save a string in the Index. Use before passing Name to 1337 // getOrInsertValueInfo when the string isn't owned elsewhere (e.g. on the 1338 // module's Strtab). 1339 StringRef saveString(StringRef String) { return Saver.save(String); } 1340 1341 /// Return a ValueInfo for \p GUID setting value \p Name. 1342 ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name) { 1343 assert(!HaveGVs); 1344 auto VP = getOrInsertValuePtr(GUID); 1345 VP->second.U.Name = Name; 1346 return ValueInfo(HaveGVs, VP); 1347 } 1348 1349 /// Return a ValueInfo for \p GV and mark it as belonging to GV. 1350 ValueInfo getOrInsertValueInfo(const GlobalValue *GV) { 1351 assert(HaveGVs); 1352 auto VP = getOrInsertValuePtr(GV->getGUID()); 1353 VP->second.U.GV = GV; 1354 return ValueInfo(HaveGVs, VP); 1355 } 1356 1357 /// Return the GUID for \p OriginalId in the OidGuidMap. 1358 GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const { 1359 const auto I = OidGuidMap.find(OriginalID); 1360 return I == OidGuidMap.end() ? 0 : I->second; 1361 } 1362 1363 std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; } 1364 const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; } 1365 1366 std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; } 1367 const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; } 1368 1369 /// Add a global value summary for a value. 1370 void addGlobalValueSummary(const GlobalValue &GV, 1371 std::unique_ptr<GlobalValueSummary> Summary) { 1372 addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary)); 1373 } 1374 1375 /// Add a global value summary for a value of the given name. 1376 void addGlobalValueSummary(StringRef ValueName, 1377 std::unique_ptr<GlobalValueSummary> Summary) { 1378 addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)), 1379 std::move(Summary)); 1380 } 1381 1382 /// Add a global value summary for the given ValueInfo. 1383 void addGlobalValueSummary(ValueInfo VI, 1384 std::unique_ptr<GlobalValueSummary> Summary) { 1385 if (const FunctionSummary *FS = dyn_cast<FunctionSummary>(Summary.get())) 1386 HasParamAccess |= !FS->paramAccesses().empty(); 1387 addOriginalName(VI.getGUID(), Summary->getOriginalName()); 1388 // Here we have a notionally const VI, but the value it points to is owned 1389 // by the non-const *this. 1390 const_cast<GlobalValueSummaryMapTy::value_type *>(VI.getRef()) 1391 ->second.SummaryList.push_back(std::move(Summary)); 1392 } 1393 1394 /// Add an original name for the value of the given GUID. 1395 void addOriginalName(GlobalValue::GUID ValueGUID, 1396 GlobalValue::GUID OrigGUID) { 1397 if (OrigGUID == 0 || ValueGUID == OrigGUID) 1398 return; 1399 if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID) 1400 OidGuidMap[OrigGUID] = 0; 1401 else 1402 OidGuidMap[OrigGUID] = ValueGUID; 1403 } 1404 1405 /// Find the summary for ValueInfo \p VI in module \p ModuleId, or nullptr if 1406 /// not found. 1407 GlobalValueSummary *findSummaryInModule(ValueInfo VI, StringRef ModuleId) const { 1408 auto SummaryList = VI.getSummaryList(); 1409 auto Summary = 1410 llvm::find_if(SummaryList, 1411 [&](const std::unique_ptr<GlobalValueSummary> &Summary) { 1412 return Summary->modulePath() == ModuleId; 1413 }); 1414 if (Summary == SummaryList.end()) 1415 return nullptr; 1416 return Summary->get(); 1417 } 1418 1419 /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if 1420 /// not found. 1421 GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID, 1422 StringRef ModuleId) const { 1423 auto CalleeInfo = getValueInfo(ValueGUID); 1424 if (!CalleeInfo) 1425 return nullptr; // This function does not have a summary 1426 return findSummaryInModule(CalleeInfo, ModuleId); 1427 } 1428 1429 /// Returns the first GlobalValueSummary for \p GV, asserting that there 1430 /// is only one if \p PerModuleIndex. 1431 GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV, 1432 bool PerModuleIndex = true) const { 1433 assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name"); 1434 return getGlobalValueSummary(GV.getGUID(), PerModuleIndex); 1435 } 1436 1437 /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that 1438 /// there 1439 /// is only one if \p PerModuleIndex. 1440 GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID, 1441 bool PerModuleIndex = true) const; 1442 1443 /// Table of modules, containing module hash and id. 1444 const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const { 1445 return ModulePathStringTable; 1446 } 1447 1448 /// Table of modules, containing hash and id. 1449 StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() { 1450 return ModulePathStringTable; 1451 } 1452 1453 /// Get the module ID recorded for the given module path. 1454 uint64_t getModuleId(const StringRef ModPath) const { 1455 return ModulePathStringTable.lookup(ModPath).first; 1456 } 1457 1458 /// Get the module SHA1 hash recorded for the given module path. 1459 const ModuleHash &getModuleHash(const StringRef ModPath) const { 1460 auto It = ModulePathStringTable.find(ModPath); 1461 assert(It != ModulePathStringTable.end() && "Module not registered"); 1462 return It->second.second; 1463 } 1464 1465 /// Convenience method for creating a promoted global name 1466 /// for the given value name of a local, and its original module's ID. 1467 static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) { 1468 SmallString<256> NewName(Name); 1469 NewName += ".llvm."; 1470 NewName += utostr((uint64_t(ModHash[0]) << 32) | 1471 ModHash[1]); // Take the first 64 bits 1472 return std::string(NewName.str()); 1473 } 1474 1475 /// Helper to obtain the unpromoted name for a global value (or the original 1476 /// name if not promoted). Split off the rightmost ".llvm.${hash}" suffix, 1477 /// because it is possible in certain clients (not clang at the moment) for 1478 /// two rounds of ThinLTO optimization and therefore promotion to occur. 1479 static StringRef getOriginalNameBeforePromote(StringRef Name) { 1480 std::pair<StringRef, StringRef> Pair = Name.rsplit(".llvm."); 1481 return Pair.first; 1482 } 1483 1484 typedef ModulePathStringTableTy::value_type ModuleInfo; 1485 1486 /// Add a new module with the given \p Hash, mapped to the given \p 1487 /// ModID, and return a reference to the module. 1488 ModuleInfo *addModule(StringRef ModPath, uint64_t ModId, 1489 ModuleHash Hash = ModuleHash{{0}}) { 1490 return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first; 1491 } 1492 1493 /// Return module entry for module with the given \p ModPath. 1494 ModuleInfo *getModule(StringRef ModPath) { 1495 auto It = ModulePathStringTable.find(ModPath); 1496 assert(It != ModulePathStringTable.end() && "Module not registered"); 1497 return &*It; 1498 } 1499 1500 /// Check if the given Module has any functions available for exporting 1501 /// in the index. We consider any module present in the ModulePathStringTable 1502 /// to have exported functions. 1503 bool hasExportedFunctions(const Module &M) const { 1504 return ModulePathStringTable.count(M.getModuleIdentifier()); 1505 } 1506 1507 const TypeIdSummaryMapTy &typeIds() const { return TypeIdMap; } 1508 1509 /// Return an existing or new TypeIdSummary entry for \p TypeId. 1510 /// This accessor can mutate the map and therefore should not be used in 1511 /// the ThinLTO backends. 1512 TypeIdSummary &getOrInsertTypeIdSummary(StringRef TypeId) { 1513 auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId)); 1514 for (auto It = TidIter.first; It != TidIter.second; ++It) 1515 if (It->second.first == TypeId) 1516 return It->second.second; 1517 auto It = TypeIdMap.insert( 1518 {GlobalValue::getGUID(TypeId), {std::string(TypeId), TypeIdSummary()}}); 1519 return It->second.second; 1520 } 1521 1522 /// This returns either a pointer to the type id summary (if present in the 1523 /// summary map) or null (if not present). This may be used when importing. 1524 const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const { 1525 auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId)); 1526 for (auto It = TidIter.first; It != TidIter.second; ++It) 1527 if (It->second.first == TypeId) 1528 return &It->second.second; 1529 return nullptr; 1530 } 1531 1532 TypeIdSummary *getTypeIdSummary(StringRef TypeId) { 1533 return const_cast<TypeIdSummary *>( 1534 static_cast<const ModuleSummaryIndex *>(this)->getTypeIdSummary( 1535 TypeId)); 1536 } 1537 1538 const auto &typeIdCompatibleVtableMap() const { 1539 return TypeIdCompatibleVtableMap; 1540 } 1541 1542 /// Return an existing or new TypeIdCompatibleVtableMap entry for \p TypeId. 1543 /// This accessor can mutate the map and therefore should not be used in 1544 /// the ThinLTO backends. 1545 TypeIdCompatibleVtableInfo & 1546 getOrInsertTypeIdCompatibleVtableSummary(StringRef TypeId) { 1547 return TypeIdCompatibleVtableMap[std::string(TypeId)]; 1548 } 1549 1550 /// For the given \p TypeId, this returns the TypeIdCompatibleVtableMap 1551 /// entry if present in the summary map. This may be used when importing. 1552 Optional<TypeIdCompatibleVtableInfo> 1553 getTypeIdCompatibleVtableSummary(StringRef TypeId) const { 1554 auto I = TypeIdCompatibleVtableMap.find(TypeId); 1555 if (I == TypeIdCompatibleVtableMap.end()) 1556 return None; 1557 return I->second; 1558 } 1559 1560 /// Collect for the given module the list of functions it defines 1561 /// (GUID -> Summary). 1562 void collectDefinedFunctionsForModule(StringRef ModulePath, 1563 GVSummaryMapTy &GVSummaryMap) const; 1564 1565 /// Collect for each module the list of Summaries it defines (GUID -> 1566 /// Summary). 1567 template <class Map> 1568 void 1569 collectDefinedGVSummariesPerModule(Map &ModuleToDefinedGVSummaries) const { 1570 for (auto &GlobalList : *this) { 1571 auto GUID = GlobalList.first; 1572 for (auto &Summary : GlobalList.second.SummaryList) { 1573 ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get(); 1574 } 1575 } 1576 } 1577 1578 /// Print to an output stream. 1579 void print(raw_ostream &OS, bool IsForDebug = false) const; 1580 1581 /// Dump to stderr (for debugging). 1582 void dump() const; 1583 1584 /// Export summary to dot file for GraphViz. 1585 void 1586 exportToDot(raw_ostream &OS, 1587 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) const; 1588 1589 /// Print out strongly connected components for debugging. 1590 void dumpSCCs(raw_ostream &OS); 1591 1592 /// Do the access attribute and DSOLocal propagation in combined index. 1593 void propagateAttributes(const DenseSet<GlobalValue::GUID> &PreservedSymbols); 1594 1595 /// Checks if we can import global variable from another module. 1596 bool canImportGlobalVar(GlobalValueSummary *S, bool AnalyzeRefs) const; 1597 }; 1598 1599 /// GraphTraits definition to build SCC for the index 1600 template <> struct GraphTraits<ValueInfo> { 1601 typedef ValueInfo NodeRef; 1602 using EdgeRef = FunctionSummary::EdgeTy &; 1603 1604 static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) { 1605 return P.first; 1606 } 1607 using ChildIteratorType = 1608 mapped_iterator<std::vector<FunctionSummary::EdgeTy>::iterator, 1609 decltype(&valueInfoFromEdge)>; 1610 1611 using ChildEdgeIteratorType = std::vector<FunctionSummary::EdgeTy>::iterator; 1612 1613 static NodeRef getEntryNode(ValueInfo V) { return V; } 1614 1615 static ChildIteratorType child_begin(NodeRef N) { 1616 if (!N.getSummaryList().size()) // handle external function 1617 return ChildIteratorType( 1618 FunctionSummary::ExternalNode.CallGraphEdgeList.begin(), 1619 &valueInfoFromEdge); 1620 FunctionSummary *F = 1621 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject()); 1622 return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge); 1623 } 1624 1625 static ChildIteratorType child_end(NodeRef N) { 1626 if (!N.getSummaryList().size()) // handle external function 1627 return ChildIteratorType( 1628 FunctionSummary::ExternalNode.CallGraphEdgeList.end(), 1629 &valueInfoFromEdge); 1630 FunctionSummary *F = 1631 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject()); 1632 return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge); 1633 } 1634 1635 static ChildEdgeIteratorType child_edge_begin(NodeRef N) { 1636 if (!N.getSummaryList().size()) // handle external function 1637 return FunctionSummary::ExternalNode.CallGraphEdgeList.begin(); 1638 1639 FunctionSummary *F = 1640 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject()); 1641 return F->CallGraphEdgeList.begin(); 1642 } 1643 1644 static ChildEdgeIteratorType child_edge_end(NodeRef N) { 1645 if (!N.getSummaryList().size()) // handle external function 1646 return FunctionSummary::ExternalNode.CallGraphEdgeList.end(); 1647 1648 FunctionSummary *F = 1649 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject()); 1650 return F->CallGraphEdgeList.end(); 1651 } 1652 1653 static NodeRef edge_dest(EdgeRef E) { return E.first; } 1654 }; 1655 1656 template <> 1657 struct GraphTraits<ModuleSummaryIndex *> : public GraphTraits<ValueInfo> { 1658 static NodeRef getEntryNode(ModuleSummaryIndex *I) { 1659 std::unique_ptr<GlobalValueSummary> Root = 1660 std::make_unique<FunctionSummary>(I->calculateCallGraphRoot()); 1661 GlobalValueSummaryInfo G(I->haveGVs()); 1662 G.SummaryList.push_back(std::move(Root)); 1663 static auto P = 1664 GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G)); 1665 return ValueInfo(I->haveGVs(), &P); 1666 } 1667 }; 1668 } // end namespace llvm 1669 1670 #endif // LLVM_IR_MODULESUMMARYINDEX_H 1671