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.Block;
29 import jdk.incubator.code.Op;
30 import jdk.incubator.code.Body;
31 import jdk.incubator.code.Value;
32
33 import java.io.IOException;
34 import java.io.UncheckedIOException;
35 import java.io.Writer;
36 import java.util.ArrayDeque;
37 import java.util.ArrayList;
38 import java.util.Deque;
39 import java.util.HashSet;
40 import java.util.List;
41 import java.util.Map;
42 import java.util.Set;
43 import java.util.stream.Collectors;
44
45 public class DotGenerator {
46
47 final Writer w;
48
49 interface NodeProperty {
50 String key();
51
52 String value();
53
54 default String toText() {
55 return key() + "=" + value();
56 }
57 }
58
59 static NodeProperty property(String key, String value) {
60 return new NodeProperty() {
61 @Override
62 public String key() {
63 return key;
64 }
65
66 @Override
67 public String value() {
68 return value;
69 }
70 };
71 }
72
73 static String properties(List<? extends NodeProperty> properties) {
74 return properties.stream().map(NodeProperty::toText).collect(Collectors.joining(" ", "[", "]"));
75 }
76
77 static NodeProperty label(String name) {
78 return new NodeProperty() {
79 @Override
80 public String key() {
81 return "label";
82 }
83
84 @Override
85 public String value() {
86 return "\"" + name + "\"";
87 }
88 };
89 }
90
91 enum Shape implements NodeProperty {
92 BOX("box"),
93 ELLIPSE("ellipse"),
94 HEXAGONE("hexagon"),
95 INVERTED_TRAPEZIUM("invtrapezium");
96
97 final String value;
98
99 Shape(String value) {
100 this.value = value;
101 }
102
103
104 @Override
105 public String key() {
106 return "shape";
107 }
108
109 @Override
110 public String value() {
111 return value;
112 }
113 }
114
115 private DotGenerator(Writer w) {
116 this.w = w;
117 }
118
119 void digraph() {
120 write("digraph G {\n");
121 }
122
123 void node(Object o, String properties) {
124 write("%s %s;\n", System.identityHashCode(o), properties);
125 }
126
127 void node(Object o, NodeProperty... properties) {
128 node(o, List.of(properties));
129 }
130
131 void node(Object o, List<? extends NodeProperty> properties) {
132 node(o, properties(properties));
133 }
134
135 void edge(Object from, Object to) {
136 write("%s -> %s;\n", System.identityHashCode(from), System.identityHashCode(to));
137 }
138
139 void write(String format, Object... args) {
140 write(w, format, args);
141 }
142
143 void end() {
144 write(w, "}\n");
145 try {
146 w.flush();
147 } catch (IOException e) {
148 throw new UncheckedIOException(e);
149 }
150 }
151
152 static void write(Writer w, String format, Object... args) {
153 try {
154 w.write(String.format(format, args));
155 } catch (IOException e) {
156 throw new UncheckedIOException(e);
157 }
158 }
159
160
161 /**
162 * Generates the representation tree for a given operation.
163 *
164 * @param op the operation
165 * @param w the writer to write the sr.dot file
166 */
167 public static void representationTree(Op op, Writer w) {
168 DotGenerator dg = new DotGenerator(w);
169
170 dg.digraph();
171
172 op.traverse(null, (t, codeElement) -> switch (codeElement) {
173 case Body b -> {
174 dg.node(b, label(""), Shape.HEXAGONE, property("style", "filled"));
175
176 dg.edge(b.parentOp(), b);
177
178 yield null;
179 }
180 case Block b -> {
181 dg.node(b, label(""), Shape.BOX);
182
183 dg.edge(b.parentBody(), b);
184
185 yield null;
186 }
187 case Op o -> {
188 List<NodeProperty> ps;
189 if (o instanceof Op.Terminating) {
190 ps = List.of(label(o.opName()), Shape.ELLIPSE, property("style", "filled"));
191 } else {
192 ps = List.of(label(o.opName()), Shape.ELLIPSE);
193 }
194 dg.node(o, ps);
195 if (o.parentBlock() != null) {
196 dg.edge(o.parentBlock(), o);
197 }
198
199 yield null;
200 }
201 });
202
203 dg.end();
204 }
205
206 /**
207 * Generates a body graph (CFG) for a given body.
208 *
209 * @param body the body
210 * @param w the writer to write the sr.dot file
211 */
212 public static void bodyGraph(Body body, Writer w) {
213 DotGenerator dg = new DotGenerator(w);
214
215 dg.digraph();
216
217 Block eb = body.entryBlock();
218 Deque<Block> stack = new ArrayDeque<>();
219 Set<Block> visited = new HashSet<>();
220 stack.push(eb);
221 while (!stack.isEmpty()) {
222 Block b = stack.pop();
223 if (!visited.add(b)) {
224 continue;
225 }
226
227 dg.node(b, label(""), Shape.BOX);
228
229 List<Block.Reference> successors = b.terminatingOp().successors();
230 for (Block.Reference s : successors) {
231 dg.edge(b, s.targetBlock());
232
233 stack.push(s.targetBlock());
234 }
235 }
236
237 dg.end();
238 }
239
240 /**
241 * Generates a body dominator tree for a given body.
242 *
243 * @param body the body
244 * @param w the writer to write the sr.dot file
245 */
246 public static void bodyDominatorTree(Body body, Writer w) {
247 DotGenerator dg = new DotGenerator(w);
248
249 dg.digraph();
250
251 Block eb = body.entryBlock();
252 Map<Block, Block> idoms = body.immediateDominators();
253
254 for (Map.Entry<Block, Block> e : idoms.entrySet()) {
255 Block child = e.getKey();
256 Block parent = e.getValue();
257
258 dg.node(child, label(""), Shape.BOX);
259
260 if (child != eb) {
261 dg.edge(parent, child);
262 }
263 }
264
265 dg.end();
266 }
267
268 /**
269 * Generates a body dominator tree for a given body, with the dominance
270 * frontier set presented for each block.
271 * <p>
272 * The dominance frontier of a block, b say, is the set of blocks where the b's
273 * dominance stops.
274 *
275 * @param body the body
276 * @param w the writer to write the sr.dot file
277 */
278 public static void bodyDominanceFrontierTree(Body body, Writer w) {
279 DotGenerator dg = new DotGenerator(w);
280
281 dg.digraph();
282
283 Block eb = body.entryBlock();
284 Map<Block, Block> idoms = body.immediateDominators();
285 Map<Block, Set<Block>> df = body.dominanceFrontier();
286
287 for (Map.Entry<Block, Block> e : idoms.entrySet()) {
288 Block child = e.getKey();
289 Block parent = e.getValue();
290
291 Set<Block> frontiers = df.get(child);
292
293 String s = frontiers == null || frontiers.isEmpty()
294 ? "[-]"
295 : frontiers.stream().map(b -> String.valueOf(b.index())).collect(Collectors.joining(",", "[", "]"));
296 dg.node(child, label("" + "\n" + s), Shape.BOX);
297
298 if (child != eb) {
299 dg.edge(parent, child);
300 }
301 }
302
303 dg.end();
304 }
305
306 /**
307 * Generates a body data dependence dag for a given body.
308 *
309 * @param body the body
310 * @param names a map of block arguments to names
311 * @param w the writer to write the sr.dot file
312 */
313 public static void dataDependenceGraph(Body body, Map<Block.Parameter, String> names, Writer w) {
314 dataDependenceGraph(body, names, false, w);
315 }
316
317 /**
318 * Generates a body data dependence graph for a given body.
319 *
320 * @param body the body
321 * @param names a map of block arguments to names
322 * @param traverseblockArgs true if a graph is produced, otherwise a DAG
323 * @param w the writer to write the sr.dot file
324 */
325 public static void dataDependenceGraph(Body body, Map<Block.Parameter, String> names,
326 boolean traverseblockArgs, Writer w) {
327 DotGenerator dg = new DotGenerator(w);
328
329 dg.digraph();
330
331 record Edge(Value from, Value to) {
332 }
333
334 Set<Value> visted = new HashSet<>();
335 Set<Edge> vistedEdges = new HashSet<>();
336 Deque<Value> stack = new ArrayDeque<>(getValues(body));
337 while (!stack.isEmpty()) {
338 Value v = stack.pop();
339 if (!visted.add(v)) {
340 continue;
341 }
342
343 if (v instanceof Op.Result or) {
344 if (!or.op().operands().isEmpty() || !(or.op() instanceof Op.Terminating)) {
345 dg.node(v, label(or.op().opName()), Shape.INVERTED_TRAPEZIUM);
346 }
347 } else if (v instanceof Block.Parameter ba) {
348 String n = names.get(v);
349 if (n != null) {
350 dg.node(v, label(n), Shape.INVERTED_TRAPEZIUM,
351 property("style", "filled"));
352 } else {
353 Block b = ba.declaringBlock();
354 dg.node(v, label("(" + b.parameters().indexOf(ba) + ")"), Shape.BOX,
355 property("style", "filled"));
356 }
357 }
358
359 Set<Op.Result> uses = v.uses();
360 stack.addAll(uses);
361 for (Op.Result use : uses) {
362 if (traverseblockArgs && use.op() instanceof Op.Terminating) {
363 for (Block.Reference s : use.op().successors()) {
364 int i = s.arguments().indexOf(v);
365 if (i != -1) {
366 Block.Parameter ba = s.targetBlock().parameters().get(i);
367
368 if (vistedEdges.add(new Edge(v, ba))) {
369 dg.edge(v, ba);
370 }
371 stack.add(ba);
372 }
373 }
374 }
375
376 if (use.op().operands().contains(v)) {
377 if (vistedEdges.add(new Edge(v, use))) {
378 dg.edge(v, use);
379 }
380 }
381 }
382 }
383
384 dg.end();
385 }
386
387 static List<Value> getValues(Body r) {
388 return r.traverse(new ArrayList<>(), (values, codeElement) -> switch (codeElement) {
389 case Block b -> {
390 values.addAll(b.parameters());
391 yield values;
392 }
393 case Op o -> {
394 values.add(o.result());
395 yield values;
396 }
397 default -> values;
398 });
399 }
400
401 }