From 2d5487cf446f9a58f6d2f76df33102423c83f285 Mon Sep 17 00:00:00 2001 From: Teresa Johnson Date: Mon, 11 Apr 2016 13:58:45 +0000 Subject: [ThinLTO] Move summary computation from BitcodeWriter to new pass Summary: This is the first step in also serializing the index out to LLVM assembly. The per-module summary written to bitcode is moved out of the bitcode writer and to a new analysis pass (ModuleSummaryIndexWrapperPass). The pass itself uses a new builder class to compute index, and the builder class is used directly in places where we don't have a pass manager (e.g. llvm-as). Because we are computing summaries outside of the bitcode writer, we no longer can use value ids created by the bitcode writer's ValueEnumerator. This required changing the reference graph edge type to use a new ValueInfo class holding a union between a GUID (combined index) and Value* (permodule index). The Value* are converted to the appropriate value ID during bitcode writing. Also, this enables removal of the BitWriter library's dependence on the Analysis library that was previously required for the summary computation. Reviewers: joker.eph Subscribers: joker.eph, llvm-commits Differential Revision: http://reviews.llvm.org/D18763 llvm-svn: 265941 --- llvm/lib/Bitcode/Writer/BitcodeWriter.cpp | 196 +++++++----------------------- 1 file changed, 43 insertions(+), 153 deletions(-) (limited to 'llvm/lib/Bitcode/Writer/BitcodeWriter.cpp') diff --git a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp index d9a4de5ddbd..262dad652fc 100644 --- a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/llvm/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" @@ -2282,8 +2275,7 @@ static void WriteValueSymbolTable( 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 @@ -2372,13 +2364,12 @@ static void WriteValueSymbolTable( // 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); @@ -2500,61 +2491,14 @@ static void WriteUseListBlock(const Function *F, ValueEnumerator &VE, 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); @@ -2581,40 +2525,15 @@ WriteFunction(const Function &F, const Module *M, ValueEnumerator &VE, 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(); @@ -2639,15 +2558,6 @@ WriteFunction(const Function &F, const Module *M, ValueEnumerator &VE, 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); @@ -2915,21 +2825,22 @@ static void WriteModStrings(const ModuleSummaryIndex &I, // 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) @@ -2948,6 +2859,7 @@ static void WritePerModuleFunctionSummaryRecord( // 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, @@ -2955,14 +2867,12 @@ static void WriteModuleLevelReferences(const GlobalVariable &V, // 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(); @@ -2970,10 +2880,10 @@ static void WriteModuleLevelReferences(const GlobalVariable &V, /// 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; @@ -3013,7 +2923,7 @@ static void WritePerModuleGlobalValueSummary( 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()) @@ -3023,39 +2933,17 @@ static void WritePerModuleGlobalValueSummary( 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); } - for (const GlobalAlias &A : M->aliases()) { - if (!A.getBaseObject()) - continue; - const Function *F = dyn_cast(A.getBaseObject()); - 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()))); - WritePerModuleFunctionSummaryRecord( - 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()) - if (auto *GV = dyn_cast(A.getBaseObject())) - WriteModuleLevelReferences(*GV, VE, NameVals, FSModRefsAbbrev, Stream); + WriteModuleLevelReferences(G, Index, VE, NameVals, FSModRefsAbbrev, Stream); Stream.ExitBlock(); } @@ -3110,11 +2998,11 @@ static void WriteCombinedGlobalValueSummary( NameVals.push_back(Index.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.getGUID()); unsigned RefId; // If this GUID doesn't have an entry, assign one. if (VMI == GUIDToValueIdMap.end()) { - GUIDToValueIdMap[RI] = ++GlobalValueId; + GUIDToValueIdMap[RI.getGUID()] = ++GlobalValueId; RefId = GlobalValueId; } else { RefId = VMI->second; @@ -3142,11 +3030,11 @@ static void WriteCombinedGlobalValueSummary( NameVals.push_back(FS->refs().size()); for (auto &RI : FS->refs()) { - const auto &VMI = GUIDToValueIdMap.find(RI); + const auto &VMI = GUIDToValueIdMap.find(RI.getGUID()); unsigned RefId; // If this GUID doesn't have an entry, assign one. if (VMI == GUIDToValueIdMap.end()) { - GUIDToValueIdMap[RI] = ++GlobalValueId; + GUIDToValueIdMap[RI.getGUID()] = ++GlobalValueId; RefId = GlobalValueId; } else { RefId = VMI->second; @@ -3162,7 +3050,7 @@ static void WriteCombinedGlobalValueSummary( } for (auto &EI : FS->calls()) { - const auto &VMI = GUIDToValueIdMap.find(EI.first); + const auto &VMI = GUIDToValueIdMap.find(EI.first.getGUID()); // 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()) @@ -3243,8 +3131,9 @@ static void writeModuleHash(BitstreamWriter &Stream, /// WriteModule - Emit the specified module to the bitstream. static void WriteModule(const Module *M, BitstreamWriter &Stream, bool ShouldPreserveUseListOrder, - uint64_t BitcodeStartBit, bool EmitSummaryIndex, - bool GenerateHash, SmallVectorImpl &Buffer) { + uint64_t BitcodeStartBit, + const ModuleSummaryIndex *Index, bool GenerateHash, + SmallVectorImpl &Buffer) { Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3); size_t BlockStartPos = Buffer.size(); @@ -3290,19 +3179,19 @@ static void WriteModule(const Module *M, BitstreamWriter &Stream, 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); @@ -3392,7 +3281,8 @@ static void WriteBitcodeHeader(BitstreamWriter &Stream) { /// 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); @@ -3417,8 +3307,8 @@ void llvm::WriteBitcodeToFile(const Module *M, raw_ostream &Out, 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()) -- cgit v1.2.3