LLVM  6.0.0svn
GraphWriter.h
Go to the documentation of this file.
1 //===- llvm/Support/GraphWriter.h - Write graph to a .dot file --*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines a simple interface that can be used to print out generic
11 // LLVM graphs to ".dot" files. "dot" is a tool that is part of the AT&T
12 // graphviz package (http://www.research.att.com/sw/tools/graphviz/) which can
13 // be used to turn the files output by this interface into a variety of
14 // different graphics formats.
15 //
16 // Graphs do not need to implement any interface past what is already required
17 // by the GraphTraits template, but they can choose to implement specializations
18 // of the DOTGraphTraits template if they want to customize the graphs output in
19 // any way.
20 //
21 //===----------------------------------------------------------------------===//
22 
23 #ifndef LLVM_SUPPORT_GRAPHWRITER_H
24 #define LLVM_SUPPORT_GRAPHWRITER_H
25 
26 #include "llvm/ADT/GraphTraits.h"
27 #include "llvm/ADT/StringRef.h"
28 #include "llvm/ADT/Twine.h"
31 #include <algorithm>
32 #include <cstddef>
33 #include <iterator>
34 #include <string>
35 #include <type_traits>
36 #include <vector>
37 
38 namespace llvm {
39 
40 namespace DOT { // Private functions...
41 
42 std::string EscapeString(const std::string &Label);
43 
44 /// \brief Get a color string for this node number. Simply round-robin selects
45 /// from a reasonable number of colors.
46 StringRef getColorString(unsigned NodeNumber);
47 
48 } // end namespace DOT
49 
50 namespace GraphProgram {
51 
52 enum Name {
53  DOT,
54  FDP,
58 };
59 
60 } // end namespace GraphProgram
61 
62 bool DisplayGraph(StringRef Filename, bool wait = true,
64 
65 template<typename GraphType>
66 class GraphWriter {
67  raw_ostream &O;
68  const GraphType &G;
69 
70  using DOTTraits = DOTGraphTraits<GraphType>;
71  using GTraits = GraphTraits<GraphType>;
72  using NodeRef = typename GTraits::NodeRef;
73  using node_iterator = typename GTraits::nodes_iterator;
74  using child_iterator = typename GTraits::ChildIteratorType;
75  DOTTraits DTraits;
76 
77  static_assert(std::is_pointer<NodeRef>::value,
78  "FIXME: Currently GraphWriter requires the NodeRef type to be "
79  "a pointer.\nThe pointer usage should be moved to "
80  "DOTGraphTraits, and removed from GraphWriter itself.");
81 
82  // Writes the edge labels of the node to O and returns true if there are any
83  // edge labels not equal to the empty string "".
84  bool getEdgeSourceLabels(raw_ostream &O, NodeRef Node) {
85  child_iterator EI = GTraits::child_begin(Node);
86  child_iterator EE = GTraits::child_end(Node);
87  bool hasEdgeSourceLabels = false;
88 
89  for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i) {
90  std::string label = DTraits.getEdgeSourceLabel(Node, EI);
91 
92  if (label.empty())
93  continue;
94 
95  hasEdgeSourceLabels = true;
96 
97  if (i)
98  O << "|";
99 
100  O << "<s" << i << ">" << DOT::EscapeString(label);
101  }
102 
103  if (EI != EE && hasEdgeSourceLabels)
104  O << "|<s64>truncated...";
105 
106  return hasEdgeSourceLabels;
107  }
108 
109 public:
110  GraphWriter(raw_ostream &o, const GraphType &g, bool SN) : O(o), G(g) {
111  DTraits = DOTTraits(SN);
112  }
113 
114  void writeGraph(const std::string &Title = "") {
115  // Output the header for the graph...
116  writeHeader(Title);
117 
118  // Emit all of the nodes in the graph...
119  writeNodes();
120 
121  // Output any customizations on the graph
123 
124  // Output the end of the graph
125  writeFooter();
126  }
127 
128  void writeHeader(const std::string &Title) {
129  std::string GraphName = DTraits.getGraphName(G);
130 
131  if (!Title.empty())
132  O << "digraph \"" << DOT::EscapeString(Title) << "\" {\n";
133  else if (!GraphName.empty())
134  O << "digraph \"" << DOT::EscapeString(GraphName) << "\" {\n";
135  else
136  O << "digraph unnamed {\n";
137 
138  if (DTraits.renderGraphFromBottomUp())
139  O << "\trankdir=\"BT\";\n";
140 
141  if (!Title.empty())
142  O << "\tlabel=\"" << DOT::EscapeString(Title) << "\";\n";
143  else if (!GraphName.empty())
144  O << "\tlabel=\"" << DOT::EscapeString(GraphName) << "\";\n";
145  O << DTraits.getGraphProperties(G);
146  O << "\n";
147  }
148 
149  void writeFooter() {
150  // Finish off the graph
151  O << "}\n";
152  }
153 
154  void writeNodes() {
155  // Loop over the graph, printing it out...
156  for (const auto Node : nodes<GraphType>(G))
157  if (!isNodeHidden(Node))
158  writeNode(Node);
159  }
160 
161  bool isNodeHidden(NodeRef Node) {
162  return DTraits.isNodeHidden(Node);
163  }
164 
165  void writeNode(NodeRef Node) {
166  std::string NodeAttributes = DTraits.getNodeAttributes(Node, G);
167 
168  O << "\tNode" << static_cast<const void*>(Node) << " [shape=record,";
169  if (!NodeAttributes.empty()) O << NodeAttributes << ",";
170  O << "label=\"{";
171 
172  if (!DTraits.renderGraphFromBottomUp()) {
173  O << DOT::EscapeString(DTraits.getNodeLabel(Node, G));
174 
175  // If we should include the address of the node in the label, do so now.
176  std::string Id = DTraits.getNodeIdentifierLabel(Node, G);
177  if (!Id.empty())
178  O << "|" << DOT::EscapeString(Id);
179 
180  std::string NodeDesc = DTraits.getNodeDescription(Node, G);
181  if (!NodeDesc.empty())
182  O << "|" << DOT::EscapeString(NodeDesc);
183  }
184 
185  std::string edgeSourceLabels;
186  raw_string_ostream EdgeSourceLabels(edgeSourceLabels);
187  bool hasEdgeSourceLabels = getEdgeSourceLabels(EdgeSourceLabels, Node);
188 
189  if (hasEdgeSourceLabels) {
190  if (!DTraits.renderGraphFromBottomUp()) O << "|";
191 
192  O << "{" << EdgeSourceLabels.str() << "}";
193 
194  if (DTraits.renderGraphFromBottomUp()) O << "|";
195  }
196 
197  if (DTraits.renderGraphFromBottomUp()) {
198  O << DOT::EscapeString(DTraits.getNodeLabel(Node, G));
199 
200  // If we should include the address of the node in the label, do so now.
201  std::string Id = DTraits.getNodeIdentifierLabel(Node, G);
202  if (!Id.empty())
203  O << "|" << DOT::EscapeString(Id);
204 
205  std::string NodeDesc = DTraits.getNodeDescription(Node, G);
206  if (!NodeDesc.empty())
207  O << "|" << DOT::EscapeString(NodeDesc);
208  }
209 
210  if (DTraits.hasEdgeDestLabels()) {
211  O << "|{";
212 
213  unsigned i = 0, e = DTraits.numEdgeDestLabels(Node);
214  for (; i != e && i != 64; ++i) {
215  if (i) O << "|";
216  O << "<d" << i << ">"
217  << DOT::EscapeString(DTraits.getEdgeDestLabel(Node, i));
218  }
219 
220  if (i != e)
221  O << "|<d64>truncated...";
222  O << "}";
223  }
224 
225  O << "}\"];\n"; // Finish printing the "node" line
226 
227  // Output all of the edges now
228  child_iterator EI = GTraits::child_begin(Node);
229  child_iterator EE = GTraits::child_end(Node);
230  for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i)
231  if (!DTraits.isNodeHidden(*EI))
232  writeEdge(Node, i, EI);
233  for (; EI != EE; ++EI)
234  if (!DTraits.isNodeHidden(*EI))
235  writeEdge(Node, 64, EI);
236  }
237 
238  void writeEdge(NodeRef Node, unsigned edgeidx, child_iterator EI) {
239  if (NodeRef TargetNode = *EI) {
240  int DestPort = -1;
241  if (DTraits.edgeTargetsEdgeSource(Node, EI)) {
242  child_iterator TargetIt = DTraits.getEdgeTarget(Node, EI);
243 
244  // Figure out which edge this targets...
245  unsigned Offset =
246  (unsigned)std::distance(GTraits::child_begin(TargetNode), TargetIt);
247  DestPort = static_cast<int>(Offset);
248  }
249 
250  if (DTraits.getEdgeSourceLabel(Node, EI).empty())
251  edgeidx = -1;
252 
253  emitEdge(static_cast<const void*>(Node), edgeidx,
254  static_cast<const void*>(TargetNode), DestPort,
255  DTraits.getEdgeAttributes(Node, EI, G));
256  }
257  }
258 
259  /// emitSimpleNode - Outputs a simple (non-record) node
260  void emitSimpleNode(const void *ID, const std::string &Attr,
261  const std::string &Label, unsigned NumEdgeSources = 0,
262  const std::vector<std::string> *EdgeSourceLabels = nullptr) {
263  O << "\tNode" << ID << "[ ";
264  if (!Attr.empty())
265  O << Attr << ",";
266  O << " label =\"";
267  if (NumEdgeSources) O << "{";
268  O << DOT::EscapeString(Label);
269  if (NumEdgeSources) {
270  O << "|{";
271 
272  for (unsigned i = 0; i != NumEdgeSources; ++i) {
273  if (i) O << "|";
274  O << "<s" << i << ">";
275  if (EdgeSourceLabels) O << DOT::EscapeString((*EdgeSourceLabels)[i]);
276  }
277  O << "}}";
278  }
279  O << "\"];\n";
280  }
281 
282  /// emitEdge - Output an edge from a simple node into the graph...
283  void emitEdge(const void *SrcNodeID, int SrcNodePort,
284  const void *DestNodeID, int DestNodePort,
285  const std::string &Attrs) {
286  if (SrcNodePort > 64) return; // Eminating from truncated part?
287  if (DestNodePort > 64) DestNodePort = 64; // Targeting the truncated part?
288 
289  O << "\tNode" << SrcNodeID;
290  if (SrcNodePort >= 0)
291  O << ":s" << SrcNodePort;
292  O << " -> Node" << DestNodeID;
293  if (DestNodePort >= 0 && DTraits.hasEdgeDestLabels())
294  O << ":d" << DestNodePort;
295 
296  if (!Attrs.empty())
297  O << "[" << Attrs << "]";
298  O << ";\n";
299  }
300 
301  /// getOStream - Get the raw output stream into the graph file. Useful to
302  /// write fancy things using addCustomGraphFeatures().
304  return O;
305  }
306 };
307 
308 template<typename GraphType>
309 raw_ostream &WriteGraph(raw_ostream &O, const GraphType &G,
310  bool ShortNames = false,
311  const Twine &Title = "") {
312  // Start the graph emission process...
313  GraphWriter<GraphType> W(O, G, ShortNames);
314 
315  // Emit the graph.
316  W.writeGraph(Title.str());
317 
318  return O;
319 }
320 
321 std::string createGraphFilename(const Twine &Name, int &FD);
322 
323 template <typename GraphType>
324 std::string WriteGraph(const GraphType &G, const Twine &Name,
325  bool ShortNames = false, const Twine &Title = "") {
326  int FD;
327  // Windows can't always handle long paths, so limit the length of the name.
328  std::string N = Name.str();
329  N = N.substr(0, std::min<std::size_t>(N.size(), 140));
330  std::string Filename = createGraphFilename(N, FD);
331  raw_fd_ostream O(FD, /*shouldClose=*/ true);
332 
333  if (FD == -1) {
334  errs() << "error opening file '" << Filename << "' for writing!\n";
335  return "";
336  }
337 
338  llvm::WriteGraph(O, G, ShortNames, Title);
339  errs() << " done. \n";
340 
341  return Filename;
342 }
343 
344 /// ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file,
345 /// then cleanup. For use from the debugger.
346 ///
347 template<typename GraphType>
348 void ViewGraph(const GraphType &G, const Twine &Name,
349  bool ShortNames = false, const Twine &Title = "",
351  std::string Filename = llvm::WriteGraph(G, Name, ShortNames, Title);
352 
353  if (Filename.empty())
354  return;
355 
356  DisplayGraph(Filename, false, Program);
357 }
358 
359 } // end namespace llvm
360 
361 #endif // LLVM_SUPPORT_GRAPHWRITER_H
void emitSimpleNode(const void *ID, const std::string &Attr, const std::string &Label, unsigned NumEdgeSources=0, const std::vector< std::string > *EdgeSourceLabels=nullptr)
emitSimpleNode - Outputs a simple (non-record) node
Definition: GraphWriter.h:260
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static void addCustomGraphFeatures(const GraphType &, GraphWriter &)
addCustomGraphFeatures - If a graph is made up of more than just straight-forward nodes and edges...
bool isNodeHidden(NodeRef Node)
Definition: GraphWriter.h:161
void writeEdge(NodeRef Node, unsigned edgeidx, child_iterator EI)
Definition: GraphWriter.h:238
void writeGraph(const std::string &Title="")
Definition: GraphWriter.h:114
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
raw_ostream & WriteGraph(raw_ostream &O, const GraphType &G, bool ShortNames=false, const Twine &Title="")
Definition: GraphWriter.h:309
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
std::string EscapeString(const std::string &Label)
Definition: GraphWriter.cpp:36
void ViewGraph(const GraphType &G, const Twine &Name, bool ShortNames=false, const Twine &Title="", GraphProgram::Name Program=GraphProgram::DOT)
ViewGraph - Emit a dot graph, run &#39;dot&#39;, run gv on the postscript file, then cleanup.
Definition: GraphWriter.h:348
std::string & str()
Flushes the stream contents to the target string and returns the string&#39;s reference.
Definition: raw_ostream.h:478
std::string createGraphFilename(const Twine &Name, int &FD)
Definition: GraphWriter.cpp:80
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
StringRef getColorString(unsigned NodeNumber)
Get a color string for this node number.
Definition: GraphWriter.cpp:71
raw_ostream & getOStream()
getOStream - Get the raw output stream into the graph file.
Definition: GraphWriter.h:303
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:361
bool DisplayGraph(StringRef Filename, bool wait=true, GraphProgram::Name program=GraphProgram::DOT)
#define N
void emitEdge(const void *SrcNodeID, int SrcNodePort, const void *DestNodeID, int DestNodePort, const std::string &Attrs)
emitEdge - Output an edge from a simple node into the graph...
Definition: GraphWriter.h:283
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:462
void writeHeader(const std::string &Title)
Definition: GraphWriter.h:128
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
void writeNode(NodeRef Node)
Definition: GraphWriter.h:165
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
GraphWriter(raw_ostream &o, const GraphType &g, bool SN)
Definition: GraphWriter.h:110