contrib/llvm-project/llvm/include/llvm/IR/ModuleSummaryIndex.h

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