diff --git a/llvm/include/llvm/Analysis/HeatUtils.h b/llvm/include/llvm/Analysis/HeatUtils.h --- a/llvm/include/llvm/Analysis/HeatUtils.h +++ b/llvm/include/llvm/Analysis/HeatUtils.h @@ -22,6 +22,10 @@ class BlockFrequencyInfo; class Function; +// Returns number of calls of calledFunction by callerFunction. +uint64_t +getNumOfCalls(Function &callerFunction, Function &calledFunction); + // Returns the maximum frequency of a BB in a function. uint64_t getMaxFreq(const Function &F, const BlockFrequencyInfo *BFI); diff --git a/llvm/lib/Analysis/CallPrinter.cpp b/llvm/lib/Analysis/CallPrinter.cpp --- a/llvm/lib/Analysis/CallPrinter.cpp +++ b/llvm/lib/Analysis/CallPrinter.cpp @@ -14,63 +14,279 @@ //===----------------------------------------------------------------------===// #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; +// This option shows static (relative) call counts. +// FIXME: +// Need to show real counts when profile data is available +static cl::opt ShowHeatColors("callgraph-heat-colors", cl::init(false), + cl::Hidden, + cl::desc("Show heat colors in call-graph")); + +static cl::opt + ShowEdgeWeight("callgraph-show-weights", cl::init(false), cl::Hidden, + cl::desc("Show edges labeled with weights")); + +static cl::opt + CallMultiGraph("callgraph-multigraph", cl::init(false), cl::Hidden, + cl::desc("Show call-multigraph (do not remove parallel edges)")); + +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 { +class CallGraphDOTInfo { +private: + Module *M; + CallGraph *CG; + DenseMap Freq; + uint64_t MaxFreq; + +public: + std::function LookupBFI; + + CallGraphDOTInfo(Module *M, CallGraph *CG, + function_ref LookupBFI) + : M(M), CG(CG), LookupBFI(LookupBFI) { + MaxFreq = 0; + + for (auto F = M->getFunctionList().begin(); F != M->getFunctionList().end(); ++F) { + uint64_t localSumFreq = 0; + SmallSet Callers; + for (User *U : (*F).users()) + if (isa(U)) + Callers.insert(cast(U)->getFunction()); + for (auto iter = Callers.begin() ; iter != Callers.end() ; ++iter) + localSumFreq += getNumOfCalls((**iter), *F); + if (localSumFreq >= MaxFreq) + MaxFreq = localSumFreq; + Freq[&*F] = localSumFreq; + } + if (!CallMultiGraph) + 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; } + +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.insert(CI->second->getFunction())).second) { + 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 { + DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} - static std::string getGraphName(CallGraph *Graph) { return "Call graph"; } + static std::string getGraphName(CallGraphDOTInfo *CGInfo) { + return "Call graph: " + + std::string(CGInfo->getModule()->getModuleIdentifier()); + } + + static bool isNodeHidden(const CallGraphNode *Node) { + if (CallMultiGraph || 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"; - 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; + } + + // 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 (!ShowEdgeWeight) + return ""; + + Function *Caller = Node->getFunction(); + if (Caller == nullptr || Caller->isDeclaration()) + return ""; + + Function *Callee = (*I)->getFunction(); + if (Callee == nullptr) + return ""; -struct AnalysisCallGraphWrapperPassTraits { - static CallGraph *getGraph(CallGraphWrapperPass *P) { - return &P->getCallGraph(); + uint64_t Counter = getNumOfCalls(*Caller, *Callee); + double Width = + 1 + 2 * (double(Counter) / CGInfo->getMaxFreq()); + 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) + 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; } }; } // end llvm namespace namespace { - -struct CallGraphViewer - : public DOTGraphTraitsModuleViewer { +// Viewer +class CallGraphViewer : public ModulePass { +public: static char ID; + CallGraphViewer() : ModulePass(ID) {} - CallGraphViewer() - : DOTGraphTraitsModuleViewer( - "callgraph", ID) { - initializeCallGraphViewerPass(*PassRegistry::getPassRegistry()); - } + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnModule(Module &M) override; }; -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) {} - CallGraphDOTPrinter() - : DOTGraphTraitsModulePrinter( - "callgraph", ID) { - initializeCallGraphDOTPrinterPass(*PassRegistry::getPassRegistry()); - } + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnModule(Module &M) override; }; +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; diff --git a/llvm/lib/Analysis/HeatUtils.cpp b/llvm/lib/Analysis/HeatUtils.cpp --- a/llvm/lib/Analysis/HeatUtils.cpp +++ b/llvm/lib/Analysis/HeatUtils.cpp @@ -36,6 +36,19 @@ "#d24b40", "#d0473d", "#cc403a", "#ca3b37", "#c53334", "#c32e31", "#be242e", "#bb1b2c", "#b70d28"}; +uint64_t +getNumOfCalls(Function &callerFunction, Function &calledFunction) { + uint64_t counter = 0; + for (User *U : calledFunction.users()) { + if (auto CI = dyn_cast(U)) { + if (CI->getCaller() == (&callerFunction)) { + counter += 1; + } + } + } + return counter; +} + uint64_t getMaxFreq(const Function &F, const BlockFrequencyInfo *BFI) { uint64_t maxFreq = 0; for (const BasicBlock &BB : F) { diff --git a/llvm/test/Other/heat-colors-graphs.ll b/llvm/test/Other/heat-colors-graphs.ll --- a/llvm/test/Other/heat-colors-graphs.ll +++ b/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: diff --git a/llvm/test/Other/heat-colors-multigraph.ll b/llvm/test/Other/heat-colors-multigraph.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Other/heat-colors-multigraph.ll @@ -0,0 +1,16 @@ +; RUN: opt %s -dot-callgraph -callgraph-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 +}