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