xref: /freebsd/contrib/llvm-project/llvm/include/llvm/Analysis/CFGPrinter.h (revision 700637cbb5e582861067a11aaca4d053546871d2) 
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/Compiler.h"
31 #include "llvm/Support/DOTGraphTraits.h"
32 #include "llvm/Support/FormatVariadic.h"
33 
34 namespace llvm {
35 class ModuleSlotTracker;
36 
37 template <class GraphType> struct GraphTraits;
38 class CFGViewerPass : public PassInfoMixin<CFGViewerPass> {
39 public:
40   LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
isRequired()41   static bool isRequired() { return true; }
42 };
43 
44 class CFGOnlyViewerPass : public PassInfoMixin<CFGOnlyViewerPass> {
45 public:
46   LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
isRequired()47   static bool isRequired() { return true; }
48 };
49 
50 class CFGPrinterPass : public PassInfoMixin<CFGPrinterPass> {
51 public:
52   LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
isRequired()53   static bool isRequired() { return true; }
54 };
55 
56 class CFGOnlyPrinterPass : public PassInfoMixin<CFGOnlyPrinterPass> {
57 public:
58   LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
isRequired()59   static bool isRequired() { return true; }
60 };
61 
62 class DOTFuncInfo {
63 private:
64   const Function *F;
65   const BlockFrequencyInfo *BFI;
66   const BranchProbabilityInfo *BPI;
67   std::unique_ptr<ModuleSlotTracker> MSTStorage;
68   uint64_t MaxFreq;
69   bool ShowHeat;
70   bool EdgeWeights;
71   bool RawWeights;
72 
73 public:
DOTFuncInfo(const Function * F)74   DOTFuncInfo(const Function *F) : DOTFuncInfo(F, nullptr, nullptr, 0) {}
75   LLVM_ABI ~DOTFuncInfo();
76 
77   LLVM_ABI DOTFuncInfo(const Function *F, const BlockFrequencyInfo *BFI,
78                        const BranchProbabilityInfo *BPI, uint64_t MaxFreq);
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 
86   LLVM_ABI ModuleSlotTracker *getModuleSlotTracker();
87 
getMaxFreq()88   uint64_t getMaxFreq() const { return MaxFreq; }
89 
getFreq(const BasicBlock * BB)90   uint64_t getFreq(const BasicBlock *BB) const {
91     return BFI->getBlockFreq(BB).getFrequency();
92   }
93 
setHeatColors(bool ShowHeat)94   void setHeatColors(bool ShowHeat) { this->ShowHeat = ShowHeat; }
95 
showHeatColors()96   bool showHeatColors() { return ShowHeat; }
97 
setRawEdgeWeights(bool RawWeights)98   void setRawEdgeWeights(bool RawWeights) { this->RawWeights = RawWeights; }
99 
useRawEdgeWeights()100   bool useRawEdgeWeights() { return RawWeights; }
101 
setEdgeWeights(bool EdgeWeights)102   void setEdgeWeights(bool EdgeWeights) { this->EdgeWeights = EdgeWeights; }
103 
showEdgeWeights()104   bool showEdgeWeights() { return EdgeWeights; }
105 };
106 
107 template <>
108 struct GraphTraits<DOTFuncInfo *> : public GraphTraits<const BasicBlock *> {
109   static NodeRef getEntryNode(DOTFuncInfo *CFGInfo) {
110     return &(CFGInfo->getFunction()->getEntryBlock());
111   }
112 
113   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
114   using nodes_iterator = pointer_iterator<Function::const_iterator>;
115 
116   static nodes_iterator nodes_begin(DOTFuncInfo *CFGInfo) {
117     return nodes_iterator(CFGInfo->getFunction()->begin());
118   }
119 
120   static nodes_iterator nodes_end(DOTFuncInfo *CFGInfo) {
121     return nodes_iterator(CFGInfo->getFunction()->end());
122   }
123 
124   static size_t size(DOTFuncInfo *CFGInfo) {
125     return CFGInfo->getFunction()->size();
126   }
127 };
128 
129 template <typename BasicBlockT>
130 std::string SimpleNodeLabelString(const BasicBlockT *Node) {
131   if (!Node->getName().empty())
132     return Node->getName().str();
133 
134   std::string Str;
135   raw_string_ostream OS(Str);
136 
137   Node->printAsOperand(OS, false);
138   return Str;
139 }
140 
141 template <typename BasicBlockT>
142 std::string CompleteNodeLabelString(
143     const BasicBlockT *Node,
144     function_ref<void(raw_string_ostream &, const BasicBlockT &)>
145         HandleBasicBlock,
146     function_ref<void(std::string &, unsigned &, unsigned)>
147         HandleComment) {
148 
149   enum { MaxColumns = 80 };
150   std::string OutStr;
151   raw_string_ostream OS(OutStr);
152   HandleBasicBlock(OS, *Node);
153   // Remove "%" from BB name
154   if (OutStr[0] == '%') {
155     OutStr.erase(OutStr.begin());
156   }
157   // Place | after BB name to separate it into header
158   OutStr.insert(OutStr.find_first_of('\n') + 1, "\\|");
159 
160   unsigned ColNum = 0;
161   unsigned LastSpace = 0;
162   for (unsigned i = 0; i != OutStr.length(); ++i) {
163     if (OutStr[i] == '\n') { // Left justify
164       OutStr[i] = '\\';
165       OutStr.insert(OutStr.begin() + i + 1, 'l');
166       ColNum = 0;
167       LastSpace = 0;
168     } else if (OutStr[i] == ';') {             // Delete comments!
169       unsigned Idx = OutStr.find('\n', i + 1); // Find end of line
170       HandleComment(OutStr, i, Idx);
171     } else if (ColNum == MaxColumns) { // Wrap lines.
172       // Wrap very long names even though we can't find a space.
173       if (!LastSpace)
174         LastSpace = i;
175       OutStr.insert(LastSpace, "\\l...");
176       ColNum = i - LastSpace;
177       LastSpace = 0;
178       i += 3; // The loop will advance 'i' again.
179     } else
180       ++ColNum;
181     if (OutStr[i] == ' ')
182       LastSpace = i;
183   }
184   return OutStr;
185 }
186 
187 template <>
188 struct DOTGraphTraits<DOTFuncInfo *> : public DefaultDOTGraphTraits {
189 
190   // Cache for is hidden property
191   DenseMap<const BasicBlock *, bool> isOnDeoptOrUnreachablePath;
192 
193   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
194 
195   static void eraseComment(std::string &OutStr, unsigned &I, unsigned Idx) {
196     OutStr.erase(OutStr.begin() + I, OutStr.begin() + Idx);
197     --I;
198   }
199 
200   static std::string getGraphName(DOTFuncInfo *CFGInfo) {
201     return "CFG for '" + CFGInfo->getFunction()->getName().str() + "' function";
202   }
203 
204   static std::string getSimpleNodeLabel(const BasicBlock *Node, DOTFuncInfo *) {
205     return SimpleNodeLabelString(Node);
206   }
207 
208   LLVM_ABI static std::string getCompleteNodeLabel(
209       const BasicBlock *Node, DOTFuncInfo *,
210       function_ref<void(raw_string_ostream &, const BasicBlock &)>
211           HandleBasicBlock = {},
212       function_ref<void(std::string &, unsigned &, unsigned)> HandleComment =
213           eraseComment);
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 Str;
242     }
243     return "";
244   }
245 
246   static std::string getBBName(const BasicBlock *Node) {
247     std::string NodeName = Node->getName().str();
248     if (NodeName.empty()) {
249       raw_string_ostream NodeOS(NodeName);
250       Node->printAsOperand(NodeOS, false);
251       // Removing %
252       NodeName.erase(NodeName.begin());
253     }
254     return NodeName;
255   }
256 
257   /// Display the raw branch weights from PGO.
258   std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I,
259                                 DOTFuncInfo *CFGInfo) {
260     // If BPI is not provided do not display any edge attributes
261     if (!CFGInfo->showEdgeWeights())
262       return "";
263 
264     unsigned OpNo = I.getSuccessorIndex();
265     const Instruction *TI = Node->getTerminator();
266     BasicBlock *SuccBB = TI->getSuccessor(OpNo);
267     auto BranchProb = CFGInfo->getBPI()->getEdgeProbability(Node, SuccBB);
268     double WeightPercent = ((double)BranchProb.getNumerator()) /
269                            ((double)BranchProb.getDenominator());
270     std::string TTAttr =
271         formatv("tooltip=\"{0} -> {1}\\nProbability {2:P}\" ", getBBName(Node),
272                 getBBName(SuccBB), WeightPercent);
273 
274     if (TI->getNumSuccessors() == 1)
275       return TTAttr + "penwidth=2";
276 
277     if (OpNo >= TI->getNumSuccessors())
278       return TTAttr;
279 
280     double Width = 1 + WeightPercent;
281 
282     if (!CFGInfo->useRawEdgeWeights())
283       return TTAttr +
284              formatv("label=\"{0:P}\" penwidth={1}", WeightPercent, Width)
285                  .str();
286 
287     // Prepend a 'W' to indicate that this is a weight rather than the actual
288     // profile count (due to scaling).
289 
290     uint64_t Freq = CFGInfo->getFreq(Node);
291     std::string Attrs =
292         TTAttr + formatv("label=\"W:{0}\" penwidth={1}",
293                          (uint64_t)(Freq * WeightPercent), Width)
294                      .str();
295     if (Attrs.size())
296       return Attrs;
297 
298     MDNode *WeightsNode = getBranchWeightMDNode(*TI);
299     if (!WeightsNode)
300       return TTAttr;
301 
302     OpNo = I.getSuccessorIndex() + 1;
303     if (OpNo >= WeightsNode->getNumOperands())
304       return TTAttr;
305     ConstantInt *Weight =
306         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(OpNo));
307     if (!Weight)
308       return TTAttr;
309     return (TTAttr + "label=\"W:" + std::to_string(Weight->getZExtValue()) +
310             "\" penwidth=" + std::to_string(Width));
311   }
312 
313   std::string getNodeAttributes(const BasicBlock *Node, DOTFuncInfo *CFGInfo) {
314 
315     if (!CFGInfo->showHeatColors())
316       return "";
317 
318     uint64_t Freq = CFGInfo->getFreq(Node);
319     std::string Color = getHeatColor(Freq, CFGInfo->getMaxFreq());
320     std::string EdgeColor = (Freq <= (CFGInfo->getMaxFreq() / 2))
321                                 ? (getHeatColor(0))
322                                 : (getHeatColor(1));
323 
324     std::string Attrs = "color=\"" + EdgeColor + "ff\", style=filled," +
325                         " fillcolor=\"" + Color + "70\"" +
326                         " fontname=\"Courier\"";
327     return Attrs;
328   }
329   LLVM_ABI bool isNodeHidden(const BasicBlock *Node,
330                              const DOTFuncInfo *CFGInfo);
331   LLVM_ABI void computeDeoptOrUnreachablePaths(const Function *F);
332 };
333 } // namespace llvm
334 
335 #endif
336