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