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