LLVM  12.0.0git
CFGPrinter.h
Go to the documentation of this file.
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"
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"
32 
33 namespace llvm {
34 class CFGViewerPass : public PassInfoMixin<CFGViewerPass> {
35 public:
37 };
38 
39 class CFGOnlyViewerPass : public PassInfoMixin<CFGOnlyViewerPass> {
40 public:
42 };
43 
44 class CFGPrinterPass : public PassInfoMixin<CFGPrinterPass> {
45 public:
47 };
48 
49 class CFGOnlyPrinterPass : public PassInfoMixin<CFGOnlyPrinterPass> {
50 public:
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() { 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 
100 template <>
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
108 
110  return nodes_iterator(CFGInfo->getFunction()->begin());
111  }
112 
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 <>
124 
125  // Cache for is hidden property
127 
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 *,
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,
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.
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 
303 namespace llvm {
304 class FunctionPass;
305 FunctionPass *createCFGPrinterLegacyPassPass();
306 FunctionPass *createCFGOnlyPrinterLegacyPassPass();
307 } // End llvm namespace
308 
309 #endif
size_t size() const
Definition: Function.h:752
bool showHeatColors()
Definition: CFGPrinter.h:89
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:248
This class represents lattice values for constants.
Definition: AllocatorList.h:23
DOTFuncInfo(const Function *F)
Definition: CFGPrinter.h:65
static std::string getSimpleNodeLabel(const BasicBlock *Node, DOTFuncInfo *)
Definition: CFGPrinter.h:134
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
iterator end()
Definition: Function.h:749
static std::string getGraphName(DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:130
FunctionPass * createCFGPrinterLegacyPassPass()
Definition: CFGPrinter.cpp:265
bool useRawEdgeWeights()
Definition: CFGPrinter.h:93
static std::string getCompleteNodeLabel(const BasicBlock *Node, DOTFuncInfo *, llvm::function_ref< void(raw_string_ostream &, const BasicBlock &)> HandleBasicBlock=[](raw_string_ostream &OS, const BasicBlock &Node) -> void { OS<< Node;}, llvm::function_ref< void(std::string &, unsigned &, unsigned)> HandleComment=eraseComment)
Definition: CFGPrinter.h:150
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:176
DOTFuncInfo(const Function *F, const BlockFrequencyInfo *BFI, const BranchProbabilityInfo *BPI, uint64_t MaxFreq)
Definition: CFGPrinter.h:67
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
Metadata node.
Definition: Metadata.h:870
uint64_t getFreq(const BasicBlock *BB)
Definition: CFGPrinter.h:83
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1075
std::string getNodeAttributes(const BasicBlock *Node, DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:283
static nodes_iterator nodes_begin(DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:109
bool showEdgeWeights()
Definition: CFGPrinter.h:97
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
static CaseIteratorImpl fromSuccessorIndex(SwitchInstT *SI, unsigned SuccessorIndex)
Initializes case iterator for given SwitchInst and for given successor index.
static bool isSimple(Instruction *I)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
#define F(x, y, z)
Definition: MD5.cpp:56
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:277
static NodeRef getEntryNode(DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:102
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
iterator begin()
Definition: Function.h:747
static std::string getEdgeSourceLabel(const BasicBlock *Node, const_succ_iterator I)
Definition: CFGPrinter.h:207
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
StringRef getString() const
Definition: Metadata.cpp:464
const BasicBlock & getEntryBlock() const
Definition: Function.h:731
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
FunctionPass * createCFGOnlyPrinterLegacyPassPass()
Definition: CFGPrinter.cpp:269
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:144
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Conditional or Unconditional Branch instruction.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static void eraseComment(std::string &OutStr, unsigned &I, unsigned Idx)
Definition: CFGPrinter.h:145
void setEdgeWeights(bool EdgeWeights)
Definition: CFGPrinter.h:95
const Function * getFunction()
Definition: CFGPrinter.h:79
static nodes_iterator nodes_end(DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:113
std::string & str()
Flushes the stream contents to the target string and returns the string's reference.
Definition: raw_ostream.h:625
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
DOTGraphTraits(bool isSimple=false)
Definition: CFGPrinter.h:128
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
llvm::DenseMap< const BasicBlock *, bool > isHiddenBasicBlock
Definition: CFGPrinter.h:126
Color
A "color", which is either even or odd.
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
const BranchProbabilityInfo * getBPI()
Definition: CFGPrinter.h:77
const BlockFrequencyInfo * getBFI()
Definition: CFGPrinter.h:75
uint64_t getMaxFreq()
Definition: CFGPrinter.h:81
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
std::string getNodeLabel(const BasicBlock *Node, DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:199
Analysis providing branch probability information.
void setHeatColors(bool ShowHeat)
Definition: CFGPrinter.h:87
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:295
#define I(x, y, z)
Definition: MD5.cpp:59
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
std::string getHeatColor(uint64_t freq, uint64_t maxFreq)
Definition: HeatUtils.cpp:62
std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I, DOTFuncInfo *CFGInfo)
Display the raw branch weights from PGO.
Definition: CFGPrinter.h:231
const std::string to_string(const T &Value)
Definition: ScopedPrinter.h:61
Multiway switch.
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:607
static size_t size(DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:117
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
void setRawEdgeWeights(bool RawWeights)
Definition: CFGPrinter.h:91
A single uniqued string.
Definition: Metadata.h:602
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1081