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/Analysis/ModuleSummaryAnalysis.cpp | 186 ++++++++++++++++++++++++++++ 1 file changed, 186 insertions(+) create mode 100644 llvm/lib/Analysis/ModuleSummaryAnalysis.cpp (limited to 'llvm/lib/Analysis/ModuleSummaryAnalysis.cpp') diff --git a/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp b/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp new file mode 100644 index 0000000..5c8b0aa --- /dev/null +++ b/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp @@ -0,0 +1,186 @@ +//===- 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); + } + } +} + +void ModuleSummaryIndexBuilder::computeFunctionInfo(const Function &F, + BlockFrequencyInfo *BFI) { + // Summary not currently supported for anonymous functions, they must + // be renamed. + if (!F.hasName()) + return; + + 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)); + Index->addGlobalValueInfo(F.getName(), std::move(GVInfo)); +} + +void 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)); + Index->addGlobalValueInfo(V.getName(), std::move(GVInfo)); +} + +ModuleSummaryIndexBuilder::ModuleSummaryIndexBuilder( + const Module *M, + std::function Ftor) + : Index(llvm::make_unique()), M(M) { + // Compute summaries for all functions defined in module, and save in the + // index. + for (auto &F : *M) { + if (F.isDeclaration()) + continue; + + BlockFrequencyInfo *BFI = nullptr; + std::unique_ptr BFIPtr; + if (Ftor) + BFI = Ftor(F); + else if (F.getEntryCount().hasValue()) { + LoopInfo LI{DominatorTree(const_cast(F))}; + BranchProbabilityInfo BPI{F, LI}; + BFIPtr = llvm::make_unique(F, BPI, LI); + BFI = BFIPtr.get(); + } + + computeFunctionInfo(F, BFI); + } + + // Compute summaries for all variables defined in module, and save in the + // index. + for (const GlobalVariable &G : M->globals()) { + if (G.isDeclaration()) + continue; + computeVariableInfo(G); + } +} + +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, [this](const Function &F) { + return &(this->getAnalysis( + *const_cast(&F)) + .getBFI()); + }); + return false; +} + +bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { + IndexBuilder.reset(); + return false; +} + +void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); +} -- cgit v1.1