xref: /freebsd/contrib/llvm-project/llvm/include/llvm/Analysis/CFGPrinter.h (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583) 
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);
isRequired()38   static bool isRequired() { return true; }
39 };
40 
41 class CFGOnlyViewerPass : public PassInfoMixin<CFGOnlyViewerPass> {
42 public:
43   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
isRequired()44   static bool isRequired() { return true; }
45 };
46 
47 class CFGPrinterPass : public PassInfoMixin<CFGPrinterPass> {
48 public:
49   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
isRequired()50   static bool isRequired() { return true; }
51 };
52 
53 class CFGOnlyPrinterPass : public PassInfoMixin<CFGOnlyPrinterPass> {
54 public:
55   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
isRequired()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:
DOTFuncInfo(const Function * F)70   DOTFuncInfo(const Function *F) : DOTFuncInfo(F, nullptr, nullptr, 0) {}
71 
DOTFuncInfo(const Function * F,const BlockFrequencyInfo * BFI,const BranchProbabilityInfo * BPI,uint64_t MaxFreq)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 
getBFI()80   const BlockFrequencyInfo *getBFI() const { return BFI; }
81 
getBPI()82   const BranchProbabilityInfo *getBPI() const { return BPI; }
83 
getFunction()84   const Function *getFunction() const { return this->F; }
85 
getMaxFreq()86   uint64_t getMaxFreq() const { return MaxFreq; }
87 
getFreq(const BasicBlock * BB)88   uint64_t getFreq(const BasicBlock *BB) const {
89     return BFI->getBlockFreq(BB).getFrequency();
90   }
91 
setHeatColors(bool ShowHeat)92   void setHeatColors(bool ShowHeat) { this->ShowHeat = ShowHeat; }
93 
showHeatColors()94   bool showHeatColors() { return ShowHeat; }
95 
setRawEdgeWeights(bool RawWeights)96   void setRawEdgeWeights(bool RawWeights) { this->RawWeights = RawWeights; }
97 
useRawEdgeWeights()98   bool useRawEdgeWeights() { return RawWeights; }
99 
setEdgeWeights(bool EdgeWeights)100   void setEdgeWeights(bool EdgeWeights) { this->EdgeWeights = EdgeWeights; }
101 
showEdgeWeights()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 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 OutStr;
149   raw_string_ostream OS(OutStr);
150   HandleBasicBlock(OS, *Node);
151   // Remove "%" from BB name
152   if (OutStr[0] == '%') {
153     OutStr.erase(OutStr.begin());
154   }
155   // Place | after BB name to separate it into header
156   OutStr.insert(OutStr.find_first_of('\n') + 1, "\\|");
157 
158   unsigned ColNum = 0;
159   unsigned LastSpace = 0;
160   for (unsigned i = 0; i != OutStr.length(); ++i) {
161     if (OutStr[i] == '\n') { // Left justify
162       OutStr[i] = '\\';
163       OutStr.insert(OutStr.begin() + i + 1, 'l');
164       ColNum = 0;
165       LastSpace = 0;
166     } else if (OutStr[i] == ';') {             // Delete comments!
167       unsigned Idx = OutStr.find('\n', i + 1); // Find end of line
168       HandleComment(OutStr, i, Idx);
169     } else if (ColNum == MaxColumns) { // Wrap lines.
170       // Wrap very long names even though we can't find a space.
171       if (!LastSpace)
172         LastSpace = i;
173       OutStr.insert(LastSpace, "\\l...");
174       ColNum = i - LastSpace;
175       LastSpace = 0;
176       i += 3; // The loop will advance 'i' again.
177     } else
178       ++ColNum;
179     if (OutStr[i] == ' ')
180       LastSpace = i;
181   }
182   return OutStr;
183 }
184 
185 template <>
186 struct DOTGraphTraits<DOTFuncInfo *> : public DefaultDOTGraphTraits {
187 
188   // Cache for is hidden property
189   DenseMap<const BasicBlock *, bool> isOnDeoptOrUnreachablePath;
190 
191   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
192 
193   static void eraseComment(std::string &OutStr, unsigned &I, unsigned Idx) {
194     OutStr.erase(OutStr.begin() + I, OutStr.begin() + Idx);
195     --I;
196   }
197 
198   static std::string getGraphName(DOTFuncInfo *CFGInfo) {
199     return "CFG for '" + CFGInfo->getFunction()->getName().str() + "' function";
200   }
201 
202   static std::string getSimpleNodeLabel(const BasicBlock *Node, DOTFuncInfo *) {
203     return SimpleNodeLabelString(Node);
204   }
205 
206   static void printBasicBlock(raw_string_ostream &OS, const BasicBlock &Node) {
207     // Prepend label name
208     Node.printAsOperand(OS, false);
209     OS << ":\n";
210     for (const Instruction &Inst : Node)
211       OS << Inst << "\n";
212   }
213 
214   static std::string getCompleteNodeLabel(
215       const BasicBlock *Node, DOTFuncInfo *,
216       function_ref<void(raw_string_ostream &, const BasicBlock &)>
217           HandleBasicBlock = printBasicBlock,
218       function_ref<void(std::string &, unsigned &, unsigned)>
219           HandleComment = eraseComment) {
220     return CompleteNodeLabelString(Node, HandleBasicBlock, HandleComment);
221   }
222 
223   std::string getNodeLabel(const BasicBlock *Node, DOTFuncInfo *CFGInfo) {
224 
225     if (isSimple())
226       return getSimpleNodeLabel(Node, CFGInfo);
227     else
228       return getCompleteNodeLabel(Node, CFGInfo);
229   }
230 
231   static std::string getEdgeSourceLabel(const BasicBlock *Node,
232                                         const_succ_iterator I) {
233     // Label source of conditional branches with "T" or "F"
234     if (const BranchInst *BI = dyn_cast<BranchInst>(Node->getTerminator()))
235       if (BI->isConditional())
236         return (I == succ_begin(Node)) ? "T" : "F";
237 
238     // Label source of switch edges with the associated value.
239     if (const SwitchInst *SI = dyn_cast<SwitchInst>(Node->getTerminator())) {
240       unsigned SuccNo = I.getSuccessorIndex();
241 
242       if (SuccNo == 0)
243         return "def";
244 
245       std::string Str;
246       raw_string_ostream OS(Str);
247       auto Case = *SwitchInst::ConstCaseIt::fromSuccessorIndex(SI, SuccNo);
248       OS << Case.getCaseValue()->getValue();
249       return Str;
250     }
251     return "";
252   }
253 
254   static std::string getBBName(const BasicBlock *Node) {
255     std::string NodeName = Node->getName().str();
256     if (NodeName.empty()) {
257       raw_string_ostream NodeOS(NodeName);
258       Node->printAsOperand(NodeOS, false);
259       // Removing %
260       NodeName.erase(NodeName.begin());
261     }
262     return NodeName;
263   }
264 
265   /// Display the raw branch weights from PGO.
266   std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I,
267                                 DOTFuncInfo *CFGInfo) {
268     unsigned OpNo = I.getSuccessorIndex();
269     const Instruction *TI = Node->getTerminator();
270     BasicBlock *SuccBB = TI->getSuccessor(OpNo);
271     auto BranchProb = CFGInfo->getBPI()->getEdgeProbability(Node, SuccBB);
272     double WeightPercent = ((double)BranchProb.getNumerator()) /
273                            ((double)BranchProb.getDenominator());
274 
275     std::string TTAttr =
276         formatv("tooltip=\"{0} -> {1}\\nProbability {2:P}\" ", getBBName(Node),
277                 getBBName(SuccBB), WeightPercent);
278     if (!CFGInfo->showEdgeWeights())
279       return TTAttr;
280 
281     if (TI->getNumSuccessors() == 1)
282       return TTAttr + "penwidth=2";
283 
284     if (OpNo >= TI->getNumSuccessors())
285       return TTAttr;
286 
287     double Width = 1 + WeightPercent;
288 
289     if (!CFGInfo->useRawEdgeWeights())
290       return TTAttr +
291              formatv("label=\"{0:P}\" penwidth={1}", WeightPercent, Width)
292                  .str();
293 
294     // Prepend a 'W' to indicate that this is a weight rather than the actual
295     // profile count (due to scaling).
296 
297     uint64_t Freq = CFGInfo->getFreq(Node);
298     std::string Attrs =
299         TTAttr + formatv("label=\"W:{0}\" penwidth={1}",
300                          (uint64_t)(Freq * WeightPercent), Width)
301                      .str();
302     if (Attrs.size())
303       return Attrs;
304 
305     MDNode *WeightsNode = getBranchWeightMDNode(*TI);
306     if (!WeightsNode)
307       return TTAttr;
308 
309     OpNo = I.getSuccessorIndex() + 1;
310     if (OpNo >= WeightsNode->getNumOperands())
311       return TTAttr;
312     ConstantInt *Weight =
313         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(OpNo));
314     if (!Weight)
315       return TTAttr;
316     return (TTAttr + "label=\"W:" + std::to_string(Weight->getZExtValue()) +
317             "\" penwidth=" + std::to_string(Width));
318   }
319 
320   std::string getNodeAttributes(const BasicBlock *Node, DOTFuncInfo *CFGInfo) {
321 
322     if (!CFGInfo->showHeatColors())
323       return "";
324 
325     uint64_t Freq = CFGInfo->getFreq(Node);
326     std::string Color = getHeatColor(Freq, CFGInfo->getMaxFreq());
327     std::string EdgeColor = (Freq <= (CFGInfo->getMaxFreq() / 2))
328                                 ? (getHeatColor(0))
329                                 : (getHeatColor(1));
330 
331     std::string Attrs = "color=\"" + EdgeColor + "ff\", style=filled," +
332                         " fillcolor=\"" + Color + "70\"" +
333                         " fontname=\"Courier\"";
334     return Attrs;
335   }
336   bool isNodeHidden(const BasicBlock *Node, const DOTFuncInfo *CFGInfo);
337   void computeDeoptOrUnreachablePaths(const Function *F);
338 };
339 } // End llvm namespace
340 
341 #endif
342