1 /*
2 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.incubator.code.tools.dot;
27
28 import jdk.incubator.code.tools.renderer.CommonRenderer;
29
30 import java.io.Writer;
31 import jdk.incubator.code.Block;
32 import jdk.incubator.code.Body;
33 import jdk.incubator.code.Op;
34 import jdk.incubator.code.Value;
35 import java.util.*;
36
37 /**
38 * Created by gfrost
39 * http://www.graphviz.org/Documentation/dotguide.pdf
40 */
41 public class DotRenderer extends CommonRenderer<DotRenderer> {
42 public DotRenderer() {
43 super();
44 }
45
46 static String sysident(Object o) {
47 return Integer.toString(System.identityHashCode(o));
48 }
49
50 DotRenderer end() {
51 return out().cbrace().nl();
52 }
53
54 public DotRenderer start(String name) {
55 return append("digraph").space().append(name).obrace().in().nl();
56 }
57
58 public DotRenderer rankdir(String s) {
59 return append("rankdir").equal().append(s).semicolon().nl();
60 }
61
62 public DotRenderer concentrate() {
63 return append("concentrate=true").nl();
64 }
65
66 public DotRenderer newrank() {
67 return append("newrank=true").nl();
68 }
69
70 public DotRenderer edgesFirst() {
71 return append("outputorder=edgesfirst").nl();
72 }
73
74
75 public <T extends CommonRenderer<T>> DotRenderer graph(NestedRendererSAM<GraphRenderer> nb) {
76
77 nb.build(new GraphRenderer(this)).end();
78 return self();
79 }
80
81
82 public static class GraphRenderer extends CommonRenderer<GraphRenderer> {
83 public GraphRenderer(DotRenderer dotRenderer) {
84 super(dotRenderer);
85 }
86
87 GraphRenderer end() {
88 return self();
89 }
90
91 public GraphRenderer node(String name, String shape, NestedRendererSAM<NodeRenderer> sam) {
92 sam.build(new NodeRenderer(this, name, shape)).end();
93 return self();
94 }
95
96 public GraphRenderer node(String name, String shape) {
97 return node(name, shape, (n) -> n);
98 }
99
100 public GraphRenderer record(String name, NestedRendererSAM<NodeRenderer> sam) {
101 sam.build(new NodeRenderer(this, name, "record")).end();
102 return self();
103 }
104
105 public GraphRenderer record(String name) {
106 return record(name, (n) -> n);
107 }
108
109 public GraphRenderer ellipse(String name, NestedRendererSAM<NodeRenderer> sam) {
110 sam.build(new NodeRenderer(this, name, "ellipse")).end();
111 return self();
112 }
113
114 public GraphRenderer ellipse(String name) {
115 return ellipse(name, (n) -> n);
116 }
117
118 public GraphRenderer ellipse(Object o, NestedRendererSAM<NodeRenderer> sam) {
119 sam.build(new NodeRenderer(this, sysident(o), "ellipse")).end();
120 return self();
121 }
122
123 public GraphRenderer ellipse(Object o) {
124 return ellipse(o, (n) -> n);
125 }
126
127 public GraphRenderer circle(String name, NestedRendererSAM<NodeRenderer> sam) {
128 sam.build(new NodeRenderer(this, name, "circle")).end();
129 return self();
130 }
131
132 public GraphRenderer circle(String name) {
133 return circle(name, (n) -> n);
134 }
135
136 public GraphRenderer invertedtrapezium(String name, NestedRendererSAM<NodeRenderer> sam) {
137 sam.build(new NodeRenderer(this, name, "invtrapezium")).end();
138 return self();
139 }
140
141 public GraphRenderer invertedtrapezium(String name) {
142 return invertedtrapezium(name, (n) -> n);
143 }
144
145 public GraphRenderer invertedtrapezium(Object o, NestedRendererSAM<NodeRenderer> sam) {
146 sam.build(new NodeRenderer(this, sysident(o), "invtrapezium")).end();
147 return self();
148 }
149
150 public GraphRenderer invertedtrapezium(Object o) {
151 return invertedtrapezium(o, (n) -> n);
152 }
153
154 public GraphRenderer box(String name, NestedRendererSAM<NodeRenderer> sam) {
155 sam.build(new NodeRenderer(this, name, "box")).end();
156 return self();
157 }
158
159 public GraphRenderer box(String name) {
160 return box(name, (n) -> n);
161 }
162
163 public GraphRenderer box(Object o, NestedRendererSAM<NodeRenderer> sam) {
164 sam.build(new NodeRenderer(this, sysident(o), "box")).end();
165 return self();
166 }
167
168 public GraphRenderer box(Object o) {
169 return box(o, (n) -> n);
170 }
171
172 public GraphRenderer hexagon(String name, NestedRendererSAM<NodeRenderer> sam) {
173 sam.build(new NodeRenderer(this, name, "hexagon")).end();
174 return self();
175 }
176
177 public GraphRenderer hexagon(String name) {
178 return hexagon(name, (n) -> n);
179 }
180
181 public GraphRenderer hexagon(Object o, NestedRendererSAM<NodeRenderer> sam) {
182 sam.build(new NodeRenderer(this, sysident(o), "hexagon")).end();
183 return self();
184 }
185
186 public GraphRenderer hexagon(Object o) {
187 return hexagon(o, (n) -> n);
188 }
189
190 public static class NodeRenderer extends CommonRenderer<NodeRenderer> {
191 NodeRenderer(GraphRenderer graphRenderer, String name, String shape) {
192 super(graphRenderer);
193 append(name).osbrace().append("shape").equal().oquot().append(shape).cquot().space();
194 // append(name).osbrace().append("shape").equal().append(shape).space();
195 // append(name).osbrace();//.append("shape").equal().append(shape).space();
196 }
197
198 public NodeRenderer end() {
199 return csbrace().semicolon().nl();
200 }
201
202 NodeRenderer label(String label, NestedRendererSAM<LabelRenderer> sam) {
203 LabelRenderer renderer = new LabelRenderer(this, label);
204 sam.build(renderer).end();
205 return self();
206 }
207
208 NodeRenderer label(NestedRendererSAM<LabelRenderer> sam) {
209 LabelRenderer renderer = new LabelRenderer(this, "");
210 sam.build(renderer).end();
211 return self();
212 }
213
214 NodeRenderer label(String label) {
215 return label(label, (l) -> l);
216 }
217
218
219 public NodeRenderer color(String color) {
220 return append("color").equal().oquot().append(color).cquot().space();
221 }
222
223 public NodeRenderer style(String style) {
224 return append("style").equal().oquot().append(style).cquot().space();
225 }
226
227 public static class LabelRenderer extends CommonRenderer<LabelRenderer> {
228 int count = 0;
229
230 LabelRenderer(NodeRenderer nodeRenderer, String label) {
231 super(nodeRenderer);
232 append("label").equal().oquot().append(label);
233 }
234
235 public LabelRenderer end() {
236 return cquot().space();
237 }
238
239 LabelRenderer port(String label, String text) {
240 if (count > 0) {
241 pipe();
242 }
243 count++;
244 return lt().append(label).gt().append(text);
245 }
246
247 LabelRenderer label(String label, String text) {
248 if (count > 0) {
249 pipe();
250 }
251 count++;
252 return append(text);
253 }
254
255 LabelRenderer box(NestedRendererSAM<BoxRenderer> sam) {
256 sam.build(new BoxRenderer(this)).end();
257 count = 0;
258 return self();
259 }
260
261 static class BoxRenderer extends CommonRenderer<BoxRenderer> {
262 int count = 0;
263
264 BoxRenderer(LabelRenderer labelRenderer) {
265 super(labelRenderer);
266 pipe().obrace();
267 }
268
269 BoxRenderer(BoxRenderer boxRenderer) {
270 super(boxRenderer);
271 pipe().obrace();
272 }
273
274 BoxRenderer end() {
275 return cbrace().pipe();
276 }
277
278 BoxRenderer port(String label, String text) {
279 if (count > 0) {
280 pipe();
281 }
282 count++;
283 return lt().append(label).gt().append(text);
284 }
285
286 BoxRenderer label(String text) {
287 if (count > 0) {
288 pipe();
289 }
290 count++;
291 return append(text);
292 }
293
294 BoxRenderer box(NestedRendererSAM<BoxRenderer> sam) {
295 sam.build(new BoxRenderer(this)).end();
296 count = 0;
297 return self();
298 }
299 }
300 }
301 }
302
303 public GraphRenderer edge(String from, String to, NestedRendererSAM<EdgeRenderer> sam) {
304 sam.build(new EdgeRenderer(this, from, to)).end();
305 return self();
306 }
307
308 public GraphRenderer edge(String from, String to) {
309 return edge(from, to, (n) -> n);
310 }
311
312 public GraphRenderer edge(Object from, Object to, NestedRendererSAM<EdgeRenderer> sam) {
313 sam.build(new EdgeRenderer(this, sysident(from), sysident(to))).end();
314 return self();
315 }
316
317 public GraphRenderer edge(Object from, Object to) {
318 return edge(from, to, (n) -> n);
319 }
320
321 public static class EdgeRenderer extends CommonRenderer<EdgeRenderer> {
322 EdgeRenderer(GraphRenderer graphRenderer, String from, String to) {
323 super(graphRenderer);
324 append(from).rarrow().append(to).osbrace();
325 }
326
327 public EdgeRenderer end() {
328 return csbrace().semicolon().nl().self();
329 }
330
331 EdgeRenderer label(String label, NestedRendererSAM<LabelRenderer> sam) {
332 LabelRenderer renderer = new LabelRenderer(this, label);
333 sam.build(renderer).end();
334 return self();
335 }
336
337
338 EdgeRenderer label(String label) {
339 return label(label, (l) -> l);
340 }
341
342 public static class LabelRenderer extends CommonRenderer<LabelRenderer> {
343
344 LabelRenderer(EdgeRenderer edgeRenderer, String label) {
345 super(edgeRenderer);
346 append("label").equal().oquot().append(label);
347 }
348
349 public LabelRenderer end() {
350 return cquot().space();
351 }
352
353 }
354 }
355 }
356
357 public static void representationTree(Op op, Writer w) {
358 new DotRenderer().writer(w).start("g").graph((g) -> {
359 op.traverse(null, (t, codeElement) -> switch (codeElement) {
360 case Body b -> {
361 g.hexagon(b, (n) -> n.label("").style("filled"));
362 g.edge(b.parentOp(), b);
363 yield null;
364 }
365 case Block b -> {
366 g.box(b, (n) -> n.label(""));
367 g.edge(b.parentBody(), b);
368 yield null;
369 }
370 case Op o -> {
371 if (o instanceof Op.Terminating) {
372 g.ellipse(o, (n) -> n.label(o.opName()).style("filled"));
373 } else {
374 g.ellipse(o, (n) -> n.label(o.opName()));
375 }
376 if (o.parentBlock() != null) {
377 g.edge(o.parentBlock(), o);
378 }
379 yield null;
380 }
381 });
382 return g;
383 }).end();
384
385 }
386
387 public static void bodyGraph(Body body, Writer w) {
388 Block eb = body.entryBlock();
389 Deque<Block> stack = new ArrayDeque<>();
390 Set<Block> visited = new HashSet<>();
391 stack.push(eb);
392 new DotRenderer().writer(w).start("g").graph((g) -> {
393 while (!stack.isEmpty()) {
394 Block b = stack.pop();
395 if (!visited.add(b)) {
396 continue;
397 }
398
399 g.box(b, (box) -> box.label(""));
400
401 List<Block.Reference> successors = b.terminatingOp().successors();
402 for (Block.Reference s : successors) {
403 g.edge(b, s.targetBlock());
404
405 stack.push(s.targetBlock());
406 }
407 }
408 return g;
409 }).end();
410
411 }
412
413 public static void bodyDominatorTree(Body body, Writer w) {
414 Block eb = body.entryBlock();
415 Map<Block, Block> idoms = body.immediateDominators();
416
417 new DotRenderer().writer(w).start("g").graph((g) -> {
418 for (Map.Entry<Block, Block> e : idoms.entrySet()) {
419 Block child = e.getKey();
420 Block parent = e.getValue();
421
422 g.box(child, (b) -> b.label(""));
423
424 if (child != eb) {
425 g.edge(parent, child);
426 }
427 }
428 return g;
429 }).end();
430 }
431
432 /**
433 * Generates a body data dependence graph for a given body.
434 *
435 * @param body the body
436 * @param names a map of block arguments to names
437 * @param traverseblockArgs true if a graph is produced, otherwise a DAG
438 * @param w the writer to write the sr.dot file
439 */
440 public static void dataDependenceGraph(Body body, Map<Block.Parameter, String> names,
441 boolean traverseblockArgs, Writer w) {
442
443
444 record Edge(Value from, Value to) {
445 }
446 new DotRenderer().writer(w).start("SR").graph((g) -> {
447 Set<Value> visted = new HashSet<>();
448 Set<Edge> vistedEdges = new HashSet<>();
449 Deque<Value> stack = new ArrayDeque<>(getValues(body));
450 while (!stack.isEmpty()) {
451 Value v = stack.pop();
452 if (!visted.add(v)) {
453 continue;
454 }
455
456 if (v instanceof Op.Result or) {
457 if (!or.op().operands().isEmpty() || !(or.op() instanceof Op.Terminating)) {
458 g.invertedtrapezium(v, (node) -> node.label(or.op().opName()));
459 }
460 } else if (v instanceof Block.Parameter ba) {
461 String n = names.get(v);
462 if (n != null) {
463 g.invertedtrapezium(v, (node) -> node.label(n).style("filled"));
464 } else {
465 Block b = ba.declaringBlock();
466
467 g.box(v, (node) -> node.label("(" + b.parameters().indexOf(ba) + ")").style("filled"));
468 }
469 }
470
471 Set<Op.Result> uses = v.uses();
472 stack.addAll(uses);
473 for (Op.Result use : uses) {
474 if (traverseblockArgs && use.op() instanceof Op.Terminating) {
475 for (Block.Reference s : use.op().successors()) {
476 int i = s.arguments().indexOf(v);
477 if (i != -1) {
478 Block.Parameter ba = s.targetBlock().parameters().get(i);
479
480 if (vistedEdges.add(new Edge(v, ba))) {
481 g.edge(v, ba);
482 }
483 stack.add(ba);
484 }
485 }
486 }
487
488 if (use.op().operands().contains(v)) {
489 if (vistedEdges.add(new Edge(v, use))) {
490 g.edge(v, use);
491 }
492 }
493 }
494 }
495 return g;
496 }).end();
497 }
498
499 private static List<Value> getValues(Body r) {
500 return r.traverse(new ArrayList<>(), (values, codeElement) -> switch (codeElement) {
501 case Block b -> {
502 values.addAll(b.parameters());
503 yield values;
504 }
505 case Op op -> {
506 values.add(op.result());
507 yield values;
508 }
509 default -> values;
510 });
511 }
512 }