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/DOTGraphTraits.h"
30 #include "llvm/Support/FormatVariadic.h"
31 
32 namespace llvm {
33 template <class GraphType> struct GraphTraits;
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:
65   DOTFuncInfo(const Function *F) : DOTFuncInfo(F, nullptr, nullptr, 0) {}
66 
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 
75   const BlockFrequencyInfo *getBFI() const { return BFI; }
76 
77   const BranchProbabilityInfo *getBPI() const { return BPI; }
78 
79   const Function *getFunction() const { return this->F; }
80 
81   uint64_t getMaxFreq() const { return MaxFreq; }
82 
83   uint64_t getFreq(const BasicBlock *BB) const {
84     return BFI->getBlockFreq(BB).getFrequency();
85   }
86 
87   void setHeatColors(bool ShowHeat) { this->ShowHeat = ShowHeat; }
88 
89   bool showHeatColors() { return ShowHeat; }
90 
91   void setRawEdgeWeights(bool RawWeights) { this->RawWeights = RawWeights; }
92 
93   bool useRawEdgeWeights() { return RawWeights; }
94 
95   void setEdgeWeights(bool EdgeWeights) { this->EdgeWeights = EdgeWeights; }
96 
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> isOnDeoptOrUnreachablePath;
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, const DOTFuncInfo *CFGInfo);
299   void computeDeoptOrUnreachablePaths(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