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