LLVM  13.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() 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 <>
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 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
llvm::SuccIterator
Definition: CFG.h:139
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::createCFGOnlyPrinterLegacyPassPass
FunctionPass * createCFGOnlyPrinterLegacyPassPass()
Definition: CFGPrinter.cpp:269
Attrs
Function Attrs
Definition: README_ALTIVEC.txt:215
llvm
Definition: AllocatorList.h:23
llvm::Function::end
iterator end()
Definition: Function.h:780
llvm::DOTFuncInfo::DOTFuncInfo
DOTFuncInfo(const Function *F, const BlockFrequencyInfo *BFI, const BranchProbabilityInfo *BPI, uint64_t MaxFreq)
Definition: CFGPrinter.h:67
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:61
llvm::DOTFuncInfo::showHeatColors
bool showHeatColors()
Definition: CFGPrinter.h:89
llvm::DOTFuncInfo::setHeatColors
void setHeatColors(bool ShowHeat)
Definition: CFGPrinter.h:87
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:614
double
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in and only one load from a constant double
Definition: README-SSE.txt:85
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:762
llvm::CFGPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
llvm::DOTFuncInfo::getBFI
const BlockFrequencyInfo * getBFI() const
Definition: CFGPrinter.h:75
llvm::DOTFuncInfo::setEdgeWeights
void setEdgeWeights(bool EdgeWeights)
Definition: CFGPrinter.h:95
STLExtras.h
llvm::CFGOnlyPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
llvm::getHeatColor
std::string getHeatColor(uint64_t freq, uint64_t maxFreq)
Definition: HeatUtils.cpp:62
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::DOTGraphTraits< DOTFuncInfo * >::getGraphName
static std::string getGraphName(DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:130
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1108
llvm::formatv
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
Definition: FormatVariadic.h:250
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:740
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
Constants.h
llvm::GraphTraits< DOTFuncInfo * >::nodes_begin
static nodes_iterator nodes_begin(DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:109
llvm::CFGOnlyViewerPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
llvm::BranchProbabilityInfo
Analysis providing branch probability information.
Definition: BranchProbabilityInfo.h:115
llvm::CFGViewerPass
Definition: CFGPrinter.h:34
llvm::Instruction
Definition: Instruction.h:45
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:752
llvm::SwitchInst::CaseIteratorImpl::fromSuccessorIndex
static CaseIteratorImpl fromSuccessorIndex(SwitchInstT *SI, unsigned SuccessorIndex)
Initializes case iterator for given SwitchInst and for given successor index.
Definition: Instructions.h:3319
FormatVariadic.h
llvm::StringRef::str
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:245
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:282
llvm::GraphTraits< DOTFuncInfo * >::getEntryNode
static NodeRef getEntryNode(DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:102
CFG.h
llvm::DOTGraphTraits
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
Definition: DOTGraphTraits.h:161
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1102
llvm::DOTFuncInfo::getMaxFreq
uint64_t getMaxFreq() const
Definition: CFGPrinter.h:81
llvm::pointer_iterator
Definition: iterator.h:320
BranchProbabilityInfo.h
llvm::createCFGPrinterLegacyPassPass
FunctionPass * createCFGPrinterLegacyPassPass()
Definition: CFGPrinter.cpp:265
llvm::DOTFuncInfo::useRawEdgeWeights
bool useRawEdgeWeights()
Definition: CFGPrinter.h:93
llvm::DenseMap< const BasicBlock *, bool >
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
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
HeatUtils.h
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::GraphTraits< DOTFuncInfo * >::nodes_end
static nodes_iterator nodes_end(DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:113
llvm::GraphTraits< const BasicBlock * >
Definition: CFG.h:310
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
llvm::BranchProbabilityInfo::getEdgeProbability
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
Definition: BranchProbabilityInfo.cpp:1133
llvm::DOTGraphTraits< DOTFuncInfo * >::getNodeLabel
std::string getNodeLabel(const BasicBlock *Node, DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:199
BlockFrequencyInfo.h
Node
Definition: ItaniumDemangle.h:114
llvm::GraphTraits< DOTFuncInfo * >::size
static size_t size(DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:117
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:294
llvm::Function::begin
iterator begin()
Definition: Function.h:778
llvm::ConstantInt::getZExtValue
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:140
llvm::DOTGraphTraits< DOTFuncInfo * >::getEdgeAttributes
std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I, DOTFuncInfo *CFGInfo)
Display the raw branch weights from PGO.
Definition: CFGPrinter.h:231
GraphWriter.h
llvm::CFGOnlyViewerPass
Definition: CFGPrinter.h:39
llvm::DOTFuncInfo
Definition: CFGPrinter.h:54
llvm::DOTGraphTraits< DOTFuncInfo * >::getCompleteNodeLabel
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
llvm::DOTGraphTraits< DOTFuncInfo * >::getEdgeSourceLabel
static std::string getEdgeSourceLabel(const BasicBlock *Node, const_succ_iterator I)
Definition: CFGPrinter.h:207
Function.h
PassManager.h
llvm::DOTFuncInfo::getFreq
uint64_t getFreq(const BasicBlock *BB) const
Definition: CFGPrinter.h:83
llvm::DOTGraphTraits< DOTFuncInfo * >::getNodeAttributes
std::string getNodeAttributes(const BasicBlock *Node, DOTFuncInfo *CFGInfo)
Definition: CFGPrinter.h:283
isSimple
static bool isSimple(Instruction *I)
Definition: SLPVectorizer.cpp:525
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:403
llvm::CFGOnlyPrinterPass
Definition: CFGPrinter.h:49
Instructions.h
llvm::CFGViewerPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:62
llvm::CFGPrinterPass
Definition: CFGPrinter.h:44
llvm::DOTFuncInfo::getBPI
const BranchProbabilityInfo * getBPI() const
Definition: CFGPrinter.h:77
llvm::DefaultDOTGraphTraits
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
Definition: DOTGraphTraits.h:28
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::DOTFuncInfo::showEdgeWeights
bool showEdgeWeights()
Definition: CFGPrinter.h:97
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3179
llvm::DOTFuncInfo::getFunction
const Function * getFunction() const
Definition: CFGPrinter.h:79
llvm::MDString::getString
StringRef getString() const
Definition: Metadata.cpp:477
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3035
llvm::MDString
A single uniqued string.
Definition: Metadata.h:611
llvm::DOTFuncInfo::setRawEdgeWeights
void setRawEdgeWeights(bool RawWeights)
Definition: CFGPrinter.h:91
llvm::raw_string_ostream::str
std::string & str()
Flushes the stream contents to the target string and returns the string's reference.
Definition: raw_ostream.h:632
llvm::DOTGraphTraits< DOTFuncInfo * >::DOTGraphTraits
DOTGraphTraits(bool isSimple=false)
Definition: CFGPrinter.h:128
llvm::DOTGraphTraits< DOTFuncInfo * >::isOnDeoptOrUnreachablePath
llvm::DenseMap< const BasicBlock *, bool > isOnDeoptOrUnreachablePath
Definition: CFGPrinter.h:126
llvm::DOTGraphTraits< DOTFuncInfo * >::getSimpleNodeLabel
static std::string getSimpleNodeLabel(const BasicBlock *Node, DOTFuncInfo *)
Definition: CFGPrinter.h:134
llvm::Function::size
size_t size() const
Definition: Function.h:783
llvm::DOTGraphTraits< DOTFuncInfo * >::eraseComment
static void eraseComment(std::string &OutStr, unsigned &I, unsigned Idx)
Definition: CFGPrinter.h:145
llvm::DOTFuncInfo::DOTFuncInfo
DOTFuncInfo(const Function *F)
Definition: CFGPrinter.h:65