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