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