Heat Coloring (2/3): Adding Heat Functionality to CFGPrinter

[knaumov]

Summary

This patch is the second 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. This patch introduces the heat coloring of the Control Flow Graph which is based on the relative "hotness" of each BB. All the functionality of this patch was developed and discussed in the preceding patches.

[davidxl]

llvm/include/llvm/Analysis/CFGPrinter.h

276–289

The formatting (indentation) looks wrong. Apply clang-format to fix it.

281

For color blinded folks, using different box size or box boundary thickness may be a better choice. Is it possible to add that?

llvm/include/llvm/Analysis/HeatUtils.h

30

These two methods do not belong to this patch.

[knaumov]

Answering @davidxl 's comments:

• Fixed the introduction of getNumOfCalls methods.
• Concerning the color-blind accessibility - from my research, I have found that the combination of blue and red and all of the intermediate colors are well perceived by the majority of types of color-blind people. I have not found a way to make edges of the boxes gradually bolder to reflect the gradation from cold to hot methods. If any such solutions were to be found, it would be great to implement them, but my suggestion is to do it as a separate future patch while the current series of patches introduces only necessary functionality.
• Clang-Format: I have applied the clang-format on the said file and found out that not only my changes were formatted, but most of the original file as well. I have reverted the clang-format, as it makes the diff big and hard to follow. Of course, once I am going to be pushing the changes, I will apply clang-format over all the files that were altered by my patches.

[davidxl]

For clang-format, you can use clang/tools/clang-format/clang-format-diff.py to format diff only: https://clang.llvm.org/docs/ClangFormat.html.

[davidxl]

lgtm

[kbobyrev]

I already hit one corner case and fixed it with https://github.com/llvm/llvm-project/commit/3847737fa489dc88d1d45bbedc550e87bf88fbe1 but I can totally see more coming with more tests being added. The test coverage is not sufficient and I certainly expect this code to hit more bugs in the future with the current state.

I don't have enough time to look at this whole patch and infrastructure carefully and certainly don't have time to fix it, so please do that since you are the author.

In particular, llvm/lib/Analysis/HeatUtils.cpp looks very scary. There are casts to double (double percent = log2(double(freq)) / log2(maxFreq);) that I don't understand, pieces like this looking very suspicious

if (freq > maxFreq)
  freq = maxFreq;

Corner cases handled in a very strange way

if (percent > 1.0)
  percent = 1.0;
if (percent < 0.0)
  percent = 0.0;

Casts from unsigned to doubles and back again (unsigned colorId = unsigned(round(percent * (heatSize - 1.0)));), and std::strings everywhere.

I would suggest thinking more about floating point arithmetics since the patch I provided fixes the case where percent is NaN and then being casted to unsigned and used as an index in the array...

asserts should be placed in many places to ensure everything is going as planned, if there are any assumptions under which your functions operate they should be documented (// Returns the maximum frequency of a BB in a function. and other comments don't tell anything I couldn't infer from the function signature and don't say anything about the requirements or returned value ranges) and mentioned in the code. I would also not recommend calling a value which is in [0, 1] range percent since percent is from 0 to 100. With all of this, it is really hard to understand the code and later fix it for anyone not familiar with it. And, again, I would expect more bugs to originate from this code if it stays the same.

[knaumov]

Addressed to @kbobyrev:
Thank you for the detailed report! I will add new assert/verification code to cover the point you discussed.

[kbobyrev]

Thank you! And I apologize for the bad tone. I was just very frustrated because I spent a long time trying to figure out what the issue is and it wasn't very clear from the first look, but that's no excuse for the style of my previous message. I do think this infrastructure is useful, so I am looking forward to the new changes!

llvm/include/llvm/Analysis/CFGPrinter.h

 //
 //===----------------------------------------------------------------------===//
 
 #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/PassManager.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/GraphWriter.h"
 
public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
 class DOTFuncInfo {
 private:
   const Function *F;
   const BlockFrequencyInfo *BFI;
   const BranchProbabilityInfo *BPI;
+  uint64_t MaxFreq;
+  bool ShowHeat;
+  bool EdgeWeights;
+  bool RawWeights;
 
 public:
-  DOTFuncInfo(const Function *F) : DOTFuncInfo(F, nullptr, nullptr) {}
+  DOTFuncInfo(const Function *F) : DOTFuncInfo(F, nullptr, nullptr, 0) {}
 
   DOTFuncInfo(const Function *F, const BlockFrequencyInfo *BFI,
-             BranchProbabilityInfo *BPI)
-      : F(F), BFI(BFI), BPI(BPI) {
+             BranchProbabilityInfo *BPI, uint64_t MaxFreq)
+      : F(F), BFI(BFI), BPI(BPI), MaxFreq(MaxFreq) {
+    ShowHeat = false;
+    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 setRawEdgeWeights(bool RawWeights) { this->RawWeights = RawWeights; }
+
+  bool useRawEdgeWeights() { return RawWeights; }
+
+  void setEdgeWeights(bool EdgeWeights) { this->EdgeWeights = EdgeWeights; }
+
+  bool showEdgeWeights() { return EdgeWeights; }
 };
 
 template <>
 struct GraphTraits<DOTFuncInfo *> : public GraphTraits<const BasicBlock *> {
   static NodeRef getEntryNode(DOTFuncInfo *CFGInfo) {
     return &(CFGInfo->getFunction()->getEntryBlock());
   }
 
if (const SwitchInst *SI = dyn_cast<SwitchInst>(Node->getTerminator())) {
       return OS.str();
     }
     return "";
   }
 
   /// Display the raw branch weights from PGO.
   std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I,
                                 DOTFuncInfo *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, DOTFuncInfo *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 {
   class FunctionPass;
   FunctionPass *createCFGPrinterLegacyPassPass ();
   FunctionPass *createCFGOnlyPrinterLegacyPassPass ();
 } // End llvm namespace
 
 #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 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 {
+
+// 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
 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 writeCFGToDotFile(Function &F, BlockFrequencyInfo *BFI,
-                                 BranchProbabilityInfo *BPI,
-                                 bool isSimple) {
+                                 BranchProbabilityInfo *BPI, uint64_t MaxFreq,
+                                 bool CFGOnly = false) {
   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);
 
-  DOTFuncInfo CFGInfo(&F, BFI, BPI);
+  DOTFuncInfo CFGInfo(&F, BFI, BPI, MaxFreq);
+  CFGInfo.setHeatColors(ShowHeatColors);
+  CFGInfo.setEdgeWeights(ShowEdgeWeight);
+  CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
+
   if (!EC)
-    WriteGraph(File, &CFGInfo, isSimple);
+    WriteGraph(File, &CFGInfo, CFGOnly);
   else
     errs() << "  error opening file for writing!";
   errs() << "\n";
 }
 
 static void viewCFG(Function &F, BlockFrequencyInfo *BFI,
-                                 BranchProbabilityInfo *BPI,
-                                 bool isSimple) {
-  DOTFuncInfo CFGInfo(&F, BFI, BPI);
-  ViewGraph(&CFGInfo, "cfg." + F.getName(), isSimple);
+                                 BranchProbabilityInfo *BPI, uint64_t MaxFreq,
+                                 bool CFGOnly = false) {
+  DOTFuncInfo CFGInfo(&F, BFI, BPI, MaxFreq);
+  CFGInfo.setHeatColors(ShowHeatColors);
+  CFGInfo.setEdgeWeights(ShowEdgeWeight);
+  CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
+
+  ViewGraph(&CFGInfo, "cfg." + F.getName(), CFGOnly);
 }
 
 namespace {
   struct CFGViewerLegacyPass : public FunctionPass {
     static char ID; // Pass identifcation, replacement for typeid
     CFGViewerLegacyPass() : FunctionPass(ID) {
       initializeCFGViewerLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
       auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
       auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
-      viewCFG(F, BFI, BPI, /*isSimple=*/false);
+      viewCFG(F, BFI, BPI, getMaxFreq(F, BFI));
       return false;
     }
 
     void print(raw_ostream &OS, const Module* = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
-      FunctionPass::getAnalysisUsage(AU); // Maybe Change to FunctionPass::...
+      FunctionPass::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) {
   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
-  viewCFG(F, BFI, BPI, /*isSimple=*/false);
+  viewCFG(F, BFI, BPI, getMaxFreq(F, BFI));
   return PreservedAnalyses::all();
 }
 
 
 namespace {
   struct CFGOnlyViewerLegacyPass : public FunctionPass {
     static char ID; // Pass identifcation, replacement for typeid
     CFGOnlyViewerLegacyPass() : FunctionPass(ID) {
       initializeCFGOnlyViewerLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
       auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
       auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
-      viewCFG(F, BFI, BPI, /*isSimple=*/false);
+      viewCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
       return false;
     }
 
     void print(raw_ostream &OS, const Module* = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       FunctionPass::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) {
   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
-  viewCFG(F, BFI, BPI, /*isSimple=*/false);
+  viewCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
   return PreservedAnalyses::all();
 }
 
 namespace {
   struct CFGPrinterLegacyPass : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     CFGPrinterLegacyPass() : FunctionPass(ID) {
       initializeCFGPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
       auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
       auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
-      writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false);
+      writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI));
       return false;
     }
 
     void print(raw_ostream &OS, const Module* = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       FunctionPass::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) {
   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
-  writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false);
+  writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI));
   return PreservedAnalyses::all();
 }
 
 namespace {
   struct CFGOnlyPrinterLegacyPass : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     CFGOnlyPrinterLegacyPass() : FunctionPass(ID) {
       initializeCFGOnlyPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
       auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
       auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
-      writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false);
+      writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
       return false;
     }
     void print(raw_ostream &OS, const Module* = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       FunctionPass::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) {
   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
-  writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false);
+  writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/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.
 ///

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/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 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/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}

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
+
+; 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)]+}}"
+
+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}