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 33 namespace llvm { 34 class CFGViewerPass : public PassInfoMixin<CFGViewerPass> { 35 public: 36 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 37 }; 38 39 class CFGOnlyViewerPass : public PassInfoMixin<CFGOnlyViewerPass> { 40 public: 41 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 42 }; 43 44 class CFGPrinterPass : public PassInfoMixin<CFGPrinterPass> { 45 public: 46 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 47 }; 48 49 class CFGOnlyPrinterPass : public PassInfoMixin<CFGOnlyPrinterPass> { 50 public: 51 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 52 }; 53 54 class DOTFuncInfo { 55 private: 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 64 public: DOTFuncInfo(const Function * F)65 DOTFuncInfo(const Function *F) : DOTFuncInfo(F, nullptr, nullptr, 0) {} 66 DOTFuncInfo(const Function * F,const BlockFrequencyInfo * BFI,const BranchProbabilityInfo * BPI,uint64_t MaxFreq)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 getBFI()75 const BlockFrequencyInfo *getBFI() { return BFI; } 76 getBPI()77 const BranchProbabilityInfo *getBPI() { return BPI; } 78 getFunction()79 const Function *getFunction() { return this->F; } 80 getMaxFreq()81 uint64_t getMaxFreq() { return MaxFreq; } 82 getFreq(const BasicBlock * BB)83 uint64_t getFreq(const BasicBlock *BB) { 84 return BFI->getBlockFreq(BB).getFrequency(); 85 } 86 setHeatColors(bool ShowHeat)87 void setHeatColors(bool ShowHeat) { this->ShowHeat = ShowHeat; } 88 showHeatColors()89 bool showHeatColors() { return ShowHeat; } 90 setRawEdgeWeights(bool RawWeights)91 void setRawEdgeWeights(bool RawWeights) { this->RawWeights = RawWeights; } 92 useRawEdgeWeights()93 bool useRawEdgeWeights() { return RawWeights; } 94 setEdgeWeights(bool EdgeWeights)95 void setEdgeWeights(bool EdgeWeights) { this->EdgeWeights = EdgeWeights; } 96 showEdgeWeights()97 bool showEdgeWeights() { return EdgeWeights; } 98 }; 99 100 template <> 101 struct 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 122 template <> 123 struct 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); 299 void computeHiddenNodes(const Function *F); 300 }; 301 } // End llvm namespace 302 303 namespace llvm { 304 class FunctionPass; 305 FunctionPass *createCFGPrinterLegacyPassPass(); 306 FunctionPass *createCFGOnlyPrinterLegacyPassPass(); 307 } // End llvm namespace 308 309 #endif 310