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