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