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

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