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