llvm/lib/Analysis/CallPrinter.cpp

   1 //===- CallPrinter.cpp - DOT printer for call graph -----------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines '-dot-callgraph', which emit a callgraph.<fnname>.dot
  10 // containing the call graph of a module.
  11 //
  12 // There is also a pass available to directly call dotty ('-view-callgraph').
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Analysis/CallPrinter.h"
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/SmallSet.h"
  19 #include "llvm/Analysis/BlockFrequencyInfo.h"
  20 #include "llvm/Analysis/CallGraph.h"
  21 #include "llvm/Analysis/HeatUtils.h"
  22 #include "llvm/IR/Instructions.h"
  23 #include "llvm/IR/Module.h"
  24 #include "llvm/InitializePasses.h"
  25 #include "llvm/Support/CommandLine.h"
  26 #include "llvm/Support/DOTGraphTraits.h"
  27 #include "llvm/Support/GraphWriter.h"
  28
  29 using namespace llvm;
  30
  31 namespace llvm {
  32 template <class GraphType> struct GraphTraits;
  33 } // namespace llvm
  34
  35 // This option shows static (relative) call counts.
  36 // FIXME:
  37 // Need to show real counts when profile data is available
  38 static cl::opt<bool> ShowHeatColors("callgraph-heat-colors", cl::init(false),
  39                                     cl::Hidden,
  40                                     cl::desc("Show heat colors in call-graph"));
  41
  42 static cl::opt<bool>
  43     ShowEdgeWeight("callgraph-show-weights", cl::init(false), cl::Hidden,
  44                        cl::desc("Show edges labeled with weights"));
  45
  46 static cl::opt<bool>
  47     CallMultiGraph("callgraph-multigraph", cl::init(false), cl::Hidden,
  48             cl::desc("Show call-multigraph (do not remove parallel edges)"));
  49
  50 static cl::opt<std::string> CallGraphDotFilenamePrefix(
  51     "callgraph-dot-filename-prefix", cl::Hidden,
  52     cl::desc("The prefix used for the CallGraph dot file names."));
  53
  54 namespace llvm {
  55
  56 class CallGraphDOTInfo {
  57 private:
  58   Module *M;
  59   CallGraph *CG;
  60   DenseMap<const Function *, uint64_t> Freq;
  61   uint64_t MaxFreq;
  62
  63 public:
  64   std::function<BlockFrequencyInfo *(Function &)> LookupBFI;
  65
  66   CallGraphDOTInfo(Module *M, CallGraph *CG,
  67                    function_ref<BlockFrequencyInfo *(Function &)> LookupBFI)
  68       : M(M), CG(CG), LookupBFI(LookupBFI) {
  69     MaxFreq = 0;
  70
  71     for (Function &F : M->getFunctionList()) {
  72       uint64_t localSumFreq = 0;
  73       SmallSet<Function *, 16> Callers;
  74       for (User *U : F.users())
  75         if (isa<CallInst>(U))
  76           Callers.insert(cast<Instruction>(U)->getFunction());
  77       for (Function *Caller : Callers)
  78         localSumFreq += getNumOfCalls(*Caller, F);
  79       if (localSumFreq >= MaxFreq)
  80         MaxFreq = localSumFreq;
  81       Freq[&F] = localSumFreq;
  82     }
  83     if (!CallMultiGraph)
  84       removeParallelEdges();
  85   }
  86
  87   Module *getModule() const { return M; }
  88
  89   CallGraph *getCallGraph() const { return CG; }
  90
  91   uint64_t getFreq(const Function *F) { return Freq[F]; }
  92
  93   uint64_t getMaxFreq() { return MaxFreq; }
  94
  95 private:
  96   void removeParallelEdges() {
  97     for (auto &I : (*CG)) {
  98       CallGraphNode *Node = I.second.get();
  99
 100       bool FoundParallelEdge = true;
 101       while (FoundParallelEdge) {
 102         SmallSet<Function *, 16> Visited;
 103         FoundParallelEdge = false;
 104         for (auto CI = Node->begin(), CE = Node->end(); CI != CE; CI++) {
 105           if (!(Visited.insert(CI->second->getFunction())).second) {
 106             FoundParallelEdge = true;
 107             Node->removeCallEdge(CI);
 108             break;
 109           }
 110         }
 111       }
 112     }
 113   }
 114 };
 115
 116 template <>
 117 struct GraphTraits<CallGraphDOTInfo *>
 118     : public GraphTraits<const CallGraphNode *> {
 119   static NodeRef getEntryNode(CallGraphDOTInfo *CGInfo) {
 120     // Start at the external node!
 121     return CGInfo->getCallGraph()->getExternalCallingNode();
 122   }
 123
 124   typedef std::pair<const Function *const, std::unique_ptr<CallGraphNode>>
 125       PairTy;
 126   static const CallGraphNode *CGGetValuePtr(const PairTy &P) {
 127     return P.second.get();
 128   }
 129
 130   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 131   typedef mapped_iterator<CallGraph::const_iterator, decltype(&CGGetValuePtr)>
 132       nodes_iterator;
 133
 134   static nodes_iterator nodes_begin(CallGraphDOTInfo *CGInfo) {
 135     return nodes_iterator(CGInfo->getCallGraph()->begin(), &CGGetValuePtr);
 136   }
 137   static nodes_iterator nodes_end(CallGraphDOTInfo *CGInfo) {
 138     return nodes_iterator(CGInfo->getCallGraph()->end(), &CGGetValuePtr);
 139   }
 140 };
 141
 142 template <>
 143 struct DOTGraphTraits<CallGraphDOTInfo *> : public DefaultDOTGraphTraits {
 144
 145   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
 146
 147   static std::string getGraphName(CallGraphDOTInfo *CGInfo) {
 148     return "Call graph: " +
 149            std::string(CGInfo->getModule()->getModuleIdentifier());
 150   }
 151
 152   static bool isNodeHidden(const CallGraphNode *Node,
 153                            const CallGraphDOTInfo *CGInfo) {
 154     if (CallMultiGraph || Node->getFunction())
 155       return false;
 156     return true;
 157   }
 158
 159   std::string getNodeLabel(const CallGraphNode *Node,
 160                            CallGraphDOTInfo *CGInfo) {
 161     if (Node == CGInfo->getCallGraph()->getExternalCallingNode())
 162       return "external caller";
 163     if (Node == CGInfo->getCallGraph()->getCallsExternalNode())
 164       return "external callee";
 165
 166     if (Function *Func = Node->getFunction())
 167       return std::string(Func->getName());
 168     return "external node";
 169   }
 170   static const CallGraphNode *CGGetValuePtr(CallGraphNode::CallRecord P) {
 171     return P.second;
 172   }
 173
 174   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 175   typedef mapped_iterator<CallGraphNode::const_iterator,
 176                           decltype(&CGGetValuePtr)>
 177       nodes_iterator;
 178
 179   std::string getEdgeAttributes(const CallGraphNode *Node, nodes_iterator I,
 180                                 CallGraphDOTInfo *CGInfo) {
 181     if (!ShowEdgeWeight)
 182       return "";
 183
 184     Function *Caller = Node->getFunction();
 185     if (Caller == nullptr || Caller->isDeclaration())
 186       return "";
 187
 188     Function *Callee = (*I)->getFunction();
 189     if (Callee == nullptr)
 190       return "";
 191
 192     uint64_t Counter = getNumOfCalls(*Caller, *Callee);
 193     double Width =
 194         1 + 2 * (double(Counter) / CGInfo->getMaxFreq());
 195     std::string Attrs = "label=\"" + std::to_string(Counter) +
 196                         "\" penwidth=" + std::to_string(Width);
 197     return Attrs;
 198   }
 199
 200   std::string getNodeAttributes(const CallGraphNode *Node,
 201                                 CallGraphDOTInfo *CGInfo) {
 202     Function *F = Node->getFunction();
 203     if (F == nullptr)
 204       return "";
 205     std::string attrs;
 206     if (ShowHeatColors) {
 207       uint64_t freq = CGInfo->getFreq(F);
 208       std::string color = getHeatColor(freq, CGInfo->getMaxFreq());
 209       std::string edgeColor = (freq <= (CGInfo->getMaxFreq() / 2))
 210                                   ? getHeatColor(0)
 211                                   : getHeatColor(1);
 212       attrs = "color=\"" + edgeColor + "ff\", style=filled, fillcolor=\"" +
 213               color + "80\"";
 214     }
 215     return attrs;
 216   }
 217 };
 218
 219 } // namespace llvm
 220
 221 namespace {
 222 void doCallGraphDOTPrinting(
 223     Module &M, function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
 224   std::string Filename;
 225   if (!CallGraphDotFilenamePrefix.empty())
 226     Filename = (CallGraphDotFilenamePrefix + ".callgraph.dot");
 227   else
 228     Filename = (std::string(M.getModuleIdentifier()) + ".callgraph.dot");
 229   errs() << "Writing '" << Filename << "'...";
 230
 231   std::error_code EC;
 232   raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
 233
 234   CallGraph CG(M);
 235   CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI);
 236
 237   if (!EC)
 238     WriteGraph(File, &CFGInfo);
 239   else
 240     errs() << "  error opening file for writing!";
 241   errs() << "\n";
 242 }
 243
 244 void viewCallGraph(Module &M,
 245                    function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
 246   CallGraph CG(M);
 247   CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI);
 248
 249   std::string Title =
 250       DOTGraphTraits<CallGraphDOTInfo *>::getGraphName(&CFGInfo);
 251   ViewGraph(&CFGInfo, "callgraph", true, Title);
 252 }
 253 } // namespace
 254
 255 namespace llvm {
 256 PreservedAnalyses CallGraphDOTPrinterPass::run(Module &M,
 257                                                ModuleAnalysisManager &AM) {
 258   FunctionAnalysisManager &FAM =
 259       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 260
 261   auto LookupBFI = [&FAM](Function &F) {
 262     return &FAM.getResult<BlockFrequencyAnalysis>(F);
 263   };
 264
 265   doCallGraphDOTPrinting(M, LookupBFI);
 266
 267   return PreservedAnalyses::all();
 268 }
 269
 270 PreservedAnalyses CallGraphViewerPass::run(Module &M,
 271                                            ModuleAnalysisManager &AM) {
 272
 273   FunctionAnalysisManager &FAM =
 274       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 275
 276   auto LookupBFI = [&FAM](Function &F) {
 277     return &FAM.getResult<BlockFrequencyAnalysis>(F);
 278   };
 279
 280   viewCallGraph(M, LookupBFI);
 281
 282   return PreservedAnalyses::all();
 283 }
 284 } // namespace llvm
 285
 286 namespace {
 287 // Viewer
 288 class CallGraphViewer : public ModulePass {
 289 public:
 290   static char ID;
 291   CallGraphViewer() : ModulePass(ID) {}
 292
 293   void getAnalysisUsage(AnalysisUsage &AU) const override;
 294   bool runOnModule(Module &M) override;
 295 };
 296
 297 void CallGraphViewer::getAnalysisUsage(AnalysisUsage &AU) const {
 298   ModulePass::getAnalysisUsage(AU);
 299   AU.addRequired<BlockFrequencyInfoWrapperPass>();
 300   AU.setPreservesAll();
 301 }
 302
 303 bool CallGraphViewer::runOnModule(Module &M) {
 304   auto LookupBFI = [this](Function &F) {
 305     return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
 306   };
 307
 308   viewCallGraph(M, LookupBFI);
 309
 310   return false;
 311 }
 312
 313 // DOT Printer
 314
 315 class CallGraphDOTPrinter : public ModulePass {
 316 public:
 317   static char ID;
 318   CallGraphDOTPrinter() : ModulePass(ID) {}
 319
 320   void getAnalysisUsage(AnalysisUsage &AU) const override;
 321   bool runOnModule(Module &M) override;
 322 };
 323
 324 void CallGraphDOTPrinter::getAnalysisUsage(AnalysisUsage &AU) const {
 325   ModulePass::getAnalysisUsage(AU);
 326   AU.addRequired<BlockFrequencyInfoWrapperPass>();
 327   AU.setPreservesAll();
 328 }
 329
 330 bool CallGraphDOTPrinter::runOnModule(Module &M) {
 331   auto LookupBFI = [this](Function &F) {
 332     return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
 333   };
 334
 335   doCallGraphDOTPrinting(M, LookupBFI);
 336
 337   return false;
 338 }
 339
 340 } // end anonymous namespace
 341
 342 char CallGraphViewer::ID = 0;
 343 INITIALIZE_PASS(CallGraphViewer, "view-callgraph", "View call graph", false,
 344                 false)
 345
 346 char CallGraphDOTPrinter::ID = 0;
 347 INITIALIZE_PASS(CallGraphDOTPrinter, "dot-callgraph",
 348                 "Print call graph to 'dot' file", false, false)
 349
 350 // Create methods available outside of this file, to use them
 351 // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
 352 // the link time optimization.
 353
 354 ModulePass *llvm::createCallGraphViewerPass() { return new CallGraphViewer(); }
 355
 356 ModulePass *llvm::createCallGraphDOTPrinterPass() {
 357   return new CallGraphDOTPrinter();
 358 }