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

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