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 151 if (Node->getName().empty()) { 152 Node->printAsOperand(OS, false); 153 OS << ':'; 154 } 155 156 HandleBasicBlock(OS, *Node); 157 std::string OutStr = OS.str(); 158 if (OutStr[0] == '\n') 159 OutStr.erase(OutStr.begin()); 160 161 unsigned ColNum = 0; 162 unsigned LastSpace = 0; 163 for (unsigned i = 0; i != OutStr.length(); ++i) { 164 if (OutStr[i] == '\n') { // Left justify 165 OutStr[i] = '\\'; 166 OutStr.insert(OutStr.begin() + i + 1, 'l'); 167 ColNum = 0; 168 LastSpace = 0; 169 } else if (OutStr[i] == ';') { // Delete comments! 170 unsigned Idx = OutStr.find('\n', i + 1); // Find end of line 171 HandleComment(OutStr, i, Idx); 172 } else if (ColNum == MaxColumns) { // Wrap lines. 173 // Wrap very long names even though we can't find a space. 174 if (!LastSpace) 175 LastSpace = i; 176 OutStr.insert(LastSpace, "\\l..."); 177 ColNum = i - LastSpace; 178 LastSpace = 0; 179 i += 3; // The loop will advance 'i' again. 180 } else 181 ++ColNum; 182 if (OutStr[i] == ' ') 183 LastSpace = i; 184 } 185 return OutStr; 186 } 187 188 template <> 189 struct DOTGraphTraits<DOTFuncInfo *> : public DefaultDOTGraphTraits { 190 191 // Cache for is hidden property 192 DenseMap<const BasicBlock *, bool> isOnDeoptOrUnreachablePath; 193 194 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} 195 196 static void eraseComment(std::string &OutStr, unsigned &I, unsigned Idx) { 197 OutStr.erase(OutStr.begin() + I, OutStr.begin() + Idx); 198 --I; 199 } 200 201 static std::string getGraphName(DOTFuncInfo *CFGInfo) { 202 return "CFG for '" + CFGInfo->getFunction()->getName().str() + "' function"; 203 } 204 205 static std::string getSimpleNodeLabel(const BasicBlock *Node, DOTFuncInfo *) { 206 return SimpleNodeLabelString(Node); 207 } 208 209 static std::string getCompleteNodeLabel( 210 const BasicBlock *Node, DOTFuncInfo *, 211 function_ref<void(raw_string_ostream &, const BasicBlock &)> 212 HandleBasicBlock = [](raw_string_ostream &OS, 213 const BasicBlock &Node) -> void { OS << Node; }, 214 function_ref<void(std::string &, unsigned &, unsigned)> 215 HandleComment = eraseComment) { 216 return CompleteNodeLabelString(Node, HandleBasicBlock, HandleComment); 217 } 218 219 std::string getNodeLabel(const BasicBlock *Node, DOTFuncInfo *CFGInfo) { 220 221 if (isSimple()) 222 return getSimpleNodeLabel(Node, CFGInfo); 223 else 224 return getCompleteNodeLabel(Node, CFGInfo); 225 } 226 227 static std::string getEdgeSourceLabel(const BasicBlock *Node, 228 const_succ_iterator I) { 229 // Label source of conditional branches with "T" or "F" 230 if (const BranchInst *BI = dyn_cast<BranchInst>(Node->getTerminator())) 231 if (BI->isConditional()) 232 return (I == succ_begin(Node)) ? "T" : "F"; 233 234 // Label source of switch edges with the associated value. 235 if (const SwitchInst *SI = dyn_cast<SwitchInst>(Node->getTerminator())) { 236 unsigned SuccNo = I.getSuccessorIndex(); 237 238 if (SuccNo == 0) 239 return "def"; 240 241 std::string Str; 242 raw_string_ostream OS(Str); 243 auto Case = *SwitchInst::ConstCaseIt::fromSuccessorIndex(SI, SuccNo); 244 OS << Case.getCaseValue()->getValue(); 245 return OS.str(); 246 } 247 return ""; 248 } 249 250 /// Display the raw branch weights from PGO. 251 std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I, 252 DOTFuncInfo *CFGInfo) { 253 if (!CFGInfo->showEdgeWeights()) 254 return ""; 255 256 const Instruction *TI = Node->getTerminator(); 257 if (TI->getNumSuccessors() == 1) 258 return "penwidth=2"; 259 260 unsigned OpNo = I.getSuccessorIndex(); 261 262 if (OpNo >= TI->getNumSuccessors()) 263 return ""; 264 265 BasicBlock *SuccBB = TI->getSuccessor(OpNo); 266 auto BranchProb = CFGInfo->getBPI()->getEdgeProbability(Node, SuccBB); 267 double WeightPercent = ((double)BranchProb.getNumerator()) / 268 ((double)BranchProb.getDenominator()); 269 double Width = 1 + WeightPercent; 270 271 if (!CFGInfo->useRawEdgeWeights()) 272 return formatv("label=\"{0:P}\" penwidth={1}", WeightPercent, Width) 273 .str(); 274 275 // Prepend a 'W' to indicate that this is a weight rather than the actual 276 // profile count (due to scaling). 277 278 uint64_t Freq = CFGInfo->getFreq(Node); 279 std::string Attrs = formatv("label=\"W:{0}\" penwidth={1}", 280 (uint64_t)(Freq * WeightPercent), Width); 281 if (Attrs.size()) 282 return Attrs; 283 284 MDNode *WeightsNode = getBranchWeightMDNode(*TI); 285 if (!WeightsNode) 286 return ""; 287 288 OpNo = I.getSuccessorIndex() + 1; 289 if (OpNo >= WeightsNode->getNumOperands()) 290 return ""; 291 ConstantInt *Weight = 292 mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(OpNo)); 293 if (!Weight) 294 return ""; 295 return ("label=\"W:" + std::to_string(Weight->getZExtValue()) + 296 "\" penwidth=" + std::to_string(Width)); 297 } 298 299 std::string getNodeAttributes(const BasicBlock *Node, DOTFuncInfo *CFGInfo) { 300 301 if (!CFGInfo->showHeatColors()) 302 return ""; 303 304 uint64_t Freq = CFGInfo->getFreq(Node); 305 std::string Color = getHeatColor(Freq, CFGInfo->getMaxFreq()); 306 std::string EdgeColor = (Freq <= (CFGInfo->getMaxFreq() / 2)) 307 ? (getHeatColor(0)) 308 : (getHeatColor(1)); 309 310 std::string Attrs = "color=\"" + EdgeColor + "ff\", style=filled," + 311 " fillcolor=\"" + Color + "70\""; 312 return Attrs; 313 } 314 bool isNodeHidden(const BasicBlock *Node, const DOTFuncInfo *CFGInfo); 315 void computeDeoptOrUnreachablePaths(const Function *F); 316 }; 317 } // End llvm namespace 318 319 namespace llvm { 320 class FunctionPass; 321 FunctionPass *createCFGPrinterLegacyPassPass(); 322 FunctionPass *createCFGOnlyPrinterLegacyPassPass(); 323 } // End llvm namespace 324 325 #endif 326