Index: llvm/include/llvm/Analysis/CFGPrinter.h =================================================================== --- llvm/include/llvm/Analysis/CFGPrinter.h +++ llvm/include/llvm/Analysis/CFGPrinter.h @@ -20,6 +20,7 @@ #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" @@ -58,13 +59,20 @@ 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; } @@ -72,6 +80,24 @@ 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 <> @@ -197,9 +223,37 @@ /// 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 ""; @@ -207,17 +261,32 @@ MDString *MDName = cast(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(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); Index: llvm/include/llvm/Analysis/HeatUtils.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/HeatUtils.h @@ -0,0 +1,48 @@ +//===-- 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 + +namespace llvm { + +// Returns number of calls of calledFunction by callerFunction. +uint64_t +getNumOfCalls(Function &callerFunction, Function &calledFunction, + function_ref LookupBFI); + +// Returns number of calls from the call-site. +uint64_t +getNumOfCalls(CallSite &callsite, + function_ref LookupBFI); + +// Returns the maximum frequency of a BB in a function. +uint64_t getMaxFreq(const Function &F, const BlockFrequencyInfo *BFI); + +// Calculates heat color based on current and maximum frequencies. +std::string getHeatColor(uint64_t freq, uint64_t maxFreq); + +// Calculates heat color based on percent of "hotness". +std::string getHeatColor(double percent); + +} // namespace llvm + +#endif \ No newline at end of file Index: llvm/lib/Analysis/CFGPrinter.cpp =================================================================== --- llvm/lib/Analysis/CFGPrinter.cpp +++ llvm/lib/Analysis/CFGPrinter.cpp @@ -42,9 +42,21 @@ static cl::opt HideDeoptimizePaths("cfg-hide-deoptimize-paths", cl::init(false)); +static cl::opt ShowHeatColors("cfg-heat-colors", cl::init(false), + cl::Hidden, + cl::desc("Show heat colors in CFG")); + +static cl::opt UseRawEdgeWeight("cfg-raw-weights", cl::init(false), + cl::Hidden, + cl::desc("Use raw weights for labels. " + "Use percentages as default.")); + +static cl::opt 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 << "'..."; @@ -52,19 +64,27 @@ 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 { @@ -77,14 +97,14 @@ bool runOnFunction(Function &F) override { auto *BPI = &getAnalysis().getBPI(); auto *BFI = &getAnalysis().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(); AU.addRequired(); AU.setPreservesAll(); @@ -99,7 +119,7 @@ FunctionAnalysisManager &AM) { auto *BFI = &AM.getResult(F); auto *BPI = &AM.getResult(F); - viewCFG(F, BFI, BPI, /*isSimple=*/false); + viewCFG(F, BFI, BPI, getMaxFreq(F, BFI)); return PreservedAnalyses::all(); } @@ -114,7 +134,7 @@ bool runOnFunction(Function &F) override { auto *BPI = &getAnalysis().getBPI(); auto *BFI = &getAnalysis().getBFI(); - viewCFG(F, BFI, BPI, /*isSimple=*/false); + viewCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true); return false; } @@ -137,7 +157,7 @@ FunctionAnalysisManager &AM) { auto *BFI = &AM.getResult(F); auto *BPI = &AM.getResult(F); - viewCFG(F, BFI, BPI, /*isSimple=*/false); + viewCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true); return PreservedAnalyses::all(); } @@ -151,7 +171,7 @@ bool runOnFunction(Function &F) override { auto *BPI = &getAnalysis().getBPI(); auto *BFI = &getAnalysis().getBFI(); - writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false); + writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI)); return false; } @@ -174,7 +194,7 @@ FunctionAnalysisManager &AM) { auto *BFI = &AM.getResult(F); auto *BPI = &AM.getResult(F); - writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false); + writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI)); return PreservedAnalyses::all(); } @@ -188,7 +208,7 @@ bool runOnFunction(Function &F) override { auto *BPI = &getAnalysis().getBPI(); auto *BFI = &getAnalysis().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 {} @@ -211,7 +231,7 @@ FunctionAnalysisManager &AM) { auto *BFI = &AM.getResult(F); auto *BPI = &AM.getResult(F); - writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false); + writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true); return PreservedAnalyses::all(); } Index: llvm/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/lib/Analysis/CMakeLists.txt +++ llvm/lib/Analysis/CMakeLists.txt @@ -34,6 +34,7 @@ EHPersonalities.cpp GlobalsModRef.cpp GuardUtils.cpp + HeatUtils.cpp IVDescriptors.cpp IVUsers.cpp IndirectCallPromotionAnalysis.cpp Index: llvm/lib/Analysis/HeatUtils.cpp =================================================================== --- /dev/null +++ llvm/lib/Analysis/HeatUtils.cpp @@ -0,0 +1,90 @@ +//===-- 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 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 LookupBFI) { + uint64_t counter = 0; + for (User *U : calledFunction.users()) { + if (isa(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 Index: llvm/test/Other/2007-06-05-PassID.ll =================================================================== --- llvm/test/Other/2007-06-05-PassID.ll +++ llvm/test/Other/2007-06-05-PassID.ll @@ -1,5 +1,13 @@ ;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() { Index: llvm/test/Other/cfg-printer-branch-weights-percent.ll =================================================================== --- /dev/null +++ llvm/test/Other/cfg-printer-branch-weights-percent.ll @@ -0,0 +1,19 @@ +;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} Index: llvm/test/Other/cfg-printer-branch-weights.ll =================================================================== --- llvm/test/Other/cfg-printer-branch-weights.ll +++ llvm/test/Other/cfg-printer-branch-weights.ll @@ -1,4 +1,4 @@ -;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) { @@ -6,11 +6,11 @@ %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 Index: llvm/test/Other/heat-colors-graphs.ll =================================================================== --- /dev/null +++ llvm/test/Other/heat-colors-graphs.ll @@ -0,0 +1,19 @@ +; 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}