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     /// Indicate if the global value should be hidden.
 130     unsigned AutoHide : 1;
 131
 132     /// Convenience Constructors
 133     explicit GVFlags(GlobalValue::LinkageTypes Linkage,
 134                      bool NotEligibleToImport, bool LiveRoot, bool AutoHide)
 135         : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport),
 136           LiveRoot(LiveRoot), AutoHide(AutoHide) {}
 137   };
 138
 139 private:
 140   /// Kind of summary for use in dyn_cast<> et al.
 141   SummaryKind Kind;
 142
 143   GVFlags Flags;
 144
 145   /// This is the hash of the name of the symbol in the original file. It is
 146   /// identical to the GUID for global symbols, but differs for local since the
 147   /// GUID includes the module level id in the hash.
 148   GlobalValue::GUID OriginalName;
 149
 150   /// \brief Path of module IR containing value's definition, used to locate
 151   /// module during importing.
 152   ///
 153   /// This is only used during parsing of the combined index, or when
 154   /// parsing the per-module index for creation of the combined summary index,
 155   /// not during writing of the per-module index which doesn't contain a
 156   /// module path string table.
 157   StringRef ModulePath;
 158
 159   /// List of values referenced by this global value's definition
 160   /// (either by the initializer of a global variable, or referenced
 161   /// from within a function). This does not include functions called, which
 162   /// are listed in the derived FunctionSummary object.
 163   std::vector<ValueInfo> RefEdgeList;
 164
 165 protected:
 166   /// GlobalValueSummary constructor.
 167   GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
 168       : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {}
 169
 170 public:
 171   virtual ~GlobalValueSummary() = default;
 172
 173   /// Returns the hash of the original name, it is identical to the GUID for
 174   /// externally visible symbols, but not for local ones.
 175   GlobalValue::GUID getOriginalName() { return OriginalName; }
 176
 177   /// Initialize the original name hash in this summary.
 178   void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
 179
 180   /// Which kind of summary subclass this is.
 181   SummaryKind getSummaryKind() const { return Kind; }
 182
 183   /// Set the path to the module containing this function, for use in
 184   /// the combined index.
 185   void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
 186
 187   /// Get the path to the module containing this function.
 188   StringRef modulePath() const { return ModulePath; }
 189
 190   /// Get the flags for this GlobalValue (see \p struct GVFlags).
 191   GVFlags flags() { return Flags; }
 192
 193   /// Return linkage type recorded for this global value.
 194   GlobalValue::LinkageTypes linkage() const {
 195     return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
 196   }
 197
 198   /// Sets the linkage to the value determined by global summary-based
 199   /// optimization. Will be applied in the ThinLTO backends.
 200   void setLinkage(GlobalValue::LinkageTypes Linkage) {
 201     Flags.Linkage = Linkage;
 202   }
 203
 204   /// Sets the visibility to be autohidden.
 205   void setAutoHide() { Flags.AutoHide = true; }
 206
 207   /// Return true if this global value can't be imported.
 208   bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
 209
 210   /// Return true if this global value must be considered a root for live
 211   /// value analysis on the index.
 212   bool liveRoot() const { return Flags.LiveRoot; }
 213
 214   /// Flag that this global value must be considered a root for live
 215   /// value analysis on the index.
 216   void setLiveRoot() { Flags.LiveRoot = true; }
 217
 218   /// Flag that this global value cannot be imported.
 219   void setNotEligibleToImport() { Flags.NotEligibleToImport = true; }
 220
 221   /// Return the list of values referenced by this global value definition.
 222   ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
 223 };
 224
 225 /// \brief Alias summary information.
 226 class AliasSummary : public GlobalValueSummary {
 227   GlobalValueSummary *AliaseeSummary;
 228
 229 public:
 230   /// Summary constructors.
 231   AliasSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
 232       : GlobalValueSummary(AliasKind, Flags, std::move(Refs)) {}
 233
 234   /// Check if this is an alias summary.
 235   static bool classof(const GlobalValueSummary *GVS) {
 236     return GVS->getSummaryKind() == AliasKind;
 237   }
 238
 239   void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
 240
 241   const GlobalValueSummary &getAliasee() const {
 242     return const_cast<AliasSummary *>(this)->getAliasee();
 243   }
 244
 245   GlobalValueSummary &getAliasee() {
 246     assert(AliaseeSummary && "Unexpected missing aliasee summary");
 247     return *AliaseeSummary;
 248   }
 249 };
 250
 251 /// \brief Function summary information to aid decisions and implementation of
 252 /// importing.
 253 class FunctionSummary : public GlobalValueSummary {
 254 public:
 255   /// <CalleeValueInfo, CalleeInfo> call edge pair.
 256   typedef std::pair<ValueInfo, CalleeInfo> EdgeTy;
 257
 258 private:
 259   /// Number of instructions (ignoring debug instructions, e.g.) computed
 260   /// during the initial compile step when the summary index is first built.
 261   unsigned InstCount;
 262
 263   /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
 264   std::vector<EdgeTy> CallGraphEdgeList;
 265
 266   /// List of type identifiers used by this function, represented as GUIDs.
 267   std::vector<GlobalValue::GUID> TypeIdList;
 268
 269 public:
 270   /// Summary constructors.
 271   FunctionSummary(GVFlags Flags, unsigned NumInsts, std::vector<ValueInfo> Refs,
 272                   std::vector<EdgeTy> CGEdges,
 273                   std::vector<GlobalValue::GUID> TypeIds)
 274       : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
 275         InstCount(NumInsts), CallGraphEdgeList(std::move(CGEdges)),
 276         TypeIdList(std::move(TypeIds)) {}
 277
 278   /// Check if this is a function summary.
 279   static bool classof(const GlobalValueSummary *GVS) {
 280     return GVS->getSummaryKind() == FunctionKind;
 281   }
 282
 283   /// Get the instruction count recorded for this function.
 284   unsigned instCount() const { return InstCount; }
 285
 286   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
 287   ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
 288
 289   /// Returns the list of type identifiers used by this function.
 290   ArrayRef<GlobalValue::GUID> type_tests() const { return TypeIdList; }
 291 };
 292
 293 /// \brief Global variable summary information to aid decisions and
 294 /// implementation of importing.
 295 ///
 296 /// Currently this doesn't add anything to the base \p GlobalValueSummary,
 297 /// but is a placeholder as additional info may be added to the summary
 298 /// for variables.
 299 class GlobalVarSummary : public GlobalValueSummary {
 300
 301 public:
 302   /// Summary constructors.
 303   GlobalVarSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
 304       : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)) {}
 305
 306   /// Check if this is a global variable summary.
 307   static bool classof(const GlobalValueSummary *GVS) {
 308     return GVS->getSummaryKind() == GlobalVarKind;
 309   }
 310 };
 311
 312 struct TypeTestResolution {
 313   /// Specifies which kind of type check we should emit for this byte array.
 314   /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
 315   /// details on each kind of check; the enumerators are described with
 316   /// reference to that document.
 317   enum Kind {
 318     Unsat,     ///< Unsatisfiable type (i.e. no global has this type metadata)
 319     ByteArray, ///< Test a byte array (first example)
 320     Inline,    ///< Inlined bit vector ("Short Inline Bit Vectors")
 321     Single,    ///< Single element (last example in "Short Inline Bit Vectors")
 322     AllOnes,   ///< All-ones bit vector ("Eliminating Bit Vector Checks for
 323                ///  All-Ones Bit Vectors")
 324   } TheKind = Unsat;
 325
 326   /// Range of size-1 expressed as a bit width. For example, if the size is in
 327   /// range [1,256], this number will be 8. This helps generate the most compact
 328   /// instruction sequences.
 329   unsigned SizeM1BitWidth = 0;
 330 };
 331
 332 struct TypeIdSummary {
 333   TypeTestResolution TTRes;
 334 };
 335
 336 /// 160 bits SHA1
 337 typedef std::array<uint32_t, 5> ModuleHash;
 338
 339 /// List of global value summary structures for a particular value held
 340 /// in the GlobalValueMap. Requires a vector in the case of multiple
 341 /// COMDAT values of the same name.
 342 typedef std::vector<std::unique_ptr<GlobalValueSummary>> GlobalValueSummaryList;
 343
 344 /// Map from global value GUID to corresponding summary structures.
 345 /// Use a std::map rather than a DenseMap since it will likely incur
 346 /// less overhead, as the value type is not very small and the size
 347 /// of the map is unknown, resulting in inefficiencies due to repeated
 348 /// insertions and resizing.
 349 typedef std::map<GlobalValue::GUID, GlobalValueSummaryList>
 350     GlobalValueSummaryMapTy;
 351
 352 /// Type used for iterating through the global value summary map.
 353 typedef GlobalValueSummaryMapTy::const_iterator const_gvsummary_iterator;
 354 typedef GlobalValueSummaryMapTy::iterator gvsummary_iterator;
 355
 356 /// String table to hold/own module path strings, which additionally holds the
 357 /// module ID assigned to each module during the plugin step, as well as a hash
 358 /// of the module. The StringMap makes a copy of and owns inserted strings.
 359 typedef StringMap<std::pair<uint64_t, ModuleHash>> ModulePathStringTableTy;
 360
 361 /// Map of global value GUID to its summary, used to identify values defined in
 362 /// a particular module, and provide efficient access to their summary.
 363 typedef std::map<GlobalValue::GUID, GlobalValueSummary *> GVSummaryMapTy;
 364
 365 /// Class to hold module path string table and global value map,
 366 /// and encapsulate methods for operating on them.
 367 class ModuleSummaryIndex {
 368 private:
 369   /// Map from value name to list of summary instances for values of that
 370   /// name (may be duplicates in the COMDAT case, e.g.).
 371   GlobalValueSummaryMapTy GlobalValueMap;
 372
 373   /// Holds strings for combined index, mapping to the corresponding module ID.
 374   ModulePathStringTableTy ModulePathStringTable;
 375
 376   /// Mapping from type identifiers to summary information for that type
 377   /// identifier.
 378   // FIXME: Add bitcode read/write support for this field.
 379   std::map<std::string, TypeIdSummary> TypeIdMap;
 380
 381   // YAML I/O support.
 382   friend yaml::MappingTraits<ModuleSummaryIndex>;
 383
 384 public:
 385   gvsummary_iterator begin() { return GlobalValueMap.begin(); }
 386   const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
 387   gvsummary_iterator end() { return GlobalValueMap.end(); }
 388   const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
 389   size_t size() const { return GlobalValueMap.size(); }
 390
 391   /// Get the list of global value summary objects for a given value name.
 392   const GlobalValueSummaryList &getGlobalValueSummaryList(StringRef ValueName) {
 393     return GlobalValueMap[GlobalValue::getGUID(ValueName)];
 394   }
 395
 396   /// Get the list of global value summary objects for a given value name.
 397   const const_gvsummary_iterator
 398   findGlobalValueSummaryList(StringRef ValueName) const {
 399     return GlobalValueMap.find(GlobalValue::getGUID(ValueName));
 400   }
 401
 402   /// Get the list of global value summary objects for a given value GUID.
 403   const const_gvsummary_iterator
 404   findGlobalValueSummaryList(GlobalValue::GUID ValueGUID) const {
 405     return GlobalValueMap.find(ValueGUID);
 406   }
 407
 408   /// Add a global value summary for a value of the given name.
 409   void addGlobalValueSummary(StringRef ValueName,
 410                              std::unique_ptr<GlobalValueSummary> Summary) {
 411     GlobalValueMap[GlobalValue::getGUID(ValueName)].push_back(
 412         std::move(Summary));
 413   }
 414
 415   /// Add a global value summary for a value of the given GUID.
 416   void addGlobalValueSummary(GlobalValue::GUID ValueGUID,
 417                              std::unique_ptr<GlobalValueSummary> Summary) {
 418     GlobalValueMap[ValueGUID].push_back(std::move(Summary));
 419   }
 420
 421   /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
 422   /// not found.
 423   GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
 424                                           StringRef ModuleId) const {
 425     auto CalleeInfoList = findGlobalValueSummaryList(ValueGUID);
 426     if (CalleeInfoList == end()) {
 427       return nullptr; // This function does not have a summary
 428     }
 429     auto Summary =
 430         llvm::find_if(CalleeInfoList->second,
 431                       [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
 432                         return Summary->modulePath() == ModuleId;
 433                       });
 434     if (Summary == CalleeInfoList->second.end())
 435       return nullptr;
 436     return Summary->get();
 437   }
 438
 439   /// Returns the first GlobalValueSummary for \p GV, asserting that there
 440   /// is only one if \p PerModuleIndex.
 441   GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
 442                                             bool PerModuleIndex = true) const {
 443     assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
 444     return getGlobalValueSummary(GlobalValue::getGUID(GV.getName()),
 445                                  PerModuleIndex);
 446   }
 447
 448   /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
 449   /// there
 450   /// is only one if \p PerModuleIndex.
 451   GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
 452                                             bool PerModuleIndex = true) const;
 453
 454   /// Table of modules, containing module hash and id.
 455   const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
 456     return ModulePathStringTable;
 457   }
 458
 459   /// Table of modules, containing hash and id.
 460   StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
 461     return ModulePathStringTable;
 462   }
 463
 464   /// Get the module ID recorded for the given module path.
 465   uint64_t getModuleId(const StringRef ModPath) const {
 466     return ModulePathStringTable.lookup(ModPath).first;
 467   }
 468
 469   /// Get the module SHA1 hash recorded for the given module path.
 470   const ModuleHash &getModuleHash(const StringRef ModPath) const {
 471     auto It = ModulePathStringTable.find(ModPath);
 472     assert(It != ModulePathStringTable.end() && "Module not registered");
 473     return It->second.second;
 474   }
 475
 476   /// Add the given per-module index into this module index/summary,
 477   /// assigning it the given module ID. Each module merged in should have
 478   /// a unique ID, necessary for consistent renaming of promoted
 479   /// static (local) variables.
 480   void mergeFrom(std::unique_ptr<ModuleSummaryIndex> Other,
 481                  uint64_t NextModuleId);
 482
 483   /// Convenience method for creating a promoted global name
 484   /// for the given value name of a local, and its original module's ID.
 485   static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
 486     SmallString<256> NewName(Name);
 487     NewName += ".llvm.";
 488     NewName += utohexstr(ModHash[0]); // Take the first 32 bits
 489     return NewName.str();
 490   }
 491
 492   /// Helper to obtain the unpromoted name for a global value (or the original
 493   /// name if not promoted).
 494   static StringRef getOriginalNameBeforePromote(StringRef Name) {
 495     std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
 496     return Pair.first;
 497   }
 498
 499   /// Add a new module path with the given \p Hash, mapped to the given \p
 500   /// ModID, and return an iterator to the entry in the index.
 501   ModulePathStringTableTy::iterator
 502   addModulePath(StringRef ModPath, uint64_t ModId,
 503                 ModuleHash Hash = ModuleHash{{0}}) {
 504     return ModulePathStringTable.insert(std::make_pair(
 505                                             ModPath,
 506                                             std::make_pair(ModId, Hash))).first;
 507   }
 508
 509   /// Check if the given Module has any functions available for exporting
 510   /// in the index. We consider any module present in the ModulePathStringTable
 511   /// to have exported functions.
 512   bool hasExportedFunctions(const Module &M) const {
 513     return ModulePathStringTable.count(M.getModuleIdentifier());
 514   }
 515
 516   TypeIdSummary &getTypeIdSummary(StringRef TypeId) {
 517     return TypeIdMap[TypeId];
 518   }
 519
 520   /// Remove entries in the GlobalValueMap that have empty summaries due to the
 521   /// eager nature of map entry creation during VST parsing. These would
 522   /// also be suppressed during combined index generation in mergeFrom(),
 523   /// but if there was only one module or this was the first module we might
 524   /// not invoke mergeFrom.
 525   void removeEmptySummaryEntries();
 526
 527   /// Collect for the given module the list of function it defines
 528   /// (GUID -> Summary).
 529   void collectDefinedFunctionsForModule(StringRef ModulePath,
 530                                         GVSummaryMapTy &GVSummaryMap) const;
 531
 532   /// Collect for each module the list of Summaries it defines (GUID ->
 533   /// Summary).
 534   void collectDefinedGVSummariesPerModule(
 535       StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const;
 536 };
 537
 538 } // End llvm namespace
 539
 540 #endif