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
19 namespace v8 {
20 namespace internal {
21 namespace compiler {
22
23 #define DEAD_COLOR "#999999"
24
25 class 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
GetControlCluster(Node * node)49 static 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
Pre(Node * node)62 GenericGraphVisit::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
PreEdge(Node * from,int index,Node * to)79 GenericGraphVisit::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
90 class Escaped {
91 public:
Escaped(const OStringStream & os)92 explicit Escaped(const OStringStream& os) : str_(os.c_str()) {}
93
operator <<(OStream & os,const Escaped & e)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:
needs_escape(char ch)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
IsLikelyBackEdge(Node * from,int index,Node * to)120 static 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
AnnotateNode(Node * node)133 void 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
PrintEdge(Node::Edge edge)199 void 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
Print()225 void 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
GraphVisualizer(OStream & os,Zone * zone,const Graph * graph)265 GraphVisualizer::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
operator <<(OStream & os,const AsDOT & ad)275 OStream& 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