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