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