Heat Coloring for CFGPrinter and CallPrinter

[knaumov]

Summary

Extends the CFGPrinter and CallPrinter with heat colors based on heuristics or profiling information.

This patch was firstly published by Rodrigo Caetano Rocha (@rcorcs) on 11/24/17. After several rounds of reviews, it was deployed, but, mainly due to the conflict with Polly, it was reverted. After that, the conflict with Polly alongside some other small issues was fixed, but never deployed. The diff then was closed due to the commit that probably happened during migration. I would like to bring this change upstream. I have taken it up to me to make some changes regarding flags initialization and refactoring some older tests to match the new output of CFGPrinter specifically. All the further info on the patch you can find in the previous reviews.

Initial diff: reviews.llvm.org/D40425
First commit: reviews.llvm.org/rL335996
Revert commit: reviews.llvm.org/rL336000
Polly fix: reviews.llvm.org/D49154

[knaumov]

ping

[davidxl]

llvm/lib/Analysis/HeatUtils.cpp

40

You can use ProfileSummaryInfo::hasProfileSummary interface.

67

parameter not used

68

clang-format

74

The function entry count should have the information

100

for the program's max count, max function count, get it from ProfileSummaryInfo.

[sfertile]

I'm embarrassed to say I though the old patches landed after the Polly fix, so I really appreciate you taking the time to update the patches.

I've added a few comments to start/ One thing I would suggest is running clang-format over all the changes.

llvm/include/llvm/Analysis/CFGPrinter.h

263–266

Minor nit: Fix the extra white space.

271

Remove extra blank line.

280

const unsigned MaxEdgeWidth = 2
so shouldn't this just be double Width = 1.0 + WeightPercent;

282

Can we convert the else block into an early return instead -->

if (!CFGInfo->useRawEdgeWeights())
  return formatv("label=\"{0:P}\" penwidth={1}", WeightPercent, Width).str();

[knaumov]

Addressed @davidxl and @sfertile comments.

Answering @davidxl 's comment on "The function entry count should have the information", line 73, HeatUtils.cpp:
This function counts the number of calls of one specific function by another specific function while Function.entryCount() returns number entries for this function.

Answering @davidxl 's comment on "for the program's max count, max function count, get it from ProfileSummaryInfo.", line 99, HeatUtils.cpp:
ProfileSummaryInfo doesn't contain info on the maximum frequency in the module, it needs to be calculated.

Updates:

• Ran clang-format through all the files
• Deleted some function which had no use (see hasProfiling function)
• Deleted const unsigned variables

[knaumov]

ping

[davidxl]

In D73142#1855835, @knaumov wrote:

Addressed @davidxl and @sfertile comments.

Answering @davidxl 's comment on "The function entry count should have the information", line 73, HeatUtils.cpp:
This function counts the number of calls of one specific function by another specific function while Function.entryCount() returns number entries for this function.

Answering @davidxl 's comment on "for the program's max count, max function count, get it from ProfileSummaryInfo.", line 99, HeatUtils.cpp:
ProfileSummaryInfo doesn't contain info on the maximum frequency in the module, it needs to be calculated.

Updates:

• Ran clang-format through all the files
• Deleted some function which had no use (see hasProfiling function)
• Deleted const unsigned variables

The max count info from a module can be misleading. The module itself in most of the cases are cold, so profile summary should be used for cases when profile data is available.

Another major issue is that when real profile is not available (when heurstic is used), the blockfrequency value is relative to the a function, so you can not really compare block frequency values across function boundaries. For that, a round of synthetic profile count propagation is needed.

llvm/lib/Analysis/CallPrinter.cpp

37

By looking at the code, it seems that the difference of 'full' vs 'nonfull' is a whether it is a multi-graph or not.

71

How can this be? The caller of the callsite can not be a declaration.

[knaumov]

Changes:

• Renamed a flag ("callgraph-full" -> "call-multigraph") to reflect its purpose more clearly
• Removed unnecessary if-check
• General refactoring and restructuring
• Removed useHeuristic from the code - from the structure of the code it is vivid that useHeuristic variable used in getMaxFreq functions is always set to "true" and never becomes "false".

Addressing @davidxl 's comments:
ProfileSummaryInfo class will not be useful in this problem as it only gives the result on
whether the BB or the Function is hot or cold, without information on how hot or cold
it is when compared to the other BBs or Functions.
On the other hand, I agree with the fact that comparing local maximum BB frequencies
in function throughout the module is useless and can be misleading. However, I don't
see any "nice" way out of that, as the solution that you suggested (SyntheticCountsPropagation pass)
involves altering the module which should be avoided in a diagnostical pass. Also, as CallGraphs
are printed per function, there is no worry that the colors are going to be somewhat misleading.

[davidxl]

Since it is meaningless to compare blockfrequency across function boundaries (and computing module max): the following can be done

1. when profile is available, try to compute max block count (actual profile count) per module
2. when profile is not available, try to do function scope heat coloring only.

[knaumov]

• Removed flag that was targeting coloring BB based on their relative hotness across the module.

I have decided to do that for the following reasons:

1. The patch is self-contained without this feature. This feature can be added in a follow-up patch.
2. The feature itself is not as important and valuable as was first thought of.

My suggestions for implementing this feature:
Although we only have a relative frequency of BB with respect to the function, using the relative frequency of a function with respect to the module we can translate it to be relative to the module. We can do that using ProfileSummary to get the number of entries per a function.

[knaumov]

Fixes:

• Restoring the effect of clang-format

The effect of clang-format was restored for better readability of the patch

• Deleted Heuristic fully

As I said in the previous diffs, Heuristic bool was always true and never changing.

• Transferred CFGPrinter back to Function Pass

The patch was made module in order to implement the comparison between BB across functions. As this patch is not targeting this behavior, the pass was decided to remain Function Pass

• Small stylistics changes

[davidxl]

is there call graph related test case?

Also some sample output file of the CFG and CallGraph with heat color will be helpful.

llvm/include/llvm/Analysis/HeatUtils.h

29

Add documentation.

33

add documentation. Similarly for other interfaces.

llvm/lib/Analysis/CallPrinter.cpp

83

this quadratic behavior.

[knaumov]

Fixes:

• Added documentation to the new functions
• Added two test cases - one for multigraph, the second one for heat CallGraph/CFG specifically
• Reduced the quadratic behavior that was mentioned by @davidxl . There is no way to reduce the behavior to smaller than O(n^2), but I've made it to (n^2)/2. There is no need to go beyond this as this is just a debugging feature that is not to be used outside of debugging.

Also, I am attaching two samples of heat coloring - CFG and CallGraph.

good_cfg.pdf19 KBDownload

good_callgraph.pdf14 KBDownload

[knaumov]

Ping

[davidxl]

The cfg example (and pdf) looks great. However the callgraph example looks not quite right. Can you provide the test_for_loop.ll file as well? thanks.

[davidxl]

If you split the CFG part of the changes into a separate patch, I think it is almost in good shape to land first.

[knaumov]

All of the related patches were successfully reviewed and landed!
Thanks to everyone who has participated in this long journey!

llvm/include/llvm/Analysis/CFGPrinter.h

 // This file defines external functions that can be called to explicitly
 // instantiate the CFG printer.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CFGPRINTER_H
 #define LLVM_ANALYSIS_CFGPRINTER_H
 
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/HeatUtils.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/GraphWriter.h"
 
 namespace llvm {
-class CFGViewerPass
-    : public PassInfoMixin<CFGViewerPass> {
+class CFGViewerPass : public PassInfoMixin<CFGViewerPass> {
 public:
-  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
 
-class CFGOnlyViewerPass
-    : public PassInfoMixin<CFGOnlyViewerPass> {
+class CFGOnlyViewerPass : public PassInfoMixin<CFGOnlyViewerPass> {
 public:
-  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
 
-class CFGPrinterPass
-    : public PassInfoMixin<CFGPrinterPass> {
+class CFGPrinterPass : public PassInfoMixin<CFGPrinterPass> {
 public:
-  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
 
-class CFGOnlyPrinterPass
-    : public PassInfoMixin<CFGOnlyPrinterPass> {
+class CFGOnlyPrinterPass : public PassInfoMixin<CFGOnlyPrinterPass> {
 public:
-  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
+};
+
+class CFGDOTInfo {
+private:
+  const Function *F;
+  const BlockFrequencyInfo *BFI;
+  const BranchProbabilityInfo *BPI;
+  uint64_t MaxFreq;
+  bool ShowHeat;
+  bool Heuristic;
+  bool EdgeWeights;
+  bool RawWeights;
+
+public:
+  CFGDOTInfo(const Function *F) : CFGDOTInfo(F, nullptr, nullptr, 0) {}
+
+  CFGDOTInfo(const Function *F, const BlockFrequencyInfo *BFI,
+             BranchProbabilityInfo *BPI, uint64_t MaxFreq)
+      : F(F), BFI(BFI), BPI(BPI), MaxFreq(MaxFreq) {
+    ShowHeat = false;
+    Heuristic = true;
+    EdgeWeights = true;
+    RawWeights = true;
+  }
+
+  const BlockFrequencyInfo *getBFI() { return BFI; }
+
+  const BranchProbabilityInfo *getBPI() { return BPI; }
+
+  const Function *getFunction() { return this->F; }
+
+  uint64_t getMaxFreq() { return MaxFreq; }
+
+  uint64_t getFreq(const BasicBlock *BB) {
+    return BFI->getBlockFreq(BB).getFrequency();
+  }
+
+  void setHeatColors(bool ShowHeat) { this->ShowHeat = ShowHeat; }
+
+  bool showHeatColors() { return ShowHeat; }
+
+  void setHeuristic(bool Heuristic) { this->Heuristic = Heuristic; }
+
+  bool useHeuristic() { return Heuristic; }
+
+  void setRawEdgeWeights(bool RawWeights) { this->RawWeights = RawWeights; }
+
+  bool useRawEdgeWeights() { return RawWeights; }
+
+  void setEdgeWeights(bool EdgeWeights) { this->EdgeWeights = EdgeWeights; }
+
+  bool showEdgeWeights() { return EdgeWeights; }
 };
 
-template<>
-struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits {
+template <>
+struct GraphTraits<CFGDOTInfo *> : public GraphTraits<const BasicBlock *> {
+  static NodeRef getEntryNode(CFGDOTInfo *CFGInfo) {
+    return &(CFGInfo->getFunction()->getEntryBlock());
+  }
+
+  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+  using nodes_iterator = pointer_iterator<Function::const_iterator>;
+
+  static nodes_iterator nodes_begin(CFGDOTInfo *CFGInfo) {
+    return nodes_iterator(CFGInfo->getFunction()->begin());
+  }
+
+  static nodes_iterator nodes_end(CFGDOTInfo *CFGInfo) {
+    return nodes_iterator(CFGInfo->getFunction()->end());
+  }
+
+  static size_t size(CFGDOTInfo *CFGInfo) {
+    return CFGInfo->getFunction()->size();
+  }
+};
+
+template <> struct DOTGraphTraits<CFGDOTInfo *> : public DefaultDOTGraphTraits {
 
   // Cache for is hidden property
   llvm::DenseMap <const BasicBlock *, bool> isHiddenBasicBlock;
 
   DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
 
-  static std::string getGraphName(const Function *F) {
-    return "CFG for '" + F->getName().str() + "' function";
+  static std::string getGraphName(CFGDOTInfo *CFGInfo) {
+    return "CFG for '" + CFGInfo->getFunction()->getName().str() + "' function";
   }
 
-  static std::string getSimpleNodeLabel(const BasicBlock *Node,
-                                        const Function *) {
+  static std::string getSimpleNodeLabel(const BasicBlock *Node, CFGDOTInfo *) {
     if (!Node->getName().empty())
       return Node->getName().str();
 
     std::string Str;
     raw_string_ostream OS(Str);
 
     Node->printAsOperand(OS, false);
     return OS.str();
   }
 
   static std::string getCompleteNodeLabel(const BasicBlock *Node,
-                                          const Function *) {
+                                          CFGDOTInfo *) {
     enum { MaxColumns = 80 };
     std::string Str;
     raw_string_ostream OS(Str);
 
     if (Node->getName().empty()) {
       Node->printAsOperand(OS, false);
       OS << ":";
     }
 
     OS << *Node;
     std::string OutStr = OS.str();
-    if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
+    if (OutStr[0] == '\n')
+      OutStr.erase(OutStr.begin());
 
     // Process string output to make it nicer...
     unsigned ColNum = 0;
     unsigned LastSpace = 0;
     for (unsigned i = 0; i != OutStr.length(); ++i) {
-      if (OutStr[i] == '\n') {                            // Left justify
+      if (OutStr[i] == '\n') { // Left justify
         OutStr[i] = '\\';
-        OutStr.insert(OutStr.begin()+i+1, 'l');
+        OutStr.insert(OutStr.begin() + i + 1, 'l');
         ColNum = 0;
         LastSpace = 0;
-      } else if (OutStr[i] == ';') {                      // Delete comments!
-        unsigned Idx = OutStr.find('\n', i+1);            // Find end of line
-        OutStr.erase(OutStr.begin()+i, OutStr.begin()+Idx);
+      } else if (OutStr[i] == ';') {
+        unsigned Idx = OutStr.find('\n', i + 1); // Find end of line
+        OutStr.erase(OutStr.begin() + i, OutStr.begin() + Idx);
         --i;
-      } else if (ColNum == MaxColumns) {                  // Wrap lines.
+      } else if (ColNum == MaxColumns) { // Wrap lines.
         // Wrap very long names even though we can't find a space.
         if (!LastSpace)
           LastSpace = i;
         OutStr.insert(LastSpace, "\\l...");
         ColNum = i - LastSpace;
         LastSpace = 0;
         i += 3; // The loop will advance 'i' again.
-      }
-      else
+      } else
         ++ColNum;
       if (OutStr[i] == ' ')
         LastSpace = i;
     }
     return OutStr;
   }
 
-  std::string getNodeLabel(const BasicBlock *Node,
-                           const Function *Graph) {
+  std::string getNodeLabel(const BasicBlock *Node, CFGDOTInfo *CFGInfo) {
+
     if (isSimple())
-      return getSimpleNodeLabel(Node, Graph);
+      return getSimpleNodeLabel(Node, CFGInfo);
     else
-      return getCompleteNodeLabel(Node, Graph);
+      return getCompleteNodeLabel(Node, CFGInfo);
   }
 
   static std::string getEdgeSourceLabel(const BasicBlock *Node,
                                         succ_const_iterator I) {
     // Label source of conditional branches with "T" or "F"
     if (const BranchInst *BI = dyn_cast<BranchInst>(Node->getTerminator()))
       if (BI->isConditional())
         return (I == succ_begin(Node)) ? "T" : "F";
 
     // Label source of switch edges with the associated value.
     if (const SwitchInst *SI = dyn_cast<SwitchInst>(Node->getTerminator())) {
       unsigned SuccNo = I.getSuccessorIndex();
 
-      if (SuccNo == 0) return "def";
+      if (SuccNo == 0)
+        return "def";
 
       std::string Str;
       raw_string_ostream OS(Str);
       auto Case = *SwitchInst::ConstCaseIt::fromSuccessorIndex(SI, SuccNo);
       OS << Case.getCaseValue()->getValue();
       return OS.str();
     }
     return "";
   }
 
   /// Display the raw branch weights from PGO.
   std::string getEdgeAttributes(const BasicBlock *Node, succ_const_iterator I,
-                                const Function *F) {
+                                CFGDOTInfo *CFGInfo) {
+    if (!CFGInfo->showEdgeWeights())
+      return "";
+
     const Instruction *TI = Node->getTerminator();
     if (TI->getNumSuccessors() == 1)
+      return "penwidth=2";
+
+    unsigned OpNo = I.getSuccessorIndex();
+
+    if (OpNo >= TI->getNumSuccessors())
       return "";
 
+    BasicBlock *SuccBB = TI->getSuccessor(OpNo);
+    auto BranchProb = CFGInfo->getBPI()->getEdgeProbability(Node, SuccBB);
+    double WeightPercent = ((double)BranchProb.getNumerator()) /
+                           ((double)BranchProb.getDenominator());
+    double Width = 1 + WeightPercent;
+
+    if (!CFGInfo->useRawEdgeWeights())
+      return formatv("label=\"{0:P}\" penwidth={1}", WeightPercent, Width)
+          .str();
+
+    // Prepend a 'W' to indicate that this is a weight rather than the actual
+    // profile count (due to scaling).
+
+    uint64_t Freq = CFGInfo->getFreq(Node);
+    std::string Attrs = formatv("label=\"W:{0}\" penwidth={1}",
+                    (uint64_t)(Freq * WeightPercent), Width);
+    if (Attrs.size())
+      return Attrs;
+
     MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
     if (!WeightsNode)
       return "";
 
     MDString *MDName = cast<MDString>(WeightsNode->getOperand(0));
     if (MDName->getString() != "branch_weights")
       return "";
 
-    unsigned OpNo = I.getSuccessorIndex() + 1;
+    OpNo = I.getSuccessorIndex() + 1;
     if (OpNo >= WeightsNode->getNumOperands())
       return "";
     ConstantInt *Weight =
         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(OpNo));
     if (!Weight)
       return "";
+    return ("label=\"W:" + std::to_string(Weight->getZExtValue()) +
+            "\" penwidth=" + std::to_string(Width));
+  }
 
-    // Prepend a 'W' to indicate that this is a weight rather than the actual
-    // profile count (due to scaling).
-    return ("label=\"W:" + Twine(Weight->getZExtValue()) + "\"").str();
+  std::string getNodeAttributes(const BasicBlock *Node, CFGDOTInfo *CFGInfo) {
+
+    if (!CFGInfo->showHeatColors())
+      return "";
+
+    uint64_t Freq = CFGInfo->getFreq(Node);
+    std::string Color = getHeatColor(Freq, CFGInfo->getMaxFreq());
+    std::string EdgeColor = (Freq <= (CFGInfo->getMaxFreq() / 2))
+                                ? (getHeatColor(0))
+                                : (getHeatColor(1));
+
+    std::string Attrs = "color=\"" + EdgeColor + "ff\", style=filled," +
+                        "fillcolor=\"" + Color + "70\"";
+    return Attrs;
   }
   bool isNodeHidden(const BasicBlock *Node);
   void computeHiddenNodes(const Function *F);
 };
-} // End llvm namespace
+} // namespace llvm
 
 namespace llvm {
-  class FunctionPass;
-  FunctionPass *createCFGPrinterLegacyPassPass ();
-  FunctionPass *createCFGOnlyPrinterLegacyPassPass ();
-} // End llvm namespace
+class ModulePass;
+ModulePass *createCFGPrinterLegacyPassPass();
+ModulePass *createCFGOnlyPrinterLegacyPassPass();
+} // namespace llvm
 
 #endif

llvm/include/llvm/Analysis/HeatUtils.h

+//===-- HeatUtils.h - Utility for printing heat colors ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Utility for printing heat colors based on heuristics or profiling
+// information.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_HEATUTILS_H
+#define LLVM_ANALYSIS_HEATUTILS_H
+
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
+
+#include <string>
+
+namespace llvm {
+
+uint64_t
+getNumOfCalls(Function &callerFunction, Function &calledFunction,
+              function_ref<BlockFrequencyInfo *(Function &)> LookupBFI);
+
+uint64_t
+getNumOfCalls(CallSite &callsite,
+              function_ref<BlockFrequencyInfo *(Function &)> LookupBFI);
+
+uint64_t getMaxFreq(const Function &F, const BlockFrequencyInfo *BFI);
+
+std::string getHeatColor(uint64_t freq, uint64_t maxFreq);
+
+std::string getHeatColor(double percent);
+
+} // namespace llvm
+
+#endif
 No newline at end of file

llvm/lib/Analysis/CFGPrinter.cpp

static cl::opt<std::string> CFGDotFilenamePrefix(
     cl::desc("The prefix used for the CFG dot file names."));
 
 static cl::opt<bool> HideUnreachablePaths("cfg-hide-unreachable-paths",
             cl::init(false));
 
 static cl::opt<bool> HideDeoptimizePaths("cfg-hide-deoptimize-paths",
             cl::init(false));
 
+static cl::opt<bool> ShowHeatColors("cfg-heat-colors", cl::init(false),
+                                    cl::Hidden,
+                                    cl::desc("Show heat colors in CFG"));
+
+static cl::opt<bool> UseRawEdgeWeight("cfg-raw-weights", cl::init(false),
+                                      cl::Hidden,
+                                      cl::desc("Use raw weights for labels. "
+                                               "Use percentages as default."));
+
+static cl::opt<bool> ShowEdgeWeight("cfg-weights", cl::init(false), cl::Hidden,
+                                    cl::desc("Show edges labeled with weights"));
+
+static void writeHeatCFGToDotFile(Function &F, BlockFrequencyInfo *BFI,
+                                 BranchProbabilityInfo *BPI, uint64_t MaxFreq,
+                                 bool UseHeuristic, bool isSimple) {
+  std::string Filename =
+      (CFGDotFilenamePrefix + "." + F.getName() + ".dot").str();
+  errs() << "Writing '" << Filename << "'...";
+
+  std::error_code EC;
+  raw_fd_ostream File(Filename, EC, sys::fs::F_Text);
+
+  CFGDOTInfo CFGInfo(&F, BFI, BPI, MaxFreq);
+  CFGInfo.setHeuristic(UseHeuristic);
+  CFGInfo.setHeatColors(ShowHeatColors);
+  CFGInfo.setEdgeWeights(ShowEdgeWeight);
+  CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
+
+  if (!EC)
+    WriteGraph(File, &CFGInfo, isSimple);
+  else
+    errs() << "  error opening file for writing!";
+  errs() << "\n";
+}
+
+static void writeAllCFGsToDotFile(Module &M,
+                       function_ref<BlockFrequencyInfo *(Function &)> LookupBFI,
+                       function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
+                       bool isSimple) {
+  uint64_t MaxFreq = 0;
+  for (auto &F : M) {
+    if (F.isDeclaration()) continue;
+    auto *BFI = LookupBFI(F);
+    auto *BPI = LookupBPI(F);
+    MaxFreq = getMaxFreq(F, BFI);
+    writeHeatCFGToDotFile(F, BFI, BPI, MaxFreq, true, isSimple);
+  }
+
+}
+
+static void viewHeatCFG(Function &F, BlockFrequencyInfo *BFI,
+                                 BranchProbabilityInfo *BPI, uint64_t MaxFreq,
+                                 bool UseHeuristic, bool isSimple) {
+  CFGDOTInfo CFGInfo(&F, BFI, BPI, MaxFreq);
+  CFGInfo.setHeuristic(UseHeuristic);
+  CFGInfo.setHeatColors(ShowHeatColors);
+  CFGInfo.setEdgeWeights(ShowEdgeWeight);
+  CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
+
+  ViewGraph(&CFGInfo, "cfg." + F.getName(), isSimple);
+}
+
+static void viewAllCFGs(Module &M,
+                       function_ref<BlockFrequencyInfo *(Function &)> LookupBFI,
+                       function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
+                       bool isSimple) {
+  uint64_t MaxFreq = 0;
+  for (auto &F : M) {
+    if (F.isDeclaration()) continue;
+    auto *BFI = LookupBFI(F);
+    auto *BPI = LookupBPI(F);
+    MaxFreq = getMaxFreq(F, BFI);
+    viewHeatCFG(F, BFI, BPI, MaxFreq, true, isSimple);
+  }
+}
+
 namespace {
-  struct CFGViewerLegacyPass : public FunctionPass {
+  struct CFGViewerLegacyPass : public ModulePass {
     static char ID; // Pass identifcation, replacement for typeid
-    CFGViewerLegacyPass() : FunctionPass(ID) {
+    CFGViewerLegacyPass() : ModulePass(ID) {
       initializeCFGViewerLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
-    bool runOnFunction(Function &F) override {
-      F.viewCFG();
+    bool runOnModule(Module &M) override {
+      auto LookupBFI = [this](Function &F) {
+        return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
+      };
+      auto LookupBPI = [this](Function &F) {
+        return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
+      };
+      viewAllCFGs(M, LookupBFI, LookupBPI, /*isSimple=*/false);
       return false;
     }
 
-    void print(raw_ostream &OS, const Module* = nullptr) const override {}
+    void print(raw_ostream &OS, const Module * = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      ModulePass::getAnalysisUsage(AU);
+      AU.addRequired<BlockFrequencyInfoWrapperPass>();
+      AU.addRequired<BranchProbabilityInfoWrapperPass>();
       AU.setPreservesAll();
     }
-  };
 }
 
 char CFGViewerLegacyPass::ID = 0;
 INITIALIZE_PASS(CFGViewerLegacyPass, "view-cfg", "View CFG of function", false, true)
 
-PreservedAnalyses CFGViewerPass::run(Function &F,
-                                     FunctionAnalysisManager &AM) {
-  F.viewCFG();
+PreservedAnalyses CFGViewerPass::run(Module &M,
+                                     ModuleAnalysisManager &AM) {
+  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+  auto LookupBFI = [&FAM](Function &F) {
+    return &FAM.getResult<BlockFrequencyAnalysis>(F);
+  };
+  auto LookupBPI = [&FAM](Function &F) {
+    return &FAM.getResult<BranchProbabilityAnalysis>(F);
+  };
+  viewAllCFGs(M, LookupBFI, LookupBPI, /*isSimple=*/false);
   return PreservedAnalyses::all();
 }
 
 
 namespace {
-  struct CFGOnlyViewerLegacyPass : public FunctionPass {
+  struct CFGOnlyViewerLegacyPass : public ModulePass {
     static char ID; // Pass identifcation, replacement for typeid
-    CFGOnlyViewerLegacyPass() : FunctionPass(ID) {
+    CFGOnlyViewerLegacyPass() : ModulePass(ID) {
       initializeCFGOnlyViewerLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
-    bool runOnFunction(Function &F) override {
-      F.viewCFGOnly();
+    bool runOnModule(Module &M) override {
+      auto LookupBFI = [this](Function &F) {
+        return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
+      };
+      auto LookupBPI = [this](Function &F) {
+        return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
+      };
+      viewAllCFGs(M, LookupBFI, LookupBPI, /*isSimple=*/true);
       return false;
     }
 
-    void print(raw_ostream &OS, const Module* = nullptr) const override {}
+    void print(raw_ostream &OS, const Module * = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      ModulePass::getAnalysisUsage(AU);
+      AU.addRequired<BlockFrequencyInfoWrapperPass>();
+      AU.addRequired<BranchProbabilityInfoWrapperPass>();
       AU.setPreservesAll();
     }
   };
 }
 
 char CFGOnlyViewerLegacyPass::ID = 0;
 INITIALIZE_PASS(CFGOnlyViewerLegacyPass, "view-cfg-only",
                 "View CFG of function (with no function bodies)", false, true)
 
-PreservedAnalyses CFGOnlyViewerPass::run(Function &F,
-                                         FunctionAnalysisManager &AM) {
-  F.viewCFGOnly();
+PreservedAnalyses CFGOnlyViewerPass::run(Module &M,
+                                         ModuleAnalysisManager &AM) {
+  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+  auto LookupBFI = [&FAM](Function &F) {
+    return &FAM.getResult<BlockFrequencyAnalysis>(F);
+  };
+  auto LookupBPI = [&FAM](Function &F) {
+    return &FAM.getResult<BranchProbabilityAnalysis>(F);
+  };
+  viewAllCFGs(M, LookupBFI, LookupBPI, /*isSimple=*/true);
   return PreservedAnalyses::all();
 }
 
-static void writeCFGToDotFile(Function &F, bool CFGOnly = false) {
-  if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
-     return;
-  std::string Filename =
-      (CFGDotFilenamePrefix + "." + F.getName() + ".dot").str();
-  errs() << "Writing '" << Filename << "'...";
-
-  std::error_code EC;
-  raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
-
-  if (!EC)
-    WriteGraph(File, (const Function*)&F, CFGOnly);
-  else
-    errs() << "  error opening file for writing!";
-  errs() << "\n";
-}
-
 namespace {
-  struct CFGPrinterLegacyPass : public FunctionPass {
+  struct CFGPrinterLegacyPass : public ModulePass {
     static char ID; // Pass identification, replacement for typeid
-    CFGPrinterLegacyPass() : FunctionPass(ID) {
+    CFGPrinterLegacyPass() : ModulePass(ID) {
       initializeCFGPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
-    bool runOnFunction(Function &F) override {
-      writeCFGToDotFile(F);
+    bool runOnModule(Module &M) override {
+      auto LookupBFI = [this](Function &F) {
+        return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
+      };
+      auto LookupBPI = [this](Function &F) {
+        return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
+      };
+      writeAllCFGsToDotFile(M, LookupBFI, LookupBPI, /*isSimple=*/false);
       return false;
     }
 
-    void print(raw_ostream &OS, const Module* = nullptr) const override {}
+    void print(raw_ostream &OS, const Module * = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      ModulePass::getAnalysisUsage(AU);
+      AU.addRequired<BlockFrequencyInfoWrapperPass>();
+      AU.addRequired<BranchProbabilityInfoWrapperPass>();
       AU.setPreservesAll();
     }
   };
 }
 
 char CFGPrinterLegacyPass::ID = 0;
 INITIALIZE_PASS(CFGPrinterLegacyPass, "dot-cfg", "Print CFG of function to 'dot' file",
                 false, true)
 
-PreservedAnalyses CFGPrinterPass::run(Function &F,
-                                      FunctionAnalysisManager &AM) {
-  writeCFGToDotFile(F);
+PreservedAnalyses CFGPrinterPass::run(Module &M,
+                                      ModuleAnalysisManager &AM) {
+  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+  auto LookupBFI = [&FAM](Function &F) {
+    return &FAM.getResult<BlockFrequencyAnalysis>(F);
+  };
+  auto LookupBPI = [&FAM](Function &F) {
+    return &FAM.getResult<BranchProbabilityAnalysis>(F);
+  };
+  writeAllCFGsToDotFile(M, LookupBFI, LookupBPI, /*isSimple=*/false);
   return PreservedAnalyses::all();
 }
 
 namespace {
-  struct CFGOnlyPrinterLegacyPass : public FunctionPass {
+  struct CFGOnlyPrinterLegacyPass : public ModulePass {
     static char ID; // Pass identification, replacement for typeid
-    CFGOnlyPrinterLegacyPass() : FunctionPass(ID) {
+    CFGOnlyPrinterLegacyPass() : ModulePass(ID) {
       initializeCFGOnlyPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
-    bool runOnFunction(Function &F) override {
-      writeCFGToDotFile(F, /*CFGOnly=*/true);
+    bool runOnModule(Module &M) override {
+      auto LookupBFI = [this](Function &F) {
+        return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
+      };
+      auto LookupBPI = [this](Function &F) {
+        return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
+      };
+      writeAllCFGsToDotFile(M, LookupBFI, LookupBPI, /*isSimple=*/true);
       return false;
     }
-    void print(raw_ostream &OS, const Module* = nullptr) const override {}
+    void print(raw_ostream &OS, const Module * = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      ModulePass::getAnalysisUsage(AU);
+      AU.addRequired<BlockFrequencyInfoWrapperPass>();
+      AU.addRequired<BranchProbabilityInfoWrapperPass>();
       AU.setPreservesAll();
     }
   };
 }
 
 char CFGOnlyPrinterLegacyPass::ID = 0;
 INITIALIZE_PASS(CFGOnlyPrinterLegacyPass, "dot-cfg-only",
    "Print CFG of function to 'dot' file (with no function bodies)",
    false, true)
 
-PreservedAnalyses CFGOnlyPrinterPass::run(Function &F,
-                                          FunctionAnalysisManager &AM) {
-  writeCFGToDotFile(F, /*CFGOnly=*/true);
+PreservedAnalyses CFGOnlyPrinterPass::run(Module &M,
+                                          ModuleAnalysisManager &AM) {
+  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+  auto LookupBFI = [&FAM](Function &F) {
+    return &FAM.getResult<BlockFrequencyAnalysis>(F);
+  };
+  auto LookupBPI = [&FAM](Function &F) {
+    return &FAM.getResult<BranchProbabilityAnalysis>(F);
+  };
+  writeAllCFGsToDotFile(M, LookupBFI, LookupBPI, /*isSimple=*/true);
   return PreservedAnalyses::all();
 }
 
 /// viewCFG - This function is meant for use from the debugger.  You can just
 /// say 'call F->viewCFG()' and a ghostview window should pop up from the
 /// program, displaying the CFG of the current function.  This depends on there
 /// being a 'dot' and 'gv' program in your path.
 ///
 void Function::viewCFG() const {
   if (!CFGFuncName.empty() && !getName().contains(CFGFuncName))
      return;
-  ViewGraph(this, "cfg" + getName());
+  CFGDOTInfo CFGInfo(this);
+  ViewGraph(&CFGInfo, "cfg" + getName());
 }
 
 /// viewCFGOnly - This function is meant for use from the debugger.  It works
 /// just like viewCFG, but it does not include the contents of basic blocks
 /// into the nodes, just the label.  If you are only interested in the CFG
 /// this can make the graph smaller.
 ///
 void Function::viewCFGOnly() const {
   if (!CFGFuncName.empty() && !getName().contains(CFGFuncName))
      return;
-  ViewGraph(this, "cfg" + getName(), true);
+  CFGDOTInfo CFGInfo(this);
+  ViewGraph(&CFGInfo, "cfg" + getName(), true);
 }
 
-FunctionPass *llvm::createCFGPrinterLegacyPassPass () {
+ModulePass *llvm::createCFGPrinterLegacyPassPass() {
   return new CFGPrinterLegacyPass();
 }
 
-FunctionPass *llvm::createCFGOnlyPrinterLegacyPassPass () {
+ModulePass *llvm::createCFGOnlyPrinterLegacyPassPass() {
   return new CFGOnlyPrinterLegacyPass();
 }
 
-void DOTGraphTraits<const Function *>::computeHiddenNodes(const Function *F) {
+void DOTGraphTraits<CFGDOTInfo *>::computeHiddenNodes(const Function *F) {
   auto evaluateBB = [&](const BasicBlock *Node) {
     if (succ_begin(Node) == succ_end(Node)) {
       const Instruction *TI = Node->getTerminator();
       isHiddenBasicBlock[Node] =
         (HideUnreachablePaths && isa<UnreachableInst>(TI)) ||
         (HideDeoptimizePaths && Node->getTerminatingDeoptimizeCall());
       return;
     }
     isHiddenBasicBlock[Node] = std::all_of(
         succ_begin(Node), succ_end(Node),
         [this](const BasicBlock *BB) { return isHiddenBasicBlock[BB]; });
   };
   /// The post order traversal iteration is done to know the status of
   /// isHiddenBasicBlock for all the successors on the current BB.
   for_each(po_begin(&F->getEntryBlock()), po_end(&F->getEntryBlock()),
            evaluateBB);
 }
 
-bool DOTGraphTraits<const Function *>::isNodeHidden(const BasicBlock *Node) {
+bool DOTGraphTraits<CFGDOTInfo *>::isNodeHidden(const BasicBlock *Node) {
   // If both restricting flags are false, all nodes are displayed.
   if (!HideUnreachablePaths && !HideDeoptimizePaths)
     return false;
   if (isHiddenBasicBlock.find(Node) == isHiddenBasicBlock.end())
     computeHiddenNodes(Node->getParent());
   return isHiddenBasicBlock[Node];
 }

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   DependenceGraphBuilder.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DomTreeUpdater.cpp
   DominanceFrontier.cpp
   EHPersonalities.cpp
   GlobalsModRef.cpp
   GuardUtils.cpp
+  HeatUtils.cpp
   IVDescriptors.cpp
   IVUsers.cpp
   IndirectCallPromotionAnalysis.cpp
   InlineCost.cpp
   InstCount.cpp
   InstructionPrecedenceTracking.cpp
   InstructionSimplify.cpp
   Interval.cpp

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."));
+
 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 (Function &Callee : *M) {
+          uint64_t Counter = getNumOfCalls(F, Callee, LookupBFI);
+          if (Counter > MaxEdgeCount) {
+            MaxEdgeCount = Counter;
+          }
+        }
+      }
+    }
+    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; }
+
+  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";
 
-  static std::string getGraphName(CallGraph *Graph) { return "Call graph"; }
+    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<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 llvm
 
 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 =
+      (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/DomPrinter.cpp

 #include "llvm/Analysis/DomPrinter.h"
 #include "llvm/Analysis/DOTGraphTraitsPass.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/InitializePasses.h"
 
 using namespace llvm;
 
 namespace llvm {
-template<>
-struct DOTGraphTraits<DomTreeNode*> : public DefaultDOTGraphTraits {
+template <>
+struct DOTGraphTraits<DomTreeNode *> : public DefaultDOTGraphTraits {
 
-  DOTGraphTraits (bool isSimple=false)
-    : DefaultDOTGraphTraits(isSimple) {}
+  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
 
   std::string getNodeLabel(DomTreeNode *Node, DomTreeNode *Graph) {
 
     BasicBlock *BB = Node->getBlock();
 
     if (!BB)
       return "Post dominance root node";
 
-
     if (isSimple())
-      return DOTGraphTraits<const Function*>
-        ::getSimpleNodeLabel(BB, BB->getParent());
+      return DOTGraphTraits<CFGDOTInfo *>::getSimpleNodeLabel(BB, nullptr);
     else
-      return DOTGraphTraits<const Function*>
-        ::getCompleteNodeLabel(BB, BB->getParent());
+      return DOTGraphTraits<CFGDOTInfo *>::getCompleteNodeLabel(BB, nullptr);
   }
 };
 
-template<>
-struct DOTGraphTraits<DominatorTree*> : public DOTGraphTraits<DomTreeNode*> {
+template <>
+struct DOTGraphTraits<DominatorTree *> : public DOTGraphTraits<DomTreeNode *> {
 
-  DOTGraphTraits (bool isSimple=false)
-    : DOTGraphTraits<DomTreeNode*>(isSimple) {}
+  DOTGraphTraits(bool isSimple = false)
+      : DOTGraphTraits<DomTreeNode *>(isSimple) {}
 
   static std::string getGraphName(DominatorTree *DT) {
     return "Dominator tree";
   }
 
   std::string getNodeLabel(DomTreeNode *Node, DominatorTree *G) {
-    return DOTGraphTraits<DomTreeNode*>::getNodeLabel(Node, G->getRootNode());
+    return DOTGraphTraits<DomTreeNode *>::getNodeLabel(Node, G->getRootNode());
   }
 };
 
-template<>
-struct DOTGraphTraits<PostDominatorTree*>
-  : public DOTGraphTraits<DomTreeNode*> {
+template <>
+struct DOTGraphTraits<PostDominatorTree *>
+    : public DOTGraphTraits<DomTreeNode *> {
 
-  DOTGraphTraits (bool isSimple=false)
-    : DOTGraphTraits<DomTreeNode*>(isSimple) {}
+  DOTGraphTraits(bool isSimple = false)
+      : DOTGraphTraits<DomTreeNode *>(isSimple) {}
 
   static std::string getGraphName(PostDominatorTree *DT) {
     return "Post dominator tree";
   }
 
-  std::string getNodeLabel(DomTreeNode *Node, PostDominatorTree *G ) {
-    return DOTGraphTraits<DomTreeNode*>::getNodeLabel(Node, G->getRootNode());
+  std::string getNodeLabel(DomTreeNode *Node, PostDominatorTree *G) {
+    return DOTGraphTraits<DomTreeNode *>::getNodeLabel(Node, G->getRootNode());
   }
 };
 }
 
 void DominatorTree::viewGraph(const Twine &Name, const Twine &Title) {
 #ifndef NDEBUG
   ViewGraph(this, Name, false, Title);
 #else
   errs() << "DomTree dump not available, build with DEBUG\n";
-#endif  // NDEBUG
+#endif // NDEBUG
 }
 
 void DominatorTree::viewGraph() {
 #ifndef NDEBUG
   this->viewGraph("domtree", "Dominator Tree for function");
 #else
   errs() << "DomTree dump not available, build with DEBUG\n";
-#endif  // NDEBUG
+#endif // NDEBUG
 }
 
 namespace {
 struct DominatorTreeWrapperPassAnalysisGraphTraits {
   static DominatorTree *getGraph(DominatorTreeWrapperPass *DTWP) {
     return &DTWP->getDomTree();
   }
 };
 
-struct DomViewer : public DOTGraphTraitsViewer<
-                       DominatorTreeWrapperPass, false, DominatorTree *,
+struct DomViewer
+    : public DOTGraphTraitsViewer<DominatorTreeWrapperPass, false,
+                                  DominatorTree *,
                                   DominatorTreeWrapperPassAnalysisGraphTraits> {
   static char ID;
   DomViewer()
       : DOTGraphTraitsViewer<DominatorTreeWrapperPass, false, DominatorTree *,
-                             DominatorTreeWrapperPassAnalysisGraphTraits>(
-            "dom", ID) {
+                             DominatorTreeWrapperPassAnalysisGraphTraits>("dom",
+                                                                          ID) {
     initializeDomViewerPass(*PassRegistry::getPassRegistry());
   }
 };
 
-struct DomOnlyViewer : public DOTGraphTraitsViewer<
-                           DominatorTreeWrapperPass, true, DominatorTree *,
+struct DomOnlyViewer
+    : public DOTGraphTraitsViewer<DominatorTreeWrapperPass, true,
+                                  DominatorTree *,
                                   DominatorTreeWrapperPassAnalysisGraphTraits> {
   static char ID;
   DomOnlyViewer()
       : DOTGraphTraitsViewer<DominatorTreeWrapperPass, true, DominatorTree *,
                              DominatorTreeWrapperPassAnalysisGraphTraits>(
             "domonly", ID) {
     initializeDomOnlyViewerPass(*PassRegistry::getPassRegistry());
   }
 };
 
 struct PostDominatorTreeWrapperPassAnalysisGraphTraits {
   static PostDominatorTree *getGraph(PostDominatorTreeWrapperPass *PDTWP) {
     return &PDTWP->getPostDomTree();
   }
 };
 
-struct PostDomViewer : public DOTGraphTraitsViewer<
-                          PostDominatorTreeWrapperPass, false,
-                          PostDominatorTree *,
-                          PostDominatorTreeWrapperPassAnalysisGraphTraits> {
+struct PostDomViewer
+    : public DOTGraphTraitsViewer<
+          PostDominatorTreeWrapperPass, false, PostDominatorTree *,
   static char ID;
-  PostDomViewer() :
-    DOTGraphTraitsViewer<PostDominatorTreeWrapperPass, false,
+  PostDomViewer()
+      : DOTGraphTraitsViewer<PostDominatorTreeWrapperPass, false,
                              PostDominatorTree *,
                              PostDominatorTreeWrapperPassAnalysisGraphTraits>(
-        "postdom", ID){
-      initializePostDomViewerPass(*PassRegistry::getPassRegistry());
-    }
+            "postdom", ID) {
 };
 
-struct PostDomOnlyViewer : public DOTGraphTraitsViewer<
-                            PostDominatorTreeWrapperPass, true,
-                            PostDominatorTree *,
-                            PostDominatorTreeWrapperPassAnalysisGraphTraits> {
+struct PostDomOnlyViewer
+    : public DOTGraphTraitsViewer<
+          PostDominatorTreeWrapperPass, true, PostDominatorTree *,
   static char ID;
-  PostDomOnlyViewer() :
-    DOTGraphTraitsViewer<PostDominatorTreeWrapperPass, true,
+  PostDomOnlyViewer()
+      : DOTGraphTraitsViewer<PostDominatorTreeWrapperPass, true,
                              PostDominatorTree *,
                              PostDominatorTreeWrapperPassAnalysisGraphTraits>(
-        "postdomonly", ID){
-      initializePostDomOnlyViewerPass(*PassRegistry::getPassRegistry());
-    }
+            "postdomonly", ID) {
 };
 } // end anonymous namespace
 
 char DomViewer::ID = 0;
-INITIALIZE_PASS(DomViewer, "view-dom",
-                "View dominance tree of function", false, false)
+INITIALIZE_PASS(DomViewer, "view-dom", "View dominance tree of function", false,
+                false)
 
 char DomOnlyViewer::ID = 0;
 INITIALIZE_PASS(DomOnlyViewer, "view-dom-only",
                 "View dominance tree of function (with no function bodies)",
                 false, false)
 
 char PostDomViewer::ID = 0;
 INITIALIZE_PASS(PostDomViewer, "view-postdom",
DomOnlyPrinter()
       : DOTGraphTraitsPrinter<DominatorTreeWrapperPass, true, DominatorTree *,
                               DominatorTreeWrapperPassAnalysisGraphTraits>(
             "domonly", ID) {
     initializeDomOnlyPrinterPass(*PassRegistry::getPassRegistry());
   }
 };
 
 struct PostDomPrinter
     : public DOTGraphTraitsPrinter<
-                            PostDominatorTreeWrapperPass, false,
-                            PostDominatorTree *,
-                            PostDominatorTreeWrapperPassAnalysisGraphTraits> {
+          PostDominatorTreeWrapperPass, false, PostDominatorTree *,
   static char ID;
-  PostDomPrinter() :
-    DOTGraphTraitsPrinter<PostDominatorTreeWrapperPass, false,
+  PostDomPrinter()
+      : DOTGraphTraitsPrinter<PostDominatorTreeWrapperPass, false,
                               PostDominatorTree *,
                               PostDominatorTreeWrapperPassAnalysisGraphTraits>(
             "postdom", ID) {
-      initializePostDomPrinterPass(*PassRegistry::getPassRegistry());
-    }
 };
 
 struct PostDomOnlyPrinter
     : public DOTGraphTraitsPrinter<
-                            PostDominatorTreeWrapperPass, true,
-                            PostDominatorTree *,
-                            PostDominatorTreeWrapperPassAnalysisGraphTraits> {
+          PostDominatorTreeWrapperPass, true, PostDominatorTree *,
   static char ID;
-  PostDomOnlyPrinter() :
-    DOTGraphTraitsPrinter<PostDominatorTreeWrapperPass, true,
+  PostDomOnlyPrinter()
+      : DOTGraphTraitsPrinter<PostDominatorTreeWrapperPass, true,
                               PostDominatorTree *,
                               PostDominatorTreeWrapperPassAnalysisGraphTraits>(
             "postdomonly", ID) {
-      initializePostDomOnlyPrinterPass(*PassRegistry::getPassRegistry());
-    }
 };
 } // end anonymous namespace
 
-
-
 char DomPrinter::ID = 0;
 INITIALIZE_PASS(DomPrinter, "dot-dom",
-                "Print dominance tree of function to 'dot' file",
-                false, false)
+                "Print dominance tree of function to 'dot' file", false, false)
 
 char DomOnlyPrinter::ID = 0;
 INITIALIZE_PASS(DomOnlyPrinter, "dot-dom-only",
                 "Print dominance tree of function to 'dot' file "
                 "(with no function bodies)",
                 false, false)
 
 char PostDomPrinter::ID = 0;
 INITIALIZE_PASS(PostDomPrinter, "dot-postdom",
-                "Print postdominance tree of function to 'dot' file",
-                false, false)
+                "Print postdominance tree of function to 'dot' file", false,
+                false)
 
 char PostDomOnlyPrinter::ID = 0;
 INITIALIZE_PASS(PostDomOnlyPrinter, "dot-postdom-only",
                 "Print postdominance tree of function to 'dot' file "
                 "(with no function bodies)",
                 false, false)
 
 // Create methods available outside of this file, to use them
 // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
 // the link time optimization.
 
-FunctionPass *llvm::createDomPrinterPass() {
-  return new DomPrinter();
-}
+FunctionPass *llvm::createDomPrinterPass() { return new DomPrinter(); }
 
-FunctionPass *llvm::createDomOnlyPrinterPass() {
-  return new DomOnlyPrinter();
-}
+FunctionPass *llvm::createDomOnlyPrinterPass() { return new DomOnlyPrinter(); }
 
-FunctionPass *llvm::createDomViewerPass() {
-  return new DomViewer();
-}
+FunctionPass *llvm::createDomViewerPass() { return new DomViewer(); }
 
-FunctionPass *llvm::createDomOnlyViewerPass() {
-  return new DomOnlyViewer();
-}
+FunctionPass *llvm::createDomOnlyViewerPass() { return new DomOnlyViewer(); }
 
-FunctionPass *llvm::createPostDomPrinterPass() {
-  return new PostDomPrinter();
-}
+FunctionPass *llvm::createPostDomPrinterPass() { return new PostDomPrinter(); }
 
 FunctionPass *llvm::createPostDomOnlyPrinterPass() {
   return new PostDomOnlyPrinter();
 }
 
-FunctionPass *llvm::createPostDomViewerPass() {
-  return new PostDomViewer();
-}
+FunctionPass *llvm::createPostDomViewerPass() { return new PostDomViewer(); }
 
 FunctionPass *llvm::createPostDomOnlyViewerPass() {
   return new PostDomOnlyViewer();
 }

llvm/lib/Analysis/HeatUtils.cpp

+//===-- HeatUtils.cpp - Utility for printing heat colors --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Utility for printing heat colors based on heuristics or profiling
+// information.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/HeatUtils.h"
+#include "llvm/IR/Instructions.h"
+
+namespace llvm {
+
+static const unsigned heatSize = 100;
+static const std::string heatPalette[heatSize] = {
+    "#3d50c3", "#4055c8", "#4358cb", "#465ecf", "#4961d2", "#4c66d6", "#4f69d9",
+    "#536edd", "#5572df", "#5977e3", "#5b7ae5", "#5f7fe8", "#6282ea", "#6687ed",
+    "#6a8bef", "#6c8ff1", "#7093f3", "#7396f5", "#779af7", "#7a9df8", "#7ea1fa",
+    "#81a4fb", "#85a8fc", "#88abfd", "#8caffe", "#8fb1fe", "#93b5fe", "#96b7ff",
+    "#9abbff", "#9ebeff", "#a1c0ff", "#a5c3fe", "#a7c5fe", "#abc8fd", "#aec9fc",
+    "#b2ccfb", "#b5cdfa", "#b9d0f9", "#bbd1f8", "#bfd3f6", "#c1d4f4", "#c5d6f2",
+    "#c7d7f0", "#cbd8ee", "#cedaeb", "#d1dae9", "#d4dbe6", "#d6dce4", "#d9dce1",
+    "#dbdcde", "#dedcdb", "#e0dbd8", "#e3d9d3", "#e5d8d1", "#e8d6cc", "#ead5c9",
+    "#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;
+}
+
+std::string getHeatColor(uint64_t freq, uint64_t maxFreq) {
+  if (freq > maxFreq)
+    freq = maxFreq;
+  double percent = log2(double(freq)) / log2(maxFreq);
+  return getHeatColor(percent);
+}
+
+std::string getHeatColor(double percent) {
+  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/lib/Analysis/RegionPrinter.cpp

 #ifndef NDEBUG
 #include "llvm/IR/LegacyPassManager.h"
 #endif
 
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
 /// onlySimpleRegion - Show only the simple regions in the RegionViewer.
-static cl::opt<bool>
-onlySimpleRegions("only-simple-regions",
-                  cl::desc("Show only simple regions in the graphviz viewer"),
-                  cl::Hidden,
-                  cl::init(false));
+static cl::opt<bool> onlySimpleRegions(
+    "only-simple-regions",
+    cl::desc("Show only simple regions in the graphviz viewer"), cl::Hidden,
 
 namespace llvm {
-template<>
-struct DOTGraphTraits<RegionNode*> : public DefaultDOTGraphTraits {
+template <> struct DOTGraphTraits<RegionNode *> : public DefaultDOTGraphTraits {
 
-  DOTGraphTraits (bool isSimple=false)
-    : DefaultDOTGraphTraits(isSimple) {}
+  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
 
   std::string getNodeLabel(RegionNode *Node, RegionNode *Graph) {
 
     if (!Node->isSubRegion()) {
       BasicBlock *BB = Node->getNodeAs<BasicBlock>();
 
       if (isSimple())
-        return DOTGraphTraits<const Function*>
-          ::getSimpleNodeLabel(BB, BB->getParent());
+        return DOTGraphTraits<CFGDOTInfo *>::getSimpleNodeLabel(BB, nullptr);
       else
-        return DOTGraphTraits<const Function*>
-          ::getCompleteNodeLabel(BB, BB->getParent());
+        return DOTGraphTraits<CFGDOTInfo *>::getCompleteNodeLabel(BB, nullptr);
     }
 
     return "Not implemented";
   }
 };
 
 template <>
 struct DOTGraphTraits<RegionInfo *> : public DOTGraphTraits<RegionNode *> {
 
-  DOTGraphTraits (bool isSimple = false)
-    : DOTGraphTraits<RegionNode*>(isSimple) {}
+  DOTGraphTraits(bool isSimple = false)
+      : DOTGraphTraits<RegionNode *>(isSimple) {}
 
   static std::string getGraphName(const RegionInfo *) { return "Region Graph"; }
 
   std::string getNodeLabel(RegionNode *Node, RegionInfo *G) {
     return DOTGraphTraits<RegionNode *>::getNodeLabel(
         Node, reinterpret_cast<RegionNode *>(G->getTopLevelRegion()));
   }
 
std::string getEdgeAttributes(RegionNode *srcNode,
     return "";
   }
 
   // Print the cluster of the subregions. This groups the single basic blocks
   // and adds a different background color for each group.
   static void printRegionCluster(const Region &R, GraphWriter<RegionInfo *> &GW,
                                  unsigned depth = 0) {
     raw_ostream &O = GW.getOStream();
-    O.indent(2 * depth) << "subgraph cluster_" << static_cast<const void*>(&R)
+    O.indent(2 * depth) << "subgraph cluster_" << static_cast<const void *>(&R)
                         << " {\n";
     O.indent(2 * (depth + 1)) << "label = \"\";\n";
 
     if (!onlySimpleRegions || R.isSimple()) {
       O.indent(2 * (depth + 1)) << "style = filled;\n";
-      O.indent(2 * (depth + 1)) << "color = "
-        << ((R.getDepth() * 2 % 12) + 1) << "\n";
+      O.indent(2 * (depth + 1))
+          << "color = " << ((R.getDepth() * 2 % 12) + 1) << "\n";
 
     } else {
       O.indent(2 * (depth + 1)) << "style = solid;\n";
-      O.indent(2 * (depth + 1)) << "color = "
-        << ((R.getDepth() * 2 % 12) + 2) << "\n";
+      O.indent(2 * (depth + 1))
+          << "color = " << ((R.getDepth() * 2 % 12) + 2) << "\n";
     }
 
     for (const auto &RI : R)
       printRegionCluster(*RI, GW, depth + 1);
 
-    const RegionInfo &RI = *static_cast<const RegionInfo*>(R.getRegionInfo());
+    const RegionInfo &RI = *static_cast<const RegionInfo *>(R.getRegionInfo());
 
     for (auto *BB : R.blocks())
       if (RI.getRegionFor(BB) == &R)
-        O.indent(2 * (depth + 1)) << "Node"
-          << static_cast<const void*>(RI.getTopLevelRegion()->getBBNode(BB))
+        O.indent(2 * (depth + 1))
+            << "Node"
+            << static_cast<const void *>(RI.getTopLevelRegion()->getBBNode(BB))
             << ";\n";
 
     O.indent(2 * depth) << "}\n";
   }
 
   static void addCustomGraphFeatures(const RegionInfo *G,
                                      GraphWriter<RegionInfo *> &GW) {
     raw_ostream &O = GW.getOStream();
     O << "\tcolorscheme = \"paired12\"\n";
     printRegionCluster(*G->getTopLevelRegion(), GW, 4);
   }
 };
-} //end namespace llvm
+} // end namespace llvm
 
 namespace {
 
 struct RegionInfoPassGraphTraits {
   static RegionInfo *getGraph(RegionInfoPass *RIP) {
     return &RIP->getRegionInfo();
   }
 };
struct RegionOnlyViewer
   RegionOnlyViewer()
       : DOTGraphTraitsViewer<RegionInfoPass, true, RegionInfo *,
                              RegionInfoPassGraphTraits>("regonly", ID) {
     initializeRegionOnlyViewerPass(*PassRegistry::getPassRegistry());
   }
 };
 char RegionOnlyViewer::ID = 0;
 
-} //end anonymous namespace
+} // end anonymous namespace
 
 INITIALIZE_PASS(RegionPrinter, "dot-regions",
                 "Print regions of function to 'dot' file", true, true)
 
 INITIALIZE_PASS(
     RegionOnlyPrinter, "dot-regions-only",
     "Print regions of function to 'dot' file (with no function bodies)", true,
     true)
 
-INITIALIZE_PASS(RegionViewer, "view-regions", "View regions of function",
-                true, true)
+INITIALIZE_PASS(RegionViewer, "view-regions", "View regions of function", true,
+                true)
 
 INITIALIZE_PASS(RegionOnlyViewer, "view-regions-only",
-                "View regions of function (with no function bodies)",
-                true, true)
+                "View regions of function (with no function bodies)", true,
+                true)
 
 FunctionPass *llvm::createRegionPrinterPass() { return new RegionPrinter(); }
 
 FunctionPass *llvm::createRegionOnlyPrinterPass() {
   return new RegionOnlyPrinter();
 }
 
-FunctionPass* llvm::createRegionViewerPass() {
-  return new RegionViewer();
-}
+FunctionPass *llvm::createRegionViewerPass() { return new RegionViewer(); }
 
-FunctionPass* llvm::createRegionOnlyViewerPass() {
+FunctionPass *llvm::createRegionOnlyViewerPass() {
   return new RegionOnlyViewer();
 }
 
 #ifndef NDEBUG
 static void viewRegionInfo(RegionInfo *RI, bool ShortNames) {
   assert(RI && "Argument must be non-null");
 
   llvm::Function *F = RI->getTopLevelRegion()->getEntry()->getParent();

llvm/lib/Passes/PassRegistry.def

 MODULE_PASS("always-inline", AlwaysInlinerPass())
 MODULE_PASS("attributor", AttributorPass())
 MODULE_PASS("called-value-propagation", CalledValuePropagationPass())
 MODULE_PASS("canonicalize-aliases", CanonicalizeAliasesPass())
 MODULE_PASS("cg-profile", CGProfilePass())
 MODULE_PASS("constmerge", ConstantMergePass())
 MODULE_PASS("cross-dso-cfi", CrossDSOCFIPass())
 MODULE_PASS("deadargelim", DeadArgumentEliminationPass())
+MODULE_PASS("dot-cfg", CFGPrinterPass())
+MODULE_PASS("dot-cfg-only", CFGOnlyPrinterPass())
 MODULE_PASS("elim-avail-extern", EliminateAvailableExternallyPass())
 MODULE_PASS("forceattrs", ForceFunctionAttrsPass())
 MODULE_PASS("function-import", FunctionImportPass())
 MODULE_PASS("globaldce", GlobalDCEPass())
 MODULE_PASS("globalopt", GlobalOptPass())
 MODULE_PASS("globalsplit", GlobalSplitPass())
 MODULE_PASS("hotcoldsplit", HotColdSplittingPass())
 MODULE_PASS("hwasan", HWAddressSanitizerPass(false, false))

 MODULE_PASS("wholeprogramdevirt", WholeProgramDevirtPass(nullptr, nullptr))
 MODULE_PASS("verify", VerifierPass())
 MODULE_PASS("asan-module", ModuleAddressSanitizerPass(/*CompileKernel=*/false, false, true, false))
 MODULE_PASS("msan-module", MemorySanitizerPass({}))
 MODULE_PASS("tsan-module", ThreadSanitizerPass())
 MODULE_PASS("kasan-module", ModuleAddressSanitizerPass(/*CompileKernel=*/true, false, true, false))
 MODULE_PASS("sancov-module", ModuleSanitizerCoveragePass())
 MODULE_PASS("poison-checking", PoisonCheckingPass())
+MODULE_PASS("view-cfg", CFGViewerPass())
+MODULE_PASS("view-cfg-only", CFGOnlyViewerPass())
 #undef MODULE_PASS
 
 #ifndef CGSCC_ANALYSIS
 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)
 #endif
 CGSCC_ANALYSIS("no-op-cgscc", NoOpCGSCCAnalysis())
 CGSCC_ANALYSIS("fam-proxy", FunctionAnalysisManagerCGSCCProxy())
 CGSCC_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC))

 FUNCTION_PASS("chr", ControlHeightReductionPass())
 FUNCTION_PASS("coro-early", CoroEarlyPass())
 FUNCTION_PASS("coro-elide", CoroElidePass())
 FUNCTION_PASS("coro-cleanup", CoroCleanupPass())
 FUNCTION_PASS("correlated-propagation", CorrelatedValuePropagationPass())
 FUNCTION_PASS("dce", DCEPass())
 FUNCTION_PASS("div-rem-pairs", DivRemPairsPass())
 FUNCTION_PASS("dse", DSEPass())
-FUNCTION_PASS("dot-cfg", CFGPrinterPass())
-FUNCTION_PASS("dot-cfg-only", CFGOnlyPrinterPass())
 FUNCTION_PASS("early-cse", EarlyCSEPass(/*UseMemorySSA=*/false))
 FUNCTION_PASS("early-cse-memssa", EarlyCSEPass(/*UseMemorySSA=*/true))
 FUNCTION_PASS("ee-instrument", EntryExitInstrumenterPass(/*PostInlining=*/false))
 FUNCTION_PASS("make-guards-explicit", MakeGuardsExplicitPass())
 FUNCTION_PASS("post-inline-ee-instrument", EntryExitInstrumenterPass(/*PostInlining=*/true))
 FUNCTION_PASS("gvn-hoist", GVNHoistPass())
 FUNCTION_PASS("instcombine", InstCombinePass())
 FUNCTION_PASS("instsimplify", InstSimplifyPass())

 FUNCTION_PASS("vector-combine", VectorCombinePass())
 FUNCTION_PASS("verify", VerifierPass())
 FUNCTION_PASS("verify<domtree>", DominatorTreeVerifierPass())
 FUNCTION_PASS("verify<loops>", LoopVerifierPass())
 FUNCTION_PASS("verify<memoryssa>", MemorySSAVerifierPass())
 FUNCTION_PASS("verify<regions>", RegionInfoVerifierPass())
 FUNCTION_PASS("verify<safepoint-ir>", SafepointIRVerifierPass())
 FUNCTION_PASS("verify<scalar-evolution>", ScalarEvolutionVerifierPass())
-FUNCTION_PASS("view-cfg", CFGViewerPass())
-FUNCTION_PASS("view-cfg-only", CFGOnlyViewerPass())
 FUNCTION_PASS("transform-warning", WarnMissedTransformationsPass())
 FUNCTION_PASS("asan", AddressSanitizerPass(false, false, false))
 FUNCTION_PASS("kasan", AddressSanitizerPass(true, false, false))
 FUNCTION_PASS("msan", MemorySanitizerPass({}))
 FUNCTION_PASS("kmsan", MemorySanitizerPass({0, false, /*Kernel=*/true}))
 FUNCTION_PASS("tsan", ThreadSanitizerPass())
 #undef FUNCTION_PASS
 

llvm/lib/Transforms/Scalar/NewGVN.cpp

 bool NewGVN::isBackedge(BasicBlock *From, BasicBlock *To) const {
   return From == To ||
          RPOOrdering.lookup(DT->getNode(From)) >=
              RPOOrdering.lookup(DT->getNode(To));
 }
 
 #ifndef NDEBUG
 static std::string getBlockName(const BasicBlock *B) {
-  return DOTGraphTraits<const Function *>::getSimpleNodeLabel(B, nullptr);
+  return DOTGraphTraits<CFGDOTInfo *>::getSimpleNodeLabel(B, nullptr);
 }
 #endif
 
 // Get a MemoryAccess for an instruction, fake or real.
 MemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const {
   auto *Result = MSSA->getMemoryAccess(I);
   return Result ? Result : TempToMemory.lookup(I);
 }
NewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const {
   setBasicExpressionInfo(CI, E);
   return E;
 }
 
 // Return true if some equivalent of instruction Inst dominates instruction U.
 bool NewGVN::someEquivalentDominates(const Instruction *Inst,
                                      const Instruction *U) const {
   auto *CC = ValueToClass.lookup(Inst);
-   // This must be an instruction because we are only called from phi nodes
   // in the case that the value it needs to check against is an instruction.
 
-  // The most likely candidates for dominance are the leader and the next leader.
+  // The most likely candidates for dominance are the leader and the next
+  // leader.
   // The leader or nextleader will dominate in all cases where there is an
   // equivalent that is higher up in the dom tree.
   // We can't *only* check them, however, because the
   // dominator tree could have an infinite number of non-dominating siblings
   // with instructions that are in the right congruence class.
   //       A
   // B C D E F G
   // |
bool NewGVN::isCycleFree(const Instruction *I) const {
   }
   if (ICS == ICS_Cycle)
     return false;
   return true;
 }
 
 // Evaluate PHI nodes symbolically and create an expression result.
 const Expression *
-NewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps,
-                                     Instruction *I,
+NewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps, Instruction *I,
                                      BasicBlock *PHIBlock) const {
   // True if one of the incoming phi edges is a backedge.
   bool HasBackedge = false;
   // All constant tracks the state of whether all the *original* phi operands
   // This is really shorthand for "this phi cannot cycle due to forward
   // change in value of the phi is guaranteed not to later change the value of
   // the phi. IE it can't be v = phi(undef, v+1)
   bool OriginalOpsConstant = true;
if (ReachableEdges.count({PredBB, PHIBlock})) {
             SafeForPHIOfOps &&
             (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps));
       }
       // FIXME: For those things that are not safe we could generate
       // expressions all the way down, and see if this comes out to a
       // constant.  For anything where that is true, and unsafe, we should
       // have made a phi-of-ops (or value numbered it equivalent to something)
       // for the pieces already.
-      FoundVal = !SafeForPHIOfOps ? nullptr
-                                  : findLeaderForInst(ValueOp, Visited,
+      FoundVal =
+          !SafeForPHIOfOps ? nullptr : findLeaderForInst(ValueOp, Visited,
                                                          MemAccess, I, PredBB);
       ValueOp->deleteValue();
       if (!FoundVal) {
         // We failed to find a leader for the current ValueOp, but this might
         // change in case of the translated operands change.
         if (SafeForPHIOfOps)
           for (auto Dep : CurrentDeps)
             addAdditionalUsers(Dep, I);
 

llvm/test/Other/2007-06-05-PassID.ll

 ;RUN: opt < %s -analyze -dot-cfg-only 2>/dev/null
 ;RUN: opt < %s -analyze -passes=dot-cfg-only 2>/dev/null
+;RUN: opt < %s -analyze -dot-cfg-only \
+;RUN:          -cfg-heat-colors=true -cfg-weights=true 2>/dev/null
+;RUN: opt < %s -analyze -dot-cfg-only \
+;RUN:          -cfg-heat-colors=false -cfg-weights=false 2>/dev/null
+;RUN: opt < %s -analyze -dot-cfg \
+;RUN:          -cfg-heat-colors=true -cfg-weights=true 2>/dev/null
+;RUN: opt < %s -analyze -dot-cfg \
+;RUN:          -cfg-heat-colors=false -cfg-weights=false 2>/dev/null
 ;PR 1497
 
 define void @foo() {
 entry:
   br label %return
 
 return:   ; preds = %entry
   ret void
 }
 

llvm/test/Other/cfg-printer-branch-weights-percent.ll

+;RUN: opt < %s -analyze -dot-cfg -cfg-weights -cfg-dot-filename-prefix=%t 2>/dev/null
+;RUN: FileCheck %s -input-file=%t.f.dot
+
+define void @f(i32) {
+entry:
+  %check = icmp sgt i32 %0, 0
+  br i1 %check, label %if, label %exit, !prof !0
+
+; CHECK: label="0.50%"
+; CHECK-NOT: ["];
+if:                     ; preds = %entry
+  br label %exit
+; CHECK: label="99.50%"
+; CHECK-NOT: ["];
+exit:                   ; preds = %entry, %if
+  ret void
+}
+
+!0 = !{!"branch_weights", i32 1, i32 200}

llvm/test/Other/cfg-printer-branch-weights.ll

-;RUN: opt < %s -analyze -dot-cfg -cfg-dot-filename-prefix=%t 2>/dev/null
+;RUN: opt < %s -analyze -dot-cfg -cfg-weights -cfg-raw-weights -cfg-dot-filename-prefix=%t 2>/dev/null
 ;RUN: FileCheck %s -input-file=%t.f.dot
 
 define void @f(i32) {
 entry:
   %check = icmp sgt i32 %0, 0
   br i1 %check, label %if, label %exit, !prof !0
 
-; CHECK: label="W:1"
+; CHECK: label="W:7"
 ; CHECK-NOT: ["];
 if:                     ; preds = %entry
   br label %exit
-; CHECK: label="W:200"
+; CHECK: label="W:1600"
 ; CHECK-NOT: ["];
 exit:                   ; preds = %entry, %if
   ret void
 }
 
 !0 = !{!"branch_weights", i32 1, i32 200}

polly/lib/Analysis/ScopGraphPrinter.cpp

 template <> struct DOTGraphTraits<RegionNode *> : public DefaultDOTGraphTraits {
   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
 
   std::string getNodeLabel(RegionNode *Node, RegionNode *Graph) {
     if (!Node->isSubRegion()) {
       BasicBlock *BB = Node->getNodeAs<BasicBlock>();
 
       if (isSimple())
-        return DOTGraphTraits<const Function *>::getSimpleNodeLabel(
-            BB, BB->getParent());
+        return DOTGraphTraits<CFGDOTInfo *>::getSimpleNodeLabel(BB, nullptr);
+
       else
-        return DOTGraphTraits<const Function *>::getCompleteNodeLabel(
-            BB, BB->getParent());
+        return DOTGraphTraits<CFGDOTInfo *>::getCompleteNodeLabel(BB, nullptr);
     }
 
     return "Not implemented";
   }
 };
 
 template <>
 struct DOTGraphTraits<ScopDetectionWrapperPass *>

polly/lib/Support/RegisterPasses.cpp

#endif
 
   PM.addPass(CodePreparationPass());
   PM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
   PM.addPass(PB.buildFunctionSimplificationPipeline(
       Level, PassBuilder::ThinLTOPhase::None)); // Cleanup
 
   assert(!DumpAfter && "This option is not implemented");
   assert(DumpAfterFile.empty() && "This option is not implemented");
-
-  if (CFGPrinter)
-    PM.addPass(llvm::CFGPrinterPass());
 }
 
 /// Register Polly to be available as an optimizer
 ///
 ///
 /// We can currently run Polly at three different points int the pass manager.
 /// a) very early, b) after the canonicalizing loop transformations and c) right
 /// before the vectorizer.
parseTopLevelPipeline(ModulePassManager &MPM,
   }
 
   FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
   if (VerifyEachPass)
     FPM.addPass(VerifierPass());
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
   if (VerifyEachPass)
     MPM.addPass(VerifierPass());
-
+  if (CFGPrinter)
+    MPM.addPass(llvm::CFGPrinterPass());
   return true;
 }
 
 void registerPollyPasses(PassBuilder &PB) {
   PB.registerAnalysisRegistrationCallback(registerFunctionAnalyses);
   PB.registerPipelineParsingCallback(parseFunctionPipeline);
   PB.registerPipelineParsingCallback(parseScopPipeline);
   PB.registerParseTopLevelPipelineCallback(parseTopLevelPipeline);