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