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.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 import jdk.incubator.code.Block;
25 import jdk.incubator.code.Body;
26 import jdk.incubator.code.Op;
27 import jdk.incubator.code.dialect.core.CoreOp;
28 import jdk.incubator.code.dialect.core.CoreType;
29 import jdk.incubator.code.dialect.java.JavaOp;
30 import jdk.incubator.code.dialect.java.JavaType;
31 import jdk.incubator.code.extern.OpParser;
32 import org.junit.jupiter.api.Assertions;
33 import org.junit.jupiter.api.Test;
34
35 import java.util.HashMap;
36 import java.util.HashSet;
37 import java.util.Map;
38 import java.util.Set;
39 import java.util.function.Function;
40 import java.util.stream.Collectors;
41
42 import static jdk.incubator.code.dialect.core.CoreOp.*;
43
44 /*
45 * @test
46 * @modules jdk.incubator.code
47 * @run junit TestDominate
48 */
49
50 public class TestDominate {
51
52 @Test
53 public void testUnmodifiableIdoms() {
54 CoreOp.FuncOp f = func("f", CoreType.FUNCTION_TYPE_VOID).body(entry -> {
55 Block.Builder ifBlock = entry.block();
56 Block.Builder elseBlock = entry.block();
57 Block.Builder end = entry.block();
58
59 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
60 entry.op(conditionalBranch(p, ifBlock.successor(), elseBlock.successor()));
61
62 ifBlock.op(branch(end.successor()));
63
64 elseBlock.op(branch(end.successor()));
65
66 end.op(CoreOp.return_());
67 });
68
69 Map<Block, Block> idoms = f.body().immediateDominators();
70 Assertions.assertThrows(UnsupportedOperationException.class,
71 () -> idoms.put(f.body().entryBlock(), f.body().entryBlock()));
72 Assertions.assertThrows(UnsupportedOperationException.class,
73 idoms::clear);
74
75 Map<Block, Block> ipdoms = f.body().immediatePostDominators();
76 Assertions.assertThrows(UnsupportedOperationException.class,
77 () -> ipdoms.put(f.body().entryBlock(), f.body().entryBlock()));
78 Assertions.assertThrows(UnsupportedOperationException.class,
79 ipdoms::clear);
80 }
81
82 @Test
83 public void testIfElse() {
84 CoreOp.FuncOp f = func("f", CoreType.FUNCTION_TYPE_VOID).body(entry -> {
85 Block.Builder ifBlock = entry.block();
86 Block.Builder elseBlock = entry.block();
87 Block.Builder end = entry.block();
88
89 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
90 entry.op(conditionalBranch(p, ifBlock.successor(), elseBlock.successor()));
91
92 ifBlock.op(branch(end.successor()));
93
94 elseBlock.op(branch(end.successor()));
95
96 end.op(CoreOp.return_());
97 });
98
99 boolean[][] bvs = new boolean[][]{
100 {true, false, false, false},
101 {true, true, false, false},
102 {true, false, true, false},
103 {true, false, false, true}
104 };
105
106 test(f, bvs);
107 }
108
109 @Test
110 public void testForwardSuccessors() {
111 CoreOp.FuncOp f = func("f", CoreType.FUNCTION_TYPE_VOID).body(entry -> {
112 Block.Builder b1 = entry.block();
113 Block.Builder b2 = entry.block();
114 Block.Builder b3 = entry.block();
115 Block.Builder b4 = entry.block();
116 Block.Builder b5 = entry.block();
117
118 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
119 entry.op(conditionalBranch(p, b4.successor(), b2.successor()));
120
121 b4.op(conditionalBranch(p, b5.successor(), b3.successor()));
122
123 b2.op(conditionalBranch(p, b5.successor(), b1.successor()));
124
125 b5.op(CoreOp.return_());
126
127 b3.op(branch(b1.successor()));
128
129 b1.op(CoreOp.return_());
130 });
131
132 System.out.println(f.toText());
133 boolean[][] bvs = new boolean[][]{
134 {true, false, false, false, false, false},
135 {true, true, false, false, false, false},
136 {true, true, true, false, false, false},
137 {true, false, false, true, false, false},
138 {true, false, false, false, true, false},
139 {true, false, false, false, false, true},
140 };
141
142 test(f, bvs);
143 }
144
145 @Test
146 public void testBackbranch() {
147 CoreOp.FuncOp f = func("f", CoreType.FUNCTION_TYPE_VOID).body(entry -> {
148 Block.Builder cond = entry.block();
149 Block.Builder body = entry.block();
150 Block.Builder update = entry.block();
151 Block.Builder end = entry.block();
152
153 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
154 entry.op(branch(cond.successor()));
155
156 cond.op(conditionalBranch(p, body.successor(), end.successor()));
157
158 body.op(branch(update.successor()));
159
160 update.op(branch(cond.successor()));
161
162 end.op(CoreOp.return_());
163
164 });
165
166 boolean[][] bvs = new boolean[][]{
167 {true, false, false, false, false},
168 {true, true, false, false, false},
169 {true, true, true, false, false},
170 {true, true, true, true, false},
171 {true, true, false, false, true},
172 };
173 test(f, bvs);
174 }
175
176 static void test(CoreOp.FuncOp f, boolean[][] bvs) {
177 Block[] bs = f.body().blocks().toArray(Block[]::new);
178 for (int i = 0; i < bs.length; i++) {
179 for (int j = 0; j < bs.length; j++) {
180 Block x = bs[i];
181 Block y = bs[j];
182 Assertions.assertEquals(bvs[j][i], y.isDominatedBy(x));
183 }
184 }
185 }
186
187
188 @Test
189 public void testImmediateDominators() {
190 CoreOp.FuncOp f = func("f", CoreType.FUNCTION_TYPE_VOID).body(entry -> {
191 Block.Builder b6 = entry.block();
192 Block.Builder b5 = entry.block();
193 Block.Builder b4 = entry.block();
194 Block.Builder b3 = entry.block();
195 Block.Builder b2 = entry.block();
196 Block.Builder b1 = entry.block();
197
198 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
199 entry.op(branch(b6.successor()));
200
201 b6.op(conditionalBranch(p, b5.successor(), b4.successor()));
202
203 b5.op(branch(b1.successor()));
204
205 b4.op(conditionalBranch(p, b2.successor(), b3.successor()));
206
207 b1.op(branch(b2.successor()));
208
209 b2.op(conditionalBranch(p, b1.successor(), b3.successor()));
210
211 b3.op(branch(b2.successor()));
212 });
213 System.out.println(f.toText());
214 Map<Block, Block> idoms = f.body().immediateDominators();
215 System.out.println(idoms);
216
217 Block entry = f.body().entryBlock();
218 Block b6 = entry.successors().get(0).targetBlock();
219
220 for (Block b : f.body().blocks()) {
221 if (b == entry || b == b6) {
222 Assertions.assertEquals(entry, idoms.get(b));
223 } else {
224 Assertions.assertEquals(b6, idoms.get(b));
225 }
226 }
227 }
228
229 @Test
230 public void testCytronExample() {
231 CoreOp.FuncOp f = func("f", CoreType.FUNCTION_TYPE_VOID).body(entry -> {
232 Block.Builder exit = entry.block();
233 Block.Builder b12 = entry.block();
234 Block.Builder b11 = entry.block();
235 Block.Builder b10 = entry.block();
236 Block.Builder b9 = entry.block();
237 Block.Builder b8 = entry.block();
238 Block.Builder b7 = entry.block();
239 Block.Builder b6 = entry.block();
240 Block.Builder b5 = entry.block();
241 Block.Builder b4 = entry.block();
242 Block.Builder b3 = entry.block();
243 Block.Builder b2 = entry.block();
244 Block.Builder b1 = entry.block();
245
246 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
247
248 entry.op(conditionalBranch(p, exit.successor(), b1.successor()));
249
250 b1.op(branch(b2.successor()));
251
252 b2.op(conditionalBranch(p, b3.successor(), b7.successor()));
253
254 b3.op(conditionalBranch(p, b4.successor(), b5.successor()));
255
256 b4.op(branch(b6.successor()));
257
258 b5.op(branch(b6.successor()));
259
260 b6.op(branch(b8.successor()));
261
262 b7.op(branch(b8.successor()));
263
264 b8.op(branch(b9.successor()));
265
266 b9.op(conditionalBranch(p, b10.successor(), b11.successor()));
267
268 b10.op(branch(b11.successor()));
269
270 b11.op(conditionalBranch(p, b12.successor(), b9.successor()));
271
272 b12.op(conditionalBranch(p, exit.successor(), b2.successor()));
273
274 exit.op(CoreOp.return_());
275 });
276
277 System.out.println(f.toText());
278
279 Map<Block, Block> idoms = f.body().immediateDominators();
280 Node<String> domTree = buildDomTree(f.body().entryBlock(), idoms).transform(b -> Integer.toString(b.index()));
281 Node<String> domTreeExpected =
282 node("0",
283 node("1",
284 node("2",
285 node("7"),
286 node("8",
287 node("9",
288 node("10"),
289 node("11",
290 node("12")))),
291 node("3",
292 node("4"), node("5"), node("6")))),
293 node("13"));
294 Assertions.assertEquals(domTreeExpected, domTree);
295
296
297 Map<String, Set<String>> df = f.body().dominanceFrontier().entrySet().stream()
298 .map(e -> Map.entry(Integer.toString(e.getKey().index()),
299 e.getValue().stream().map(b -> Integer.toString(b.index())).collect(Collectors.toSet())))
300 .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
301
302 Map<String, Set<String>> dfExpected = Map.ofEntries(
303 Map.entry("1", Set.of("13")),
304 Map.entry("2", Set.of("13", "2")),
305 Map.entry("3", Set.of("8")),
306 Map.entry("4", Set.of("6")),
307 Map.entry("5", Set.of("6")),
308 Map.entry("6", Set.of("8")),
309 Map.entry("7", Set.of("8")),
310 Map.entry("8", Set.of("13", "2")),
311 Map.entry("9", Set.of("13", "2", "9")),
312 Map.entry("10", Set.of("11")),
313 Map.entry("11", Set.of("13", "2", "9")),
314 Map.entry("12", Set.of("13", "2"))
315 );
316 Assertions.assertEquals(dfExpected, df);
317 }
318
319 @Test
320 public void testPostDominance() {
321 String m = """
322 func @"f" (%0 : java.type:"boolean")java.type:"void" -> {
323 %5 : java.type:"void" = branch ^A;
324
325 ^A:
326 %8 : java.type:"void" = cbranch %0 ^B ^C;
327
328 ^B:
329 %11 : java.type:"void" = branch ^D;
330
331 ^C:
332 %13 : java.type:"void" = branch ^D;
333
334 ^D:
335 %15 : java.type:"void" = branch ^E;
336
337 ^E:
338 %15 : java.type:"void" = branch ^F;
339
340 ^F:
341 %16 : java.type:"void" = cbranch %0 ^E ^END;
342
343 ^END:
344 %18 : java.type:"void" = return;
345 };
346 """;
347 CoreOp.FuncOp f = (CoreOp.FuncOp) OpParser.fromText(JavaOp.JAVA_DIALECT_FACTORY, m).get(0);
348
349 Map<Block, Block> ipdoms = f.body().immediatePostDominators();
350 Assertions.assertFalse(ipdoms.containsKey(Body.IPDOM_EXIT));
351
352 Block exit = ipdoms.containsKey(Body.IPDOM_EXIT) ? Body.IPDOM_EXIT : f.body().blocks().getLast();
353 Node<String> domTree = buildDomTree(exit, ipdoms).transform(b -> Integer.toString(b.index()));
354 Node<String> domTreeExpected =
355 node("7",
356 node("6",
357 node("5",
358 node("4",
359 node("2"),
360 node("3"),
361 node("1",
362 node("0"))))));
363 Assertions.assertEquals(domTreeExpected, domTree);
364 }
365
366 @Test
367 public void testPostDominanceFrontier() {
368 String m = """
369 func @"f" (%0 : java.type:"boolean")java.type:"void" -> {
370 %5 : java.type:"void" = cbranch %0 ^B ^F;
371
372 ^B:
373 %8 : java.type:"void" = cbranch %0 ^C ^D;
374
375 ^C:
376 %11 : java.type:"void" = branch ^E;
377
378 ^D:
379 %13 : java.type:"void" = branch ^E;
380
381 ^E:
382 %15 : java.type:"void" = branch ^F;
383
384 ^F:
385 %18 : java.type:"void" = return;
386 };
387 """;
388 CoreOp.FuncOp f = (CoreOp.FuncOp) OpParser.fromText(JavaOp.JAVA_DIALECT_FACTORY, m).get(0);
389
390 Map<Block, Block> ipdoms = f.body().immediatePostDominators();
391 Assertions.assertFalse(ipdoms.containsKey(Body.IPDOM_EXIT));
392
393 Block exit = ipdoms.containsKey(Body.IPDOM_EXIT) ? Body.IPDOM_EXIT : f.body().blocks().getLast();
394 Node<String> domTree = buildDomTree(exit, ipdoms).transform(b -> Integer.toString(b.index()));
395 Node<String> domTreeExpected =
396 node("5",
397 node("4",
398 node("1"),
399 node("2"),
400 node("3")),
401 node("0"));
402 Assertions.assertEquals(domTreeExpected, domTree);
403
404 Map<String, Set<String>> df = f.body().postDominanceFrontier().entrySet().stream()
405 .map(e -> Map.entry(Integer.toString(e.getKey().index()),
406 e.getValue().stream().map(b -> Integer.toString(b.index())).collect(Collectors.toSet())))
407 .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
408
409 Map<String, Set<String>> dfExpected = Map.ofEntries(
410 Map.entry("1", Set.of("0")),
411 Map.entry("2", Set.of("1")),
412 Map.entry("3", Set.of("1")),
413 Map.entry("4", Set.of("0"))
414 );
415 Assertions.assertEquals(dfExpected, df);
416 }
417
418
419 static Node<Block> buildDomTree(Block entryBlock, Map<Block, Block> idoms) {
420 Map<Block, Node<Block>> m = new HashMap<>();
421 for (Map.Entry<Block, Block> e : idoms.entrySet()) {
422 Block id = e.getValue();
423 Block b = e.getKey();
424 if (b == entryBlock) {
425 continue;
426 }
427
428 Node<Block> parent = m.computeIfAbsent(id, _k -> new Node<>(_k, new HashSet<>()));
429 Node<Block> child = m.computeIfAbsent(b, _k -> new Node<>(_k, new HashSet<>()));
430 parent.children.add(child);
431 }
432 return m.get(entryBlock);
433 }
434
435 @SafeVarargs
436 static <T> Node<T> node(T t, Node<T>... children) {
437 return new Node<>(t, Set.of(children));
438 }
439
440 static <T> Node<T> node(T t, Set<Node<T>> children) {
441 return new Node<>(t, children);
442 }
443
444 record Node<T>(T t, Set<Node<T>> children) {
445 <U> Node<U> transform(Function<T, U> f) {
446 Set<Node<U>> mchildren = new HashSet<>();
447 for (Node<T> nc : children) {
448 mchildren.add(nc.transform(f));
449 }
450 return node(f.apply(t), mchildren);
451 }
452 }
453 }