Index: include/llvm/Analysis/ModuleSummaryAnalysis.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ModuleSummaryAnalysis.h @@ -0,0 +1,88 @@ +//===- ModuleSummaryAnalysis.h - Module summary index builder ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This is the interface to build a ModuleSummaryIndex for a module. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_MODULESUMMARYANALYSIS_H +#define LLVM_ANALYSIS_MODULESUMMARYANALYSIS_H + +#include "llvm/ADT/STLExtras.h" +#include "llvm/IR/ModuleSummaryIndex.h" +#include "llvm/Pass.h" + +namespace llvm { + +class BlockFrequencyInfo; + +/// Class to build a module summary index for the given Module, possibly from +/// a Pass. +class ModuleSummaryIndexBuilder { + /// The index being built + std::unique_ptr Index; + /// The module for which we are building an index + const Module *M; + /// Map of aliasee to all of its aliases. + DenseMap> AliasMap; + +public: + /// Default constructor + ModuleSummaryIndexBuilder() = default; + + /// Constructor that builds an index for the given Module. + ModuleSummaryIndexBuilder(const Module *M, Pass *P = nullptr); + + /// Get a reference to the index owned by builder + ModuleSummaryIndex &getIndex() const { return *Index; } + + /// Take ownership of the built index + std::unique_ptr takeIndex() { return std::move(Index); } + +private: + /// Compute info for given function with optional frequency information + std::unique_ptr + computeFunctionInfo(const Function &F, BlockFrequencyInfo *BFI = nullptr); + + /// Compute info for given variable with optional frequency information + std::unique_ptr computeVariableInfo(const GlobalVariable &V); + + /// Clone the given info to all aliases of GV + void cloneToAliases(const GlobalValue &GV, const GlobalValueInfo &GVInfo); +}; + +/// Legacy wrapper pass to provide the ModuleSummaryIndex object. +class ModuleSummaryIndexWrapperPass : public ModulePass { + std::unique_ptr IndexBuilder; + +public: + static char ID; + + ModuleSummaryIndexWrapperPass(); + + /// Get the index built by pass + ModuleSummaryIndex &getIndex() { return IndexBuilder->getIndex(); } + const ModuleSummaryIndex &getIndex() const { + return IndexBuilder->getIndex(); + } + + bool runOnModule(Module &M) override; + bool doFinalization(Module &M) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +//===--------------------------------------------------------------------===// +// +// createModuleSummaryIndexWrapperPass - This pass builds a ModuleSummaryIndex +// object for the module, to be written to bitcode or LLVM assembly. +// +ModulePass *createModuleSummaryIndexWrapperPass(); +} + +#endif Index: include/llvm/Bitcode/ReaderWriter.h =================================================================== --- include/llvm/Bitcode/ReaderWriter.h +++ include/llvm/Bitcode/ReaderWriter.h @@ -107,7 +107,7 @@ /// for use in ThinLTO optimization). void WriteBitcodeToFile(const Module *M, raw_ostream &Out, bool ShouldPreserveUseListOrder = false, - bool EmitSummaryIndex = false, + const ModuleSummaryIndex *Index = nullptr, bool GenerateHash = false); /// Write the specified module summary index to the given raw output stream, Index: include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- include/llvm/IR/ModuleSummaryIndex.h +++ include/llvm/IR/ModuleSummaryIndex.h @@ -18,6 +18,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringMap.h" #include "llvm/IR/Function.h" @@ -46,6 +47,43 @@ } }; +/// Struct to hold value either by GUID or Value*, depending on whether this +/// is a combined or per-module index, respectively. +struct ValueInfo { + /// The value representation used in this instance. + enum ValueInfoKind { + VI_Id, + VI_Value, + }; + + /// Union of the two possible value types. + union ValueUnion { + GlobalValue::GUID Id; + const Value *V; + ValueUnion(GlobalValue::GUID Id) : Id(Id) {} + ValueUnion(const Value *V) : V(V) {} + }; + + /// The value being represented. + ValueUnion TheValue; + /// The value representation. + ValueInfoKind Kind; + /// Constructor for a GUID value + ValueInfo(GlobalValue::GUID Id = 0) : TheValue(Id), Kind(VI_Id) {} + /// Constructor for a Value* value + ValueInfo(const Value *V) : TheValue(V), Kind(VI_Value) {} + /// Accessor for GUID value + GlobalValue::GUID getId() const { + assert(Kind == VI_Id && "Not an Id type"); + return TheValue.Id; + } + /// Accessor for Value* value + const Value *getValue() const { + assert(Kind == VI_Value && "Not a Value type"); + return TheValue.V; + } +}; + /// \brief Function and variable summary information to aid decisions and /// implementation of importing. /// @@ -78,11 +116,11 @@ /// types based on global summary-based analysis. GlobalValue::LinkageTypes Linkage; - /// List of GUIDs of values referenced by this global value's definition + /// List 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; + std::vector RefEdgeList; protected: /// GlobalValueSummary constructor. @@ -92,6 +130,11 @@ public: virtual ~GlobalValueSummary() = default; + /// Support deep copy + virtual std::unique_ptr clone() { + return llvm::make_unique(*this); + } + /// Which kind of summary subclass this is. SummaryKind getSummaryKind() const { return Kind; } @@ -109,31 +152,35 @@ /// by \p RefGUID. void addRefEdge(GlobalValue::GUID RefGUID) { RefEdgeList.push_back(RefGUID); } + /// Record a reference from this global value to the global value identified + /// by \p RefV. + void addRefEdge(const Value *RefV) { RefEdgeList.push_back(RefV); } + /// Record a reference from this global value to each global value identified /// in \p RefEdges. - void addRefEdges(DenseSet &RefEdges) { + void addRefEdges(DenseSet &RefEdges) { for (auto &RI : RefEdges) addRefEdge(RI); } - /// Return the list of GUIDs referenced by this global value definition. - std::vector &refs() { return RefEdgeList; } - const std::vector &refs() const { return RefEdgeList; } + /// Return the list of values 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; + /// call edge pair. + typedef std::pair EdgeTy; private: /// Number of instructions (ignoring debug instructions, e.g.) computed /// during the initial compile step when the summary index is first built. unsigned InstCount; - /// List of call edge pairs from this function. + /// List of call edge pairs from this function. std::vector CallGraphEdgeList; public: @@ -141,6 +188,11 @@ FunctionSummary(GlobalValue::LinkageTypes Linkage, unsigned NumInsts) : GlobalValueSummary(FunctionKind, Linkage), InstCount(NumInsts) {} + /// Support deep copy + std::unique_ptr clone() { + return llvm::make_unique(*this); + } + /// Check if this is a function summary. static bool classof(const GlobalValueSummary *GVS) { return GVS->getSummaryKind() == FunctionKind; @@ -156,14 +208,21 @@ CallGraphEdgeList.push_back(std::make_pair(CalleeGUID, Info)); } + /// Record a call graph edge from this function to the function identified + /// by \p CalleeV, with \p CalleeInfo including the cumulative profile + /// count (across all calls from this function) or 0 if no PGO. + void addCallGraphEdge(const Value *CalleeV, CalleeInfo Info) { + CallGraphEdgeList.push_back(std::make_pair(CalleeV, Info)); + } + /// Record a call graph edge from this function to each function recorded /// in \p CallGraphEdges. - void addCallGraphEdges(DenseMap &CallGraphEdges) { + void addCallGraphEdges(DenseMap &CallGraphEdges) { for (auto &EI : CallGraphEdges) addCallGraphEdge(EI.first, EI.second); } - /// Return the list of pairs. + /// Return the list of pairs. std::vector &calls() { return CallGraphEdgeList; } const std::vector &calls() const { return CallGraphEdgeList; } }; @@ -181,6 +240,11 @@ GlobalVarSummary(GlobalValue::LinkageTypes Linkage) : GlobalValueSummary(GlobalVarKind, Linkage) {} + /// Support deep copy + std::unique_ptr clone() { + return llvm::make_unique(*this); + } + /// Check if this is a global variable summary. static bool classof(const GlobalValueSummary *GVS) { return GVS->getSummaryKind() == GlobalVarKind; @@ -214,6 +278,10 @@ std::unique_ptr Summary = nullptr) : Summary(std::move(Summary)), BitcodeIndex(Offset) {} + /// Make a deep copy + GlobalValueInfo(const GlobalValueInfo &GVI) + : Summary(GVI.summary()->clone()), BitcodeIndex(GVI.bitcodeIndex()) {} + /// Record the summary information parsed out of the summary block during /// parsing or combined index creation. void setSummary(std::unique_ptr GVSummary) { Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -198,6 +198,7 @@ void initializeMachineBlockPlacementStatsPass(PassRegistry&); void initializeMachineBranchProbabilityInfoPass(PassRegistry&); void initializeMachineCSEPass(PassRegistry&); +void initializeModuleSummaryIndexWrapperPassPass(PassRegistry &); void initializeImplicitNullChecksPass(PassRegistry&); void initializeMachineDominatorTreePass(PassRegistry&); void initializeMachineDominanceFrontierPass(PassRegistry&); @@ -313,6 +314,7 @@ void initializeLoadCombinePass(PassRegistry&); void initializeRewriteSymbolsPass(PassRegistry&); void initializeWinEHPreparePass(PassRegistry&); +void initializeWriteBitcodePassPass(PassRegistry &); void initializePlaceBackedgeSafepointsImplPass(PassRegistry&); void initializePlaceSafepointsPass(PassRegistry&); void initializeDwarfEHPreparePass(PassRegistry&); Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -60,6 +60,7 @@ initializeMemDerefPrinterPass(Registry); initializeMemoryDependenceWrapperPassPass(Registry); initializeModuleDebugInfoPrinterPass(Registry); + initializeModuleSummaryIndexWrapperPassPass(Registry); initializeObjCARCAAWrapperPassPass(Registry); initializePostDominatorTreeWrapperPassPass(Registry); initializeRegionInfoPassPass(Registry); Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -49,6 +49,7 @@ MemoryDependenceAnalysis.cpp MemoryLocation.cpp ModuleDebugInfoPrinter.cpp + ModuleSummaryAnalysis.cpp ObjCARCAliasAnalysis.cpp ObjCARCAnalysisUtils.cpp ObjCARCInstKind.cpp Index: lib/Analysis/ModuleSummaryAnalysis.cpp =================================================================== --- /dev/null +++ lib/Analysis/ModuleSummaryAnalysis.cpp @@ -0,0 +1,210 @@ +//===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass builds a ModuleSummaryIndex object for the module, to be written +// to bitcode or LLVM assembly. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/ModuleSummaryAnalysis.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/BlockFrequencyInfoImpl.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/ValueSymbolTable.h" +#include "llvm/Pass.h" +using namespace llvm; + +#define DEBUG_TYPE "module-summary-analysis" + +// Walk through the operands of a given User via worklist iteration and populate +// the set of GlobalValue references encountered. Invoked either on an +// Instruction or a GlobalVariable (which walks its initializer). +static void findRefEdges(const User *CurUser, DenseSet &RefEdges, + SmallPtrSet &Visited) { + SmallVector Worklist; + Worklist.push_back(CurUser); + + while (!Worklist.empty()) { + const User *U = Worklist.pop_back_val(); + + if (!Visited.insert(U).second) + continue; + + ImmutableCallSite CS(U); + + for (const auto &OI : U->operands()) { + const User *Operand = dyn_cast(OI); + if (!Operand) + continue; + if (isa(Operand)) + continue; + if (isa(Operand)) { + // We have a reference to a global value. This should be added to + // the reference set unless it is a callee. Callees are handled + // specially by WriteFunction and are added to a separate list. + if (!(CS && CS.isCallee(&OI))) + RefEdges.insert(Operand); + continue; + } + Worklist.push_back(Operand); + } + } +} + +std::unique_ptr +ModuleSummaryIndexBuilder::computeFunctionInfo(const Function &F, + BlockFrequencyInfo *BFI) { + 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; + for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) + for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; + ++I) { + if (!isa(I)) + ++NumInsts; + + if (auto CS = ImmutableCallSite(&*I)) { + auto *CalledFunction = CS.getCalledFunction(); + if (CalledFunction && CalledFunction->hasName() && + !CalledFunction->isIntrinsic()) { + auto ScaledCount = BFI ? BFI->getBlockProfileCount(&*BB) : None; + auto *CalleeId = + M->getValueSymbolTable().lookup(CalledFunction->getName()); + CallGraphEdges[CalleeId] += + (ScaledCount ? ScaledCount.getValue() : 0); + } + } + findRefEdges(&*I, RefEdges, Visited); + } + + std::unique_ptr FuncSummary = + llvm::make_unique(F.getLinkage(), NumInsts); + FuncSummary->addCallGraphEdges(CallGraphEdges); + FuncSummary->addRefEdges(RefEdges); + std::unique_ptr GVInfo = + llvm::make_unique(0, std::move(FuncSummary)); + return GVInfo; +} + +std::unique_ptr +ModuleSummaryIndexBuilder::computeVariableInfo(const GlobalVariable &V) { + DenseSet RefEdges; + SmallPtrSet Visited; + findRefEdges(&V, RefEdges, Visited); + std::unique_ptr GVarSummary = + llvm::make_unique(V.getLinkage()); + GVarSummary->addRefEdges(RefEdges); + std::unique_ptr GVInfo = + llvm::make_unique(0, std::move(GVarSummary)); + return GVInfo; +} + +void ModuleSummaryIndexBuilder::cloneToAliases(const GlobalValue &GV, + const GlobalValueInfo &GVInfo) { + // Make a copy for any aliases. + auto AMI = AliasMap.find(&GV); + if (AMI != AliasMap.end()) + for (auto *A : AMI->second) + Index->addGlobalValueInfo(A->getName(), + llvm::make_unique(GVInfo)); +} + +ModuleSummaryIndexBuilder::ModuleSummaryIndexBuilder(const Module *M, Pass *P) + : Index(llvm::make_unique()), M(M) { + for (const GlobalAlias &A : M->aliases()) + AliasMap[A.getBaseObject()].insert(&A); + + // Compute summaries for all functions defined in module, and save in the + // index for that function and any aliases. + for (auto &F : *M) { + if (F.isDeclaration()) + continue; + + BlockFrequencyInfo *BFI = nullptr; + std::unique_ptr BFIPtr; + if (P) + BFI = &(P->getAnalysis( + *const_cast(&F)) + .getBFI()); + else if (F.getEntryCount().hasValue()) { + Function &Func = const_cast(F); + LoopInfo LI{DominatorTree(Func)}; + BranchProbabilityInfo BPI{Func, LI}; + BFIPtr = llvm::make_unique(Func, BPI, LI); + BFI = BFIPtr.get(); + } + + std::unique_ptr GVInfo = computeFunctionInfo(F, BFI); + cloneToAliases(F, *GVInfo); + /// Ignore anonymous functions. Their aliases will have the info. + if (F.hasName()) + Index->addGlobalValueInfo(F.getName(), std::move(GVInfo)); + } + + // Compute summaries for all variables defined in module, and save in the + // index for that function and any aliases. + for (const GlobalVariable &G : M->globals()) { + if (G.isDeclaration()) + continue; + std::unique_ptr GVInfo = computeVariableInfo(G); + cloneToAliases(G, *GVInfo); + Index->addGlobalValueInfo(G.getName(), std::move(GVInfo)); + } + + for (const GlobalAlias &A : M->aliases()) { + // Add the alias to the reference list of aliasee function. + // FIXME: Leave this in for now to be consistent with the way the index + // was setup in the bitcode writer. Should remove and eventually replace + // with explicit alias -> aliasee relationship for all aliases. + if (isa(A.getBaseObject())) { + auto *Info = Index->getGlobalValueInfo(A); + FunctionSummary *FS = cast(Info->summary()); + FS->addRefEdge(M->getValueSymbolTable().lookup(A.getName())); + } + } +} + +char ModuleSummaryIndexWrapperPass::ID = 0; +INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", + "Module Summary Analysis", false, true) +INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) +INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", + "Module Summary Analysis", false, true) + +ModulePass *llvm::createModuleSummaryIndexWrapperPass() { + return new ModuleSummaryIndexWrapperPass(); +} + +ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() + : ModulePass(ID) { + initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); +} + +bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { + IndexBuilder = llvm::make_unique(&M); + return false; +} + +bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { + IndexBuilder.reset(); + return false; +} + +void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); +} Index: lib/Bitcode/Writer/BitcodeWriter.cpp =================================================================== --- lib/Bitcode/Writer/BitcodeWriter.cpp +++ lib/Bitcode/Writer/BitcodeWriter.cpp @@ -13,12 +13,7 @@ #include "ValueEnumerator.h" #include "llvm/ADT/StringExtras.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" @@ -26,10 +21,8 @@ #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/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" @@ -2271,8 +2264,7 @@ const ValueSymbolTable &VST, const ValueEnumerator &VE, BitstreamWriter &Stream, uint64_t VSTOffsetPlaceholder = 0, uint64_t BitcodeStartBit = 0, - DenseMap> * - GlobalValueIndex = nullptr) { + DenseMap *FunctionToBitcodeIndex = nullptr) { if (VST.empty()) { // WriteValueSymbolTableForwardDecl should have returned early as // well. Ensure this handling remains in sync by asserting that @@ -2361,13 +2353,12 @@ // Must be the module-level VST, where we pass in the Index and // have a VSTOffsetPlaceholder. The function-level VST should not // contain any Function symbols. - assert(GlobalValueIndex); + assert(FunctionToBitcodeIndex); assert(VSTOffsetPlaceholder > 0); // Save the word offset of the function (from the start of the // actual bitcode written to the stream). - uint64_t BitcodeIndex = - (*GlobalValueIndex)[F]->bitcodeIndex() - BitcodeStartBit; + uint64_t BitcodeIndex = (*FunctionToBitcodeIndex)[F] - BitcodeStartBit; assert((BitcodeIndex & 31) == 0 && "function block not 32-bit aligned"); NameVals.push_back(BitcodeIndex / 32); @@ -2489,61 +2480,14 @@ Stream.ExitBlock(); } -// Walk through the operands of a given User via worklist iteration and populate -// the set of GlobalValue references encountered. Invoked either on an -// Instruction or a GlobalVariable (which walks its initializer). -static void findRefEdges(const User *CurUser, const ValueEnumerator &VE, - DenseSet &RefEdges, - SmallPtrSet &Visited) { - SmallVector Worklist; - Worklist.push_back(CurUser); - - while (!Worklist.empty()) { - const User *U = Worklist.pop_back_val(); - - if (!Visited.insert(U).second) - continue; - - ImmutableCallSite CS(U); - - for (const auto &OI : U->operands()) { - const User *Operand = dyn_cast(OI); - if (!Operand) - continue; - if (isa(Operand)) - continue; - if (isa(Operand)) { - // We have a reference to a global value. This should be added to - // the reference set unless it is a callee. Callees are handled - // specially by WriteFunction and are added to a separate list. - if (!(CS && CS.isCallee(&OI))) - RefEdges.insert(VE.getValueID(Operand)); - continue; - } - Worklist.push_back(Operand); - } - } -} - /// Emit a function body to the module stream. static void WriteFunction(const Function &F, const Module *M, ValueEnumerator &VE, BitstreamWriter &Stream, - DenseMap> & - GlobalValueIndex, - bool EmitSummaryIndex) { + DenseMap &FunctionToBitcodeIndex) { // 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); - } + FunctionToBitcodeIndex[&F] = Stream.GetCurrentBitNo(); Stream.EnterSubblock(bitc::FUNCTION_BLOCK_ID, 4); VE.incorporateFunction(F); @@ -2570,40 +2514,15 @@ bool NeedsMetadataAttachment = F.hasMetadata(); 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(); I != E; ++I) { WriteInstruction(*I, InstID, VE, Stream, Vals); - if (!isa(I)) - ++NumInsts; - if (!I->getType()->isVoidTy()) ++InstID; - if (EmitSummaryIndex) { - if (auto CS = ImmutableCallSite(&*I)) { - auto *CalledFunction = CS.getCalledFunction(); - if (CalledFunction && CalledFunction->hasName() && - !CalledFunction->isIntrinsic()) { - auto ScaledCount = BFI ? BFI->getBlockProfileCount(&*BB) : None; - unsigned CalleeId = VE.getValueID( - M->getValueSymbolTable().lookup(CalledFunction->getName())); - CallGraphEdges[CalleeId] += - (ScaledCount ? ScaledCount.getValue() : 0); - } - } - findRefEdges(&*I, VE, RefEdges, Visited); - } - // If the instruction has metadata, write a metadata attachment later. NeedsMetadataAttachment |= I->hasMetadataOtherThanDebugLoc(); @@ -2628,15 +2547,6 @@ LastDL = DL; } - std::unique_ptr FuncSummary; - if (EmitSummaryIndex) { - FuncSummary = llvm::make_unique(F.getLinkage(), NumInsts); - FuncSummary->addCallGraphEdges(CallGraphEdges); - FuncSummary->addRefEdges(RefEdges); - } - GlobalValueIndex[&F] = - llvm::make_unique(BitcodeIndex, std::move(FuncSummary)); - // Emit names for all the instructions etc. WriteValueSymbolTable(F.getValueSymbolTable(), VE, Stream); @@ -2904,21 +2814,22 @@ // Helper to emit a single function summary record. static void WritePerModuleFunctionSummaryRecord( - SmallVector &NameVals, FunctionSummary *FS, unsigned ValueID, - unsigned FSCallsAbbrev, unsigned FSCallsProfileAbbrev, - BitstreamWriter &Stream, const Function &F) { - assert(FS); + SmallVector &NameVals, GlobalValueInfo *Info, + unsigned ValueID, const ValueEnumerator &VE, unsigned FSCallsAbbrev, + unsigned FSCallsProfileAbbrev, BitstreamWriter &Stream, const Function &F) { NameVals.push_back(ValueID); + + FunctionSummary *FS = cast(Info->summary()); 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); + NameVals.push_back(VE.getValueID(RI.getValue())); bool HasProfileData = F.getEntryCount().hasValue(); for (auto &ECI : FS->calls()) { - NameVals.push_back(ECI.first); + NameVals.push_back(VE.getValueID(ECI.first.getValue())); assert(ECI.second.CallsiteCount > 0 && "Expected at least one callsite"); NameVals.push_back(ECI.second.CallsiteCount); if (HasProfileData) @@ -2937,6 +2848,7 @@ // Collect the global value references in the given variable's initializer, // and emit them in a summary record. static void WriteModuleLevelReferences(const GlobalVariable &V, + const ModuleSummaryIndex &Index, const ValueEnumerator &VE, SmallVector &NameVals, unsigned FSModRefsAbbrev, @@ -2944,14 +2856,12 @@ // Only interested in recording variable defs in the summary. if (V.isDeclaration()) return; - DenseSet RefEdges; - SmallPtrSet Visited; - findRefEdges(&V, VE, RefEdges, Visited); NameVals.push_back(VE.getValueID(&V)); NameVals.push_back(getEncodedLinkage(V.getLinkage())); - for (auto RefId : RefEdges) { - NameVals.push_back(RefId); - } + auto *Info = Index.getGlobalValueInfo(V); + GlobalVarSummary *VS = cast(Info->summary()); + for (auto Ref : VS->refs()) + NameVals.push_back(VE.getValueID(Ref.getValue())); Stream.EmitRecord(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS, NameVals, FSModRefsAbbrev); NameVals.clear(); @@ -2959,10 +2869,10 @@ /// Emit the per-module summary section alongside the rest of /// the module's bitcode. -static void WritePerModuleGlobalValueSummary( - DenseMap> & - GlobalValueIndex, - const Module *M, const ValueEnumerator &VE, BitstreamWriter &Stream) { +static void WritePerModuleGlobalValueSummary(const Module *M, + const ModuleSummaryIndex &Index, + const ValueEnumerator &VE, + BitstreamWriter &Stream) { if (M->empty()) return; @@ -3002,7 +2912,7 @@ unsigned FSModRefsAbbrev = Stream.EmitAbbrev(Abbv); SmallVector NameVals; - // Iterate over the list of functions instead of the GlobalValueIndex map to + // Iterate over the list of functions instead of the Index to // ensure the ordering is stable. for (const Function &F : *M) { if (F.isDeclaration()) @@ -3012,11 +2922,10 @@ if (!F.hasName()) continue; - assert(GlobalValueIndex.count(&F) == 1); - + auto *Info = Index.getGlobalValueInfo(F); WritePerModuleFunctionSummaryRecord( - NameVals, cast(GlobalValueIndex[&F]->summary()), - VE.getValueID(M->getValueSymbolTable().lookup(F.getName())), + NameVals, Info, + VE.getValueID(M->getValueSymbolTable().lookup(F.getName())), VE, FSCallsAbbrev, FSCallsProfileAbbrev, Stream, F); } @@ -3027,24 +2936,21 @@ if (!F || F->isDeclaration()) continue; - assert(GlobalValueIndex.count(F) == 1); - FunctionSummary *FS = cast(GlobalValueIndex[F]->summary()); - // Add the alias to the reference list of aliasee function. - FS->addRefEdge( - VE.getValueID(M->getValueSymbolTable().lookup(A.getName()))); + auto *Info = Index.getGlobalValueInfo(A); WritePerModuleFunctionSummaryRecord( - NameVals, FS, - VE.getValueID(M->getValueSymbolTable().lookup(A.getName())), + NameVals, Info, + VE.getValueID(M->getValueSymbolTable().lookup(A.getName())), VE, 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); + WriteModuleLevelReferences(G, Index, VE, NameVals, FSModRefsAbbrev, Stream); for (const GlobalAlias &A : M->aliases()) if (auto *GV = dyn_cast(A.getBaseObject())) - WriteModuleLevelReferences(*GV, VE, NameVals, FSModRefsAbbrev, Stream); + WriteModuleLevelReferences(*GV, Index, VE, NameVals, FSModRefsAbbrev, + Stream); Stream.ExitBlock(); } @@ -3099,11 +3005,11 @@ NameVals.push_back(I.getModuleId(VS->modulePath())); NameVals.push_back(getEncodedLinkage(VS->linkage())); for (auto &RI : VS->refs()) { - const auto &VMI = GUIDToValueIdMap.find(RI); + const auto &VMI = GUIDToValueIdMap.find(RI.getId()); unsigned RefId; // If this GUID doesn't have an entry, assign one. if (VMI == GUIDToValueIdMap.end()) { - GUIDToValueIdMap[RI] = ++GlobalValueId; + GUIDToValueIdMap[RI.getId()] = ++GlobalValueId; RefId = GlobalValueId; } else { RefId = VMI->second; @@ -3131,11 +3037,11 @@ NameVals.push_back(FS->refs().size()); for (auto &RI : FS->refs()) { - const auto &VMI = GUIDToValueIdMap.find(RI); + const auto &VMI = GUIDToValueIdMap.find(RI.getId()); unsigned RefId; // If this GUID doesn't have an entry, assign one. if (VMI == GUIDToValueIdMap.end()) { - GUIDToValueIdMap[RI] = ++GlobalValueId; + GUIDToValueIdMap[RI.getId()] = ++GlobalValueId; RefId = GlobalValueId; } else { RefId = VMI->second; @@ -3151,7 +3057,7 @@ } for (auto &EI : FS->calls()) { - const auto &VMI = GUIDToValueIdMap.find(EI.first); + const auto &VMI = GUIDToValueIdMap.find(EI.first.getId()); // 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()) @@ -3232,7 +3138,8 @@ /// WriteModule - Emit the specified module to the bitstream. static void WriteModule(const Module *M, BitstreamWriter &Stream, bool ShouldPreserveUseListOrder, - uint64_t BitcodeStartBit, bool EmitSummaryIndex, + uint64_t BitcodeStartBit, + const ModuleSummaryIndex *Index, bool GenerateHash, SmallVectorImpl &Buffer) { Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3); size_t BlockStartPos = Buffer.size(); @@ -3279,19 +3186,19 @@ WriteOperandBundleTags(M, Stream); // Emit function bodies. - DenseMap> GlobalValueIndex; + DenseMap FunctionToBitcodeIndex; for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) if (!F->isDeclaration()) - WriteFunction(*F, M, VE, Stream, GlobalValueIndex, EmitSummaryIndex); + WriteFunction(*F, M, VE, Stream, FunctionToBitcodeIndex); // Need to write after the above call to WriteFunction which populates // the summary information in the index. - if (EmitSummaryIndex) - WritePerModuleGlobalValueSummary(GlobalValueIndex, M, VE, Stream); + if (Index) + WritePerModuleGlobalValueSummary(M, *Index, VE, Stream); WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream, VSTOffsetPlaceholder, BitcodeStartBit, - &GlobalValueIndex); + &FunctionToBitcodeIndex); if (GenerateHash) { writeModuleHash(Stream, Buffer, BlockStartPos); @@ -3381,7 +3288,8 @@ /// stream. void llvm::WriteBitcodeToFile(const Module *M, raw_ostream &Out, bool ShouldPreserveUseListOrder, - bool EmitSummaryIndex, bool GenerateHash) { + const ModuleSummaryIndex *Index, + bool GenerateHash) { SmallVector Buffer; Buffer.reserve(256*1024); @@ -3406,8 +3314,8 @@ WriteIdentificationBlock(M, Stream); // Emit the module. - WriteModule(M, Stream, ShouldPreserveUseListOrder, BitcodeStartBit, - EmitSummaryIndex, GenerateHash, Buffer); + WriteModule(M, Stream, ShouldPreserveUseListOrder, BitcodeStartBit, Index, + GenerateHash, Buffer); } if (TT.isOSDarwin() || TT.isOSBinFormatMachO()) Index: lib/Bitcode/Writer/BitcodeWriterPass.cpp =================================================================== --- lib/Bitcode/Writer/BitcodeWriterPass.cpp +++ lib/Bitcode/Writer/BitcodeWriterPass.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Bitcode/BitcodeWriterPass.h" +#include "llvm/Analysis/ModuleSummaryAnalysis.h" #include "llvm/Bitcode/ReaderWriter.h" #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" @@ -19,7 +20,10 @@ using namespace llvm; PreservedAnalyses BitcodeWriterPass::run(Module &M) { - WriteBitcodeToFile(&M, OS, ShouldPreserveUseListOrder, EmitSummaryIndex); + std::unique_ptr Index; + if (EmitSummaryIndex) + Index = ModuleSummaryIndexBuilder(&M).takeIndex(); + WriteBitcodeToFile(&M, OS, ShouldPreserveUseListOrder, Index.get()); return PreservedAnalyses::all(); } @@ -31,22 +35,42 @@ public: static char ID; // Pass identification, replacement for typeid + WriteBitcodePass() : ModulePass(ID), OS(dbgs()) { + initializeWriteBitcodePassPass(*PassRegistry::getPassRegistry()); + } + explicit WriteBitcodePass(raw_ostream &o, bool ShouldPreserveUseListOrder, bool EmitSummaryIndex) : ModulePass(ID), OS(o), ShouldPreserveUseListOrder(ShouldPreserveUseListOrder), - EmitSummaryIndex(EmitSummaryIndex) {} + EmitSummaryIndex(EmitSummaryIndex) { + initializeWriteBitcodePassPass(*PassRegistry::getPassRegistry()); + } const char *getPassName() const override { return "Bitcode Writer"; } bool runOnModule(Module &M) override { - WriteBitcodeToFile(&M, OS, ShouldPreserveUseListOrder, EmitSummaryIndex); + const ModuleSummaryIndex *Index = + EmitSummaryIndex + ? &(getAnalysis().getIndex()) + : nullptr; + WriteBitcodeToFile(&M, OS, ShouldPreserveUseListOrder, Index); return false; } + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesAll(); + if (EmitSummaryIndex) + AU.addRequired(); + } }; } char WriteBitcodePass::ID = 0; +INITIALIZE_PASS_BEGIN(WriteBitcodePass, "write-bitcode", "Write Bitcode", false, + true) +INITIALIZE_PASS_DEPENDENCY(ModuleSummaryIndexWrapperPass) +INITIALIZE_PASS_END(WriteBitcodePass, "write-bitcode", "Write Bitcode", false, + true) ModulePass *llvm::createBitcodeWriterPass(raw_ostream &Str, bool ShouldPreserveUseListOrder, 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 = Analysis Core Support +required_libraries = Core Support Index: lib/LTO/ThinLTOCodeGenerator.cpp =================================================================== --- lib/LTO/ThinLTOCodeGenerator.cpp +++ lib/LTO/ThinLTOCodeGenerator.cpp @@ -16,6 +16,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/Analysis/ModuleSummaryAnalysis.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Bitcode/BitcodeWriterPass.h" @@ -326,7 +327,8 @@ SmallVector OutputBuffer; { raw_svector_ostream OS(OutputBuffer); - WriteBitcodeToFile(&TheModule, OS, true, true); + ModuleSummaryIndexBuilder IndexBuilder(&TheModule); + WriteBitcodeToFile(&TheModule, OS, true, &IndexBuilder.getIndex()); } return make_unique(std::move(OutputBuffer)); } Index: lib/Transforms/IPO/FunctionImport.cpp =================================================================== --- lib/Transforms/IPO/FunctionImport.cpp +++ lib/Transforms/IPO/FunctionImport.cpp @@ -145,7 +145,7 @@ FunctionImporter::ImportMapTy &ImportsForModule, StringMap &ExportLists) { for (auto &Edge : Summary.calls()) { - auto GUID = Edge.first; + auto GUID = Edge.first.getId(); DEBUG(dbgs() << " edge -> " << GUID << " Threshold:" << Threshold << "\n"); if (DefinedFunctions.count(GUID)) { @@ -181,11 +181,12 @@ // Mark all functions and globals referenced by this function as exported to // the outside if they are defined in the same source module. for (auto &Edge : CalleeSummary->calls()) { - auto CalleeGUID = Edge.first; + auto CalleeGUID = Edge.first.getId(); if (isGlobalExported(Index, ExportModulePath, CalleeGUID)) ExportList.insert(CalleeGUID); } - for (auto &GUID : CalleeSummary->refs()) { + for (auto &Ref : CalleeSummary->refs()) { + auto GUID = Ref.getId(); if (isGlobalExported(Index, ExportModulePath, GUID)) ExportList.insert(GUID); } Index: tools/llvm-as/CMakeLists.txt =================================================================== --- tools/llvm-as/CMakeLists.txt +++ tools/llvm-as/CMakeLists.txt @@ -1,4 +1,5 @@ set(LLVM_LINK_COMPONENTS + Analysis AsmParser BitWriter Core Index: tools/llvm-as/LLVMBuild.txt =================================================================== --- tools/llvm-as/LLVMBuild.txt +++ tools/llvm-as/LLVMBuild.txt @@ -19,4 +19,4 @@ type = Tool name = llvm-as parent = Tools -required_libraries = AsmParser BitWriter +required_libraries = Analysis AsmParser BitWriter Index: tools/llvm-as/llvm-as.cpp =================================================================== --- tools/llvm-as/llvm-as.cpp +++ tools/llvm-as/llvm-as.cpp @@ -15,6 +15,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Analysis/ModuleSummaryAnalysis.h" #include "llvm/AsmParser/Parser.h" #include "llvm/Bitcode/ReaderWriter.h" #include "llvm/IR/LLVMContext.h" @@ -83,9 +84,14 @@ exit(1); } - if (Force || !CheckBitcodeOutputToConsole(Out->os(), true)) - WriteBitcodeToFile(M, Out->os(), PreserveBitcodeUseListOrder, - EmitSummaryIndex, EmitModuleHash); + if (Force || !CheckBitcodeOutputToConsole(Out->os(), true)) { + std::unique_ptr Index; + if (EmitSummaryIndex) + Index = ModuleSummaryIndexBuilder(M).takeIndex(); + + WriteBitcodeToFile(M, Out->os(), PreserveBitcodeUseListOrder, Index.get(), + EmitModuleHash); + } // Declare success. Out->keep();