LCOV - code coverage report
Current view: top level - include/llvm/IR - ModuleSummaryIndex.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 180 186 96.8 %
Date: 2018-07-13 00:08:38 Functions: 35 39 89.7 %
Legend: Lines: hit not hit

          Line data    Source code
       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        1041 :       : Hotness(static_cast<uint32_t>(Hotness)), RelBlockFreq(RelBF) {}
      76             : 
      77             :   void updateHotness(const HotnessType OtherHotness) {
      78         664 :     Hotness = std::max(Hotness, static_cast<uint32_t>(OtherHotness));
      79             :   }
      80             : 
      81        1028 :   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         274 :   void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq) {
      89         274 :     if (EntryFreq == 0)
      90           0 :       return;
      91             :     using Scaled64 = ScaledNumber<uint64_t>;
      92             :     Scaled64 Temp(BlockFreq, ScaleShift);
      93         274 :     Temp /= Scaled64::get(EntryFreq);
      94             : 
      95             :     uint64_t Sum =
      96         548 :         SaturatingAdd<uint64_t>(Temp.toInt<uint64_t>(), RelBlockFreq);
      97         548 :     Sum = std::min(Sum, uint64_t(MaxRelBlockFreq));
      98         274 :     RelBlockFreq = static_cast<uint32_t>(Sum);
      99             :   }
     100             : };
     101             : 
     102             : class GlobalValueSummary;
     103             : 
     104             : using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>;
     105             : 
     106       12768 : struct GlobalValueSummaryInfo {
     107             :   union NameOrGV {
     108        4274 :     NameOrGV(bool HaveGVs) {
     109        4274 :       if (HaveGVs)
     110        1504 :         GV = nullptr;
     111             :       else
     112        2770 :         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        4274 :   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       99747 :   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        8156 :   GlobalValue::GUID getGUID() const { return getRef()->first; }
     161             :   const GlobalValue *getValue() const {
     162             :     assert(haveGVs());
     163         797 :     return getRef()->second.U.GV;
     164             :   }
     165             : 
     166             :   ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const {
     167             :     return getRef()->second.SummaryList;
     168             :   }
     169             : 
     170        1288 :   StringRef name() const {
     171           0 :     return haveGVs() ? getRef()->second.U.GV->getName()
     172        2576 :                      : 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          19 :   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        1518 :     return L.getRef() == R.getRef();
     227             :   }
     228         548 :   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           2 : 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      100731 :         : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport),
     268      103030 :           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      103030 :       : 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      103029 :   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        1179 :   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        2371 :   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        2085 :   GVFlags flags() const { return Flags; }
     326             : 
     327             :   /// Return linkage type recorded for this global value.
     328             :   GlobalValue::LinkageTypes linkage() const {
     329        5376 :     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         557 :     Flags.Linkage = Linkage;
     336             :   }
     337             : 
     338             :   /// Return true if this global value can't be imported.
     339         289 :   bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
     340             : 
     341        2505 :   bool isLive() const { return Flags.Live; }
     342             : 
     343         827 :   void setLive(bool Live) { Flags.Live = Live; }
     344             : 
     345         197 :   void setDSOLocal(bool Local) { Flags.DSOLocal = Local; }
     346             : 
     347        1718 :   bool isDSOLocal() const { return Flags.DSOLocal; }
     348             : 
     349             :   /// Flag that this global value cannot be imported.
     350          62 :   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        1046 : 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         523 :   AliasSummary(GVFlags Flags)
     372         523 :       : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}),
     373         523 :         AliaseeSummary(nullptr), AliaseeGUID(0) {}
     374             : 
     375             :   /// Check if this is an alias summary.
     376             :   static bool classof(const GlobalValueSummary *GVS) {
     377        4174 :     return GVS->getSummaryKind() == AliasKind;
     378             :   }
     379             : 
     380         523 :   void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
     381         390 :   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         568 :                          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          46 :     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      206345 : 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        1031 :   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        1156 :   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       99744 :   makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) {
     476             :     return FunctionSummary(
     477             :         FunctionSummary::GVFlags(
     478             :             GlobalValue::LinkageTypes::AvailableExternallyLinkage,
     479             :             /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false),
     480       99744 :         0, FunctionSummary::FFlags{}, std::vector<ValueInfo>(),
     481       99744 :         std::move(Edges), std::vector<GlobalValue::GUID>(),
     482       99744 :         std::vector<FunctionSummary::VFuncId>(),
     483       99744 :         std::vector<FunctionSummary::VFuncId>(),
     484       99744 :         std::vector<FunctionSummary::ConstVCall>(),
     485      398976 :         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      102029 :   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      102029 :       : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
     514             :         InstCount(NumInsts), FunFlags(FunFlags),
     515      204058 :         CallGraphEdgeList(std::move(CGEdges)) {
     516      203838 :     if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
     517      305785 :         !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
     518             :         !TypeCheckedLoadConstVCalls.empty())
     519         172 :       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      102029 :   }
     525             : 
     526             :   /// Check if this is a function summary.
     527             :   static bool classof(const GlobalValueSummary *GVS) {
     528        4366 :     return GVS->getSummaryKind() == FunctionKind;
     529             :   }
     530             : 
     531             :   /// Get function attribute flags.
     532        1470 :   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        1639 :     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        1300 :     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        1300 :     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        1300 :     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        1300 :     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           8 :   void addTypeTest(GlobalValue::GUID Guid) {
     587           8 :     if (!TIdInfo)
     588           0 :       TIdInfo = llvm::make_unique<TypeIdInfo>();
     589           8 :     TIdInfo->TypeTests.push_back(Guid);
     590           8 :   }
     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         429 :     return L.GUID == R.GUID && L.Offset == R.Offset;
     606             :   }
     607             : 
     608           8 :   static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
     609             : };
     610             : 
     611             : template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
     612             :   static FunctionSummary::ConstVCall getEmptyKey() {
     613          17 :     return {{0, uint64_t(-1)}, {}};
     614             :   }
     615             : 
     616             :   static FunctionSummary::ConstVCall getTombstoneKey() {
     617          10 :     return {{0, uint64_t(-2)}, {}};
     618             :   }
     619             : 
     620         399 :   static bool isEqual(FunctionSummary::ConstVCall L,
     621             :                       FunctionSummary::ConstVCall R) {
     622         388 :     return DenseMapInfo<FunctionSummary::VFuncId>::isEqual(L.VFunc, R.VFunc) &&
     623         787 :            L.Args == R.Args;
     624             :   }
     625             : 
     626             :   static unsigned getHashValue(FunctionSummary::ConstVCall I) {
     627           4 :     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         956 : class GlobalVarSummary : public GlobalValueSummary {
     638             : 
     639             : public:
     640             :   GlobalVarSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
     641         478 :       : 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         137 : 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         236 : 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         137 : 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        9471 : 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        4247 :   getOrInsertValuePtr(GlobalValue::GUID GUID) {
     790        8494 :     return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs))
     791        4247 :                  .first;
     792             :   }
     793             : 
     794             : public:
     795             :   // See HaveGVs variable comment.
     796        9784 :   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           7 :   static void discoverNodes(ValueInfo V,
     809             :                             std::map<ValueInfo, bool> &FunctionHasParent) {
     810           7 :     if (!V.getSummaryList().size())
     811             :       return; // skip external functions that don't have summaries
     812             : 
     813             :     // Mark discovered if we haven't yet
     814          12 :     auto S = FunctionHasParent.emplace(V, false);
     815             : 
     816             :     // Stop if we've already discovered this node
     817           6 :     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          10 :     for (auto &C : F->calls()) {
     825             :       // Insert node if necessary
     826           8 :       auto S = FunctionHasParent.emplace(C.first, true);
     827             : 
     828             :       // Skip nodes that we're sure have parents
     829           4 :       if (!S.second && S.first->second)
     830             :         continue;
     831             : 
     832           3 :       if (S.second)
     833           3 :         discoverNodes(C.first, FunctionHasParent);
     834             :       else
     835           0 :         S.first->second = true;
     836             :     }
     837             :   }
     838             : 
     839             :   // Calculate the callgraph root
     840           1 :   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           6 :     for (auto &S : *this) {
     847             :       // Skip external functions
     848          14 :       if (!S.second.SummaryList.size() ||
     849             :           !isa<FunctionSummary>(S.second.SummaryList.front().get()))
     850           1 :         continue;
     851           8 :       discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent);
     852             :     }
     853             : 
     854             :     std::vector<FunctionSummary::EdgeTy> Edges;
     855             :     // create edges to all roots in the Index
     856           6 :     for (auto &P : FunctionHasParent) {
     857           5 :       if (P.second)
     858           3 :         continue; // skip over non-root nodes
     859           4 :       Edges.push_back(std::make_pair(P.first, CalleeInfo{}));
     860             :     }
     861           1 :     if (Edges.empty()) {
     862             :       // Failed to find root - return an empty node
     863           0 :       return FunctionSummary::makeDummyFunctionSummary({});
     864             :     }
     865           3 :     auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
     866           1 :     return CallGraphRoot;
     867             :   }
     868             : 
     869             :   bool withGlobalValueDeadStripping() const {
     870             :     return WithGlobalValueDeadStripping;
     871             :   }
     872             :   void setWithGlobalValueDeadStripping() {
     873         450 :     WithGlobalValueDeadStripping = true;
     874             :   }
     875             : 
     876             :   bool skipModuleByDistributedBackend() const {
     877             :     return SkipModuleByDistributedBackend;
     878             :   }
     879             :   void setSkipModuleByDistributedBackend() {
     880           3 :     SkipModuleByDistributedBackend = true;
     881             :   }
     882             : 
     883             :   bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
     884        4173 :     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        7308 :   ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
     896             :     auto I = GlobalValueMap.find(GUID);
     897       21924 :     return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I);
     898             :   }
     899             : 
     900             :   /// Return a ValueInfo for \p GUID.
     901             :   ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) {
     902        1269 :     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          13 :   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        1536 :     auto VP = getOrInsertValuePtr(GUID);
     914        1536 :     VP->second.U.Name = Name;
     915        1536 :     return ValueInfo(HaveGVs, VP);
     916             :   }
     917             : 
     918             :   /// Return a ValueInfo for \p GV and mark it as belonging to GV.
     919        1442 :   ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
     920             :     assert(HaveGVs);
     921        1442 :     auto VP = getOrInsertValuePtr(GV->getGUID());
     922        1442 :     VP->second.U.GV = GV;
     923        2884 :     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          93 :     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         889 :   void addGlobalValueSummary(const GlobalValue &GV,
     940             :                              std::unique_ptr<GlobalValueSummary> Summary) {
     941        1778 :     addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary));
     942         889 :   }
     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        3260 :   void addGlobalValueSummary(ValueInfo VI,
     953             :                              std::unique_ptr<GlobalValueSummary> Summary) {
     954        6520 :     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        3260 :         ->second.SummaryList.push_back(std::move(Summary));
     959        3260 :   }
     960             : 
     961             :   /// Add an original name for the value of the given GUID.
     962        3428 :   void addOriginalName(GlobalValue::GUID ValueGUID,
     963             :                        GlobalValue::GUID OrigGUID) {
     964        3428 :     if (OrigGUID == 0 || ValueGUID == OrigGUID)
     965             :       return;
     966           8 :     if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
     967           0 :       OidGuidMap[OrigGUID] = 0;
     968             :     else
     969         245 :       OidGuidMap[OrigGUID] = ValueGUID;
     970             :   }
     971             : 
     972             :   /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
     973             :   /// not found.
     974         771 :   GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
     975             :                                           StringRef ModuleId) const {
     976         771 :     auto CalleeInfo = getValueInfo(ValueGUID);
     977         771 :     if (!CalleeInfo) {
     978             :       return nullptr; // This function does not have a summary
     979             :     }
     980             :     auto Summary =
     981             :         llvm::find_if(CalleeInfo.getSummaryList(),
     982         728 :                       [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
     983         728 :                         return Summary->modulePath() == ModuleId;
     984         728 :                       });
     985         769 :     if (Summary == CalleeInfo.getSummaryList().end())
     986             :       return nullptr;
     987         682 :     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         256 :     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          96 :     return ModulePathStringTable;
    1007             :   }
    1008             : 
    1009             :   /// Table of modules, containing hash and id.
    1010             :   StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
    1011          85 :     return ModulePathStringTable;
    1012             :   }
    1013             : 
    1014             :   /// Get the module ID recorded for the given module path.
    1015             :   uint64_t getModuleId(const StringRef ModPath) const {
    1016         819 :     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         339 :     auto It = ModulePathStringTable.find(ModPath);
    1022             :     assert(It != ModulePathStringTable.end() && "Module not registered");
    1023         119 :     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         119 :   static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
    1029             :     SmallString<256> NewName(Name);
    1030             :     NewName += ".llvm.";
    1031         238 :     NewName += utostr((uint64_t(ModHash[0]) << 32) |
    1032             :                       ModHash[1]); // Take the first 64 bits
    1033         119 :     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          10 :     std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
    1040          10 :     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         796 :   ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
    1048             :                         ModuleHash Hash = ModuleHash{{0}}) {
    1049        1592 :     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        1169 :     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         342 :   bool hasExportedFunctions(const Module &M) const {
    1063         684 :     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          85 :   TypeIdSummary &getOrInsertTypeIdSummary(StringRef TypeId) {
    1073         170 :     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          73 :   const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const {
    1079          73 :     auto I = TypeIdMap.find(TypeId);
    1080          73 :     if (I == TypeIdMap.end())
    1081             :       return nullptr;
    1082          55 :     return &I->second;
    1083             :   }
    1084             : 
    1085             :   /// Collect for the given module the list of function 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          12 :   static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) {
    1113          12 :     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          10 :     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          17 :     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           1 :   static NodeRef getEntryNode(ModuleSummaryIndex *I) {
    1145             :     std::unique_ptr<GlobalValueSummary> Root =
    1146           2 :         make_unique<FunctionSummary>(I->calculateCallGraphRoot());
    1147           1 :     GlobalValueSummaryInfo G(I->haveGVs());
    1148             :     G.SummaryList.push_back(std::move(Root));
    1149             :     static auto P =
    1150           2 :         GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G));
    1151           3 :     return ValueInfo(I->haveGVs(), &P);
    1152             :   }
    1153             : };
    1154             : 
    1155             : } // end namespace llvm
    1156             : 
    1157             : #endif // LLVM_IR_MODULESUMMARYINDEX_H

Generated by: LCOV version 1.13