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/raw_ostream.h" 31#include <algorithm> 32#include <cstddef> 33#include <iterator> 34#include <string> 35#include <type_traits> 36#include <vector> 37 38namespace llvm { 39 40namespace DOT { // Private functions... 41 42std::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. 46StringRef getColorString(unsigned NodeNumber); 47 48} // end namespace DOT 49 50namespace GraphProgram { 51 52enum Name { 53 DOT, 54 FDP, 55 NEATO, 56 TWOPI, 57 CIRCO 58}; 59 60} // end namespace GraphProgram 61 62bool DisplayGraph(StringRef Filename, bool wait = true, 63 GraphProgram::Name program = GraphProgram::DOT); 64 65template<typename GraphType> 66class 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 109public: 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 122 DOTGraphTraits<GraphType>::addCustomGraphFeatures(G, *this); 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(). 303 raw_ostream &getOStream() { 304 return O; 305 } 306}; 307 308template<typename GraphType> 309raw_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 321std::string createGraphFilename(const Twine &Name, int &FD); 322 323template <typename GraphType> 324std::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/// 347template<typename GraphType> 348void ViewGraph(const GraphType &G, const Twine &Name, 349 bool ShortNames = false, const Twine &Title = "", 350 GraphProgram::Name Program = GraphProgram::DOT) { 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 362