1// Copyright 2013 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/compiler/graph-visualizer.h"
6
7#include "src/compiler/generic-algorithm.h"
8#include "src/compiler/generic-node.h"
9#include "src/compiler/generic-node-inl.h"
10#include "src/compiler/graph.h"
11#include "src/compiler/graph-inl.h"
12#include "src/compiler/node.h"
13#include "src/compiler/node-properties.h"
14#include "src/compiler/node-properties-inl.h"
15#include "src/compiler/opcodes.h"
16#include "src/compiler/operator.h"
17#include "src/ostreams.h"
18
19namespace v8 {
20namespace internal {
21namespace compiler {
22
23#define DEAD_COLOR "#999999"
24
25class GraphVisualizer : public NullNodeVisitor {
26 public:
27  GraphVisualizer(OStream& os, Zone* zone, const Graph* graph);  // NOLINT
28
29  void Print();
30
31  GenericGraphVisit::Control Pre(Node* node);
32  GenericGraphVisit::Control PreEdge(Node* from, int index, Node* to);
33
34 private:
35  void AnnotateNode(Node* node);
36  void PrintEdge(Node::Edge edge);
37
38  Zone* zone_;
39  NodeSet all_nodes_;
40  NodeSet white_nodes_;
41  bool use_to_def_;
42  OStream& os_;
43  const Graph* const graph_;
44
45  DISALLOW_COPY_AND_ASSIGN(GraphVisualizer);
46};
47
48
49static Node* GetControlCluster(Node* node) {
50  if (OperatorProperties::IsBasicBlockBegin(node->op())) {
51    return node;
52  } else if (OperatorProperties::GetControlInputCount(node->op()) == 1) {
53    Node* control = NodeProperties::GetControlInput(node, 0);
54    return OperatorProperties::IsBasicBlockBegin(control->op()) ? control
55                                                                : NULL;
56  } else {
57    return NULL;
58  }
59}
60
61
62GenericGraphVisit::Control GraphVisualizer::Pre(Node* node) {
63  if (all_nodes_.count(node) == 0) {
64    Node* control_cluster = GetControlCluster(node);
65    if (control_cluster != NULL) {
66      os_ << "  subgraph cluster_BasicBlock" << control_cluster->id() << " {\n";
67    }
68    os_ << "  ID" << node->id() << " [\n";
69    AnnotateNode(node);
70    os_ << "  ]\n";
71    if (control_cluster != NULL) os_ << "  }\n";
72    all_nodes_.insert(node);
73    if (use_to_def_) white_nodes_.insert(node);
74  }
75  return GenericGraphVisit::CONTINUE;
76}
77
78
79GenericGraphVisit::Control GraphVisualizer::PreEdge(Node* from, int index,
80                                                    Node* to) {
81  if (use_to_def_) return GenericGraphVisit::CONTINUE;
82  // When going from def to use, only consider white -> other edges, which are
83  // the dead nodes that use live nodes. We're probably not interested in
84  // dead nodes that only use other dead nodes.
85  if (white_nodes_.count(from) > 0) return GenericGraphVisit::CONTINUE;
86  return GenericGraphVisit::SKIP;
87}
88
89
90class Escaped {
91 public:
92  explicit Escaped(const OStringStream& os) : str_(os.c_str()) {}
93
94  friend OStream& operator<<(OStream& os, const Escaped& e) {
95    for (const char* s = e.str_; *s != '\0'; ++s) {
96      if (needs_escape(*s)) os << "\\";
97      os << *s;
98    }
99    return os;
100  }
101
102 private:
103  static bool needs_escape(char ch) {
104    switch (ch) {
105      case '>':
106      case '<':
107      case '|':
108      case '}':
109      case '{':
110        return true;
111      default:
112        return false;
113    }
114  }
115
116  const char* const str_;
117};
118
119
120static bool IsLikelyBackEdge(Node* from, int index, Node* to) {
121  if (from->opcode() == IrOpcode::kPhi ||
122      from->opcode() == IrOpcode::kEffectPhi) {
123    Node* control = NodeProperties::GetControlInput(from, 0);
124    return control->opcode() != IrOpcode::kMerge && control != to && index != 0;
125  } else if (from->opcode() == IrOpcode::kLoop) {
126    return index != 0;
127  } else {
128    return false;
129  }
130}
131
132
133void GraphVisualizer::AnnotateNode(Node* node) {
134  if (!use_to_def_) {
135    os_ << "    style=\"filled\"\n"
136        << "    fillcolor=\"" DEAD_COLOR "\"\n";
137  }
138
139  os_ << "    shape=\"record\"\n";
140  switch (node->opcode()) {
141    case IrOpcode::kEnd:
142    case IrOpcode::kDead:
143    case IrOpcode::kStart:
144      os_ << "    style=\"diagonals\"\n";
145      break;
146    case IrOpcode::kMerge:
147    case IrOpcode::kIfTrue:
148    case IrOpcode::kIfFalse:
149    case IrOpcode::kLoop:
150      os_ << "    style=\"rounded\"\n";
151      break;
152    default:
153      break;
154  }
155
156  OStringStream label;
157  label << *node->op();
158  os_ << "    label=\"{{#" << node->id() << ":" << Escaped(label);
159
160  InputIter i = node->inputs().begin();
161  for (int j = OperatorProperties::GetValueInputCount(node->op()); j > 0;
162       ++i, j--) {
163    os_ << "|<I" << i.index() << ">#" << (*i)->id();
164  }
165  for (int j = OperatorProperties::GetContextInputCount(node->op()); j > 0;
166       ++i, j--) {
167    os_ << "|<I" << i.index() << ">X #" << (*i)->id();
168  }
169  for (int j = OperatorProperties::GetFrameStateInputCount(node->op()); j > 0;
170       ++i, j--) {
171    os_ << "|<I" << i.index() << ">F #" << (*i)->id();
172  }
173  for (int j = OperatorProperties::GetEffectInputCount(node->op()); j > 0;
174       ++i, j--) {
175    os_ << "|<I" << i.index() << ">E #" << (*i)->id();
176  }
177
178  if (!use_to_def_ || OperatorProperties::IsBasicBlockBegin(node->op()) ||
179      GetControlCluster(node) == NULL) {
180    for (int j = OperatorProperties::GetControlInputCount(node->op()); j > 0;
181         ++i, j--) {
182      os_ << "|<I" << i.index() << ">C #" << (*i)->id();
183    }
184  }
185  os_ << "}";
186
187  if (FLAG_trace_turbo_types && !NodeProperties::IsControl(node)) {
188    Bounds bounds = NodeProperties::GetBounds(node);
189    OStringStream upper;
190    bounds.upper->PrintTo(upper);
191    OStringStream lower;
192    bounds.lower->PrintTo(lower);
193    os_ << "|" << Escaped(upper) << "|" << Escaped(lower);
194  }
195  os_ << "}\"\n";
196}
197
198
199void GraphVisualizer::PrintEdge(Node::Edge edge) {
200  Node* from = edge.from();
201  int index = edge.index();
202  Node* to = edge.to();
203  bool unconstrained = IsLikelyBackEdge(from, index, to);
204  os_ << "  ID" << from->id();
205  if (all_nodes_.count(to) == 0) {
206    os_ << ":I" << index << ":n -> DEAD_INPUT";
207  } else if (OperatorProperties::IsBasicBlockBegin(from->op()) ||
208             GetControlCluster(from) == NULL ||
209             (OperatorProperties::GetControlInputCount(from->op()) > 0 &&
210              NodeProperties::GetControlInput(from) != to)) {
211    os_ << ":I" << index << ":n -> ID" << to->id() << ":s"
212        << "[" << (unconstrained ? "constraint=false, " : "")
213        << (NodeProperties::IsControlEdge(edge) ? "style=bold, " : "")
214        << (NodeProperties::IsEffectEdge(edge) ? "style=dotted, " : "")
215        << (NodeProperties::IsContextEdge(edge) ? "style=dashed, " : "") << "]";
216  } else {
217    os_ << " -> ID" << to->id() << ":s [color=transparent, "
218        << (unconstrained ? "constraint=false, " : "")
219        << (NodeProperties::IsControlEdge(edge) ? "style=dashed, " : "") << "]";
220  }
221  os_ << "\n";
222}
223
224
225void GraphVisualizer::Print() {
226  os_ << "digraph D {\n"
227      << "  node [fontsize=8,height=0.25]\n"
228      << "  rankdir=\"BT\"\n"
229      << "  ranksep=\"1.2 equally\"\n"
230      << "  overlap=\"false\"\n"
231      << "  splines=\"true\"\n"
232      << "  concentrate=\"true\"\n"
233      << "  \n";
234
235  // Make sure all nodes have been output before writing out the edges.
236  use_to_def_ = true;
237  // TODO(svenpanne) Remove the need for the const_casts.
238  const_cast<Graph*>(graph_)->VisitNodeInputsFromEnd(this);
239  white_nodes_.insert(const_cast<Graph*>(graph_)->start());
240
241  // Visit all uses of white nodes.
242  use_to_def_ = false;
243  GenericGraphVisit::Visit<GraphVisualizer, NodeUseIterationTraits<Node> >(
244      const_cast<Graph*>(graph_), zone_, white_nodes_.begin(),
245      white_nodes_.end(), this);
246
247  os_ << "  DEAD_INPUT [\n"
248      << "    style=\"filled\" \n"
249      << "    fillcolor=\"" DEAD_COLOR "\"\n"
250      << "  ]\n"
251      << "\n";
252
253  // With all the nodes written, add the edges.
254  for (NodeSetIter i = all_nodes_.begin(); i != all_nodes_.end(); ++i) {
255    Node::Inputs inputs = (*i)->inputs();
256    for (Node::Inputs::iterator iter(inputs.begin()); iter != inputs.end();
257         ++iter) {
258      PrintEdge(iter.edge());
259    }
260  }
261  os_ << "}\n";
262}
263
264
265GraphVisualizer::GraphVisualizer(OStream& os, Zone* zone,
266                                 const Graph* graph)  // NOLINT
267    : zone_(zone),
268      all_nodes_(NodeSet::key_compare(), NodeSet::allocator_type(zone)),
269      white_nodes_(NodeSet::key_compare(), NodeSet::allocator_type(zone)),
270      use_to_def_(true),
271      os_(os),
272      graph_(graph) {}
273
274
275OStream& operator<<(OStream& os, const AsDOT& ad) {
276  Zone tmp_zone(ad.graph.zone()->isolate());
277  GraphVisualizer(os, &tmp_zone, &ad.graph).Print();
278  return os;
279}
280}
281}
282}  // namespace v8::internal::compiler
283