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/Twine.h"
28#include "llvm/Support/DOTGraphTraits.h"
29#include "llvm/Support/raw_ostream.h"
30#include <vector>
31
32namespace llvm {
33
34namespace DOT {  // Private functions...
35  std::string EscapeString(const std::string &Label);
36
37  /// \brief Get a color string for this node number. Simply round-robin selects
38  /// from a reasonable number of colors.
39  StringRef getColorString(unsigned NodeNumber);
40}
41
42namespace GraphProgram {
43   enum Name {
44      DOT,
45      FDP,
46      NEATO,
47      TWOPI,
48      CIRCO
49   };
50}
51
52bool DisplayGraph(StringRef Filename, bool wait = true,
53                  GraphProgram::Name program = GraphProgram::DOT);
54
55template<typename GraphType>
56class GraphWriter {
57  raw_ostream &O;
58  const GraphType &G;
59
60  typedef DOTGraphTraits<GraphType>           DOTTraits;
61  typedef GraphTraits<GraphType>              GTraits;
62  typedef typename GTraits::NodeRef           NodeRef;
63  typedef typename GTraits::nodes_iterator    node_iterator;
64  typedef typename GTraits::ChildIteratorType child_iterator;
65  DOTTraits DTraits;
66
67  static_assert(std::is_pointer<NodeRef>::value,
68                "FIXME: Currently GraphWriter requires the NodeRef type to be "
69                "a pointer.\nThe pointer usage should be moved to "
70                "DOTGraphTraits, and removed from GraphWriter itself.");
71
72  // Writes the edge labels of the node to O and returns true if there are any
73  // edge labels not equal to the empty string "".
74  bool getEdgeSourceLabels(raw_ostream &O, NodeRef Node) {
75    child_iterator EI = GTraits::child_begin(Node);
76    child_iterator EE = GTraits::child_end(Node);
77    bool hasEdgeSourceLabels = false;
78
79    for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i) {
80      std::string label = DTraits.getEdgeSourceLabel(Node, EI);
81
82      if (label.empty())
83        continue;
84
85      hasEdgeSourceLabels = true;
86
87      if (i)
88        O << "|";
89
90      O << "<s" << i << ">" << DOT::EscapeString(label);
91    }
92
93    if (EI != EE && hasEdgeSourceLabels)
94      O << "|<s64>truncated...";
95
96    return hasEdgeSourceLabels;
97  }
98
99public:
100  GraphWriter(raw_ostream &o, const GraphType &g, bool SN) : O(o), G(g) {
101    DTraits = DOTTraits(SN);
102  }
103
104  void writeGraph(const std::string &Title = "") {
105    // Output the header for the graph...
106    writeHeader(Title);
107
108    // Emit all of the nodes in the graph...
109    writeNodes();
110
111    // Output any customizations on the graph
112    DOTGraphTraits<GraphType>::addCustomGraphFeatures(G, *this);
113
114    // Output the end of the graph
115    writeFooter();
116  }
117
118  void writeHeader(const std::string &Title) {
119    std::string GraphName = DTraits.getGraphName(G);
120
121    if (!Title.empty())
122      O << "digraph \"" << DOT::EscapeString(Title) << "\" {\n";
123    else if (!GraphName.empty())
124      O << "digraph \"" << DOT::EscapeString(GraphName) << "\" {\n";
125    else
126      O << "digraph unnamed {\n";
127
128    if (DTraits.renderGraphFromBottomUp())
129      O << "\trankdir=\"BT\";\n";
130
131    if (!Title.empty())
132      O << "\tlabel=\"" << DOT::EscapeString(Title) << "\";\n";
133    else if (!GraphName.empty())
134      O << "\tlabel=\"" << DOT::EscapeString(GraphName) << "\";\n";
135    O << DTraits.getGraphProperties(G);
136    O << "\n";
137  }
138
139  void writeFooter() {
140    // Finish off the graph
141    O << "}\n";
142  }
143
144  void writeNodes() {
145    // Loop over the graph, printing it out...
146    for (node_iterator I = GTraits::nodes_begin(G), E = GTraits::nodes_end(G);
147         I != E; ++I)
148      if (!isNodeHidden(*I))
149        writeNode(*I);
150  }
151
152  bool isNodeHidden(NodeRef Node) {
153    return DTraits.isNodeHidden(Node);
154  }
155
156  void writeNode(NodeRef Node) {
157    std::string NodeAttributes = DTraits.getNodeAttributes(Node, G);
158
159    O << "\tNode" << static_cast<const void*>(Node) << " [shape=record,";
160    if (!NodeAttributes.empty()) O << NodeAttributes << ",";
161    O << "label=\"{";
162
163    if (!DTraits.renderGraphFromBottomUp()) {
164      O << DOT::EscapeString(DTraits.getNodeLabel(Node, G));
165
166      // If we should include the address of the node in the label, do so now.
167      std::string Id = DTraits.getNodeIdentifierLabel(Node, G);
168      if (!Id.empty())
169        O << "|" << DOT::EscapeString(Id);
170
171      std::string NodeDesc = DTraits.getNodeDescription(Node, G);
172      if (!NodeDesc.empty())
173        O << "|" << DOT::EscapeString(NodeDesc);
174    }
175
176    std::string edgeSourceLabels;
177    raw_string_ostream EdgeSourceLabels(edgeSourceLabels);
178    bool hasEdgeSourceLabels = getEdgeSourceLabels(EdgeSourceLabels, Node);
179
180    if (hasEdgeSourceLabels) {
181      if (!DTraits.renderGraphFromBottomUp()) O << "|";
182
183      O << "{" << EdgeSourceLabels.str() << "}";
184
185      if (DTraits.renderGraphFromBottomUp()) O << "|";
186    }
187
188    if (DTraits.renderGraphFromBottomUp()) {
189      O << DOT::EscapeString(DTraits.getNodeLabel(Node, G));
190
191      // If we should include the address of the node in the label, do so now.
192      std::string Id = DTraits.getNodeIdentifierLabel(Node, G);
193      if (!Id.empty())
194        O << "|" << DOT::EscapeString(Id);
195
196      std::string NodeDesc = DTraits.getNodeDescription(Node, G);
197      if (!NodeDesc.empty())
198        O << "|" << DOT::EscapeString(NodeDesc);
199    }
200
201    if (DTraits.hasEdgeDestLabels()) {
202      O << "|{";
203
204      unsigned i = 0, e = DTraits.numEdgeDestLabels(Node);
205      for (; i != e && i != 64; ++i) {
206        if (i) O << "|";
207        O << "<d" << i << ">"
208          << DOT::EscapeString(DTraits.getEdgeDestLabel(Node, i));
209      }
210
211      if (i != e)
212        O << "|<d64>truncated...";
213      O << "}";
214    }
215
216    O << "}\"];\n";   // Finish printing the "node" line
217
218    // Output all of the edges now
219    child_iterator EI = GTraits::child_begin(Node);
220    child_iterator EE = GTraits::child_end(Node);
221    for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i)
222      if (!DTraits.isNodeHidden(*EI))
223        writeEdge(Node, i, EI);
224    for (; EI != EE; ++EI)
225      if (!DTraits.isNodeHidden(*EI))
226        writeEdge(Node, 64, EI);
227  }
228
229  void writeEdge(NodeRef Node, unsigned edgeidx, child_iterator EI) {
230    if (NodeRef TargetNode = *EI) {
231      int DestPort = -1;
232      if (DTraits.edgeTargetsEdgeSource(Node, EI)) {
233        child_iterator TargetIt = DTraits.getEdgeTarget(Node, EI);
234
235        // Figure out which edge this targets...
236        unsigned Offset =
237          (unsigned)std::distance(GTraits::child_begin(TargetNode), TargetIt);
238        DestPort = static_cast<int>(Offset);
239      }
240
241      if (DTraits.getEdgeSourceLabel(Node, EI).empty())
242        edgeidx = -1;
243
244      emitEdge(static_cast<const void*>(Node), edgeidx,
245               static_cast<const void*>(TargetNode), DestPort,
246               DTraits.getEdgeAttributes(Node, EI, G));
247    }
248  }
249
250  /// emitSimpleNode - Outputs a simple (non-record) node
251  void emitSimpleNode(const void *ID, const std::string &Attr,
252                   const std::string &Label, unsigned NumEdgeSources = 0,
253                   const std::vector<std::string> *EdgeSourceLabels = nullptr) {
254    O << "\tNode" << ID << "[ ";
255    if (!Attr.empty())
256      O << Attr << ",";
257    O << " label =\"";
258    if (NumEdgeSources) O << "{";
259    O << DOT::EscapeString(Label);
260    if (NumEdgeSources) {
261      O << "|{";
262
263      for (unsigned i = 0; i != NumEdgeSources; ++i) {
264        if (i) O << "|";
265        O << "<s" << i << ">";
266        if (EdgeSourceLabels) O << DOT::EscapeString((*EdgeSourceLabels)[i]);
267      }
268      O << "}}";
269    }
270    O << "\"];\n";
271  }
272
273  /// emitEdge - Output an edge from a simple node into the graph...
274  void emitEdge(const void *SrcNodeID, int SrcNodePort,
275                const void *DestNodeID, int DestNodePort,
276                const std::string &Attrs) {
277    if (SrcNodePort  > 64) return;             // Eminating from truncated part?
278    if (DestNodePort > 64) DestNodePort = 64;  // Targeting the truncated part?
279
280    O << "\tNode" << SrcNodeID;
281    if (SrcNodePort >= 0)
282      O << ":s" << SrcNodePort;
283    O << " -> Node" << DestNodeID;
284    if (DestNodePort >= 0 && DTraits.hasEdgeDestLabels())
285      O << ":d" << DestNodePort;
286
287    if (!Attrs.empty())
288      O << "[" << Attrs << "]";
289    O << ";\n";
290  }
291
292  /// getOStream - Get the raw output stream into the graph file. Useful to
293  /// write fancy things using addCustomGraphFeatures().
294  raw_ostream &getOStream() {
295    return O;
296  }
297};
298
299template<typename GraphType>
300raw_ostream &WriteGraph(raw_ostream &O, const GraphType &G,
301                        bool ShortNames = false,
302                        const Twine &Title = "") {
303  // Start the graph emission process...
304  GraphWriter<GraphType> W(O, G, ShortNames);
305
306  // Emit the graph.
307  W.writeGraph(Title.str());
308
309  return O;
310}
311
312std::string createGraphFilename(const Twine &Name, int &FD);
313
314template <typename GraphType>
315std::string WriteGraph(const GraphType &G, const Twine &Name,
316                       bool ShortNames = false, const Twine &Title = "") {
317  int FD;
318  // Windows can't always handle long paths, so limit the length of the name.
319  std::string N = Name.str();
320  N = N.substr(0, std::min<std::size_t>(N.size(), 140));
321  std::string Filename = createGraphFilename(N, FD);
322  raw_fd_ostream O(FD, /*shouldClose=*/ true);
323
324  if (FD == -1) {
325    errs() << "error opening file '" << Filename << "' for writing!\n";
326    return "";
327  }
328
329  llvm::WriteGraph(O, G, ShortNames, Title);
330  errs() << " done. \n";
331
332  return Filename;
333}
334
335/// ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file,
336/// then cleanup.  For use from the debugger.
337///
338template<typename GraphType>
339void ViewGraph(const GraphType &G, const Twine &Name,
340               bool ShortNames = false, const Twine &Title = "",
341               GraphProgram::Name Program = GraphProgram::DOT) {
342  std::string Filename = llvm::WriteGraph(G, Name, ShortNames, Title);
343
344  if (Filename.empty())
345    return;
346
347  DisplayGraph(Filename, false, Program);
348}
349
350} // End llvm namespace
351
352#endif
353