1//===-- CFGPrinter.h - CFG printer external interface -----------*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This file defines a 'dot-cfg' analysis pass, which emits the 10// cfg.<fnname>.dot file for each function in the program, with a graph of the 11// CFG for that function. 12// 13// This file defines external functions that can be called to explicitly 14// instantiate the CFG printer. 15// 16//===----------------------------------------------------------------------===// 17 18#ifndef LLVM_ANALYSIS_CFGPRINTER_H 19#define LLVM_ANALYSIS_CFGPRINTER_H 20 21#include "llvm/ADT/STLExtras.h" 22#include "llvm/Analysis/BlockFrequencyInfo.h" 23#include "llvm/Analysis/BranchProbabilityInfo.h" 24#include "llvm/Analysis/HeatUtils.h" 25#include "llvm/IR/CFG.h" 26#include "llvm/IR/Constants.h" 27#include "llvm/IR/Function.h" 28#include "llvm/IR/Instructions.h" 29#include "llvm/IR/PassManager.h" 30#include "llvm/Support/FormatVariadic.h" 31#include "llvm/Support/GraphWriter.h" 32 33namespace llvm { 34class CFGViewerPass : public PassInfoMixin<CFGViewerPass> { 35public: 36 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 37}; 38 39class CFGOnlyViewerPass : public PassInfoMixin<CFGOnlyViewerPass> { 40public: 41 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 42}; 43 44class CFGPrinterPass : public PassInfoMixin<CFGPrinterPass> { 45public: 46 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 47}; 48 49class CFGOnlyPrinterPass : public PassInfoMixin<CFGOnlyPrinterPass> { 50public: 51 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 52}; 53 54class DOTFuncInfo { 55private: 56 const Function *F; 57 const BlockFrequencyInfo *BFI; 58 const BranchProbabilityInfo *BPI; 59 uint64_t MaxFreq; 60 bool ShowHeat; 61 bool EdgeWeights; 62 bool RawWeights; 63 64public: 65 DOTFuncInfo(const Function *F) : DOTFuncInfo(F, nullptr, nullptr, 0) {} 66 67 DOTFuncInfo(const Function *F, const BlockFrequencyInfo *BFI, 68 const BranchProbabilityInfo *BPI, uint64_t MaxFreq) 69 : F(F), BFI(BFI), BPI(BPI), MaxFreq(MaxFreq) { 70 ShowHeat = false; 71 EdgeWeights = !!BPI; // Print EdgeWeights when BPI is available. 72 RawWeights = !!BFI; // Print RawWeights when BFI is available. 73 } 74 75 const BlockFrequencyInfo *getBFI() { return BFI; } 76 77 const BranchProbabilityInfo *getBPI() { return BPI; } 78 79 const Function *getFunction() { return this->F; } 80 81 uint64_t getMaxFreq() { return MaxFreq; } 82 83 uint64_t getFreq(const BasicBlock *BB) { 84 return BFI->getBlockFreq(BB).getFrequency(); 85 } 86 87 void setHeatColors(bool ShowHeat) { this->ShowHeat = ShowHeat; } 88 89 bool showHeatColors() { return ShowHeat; } 90 91 void setRawEdgeWeights(bool RawWeights) { this->RawWeights = RawWeights; } 92 93 bool useRawEdgeWeights() { return RawWeights; } 94 95 void setEdgeWeights(bool EdgeWeights) { this->EdgeWeights = EdgeWeights; } 96 97 bool showEdgeWeights() { return EdgeWeights; } 98}; 99 100template <> 101struct GraphTraits<DOTFuncInfo *> : public GraphTraits<const BasicBlock *> { 102 static NodeRef getEntryNode(DOTFuncInfo *CFGInfo) { 103 return &(CFGInfo->getFunction()->getEntryBlock()); 104 } 105 106 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 107 using nodes_iterator = pointer_iterator<Function::const_iterator>; 108 109 static nodes_iterator nodes_begin(DOTFuncInfo *CFGInfo) { 110 return nodes_iterator(CFGInfo->getFunction()->begin()); 111 } 112 113 static nodes_iterator nodes_end(DOTFuncInfo *CFGInfo) { 114 return nodes_iterator(CFGInfo->getFunction()->end()); 115 } 116 117 static size_t size(DOTFuncInfo *CFGInfo) { 118 return CFGInfo->getFunction()->size(); 119 } 120}; 121 122template <> 123struct DOTGraphTraits<DOTFuncInfo *> : public DefaultDOTGraphTraits { 124 125 // Cache for is hidden property 126 llvm::DenseMap<const BasicBlock *, bool> isHiddenBasicBlock; 127 128 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} 129 130 static std::string getGraphName(DOTFuncInfo *CFGInfo) { 131 return "CFG for '" + CFGInfo->getFunction()->getName().str() + "' function"; 132 } 133 134 static std::string getSimpleNodeLabel(const BasicBlock *Node, DOTFuncInfo *) { 135 if (!Node->getName().empty()) 136 return Node->getName().str(); 137 138 std::string Str; 139 raw_string_ostream OS(Str); 140 141 Node->printAsOperand(OS, false); 142 return OS.str(); 143 } 144 145 static void eraseComment(std::string &OutStr, unsigned &I, unsigned Idx) { 146 OutStr.erase(OutStr.begin() + I, OutStr.begin() + Idx); 147 --I; 148 } 149 150 static std::string getCompleteNodeLabel( 151 const BasicBlock *Node, DOTFuncInfo *, 152 llvm::function_ref<void(raw_string_ostream &, const BasicBlock &)> 153 HandleBasicBlock = [](raw_string_ostream &OS, 154 const BasicBlock &Node) -> void { OS << Node; }, 155 llvm::function_ref<void(std::string &, unsigned &, unsigned)> 156 HandleComment = eraseComment) { 157 enum { MaxColumns = 80 }; 158 std::string Str; 159 raw_string_ostream OS(Str); 160 161 if (Node->getName().empty()) { 162 Node->printAsOperand(OS, false); 163 OS << ":"; 164 } 165 166 HandleBasicBlock(OS, *Node); 167 std::string OutStr = OS.str(); 168 if (OutStr[0] == '\n') 169 OutStr.erase(OutStr.begin()); 170 171 // Process string output to make it nicer... 172 unsigned ColNum = 0; 173 unsigned LastSpace = 0; 174 for (unsigned i = 0; i != OutStr.length(); ++i) { 175 if (OutStr[i] == '\n') { // Left justify 176 OutStr[i] = '\\'; 177 OutStr.insert(OutStr.begin() + i + 1, 'l'); 178 ColNum = 0; 179 LastSpace = 0; 180 } else if (OutStr[i] == ';') { // Delete comments! 181 unsigned Idx = OutStr.find('\n', i + 1); // Find end of line 182 HandleComment(OutStr, i, Idx); 183 } else if (ColNum == MaxColumns) { // Wrap lines. 184 // Wrap very long names even though we can't find a space. 185 if (!LastSpace) 186 LastSpace = i; 187 OutStr.insert(LastSpace, "\\l..."); 188 ColNum = i - LastSpace; 189 LastSpace = 0; 190 i += 3; // The loop will advance 'i' again. 191 } else 192 ++ColNum; 193 if (OutStr[i] == ' ') 194 LastSpace = i; 195 } 196 return OutStr; 197 } 198 199 std::string getNodeLabel(const BasicBlock *Node, DOTFuncInfo *CFGInfo) { 200 201 if (isSimple()) 202 return getSimpleNodeLabel(Node, CFGInfo); 203 else 204 return getCompleteNodeLabel(Node, CFGInfo); 205 } 206 207 static std::string getEdgeSourceLabel(const BasicBlock *Node, 208 const_succ_iterator I) { 209 // Label source of conditional branches with "T" or "F" 210 if (const BranchInst *BI = dyn_cast<BranchInst>(Node->getTerminator())) 211 if (BI->isConditional()) 212 return (I == succ_begin(Node)) ? "T" : "F"; 213 214 // Label source of switch edges with the associated value. 215 if (const SwitchInst *SI = dyn_cast<SwitchInst>(Node->getTerminator())) { 216 unsigned SuccNo = I.getSuccessorIndex(); 217 218 if (SuccNo == 0) 219 return "def"; 220 221 std::string Str; 222 raw_string_ostream OS(Str); 223 auto Case = *SwitchInst::ConstCaseIt::fromSuccessorIndex(SI, SuccNo); 224 OS << Case.getCaseValue()->getValue(); 225 return OS.str(); 226 } 227 return ""; 228 } 229 230 /// Display the raw branch weights from PGO. 231 std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I, 232 DOTFuncInfo *CFGInfo) { 233 if (!CFGInfo->showEdgeWeights()) 234 return ""; 235 236 const Instruction *TI = Node->getTerminator(); 237 if (TI->getNumSuccessors() == 1) 238 return "penwidth=2"; 239 240 unsigned OpNo = I.getSuccessorIndex(); 241 242 if (OpNo >= TI->getNumSuccessors()) 243 return ""; 244 245 BasicBlock *SuccBB = TI->getSuccessor(OpNo); 246 auto BranchProb = CFGInfo->getBPI()->getEdgeProbability(Node, SuccBB); 247 double WeightPercent = ((double)BranchProb.getNumerator()) / 248 ((double)BranchProb.getDenominator()); 249 double Width = 1 + WeightPercent; 250 251 if (!CFGInfo->useRawEdgeWeights()) 252 return formatv("label=\"{0:P}\" penwidth={1}", WeightPercent, Width) 253 .str(); 254 255 // Prepend a 'W' to indicate that this is a weight rather than the actual 256 // profile count (due to scaling). 257 258 uint64_t Freq = CFGInfo->getFreq(Node); 259 std::string Attrs = formatv("label=\"W:{0}\" penwidth={1}", 260 (uint64_t)(Freq * WeightPercent), Width); 261 if (Attrs.size()) 262 return Attrs; 263 264 MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof); 265 if (!WeightsNode) 266 return ""; 267 268 MDString *MDName = cast<MDString>(WeightsNode->getOperand(0)); 269 if (MDName->getString() != "branch_weights") 270 return ""; 271 272 OpNo = I.getSuccessorIndex() + 1; 273 if (OpNo >= WeightsNode->getNumOperands()) 274 return ""; 275 ConstantInt *Weight = 276 mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(OpNo)); 277 if (!Weight) 278 return ""; 279 return ("label=\"W:" + std::to_string(Weight->getZExtValue()) + 280 "\" penwidth=" + std::to_string(Width)); 281 } 282 283 std::string getNodeAttributes(const BasicBlock *Node, DOTFuncInfo *CFGInfo) { 284 285 if (!CFGInfo->showHeatColors()) 286 return ""; 287 288 uint64_t Freq = CFGInfo->getFreq(Node); 289 std::string Color = getHeatColor(Freq, CFGInfo->getMaxFreq()); 290 std::string EdgeColor = (Freq <= (CFGInfo->getMaxFreq() / 2)) 291 ? (getHeatColor(0)) 292 : (getHeatColor(1)); 293 294 std::string Attrs = "color=\"" + EdgeColor + "ff\", style=filled," + 295 " fillcolor=\"" + Color + "70\""; 296 return Attrs; 297 } 298 bool isNodeHidden(const BasicBlock *Node, const DOTFuncInfo *CFGInfo); 299 void computeHiddenNodes(const Function *F); 300}; 301} // End llvm namespace 302 303namespace llvm { 304class FunctionPass; 305FunctionPass *createCFGPrinterLegacyPassPass(); 306FunctionPass *createCFGOnlyPrinterLegacyPassPass(); 307} // End llvm namespace 308 309#endif 310