LCOV - code coverage report
Current view: top level - include/llvm/IR - ModuleSummaryIndex.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 141 145 97.2 %
Date: 2017-09-14 15:23:50 Functions: 26 31 83.9 %
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 <algorithm>
      29             : #include <array>
      30             : #include <cassert>
      31             : #include <cstddef>
      32             : #include <cstdint>
      33             : #include <map>
      34             : #include <memory>
      35             : #include <set>
      36             : #include <string>
      37             : #include <utility>
      38             : #include <vector>
      39             : 
      40             : namespace llvm {
      41             : 
      42             : namespace yaml {
      43             : 
      44             : template <typename T> struct MappingTraits;
      45             : 
      46             : } // end namespace yaml
      47             : 
      48             : /// \brief Class to accumulate and hold information about a callee.
      49             : struct CalleeInfo {
      50             :   enum class HotnessType : uint8_t {
      51             :     Unknown = 0,
      52             :     Cold = 1,
      53             :     None = 2,
      54             :     Hot = 3,
      55             :     Critical = 4
      56             :   };
      57             :   HotnessType Hotness = HotnessType::Unknown;
      58             : 
      59             :   CalleeInfo() = default;
      60             :   explicit CalleeInfo(HotnessType Hotness) : Hotness(Hotness) {}
      61             : 
      62             :   void updateHotness(const HotnessType OtherHotness) {
      63         584 :     Hotness = std::max(Hotness, OtherHotness);
      64             :   }
      65             : };
      66             : 
      67             : class GlobalValueSummary;
      68             : 
      69             : using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>;
      70             : 
      71       20242 : struct GlobalValueSummaryInfo {
      72             :   /// The GlobalValue corresponding to this summary. This is only used in
      73             :   /// per-module summaries.
      74             :   const GlobalValue *GV = nullptr;
      75             : 
      76             :   /// List of global value summary structures for a particular value held
      77             :   /// in the GlobalValueMap. Requires a vector in the case of multiple
      78             :   /// COMDAT values of the same name.
      79             :   GlobalValueSummaryList SummaryList;
      80             : };
      81             : 
      82             : /// Map from global value GUID to corresponding summary structures. Use a
      83             : /// std::map rather than a DenseMap so that pointers to the map's value_type
      84             : /// (which are used by ValueInfo) are not invalidated by insertion. Also it will
      85             : /// likely incur less overhead, as the value type is not very small and the size
      86             : /// of the map is unknown, resulting in inefficiencies due to repeated
      87             : /// insertions and resizing.
      88             : using GlobalValueSummaryMapTy =
      89             :     std::map<GlobalValue::GUID, GlobalValueSummaryInfo>;
      90             : 
      91             : /// Struct that holds a reference to a particular GUID in a global value
      92             : /// summary.
      93             : struct ValueInfo {
      94             :   const GlobalValueSummaryMapTy::value_type *Ref = nullptr;
      95             : 
      96             :   ValueInfo() = default;
      97         219 :   ValueInfo(const GlobalValueSummaryMapTy::value_type *Ref) : Ref(Ref) {}
      98             : 
      99         117 :   operator bool() const { return Ref; }
     100             : 
     101        5998 :   GlobalValue::GUID getGUID() const { return Ref->first; }
     102         641 :   const GlobalValue *getValue() const { return Ref->second.GV; }
     103             : 
     104             :   ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const {
     105        8930 :     return Ref->second.SummaryList;
     106             :   }
     107             : };
     108             : 
     109             : template <> struct DenseMapInfo<ValueInfo> {
     110             :   static inline ValueInfo getEmptyKey() {
     111        1380 :     return ValueInfo((GlobalValueSummaryMapTy::value_type *)-1);
     112             :   }
     113             : 
     114             :   static inline ValueInfo getTombstoneKey() {
     115         702 :     return ValueInfo((GlobalValueSummaryMapTy::value_type *)-2);
     116             :   }
     117             : 
     118        1254 :   static bool isEqual(ValueInfo L, ValueInfo R) { return L.Ref == R.Ref; }
     119         443 :   static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.Ref; }
     120             : };
     121             : 
     122             : /// \brief Function and variable summary information to aid decisions and
     123             : /// implementation of importing.
     124             : class GlobalValueSummary {
     125             : public:
     126             :   /// \brief Sububclass discriminator (for dyn_cast<> et al.)
     127             :   enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
     128             : 
     129             :   /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
     130             :   struct GVFlags {
     131             :     /// \brief The linkage type of the associated global value.
     132             :     ///
     133             :     /// One use is to flag values that have local linkage types and need to
     134             :     /// have module identifier appended before placing into the combined
     135             :     /// index, to disambiguate from other values with the same name.
     136             :     /// In the future this will be used to update and optimize linkage
     137             :     /// types based on global summary-based analysis.
     138             :     unsigned Linkage : 4;
     139             : 
     140             :     /// Indicate if the global value cannot be imported (e.g. it cannot
     141             :     /// be renamed or references something that can't be renamed).
     142             :     unsigned NotEligibleToImport : 1;
     143             : 
     144             :     /// In per-module summary, indicate that the global value must be considered
     145             :     /// a live root for index-based liveness analysis. Used for special LLVM
     146             :     /// values such as llvm.global_ctors that the linker does not know about.
     147             :     ///
     148             :     /// In combined summary, indicate that the global value is live.
     149             :     unsigned Live : 1;
     150             : 
     151             :     /// Convenience Constructors
     152             :     explicit GVFlags(GlobalValue::LinkageTypes Linkage,
     153             :                      bool NotEligibleToImport, bool Live)
     154         752 :         : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport),
     155        2663 :           Live(Live) {}
     156             :   };
     157             : 
     158             : private:
     159             :   /// Kind of summary for use in dyn_cast<> et al.
     160             :   SummaryKind Kind;
     161             : 
     162             :   GVFlags Flags;
     163             : 
     164             :   /// This is the hash of the name of the symbol in the original file. It is
     165             :   /// identical to the GUID for global symbols, but differs for local since the
     166             :   /// GUID includes the module level id in the hash.
     167             :   GlobalValue::GUID OriginalName = 0;
     168             : 
     169             :   /// \brief Path of module IR containing value's definition, used to locate
     170             :   /// module during importing.
     171             :   ///
     172             :   /// This is only used during parsing of the combined index, or when
     173             :   /// parsing the per-module index for creation of the combined summary index,
     174             :   /// not during writing of the per-module index which doesn't contain a
     175             :   /// module path string table.
     176             :   StringRef ModulePath;
     177             : 
     178             :   /// List of values referenced by this global value's definition
     179             :   /// (either by the initializer of a global variable, or referenced
     180             :   /// from within a function). This does not include functions called, which
     181             :   /// are listed in the derived FunctionSummary object.
     182             :   std::vector<ValueInfo> RefEdgeList;
     183             : 
     184        1262 :   bool isLive() const { return Flags.Live; }
     185             : 
     186             : protected:
     187             :   GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
     188        7989 :       : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {
     189             :     assert((K != AliasKind || Refs.empty()) &&
     190             :            "Expect no references for AliasSummary");
     191             :   }
     192             : 
     193             : public:
     194        5300 :   virtual ~GlobalValueSummary() = default;
     195             : 
     196             :   /// Returns the hash of the original name, it is identical to the GUID for
     197             :   /// externally visible symbols, but not for local ones.
     198             :   GlobalValue::GUID getOriginalName() { return OriginalName; }
     199             : 
     200             :   /// Initialize the original name hash in this summary.
     201         896 :   void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
     202             : 
     203             :   /// Which kind of summary subclass this is.
     204             :   SummaryKind getSummaryKind() const { return Kind; }
     205             : 
     206             :   /// Set the path to the module containing this function, for use in
     207             :   /// the combined index.
     208        1911 :   void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
     209             : 
     210             :   /// Get the path to the module containing this function.
     211             :   StringRef modulePath() const { return ModulePath; }
     212             : 
     213             :   /// Get the flags for this GlobalValue (see \p struct GVFlags).
     214        1284 :   GVFlags flags() { return Flags; }
     215             : 
     216             :   /// Return linkage type recorded for this global value.
     217             :   GlobalValue::LinkageTypes linkage() const {
     218        4087 :     return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
     219             :   }
     220             : 
     221             :   /// Sets the linkage to the value determined by global summary-based
     222             :   /// optimization. Will be applied in the ThinLTO backends.
     223             :   void setLinkage(GlobalValue::LinkageTypes Linkage) {
     224         545 :     Flags.Linkage = Linkage;
     225             :   }
     226             : 
     227             :   /// Return true if this global value can't be imported.
     228         210 :   bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
     229             : 
     230         330 :   void setLive(bool Live) { Flags.Live = Live; }
     231             : 
     232             :   /// Flag that this global value cannot be imported.
     233          42 :   void setNotEligibleToImport() { Flags.NotEligibleToImport = true; }
     234             : 
     235             :   /// Return the list of values referenced by this global value definition.
     236        5586 :   ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
     237             : 
     238             :   friend class ModuleSummaryIndex;
     239             :   friend void computeDeadSymbols(class ModuleSummaryIndex &,
     240             :                                  const DenseSet<GlobalValue::GUID> &);
     241             : };
     242             : 
     243             : /// \brief Alias summary information.
     244         954 : class AliasSummary : public GlobalValueSummary {
     245             :   GlobalValueSummary *AliaseeSummary;
     246             : 
     247             : public:
     248         477 :   AliasSummary(GVFlags Flags)
     249        1908 :       : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}) {}
     250             : 
     251             :   /// Check if this is an alias summary.
     252             :   static bool classof(const GlobalValueSummary *GVS) {
     253        1700 :     return GVS->getSummaryKind() == AliasKind;
     254             :   }
     255             : 
     256         477 :   void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
     257             : 
     258             :   const GlobalValueSummary &getAliasee() const {
     259             :     assert(AliaseeSummary && "Unexpected missing aliasee summary");
     260             :     return *AliaseeSummary;
     261             :   }
     262             : 
     263             :   GlobalValueSummary &getAliasee() {
     264             :     return const_cast<GlobalValueSummary &>(
     265         451 :                          static_cast<const AliasSummary *>(this)->getAliasee());
     266             :   }
     267             : };
     268             : 
     269             : /// \brief Function summary information to aid decisions and implementation of
     270             : /// importing.
     271        7168 : class FunctionSummary : public GlobalValueSummary {
     272             : public:
     273             :   /// <CalleeValueInfo, CalleeInfo> call edge pair.
     274             :   using EdgeTy = std::pair<ValueInfo, CalleeInfo>;
     275             : 
     276             :   /// An "identifier" for a virtual function. This contains the type identifier
     277             :   /// represented as a GUID and the offset from the address point to the virtual
     278             :   /// function pointer, where "address point" is as defined in the Itanium ABI:
     279             :   /// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
     280             :   struct VFuncId {
     281             :     GlobalValue::GUID GUID;
     282             :     uint64_t Offset;
     283             :   };
     284             : 
     285             :   /// A specification for a virtual function call with all constant integer
     286             :   /// arguments. This is used to perform virtual constant propagation on the
     287             :   /// summary.
     288        3242 :   struct ConstVCall {
     289             :     VFuncId VFunc;
     290             :     std::vector<uint64_t> Args;
     291             :   };
     292             : 
     293             :   /// Function attribute flags. Used to track if a function accesses memory,
     294             :   /// recurses or aliases.
     295             :   struct FFlags {
     296             :     unsigned ReadNone : 1;
     297             :     unsigned ReadOnly : 1;
     298             :     unsigned NoRecurse : 1;
     299             :     unsigned ReturnDoesNotAlias : 1;
     300             :   };
     301             : 
     302             : private:
     303             :   /// Number of instructions (ignoring debug instructions, e.g.) computed
     304             :   /// during the initial compile step when the summary index is first built.
     305             :   unsigned InstCount;
     306             : 
     307             :   /// Function attribute flags. Used to track if a function accesses memory,
     308             :   /// recurses or aliases.
     309             :   FFlags FunFlags;
     310             : 
     311             :   /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
     312             :   std::vector<EdgeTy> CallGraphEdgeList;
     313             : 
     314             :   /// All type identifier related information. Because these fields are
     315             :   /// relatively uncommon we only allocate space for them if necessary.
     316         854 :   struct TypeIdInfo {
     317             :     /// List of type identifiers used by this function in llvm.type.test
     318             :     /// intrinsics other than by an llvm.assume intrinsic, represented as GUIDs.
     319             :     std::vector<GlobalValue::GUID> TypeTests;
     320             : 
     321             :     /// List of virtual calls made by this function using (respectively)
     322             :     /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do
     323             :     /// not have all constant integer arguments.
     324             :     std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
     325             : 
     326             :     /// List of virtual calls made by this function using (respectively)
     327             :     /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with
     328             :     /// all constant integer arguments.
     329             :     std::vector<ConstVCall> TypeTestAssumeConstVCalls,
     330             :         TypeCheckedLoadConstVCalls;
     331             :   };
     332             : 
     333             :   std::unique_ptr<TypeIdInfo> TIdInfo;
     334             : 
     335             : public:
     336        1805 :   FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
     337             :                   std::vector<ValueInfo> Refs, std::vector<EdgeTy> CGEdges,
     338             :                   std::vector<GlobalValue::GUID> TypeTests,
     339             :                   std::vector<VFuncId> TypeTestAssumeVCalls,
     340             :                   std::vector<VFuncId> TypeCheckedLoadVCalls,
     341             :                   std::vector<ConstVCall> TypeTestAssumeConstVCalls,
     342             :                   std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
     343        3610 :       : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
     344             :         InstCount(NumInsts), FunFlags(FunFlags),
     345        7220 :         CallGraphEdgeList(std::move(CGEdges)) {
     346        5328 :     if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
     347        7061 :         !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
     348        1746 :         !TypeCheckedLoadConstVCalls.empty())
     349         366 :       TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
     350         122 :           std::move(TypeTests), std::move(TypeTestAssumeVCalls),
     351          61 :           std::move(TypeCheckedLoadVCalls),
     352          61 :           std::move(TypeTestAssumeConstVCalls),
     353          61 :           std::move(TypeCheckedLoadConstVCalls)});
     354        1805 :   }
     355             : 
     356             :   /// Check if this is a function summary.
     357             :   static bool classof(const GlobalValueSummary *GVS) {
     358        1173 :     return GVS->getSummaryKind() == FunctionKind;
     359             :   }
     360             : 
     361             :   /// Get function attribute flags.
     362             :   FFlags &fflags() { return FunFlags; }
     363             : 
     364             :   /// Get the instruction count recorded for this function.
     365             :   unsigned instCount() const { return InstCount; }
     366             : 
     367             :   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
     368        7332 :   ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
     369             : 
     370             :   /// Returns the list of type identifiers used by this function in
     371             :   /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
     372             :   /// represented as GUIDs.
     373             :   ArrayRef<GlobalValue::GUID> type_tests() const {
     374        2068 :     if (TIdInfo)
     375         261 :       return TIdInfo->TypeTests;
     376             :     return {};
     377             :   }
     378             : 
     379             :   /// Returns the list of virtual calls made by this function using
     380             :   /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
     381             :   /// integer arguments.
     382             :   ArrayRef<VFuncId> type_test_assume_vcalls() const {
     383        1988 :     if (TIdInfo)
     384         240 :       return TIdInfo->TypeTestAssumeVCalls;
     385             :     return {};
     386             :   }
     387             : 
     388             :   /// Returns the list of virtual calls made by this function using
     389             :   /// llvm.type.checked.load intrinsics that do not have all constant integer
     390             :   /// arguments.
     391             :   ArrayRef<VFuncId> type_checked_load_vcalls() const {
     392        1988 :     if (TIdInfo)
     393         240 :       return TIdInfo->TypeCheckedLoadVCalls;
     394             :     return {};
     395             :   }
     396             : 
     397             :   /// Returns the list of virtual calls made by this function using
     398             :   /// llvm.assume(llvm.type.test) intrinsics with all constant integer
     399             :   /// arguments.
     400             :   ArrayRef<ConstVCall> type_test_assume_const_vcalls() const {
     401        1988 :     if (TIdInfo)
     402         240 :       return TIdInfo->TypeTestAssumeConstVCalls;
     403             :     return {};
     404             :   }
     405             : 
     406             :   /// Returns the list of virtual calls made by this function using
     407             :   /// llvm.type.checked.load intrinsics with all constant integer arguments.
     408             :   ArrayRef<ConstVCall> type_checked_load_const_vcalls() const {
     409        1988 :     if (TIdInfo)
     410         240 :       return TIdInfo->TypeCheckedLoadConstVCalls;
     411             :     return {};
     412             :   }
     413             : 
     414             :   /// Add a type test to the summary. This is used by WholeProgramDevirt if we
     415             :   /// were unable to devirtualize a checked call.
     416           2 :   void addTypeTest(GlobalValue::GUID Guid) {
     417           4 :     if (!TIdInfo)
     418           0 :       TIdInfo = llvm::make_unique<TypeIdInfo>();
     419           4 :     TIdInfo->TypeTests.push_back(Guid);
     420           2 :   }
     421             : };
     422             : 
     423             : template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
     424             :   static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
     425             : 
     426             :   static FunctionSummary::VFuncId getTombstoneKey() {
     427             :     return {0, uint64_t(-2)};
     428             :   }
     429             : 
     430             :   static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R) {
     431         411 :     return L.GUID == R.GUID && L.Offset == R.Offset;
     432             :   }
     433             : 
     434           4 :   static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
     435             : };
     436             : 
     437             : template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
     438             :   static FunctionSummary::ConstVCall getEmptyKey() {
     439          34 :     return {{0, uint64_t(-1)}, {}};
     440             :   }
     441             : 
     442             :   static FunctionSummary::ConstVCall getTombstoneKey() {
     443          20 :     return {{0, uint64_t(-2)}, {}};
     444             :   }
     445             : 
     446         399 :   static bool isEqual(FunctionSummary::ConstVCall L,
     447             :                       FunctionSummary::ConstVCall R) {
     448         388 :     return DenseMapInfo<FunctionSummary::VFuncId>::isEqual(L.VFunc, R.VFunc) &&
     449         787 :            L.Args == R.Args;
     450             :   }
     451             : 
     452             :   static unsigned getHashValue(FunctionSummary::ConstVCall I) {
     453           4 :     return I.VFunc.GUID;
     454             :   }
     455             : };
     456             : 
     457             : /// \brief Global variable summary information to aid decisions and
     458             : /// implementation of importing.
     459             : ///
     460             : /// Currently this doesn't add anything to the base \p GlobalValueSummary,
     461             : /// but is a placeholder as additional info may be added to the summary
     462             : /// for variables.
     463         762 : class GlobalVarSummary : public GlobalValueSummary {
     464             : 
     465             : public:
     466             :   GlobalVarSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
     467        1524 :       : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)) {}
     468             : 
     469             :   /// Check if this is a global variable summary.
     470             :   static bool classof(const GlobalValueSummary *GVS) {
     471         447 :     return GVS->getSummaryKind() == GlobalVarKind;
     472             :   }
     473             : };
     474             : 
     475          86 : struct TypeTestResolution {
     476             :   /// Specifies which kind of type check we should emit for this byte array.
     477             :   /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
     478             :   /// details on each kind of check; the enumerators are described with
     479             :   /// reference to that document.
     480             :   enum Kind {
     481             :     Unsat,     ///< Unsatisfiable type (i.e. no global has this type metadata)
     482             :     ByteArray, ///< Test a byte array (first example)
     483             :     Inline,    ///< Inlined bit vector ("Short Inline Bit Vectors")
     484             :     Single,    ///< Single element (last example in "Short Inline Bit Vectors")
     485             :     AllOnes,   ///< All-ones bit vector ("Eliminating Bit Vector Checks for
     486             :                ///  All-Ones Bit Vectors")
     487             :   } TheKind = Unsat;
     488             : 
     489             :   /// Range of size-1 expressed as a bit width. For example, if the size is in
     490             :   /// range [1,256], this number will be 8. This helps generate the most compact
     491             :   /// instruction sequences.
     492             :   unsigned SizeM1BitWidth = 0;
     493             : 
     494             :   // The following fields are only used if the target does not support the use
     495             :   // of absolute symbols to store constants. Their meanings are the same as the
     496             :   // corresponding fields in LowerTypeTestsModule::TypeIdLowering in
     497             :   // LowerTypeTests.cpp.
     498             : 
     499             :   uint64_t AlignLog2 = 0;
     500             :   uint64_t SizeM1 = 0;
     501             :   uint8_t BitMask = 0;
     502             :   uint64_t InlineBits = 0;
     503             : };
     504             : 
     505         198 : struct WholeProgramDevirtResolution {
     506             :   enum Kind {
     507             :     Indir,      ///< Just do a regular virtual call
     508             :     SingleImpl, ///< Single implementation devirtualization
     509             :   } TheKind = Indir;
     510             : 
     511             :   std::string SingleImplName;
     512             : 
     513             :   struct ByArg {
     514             :     enum Kind {
     515             :       Indir,            ///< Just do a regular virtual call
     516             :       UniformRetVal,    ///< Uniform return value optimization
     517             :       UniqueRetVal,     ///< Unique return value optimization
     518             :       VirtualConstProp, ///< Virtual constant propagation
     519             :     } TheKind = Indir;
     520             : 
     521             :     /// Additional information for the resolution:
     522             :     /// - UniformRetVal: the uniform return value.
     523             :     /// - UniqueRetVal: the return value associated with the unique vtable (0 or
     524             :     ///   1).
     525             :     uint64_t Info = 0;
     526             : 
     527             :     // The following fields are only used if the target does not support the use
     528             :     // of absolute symbols to store constants.
     529             : 
     530             :     uint32_t Byte = 0;
     531             :     uint32_t Bit = 0;
     532             :   };
     533             : 
     534             :   /// Resolutions for calls with all constant integer arguments (excluding the
     535             :   /// first argument, "this"), where the key is the argument vector.
     536             :   std::map<std::vector<uint64_t>, ByArg> ResByArg;
     537             : };
     538             : 
     539         430 : struct TypeIdSummary {
     540             :   TypeTestResolution TTRes;
     541             : 
     542             :   /// Mapping from byte offset to whole-program devirt resolution for that
     543             :   /// (typeid, byte offset) pair.
     544             :   std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
     545             : };
     546             : 
     547             : /// 160 bits SHA1
     548             : using ModuleHash = std::array<uint32_t, 5>;
     549             : 
     550             : /// Type used for iterating through the global value summary map.
     551             : using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
     552             : using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
     553             : 
     554             : /// String table to hold/own module path strings, which additionally holds the
     555             : /// module ID assigned to each module during the plugin step, as well as a hash
     556             : /// of the module. The StringMap makes a copy of and owns inserted strings.
     557             : using ModulePathStringTableTy = StringMap<std::pair<uint64_t, ModuleHash>>;
     558             : 
     559             : /// Map of global value GUID to its summary, used to identify values defined in
     560             : /// a particular module, and provide efficient access to their summary.
     561             : using GVSummaryMapTy = DenseMap<GlobalValue::GUID, GlobalValueSummary *>;
     562             : 
     563             : /// Class to hold module path string table and global value map,
     564             : /// and encapsulate methods for operating on them.
     565       15499 : class ModuleSummaryIndex {
     566             : private:
     567             :   /// Map from value name to list of summary instances for values of that
     568             :   /// name (may be duplicates in the COMDAT case, e.g.).
     569             :   GlobalValueSummaryMapTy GlobalValueMap;
     570             : 
     571             :   /// Holds strings for combined index, mapping to the corresponding module ID.
     572             :   ModulePathStringTableTy ModulePathStringTable;
     573             : 
     574             :   /// Mapping from type identifiers to summary information for that type
     575             :   /// identifier.
     576             :   // FIXME: Add bitcode read/write support for this field.
     577             :   std::map<std::string, TypeIdSummary> TypeIdMap;
     578             : 
     579             :   /// Mapping from original ID to GUID. If original ID can map to multiple
     580             :   /// GUIDs, it will be mapped to 0.
     581             :   std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
     582             : 
     583             :   /// Indicates that summary-based GlobalValue GC has run, and values with
     584             :   /// GVFlags::Live==false are really dead. Otherwise, all values must be
     585             :   /// considered live.
     586             :   bool WithGlobalValueDeadStripping = false;
     587             : 
     588             :   std::set<std::string> CfiFunctionDefs;
     589             :   std::set<std::string> CfiFunctionDecls;
     590             : 
     591             :   // YAML I/O support.
     592             :   friend yaml::MappingTraits<ModuleSummaryIndex>;
     593             : 
     594             :   GlobalValueSummaryMapTy::value_type *
     595        3367 :   getOrInsertValuePtr(GlobalValue::GUID GUID) {
     596       16835 :     return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo{}).first;
     597             :   }
     598             : 
     599             : public:
     600        2698 :   gvsummary_iterator begin() { return GlobalValueMap.begin(); }
     601        2080 :   const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
     602        2698 :   gvsummary_iterator end() { return GlobalValueMap.end(); }
     603        2080 :   const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
     604         668 :   size_t size() const { return GlobalValueMap.size(); }
     605             : 
     606             :   bool withGlobalValueDeadStripping() const {
     607             :     return WithGlobalValueDeadStripping;
     608             :   }
     609             :   void setWithGlobalValueDeadStripping() {
     610         334 :     WithGlobalValueDeadStripping = true;
     611             :   }
     612             : 
     613             :   bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
     614        1810 :     return !WithGlobalValueDeadStripping || GVS->isLive();
     615             :   }
     616             :   bool isGUIDLive(GlobalValue::GUID GUID) const;
     617             : 
     618             :   /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
     619             :   ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
     620        7866 :     auto I = GlobalValueMap.find(GUID);
     621        9810 :     return ValueInfo(I == GlobalValueMap.end() ? nullptr : &*I);
     622             :   }
     623             : 
     624             :   /// Return a ValueInfo for \p GUID.
     625             :   ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) {
     626        2930 :     return ValueInfo(getOrInsertValuePtr(GUID));
     627             :   }
     628             : 
     629             :   /// Return a ValueInfo for \p GV and mark it as belonging to GV.
     630         437 :   ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
     631         437 :     auto VP = getOrInsertValuePtr(GV->getGUID());
     632         437 :     VP->second.GV = GV;
     633         437 :     return ValueInfo(VP);
     634             :   }
     635             : 
     636             :   /// Return the GUID for \p OriginalId in the OidGuidMap.
     637             :   GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const {
     638         130 :     const auto I = OidGuidMap.find(OriginalID);
     639         138 :     return I == OidGuidMap.end() ? 0 : I->second;
     640             :   }
     641             : 
     642           0 :   std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; }
     643             :   const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; }
     644             : 
     645           0 :   std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; }
     646             :   const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; }
     647             : 
     648             :   /// Add a global value summary for a value of the given name.
     649         734 :   void addGlobalValueSummary(StringRef ValueName,
     650             :                              std::unique_ptr<GlobalValueSummary> Summary) {
     651        2936 :     addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
     652         734 :                           std::move(Summary));
     653         734 :   }
     654             : 
     655             :   /// Add a global value summary for the given ValueInfo.
     656        2645 :   void addGlobalValueSummary(ValueInfo VI,
     657             :                              std::unique_ptr<GlobalValueSummary> Summary) {
     658        5290 :     addOriginalName(VI.getGUID(), Summary->getOriginalName());
     659             :     // Here we have a notionally const VI, but the value it points to is owned
     660             :     // by the non-const *this.
     661             :     const_cast<GlobalValueSummaryMapTy::value_type *>(VI.Ref)
     662        5290 :         ->second.SummaryList.push_back(std::move(Summary));
     663        2645 :   }
     664             : 
     665             :   /// Add an original name for the value of the given GUID.
     666        2813 :   void addOriginalName(GlobalValue::GUID ValueGUID,
     667             :                        GlobalValue::GUID OrigGUID) {
     668        2813 :     if (OrigGUID == 0 || ValueGUID == OrigGUID)
     669             :       return;
     670         242 :     if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
     671           0 :       OidGuidMap[OrigGUID] = 0;
     672             :     else
     673         238 :       OidGuidMap[OrigGUID] = ValueGUID;
     674             :   }
     675             : 
     676             :   /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
     677             :   /// not found.
     678         448 :   GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
     679             :                                           StringRef ModuleId) const {
     680         448 :     auto CalleeInfo = getValueInfo(ValueGUID);
     681         448 :     if (!CalleeInfo) {
     682             :       return nullptr; // This function does not have a summary
     683             :     }
     684             :     auto Summary =
     685        1344 :         llvm::find_if(CalleeInfo.getSummaryList(),
     686         464 :                       [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
     687         928 :                         return Summary->modulePath() == ModuleId;
     688         912 :                       });
     689         448 :     if (Summary == CalleeInfo.getSummaryList().end())
     690             :       return nullptr;
     691         448 :     return Summary->get();
     692             :   }
     693             : 
     694             :   /// Returns the first GlobalValueSummary for \p GV, asserting that there
     695             :   /// is only one if \p PerModuleIndex.
     696         225 :   GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
     697             :                                             bool PerModuleIndex = true) const {
     698             :     assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
     699         225 :     return getGlobalValueSummary(GlobalValue::getGUID(GV.getName()),
     700         225 :                                  PerModuleIndex);
     701             :   }
     702             : 
     703             :   /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
     704             :   /// there
     705             :   /// is only one if \p PerModuleIndex.
     706             :   GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
     707             :                                             bool PerModuleIndex = true) const;
     708             : 
     709             :   /// Table of modules, containing module hash and id.
     710             :   const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
     711          41 :     return ModulePathStringTable;
     712             :   }
     713             : 
     714             :   /// Table of modules, containing hash and id.
     715             :   StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
     716          54 :     return ModulePathStringTable;
     717             :   }
     718             : 
     719             :   /// Get the module ID recorded for the given module path.
     720             :   uint64_t getModuleId(const StringRef ModPath) const {
     721         548 :     return ModulePathStringTable.lookup(ModPath).first;
     722             :   }
     723             : 
     724             :   /// Get the module SHA1 hash recorded for the given module path.
     725             :   const ModuleHash &getModuleHash(const StringRef ModPath) const {
     726         236 :     auto It = ModulePathStringTable.find(ModPath);
     727             :     assert(It != ModulePathStringTable.end() && "Module not registered");
     728         236 :     return It->second.second;
     729             :   }
     730             : 
     731             :   /// Convenience method for creating a promoted global name
     732             :   /// for the given value name of a local, and its original module's ID.
     733         107 :   static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
     734         214 :     SmallString<256> NewName(Name);
     735         214 :     NewName += ".llvm.";
     736         428 :     NewName += utohexstr(ModHash[0]); // Take the first 32 bits
     737         321 :     return NewName.str();
     738             :   }
     739             : 
     740             :   /// Helper to obtain the unpromoted name for a global value (or the original
     741             :   /// name if not promoted).
     742             :   static StringRef getOriginalNameBeforePromote(StringRef Name) {
     743           6 :     std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
     744           6 :     return Pair.first;
     745             :   }
     746             : 
     747             :   typedef ModulePathStringTableTy::value_type ModuleInfo;
     748             : 
     749             :   /// Add a new module with the given \p Hash, mapped to the given \p
     750             :   /// ModID, and return a reference to the module.
     751        1025 :   ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
     752             :                         ModuleHash Hash = ModuleHash{{0}}) {
     753        5125 :     return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first;
     754             :   }
     755             : 
     756             :   /// Check if the given Module has any functions available for exporting
     757             :   /// in the index. We consider any module present in the ModulePathStringTable
     758             :   /// to have exported functions.
     759         257 :   bool hasExportedFunctions(const Module &M) const {
     760        1028 :     return ModulePathStringTable.count(M.getModuleIdentifier());
     761             :   }
     762             : 
     763             :   const std::map<std::string, TypeIdSummary> &typeIds() const {
     764             :     return TypeIdMap;
     765             :   }
     766             : 
     767             :   /// This accessor should only be used when exporting because it can mutate the
     768             :   /// map.
     769          40 :   TypeIdSummary &getOrInsertTypeIdSummary(StringRef TypeId) {
     770          80 :     return TypeIdMap[TypeId];
     771             :   }
     772             : 
     773             :   /// This returns either a pointer to the type id summary (if present in the
     774             :   /// summary map) or null (if not present). This may be used when importing.
     775          58 :   const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const {
     776         232 :     auto I = TypeIdMap.find(TypeId);
     777         116 :     if (I == TypeIdMap.end())
     778             :       return nullptr;
     779          42 :     return &I->second;
     780             :   }
     781             : 
     782             :   /// Collect for the given module the list of function it defines
     783             :   /// (GUID -> Summary).
     784             :   void collectDefinedFunctionsForModule(StringRef ModulePath,
     785             :                                         GVSummaryMapTy &GVSummaryMap) const;
     786             : 
     787             :   /// Collect for each module the list of Summaries it defines (GUID ->
     788             :   /// Summary).
     789             :   void collectDefinedGVSummariesPerModule(
     790             :       StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const;
     791             : };
     792             : 
     793             : } // end namespace llvm
     794             : 
     795             : #endif // LLVM_IR_MODULESUMMARYINDEX_H

Generated by: LCOV version 1.13