1193323Sed//===-- llvm/Support/GraphWriter.h - Write graph to a .dot file -*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines a simple interface that can be used to print out generic 11193323Sed// LLVM graphs to ".dot" files. "dot" is a tool that is part of the AT&T 12193323Sed// graphviz package (http://www.research.att.com/sw/tools/graphviz/) which can 13193323Sed// be used to turn the files output by this interface into a variety of 14193323Sed// different graphics formats. 15193323Sed// 16193323Sed// Graphs do not need to implement any interface past what is already required 17193323Sed// by the GraphTraits template, but they can choose to implement specializations 18193323Sed// of the DOTGraphTraits template if they want to customize the graphs output in 19193323Sed// any way. 20193323Sed// 21193323Sed//===----------------------------------------------------------------------===// 22193323Sed 23193323Sed#ifndef LLVM_SUPPORT_GRAPHWRITER_H 24193323Sed#define LLVM_SUPPORT_GRAPHWRITER_H 25193323Sed 26252723Sdim#include "llvm/ADT/GraphTraits.h" 27193323Sed#include "llvm/Support/DOTGraphTraits.h" 28252723Sdim#include "llvm/Support/Path.h" 29198090Srdivacky#include "llvm/Support/raw_ostream.h" 30252723Sdim#include <cassert> 31193323Sed#include <vector> 32193323Sed 33193323Sednamespace llvm { 34193323Sed 35193323Sednamespace DOT { // Private functions... 36198090Srdivacky std::string EscapeString(const std::string &Label); 37252723Sdim 38252723Sdim /// \brief Get a color string for this node number. Simply round-robin selects 39252723Sdim /// from a reasonable number of colors. 40252723Sdim StringRef getColorString(unsigned NodeNumber); 41193323Sed} 42193323Sed 43198090Srdivackynamespace GraphProgram { 44198090Srdivacky enum Name { 45198090Srdivacky DOT, 46198090Srdivacky FDP, 47198090Srdivacky NEATO, 48198090Srdivacky TWOPI, 49198090Srdivacky CIRCO 50198090Srdivacky }; 51198090Srdivacky} 52193323Sed 53263509Sdimvoid DisplayGraph(StringRef Filename, bool wait = true, 54263509Sdim GraphProgram::Name program = GraphProgram::DOT); 55198090Srdivacky 56193323Sedtemplate<typename GraphType> 57193323Sedclass GraphWriter { 58198090Srdivacky raw_ostream &O; 59193323Sed const GraphType &G; 60193323Sed 61193323Sed typedef DOTGraphTraits<GraphType> DOTTraits; 62193323Sed typedef GraphTraits<GraphType> GTraits; 63193323Sed typedef typename GTraits::NodeType NodeType; 64193323Sed typedef typename GTraits::nodes_iterator node_iterator; 65193323Sed typedef typename GTraits::ChildIteratorType child_iterator; 66199989Srdivacky DOTTraits DTraits; 67199989Srdivacky 68199989Srdivacky // Writes the edge labels of the node to O and returns true if there are any 69199989Srdivacky // edge labels not equal to the empty string "". 70199989Srdivacky bool getEdgeSourceLabels(raw_ostream &O, NodeType *Node) { 71199989Srdivacky child_iterator EI = GTraits::child_begin(Node); 72199989Srdivacky child_iterator EE = GTraits::child_end(Node); 73199989Srdivacky bool hasEdgeSourceLabels = false; 74199989Srdivacky 75199989Srdivacky for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i) { 76199989Srdivacky std::string label = DTraits.getEdgeSourceLabel(Node, EI); 77199989Srdivacky 78221345Sdim if (label.empty()) 79199989Srdivacky continue; 80199989Srdivacky 81199989Srdivacky hasEdgeSourceLabels = true; 82199989Srdivacky 83199989Srdivacky if (i) 84199989Srdivacky O << "|"; 85199989Srdivacky 86221345Sdim O << "<s" << i << ">" << DOT::EscapeString(label); 87199989Srdivacky } 88199989Srdivacky 89199989Srdivacky if (EI != EE && hasEdgeSourceLabels) 90199989Srdivacky O << "|<s64>truncated..."; 91199989Srdivacky 92199989Srdivacky return hasEdgeSourceLabels; 93199989Srdivacky } 94199989Srdivacky 95193323Sedpublic: 96199989Srdivacky GraphWriter(raw_ostream &o, const GraphType &g, bool SN) : O(o), G(g) { 97218893Sdim DTraits = DOTTraits(SN); 98218893Sdim } 99193323Sed 100218893Sdim void writeGraph(const std::string &Title = "") { 101218893Sdim // Output the header for the graph... 102218893Sdim writeHeader(Title); 103218893Sdim 104218893Sdim // Emit all of the nodes in the graph... 105218893Sdim writeNodes(); 106218893Sdim 107218893Sdim // Output any customizations on the graph 108218893Sdim DOTGraphTraits<GraphType>::addCustomGraphFeatures(G, *this); 109218893Sdim 110218893Sdim // Output the end of the graph 111218893Sdim writeFooter(); 112218893Sdim } 113218893Sdim 114218893Sdim void writeHeader(const std::string &Title) { 115199989Srdivacky std::string GraphName = DTraits.getGraphName(G); 116193323Sed 117218893Sdim if (!Title.empty()) 118218893Sdim O << "digraph \"" << DOT::EscapeString(Title) << "\" {\n"; 119193323Sed else if (!GraphName.empty()) 120193323Sed O << "digraph \"" << DOT::EscapeString(GraphName) << "\" {\n"; 121193323Sed else 122193323Sed O << "digraph unnamed {\n"; 123193323Sed 124199989Srdivacky if (DTraits.renderGraphFromBottomUp()) 125193323Sed O << "\trankdir=\"BT\";\n"; 126193323Sed 127218893Sdim if (!Title.empty()) 128218893Sdim O << "\tlabel=\"" << DOT::EscapeString(Title) << "\";\n"; 129193323Sed else if (!GraphName.empty()) 130193323Sed O << "\tlabel=\"" << DOT::EscapeString(GraphName) << "\";\n"; 131199989Srdivacky O << DTraits.getGraphProperties(G); 132193323Sed O << "\n"; 133193323Sed } 134193323Sed 135193323Sed void writeFooter() { 136193323Sed // Finish off the graph 137193323Sed O << "}\n"; 138193323Sed } 139193323Sed 140193323Sed void writeNodes() { 141193323Sed // Loop over the graph, printing it out... 142193323Sed for (node_iterator I = GTraits::nodes_begin(G), E = GTraits::nodes_end(G); 143193323Sed I != E; ++I) 144208599Srdivacky if (!isNodeHidden(*I)) 145208599Srdivacky writeNode(*I); 146193323Sed } 147193323Sed 148208599Srdivacky bool isNodeHidden(NodeType &Node) { 149208599Srdivacky return isNodeHidden(&Node); 150208599Srdivacky } 151208599Srdivacky 152208599Srdivacky bool isNodeHidden(NodeType *const *Node) { 153208599Srdivacky return isNodeHidden(*Node); 154208599Srdivacky } 155208599Srdivacky 156208599Srdivacky bool isNodeHidden(NodeType *Node) { 157208599Srdivacky return DTraits.isNodeHidden(Node); 158208599Srdivacky } 159208599Srdivacky 160193323Sed void writeNode(NodeType& Node) { 161193323Sed writeNode(&Node); 162193323Sed } 163193323Sed 164193323Sed void writeNode(NodeType *const *Node) { 165193323Sed writeNode(*Node); 166193323Sed } 167193323Sed 168193323Sed void writeNode(NodeType *Node) { 169199989Srdivacky std::string NodeAttributes = DTraits.getNodeAttributes(Node, G); 170193323Sed 171193323Sed O << "\tNode" << static_cast<const void*>(Node) << " [shape=record,"; 172193323Sed if (!NodeAttributes.empty()) O << NodeAttributes << ","; 173193323Sed O << "label=\"{"; 174193323Sed 175199989Srdivacky if (!DTraits.renderGraphFromBottomUp()) { 176199989Srdivacky O << DOT::EscapeString(DTraits.getNodeLabel(Node, G)); 177193323Sed 178193323Sed // If we should include the address of the node in the label, do so now. 179199989Srdivacky if (DTraits.hasNodeAddressLabel(Node, G)) 180245431Sdim O << "|" << static_cast<const void*>(Node); 181252723Sdim 182252723Sdim std::string NodeDesc = DTraits.getNodeDescription(Node, G); 183252723Sdim if (!NodeDesc.empty()) 184252723Sdim O << "|" << DOT::EscapeString(NodeDesc); 185193323Sed } 186193323Sed 187199989Srdivacky std::string edgeSourceLabels; 188199989Srdivacky raw_string_ostream EdgeSourceLabels(edgeSourceLabels); 189199989Srdivacky bool hasEdgeSourceLabels = getEdgeSourceLabels(EdgeSourceLabels, Node); 190193323Sed 191199989Srdivacky if (hasEdgeSourceLabels) { 192199989Srdivacky if (!DTraits.renderGraphFromBottomUp()) O << "|"; 193193323Sed 194199989Srdivacky O << "{" << EdgeSourceLabels.str() << "}"; 195199989Srdivacky 196199989Srdivacky if (DTraits.renderGraphFromBottomUp()) O << "|"; 197193323Sed } 198193323Sed 199199989Srdivacky if (DTraits.renderGraphFromBottomUp()) { 200199989Srdivacky O << DOT::EscapeString(DTraits.getNodeLabel(Node, G)); 201193323Sed 202193323Sed // If we should include the address of the node in the label, do so now. 203199989Srdivacky if (DTraits.hasNodeAddressLabel(Node, G)) 204245431Sdim O << "|" << static_cast<const void*>(Node); 205252723Sdim 206252723Sdim std::string NodeDesc = DTraits.getNodeDescription(Node, G); 207252723Sdim if (!NodeDesc.empty()) 208252723Sdim O << "|" << DOT::EscapeString(NodeDesc); 209193323Sed } 210193323Sed 211199989Srdivacky if (DTraits.hasEdgeDestLabels()) { 212193323Sed O << "|{"; 213193323Sed 214199989Srdivacky unsigned i = 0, e = DTraits.numEdgeDestLabels(Node); 215193323Sed for (; i != e && i != 64; ++i) { 216193323Sed if (i) O << "|"; 217207618Srdivacky O << "<d" << i << ">" 218207618Srdivacky << DOT::EscapeString(DTraits.getEdgeDestLabel(Node, i)); 219193323Sed } 220193323Sed 221193323Sed if (i != e) 222193323Sed O << "|<d64>truncated..."; 223193323Sed O << "}"; 224193323Sed } 225193323Sed 226193323Sed O << "}\"];\n"; // Finish printing the "node" line 227193323Sed 228193323Sed // Output all of the edges now 229199989Srdivacky child_iterator EI = GTraits::child_begin(Node); 230199989Srdivacky child_iterator EE = GTraits::child_end(Node); 231193323Sed for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i) 232208599Srdivacky if (!DTraits.isNodeHidden(*EI)) 233208599Srdivacky writeEdge(Node, i, EI); 234193323Sed for (; EI != EE; ++EI) 235208599Srdivacky if (!DTraits.isNodeHidden(*EI)) 236208599Srdivacky writeEdge(Node, 64, EI); 237193323Sed } 238193323Sed 239193323Sed void writeEdge(NodeType *Node, unsigned edgeidx, child_iterator EI) { 240193323Sed if (NodeType *TargetNode = *EI) { 241193323Sed int DestPort = -1; 242199989Srdivacky if (DTraits.edgeTargetsEdgeSource(Node, EI)) { 243199989Srdivacky child_iterator TargetIt = DTraits.getEdgeTarget(Node, EI); 244193323Sed 245193323Sed // Figure out which edge this targets... 246193323Sed unsigned Offset = 247193323Sed (unsigned)std::distance(GTraits::child_begin(TargetNode), TargetIt); 248193323Sed DestPort = static_cast<int>(Offset); 249193323Sed } 250193323Sed 251221345Sdim if (DTraits.getEdgeSourceLabel(Node, EI).empty()) 252199989Srdivacky edgeidx = -1; 253199989Srdivacky 254193323Sed emitEdge(static_cast<const void*>(Node), edgeidx, 255193323Sed static_cast<const void*>(TargetNode), DestPort, 256221345Sdim DTraits.getEdgeAttributes(Node, EI, G)); 257193323Sed } 258193323Sed } 259193323Sed 260193323Sed /// emitSimpleNode - Outputs a simple (non-record) node 261193323Sed void emitSimpleNode(const void *ID, const std::string &Attr, 262193323Sed const std::string &Label, unsigned NumEdgeSources = 0, 263193323Sed const std::vector<std::string> *EdgeSourceLabels = 0) { 264193323Sed O << "\tNode" << ID << "[ "; 265193323Sed if (!Attr.empty()) 266193323Sed O << Attr << ","; 267193323Sed O << " label =\""; 268193323Sed if (NumEdgeSources) O << "{"; 269193323Sed O << DOT::EscapeString(Label); 270193323Sed if (NumEdgeSources) { 271193323Sed O << "|{"; 272193323Sed 273193323Sed for (unsigned i = 0; i != NumEdgeSources; ++i) { 274193323Sed if (i) O << "|"; 275198090Srdivacky O << "<s" << i << ">"; 276207618Srdivacky if (EdgeSourceLabels) O << DOT::EscapeString((*EdgeSourceLabels)[i]); 277193323Sed } 278193323Sed O << "}}"; 279193323Sed } 280193323Sed O << "\"];\n"; 281193323Sed } 282193323Sed 283193323Sed /// emitEdge - Output an edge from a simple node into the graph... 284193323Sed void emitEdge(const void *SrcNodeID, int SrcNodePort, 285193323Sed const void *DestNodeID, int DestNodePort, 286193323Sed const std::string &Attrs) { 287193323Sed if (SrcNodePort > 64) return; // Eminating from truncated part? 288221345Sdim if (DestNodePort > 64) DestNodePort = 64; // Targeting the truncated part? 289193323Sed 290193323Sed O << "\tNode" << SrcNodeID; 291193323Sed if (SrcNodePort >= 0) 292193323Sed O << ":s" << SrcNodePort; 293193323Sed O << " -> Node" << DestNodeID; 294199989Srdivacky if (DestNodePort >= 0 && DTraits.hasEdgeDestLabels()) 295199989Srdivacky O << ":d" << DestNodePort; 296193323Sed 297193323Sed if (!Attrs.empty()) 298193323Sed O << "[" << Attrs << "]"; 299193323Sed O << ";\n"; 300193323Sed } 301212904Sdim 302212904Sdim /// getOStream - Get the raw output stream into the graph file. Useful to 303212904Sdim /// write fancy things using addCustomGraphFeatures(). 304212904Sdim raw_ostream &getOStream() { 305212904Sdim return O; 306212904Sdim } 307193323Sed}; 308193323Sed 309193323Sedtemplate<typename GraphType> 310198090Srdivackyraw_ostream &WriteGraph(raw_ostream &O, const GraphType &G, 311198090Srdivacky bool ShortNames = false, 312235633Sdim const Twine &Title = "") { 313193323Sed // Start the graph emission process... 314195098Sed GraphWriter<GraphType> W(O, G, ShortNames); 315193323Sed 316218893Sdim // Emit the graph. 317235633Sdim W.writeGraph(Title.str()); 318193323Sed 319193323Sed return O; 320193323Sed} 321193323Sed 322263509Sdimstd::string createGraphFilename(const Twine &Name, int &FD); 323193323Sed 324263509Sdimtemplate <typename GraphType> 325263509Sdimstd::string WriteGraph(const GraphType &G, const Twine &Name, 326263509Sdim bool ShortNames = false, const Twine &Title = "") { 327263509Sdim int FD; 328263509Sdim std::string Filename = createGraphFilename(Name, FD); 329263509Sdim raw_fd_ostream O(FD, /*shouldClose=*/ true); 330193323Sed 331263509Sdim if (FD == -1) { 332263509Sdim errs() << "error opening file '" << Filename << "' for writing!\n"; 333263509Sdim return ""; 334193323Sed } 335193323Sed 336263509Sdim llvm::WriteGraph(O, G, ShortNames, Title); 337263509Sdim errs() << " done. \n"; 338263509Sdim 339193323Sed return Filename; 340193323Sed} 341193323Sed 342193323Sed/// ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, 343193323Sed/// then cleanup. For use from the debugger. 344193323Sed/// 345193323Sedtemplate<typename GraphType> 346235633Sdimvoid ViewGraph(const GraphType &G, const Twine &Name, 347235633Sdim bool ShortNames = false, const Twine &Title = "", 348198090Srdivacky GraphProgram::Name Program = GraphProgram::DOT) { 349263509Sdim std::string Filename = llvm::WriteGraph(G, Name, ShortNames, Title); 350193323Sed 351263509Sdim if (Filename.empty()) 352193323Sed return; 353193323Sed 354198090Srdivacky DisplayGraph(Filename, true, Program); 355193323Sed} 356193323Sed 357193323Sed} // End llvm namespace 358193323Sed 359193323Sed#endif 360