Index: llvm/include/llvm/Analysis/HeatUtils.h =================================================================== --- llvm/include/llvm/Analysis/HeatUtils.h +++ llvm/include/llvm/Analysis/HeatUtils.h @@ -24,6 +24,16 @@ namespace llvm { +// Returns number of calls of calledFunction by callerFunction. +uint64_t +getNumOfCalls(Function &callerFunction, Function &calledFunction, + function_ref LookupBFI); + +// Returns number of calls from the call-site. +uint64_t +getNumOfCalls(CallSite &callsite, + function_ref LookupBFI); + // Returns the maximum frequency of a BB in a function. uint64_t getMaxFreq(const Function &F, const BlockFrequencyInfo *BFI); Index: llvm/lib/Analysis/CallPrinter.cpp =================================================================== --- llvm/lib/Analysis/CallPrinter.cpp +++ llvm/lib/Analysis/CallPrinter.cpp @@ -14,30 +14,248 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CallPrinter.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/DOTGraphTraitsPass.h" +#include "llvm/Analysis/HeatUtils.h" +#include "llvm/Support/CommandLine.h" #include "llvm/InitializePasses.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallSet.h" using namespace llvm; +static cl::opt ShowHeatColors("callgraph-heat-colors", cl::init(false), + cl::Hidden, + cl::desc("Show heat colors in call-graph")); + +static cl::opt + EstimateEdgeWeight("callgraph-weights", cl::init(false), cl::Hidden, + cl::desc("Show edges labeled with weights")); + +static cl::opt + CallMultiGraph("call-multigraph", cl::init(false), cl::Hidden, + cl::desc("Show call-multigraph (do not remove parallel edges)")); + +static cl::opt UseCallCounter( + "callgraph-call-count", cl::init(false), cl::Hidden, + cl::desc("Use function's call counter as a heat metric. " + "The default is the function's maximum block frequency.")); + +static cl::opt CallGraphDotFilenamePrefix( + "callgraph-dot-filename-prefix", cl::Hidden, + cl::desc("The prefix used for the CallGraph dot file names.")); + namespace llvm { -template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { - DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} +class CallGraphDOTInfo { +private: + Module *M; + CallGraph *CG; + DenseMap Freq; + uint64_t MaxFreq; + uint64_t MaxEdgeCount; + +public: + std::function LookupBFI; + + CallGraphDOTInfo(Module *M, CallGraph *CG, + function_ref LookupBFI) + : M(M), CG(CG), LookupBFI(LookupBFI) { + MaxFreq = 0; + MaxEdgeCount = 0; + + for (Function &F : *M) { + Freq[&F] = 0; + + if (F.isDeclaration()) + continue; + uint64_t localMaxFreq = 0; + if (UseCallCounter) { + Function::ProfileCount EntryCount = F.getEntryCount(); + if (EntryCount.hasValue()) + localMaxFreq = EntryCount.getCount(); + } else { + localMaxFreq = llvm::getMaxFreq(F, LookupBFI(F)); + } + if (localMaxFreq >= MaxFreq) + MaxFreq = localMaxFreq; + Freq[&F] = localMaxFreq; + } + if (!CallMultiGraph) + { + for (auto F = M->getFunctionList().begin(); F != M->getFunctionList().end(); ++F) { + for (auto pairF = F; pairF != M->getFunctionList().end(); ++pairF) { + uint64_t Counter = getNumOfCalls(*F, *pairF, LookupBFI); + if (Counter > MaxEdgeCount) + MaxEdgeCount = Counter; + Counter = getNumOfCalls(*pairF, *F, LookupBFI); + if (Counter > MaxEdgeCount) + MaxEdgeCount = Counter; + } + } + removeParallelEdges(); + } + } + + Module *getModule() const { return M; } + CallGraph *getCallGraph() const { return CG; } + + uint64_t getFreq(const Function *F) { return Freq[F]; } + + uint64_t getMaxFreq() { return MaxFreq; } + + uint64_t getMaxEdgeCount() { return MaxEdgeCount; } + +private: + void removeParallelEdges() { + for (auto &I : (*CG)) { + CallGraphNode *Node = I.second.get(); + + bool FoundParallelEdge = true; + while (FoundParallelEdge) { + SmallSet Visited; + FoundParallelEdge = false; + for (auto CI = Node->begin(), CE = Node->end(); CI != CE; CI++) { + if (!Visited.count(CI->second->getFunction())) + Visited.insert(CI->second->getFunction()); + else { + FoundParallelEdge = true; + Node->removeCallEdge(CI); + break; + } + } + } + } + } +}; + +template <> +struct GraphTraits + : public GraphTraits { + static NodeRef getEntryNode(CallGraphDOTInfo *CGInfo) { + // Start at the external node! + return CGInfo->getCallGraph()->getExternalCallingNode(); + } + + typedef std::pair> + PairTy; + static const CallGraphNode *CGGetValuePtr(const PairTy &P) { + return P.second.get(); + } + + // nodes_iterator/begin/end - Allow iteration over all nodes in the graph + typedef mapped_iterator + nodes_iterator; + + static nodes_iterator nodes_begin(CallGraphDOTInfo *CGInfo) { + return nodes_iterator(CGInfo->getCallGraph()->begin(), &CGGetValuePtr); + } + static nodes_iterator nodes_end(CallGraphDOTInfo *CGInfo) { + return nodes_iterator(CGInfo->getCallGraph()->end(), &CGGetValuePtr); + } +}; + +template <> +struct DOTGraphTraits : public DefaultDOTGraphTraits { + + SmallSet VisitedCallSites; DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} + + static std::string getGraphName(CallGraphDOTInfo *CGInfo) { + return "Call graph: " + + std::string(CGInfo->getModule()->getModuleIdentifier()); + } + + static bool isNodeHidden(const CallGraphNode *Node) { + if (CallMultiGraph) + return false; + + if (Node->getFunction()) + return false; + + return true; + } + + std::string getNodeLabel(const CallGraphNode *Node, + CallGraphDOTInfo *CGInfo) { + if (Node == CGInfo->getCallGraph()->getExternalCallingNode()) + return "external caller"; + + if (Node == CGInfo->getCallGraph()->getCallsExternalNode()) + return "external callee"; - static std::string getGraphName(CallGraph *Graph) { return "Call graph"; } - std::string getNodeLabel(CallGraphNode *Node, CallGraph *Graph) { if (Function *Func = Node->getFunction()) return std::string(Func->getName()); return "external node"; } -}; + static const CallGraphNode *CGGetValuePtr(CallGraphNode::CallRecord P) { + return P.second; + } -struct AnalysisCallGraphWrapperPassTraits { - static CallGraph *getGraph(CallGraphWrapperPass *P) { - return &P->getCallGraph(); + // nodes_iterator/begin/end - Allow iteration over all nodes in the graph + typedef mapped_iterator + nodes_iterator; + + std::string getEdgeAttributes(const CallGraphNode *Node, nodes_iterator I, + CallGraphDOTInfo *CGInfo) { + if (!EstimateEdgeWeight) + return ""; + + Function *Caller = Node->getFunction(); + if (Caller == nullptr || Caller->isDeclaration()) + return ""; + + Function *Callee = (*I)->getFunction(); + if (Callee == nullptr) + return ""; + + uint64_t Counter = 0; + if (CallMultiGraph) { + // looks for next call site between Caller and Callee + for (User *U : Callee->users()) { + auto CS = CallSite(U); + if (CS.getCaller() == Caller) { + if (VisitedCallSites.count(U)) + continue; + VisitedCallSites.insert(U); + Counter = getNumOfCalls(CS, CGInfo->LookupBFI); + break; + } + } + } else { + Counter = getNumOfCalls(*Caller, *Callee, CGInfo->LookupBFI); + } + + double Width = + 1 + 2 * (double(Counter) / CGInfo->getMaxEdgeCount()); + std::string Attrs = "label=\"" + std::to_string(Counter) + + "\" penwidth=" + std::to_string(Width); + + return Attrs; + } + + std::string getNodeAttributes(const CallGraphNode *Node, + CallGraphDOTInfo *CGInfo) { + Function *F = Node->getFunction(); + if (F == nullptr || F->isDeclaration()) + return ""; + + std::string attrs = ""; + if (ShowHeatColors) { + uint64_t freq = CGInfo->getFreq(F); + std::string color = getHeatColor(freq, CGInfo->getMaxFreq()); + std::string edgeColor = (freq <= (CGInfo->getMaxFreq() / 2)) + ? getHeatColor(0) + : getHeatColor(1); + + attrs = "color=\"" + edgeColor + "ff\", style=filled, fillcolor=\"" + + color + "80\""; + } + return attrs; } }; @@ -45,32 +263,90 @@ namespace { -struct CallGraphViewer - : public DOTGraphTraitsModuleViewer { +// Viewer + +class CallGraphViewer : public ModulePass { +public: static char ID; + CallGraphViewer() : ModulePass(ID) {} + + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnModule(Module &M) override; + + + - CallGraphViewer() - : DOTGraphTraitsModuleViewer( - "callgraph", ID) { - initializeCallGraphViewerPass(*PassRegistry::getPassRegistry()); - } }; -struct CallGraphDOTPrinter : public DOTGraphTraitsModulePrinter< - CallGraphWrapperPass, true, CallGraph *, - AnalysisCallGraphWrapperPassTraits> { +void CallGraphViewer::getAnalysisUsage(AnalysisUsage &AU) const { + ModulePass::getAnalysisUsage(AU); + AU.addRequired(); + AU.setPreservesAll(); +} + +bool CallGraphViewer::runOnModule(Module &M) { + auto LookupBFI = [this](Function &F) { + return &this->getAnalysis(F).getBFI(); + }; + + CallGraph CG(M); + CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI); + + std::string Title = + DOTGraphTraits::getGraphName(&CFGInfo); + ViewGraph(&CFGInfo, "callgraph", true, Title); + + return false; +} + +// DOT Printer + +class CallGraphDOTPrinter : public ModulePass { +public: static char ID; + CallGraphDOTPrinter() : ModulePass(ID) {} + + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnModule(Module &M) override; + + + - CallGraphDOTPrinter() - : DOTGraphTraitsModulePrinter( - "callgraph", ID) { - initializeCallGraphDOTPrinterPass(*PassRegistry::getPassRegistry()); - } }; +void CallGraphDOTPrinter::getAnalysisUsage(AnalysisUsage &AU) const { + ModulePass::getAnalysisUsage(AU); + AU.addRequired(); + AU.setPreservesAll(); +} + +bool CallGraphDOTPrinter::runOnModule(Module &M) { + auto LookupBFI = [this](Function &F) { + return &this->getAnalysis(F).getBFI(); + }; + + std::string Filename; + if (!CallGraphDotFilenamePrefix.empty()) + Filename = (CallGraphDotFilenamePrefix + ".callgraph.dot"); + else + Filename = (std::string(M.getModuleIdentifier()) + ".callgraph.dot"); + errs() << "Writing '" << Filename << "'..."; + + std::error_code EC; + raw_fd_ostream File(Filename, EC, sys::fs::F_Text); + + CallGraph CG(M); + CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI); + + if (!EC) + WriteGraph(File, &CFGInfo); + else + errs() << " error opening file for writing!"; + errs() << "\n"; + + return false; +} + } // end anonymous namespace char CallGraphViewer::ID = 0; Index: llvm/lib/Analysis/HeatUtils.cpp =================================================================== --- llvm/lib/Analysis/HeatUtils.cpp +++ llvm/lib/Analysis/HeatUtils.cpp @@ -35,6 +35,32 @@ "#d24b40", "#d0473d", "#cc403a", "#ca3b37", "#c53334", "#c32e31", "#be242e", "#bb1b2c", "#b70d28"}; +uint64_t +getNumOfCalls(CallSite &CS, + function_ref LookupBFI) { + if (CS.getInstruction() == nullptr) + return 0; + if (CS.getInstruction()->getParent() == nullptr) + return 0; + BasicBlock *BB = CS.getInstruction()->getParent(); + return LookupBFI(*CS.getCaller())->getBlockFreq(BB).getFrequency(); +} + +uint64_t +getNumOfCalls(Function &callerFunction, Function &calledFunction, + function_ref LookupBFI) { + uint64_t counter = 0; + for (User *U : calledFunction.users()) { + if (isa(U)) { + auto CS = CallSite(U); + if (CS.getCaller() == (&callerFunction)) { + counter += getNumOfCalls(CS, LookupBFI); + } + } + } + return counter; +} + uint64_t getMaxFreq(const Function &F, const BlockFrequencyInfo *BFI) { uint64_t maxFreq = 0; for (const BasicBlock &BB : F) { Index: llvm/test/Other/heat-colors-graphs.ll =================================================================== --- llvm/test/Other/heat-colors-graphs.ll +++ llvm/test/Other/heat-colors-graphs.ll @@ -1,9 +1,11 @@ ; RUN: opt < %s -analyze -dot-cfg -cfg-heat-colors -cfg-dot-filename-prefix=%t 2>/dev/null -; RUN: FileCheck %s -input-file=%t.f.dot +; RUN: FileCheck %s -input-file=%t.f.dot --check-prefixes=CHECK-CFG,CHECK-BOTH +; RUN: opt %s -dot-callgraph -callgraph-heat-colors -callgraph-dot-filename-prefix=%t 2>/dev/null +; RUN: FileCheck %s -input-file=%t.callgraph.dot --check-prefix=CHECK-BOTH -; CHECK: color="#{{[(a-z)(0-9)]+}}", style={{[a-z]+}}, fillcolor="#{{[(a-z)(0-9)]+}}" -; CHECK: color="#{{[(a-z)(0-9)]+}}", style={{[a-z]+}}, fillcolor="#{{[(a-z)(0-9)]+}}" -; CHECK: color="#{{[(a-z)(0-9)]+}}", style={{[a-z]+}}, fillcolor="#{{[(a-z)(0-9)]+}}" +; CHECK-BOTH: color="#{{[(a-z)(0-9)]+}}", style={{[a-z]+}}, fillcolor="#{{[(a-z)(0-9)]+}}" +; CHECK-CFG: color="#{{[(a-z)(0-9)]+}}", style={{[a-z]+}}, fillcolor="#{{[(a-z)(0-9)]+}}" +; CHECK-CFG: color="#{{[(a-z)(0-9)]+}}", style={{[a-z]+}}, fillcolor="#{{[(a-z)(0-9)]+}}" define void @f(i32) { entry: Index: llvm/test/Other/heat-colors-multigraph.ll =================================================================== --- /dev/null +++ llvm/test/Other/heat-colors-multigraph.ll @@ -0,0 +1,16 @@ +; RUN: opt %s -dot-callgraph -call-multigraph -callgraph-dot-filename-prefix=%t 2>/dev/null +; RUN: FileCheck %s -input-file=%t.callgraph.dot --check-prefix=CHECK-MULTIGRAPH +; RUN: opt %s -dot-callgraph -callgraph-dot-filename-prefix=%t 2>/dev/null +; RUN: FileCheck %s -input-file=%t.callgraph.dot --check-prefix=CHECK + +; CHECK-MULTIGRAPH: {external caller} +; CHECK-NOT: {external caller} + +define void @bar() { + ret void +} + +define void @foo() { + call void @bar() + ret void +}