Index: include/llvm/Bitcode/LLVMBitCodes.h =================================================================== --- include/llvm/Bitcode/LLVMBitCodes.h +++ include/llvm/Bitcode/LLVMBitCodes.h @@ -48,7 +48,7 @@ USELIST_BLOCK_ID, MODULE_STRTAB_BLOCK_ID, - FUNCTION_SUMMARY_BLOCK_ID, + GLOBALVAL_SUMMARY_BLOCK_ID, OPERAND_BUNDLE_TAGS_BLOCK_ID, @@ -175,8 +175,10 @@ VST_CODE_ENTRY = 1, // VST_ENTRY: [valueid, namechar x N] VST_CODE_BBENTRY = 2, // VST_BBENTRY: [bbid, namechar x N] VST_CODE_FNENTRY = 3, // VST_FNENTRY: [valueid, offset, namechar x N] - // VST_COMBINED_FNENTRY: [funcsumoffset, funcguid] - VST_CODE_COMBINED_FNENTRY = 4 + // VST_COMBINED_GVDEFENTRY: [valueid, sumoffset, guid] + VST_CODE_COMBINED_GVDEFENTRY = 4, + // VST_COMBINED_ENTRY: [valueid, refguid] + VST_CODE_COMBINED_ENTRY = 5 }; // The module path symbol table only has one code (MST_CODE_ENTRY). @@ -187,8 +189,24 @@ // The function summary section uses different codes in the per-module // and combined index cases. enum FunctionSummarySymtabCodes { - FS_CODE_PERMODULE_ENTRY = 1, // FS_ENTRY: [valueid, linkage, instcount] - FS_CODE_COMBINED_ENTRY = 2, // FS_ENTRY: [modid, linkage, instcount] + // PERMODULE: [valueid, linkage, instcount, numrefs, numrefs x valueid, + // n x (valueid, callsitecount)] + FS_PERMODULE = 1, + // PERMODULE_PROFILE: [valueid, linkage, instcount, numrefs, + // numrefs x valueid, + // n x (valueid, callsitecount, profilecount)] + FS_PERMODULE_PROFILE = 2, + // PERMODULE_GLOBALVAR_INIT_REFS: [valueid, n x valueid] + FS_PERMODULE_GLOBALVAR_INIT_REFS = 3, + // COMBINED: [modid, linkage, instcount, numrefs, numrefs x valueid, + // n x (valueid, callsitecount)] + FS_COMBINED = 4, + // COMBINED_PROFILE: [modid, linkage, instcount, numrefs, + // numrefs x valueid, + // n x (valueid, callsitecount, profilecount)] + FS_COMBINED_PROFILE = 5, + // COMBINED_GLOBALVAR_INIT_REFS: [modid, n x valueid] + FS_COMBINED_GLOBALVAR_INIT_REFS = 6, }; enum MetadataCodes { Index: include/llvm/Bitcode/ReaderWriter.h =================================================================== --- include/llvm/Bitcode/ReaderWriter.h +++ include/llvm/Bitcode/ReaderWriter.h @@ -70,9 +70,9 @@ ErrorOr> parseBitcodeFile(MemoryBufferRef Buffer, LLVMContext &Context); - /// Check if the given bitcode buffer contains a function summary block. - bool hasFunctionSummary(MemoryBufferRef Buffer, - DiagnosticHandlerFunction DiagnosticHandler); + /// Check if the given bitcode buffer contains a summary block. + bool hasGlobalValueSummary(MemoryBufferRef Buffer, + DiagnosticHandlerFunction DiagnosticHandler); /// Parse the specified bitcode buffer, returning the function info index. /// If IsLazy is true, parse the entire function summary into @@ -103,17 +103,16 @@ /// Value in \c M. These will be reconstructed exactly when \a M is /// deserialized. /// - /// If \c EmitFunctionSummary, emit the function summary index (currently + /// If \c EmitSummaryIndex, emit the module's summary index (currently /// for use in ThinLTO optimization). void WriteBitcodeToFile(const Module *M, raw_ostream &Out, bool ShouldPreserveUseListOrder = false, - bool EmitFunctionSummary = false); + bool EmitSummaryIndex = false); - /// Write the specified function summary index to the given raw output stream, + /// Write the specified module summary index to the given raw output stream, /// where it will be written in a new bitcode block. This is used when /// writing the combined index file for ThinLTO. - void WriteFunctionSummaryToFile(const FunctionInfoIndex &Index, - raw_ostream &Out); + void WriteIndexToFile(const FunctionInfoIndex &Index, raw_ostream &Out); /// isBitcodeWrapper - Return true if the given bytes are the magic bytes /// for an LLVM IR bitcode wrapper. Index: include/llvm/IR/FunctionInfo.h =================================================================== --- include/llvm/IR/FunctionInfo.h +++ include/llvm/IR/FunctionInfo.h @@ -9,13 +9,15 @@ // /// @file /// FunctionInfo.h This file contains the declarations the classes that hold -/// the function info index and summary. +/// the module index and summary for function importing. // //===----------------------------------------------------------------------===// #ifndef LLVM_IR_FUNCTIONINFO_H #define LLVM_IR_FUNCTIONINFO_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringMap.h" #include "llvm/IR/Function.h" @@ -25,44 +27,68 @@ namespace llvm { -/// \brief Function summary information to aid decisions and implementation of -/// importing. +/// \brief Class to accumulate and hold information about a callee. +struct CalleeInfo { + /// The static number of callsites calling corresponding function. + unsigned CallsiteCount; + /// The cumulative profile count of calls to corresponding function + /// (if using PGO, otherwise 0). + uint64_t ProfileCount; + CalleeInfo() = default; + CalleeInfo(unsigned CallsiteCount, uint64_t ProfileCount) + : CallsiteCount(CallsiteCount), ProfileCount(ProfileCount) {} + CalleeInfo &operator+=(uint64_t RHSProfileCount) { + CallsiteCount++; + ProfileCount += RHSProfileCount; + return *this; + } +}; + +/// \brief Function and variable summary information to aid decisions and +/// implementation of importing. /// -/// This is a separate class from FunctionInfo to enable lazy reading of this -/// function summary information from the combined index file during imporing. -class FunctionSummary { +/// This is a separate class from GlobalValueInfo to enable lazy reading of this +/// summary information from the combined index file during imporing. +class GlobalValueSummary { +public: + /// \brief Sububclass discriminator (for dyn_cast<> et al.) + enum SummaryKind { FunctionKind, GlobalVarKind }; + private: - /// \brief Path of module containing function IR, used to locate module when - /// importing this function. + /// Kind of summary for use in dyn_cast<> et al. + SummaryKind Kind; + + /// \brief Path of module IR containing value's definition, used to locate + /// module during importing. /// - /// This is only used during parsing of the combined function index, or when + /// This is only used during parsing of the combined index, or when /// parsing the per-module index for creation of the combined function index, /// not during writing of the per-module index which doesn't contain a /// module path string table. StringRef ModulePath; - /// \brief The linkage type of the associated function. + /// \brief The linkage type of the associated global value. /// - /// One use is to flag functions that have local linkage types and need to + /// One use is to flag values that have local linkage types and need to /// have module identifier appended before placing into the combined - /// index, to disambiguate from other functions with the same name. + /// index, to disambiguate from other values with the same name. /// In the future this will be used to update and optimize linkage /// types based on global summary-based analysis. - GlobalValue::LinkageTypes FunctionLinkage; - - // The rest of the information is used to help decide whether importing - // is likely to be profitable. - // Other information will be added as the importing is tuned, such - // as hotness (when profile available), and other function characteristics. + GlobalValue::LinkageTypes Linkage; - /// Number of instructions (ignoring debug instructions, e.g.) computed - /// during the initial compile step when the function index is first built. - unsigned InstCount; + /// List of GUIDs of values referenced by this global value's definition + /// (either by the initializer of a global variable, or referenced + /// from within a function). This does not include functions called, which + /// are listed in the derived FunctionSummary object. + std::vector RefEdgeList; public: - /// Construct a summary object from summary data expected for all - /// summary records. - FunctionSummary(unsigned NumInsts) : InstCount(NumInsts) {} + /// GlobalValueSummary constructor. + GlobalValueSummary(SummaryKind K, GlobalValue::LinkageTypes Linkage) + : Kind(K), Linkage(Linkage) {} + + /// Which kind of summary subclass this is. + SummaryKind getSummaryKind() const { return Kind; } /// Set the path to the module containing this function, for use in /// the combined index. @@ -71,105 +97,168 @@ /// Get the path to the module containing this function. StringRef modulePath() const { return ModulePath; } - /// Record linkage type. - void setFunctionLinkage(GlobalValue::LinkageTypes Linkage) { - FunctionLinkage = Linkage; + /// Return linkage type recorded for this global value. + GlobalValue::LinkageTypes linkage() const { return Linkage; } + + /// Record a reference from this global value to the global value identified + /// by \p RefGUID. + void addRefEdge(uint64_t RefGUID) { RefEdgeList.push_back(RefGUID); } + + /// Record references to be written to the summary section for this + /// global value. + void addRefEdges(DenseSet &RefEdges) { + for (auto &RI : RefEdges) + addRefEdge(RI); } - /// Return linkage type recorded for this function. - GlobalValue::LinkageTypes getFunctionLinkage() const { - return FunctionLinkage; + /// Return the list of GUIDs referenced by this global value definition. + std::vector &refs() { return RefEdgeList; } + const std::vector &refs() const { return RefEdgeList; } +}; + +/// \brief Function summary information to aid decisions and implementation of +/// importing. +class FunctionSummary : public GlobalValueSummary { +public: + /// call edge pair. + typedef std::pair EdgeTy; + +private: + /// Number of instructions (ignoring debug instructions, e.g.) computed + /// during the initial compile step when the function index is first built. + unsigned InstCount; + + /// List of call edge pairs from this function. + std::vector CallGraphEdgeList; + +public: + /// Summary constructors. + FunctionSummary(GlobalValue::LinkageTypes Linkage, unsigned NumInsts) + : GlobalValueSummary(FunctionKind, Linkage), InstCount(NumInsts) {} + + /// Check if this is a function summary. + static bool classof(const GlobalValueSummary *GVS) { + return GVS->getSummaryKind() == FunctionKind; } /// Get the instruction count recorded for this function. unsigned instCount() const { return InstCount; } + + /// Record a call graph edge from this function to the function identified + /// by \p CalleeGUID, with \p CalleeInfo including the cumulative profile + /// count (across all calls from this function) or 0 if no FDO. + void addCallGraphEdge(uint64_t CalleeGUID, CalleeInfo Info) { + CallGraphEdgeList.push_back(std::make_pair(CalleeGUID, Info)); + } + + /// Record call graph edges to be written to the summary section for \p F. + /// The edges are provided as a map from callee ID to \p CalleeInfo, + /// including the cumulative profile count (across all calls from the + /// function) or 0 if no FDO. + void addCallGraphEdges(DenseMap &CallGraphEdges) { + for (auto &EI : CallGraphEdges) + addCallGraphEdge(EI.first, EI.second); + } + + /// Return the list of pairs. + std::vector &edges() { return CallGraphEdgeList; } + const std::vector &edges() const { return CallGraphEdgeList; } }; -/// \brief Class to hold pointer to function summary and information required -/// for parsing it. +/// \brief Global variable summary information to aid decisions and +/// implementation of importing. /// -/// For the per-module index, this holds the bitcode offset -/// of the corresponding function block. For the combined index, -/// after parsing of the \a ValueSymbolTable, this initially -/// holds the offset of the corresponding function summary bitcode -/// record. After parsing the associated summary information from the summary -/// block the \a FunctionSummary is populated and stored here. -class FunctionInfo { +/// Currently this doesn't add anything to the base \p GlobalValueSummary, +/// but is a placeholder as additional info may be added to the summary +/// for variables. +class GlobalVarSummary : public GlobalValueSummary { + +public: + /// Summary constructors. + GlobalVarSummary(GlobalValue::LinkageTypes Linkage) + : GlobalValueSummary(GlobalVarKind, Linkage) {} + + /// Check if this is a global variable summary. + static bool classof(const GlobalValueSummary *GVS) { + return GVS->getSummaryKind() == GlobalVarKind; + } +}; + +/// \brief Class to hold pointer to summary object and information required +/// for parsing or writing it. +class GlobalValueInfo { private: - /// Function summary information used to help make ThinLTO importing - /// decisions. - std::unique_ptr Summary; + /// Summary information used to help make ThinLTO importing decisions. + std::unique_ptr Summary; - /// \brief The bitcode offset corresponding to either the associated - /// function's function body record, or its function summary record, + /// \brief The bitcode offset corresponding to either an associated + /// function's function body record, or to an associated summary record, /// depending on whether this is a per-module or combined index. /// /// This bitcode offset is written to or read from the associated - /// \a ValueSymbolTable entry for the function. - /// For the per-module index this holds the bitcode offset of the - /// function's body record within bitcode module block in its module, - /// which is used during lazy function parsing or ThinLTO importing. + /// \a ValueSymbolTable entry for a function. + /// For the per-module index this holds the bitcode offset of a + /// function's body record within bitcode module block in its module, + /// although this field is currently only used when writing the VST + /// (it is set to 0 and also unused when this is a global variable). /// For the combined index this holds the offset of the corresponding - /// function summary record, to enable associating the combined index + /// summary record, to enable associating the combined index /// VST records with the summary records. uint64_t BitcodeIndex; public: /// Constructor used during parsing of VST entries. - FunctionInfo(uint64_t FuncOffset) - : Summary(nullptr), BitcodeIndex(FuncOffset) {} + GlobalValueInfo(uint64_t Offset = 0) + : Summary(nullptr), BitcodeIndex(Offset) {} /// Constructor used for per-module index bitcode writing. - FunctionInfo(uint64_t FuncOffset, - std::unique_ptr FuncSummary) - : Summary(std::move(FuncSummary)), BitcodeIndex(FuncOffset) {} + GlobalValueInfo(uint64_t Offset, std::unique_ptr Summary) + : Summary(std::move(Summary)), BitcodeIndex(Offset) {} - /// Record the function summary information parsed out of the function - /// summary block during parsing or combined index creation. - void setFunctionSummary(std::unique_ptr FuncSummary) { - Summary = std::move(FuncSummary); + /// Record the summary information parsed out of the summary block during + /// parsing or combined index creation. + void setSummary(std::unique_ptr GVSummary) { + Summary = std::move(GVSummary); } - /// Get the function summary recorded for this function. - FunctionSummary *functionSummary() const { return Summary.get(); } + /// Get the summary recorded for this global value. + GlobalValueSummary *summary() const { return Summary.get(); } - /// Get the bitcode index recorded for this function, depending on - /// the index type. + /// Get the bitcode index recorded for this value symbol table entry. uint64_t bitcodeIndex() const { return BitcodeIndex; } - /// Record the bitcode index for this function, depending on - /// the index type. - void setBitcodeIndex(uint64_t FuncOffset) { BitcodeIndex = FuncOffset; } + /// Set the bitcode index recorded for this value symbol table entry. + void setBitcodeIndex(uint64_t Offset) { BitcodeIndex = Offset; } }; -/// List of function info structures for a particular function name held -/// in the FunctionMap. Requires a vector in the case of multiple -/// COMDAT functions of the same name. -typedef std::vector> FunctionInfoList; +/// List of global value info structures for a particular value held +/// in the GlobalValueMap. Requires a vector in the case of multiple +/// COMDAT values of the same name. +typedef std::vector> GlobalValueInfoList; -/// Map from function GUID to corresponding function info structures. +/// Map from global value GUID to corresponding info structures. /// Use a std::map rather than a DenseMap since it will likely incur /// less overhead, as the value type is not very small and the size /// of the map is unknown, resulting in inefficiencies due to repeated /// insertions and resizing. -typedef std::map FunctionInfoMapTy; +typedef std::map GlobalValueInfoMapTy; -/// Type used for iterating through the function info map. -typedef FunctionInfoMapTy::const_iterator const_funcinfo_iterator; -typedef FunctionInfoMapTy::iterator funcinfo_iterator; +/// Type used for iterating through the global value info map. +typedef GlobalValueInfoMapTy::const_iterator const_globalvalueinfo_iterator; +typedef GlobalValueInfoMapTy::iterator globalvalueinfo_iterator; /// String table to hold/own module path strings, which additionally holds the /// module ID assigned to each module during the plugin step. The StringMap /// makes a copy of and owns inserted strings. typedef StringMap ModulePathStringTableTy; -/// Class to hold module path string table and function map, +/// Class to hold module path string table and global value map, /// and encapsulate methods for operating on them. class FunctionInfoIndex { private: - /// Map from function name to list of function information instances - /// for functions of that name (may be duplicates in the COMDAT case, e.g.). - FunctionInfoMapTy FunctionMap; + /// Map from value name to list of information instances for values of that + /// name (may be duplicates in the COMDAT case, e.g.). + GlobalValueInfoMapTy GlobalValueMap; /// Holds strings for combined index, mapping to the corresponding module ID. ModulePathStringTableTy ModulePathStringTable; @@ -182,28 +271,40 @@ FunctionInfoIndex(const FunctionInfoIndex &) = delete; void operator=(const FunctionInfoIndex &) = delete; - funcinfo_iterator begin() { return FunctionMap.begin(); } - const_funcinfo_iterator begin() const { return FunctionMap.begin(); } - funcinfo_iterator end() { return FunctionMap.end(); } - const_funcinfo_iterator end() const { return FunctionMap.end(); } + globalvalueinfo_iterator begin() { return GlobalValueMap.begin(); } + const_globalvalueinfo_iterator begin() const { + return GlobalValueMap.begin(); + } + globalvalueinfo_iterator end() { return GlobalValueMap.end(); } + const_globalvalueinfo_iterator end() const { return GlobalValueMap.end(); } + + /// Get the list of global value info objects for a given value name. + const GlobalValueInfoList &getGlobalValueInfoList(StringRef FuncName) { + return GlobalValueMap[Function::getGUID(FuncName)]; + } - /// Get the list of function info objects for a given function. - const FunctionInfoList &getFunctionInfoList(StringRef FuncName) { - return FunctionMap[Function::getGUID(FuncName)]; + /// Get the list of global value info objects for a given value name. + const const_globalvalueinfo_iterator + findGlobalValueInfoList(StringRef ValueName) const { + return GlobalValueMap.find(Function::getGUID(ValueName)); } - /// Get the list of function info objects for a given function. - const const_funcinfo_iterator findFunctionInfoList(StringRef FuncName) const { - return FunctionMap.find(Function::getGUID(FuncName)); + /// Get the list of global value info objects for a given value GUID. + const const_globalvalueinfo_iterator + findGlobalValueInfoList(uint64_t ValueGUID) const { + return GlobalValueMap.find(ValueGUID); } - /// Add a function info for a function of the given name. - void addFunctionInfo(StringRef FuncName, std::unique_ptr Info) { - FunctionMap[Function::getGUID(FuncName)].push_back(std::move(Info)); + /// Add a global value info for a value of the given name. + void addGlobalValueInfo(StringRef ValueName, + std::unique_ptr Info) { + GlobalValueMap[Function::getGUID(ValueName)].push_back(std::move(Info)); } - void addFunctionInfo(uint64_t FuncGUID, std::unique_ptr Info) { - FunctionMap[FuncGUID].push_back(std::move(Info)); + /// Add a global value info for a value of the given GUID. + void addGlobalValueInfo(uint64_t ValueGUID, + std::unique_ptr Info) { + GlobalValueMap[ValueGUID].push_back(std::move(Info)); } /// Iterator to allow writer to walk through table during emission. @@ -218,7 +319,7 @@ return ModulePathStringTable.lookup(ModPath); } - /// Add the given per-module index into this function index/summary, + /// Add the given per-module index into this module index/summary, /// assigning it the given module ID. Each module merged in should have /// a unique ID, necessary for consistent renaming of promoted /// static (local) variables. Index: include/llvm/Object/FunctionIndexObjectFile.h =================================================================== --- include/llvm/Object/FunctionIndexObjectFile.h +++ include/llvm/Object/FunctionIndexObjectFile.h @@ -77,11 +77,11 @@ static ErrorOr findBitcodeInMemBuffer(MemoryBufferRef Object); - /// \brief Looks for function summary in the given memory buffer, + /// \brief Looks for summary sections in the given memory buffer, /// returns true if found, else false. static bool - hasFunctionSummaryInMemBuffer(MemoryBufferRef Object, - DiagnosticHandlerFunction DiagnosticHandler); + hasGlobalValueSummaryInMemBuffer(MemoryBufferRef Object, + DiagnosticHandlerFunction DiagnosticHandler); /// \brief Parse function index in the given memory buffer. /// Return new FunctionIndexObjectFile instance containing parsed function Index: include/llvm/ProfileData/ProfileCommon.h =================================================================== --- include/llvm/ProfileData/ProfileCommon.h +++ include/llvm/ProfileData/ProfileCommon.h @@ -15,6 +15,7 @@ #ifndef LLVM_PROFILEDATA_PROFILE_COMMON_H #define LLVM_PROFILEDATA_PROFILE_COMMON_H +#include "llvm/ADT/APInt.h" #include #include #include @@ -184,5 +185,17 @@ return DetailedSummary; } +/// Helper to compute the profile count for a block, based on the +/// ratio of its frequency to the entry block frequency, multiplied +/// by the entry block count. +inline uint64_t getBlockProfileCount(uint64_t BlockFreq, uint64_t EntryFreq, + uint64_t EntryCount) { + APInt ScaledCount(128, EntryCount); + APInt BlockFreqAPInt(128, BlockFreq); + APInt EntryFreqAPInt(128, EntryFreq); + ScaledCount *= BlockFreqAPInt.udiv(EntryFreqAPInt); + return ScaledCount.getLimitedValue(); +} + } // end namespace llvm #endif Index: lib/Bitcode/Reader/BitcodeReader.cpp =================================================================== --- lib/Bitcode/Reader/BitcodeReader.cpp +++ lib/Bitcode/Reader/BitcodeReader.cpp @@ -416,7 +416,7 @@ class FunctionIndexBitcodeReader { DiagnosticHandlerFunction DiagnosticHandler; - /// Eventually points to the function index built during parsing. + /// Eventually points to the module index built during parsing. FunctionInfoIndex *TheIndex = nullptr; std::unique_ptr Buffer; @@ -432,29 +432,33 @@ bool IsLazy = false; /// Used to indicate whether caller only wants to check for the presence - /// of the function summary bitcode section. All blocks are skipped, - /// but the SeenFuncSummary boolean is set. - bool CheckFuncSummaryPresenceOnly = false; + /// of the global value summary bitcode section. All blocks are skipped, + /// but the SeenGlobalValSummary boolean is set. + bool CheckGlobalValSummaryPresenceOnly = false; - /// Indicates whether we have encountered a function summary section - /// yet during parsing, used when checking if file contains function + /// Indicates whether we have encountered a global value summary section + /// yet during parsing, used when checking if file contains global value /// summary section. - bool SeenFuncSummary = false; + bool SeenGlobalValSummary = false; - /// \brief Map populated during function summary section parsing, and - /// consumed during ValueSymbolTable parsing. - /// - /// Used to correlate summary records with VST entries. For the per-module - /// index this maps the ValueID to the parsed function summary, and - /// for the combined index this maps the summary record's bitcode - /// offset to the function summary (since in the combined index the - /// VST records do not hold value IDs but rather hold the function - /// summary record offset). - DenseMap> SummaryMap; + bool SeenValueSymbolTable = false; + uint64_t VSTOffset = 0; + + // Map to save ValueId to GUID association that was recorded in the + // ValueSymbolTable. It is used after the VST is parsed to convert + // call graph edges read from the function summary from referencing + // callees by their ValueId to using the GUID instead, which is how + // they are recorded in the function index being built. + DenseMap ValueIdToCallGraphGUIDMap; + + /// Map to save the association between summary offset in the VST to the + /// GlobalValueInfo object created when parsing it. Used to access the + /// info object when parsing the summary section. + DenseMap SummaryOffsetToInfoMap; /// Map populated during module path string table parsing, from the /// module ID to a string reference owned by the index's module - /// path string table, used to correlate with combined index function + /// path string table, used to correlate with combined index /// summary records. DenseMap ModuleIdMap; @@ -469,37 +473,41 @@ FunctionIndexBitcodeReader(MemoryBuffer *Buffer, DiagnosticHandlerFunction DiagnosticHandler, bool IsLazy = false, - bool CheckFuncSummaryPresenceOnly = false); + bool CheckGlobalValSummaryPresenceOnly = false); FunctionIndexBitcodeReader(DiagnosticHandlerFunction DiagnosticHandler, bool IsLazy = false, - bool CheckFuncSummaryPresenceOnly = false); + bool CheckGlobalValSummaryPresenceOnly = false); ~FunctionIndexBitcodeReader() { freeState(); } void freeState(); void releaseBuffer(); - /// Check if the parser has encountered a function summary section. - bool foundFuncSummary() { return SeenFuncSummary; } + /// Check if the parser has encountered a summary section. + bool foundGlobalValSummary() { return SeenGlobalValSummary; } /// \brief Main interface to parsing a bitcode buffer. /// \returns true if an error occurred. std::error_code parseSummaryIndexInto(std::unique_ptr Streamer, FunctionInfoIndex *I); - /// \brief Interface for parsing a function summary lazily. + /// \brief Interface for parsing a summary lazily. std::error_code parseFunctionSummary(std::unique_ptr Streamer, FunctionInfoIndex *I, size_t FunctionSummaryOffset); private: std::error_code parseModule(); - std::error_code parseValueSymbolTable(); + std::error_code parseValueSymbolTable( + uint64_t Offset, + DenseMap &ValueIdToLinkageMap); std::error_code parseEntireSummary(); std::error_code parseModuleStringTable(); std::error_code initStream(std::unique_ptr Streamer); std::error_code initStreamFromBuffer(); std::error_code initLazyStream(std::unique_ptr Streamer); + uint64_t getGUIDFromValueId(unsigned ValueId); + GlobalValueInfo *getInfoFromSummaryOffset(uint64_t Offset); }; } // end anonymous namespace @@ -1727,6 +1735,27 @@ return V; } +/// Helper to note and return the current location, and jump to the given +/// offset. +static uint64_t jumpToValueSymbolTable(uint64_t Offset, + BitstreamCursor &Stream) { + // Save the current parsing location so we can jump back at the end + // of the VST read. + uint64_t CurrentBit = Stream.GetCurrentBitNo(); + Stream.JumpToBit(Offset * 32); +#ifndef NDEBUG + // Do some checking if we are in debug mode. + BitstreamEntry Entry = Stream.advance(); + assert(Entry.Kind == BitstreamEntry::SubBlock); + assert(Entry.ID == bitc::VALUE_SYMTAB_BLOCK_ID); +#else + // In NDEBUG mode ignore the output so we don't get an unused variable + // warning. + Stream.advance(); +#endif + return CurrentBit; +} + /// Parse the value symbol table at either the current parsing location or /// at the given bit offset if provided. std::error_code BitcodeReader::parseValueSymbolTable(uint64_t Offset) { @@ -1734,22 +1763,8 @@ // Pass in the Offset to distinguish between calling for the module-level // VST (where we want to jump to the VST offset) and the function-level // VST (where we don't). - if (Offset > 0) { - // Save the current parsing location so we can jump back at the end - // of the VST read. - CurrentBit = Stream.GetCurrentBitNo(); - Stream.JumpToBit(Offset * 32); -#ifndef NDEBUG - // Do some checking if we are in debug mode. - BitstreamEntry Entry = Stream.advance(); - assert(Entry.Kind == BitstreamEntry::SubBlock); - assert(Entry.ID == bitc::VALUE_SYMTAB_BLOCK_ID); -#else - // In NDEBUG mode ignore the output so we don't get an unused variable - // warning. - Stream.advance(); -#endif - } + if (Offset > 0) + CurrentBit = jumpToValueSymbolTable(Offset, Stream); // Compute the delta between the bitcode indices in the VST (the word offset // to the word-aligned ENTER_SUBBLOCK for the function block, and that @@ -5411,27 +5426,45 @@ FunctionIndexBitcodeReader::FunctionIndexBitcodeReader( MemoryBuffer *Buffer, DiagnosticHandlerFunction DiagnosticHandler, - bool IsLazy, bool CheckFuncSummaryPresenceOnly) + bool IsLazy, bool CheckGlobalValSummaryPresenceOnly) : DiagnosticHandler(DiagnosticHandler), Buffer(Buffer), IsLazy(IsLazy), - CheckFuncSummaryPresenceOnly(CheckFuncSummaryPresenceOnly) {} + CheckGlobalValSummaryPresenceOnly(CheckGlobalValSummaryPresenceOnly) {} FunctionIndexBitcodeReader::FunctionIndexBitcodeReader( DiagnosticHandlerFunction DiagnosticHandler, bool IsLazy, - bool CheckFuncSummaryPresenceOnly) + bool CheckGlobalValSummaryPresenceOnly) : DiagnosticHandler(DiagnosticHandler), Buffer(nullptr), IsLazy(IsLazy), - CheckFuncSummaryPresenceOnly(CheckFuncSummaryPresenceOnly) {} + CheckGlobalValSummaryPresenceOnly(CheckGlobalValSummaryPresenceOnly) {} void FunctionIndexBitcodeReader::freeState() { Buffer = nullptr; } void FunctionIndexBitcodeReader::releaseBuffer() { Buffer.release(); } -// Specialized value symbol table parser used when reading function index +uint64_t FunctionIndexBitcodeReader::getGUIDFromValueId(unsigned ValueId) { + auto VGI = ValueIdToCallGraphGUIDMap.find(ValueId); + assert(VGI != ValueIdToCallGraphGUIDMap.end()); + return VGI->second; +} + +GlobalValueInfo * +FunctionIndexBitcodeReader::getInfoFromSummaryOffset(uint64_t Offset) { + auto I = SummaryOffsetToInfoMap.find(Offset); + assert(I != SummaryOffsetToInfoMap.end()); + return I->second; +} + +// Specialized value symbol table parser used when reading module index // blocks where we don't actually create global values. -// At the end of this routine the function index is populated with a map -// from function name to FunctionInfo. The function info contains -// the function block's bitcode offset as well as the offset into the -// function summary section. -std::error_code FunctionIndexBitcodeReader::parseValueSymbolTable() { +// At the end of this routine the module index is populated with a map +// from global value name to GlobalValueInfo. The global value info contains +// the function block's bitcode offset (if applicable), or the offset into the +// summary section for the combined index. +std::error_code FunctionIndexBitcodeReader::parseValueSymbolTable( + uint64_t Offset, + DenseMap &ValueIdToLinkageMap) { + assert(Offset > 0 && "Expected non-zero VST offset"); + uint64_t CurrentBit = jumpToValueSymbolTable(Offset, Stream); + if (Stream.EnterSubBlock(bitc::VALUE_SYMTAB_BLOCK_ID)) return error("Invalid record"); @@ -5447,6 +5480,8 @@ case BitstreamEntry::Error: return error("Malformed block"); case BitstreamEntry::EndBlock: + // Done parsing VST, jump back to wherever we came from. + Stream.JumpToBit(CurrentBit); return std::error_code(); case BitstreamEntry::Record: // The interesting case. @@ -5458,6 +5493,23 @@ switch (Stream.readRecord(Entry.ID, Record)) { default: // Default behavior: ignore (e.g. VST_CODE_BBENTRY records). break; + case bitc::VST_CODE_ENTRY: { // VST_CODE_ENTRY: [valueid, namechar x N] + if (convertToString(Record, 1, ValueName)) + return error("Invalid record"); + unsigned ValueID = Record[0]; + std::unique_ptr GlobalValInfo = + llvm::make_unique(); + assert(!SourceFileName.empty()); + auto VLI = ValueIdToLinkageMap.find(ValueID); + assert(VLI != ValueIdToLinkageMap.end() && + "No linkage found for VST entry?"); + std::string GlobalId = + Function::getGlobalIdentifier(ValueName, VLI->second, SourceFileName); + TheIndex->addGlobalValueInfo(GlobalId, std::move(GlobalValInfo)); + ValueIdToCallGraphGUIDMap[ValueID] = Function::getGUID(GlobalId); + ValueName.clear(); + break; + } case bitc::VST_CODE_FNENTRY: { // VST_CODE_FNENTRY: [valueid, offset, namechar x N] if (convertToString(Record, 2, ValueName)) @@ -5465,59 +5517,58 @@ unsigned ValueID = Record[0]; uint64_t FuncOffset = Record[1]; assert(!IsLazy && "Lazy summary read only supported for combined index"); - // Gracefully handle bitcode without a function summary section, - // which will simply not populate the index. - if (foundFuncSummary()) { - DenseMap>::iterator SMI = - SummaryMap.find(ValueID); - assert(SMI != SummaryMap.end() && "Summary info not found"); - std::unique_ptr FuncInfo = - llvm::make_unique(FuncOffset); - FuncInfo->setFunctionSummary(std::move(SMI->second)); - assert(!SourceFileName.empty()); - std::string FunctionGlobalId = Function::getGlobalIdentifier( - ValueName, FuncInfo->functionSummary()->getFunctionLinkage(), - SourceFileName); - TheIndex->addFunctionInfo(FunctionGlobalId, std::move(FuncInfo)); - } + std::unique_ptr FuncInfo = + llvm::make_unique(FuncOffset); + assert(!SourceFileName.empty()); + auto VLI = ValueIdToLinkageMap.find(ValueID); + assert(VLI != ValueIdToLinkageMap.end() && + "No linkage found for VST entry?"); + std::string FunctionGlobalId = + Function::getGlobalIdentifier(ValueName, VLI->second, SourceFileName); + TheIndex->addGlobalValueInfo(FunctionGlobalId, std::move(FuncInfo)); + ValueIdToCallGraphGUIDMap[ValueID] = Function::getGUID(FunctionGlobalId); ValueName.clear(); break; } - case bitc::VST_CODE_COMBINED_FNENTRY: { - // VST_CODE_COMBINED_FNENTRY: [offset, funcguid] - uint64_t FuncSummaryOffset = Record[0]; - uint64_t FuncGUID = Record[1]; - std::unique_ptr FuncInfo = - llvm::make_unique(FuncSummaryOffset); - if (foundFuncSummary() && !IsLazy) { - DenseMap>::iterator SMI = - SummaryMap.find(FuncSummaryOffset); - assert(SMI != SummaryMap.end() && "Summary info not found"); - FuncInfo->setFunctionSummary(std::move(SMI->second)); - } - TheIndex->addFunctionInfo(FuncGUID, std::move(FuncInfo)); - - ValueName.clear(); + case bitc::VST_CODE_COMBINED_GVDEFENTRY: { + // VST_CODE_COMBINED_GVDEFENTRY: [valueid, offset, guid] + unsigned ValueID = Record[0]; + uint64_t GlobalValSummaryOffset = Record[1]; + uint64_t GlobalValGUID = Record[2]; + std::unique_ptr GlobalValInfo = + llvm::make_unique(GlobalValSummaryOffset); + SummaryOffsetToInfoMap[GlobalValSummaryOffset] = GlobalValInfo.get(); + TheIndex->addGlobalValueInfo(GlobalValGUID, std::move(GlobalValInfo)); + ValueIdToCallGraphGUIDMap[ValueID] = GlobalValGUID; + break; + } + case bitc::VST_CODE_COMBINED_ENTRY: { + // VST_CODE_COMBINED_ENTRY: [valueid, refguid] + unsigned ValueID = Record[0]; + uint64_t RefGUID = Record[1]; + ValueIdToCallGraphGUIDMap[ValueID] = RefGUID; break; } } } } -// Parse just the blocks needed for function index building out of the module. -// At the end of this routine the function Index is populated with a map -// from function name to FunctionInfo. The function info contains -// either the parsed function summary information (when parsing summaries -// eagerly), or just to the function summary record's offset +// Parse just the blocks needed for building the index out of the module. +// At the end of this routine the module Index is populated with a map +// from global value name to GlobalValueInfo. The global value info contains +// either the parsed summary information (when parsing summaries +// eagerly), or just to the summary record's offset // if parsing lazily (IsLazy). std::error_code FunctionIndexBitcodeReader::parseModule() { if (Stream.EnterSubBlock(bitc::MODULE_BLOCK_ID)) return error("Invalid record"); SmallVector Record; + DenseMap ValueIdToLinkageMap; + unsigned ValueId = 0; - // Read the function index for this module. + // Read the index for this module. while (1) { BitstreamEntry Entry = Stream.advance(); @@ -5528,9 +5579,9 @@ return std::error_code(); case BitstreamEntry::SubBlock: - if (CheckFuncSummaryPresenceOnly) { - if (Entry.ID == bitc::FUNCTION_SUMMARY_BLOCK_ID) { - SeenFuncSummary = true; + if (CheckGlobalValSummaryPresenceOnly) { + if (Entry.ID == bitc::GLOBALVAL_SUMMARY_BLOCK_ID) { + SeenGlobalValSummary = true; // No need to parse the rest since we found the summary. return std::error_code(); } @@ -5549,11 +5600,23 @@ return error("Malformed block"); break; case bitc::VALUE_SYMTAB_BLOCK_ID: - if (std::error_code EC = parseValueSymbolTable()) - return EC; + // Should have been parsed earlier via VSTOffset, unless there + // is no summary section. + assert(((SeenValueSymbolTable && VSTOffset > 0) || + !SeenGlobalValSummary) && + "Expected early VST parse via VSTOffset record"); + if (Stream.SkipBlock()) + return error("Invalid record"); break; - case bitc::FUNCTION_SUMMARY_BLOCK_ID: - SeenFuncSummary = true; + case bitc::GLOBALVAL_SUMMARY_BLOCK_ID: + assert(VSTOffset > 0 && "Expected non-zero VST offset"); + assert(!SeenValueSymbolTable && + "Already read VST when parsing summary block?"); + if (std::error_code EC = + parseValueSymbolTable(VSTOffset, ValueIdToLinkageMap)) + return EC; + SeenValueSymbolTable = true; + SeenGlobalValSummary = true; if (IsLazy) { // Lazy parsing of summary info, skip it. if (Stream.SkipBlock()) @@ -5569,8 +5632,8 @@ continue; case BitstreamEntry::Record: - // Once we find the single record of interest, skip the rest. - if (!SourceFileName.empty()) + // Once we find the last record of interest, skip the rest. + if (VSTOffset > 0) Stream.skipRecord(Entry.ID); else { Record.clear(); @@ -5579,24 +5642,63 @@ default: break; // Default behavior, ignore unknown content. /// MODULE_CODE_SOURCE_FILENAME: [namechar x N] - case bitc::MODULE_CODE_SOURCE_FILENAME: + case bitc::MODULE_CODE_SOURCE_FILENAME: { SmallString<128> ValueName; if (convertToString(Record, 0, ValueName)) return error("Invalid record"); SourceFileName = ValueName.c_str(); break; } + /// MODULE_CODE_VSTOFFSET: [offset] + case bitc::MODULE_CODE_VSTOFFSET: + if (Record.size() < 1) + return error("Invalid record"); + VSTOffset = Record[0]; + break; + // GLOBALVAR: [pointer type, isconst, initid, + // linkage, alignment, section, visibility, threadlocal, + // unnamed_addr, externally_initialized, dllstorageclass, + // comdat] + case bitc::MODULE_CODE_GLOBALVAR: { + if (Record.size() < 6) + return error("Invalid record"); + uint64_t RawLinkage = Record[3]; + GlobalValue::LinkageTypes Linkage = getDecodedLinkage(RawLinkage); + ValueIdToLinkageMap[ValueId++] = Linkage; + break; + } + // FUNCTION: [type, callingconv, isproto, linkage, paramattr, + // alignment, section, visibility, gc, unnamed_addr, + // prologuedata, dllstorageclass, comdat, prefixdata] + case bitc::MODULE_CODE_FUNCTION: { + if (Record.size() < 8) + return error("Invalid record"); + uint64_t RawLinkage = Record[3]; + GlobalValue::LinkageTypes Linkage = getDecodedLinkage(RawLinkage); + ValueIdToLinkageMap[ValueId++] = Linkage; + break; + } + // ALIAS: [alias type, addrspace, aliasee val#, linkage, visibility, + // dllstorageclass] + case bitc::MODULE_CODE_ALIAS: { + if (Record.size() < 6) + return error("Invalid record"); + uint64_t RawLinkage = Record[3]; + GlobalValue::LinkageTypes Linkage = getDecodedLinkage(RawLinkage); + ValueIdToLinkageMap[ValueId++] = Linkage; + break; + } + } } continue; } } } -// Eagerly parse the entire function summary block (i.e. for all functions -// in the index). This populates the FunctionSummary objects in -// the index. +// Eagerly parse the entire summary block. This populates the GlobalValueSummary +// objects in the index. std::error_code FunctionIndexBitcodeReader::parseEntireSummary() { - if (Stream.EnterSubBlock(bitc::FUNCTION_SUMMARY_BLOCK_ID)) + if (Stream.EnterSubBlock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID)) return error("Invalid record"); SmallVector Record; @@ -5624,17 +5726,23 @@ // information used for ThinLTO renaming and importing. Record.clear(); uint64_t CurRecordBit = Stream.GetCurrentBitNo(); - switch (Stream.readRecord(Entry.ID, Record)) { + auto BitCode = Stream.readRecord(Entry.ID, Record); + switch (BitCode) { default: // Default behavior: ignore. break; - // FS_PERMODULE_ENTRY: [valueid, linkage, instcount] - case bitc::FS_CODE_PERMODULE_ENTRY: { + // FS_PERMODULE: [valueid, linkage, instcount, numrefs, numrefs x valueid, + // n x (valueid, callsitecount)] + // FS_PERMODULE_PROFILE: [valueid, linkage, instcount, numrefs, + // numrefs x valueid, + // n x (valueid, callsitecount, profilecount)] + case bitc::FS_PERMODULE: + case bitc::FS_PERMODULE_PROFILE: { unsigned ValueID = Record[0]; uint64_t RawLinkage = Record[1]; unsigned InstCount = Record[2]; - std::unique_ptr FS = - llvm::make_unique(InstCount); - FS->setFunctionLinkage(getDecodedLinkage(RawLinkage)); + unsigned NumRefs = Record[3]; + std::unique_ptr FS = llvm::make_unique( + getDecodedLinkage(RawLinkage), InstCount); // The module path string ref set in the summary must be owned by the // index's module string table. Since we don't have a module path // string table section in the per-module index, we create a single @@ -5642,19 +5750,113 @@ // ownership. FS->setModulePath( TheIndex->addModulePath(Buffer->getBufferIdentifier(), 0)); - SummaryMap[ValueID] = std::move(FS); - break; - } - // FS_COMBINED_ENTRY: [modid, linkage, instcount] - case bitc::FS_CODE_COMBINED_ENTRY: { + static int RefListStartIndex = 4; + int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs; + assert(Record.size() >= RefListStartIndex + NumRefs && + "Record size inconsistent with number of references"); + for (unsigned I = 4, E = CallGraphEdgeStartIndex; I != E; ++I) { + unsigned RefValueId = Record[I]; + uint64_t RefGUID = getGUIDFromValueId(RefValueId); + FS->addRefEdge(RefGUID); + } + bool HasProfile = (BitCode == bitc::FS_PERMODULE_PROFILE); + for (unsigned I = CallGraphEdgeStartIndex, E = Record.size(); I != E; + ++I) { + unsigned CalleeValueId = Record[I]; + unsigned CallsiteCount = Record[++I]; + uint64_t ProfileCount = HasProfile ? Record[++I] : 0; + uint64_t CalleeGUID = getGUIDFromValueId(CalleeValueId); + FS->addCallGraphEdge(CalleeGUID, + CalleeInfo(CallsiteCount, ProfileCount)); + } + uint64_t GUID = getGUIDFromValueId(ValueID); + auto InfoList = TheIndex->findGlobalValueInfoList(GUID); + assert(InfoList != TheIndex->end() && + "Expected VST parse to create GlobalValueInfo entry"); + assert(InfoList->second.size() == 1 && + "Expected a single GlobalValueInfo per GUID in module"); + auto &Info = InfoList->second[0]; + assert(!Info->summary() && "Expected a single summary per VST entry"); + Info->setSummary(std::move(FS)); + break; + } + // FS_PERMODULE_GLOBALVAR_INIT_REFS: [valueid, n x valueid] + case bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS: { + unsigned ValueID = Record[0]; + std::unique_ptr FS = + llvm::make_unique( + /*HACK*/ GlobalValue::ExternalLinkage); + FS->setModulePath( + TheIndex->addModulePath(Buffer->getBufferIdentifier(), 0)); + for (unsigned I = 1, E = Record.size(); I != E; ++I) { + unsigned RefValueId = Record[I]; + uint64_t RefGUID = getGUIDFromValueId(RefValueId); + FS->addRefEdge(RefGUID); + } + uint64_t GUID = getGUIDFromValueId(ValueID); + auto InfoList = TheIndex->findGlobalValueInfoList(GUID); + assert(InfoList != TheIndex->end() && + "Expected VST parse to create GlobalValueInfo entry"); + assert(InfoList->second.size() == 1 && + "Expected a single GlobalValueInfo per GUID in module"); + auto &Info = InfoList->second[0]; + assert(!Info->summary() && "Expected a single summary per VST entry"); + Info->setSummary(std::move(FS)); + break; + } + // FS_COMBINED: [modid, linkage, instcount, numrefs, numrefs x valueid, + // n x (valueid, callsitecount)] + // FS_COMBINED_PROFILE: [modid, linkage, instcount, numrefs, + // numrefs x valueid, + // n x (valueid, callsitecount, profilecount)] + case bitc::FS_COMBINED: + case bitc::FS_COMBINED_PROFILE: { uint64_t ModuleId = Record[0]; uint64_t RawLinkage = Record[1]; unsigned InstCount = Record[2]; - std::unique_ptr FS = - llvm::make_unique(InstCount); - FS->setFunctionLinkage(getDecodedLinkage(RawLinkage)); + unsigned NumRefs = Record[3]; + std::unique_ptr FS = llvm::make_unique( + getDecodedLinkage(RawLinkage), InstCount); + FS->setModulePath(ModuleIdMap[ModuleId]); + static int RefListStartIndex = 4; + int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs; + assert(Record.size() >= RefListStartIndex + NumRefs && + "Record size inconsistent with number of references"); + for (unsigned I = 4, E = CallGraphEdgeStartIndex; I != E; ++I) { + unsigned RefValueId = Record[I]; + uint64_t RefGUID = getGUIDFromValueId(RefValueId); + FS->addRefEdge(RefGUID); + } + bool HasProfile = (BitCode == bitc::FS_COMBINED_PROFILE); + for (unsigned I = CallGraphEdgeStartIndex, E = Record.size(); I != E; + ++I) { + unsigned CalleeValueId = Record[I]; + unsigned CallsiteCount = Record[++I]; + uint64_t ProfileCount = HasProfile ? Record[++I] : 0; + uint64_t CalleeGUID = getGUIDFromValueId(CalleeValueId); + FS->addCallGraphEdge(CalleeGUID, + CalleeInfo(CallsiteCount, ProfileCount)); + } + auto *Info = getInfoFromSummaryOffset(CurRecordBit); + assert(!Info->summary() && "Expected a single summary per VST entry"); + Info->setSummary(std::move(FS)); + break; + } + // FS_COMBINED_GLOBALVAR_INIT_REFS: [modid, n x valueid] + case bitc::FS_COMBINED_GLOBALVAR_INIT_REFS: { + uint64_t ModuleId = Record[0]; + std::unique_ptr FS = + llvm::make_unique( + /*HACK*/ GlobalValue::ExternalLinkage); FS->setModulePath(ModuleIdMap[ModuleId]); - SummaryMap[CurRecordBit] = std::move(FS); + for (unsigned I = 1, E = Record.size(); I != E; ++I) { + unsigned RefValueId = Record[I]; + uint64_t RefGUID = getGUIDFromValueId(RefValueId); + FS->addRefEdge(RefGUID); + } + auto *Info = getInfoFromSummaryOffset(CurRecordBit); + assert(!Info->summary() && "Expected a single summary per VST entry"); + Info->setSummary(std::move(FS)); break; } } @@ -5773,7 +5975,9 @@ // importing is added so that it can be tested. SmallVector Record; switch (Stream.readRecord(Entry.ID, Record)) { - case bitc::FS_CODE_COMBINED_ENTRY: + case bitc::FS_COMBINED: + case bitc::FS_COMBINED_PROFILE: + case bitc::FS_COMBINED_GLOBALVAR_INIT_REFS: default: return error("Invalid record"); } @@ -5987,9 +6191,9 @@ return std::move(Index); } -// Check if the given bitcode buffer contains a function summary block. -bool llvm::hasFunctionSummary(MemoryBufferRef Buffer, - DiagnosticHandlerFunction DiagnosticHandler) { +// Check if the given bitcode buffer contains a global value summary block. +bool llvm::hasGlobalValueSummary(MemoryBufferRef Buffer, + DiagnosticHandlerFunction DiagnosticHandler) { std::unique_ptr Buf = MemoryBuffer::getMemBuffer(Buffer, false); FunctionIndexBitcodeReader R(Buf.get(), DiagnosticHandler, false, true); @@ -6002,7 +6206,7 @@ return cleanupOnError(EC); Buf.release(); // The FunctionIndexBitcodeReader owns it now. - return R.foundFuncSummary(); + return R.foundGlobalValSummary(); } // This method supports lazy reading of function summary data from the combined @@ -6026,7 +6230,7 @@ // contain a list of function infos in the case of a COMDAT. Walk through // and parse each function summary info at the function summary offset // recorded when parsing the value symbol table. - for (const auto &FI : Index->getFunctionInfoList(FunctionName)) { + for (const auto &FI : Index->getGlobalValueInfoList(FunctionName)) { size_t FunctionSummaryOffset = FI->bitcodeIndex(); if (std::error_code EC = R.parseFunctionSummary(nullptr, Index.get(), FunctionSummaryOffset)) Index: lib/Bitcode/Writer/BitcodeWriter.cpp =================================================================== --- lib/Bitcode/Writer/BitcodeWriter.cpp +++ lib/Bitcode/Writer/BitcodeWriter.cpp @@ -11,24 +11,30 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Bitcode/ReaderWriter.h" #include "ValueEnumerator.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Triple.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/BlockFrequencyInfoImpl.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/Bitcode/BitstreamWriter.h" #include "llvm/Bitcode/LLVMBitCodes.h" +#include "llvm/Bitcode/ReaderWriter.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/InlineAsm.h" #include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" #include "llvm/IR/UseListOrder.h" #include "llvm/IR/ValueSymbolTable.h" +#include "llvm/ProfileData/ProfileCommon.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" @@ -591,11 +597,7 @@ /// Write a record that will eventually hold the word offset of the /// module-level VST. For now the offset is 0, which will be backpatched /// after the real VST is written. Returns the bit offset to backpatch. -static uint64_t WriteValueSymbolTableForwardDecl(const ValueSymbolTable &VST, - BitstreamWriter &Stream) { - if (VST.empty()) - return 0; - +static uint64_t WriteValueSymbolTableForwardDecl(BitstreamWriter &Stream) { // Write a placeholder value in for the offset of the real VST, // which is written after the function blocks so that it can include // the offset of each function. The placeholder offset will be @@ -844,8 +846,9 @@ Vals.clear(); } - uint64_t VSTOffsetPlaceholder = - WriteValueSymbolTableForwardDecl(M->getValueSymbolTable(), Stream); + uint64_t VSTOffsetPlaceholder = 0; + if (!M->getValueSymbolTable().empty()) + VSTOffsetPlaceholder = WriteValueSymbolTableForwardDecl(Stream); return VSTOffsetPlaceholder; } @@ -2248,8 +2251,8 @@ const ValueSymbolTable &VST, const ValueEnumerator &VE, BitstreamWriter &Stream, uint64_t VSTOffsetPlaceholder = 0, uint64_t BitcodeStartBit = 0, - DenseMap> *FunctionIndex = - nullptr) { + DenseMap> + *FunctionIndex = nullptr) { if (VST.empty()) { // WriteValueSymbolTableForwardDecl should have returned early as // well. Ensure this handling remains in sync by asserting that @@ -2343,7 +2346,6 @@ // Save the word offset of the function (from the start of the // actual bitcode written to the stream). - assert(FunctionIndex->count(F) == 1); uint64_t BitcodeIndex = (*FunctionIndex)[F]->bitcodeIndex() - BitcodeStartBit; assert((BitcodeIndex & 31) == 0 && "function block not 32-bit aligned"); @@ -2375,33 +2377,61 @@ /// Emit function names and summary offsets for the combined index /// used by ThinLTO. -static void WriteCombinedValueSymbolTable(const FunctionInfoIndex &Index, - BitstreamWriter &Stream) { +static void +WriteCombinedValueSymbolTable(const FunctionInfoIndex &Index, + BitstreamWriter &Stream, + std::map &GUIDToValueIdMap, + uint64_t VSTOffsetPlaceholder) { + assert(VSTOffsetPlaceholder > 0 && "Expected non-zero VSTOffsetPlaceholder"); + // Get the offset of the VST we are writing, and backpatch it into + // the VST forward declaration record. + uint64_t VSTOffset = Stream.GetCurrentBitNo(); + assert((VSTOffset & 31) == 0 && "VST block not 32-bit aligned"); + Stream.BackpatchWord(VSTOffsetPlaceholder, VSTOffset / 32); + Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 4); BitCodeAbbrev *Abbv = new BitCodeAbbrev(); - Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_FNENTRY)); - Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcsumoffset - Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcguid - unsigned FnEntryAbbrev = Stream.EmitAbbrev(Abbv); + Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_GVDEFENTRY)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // sumoffset + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // guid + unsigned DefEntryAbbrev = Stream.EmitAbbrev(Abbv); + + Abbv = new BitCodeAbbrev(); + Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_ENTRY)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // refguid + unsigned EntryAbbrev = Stream.EmitAbbrev(Abbv); SmallVector NameVals; for (const auto &FII : Index) { + uint64_t FuncGUID = FII.first; + const auto &VMI = GUIDToValueIdMap.find(FuncGUID); + assert(VMI != GUIDToValueIdMap.end()); + for (const auto &FI : FII.second) { + // VST_CODE_COMBINED_GVDEFENTRY: [valueid, sumoffset, guid] + NameVals.push_back(VMI->second); NameVals.push_back(FI->bitcodeIndex()); - - uint64_t FuncGUID = FII.first; - - // VST_CODE_COMBINED_FNENTRY: [funcsumoffset, funcguid] - unsigned AbbrevToUse = FnEntryAbbrev; - NameVals.push_back(FuncGUID); // Emit the finished record. - Stream.EmitRecord(bitc::VST_CODE_COMBINED_FNENTRY, NameVals, AbbrevToUse); + Stream.EmitRecord(bitc::VST_CODE_COMBINED_GVDEFENTRY, NameVals, + DefEntryAbbrev); NameVals.clear(); } + GUIDToValueIdMap.erase(VMI); + } + for (const auto &GVI : GUIDToValueIdMap) { + // VST_CODE_COMBINED_ENTRY: [valueid, refguid] + NameVals.push_back(GVI.second); + NameVals.push_back(GVI.first); + + // Emit the finished record. + Stream.EmitRecord(bitc::VST_CODE_COMBINED_ENTRY, NameVals, EntryAbbrev); + NameVals.clear(); } Stream.ExitBlock(); } @@ -2440,34 +2470,45 @@ Stream.ExitBlock(); } -/// \brief Save information for the given function into the function index. -/// -/// At a minimum this saves the bitcode index of the function record that -/// was just written. However, if we are emitting function summary information, -/// for example for ThinLTO, then a \a FunctionSummary object is created -/// to hold the provided summary information. -static void SaveFunctionInfo( - const Function &F, - DenseMap> &FunctionIndex, - unsigned NumInsts, uint64_t BitcodeIndex, bool EmitFunctionSummary) { - std::unique_ptr FuncSummary; - if (EmitFunctionSummary) { - FuncSummary = llvm::make_unique(NumInsts); - FuncSummary->setFunctionLinkage(F.getLinkage()); +static void findRefEdges(const User *U, const ValueEnumerator &VE, + DenseSet &RefEdges, + SmallPtrSet &Visited) { + if (!Visited.insert(U).second) + return; + + for (const auto &OI : U->operands()) { + const User *U2 = dyn_cast(OI); + if (!U2) + continue; + if (isa(U2)) + continue; + if (!isa(U2)) { + findRefEdges(U2, VE, RefEdges, Visited); + continue; + } + RefEdges.insert(VE.getValueID(U2)); } - FunctionIndex[&F] = - llvm::make_unique(BitcodeIndex, std::move(FuncSummary)); } /// Emit a function body to the module stream. static void WriteFunction( - const Function &F, ValueEnumerator &VE, BitstreamWriter &Stream, - DenseMap> &FunctionIndex, - bool EmitFunctionSummary) { + const Function &F, const Module *M, ValueEnumerator &VE, + BitstreamWriter &Stream, + DenseMap> &FunctionIndex, + bool EmitSummaryIndex) { // Save the bitcode index of the start of this function block for recording // in the VST. uint64_t BitcodeIndex = Stream.GetCurrentBitNo(); + bool HasProfileData = F.getEntryCount().hasValue(); + std::unique_ptr BFI; + if (EmitSummaryIndex && HasProfileData) { + Function &Func = const_cast(F); + LoopInfo LI{DominatorTree(Func)}; + BranchProbabilityInfo BPI{Func, LI}; + BFI = llvm::make_unique(Func, BPI, LI); + } + Stream.EnterSubblock(bitc::FUNCTION_BLOCK_ID, 4); VE.incorporateFunction(F); @@ -2494,7 +2535,12 @@ DILocation *LastDL = nullptr; unsigned NumInsts = 0; + // Map from callee ValueId to profile count. Used to accumulate profile + // counts for all static calls to a given callee. + DenseMap CallGraphEdges; + DenseSet RefEdges; + SmallPtrSet Visited; // Finally, emit all the instructions, in order. for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); @@ -2507,6 +2553,29 @@ if (!I->getType()->isVoidTy()) ++InstID; + if (EmitSummaryIndex) { + findRefEdges(&*I, VE, RefEdges, Visited); + auto CS = ImmutableCallSite(&*I); + for (const auto &OI : I->operands()) { + if (CS && CS.isCallee(&OI)) { + auto CalledFunction = CS.getCalledFunction(); + if (CalledFunction && CalledFunction->hasName() && + !CalledFunction->isIntrinsic()) { + uint64_t ScaledCount = 0; + if (HasProfileData) + ScaledCount = getBlockProfileCount( + BFI->getBlockFreq(&(*BB)).getFrequency(), + BFI->getEntryFreq(), F.getEntryCount().getValue()); + unsigned CalleeId = VE.getValueID( + M->getValueSymbolTable().lookup(CalledFunction->getName())); + CallGraphEdges[CalleeId] += ScaledCount; + RefEdges.erase(CalleeId); + } + continue; + } + } + } + // If the instruction has metadata, write a metadata attachment later. NeedsMetadataAttachment |= I->hasMetadataOtherThanDebugLoc(); @@ -2531,6 +2600,17 @@ LastDL = DL; } + RefEdges.size(); + + std::unique_ptr FuncSummary; + if (EmitSummaryIndex) { + FuncSummary = llvm::make_unique(F.getLinkage(), NumInsts); + FuncSummary->addCallGraphEdges(CallGraphEdges); + FuncSummary->addRefEdges(RefEdges); + } + FunctionIndex[&F] = + llvm::make_unique(BitcodeIndex, std::move(FuncSummary)); + // Emit names for all the instructions etc. WriteValueSymbolTable(F.getValueSymbolTable(), VE, Stream); @@ -2540,9 +2620,6 @@ WriteUseListBlock(&F, VE, Stream); VE.purgeFunction(); Stream.ExitBlock(); - - SaveFunctionInfo(F, FunctionIndex, NumInsts, BitcodeIndex, - EmitFunctionSummary); } // Emit blockinfo, which defines the standard abbreviations etc. @@ -2776,34 +2853,99 @@ // Helper to emit a single function summary record. static void WritePerModuleFunctionSummaryRecord( - SmallVector &NameVals, FunctionSummary *FS, unsigned ValueID, - unsigned FSAbbrev, BitstreamWriter &Stream) { + SmallVector &NameVals, FunctionSummary *FS, unsigned ValueID, + unsigned FSCallsAbbrev, unsigned FSCallsProfileAbbrev, + BitstreamWriter &Stream, const Function &F) { assert(FS); NameVals.push_back(ValueID); - NameVals.push_back(getEncodedLinkage(FS->getFunctionLinkage())); + NameVals.push_back(getEncodedLinkage(FS->linkage())); NameVals.push_back(FS->instCount()); + NameVals.push_back(FS->refs().size()); + + for (auto &RI : FS->refs()) + NameVals.push_back(RI); + + bool HasProfileData = F.getEntryCount().hasValue(); + for (auto &ECI : FS->edges()) { + NameVals.push_back(ECI.first); + assert(ECI.second.CallsiteCount > 0 && "Expected at least one callsite"); + NameVals.push_back(ECI.second.CallsiteCount); + if (HasProfileData) + NameVals.push_back(ECI.second.ProfileCount); + } + + unsigned FSAbbrev = (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev); + unsigned Code = + (HasProfileData ? bitc::FS_PERMODULE_PROFILE : bitc::FS_PERMODULE); // Emit the finished record. - Stream.EmitRecord(bitc::FS_CODE_PERMODULE_ENTRY, NameVals, FSAbbrev); + Stream.EmitRecord(Code, NameVals, FSAbbrev); NameVals.clear(); } -/// Emit the per-module function summary section alongside the rest of +static void WriteModuleLevelReferences(const GlobalVariable &V, + const ValueEnumerator &VE, + SmallVector &NameVals, + unsigned FSModRefsAbbrev, + BitstreamWriter &Stream) { + DenseSet RefEdges; + SmallPtrSet Visited; + findRefEdges(&V, VE, RefEdges, Visited); + unsigned RefCount = RefEdges.size(); + if (RefCount) { + NameVals.push_back(VE.getValueID(&V)); + for (auto RefId : RefEdges) { + NameVals.push_back(RefId); + } + Stream.EmitRecord(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS, NameVals, + FSModRefsAbbrev); + NameVals.clear(); + } +} + +/// Emit the per-module summary section alongside the rest of /// the module's bitcode. -static void WritePerModuleFunctionSummary( - DenseMap> &FunctionIndex, +static void WritePerModuleGlobalValueSummary( + DenseMap> &FunctionIndex, const Module *M, const ValueEnumerator &VE, BitstreamWriter &Stream) { - Stream.EnterSubblock(bitc::FUNCTION_SUMMARY_BLOCK_ID, 3); + if (M->empty()) + return; + + Stream.EnterSubblock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID, 3); - // Abbrev for FS_CODE_PERMODULE_ENTRY. + // Abbrev for FS_PERMODULE. BitCodeAbbrev *Abbv = new BitCodeAbbrev(); - Abbv->Add(BitCodeAbbrevOp(bitc::FS_CODE_PERMODULE_ENTRY)); + Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE)); Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // instcount - unsigned FSAbbrev = Stream.EmitAbbrev(Abbv); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4)); // numrefs + // numrefs x valueid, n x (valueid, callsitecount) + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); + unsigned FSCallsAbbrev = Stream.EmitAbbrev(Abbv); - SmallVector NameVals; + // Abbrev for FS_PERMODULE_PROFILE. + Abbv = new BitCodeAbbrev(); + Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_PROFILE)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // instcount + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4)); // numrefs + // numrefs x valueid, n x (valueid, callsitecount, profilecount) + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); + unsigned FSCallsProfileAbbrev = Stream.EmitAbbrev(Abbv); + + // Abbrev for FS_PERMODULE_GLOBALVAR_INIT_REFS. + Abbv = new BitCodeAbbrev(); + Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array)); // valueids + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); + unsigned FSModRefsAbbrev = Stream.EmitAbbrev(Abbv); + + SmallVector NameVals; // Iterate over the list of functions instead of the FunctionIndex map to // ensure the ordering is stable. for (const Function &F : *M) { @@ -2817,9 +2959,9 @@ assert(FunctionIndex.count(&F) == 1); WritePerModuleFunctionSummaryRecord( - NameVals, FunctionIndex[&F]->functionSummary(), - VE.getValueID(M->getValueSymbolTable().lookup(F.getName())), FSAbbrev, - Stream); + NameVals, dyn_cast(FunctionIndex[&F]->summary()), + VE.getValueID(M->getValueSymbolTable().lookup(F.getName())), + FSCallsAbbrev, FSCallsProfileAbbrev, Stream, F); } for (const GlobalAlias &A : M->aliases()) { @@ -2830,10 +2972,25 @@ continue; assert(FunctionIndex.count(F) == 1); + FunctionSummary *FS = + dyn_cast(FunctionIndex[F]->summary()); + // Add the aliasee to the reference list of alias + FS->addRefEdge( + VE.getValueID(M->getValueSymbolTable().lookup(A.getName()))); WritePerModuleFunctionSummaryRecord( - NameVals, FunctionIndex[F]->functionSummary(), - VE.getValueID(M->getValueSymbolTable().lookup(A.getName())), FSAbbrev, - Stream); + NameVals, FS, + VE.getValueID(M->getValueSymbolTable().lookup(A.getName())), + FSCallsAbbrev, FSCallsProfileAbbrev, Stream, *F); + } + + // Capture references from GlobalVariable initializers, which are outside + // of a function scope. + for (const GlobalVariable &G : M->globals()) + WriteModuleLevelReferences(G, VE, NameVals, FSModRefsAbbrev, Stream); + for (const GlobalAlias &A : M->aliases()) { + const auto *GV = dyn_cast(A.getBaseObject()); + if (GV) + WriteModuleLevelReferences(*GV, VE, NameVals, FSModRefsAbbrev, Stream); } Stream.ExitBlock(); @@ -2841,35 +2998,130 @@ /// Emit the combined function summary section into the combined index /// file. -static void WriteCombinedFunctionSummary(const FunctionInfoIndex &I, - BitstreamWriter &Stream) { - Stream.EnterSubblock(bitc::FUNCTION_SUMMARY_BLOCK_ID, 3); +static void WriteCombinedGlobalValueSummary( + const FunctionInfoIndex &I, BitstreamWriter &Stream, + std::map &GUIDToValueIdMap, unsigned GlobalValueId) { + Stream.EnterSubblock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID, 3); - // Abbrev for FS_CODE_COMBINED_ENTRY. + // Abbrev for FS_COMBINED. BitCodeAbbrev *Abbv = new BitCodeAbbrev(); - Abbv->Add(BitCodeAbbrevOp(bitc::FS_CODE_COMBINED_ENTRY)); - Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // modid + Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // modid Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage - Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // instcount - unsigned FSAbbrev = Stream.EmitAbbrev(Abbv); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // instcount + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4)); // numrefs + // numrefs x valueid, n x (valueid, callsitecount) + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); + unsigned FSCallsAbbrev = Stream.EmitAbbrev(Abbv); - SmallVector NameVals; + // Abbrev for FS_COMBINED_PROFILE. + Abbv = new BitCodeAbbrev(); + Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_PROFILE)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // modid + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // instcount + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4)); // numrefs + // numrefs x valueid, n x (valueid, callsitecount, profilecount) + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); + unsigned FSCallsProfileAbbrev = Stream.EmitAbbrev(Abbv); + + // Abbrev for FS_COMBINED_GLOBALVAR_INIT_REFS. + Abbv = new BitCodeAbbrev(); + Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_GLOBALVAR_INIT_REFS)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // modid + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array)); // valueids + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); + unsigned FSModRefsAbbrev = Stream.EmitAbbrev(Abbv); + + SmallVector NameVals; for (const auto &FII : I) { for (auto &FI : FII.second) { - FunctionSummary *FS = FI->functionSummary(); - assert(FS); + GlobalValueSummary *S = FI->summary(); + assert(S); + + if (auto *VS = dyn_cast(S)) { + assert(!VS->refs().empty() && "Expected at least one ref edge"); + NameVals.push_back(I.getModuleId(VS->modulePath())); + for (auto &RI : VS->refs()) { + const auto &VMI = GUIDToValueIdMap.find(RI); + unsigned RefId; + // If this GUID doesn't have an entry, assign one. + if (VMI == GUIDToValueIdMap.end()) { + GUIDToValueIdMap[RI] = ++GlobalValueId; + RefId = GlobalValueId; + } else { + RefId = VMI->second; + } + NameVals.push_back(RefId); + } + // Record the starting offset of this summary entry for use + // in the VST entry. Add the current code size since the + // reader will invoke readRecord after the abbrev id read. + FI->setBitcodeIndex(Stream.GetCurrentBitNo() + + Stream.GetAbbrevIDWidth()); + + // Emit the finished record. + Stream.EmitRecord(bitc::FS_COMBINED_GLOBALVAR_INIT_REFS, NameVals, + FSModRefsAbbrev); + NameVals.clear(); + continue; + } + + auto *FS = dyn_cast(S); + assert(FS); NameVals.push_back(I.getModuleId(FS->modulePath())); - NameVals.push_back(getEncodedLinkage(FS->getFunctionLinkage())); + NameVals.push_back(getEncodedLinkage(FS->linkage())); NameVals.push_back(FS->instCount()); + NameVals.push_back(FS->refs().size()); + + for (auto &RI : FS->refs()) { + const auto &VMI = GUIDToValueIdMap.find(RI); + unsigned RefId; + // If this GUID doesn't have an entry, assign one. + if (VMI == GUIDToValueIdMap.end()) { + GUIDToValueIdMap[RI] = ++GlobalValueId; + RefId = GlobalValueId; + } else { + RefId = VMI->second; + } + NameVals.push_back(RefId); + } + + bool HasProfileData = false; + for (auto &EI : FS->edges()) { + HasProfileData |= EI.second.ProfileCount != 0; + if (HasProfileData) + break; + } + + for (auto &EI : FS->edges()) { + const auto &VMI = GUIDToValueIdMap.find(EI.first); + // If this GUID doesn't have an entry, it doesn't have a function + // summary and we don't need to record any calls to it. + if (VMI == GUIDToValueIdMap.end()) + continue; + NameVals.push_back(VMI->second); + assert(EI.second.CallsiteCount > 0 && "Expected at least one callsite"); + NameVals.push_back(EI.second.CallsiteCount); + if (HasProfileData) + NameVals.push_back(EI.second.ProfileCount); + } // Record the starting offset of this summary entry for use // in the VST entry. Add the current code size since the // reader will invoke readRecord after the abbrev id read. FI->setBitcodeIndex(Stream.GetCurrentBitNo() + Stream.GetAbbrevIDWidth()); + unsigned FSAbbrev = + (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev); + unsigned Code = + (HasProfileData ? bitc::FS_COMBINED_PROFILE : bitc::FS_COMBINED); + // Emit the finished record. - Stream.EmitRecord(bitc::FS_CODE_COMBINED_ENTRY, NameVals, FSAbbrev); + Stream.EmitRecord(Code, NameVals, FSAbbrev); NameVals.clear(); } } @@ -2904,7 +3156,7 @@ /// WriteModule - Emit the specified module to the bitstream. static void WriteModule(const Module *M, BitstreamWriter &Stream, bool ShouldPreserveUseListOrder, - uint64_t BitcodeStartBit, bool EmitFunctionSummary) { + uint64_t BitcodeStartBit, bool EmitSummaryIndex) { Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3); SmallVector Vals; @@ -2949,15 +3201,15 @@ WriteOperandBundleTags(M, Stream); // Emit function bodies. - DenseMap> FunctionIndex; + DenseMap> FunctionIndex; for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) if (!F->isDeclaration()) - WriteFunction(*F, VE, Stream, FunctionIndex, EmitFunctionSummary); + WriteFunction(*F, M, VE, Stream, FunctionIndex, EmitSummaryIndex); // Need to write after the above call to WriteFunction which populates // the summary information in the index. - if (EmitFunctionSummary) - WritePerModuleFunctionSummary(FunctionIndex, M, VE, Stream); + if (EmitSummaryIndex) + WritePerModuleGlobalValueSummary(FunctionIndex, M, VE, Stream); WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream, VSTOffsetPlaceholder, BitcodeStartBit, &FunctionIndex); @@ -3046,7 +3298,7 @@ /// stream. void llvm::WriteBitcodeToFile(const Module *M, raw_ostream &Out, bool ShouldPreserveUseListOrder, - bool EmitFunctionSummary) { + bool EmitSummaryIndex) { SmallVector Buffer; Buffer.reserve(256*1024); @@ -3072,7 +3324,7 @@ // Emit the module. WriteModule(M, Stream, ShouldPreserveUseListOrder, BitcodeStartBit, - EmitFunctionSummary); + EmitSummaryIndex); } if (TT.isOSDarwin() || TT.isOSBinFormatMachO()) @@ -3082,11 +3334,10 @@ Out.write((char*)&Buffer.front(), Buffer.size()); } -// Write the specified function summary index to the given raw output stream, +// Write the specified module summary index to the given raw output stream, // where it will be written in a new bitcode block. This is used when // writing the combined index file for ThinLTO. -void llvm::WriteFunctionSummaryToFile(const FunctionInfoIndex &Index, - raw_ostream &Out) { +void llvm::WriteIndexToFile(const FunctionInfoIndex &Index, raw_ostream &Out) { SmallVector Buffer; Buffer.reserve(256 * 1024); @@ -3102,15 +3353,28 @@ Vals.push_back(CurVersion); Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals); + uint64_t VSTOffsetPlaceholder = WriteValueSymbolTableForwardDecl(Stream); + // Write the module paths in the combined index. WriteModStrings(Index, Stream); - // Write the function summary combined index records. - WriteCombinedFunctionSummary(Index, Stream); + // Assign unique value ids to all functions in the index for use + // in writing out the call graph edges. Save the mapping from GUID + // to the new global value id to use when writing those edges, which + // are currently saved in the index in terms of GUID. + std::map GUIDToValueIdMap; + unsigned GlobalValueId = 0; + for (auto &II : Index) + GUIDToValueIdMap[II.first] = ++GlobalValueId; + + // Write the summary combined index records. + WriteCombinedGlobalValueSummary(Index, Stream, GUIDToValueIdMap, + GlobalValueId); // Need a special VST writer for the combined index (we don't have a // real VST and real values when this is invoked). - WriteCombinedValueSymbolTable(Index, Stream); + WriteCombinedValueSymbolTable(Index, Stream, GUIDToValueIdMap, + VSTOffsetPlaceholder); Stream.ExitBlock(); Index: lib/Bitcode/Writer/LLVMBuild.txt =================================================================== --- lib/Bitcode/Writer/LLVMBuild.txt +++ lib/Bitcode/Writer/LLVMBuild.txt @@ -19,4 +19,4 @@ type = Library name = BitWriter parent = Bitcode -required_libraries = Core Support +required_libraries = Analysis Core Support Index: lib/IR/FunctionInfo.cpp =================================================================== --- lib/IR/FunctionInfo.cpp +++ lib/IR/FunctionInfo.cpp @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// // -// This file implements the function info index and summary classes for the +// This file implements the module index and summary classes for the // IR library. // //===----------------------------------------------------------------------===// @@ -16,42 +16,41 @@ #include "llvm/ADT/StringMap.h" using namespace llvm; -// Create the combined function index/summary from multiple +// Create the combined module index/summary from multiple // per-module instances. void FunctionInfoIndex::mergeFrom(std::unique_ptr Other, uint64_t NextModuleId) { StringRef ModPath; - for (auto &OtherFuncInfoLists : *Other) { - uint64_t FuncGUID = OtherFuncInfoLists.first; - FunctionInfoList &List = OtherFuncInfoLists.second; + for (auto &OtherGlobalValInfoLists : *Other) { + uint64_t ValueGUID = OtherGlobalValInfoLists.first; + GlobalValueInfoList &List = OtherGlobalValInfoLists.second; - // Assert that the func info list only has one entry, since we shouldn't + // Assert that the value info list only has one entry, since we shouldn't // have duplicate names within a single per-module index. assert(List.size() == 1); - std::unique_ptr Info = std::move(List.front()); + std::unique_ptr Info = std::move(List.front()); - // Skip if there was no function summary section. - if (!Info->functionSummary()) + // Skip if there was no summary section. + if (!Info->summary()) continue; // Add the module path string ref for this module if we haven't already // saved a reference to it. if (ModPath.empty()) - ModPath = - addModulePath(Info->functionSummary()->modulePath(), NextModuleId); + ModPath = addModulePath(Info->summary()->modulePath(), NextModuleId); else - assert(ModPath == Info->functionSummary()->modulePath() && + assert(ModPath == Info->summary()->modulePath() && "Each module in the combined map should have a unique ID"); // Note the module path string ref was copied above and is still owned by // the original per-module index. Reset it to the new module path // string reference owned by the combined index. - Info->functionSummary()->setModulePath(ModPath); + Info->summary()->setModulePath(ModPath); - // Add new function info to existing list. There may be duplicates when - // combining FunctionMap entries, due to COMDAT functions. Any local - // functions were given unique global IDs. - addFunctionInfo(FuncGUID, std::move(Info)); + // Add new value info to existing list. There may be duplicates when + // combining GlobalValueMap entries, due to COMDAT values. Any local + // values were given unique global IDs. + addGlobalValueInfo(ValueGUID, std::move(Info)); } } Index: lib/Object/FunctionIndexObjectFile.cpp =================================================================== --- lib/Object/FunctionIndexObjectFile.cpp +++ lib/Object/FunctionIndexObjectFile.cpp @@ -66,15 +66,15 @@ } } -// Looks for function index in the given memory buffer. +// Looks for module summary index in the given memory buffer. // returns true if found, else false. -bool FunctionIndexObjectFile::hasFunctionSummaryInMemBuffer( +bool FunctionIndexObjectFile::hasGlobalValueSummaryInMemBuffer( MemoryBufferRef Object, DiagnosticHandlerFunction DiagnosticHandler) { ErrorOr BCOrErr = findBitcodeInMemBuffer(Object); if (!BCOrErr) return false; - return hasFunctionSummary(BCOrErr.get(), DiagnosticHandler); + return hasGlobalValueSummary(BCOrErr.get(), DiagnosticHandler); } // Parse function index in the given memory buffer. Index: lib/Transforms/IPO/FunctionImport.cpp =================================================================== --- lib/Transforms/IPO/FunctionImport.cpp +++ lib/Transforms/IPO/FunctionImport.cpp @@ -205,7 +205,7 @@ << "\n"); // Try to get a summary for this function call. - auto InfoList = Index.findFunctionInfoList(CalledFunctionName); + auto InfoList = Index.findGlobalValueInfoList(CalledFunctionName); if (InfoList == Index.end()) { DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": No summary for " << CalledFunctionName << " Ignoring.\n"); @@ -217,7 +217,7 @@ auto &Info = InfoList->second[0]; assert(Info && "Nullptr in list, error importing summaries?\n"); - auto *Summary = Info->functionSummary(); + auto *Summary = dyn_cast(Info->summary()); if (!Summary) { // FIXME: in case we are lazyloading summaries, we can do it now. DEBUG(dbgs() << DestModule.getModuleIdentifier() Index: test/Bitcode/Inputs/thinlto-function-summary-callgraph-pgo.ll =================================================================== --- /dev/null +++ test/Bitcode/Inputs/thinlto-function-summary-callgraph-pgo.ll @@ -0,0 +1,11 @@ +; ModuleID = 'thinlto-function-summary-callgraph2.ll' +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: nounwind uwtable +define void @func() #0 !prof !2 { +entry: + ret void +} + +!2 = !{!"function_entry_count", i64 1} Index: test/Bitcode/Inputs/thinlto-function-summary-callgraph.ll =================================================================== --- /dev/null +++ test/Bitcode/Inputs/thinlto-function-summary-callgraph.ll @@ -0,0 +1,10 @@ +; ModuleID = 'thinlto-function-summary-callgraph2.ll' +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: nounwind uwtable +define void @func() #0 { +entry: + ret void +} + Index: test/Bitcode/thinlto-function-summary-callgraph-pgo.ll =================================================================== --- /dev/null +++ test/Bitcode/thinlto-function-summary-callgraph-pgo.ll @@ -0,0 +1,43 @@ +; RUN: llvm-as -function-summary %s -o %t.o +; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s +; RUN: llvm-as -function-summary %p/Inputs/thinlto-function-summary-callgraph.ll -o %t2.o +; RUN: llvm-lto -thinlto -o %t3 %t.o %t2.o +; RUN: llvm-bcanalyzer -dump %t3.thinlto.bc | FileCheck %s --check-prefix=COMBINED + +; CHECK: +; CHECK-NEXT: +; CHECK-NEXT: + +; COMBINED: +; COMBINED-NEXT: +; COMBINED-NEXT: +; COMBINED-NEXT: + +; ModuleID = 'thinlto-function-summary-callgraph.ll' +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: nounwind uwtable +define i32 @main() #0 !prof !2 { +entry: + call void (...) @func() + ret i32 0 +} + +declare void @func(...) #1 + +!2 = !{!"function_entry_count", i64 1} Index: test/Bitcode/thinlto-function-summary-callgraph.ll =================================================================== --- /dev/null +++ test/Bitcode/thinlto-function-summary-callgraph.ll @@ -0,0 +1,41 @@ +; RUN: llvm-as -function-summary %s -o %t.o +; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s +; RUN: llvm-as -function-summary %p/Inputs/thinlto-function-summary-callgraph.ll -o %t2.o +; RUN: llvm-lto -thinlto -o %t3 %t.o %t2.o +; RUN: llvm-bcanalyzer -dump %t3.thinlto.bc | FileCheck %s --check-prefix=COMBINED + +; CHECK: +; CHECK-NEXT: +; CHECK-NEXT: + +; COMBINED: +; COMBINED-NEXT: +; COMBINED-NEXT: +; COMBINED-NEXT: + +; ModuleID = 'thinlto-function-summary-callgraph.ll' +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: nounwind uwtable +define i32 @main() #0 { +entry: + call void (...) @func() + ret i32 0 +} + +declare void @func(...) #1 Index: test/Bitcode/thinlto-function-summary.ll =================================================================== --- test/Bitcode/thinlto-function-summary.ll +++ test/Bitcode/thinlto-function-summary.ll @@ -4,11 +4,11 @@ ; Check the value ids in the function summary entries against the ; same in the ValueSumbolTable, to ensure the ordering is stable. ; Also check the linkage field on the summary entries. -; BC: record string = 'foo' ; BC-NEXT: record string = 'bar' Index: test/Bitcode/thinlto-summary-linkage-types.ll =================================================================== --- test/Bitcode/thinlto-summary-linkage-types.ll +++ test/Bitcode/thinlto-summary-linkage-types.ll @@ -5,57 +5,57 @@ ; RUN: llvm-bcanalyzer -dump %t2.thinlto.bc | FileCheck %s --check-prefix=COMBINED define private void @private() -; CHECK: (nullptr); @@ -1188,7 +1188,7 @@ if (EC) message(LDPL_FATAL, "Unable to open %s.thinlto.bc for writing: %s", output_name.data(), EC.message().c_str()); - WriteFunctionSummaryToFile(CombinedIndex, OS); + WriteIndexToFile(CombinedIndex, OS); OS.close(); if (options::thinlto_index_only) { Index: tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp =================================================================== --- tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp +++ tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp @@ -117,8 +117,8 @@ case bitc::METADATA_KIND_BLOCK_ID: return "METADATA_KIND_BLOCK"; case bitc::METADATA_ATTACHMENT_ID: return "METADATA_ATTACHMENT_BLOCK"; case bitc::USELIST_BLOCK_ID: return "USELIST_BLOCK_ID"; - case bitc::FUNCTION_SUMMARY_BLOCK_ID: - return "FUNCTION_SUMMARY_BLOCK"; + case bitc::GLOBALVAL_SUMMARY_BLOCK_ID: + return "GLOBALVAL_SUMMARY_BLOCK"; case bitc::MODULE_STRTAB_BLOCK_ID: return "MODULE_STRTAB_BLOCK"; } } @@ -280,7 +280,8 @@ STRINGIFY_CODE(VST_CODE, ENTRY) STRINGIFY_CODE(VST_CODE, BBENTRY) STRINGIFY_CODE(VST_CODE, FNENTRY) - STRINGIFY_CODE(VST_CODE, COMBINED_FNENTRY) + STRINGIFY_CODE(VST_CODE, COMBINED_GVDEFENTRY) + STRINGIFY_CODE(VST_CODE, COMBINED_ENTRY) } case bitc::MODULE_STRTAB_BLOCK_ID: switch (CodeID) { @@ -288,12 +289,16 @@ return nullptr; STRINGIFY_CODE(MST_CODE, ENTRY) } - case bitc::FUNCTION_SUMMARY_BLOCK_ID: + case bitc::GLOBALVAL_SUMMARY_BLOCK_ID: switch (CodeID) { default: return nullptr; - STRINGIFY_CODE(FS_CODE, PERMODULE_ENTRY) - STRINGIFY_CODE(FS_CODE, COMBINED_ENTRY) + STRINGIFY_CODE(FS, PERMODULE) + STRINGIFY_CODE(FS, PERMODULE_PROFILE) + STRINGIFY_CODE(FS, PERMODULE_GLOBALVAR_INIT_REFS) + STRINGIFY_CODE(FS, COMBINED) + STRINGIFY_CODE(FS, COMBINED_PROFILE) + STRINGIFY_CODE(FS, COMBINED_GLOBALVAR_INIT_REFS) } case bitc::METADATA_ATTACHMENT_ID: switch(CodeID) { Index: tools/llvm-lto/llvm-lto.cpp =================================================================== --- tools/llvm-lto/llvm-lto.cpp +++ tools/llvm-lto/llvm-lto.cpp @@ -237,7 +237,7 @@ raw_fd_ostream OS(OutputFilename + ".thinlto.bc", EC, sys::fs::OpenFlags::F_None); error(EC, "error opening the file '" + OutputFilename + ".thinlto.bc'"); - WriteFunctionSummaryToFile(CombinedIndex, OS); + WriteIndexToFile(CombinedIndex, OS); OS.close(); }