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/ADT/STLExtras.h"
22#include "llvm/Analysis/BlockFrequencyInfo.h"
23#include "llvm/Analysis/BranchProbabilityInfo.h"
24#include "llvm/Analysis/HeatUtils.h"
25#include "llvm/IR/CFG.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/Function.h"
28#include "llvm/IR/Instructions.h"
29#include "llvm/IR/PassManager.h"
30#include "llvm/Support/FormatVariadic.h"
31#include "llvm/Support/GraphWriter.h"
32
33namespace llvm {
34class CFGViewerPass : public PassInfoMixin<CFGViewerPass> {
35public:
36  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
37};
38
39class CFGOnlyViewerPass : public PassInfoMixin<CFGOnlyViewerPass> {
40public:
41  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
42};
43
44class CFGPrinterPass : public PassInfoMixin<CFGPrinterPass> {
45public:
46  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
47};
48
49class CFGOnlyPrinterPass : public PassInfoMixin<CFGOnlyPrinterPass> {
50public:
51  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
52};
53
54class DOTFuncInfo {
55private:
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
64public:
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() { return BFI; }
76
77  const BranchProbabilityInfo *getBPI() { return BPI; }
78
79  const Function *getFunction() { return this->F; }
80
81  uint64_t getMaxFreq() { return MaxFreq; }
82
83  uint64_t getFreq(const BasicBlock *BB) {
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
100template <>
101struct 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
122template <>
123struct DOTGraphTraits<DOTFuncInfo *> : public DefaultDOTGraphTraits {
124
125  // Cache for is hidden property
126  llvm::DenseMap<const BasicBlock *, bool> isHiddenBasicBlock;
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 computeHiddenNodes(const Function *F);
300};
301} // End llvm namespace
302
303namespace llvm {
304class FunctionPass;
305FunctionPass *createCFGPrinterLegacyPassPass();
306FunctionPass *createCFGOnlyPrinterLegacyPassPass();
307} // End llvm namespace
308
309#endif
310