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