include/llvm/IR/ModuleSummaryIndex.h

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