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