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