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 org.testng.Assert;
25 import org.testng.annotations.Test;
26
27 import jdk.incubator.code.Block;
28 import jdk.incubator.code.op.CoreOp;
29 import jdk.incubator.code.Op;
30 import jdk.incubator.code.type.FunctionType;
31 import jdk.incubator.code.type.JavaType;
32 import java.util.HashMap;
33 import java.util.HashSet;
34 import java.util.Map;
35 import java.util.Set;
36 import java.util.function.Function;
37 import java.util.stream.Collectors;
38
39 import static jdk.incubator.code.op.CoreOp._return;
40 import static jdk.incubator.code.op.CoreOp.branch;
41 import static jdk.incubator.code.op.CoreOp.conditionalBranch;
42 import static jdk.incubator.code.op.CoreOp.constant;
43 import static jdk.incubator.code.op.CoreOp.func;
44
45 /*
46 * @test
47 * @modules jdk.incubator.code
48 * @run testng TestDominate
49 */
50
51 public class TestDominate {
52
53 public void testUnmodifiableIdoms() {
54 CoreOp.FuncOp f = func("f", FunctionType.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(_return());
67 });
68
69 Map<Block, Block> idoms = f.body().immediateDominators();
70 Assert.assertThrows(UnsupportedOperationException.class,
71 () -> idoms.put(f.body().entryBlock(), f.body().entryBlock()));
72 Assert.assertThrows(UnsupportedOperationException.class,
73 idoms::clear);
74 }
75
76 @Test
77 public void testIfElse() {
78 CoreOp.FuncOp f = func("f", FunctionType.VOID).body(entry -> {
79 Block.Builder ifBlock = entry.block();
80 Block.Builder elseBlock = entry.block();
81 Block.Builder end = entry.block();
82
83 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
84 entry.op(conditionalBranch(p, ifBlock.successor(), elseBlock.successor()));
85
86 ifBlock.op(branch(end.successor()));
87
88 elseBlock.op(branch(end.successor()));
89
90 end.op(_return());
91 });
92
93 boolean[][] bvs = new boolean[][]{
94 {true, false, false, false},
95 {true, true, false, false},
96 {true, false, true, false},
97 {true, false, false, true}
98 };
99
100 test(f, bvs);
101 }
102
103 @Test
104 public void testForwardSuccessors() {
105 CoreOp.FuncOp f = func("f", FunctionType.VOID).body(entry -> {
106 Block.Builder b1 = entry.block();
107 Block.Builder b2 = entry.block();
108 Block.Builder b3 = entry.block();
109 Block.Builder b4 = entry.block();
110 Block.Builder b5 = entry.block();
111
112 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
113 entry.op(conditionalBranch(p, b4.successor(), b2.successor()));
114
115 b4.op(conditionalBranch(p, b5.successor(), b3.successor()));
116
117 b2.op(conditionalBranch(p, b5.successor(), b1.successor()));
118
119 b5.op(_return());
120
121 b3.op(branch(b1.successor()));
122
123 b1.op(_return());
124 });
125
126 f.writeTo(System.out);
127 boolean[][] bvs = new boolean[][]{
128 {true, false, false, false, false, false},
129 {true, true, false, false, false, false},
130 {true, true, true, false, false, false},
131 {true, false, false, true, false, false},
132 {true, false, false, false, true, false},
133 {true, false, false, false, false, true},
134 };
135
136 test(f, bvs);
137 }
138
139 @Test
140 public void testBackbranch() {
141 CoreOp.FuncOp f = func("f", FunctionType.VOID).body(entry -> {
142 Block.Builder cond = entry.block();
143 Block.Builder body = entry.block();
144 Block.Builder update = entry.block();
145 Block.Builder end = entry.block();
146
147 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
148 entry.op(branch(cond.successor()));
149
150 cond.op(conditionalBranch(p, body.successor(), end.successor()));
151
152 body.op(branch(update.successor()));
153
154 update.op(branch(cond.successor()));
155
156 end.op(_return());
157
158 });
159
160 boolean[][] bvs = new boolean[][]{
161 {true, false, false, false, false},
162 {true, true, false, false, false},
163 {true, true, true, false, false},
164 {true, true, true, true, false},
165 {true, true, false, false, true},
166 };
167 test(f, bvs);
168 }
169
170 static void test(CoreOp.FuncOp f, boolean[][] bvs) {
171 Block[] bs = f.body().blocks().toArray(Block[]::new);
172 for (int i = 0; i < bs.length; i++) {
173 for (int j = 0; j < bs.length; j++) {
174 Block x = bs[i];
175 Block y = bs[j];
176 Assert.assertEquals(y.isDominatedBy(x), bvs[j][i]);
177 }
178 }
179 }
180
181
182 @Test
183 public void testImmediateDominators() {
184 CoreOp.FuncOp f = func("f", FunctionType.VOID).body(entry -> {
185 Block.Builder b6 = entry.block();
186 Block.Builder b5 = entry.block();
187 Block.Builder b4 = entry.block();
188 Block.Builder b3 = entry.block();
189 Block.Builder b2 = entry.block();
190 Block.Builder b1 = entry.block();
191
192 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
193 entry.op(branch(b6.successor()));
194
195 b6.op(conditionalBranch(p, b5.successor(), b4.successor()));
196
197 b5.op(branch(b1.successor()));
198
199 b4.op(conditionalBranch(p, b2.successor(), b3.successor()));
200
201 b1.op(branch(b2.successor()));
202
203 b2.op(conditionalBranch(p, b1.successor(), b3.successor()));
204
205 b3.op(branch(b2.successor()));
206 });
207 f.writeTo(System.out);
208 Map<Block, Block> idoms = f.body().immediateDominators();
209 System.out.println(idoms);
210
211 Block entry = f.body().entryBlock();
212 Block b6 = entry.successors().get(0).targetBlock();
213
214 for (Block b : f.body().blocks()) {
215 if (b == entry || b == b6) {
216 Assert.assertEquals(idoms.get(b), entry);
217 } else {
218 Assert.assertEquals(idoms.get(b), b6);
219 }
220 }
221 }
222
223 @Test
224 public void testCytronExample() {
225 CoreOp.FuncOp f = func("f", FunctionType.VOID).body(entry -> {
226 Block.Builder exit = entry.block();
227 Block.Builder b12 = entry.block();
228 Block.Builder b11 = entry.block();
229 Block.Builder b10 = entry.block();
230 Block.Builder b9 = entry.block();
231 Block.Builder b8 = entry.block();
232 Block.Builder b7 = entry.block();
233 Block.Builder b6 = entry.block();
234 Block.Builder b5 = entry.block();
235 Block.Builder b4 = entry.block();
236 Block.Builder b3 = entry.block();
237 Block.Builder b2 = entry.block();
238 Block.Builder b1 = entry.block();
239
240 Op.Result p = entry.op(constant(JavaType.BOOLEAN, true));
241
242 entry.op(conditionalBranch(p, exit.successor(), b1.successor()));
243
244 b1.op(branch(b2.successor()));
245
246 b2.op(conditionalBranch(p, b3.successor(), b7.successor()));
247
248 b3.op(conditionalBranch(p, b4.successor(), b5.successor()));
249
250 b4.op(branch(b6.successor()));
251
252 b5.op(branch(b6.successor()));
253
254 b6.op(branch(b8.successor()));
255
256 b7.op(branch(b8.successor()));
257
258 b8.op(branch(b9.successor()));
259
260 b9.op(conditionalBranch(p, b10.successor(), b11.successor()));
261
262 b10.op(branch(b11.successor()));
263
264 b11.op(conditionalBranch(p, b12.successor(), b9.successor()));
265
266 b12.op(conditionalBranch(p, exit.successor(), b2.successor()));
267
268 exit.op(_return());
269 });
270
271 f.writeTo(System.out);
272
273 Map<Block, Block> idoms = f.body().immediateDominators();
274 Node<String> domTree = buildDomTree(f.body().entryBlock(), idoms).transform(b -> Integer.toString(b.index()));
275 Node<String> domTreeExpected =
276 node("0",
277 node("1",
278 node("2",
279 node("7"),
280 node("8",
281 node("9",
282 node("10"),
283 node("11",
284 node("12")))),
285 node("3",
286 node("4"), node("5"), node("6")))),
287 node("13"));
288 Assert.assertEquals(domTree, domTreeExpected);
289
290
291 Map<String, Set<String>> df = f.body().dominanceFrontier().entrySet().stream()
292 .map(e -> Map.entry(Integer.toString(e.getKey().index()),
293 e.getValue().stream().map(b -> Integer.toString(b.index())).collect(Collectors.toSet())))
294 .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
295
296 Map<String, Set<String>> dfExpected = Map.ofEntries(
297 Map.entry("1", Set.of("13")),
298 Map.entry("2", Set.of("13", "2")),
299 Map.entry("3", Set.of("8")),
300 Map.entry("4", Set.of("6")),
301 Map.entry("5", Set.of("6")),
302 Map.entry("6", Set.of("8")),
303 Map.entry("7", Set.of("8")),
304 Map.entry("8", Set.of("13", "2")),
305 Map.entry("9", Set.of("13", "2", "9")),
306 Map.entry("10", Set.of("11")),
307 Map.entry("11", Set.of("13", "2", "9")),
308 Map.entry("12", Set.of("13", "2"))
309 );
310 Assert.assertEquals(df, dfExpected);
311 }
312
313 static Node<Block> buildDomTree(Block entryBlock, Map<Block, Block> idoms) {
314 Map<Block, Node<Block>> m = new HashMap<>();
315 for (Map.Entry<Block, Block> e : idoms.entrySet()) {
316 Block id = e.getValue();
317 Block b = e.getKey();
318 if (b == entryBlock) {
319 continue;
320 }
321
322 Node<Block> parent = m.computeIfAbsent(id, _k -> new Node<>(_k, new HashSet<>()));
323 Node<Block> child = m.computeIfAbsent(b, _k -> new Node<>(_k, new HashSet<>()));
324 parent.children.add(child);
325 }
326 return m.get(entryBlock);
327 }
328
329 @SafeVarargs
330 static <T> Node<T> node(T t, Node<T>... children) {
331 return new Node<>(t, Set.of(children));
332 }
333
334 static <T> Node<T> node(T t, Set<Node<T>> children) {
335 return new Node<>(t, children);
336 }
337
338 record Node<T>(T t, Set<Node<T>> children) {
339 <U> Node<U> transform(Function<T, U> f) {
340 Set<Node<U>> mchildren = new HashSet<>();
341 for (Node<T> nc : children) {
342 mchildren.add(nc.transform(f));
343 }
344 return node(f.apply(t), mchildren);
345 }
346 }
347 }