Heat Coloring (3/3): Adding Heat Functionality to CallPrinter

[knaumov]

Summary

This patch is the third in the sequence of three patches related to the following diff (https://reviews.llvm.org/D73142). The first patch from the sequence that has introduced the structure for DOTFunction Information is found here - D76820. The second patch introduced similar functionality to the CFG - (D77161). This patch introduces the heat coloring of the CallPrinter which is based on the relative "hotness" of each function. All the functionality of this patch was developed and discussed in the preceding patches.

[knaumov]

Transferred the getNumOfCalls functions from the previous review.

[davidxl]

Can you also provide the test_for_loop.ll (perhaps as a test case?) which correspond to the pdf file attached to the original patch?

llvm/lib/Analysis/CallPrinter.cpp

38

callgraph-multigraph to be consistent with other option names

42

to be consistent with naming convention in PGO, perhaps use 'callgraph-entry-count'

[knaumov]

Answering @davidxl 's comments:

• Renamed flags

Attaching the file test_heat.ll for which the .pdf from the original patch was created:

test_heat.ll1 KBDownload

Where do you want me to put it?

[knaumov]

The wrong diff uploaded previously, reupload

[davidxl]

Looked at the example .ll file for good_callgraph.pdf -- they don't seem to match. There is no callgraph edge from bar1 to bar2, but the pdf file shows there is one. Similarly for other edges between bar* functions.

[knaumov]

• Changed the flag in the test

Indeed, sorry, wrong .ll test.
This one should be the one:

test_heat.ll1 KBDownload

[davidxl]

The call edges now look correct, but the resulting hotness does not look right. The caller 'foo' is marked as hot with red color, but hot callees like 'bar1' etc in the loop are not (Note that the branches in the loop are not highly biased).

[knaumov]

• Fixed the functionality of heat coloring - now the coloring of CallGraph is done by analyzing how many times the given function was called. The more times it's being called - the hotter ("redder") it will be on the graph.

[davidxl]

Can you also upload the graph with the fix?

[knaumov]

This Callgraph was generated from test_heat.ll
You can see, as foo is not being called by anyone, it is marked as the coldest block. Bar functions are ranked from the least number to the greatest by their hotness which makes sense - whenever function bar1 is called, it is calling all of the other bars that follow and so on. Thus, bar5 is the hottest function in the .ll file

test_heat.ll.callgraph.pdf14 KBDownload

[davidxl]

thanks. The example graph looks great. Will take a look at the patch in details soon.

[davidxl]

llvm/include/llvm/Analysis/HeatUtils.h

34

Use CallBase instead of CallSite

llvm/lib/Analysis/CallPrinter.cpp

34

ShowEdgeWeight and callgraph-show-weights ?

71

This is O(N^2) to the number of functions. For a C++ module, this can be quite large.

76

why max but not sum?

113

can directly use insert method and check its return value

217

what is this check for?

llvm/lib/Analysis/HeatUtils.cpp

46

As I mentioned in one of the previous reviews, the blockfrequency is relative to the parent function (because of the final scaling step used in computing the integer frequency value which depends on the min and max value) and it will be meaningless to compare block frequency of callsites in different functions.

57

where does the '5' come from?

[knaumov]

Addressed @davidxl 's comments, did some refactoring

[davidxl]

llvm/lib/Analysis/CallPrinter.cpp

29

Add a comment that this currently only shows static call counts. Also a FIXME to show real counts when profile data is available

81

This part can be folded into the previous loop that computes MaxFreq

[knaumov]

Addressed @davidxl 's comments:

• Added comments
• Brought for-loop iteration over functions in the module into the previous one

[davidxl]

llvm/lib/Analysis/CallPrinter.cpp

80

Is this loop needed? Can you just check the *iter, *F pair? -- the enclosing loop should cover all caller,callee pairs in the module.

[knaumov]

I have noticed that MaxEdgeCount is essentially count the same thing as MaxFreq, so I replaced its uses in all the cases.

[knaumov]

ping

[davidxl]

lgtm

llvm/include/llvm/Analysis/HeatUtils.h

 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 
 #include <string>
 
 namespace llvm {
 
+// Returns number of calls of calledFunction by callerFunction.
+uint64_t
+getNumOfCalls(Function &callerFunction, Function &calledFunction,
+              function_ref<BlockFrequencyInfo *(Function &)> LookupBFI);
+
+// Returns number of calls from the call-site.
+uint64_t
+getNumOfCalls(CallSite &callsite,
+              function_ref<BlockFrequencyInfo *(Function &)> LookupBFI);
+
 // Returns the maximum frequency of a BB in a function.
 uint64_t getMaxFreq(const Function &F, const BlockFrequencyInfo *BFI);
 
 // Calculates heat color based on current and maximum frequencies.
 std::string getHeatColor(uint64_t freq, uint64_t maxFreq);
 
 // Calculates heat color based on percent of "hotness".
 std::string getHeatColor(double percent);
 
 } // namespace llvm
 
 #endif

llvm/lib/Analysis/CallPrinter.cpp

 //===- CallPrinter.cpp - DOT printer for call graph -----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines '-dot-callgraph', which emit a callgraph.<fnname>.dot
 // containing the call graph of a module.
 //
 // There is also a pass available to directly call dotty ('-view-callgraph').
 //
 //===----------------------------------------------------------------------===//
 
 #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<bool> ShowHeatColors("callgraph-heat-colors", cl::init(false),
+                                    cl::Hidden,
+                                    cl::desc("Show heat colors in call-graph"));
+
+static cl::opt<bool>
+    EstimateEdgeWeight("callgraph-weights", cl::init(false), cl::Hidden,
+                       cl::desc("Show edges labeled with weights"));
+
+static cl::opt<bool>
+    CallMultiGraph("call-multigraph", cl::init(false), cl::Hidden,
+            cl::desc("Show call-multigraph (do not remove parallel edges)"));
+
+static cl::opt<bool> 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<std::string> CallGraphDotFilenamePrefix(
+    "callgraph-dot-filename-prefix", cl::Hidden,
+    cl::desc("The prefix used for the CallGraph dot file names."));
+
 namespace llvm {
 
-template <> struct DOTGraphTraits<CallGraph *> : public DefaultDOTGraphTraits {
-  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
+class CallGraphDOTInfo {
+private:
+  Module *M;
+  CallGraph *CG;
+  DenseMap<const Function *, uint64_t> Freq;
+  uint64_t MaxFreq;
+  uint64_t MaxEdgeCount;
+
+public:
+  std::function<BlockFrequencyInfo *(Function &)> LookupBFI;
+
+  CallGraphDOTInfo(Module *M, CallGraph *CG,
+                   function_ref<BlockFrequencyInfo *(Function &)> 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<Function *, 16> 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<CallGraphDOTInfo *>
+    : public GraphTraits<const CallGraphNode *> {
+  static NodeRef getEntryNode(CallGraphDOTInfo *CGInfo) {
+    // Start at the external node!
+    return CGInfo->getCallGraph()->getExternalCallingNode();
+  }
+
+  typedef std::pair<const Function *const, std::unique_ptr<CallGraphNode>>
+      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<CallGraph::const_iterator, decltype(&CGGetValuePtr)>
+      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<CallGraphDOTInfo *> : public DefaultDOTGraphTraits {
+
+  SmallSet<User *, 16> 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;
+  }
+
+  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+  typedef mapped_iterator<CallGraphNode::const_iterator,
+                          decltype(&CGGetValuePtr)>
+      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);
 
-struct AnalysisCallGraphWrapperPassTraits {
-  static CallGraph *getGraph(CallGraphWrapperPass *P) {
-    return &P->getCallGraph();
+      attrs = "color=\"" + edgeColor + "ff\", style=filled, fillcolor=\"" +
+              color + "80\"";
+    }
+    return attrs;
   }
 };
 
 } // end llvm namespace
 
 namespace {
 
-struct CallGraphViewer
-    : public DOTGraphTraitsModuleViewer<CallGraphWrapperPass, true, CallGraph *,
-                                        AnalysisCallGraphWrapperPassTraits> {
+// 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<CallGraphWrapperPass, true, CallGraph *,
-                                   AnalysisCallGraphWrapperPassTraits>(
-            "callgraph", ID) {
-    initializeCallGraphViewerPass(*PassRegistry::getPassRegistry());
-  }
+
+
+
+};
+
+void CallGraphViewer::getAnalysisUsage(AnalysisUsage &AU) const {
+  ModulePass::getAnalysisUsage(AU);
+  AU.addRequired<BlockFrequencyInfoWrapperPass>();
+  AU.setPreservesAll();
+
+bool CallGraphViewer::runOnModule(Module &M) {
+  auto LookupBFI = [this](Function &F) {
+    return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
   };
 
-struct CallGraphDOTPrinter : public DOTGraphTraitsModulePrinter<
-                              CallGraphWrapperPass, true, CallGraph *,
-                              AnalysisCallGraphWrapperPassTraits> {
+  CallGraph CG(M);
+  CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI);
+
+  std::string Title =
+      DOTGraphTraits<CallGraphDOTInfo *>::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<CallGraphWrapperPass, true, CallGraph *,
-                                    AnalysisCallGraphWrapperPassTraits>(
-            "callgraph", ID) {
-    initializeCallGraphDOTPrinterPass(*PassRegistry::getPassRegistry());
-  }
+
+
+};
+
+void CallGraphDOTPrinter::getAnalysisUsage(AnalysisUsage &AU) const {
+  ModulePass::getAnalysisUsage(AU);
+  AU.addRequired<BlockFrequencyInfoWrapperPass>();
+  AU.setPreservesAll();
+
+bool CallGraphDOTPrinter::runOnModule(Module &M) {
+  auto LookupBFI = [this](Function &F) {
+    return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(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;
 INITIALIZE_PASS(CallGraphViewer, "view-callgraph", "View call graph", false,
                 false)
 
 char CallGraphDOTPrinter::ID = 0;
 INITIALIZE_PASS(CallGraphDOTPrinter, "dot-callgraph",

llvm/lib/Analysis/HeatUtils.cpp

static const std::string heatPalette[heatSize] = {
     "#ecd3c5", "#eed0c0", "#efcebd", "#f1ccb8", "#f2cab5", "#f3c7b1", "#f4c5ad",
     "#f5c1a9", "#f6bfa6", "#f7bca1", "#f7b99e", "#f7b599", "#f7b396", "#f7af91",
     "#f7ac8e", "#f7a889", "#f6a385", "#f5a081", "#f59c7d", "#f4987a", "#f39475",
     "#f29072", "#f08b6e", "#ef886b", "#ed8366", "#ec7f63", "#e97a5f", "#e8765c",
     "#e57058", "#e36c55", "#e16751", "#de614d", "#dc5d4a", "#d85646", "#d65244",
     "#d24b40", "#d0473d", "#cc403a", "#ca3b37", "#c53334", "#c32e31", "#be242e",
     "#bb1b2c", "#b70d28"};
 
+uint64_t
+getNumOfCalls(CallSite &CS,
+              function_ref<BlockFrequencyInfo *(Function &)> 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<BlockFrequencyInfo *(Function &)> LookupBFI) {
+  uint64_t counter = 0;
+  for (User *U : calledFunction.users()) {
+    if (isa<CallInst>(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) {
     uint64_t freqVal = BFI->getBlockFreq(&BB).getFrequency();
     if (freqVal >= maxFreq)
       maxFreq = freqVal;
   }
   return maxFreq;
if (percent > 1.0)
     percent = 1.0;
   if (percent < 0.0)
     percent = 0.0;
   unsigned colorId = unsigned(round(percent * (heatSize - 1.0)));
   return heatPalette[colorId];
 }
 
 } // namespace llvm
 No newline at end of file

llvm/test/Other/heat-colors-graphs.ll

 ; 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:
   %check = icmp sgt i32 %0, 0
   br i1 %check, label %if, label %exit, !prof !0
 
 if:                     ; preds = %entry
   br label %exit
 exit:                   ; preds = %entry, %if
   ret void
 }
 
 !0 = !{!"branch_weights", i32 1, i32 200}

llvm/test/Other/heat-colors-multigraph.ll

+; 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
+}