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 /// \brief Class to accumulate and hold information about a callee.
  32 struct CalleeInfo {
  33   enum class HotnessType : uint8_t { Unknown = 0, Cold = 1, None = 2, Hot = 3 };
  34   HotnessType Hotness = HotnessType::Unknown;
  35
  36   CalleeInfo() = default;
  37   explicit CalleeInfo(HotnessType Hotness) : Hotness(Hotness) {}
  38
  39   void updateHotness(const HotnessType OtherHotness) {
  40     Hotness = std::max(Hotness, OtherHotness);
  41   }
  42 };
  43
  44 /// Struct to hold value either by GUID or GlobalValue*. Values in combined
  45 /// indexes as well as indirect calls are GUIDs, all others are GlobalValues.
  46 struct ValueInfo {
  47   /// The value representation used in this instance.
  48   enum ValueInfoKind {
  49     VI_GUID,
  50     VI_Value,
  51   };
  52
  53   /// Union of the two possible value types.
  54   union ValueUnion {
  55     GlobalValue::GUID Id;
  56     const GlobalValue *GV;
  57     ValueUnion(GlobalValue::GUID Id) : Id(Id) {}
  58     ValueUnion(const GlobalValue *GV) : GV(GV) {}
  59   };
  60
  61   /// The value being represented.
  62   ValueUnion TheValue;
  63   /// The value representation.
  64   ValueInfoKind Kind;
  65   /// Constructor for a GUID value
  66   ValueInfo(GlobalValue::GUID Id = 0) : TheValue(Id), Kind(VI_GUID) {}
  67   /// Constructor for a GlobalValue* value
  68   ValueInfo(const GlobalValue *V) : TheValue(V), Kind(VI_Value) {}
  69   /// Accessor for GUID value
  70   GlobalValue::GUID getGUID() const {
  71     assert(Kind == VI_GUID && "Not a GUID type");
  72     return TheValue.Id;
  73   }
  74   /// Accessor for GlobalValue* value
  75   const GlobalValue *getValue() const {
  76     assert(Kind == VI_Value && "Not a Value type");
  77     return TheValue.GV;
  78   }
  79   bool isGUID() const { return Kind == VI_GUID; }
  80 };
  81
  82 template <> struct DenseMapInfo<ValueInfo> {
  83   static inline ValueInfo getEmptyKey() { return ValueInfo((GlobalValue *)-1); }
  84   static inline ValueInfo getTombstoneKey() {
  85     return ValueInfo((GlobalValue *)-2);
  86   }
  87   static bool isEqual(ValueInfo L, ValueInfo R) {
  88     if (L.isGUID() != R.isGUID())
  89       return false;
  90     return L.isGUID() ? (L.getGUID() == R.getGUID())
  91                       : (L.getValue() == R.getValue());
  92   }
  93   static unsigned getHashValue(ValueInfo I) {
  94     return I.isGUID() ? I.getGUID() : (uintptr_t)I.getValue();
  95   }
  96 };
  97
  98 /// \brief Function and variable summary information to aid decisions and
  99 /// implementation of importing.
 100 class GlobalValueSummary {
 101 public:
 102   /// \brief Sububclass discriminator (for dyn_cast<> et al.)
 103   enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
 104
 105   /// Group flags (Linkage, noRename, isOptSize, etc.) as a bitfield.
 106   struct GVFlags {
 107     /// \brief The linkage type of the associated global value.
 108     ///
 109     /// One use is to flag values that have local linkage types and need to
 110     /// have module identifier appended before placing into the combined
 111     /// index, to disambiguate from other values with the same name.
 112     /// In the future this will be used to update and optimize linkage
 113     /// types based on global summary-based analysis.
 114     unsigned Linkage : 4;
 115
 116     /// Indicate if the global value cannot be renamed (in a specific section,
 117     /// possibly referenced from inline assembly, etc).
 118     unsigned NoRename : 1;
 119
 120     /// Indicate if a function contains inline assembly (which is opaque),
 121     /// that may reference a local value. This is used to prevent importing
 122     /// of this function, since we can't promote and rename the uses of the
 123     /// local in the inline assembly. Use a flag rather than bloating the
 124     /// summary with references to every possible local value in the
 125     /// llvm.used set.
 126     unsigned HasInlineAsmMaybeReferencingInternal : 1;
 127
 128     /// Indicate if the function is not viable to inline.
 129     unsigned IsNotViableToInline : 1;
 130
 131     /// Convenience Constructors
 132     explicit GVFlags(GlobalValue::LinkageTypes Linkage, bool NoRename,
 133                      bool HasInlineAsmMaybeReferencingInternal,
 134                      bool IsNotViableToInline)
 135         : Linkage(Linkage), NoRename(NoRename),
 136           HasInlineAsmMaybeReferencingInternal(
 137               HasInlineAsmMaybeReferencingInternal),
 138           IsNotViableToInline(IsNotViableToInline) {}
 139
 140     GVFlags(const GlobalValue &GV)
 141         : Linkage(GV.getLinkage()), NoRename(GV.hasSection()),
 142           HasInlineAsmMaybeReferencingInternal(false) {
 143       IsNotViableToInline = false;
 144       if (const auto *F = dyn_cast<Function>(&GV))
 145         // Inliner doesn't handle variadic functions.
 146         // FIXME: refactor this to use the same code that inliner is using.
 147         IsNotViableToInline = F->isVarArg();
 148     }
 149   };
 150
 151 private:
 152   /// Kind of summary for use in dyn_cast<> et al.
 153   SummaryKind Kind;
 154
 155   GVFlags Flags;
 156
 157   /// This is the hash of the name of the symbol in the original file. It is
 158   /// identical to the GUID for global symbols, but differs for local since the
 159   /// GUID includes the module level id in the hash.
 160   GlobalValue::GUID OriginalName;
 161
 162   /// \brief Path of module IR containing value's definition, used to locate
 163   /// module during importing.
 164   ///
 165   /// This is only used during parsing of the combined index, or when
 166   /// parsing the per-module index for creation of the combined summary index,
 167   /// not during writing of the per-module index which doesn't contain a
 168   /// module path string table.
 169   StringRef ModulePath;
 170
 171   /// List of values referenced by this global value's definition
 172   /// (either by the initializer of a global variable, or referenced
 173   /// from within a function). This does not include functions called, which
 174   /// are listed in the derived FunctionSummary object.
 175   std::vector<ValueInfo> RefEdgeList;
 176
 177 protected:
 178   /// GlobalValueSummary constructor.
 179   GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
 180       : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {}
 181
 182 public:
 183   virtual ~GlobalValueSummary() = default;
 184
 185   /// Returns the hash of the original name, it is identical to the GUID for
 186   /// externally visible symbols, but not for local ones.
 187   GlobalValue::GUID getOriginalName() { return OriginalName; }
 188
 189   /// Initialize the original name hash in this summary.
 190   void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
 191
 192   /// Which kind of summary subclass this is.
 193   SummaryKind getSummaryKind() const { return Kind; }
 194
 195   /// Set the path to the module containing this function, for use in
 196   /// the combined index.
 197   void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
 198
 199   /// Get the path to the module containing this function.
 200   StringRef modulePath() const { return ModulePath; }
 201
 202   /// Get the flags for this GlobalValue (see \p struct GVFlags).
 203   GVFlags flags() { return Flags; }
 204
 205   /// Return linkage type recorded for this global value.
 206   GlobalValue::LinkageTypes linkage() const {
 207     return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
 208   }
 209
 210   /// Sets the linkage to the value determined by global summary-based
 211   /// optimization. Will be applied in the ThinLTO backends.
 212   void setLinkage(GlobalValue::LinkageTypes Linkage) {
 213     Flags.Linkage = Linkage;
 214   }
 215
 216   bool isNotViableToInline() const { return Flags.IsNotViableToInline; }
 217
 218   /// Return true if this summary is for a GlobalValue that needs promotion
 219   /// to be referenced from another module.
 220   bool needsRenaming() const { return GlobalValue::isLocalLinkage(linkage()); }
 221
 222   /// Return true if this global value cannot be renamed (in a specific section,
 223   /// possibly referenced from inline assembly, etc).
 224   bool noRename() const { return Flags.NoRename; }
 225
 226   /// Flag that this global value cannot be renamed (in a specific section,
 227   /// possibly referenced from inline assembly, etc).
 228   void setNoRename() { Flags.NoRename = true; }
 229
 230   /// Return true if this global value possibly references another value
 231   /// that can't be renamed.
 232   bool hasInlineAsmMaybeReferencingInternal() const {
 233     return Flags.HasInlineAsmMaybeReferencingInternal;
 234   }
 235
 236   /// Flag that this global value possibly references another value that
 237   /// can't be renamed.
 238   void setHasInlineAsmMaybeReferencingInternal() {
 239     Flags.HasInlineAsmMaybeReferencingInternal = true;
 240   }
 241
 242   /// Return the list of values referenced by this global value definition.
 243   ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
 244 };
 245
 246 /// \brief Alias summary information.
 247 class AliasSummary : public GlobalValueSummary {
 248   GlobalValueSummary *AliaseeSummary;
 249
 250 public:
 251   /// Summary constructors.
 252   AliasSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
 253       : GlobalValueSummary(AliasKind, Flags, std::move(Refs)) {}
 254
 255   /// Check if this is an alias summary.
 256   static bool classof(const GlobalValueSummary *GVS) {
 257     return GVS->getSummaryKind() == AliasKind;
 258   }
 259
 260   void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
 261
 262   const GlobalValueSummary &getAliasee() const {
 263     return const_cast<AliasSummary *>(this)->getAliasee();
 264   }
 265
 266   GlobalValueSummary &getAliasee() {
 267     assert(AliaseeSummary && "Unexpected missing aliasee summary");
 268     return *AliaseeSummary;
 269   }
 270 };
 271
 272 /// \brief Function summary information to aid decisions and implementation of
 273 /// importing.
 274 class FunctionSummary : public GlobalValueSummary {
 275 public:
 276   /// <CalleeValueInfo, CalleeInfo> call edge pair.
 277   typedef std::pair<ValueInfo, CalleeInfo> EdgeTy;
 278
 279 private:
 280   /// Number of instructions (ignoring debug instructions, e.g.) computed
 281   /// during the initial compile step when the summary index is first built.
 282   unsigned InstCount;
 283
 284   /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
 285   std::vector<EdgeTy> CallGraphEdgeList;
 286
 287   /// List of type identifiers used by this function, represented as GUIDs.
 288   std::vector<GlobalValue::GUID> TypeIdList;
 289
 290 public:
 291   /// Summary constructors.
 292   FunctionSummary(GVFlags Flags, unsigned NumInsts, std::vector<ValueInfo> Refs,
 293                   std::vector<EdgeTy> CGEdges,
 294                   std::vector<GlobalValue::GUID> TypeIds)
 295       : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
 296         InstCount(NumInsts), CallGraphEdgeList(std::move(CGEdges)),
 297         TypeIdList(std::move(TypeIds)) {}
 298
 299   /// Check if this is a function summary.
 300   static bool classof(const GlobalValueSummary *GVS) {
 301     return GVS->getSummaryKind() == FunctionKind;
 302   }
 303
 304   /// Get the instruction count recorded for this function.
 305   unsigned instCount() const { return InstCount; }
 306
 307   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
 308   ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
 309
 310   /// Returns the list of type identifiers used by this function.
 311   ArrayRef<GlobalValue::GUID> type_tests() const { return TypeIdList; }
 312 };
 313
 314 /// \brief Global variable summary information to aid decisions and
 315 /// implementation of importing.
 316 ///
 317 /// Currently this doesn't add anything to the base \p GlobalValueSummary,
 318 /// but is a placeholder as additional info may be added to the summary
 319 /// for variables.
 320 class GlobalVarSummary : public GlobalValueSummary {
 321
 322 public:
 323   /// Summary constructors.
 324   GlobalVarSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
 325       : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)) {}
 326
 327   /// Check if this is a global variable summary.
 328   static bool classof(const GlobalValueSummary *GVS) {
 329     return GVS->getSummaryKind() == GlobalVarKind;
 330   }
 331 };
 332
 333 /// 160 bits SHA1
 334 typedef std::array<uint32_t, 5> ModuleHash;
 335
 336 /// List of global value summary structures for a particular value held
 337 /// in the GlobalValueMap. Requires a vector in the case of multiple
 338 /// COMDAT values of the same name.
 339 typedef std::vector<std::unique_ptr<GlobalValueSummary>> GlobalValueSummaryList;
 340
 341 /// Map from global value GUID to corresponding summary structures.
 342 /// Use a std::map rather than a DenseMap since it will likely incur
 343 /// less overhead, as the value type is not very small and the size
 344 /// of the map is unknown, resulting in inefficiencies due to repeated
 345 /// insertions and resizing.
 346 typedef std::map<GlobalValue::GUID, GlobalValueSummaryList>
 347     GlobalValueSummaryMapTy;
 348
 349 /// Type used for iterating through the global value summary map.
 350 typedef GlobalValueSummaryMapTy::const_iterator const_gvsummary_iterator;
 351 typedef GlobalValueSummaryMapTy::iterator gvsummary_iterator;
 352
 353 /// String table to hold/own module path strings, which additionally holds the
 354 /// module ID assigned to each module during the plugin step, as well as a hash
 355 /// of the module. The StringMap makes a copy of and owns inserted strings.
 356 typedef StringMap<std::pair<uint64_t, ModuleHash>> ModulePathStringTableTy;
 357
 358 /// Map of global value GUID to its summary, used to identify values defined in
 359 /// a particular module, and provide efficient access to their summary.
 360 typedef std::map<GlobalValue::GUID, GlobalValueSummary *> GVSummaryMapTy;
 361
 362 /// Class to hold module path string table and global value map,
 363 /// and encapsulate methods for operating on them.
 364 class ModuleSummaryIndex {
 365 private:
 366   /// Map from value name to list of summary instances for values of that
 367   /// name (may be duplicates in the COMDAT case, e.g.).
 368   GlobalValueSummaryMapTy GlobalValueMap;
 369
 370   /// Holds strings for combined index, mapping to the corresponding module ID.
 371   ModulePathStringTableTy ModulePathStringTable;
 372
 373 public:
 374   gvsummary_iterator begin() { return GlobalValueMap.begin(); }
 375   const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
 376   gvsummary_iterator end() { return GlobalValueMap.end(); }
 377   const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
 378
 379   /// Get the list of global value summary objects for a given value name.
 380   const GlobalValueSummaryList &getGlobalValueSummaryList(StringRef ValueName) {
 381     return GlobalValueMap[GlobalValue::getGUID(ValueName)];
 382   }
 383
 384   /// Get the list of global value summary objects for a given value name.
 385   const const_gvsummary_iterator
 386   findGlobalValueSummaryList(StringRef ValueName) const {
 387     return GlobalValueMap.find(GlobalValue::getGUID(ValueName));
 388   }
 389
 390   /// Get the list of global value summary objects for a given value GUID.
 391   const const_gvsummary_iterator
 392   findGlobalValueSummaryList(GlobalValue::GUID ValueGUID) const {
 393     return GlobalValueMap.find(ValueGUID);
 394   }
 395
 396   /// Add a global value summary for a value of the given name.
 397   void addGlobalValueSummary(StringRef ValueName,
 398                              std::unique_ptr<GlobalValueSummary> Summary) {
 399     GlobalValueMap[GlobalValue::getGUID(ValueName)].push_back(
 400         std::move(Summary));
 401   }
 402
 403   /// Add a global value summary for a value of the given GUID.
 404   void addGlobalValueSummary(GlobalValue::GUID ValueGUID,
 405                              std::unique_ptr<GlobalValueSummary> Summary) {
 406     GlobalValueMap[ValueGUID].push_back(std::move(Summary));
 407   }
 408
 409   /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
 410   /// not found.
 411   GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
 412                                           StringRef ModuleId) const {
 413     auto CalleeInfoList = findGlobalValueSummaryList(ValueGUID);
 414     if (CalleeInfoList == end()) {
 415       return nullptr; // This function does not have a summary
 416     }
 417     auto Summary =
 418         llvm::find_if(CalleeInfoList->second,
 419                       [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
 420                         return Summary->modulePath() == ModuleId;
 421                       });
 422     if (Summary == CalleeInfoList->second.end())
 423       return nullptr;
 424     return Summary->get();
 425   }
 426
 427   /// Returns the first GlobalValueSummary for \p GV, asserting that there
 428   /// is only one if \p PerModuleIndex.
 429   GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
 430                                             bool PerModuleIndex = true) const {
 431     assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
 432     return getGlobalValueSummary(GlobalValue::getGUID(GV.getName()),
 433                                  PerModuleIndex);
 434   }
 435
 436   /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
 437   /// there
 438   /// is only one if \p PerModuleIndex.
 439   GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
 440                                             bool PerModuleIndex = true) const;
 441
 442   /// Table of modules, containing module hash and id.
 443   const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
 444     return ModulePathStringTable;
 445   }
 446
 447   /// Table of modules, containing hash and id.
 448   StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
 449     return ModulePathStringTable;
 450   }
 451
 452   /// Get the module ID recorded for the given module path.
 453   uint64_t getModuleId(const StringRef ModPath) const {
 454     return ModulePathStringTable.lookup(ModPath).first;
 455   }
 456
 457   /// Get the module SHA1 hash recorded for the given module path.
 458   const ModuleHash &getModuleHash(const StringRef ModPath) const {
 459     auto It = ModulePathStringTable.find(ModPath);
 460     assert(It != ModulePathStringTable.end() && "Module not registered");
 461     return It->second.second;
 462   }
 463
 464   /// Add the given per-module index into this module index/summary,
 465   /// assigning it the given module ID. Each module merged in should have
 466   /// a unique ID, necessary for consistent renaming of promoted
 467   /// static (local) variables.
 468   void mergeFrom(std::unique_ptr<ModuleSummaryIndex> Other,
 469                  uint64_t NextModuleId);
 470
 471   /// Convenience method for creating a promoted global name
 472   /// for the given value name of a local, and its original module's ID.
 473   static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
 474     SmallString<256> NewName(Name);
 475     NewName += ".llvm.";
 476     NewName += utohexstr(ModHash[0]); // Take the first 32 bits
 477     return NewName.str();
 478   }
 479
 480   /// Helper to obtain the unpromoted name for a global value (or the original
 481   /// name if not promoted).
 482   static StringRef getOriginalNameBeforePromote(StringRef Name) {
 483     std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
 484     return Pair.first;
 485   }
 486
 487   /// Add a new module path with the given \p Hash, mapped to the given \p
 488   /// ModID, and return an iterator to the entry in the index.
 489   ModulePathStringTableTy::iterator
 490   addModulePath(StringRef ModPath, uint64_t ModId,
 491                 ModuleHash Hash = ModuleHash{{0}}) {
 492     return ModulePathStringTable.insert(std::make_pair(
 493                                             ModPath,
 494                                             std::make_pair(ModId, Hash))).first;
 495   }
 496
 497   /// Check if the given Module has any functions available for exporting
 498   /// in the index. We consider any module present in the ModulePathStringTable
 499   /// to have exported functions.
 500   bool hasExportedFunctions(const Module &M) const {
 501     return ModulePathStringTable.count(M.getModuleIdentifier());
 502   }
 503
 504   /// Remove entries in the GlobalValueMap that have empty summaries due to the
 505   /// eager nature of map entry creation during VST parsing. These would
 506   /// also be suppressed during combined index generation in mergeFrom(),
 507   /// but if there was only one module or this was the first module we might
 508   /// not invoke mergeFrom.
 509   void removeEmptySummaryEntries();
 510
 511   /// Collect for the given module the list of function it defines
 512   /// (GUID -> Summary).
 513   void collectDefinedFunctionsForModule(StringRef ModulePath,
 514                                         GVSummaryMapTy &GVSummaryMap) const;
 515
 516   /// Collect for each module the list of Summaries it defines (GUID ->
 517   /// Summary).
 518   void collectDefinedGVSummariesPerModule(
 519       StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const;
 520 };
 521
 522 } // End llvm namespace
 523
 524 #endif