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 /*
25 * @test
26 * @run testng TestLiveness
27 */
28
29 import org.testng.Assert;
30 import org.testng.annotations.Test;
31
32 import java.lang.reflect.code.Block;
33 import java.lang.reflect.code.CodeElement;
34 import java.lang.reflect.code.Op;
35 import java.lang.reflect.code.Value;
36 import java.lang.reflect.code.analysis.Liveness;
37 import java.lang.reflect.code.op.CoreOp;
38 import java.lang.reflect.code.type.JavaType;
39 import java.lang.reflect.code.parser.OpParser;
40 import java.util.HashMap;
41 import java.util.List;
42 import java.util.Map;
43 import java.util.Set;
44 import java.util.concurrent.atomic.AtomicInteger;
45 import java.util.stream.Collectors;
46
47 public class TestLiveness {
48
49 static final String F = """
50 func @"f" (%0 : int, %1 : int)int -> {
51 %2 : int = add %0 %1;
52 return %2;
53 };
54 """;
55
56 @Test
57 public void testF() {
58 Op op = OpParser.fromString(CoreOp.FACTORY, F).getFirst();
59
60 var actual = liveness(op);
61 var expected = Map.of(
62 0, List.of(Set.of(), Set.of()));
63 Assert.assertEquals(actual, expected);
64 }
65
66 static final String IF_ELSE = """
67 func @"ifelse" (%0 : int, %1 : int, %2 : int)int -> {
68 %3 : int = constant @"10";
69 %4 : boolean = lt %2 %3;
70 cbranch %4 ^block_0 ^block_1;
71
72 ^block_0:
73 %5 : int = constant @"1";
74 %6 : int = add %0 %5;
75 branch ^block_2(%6, %1);
76
77 ^block_1:
78 %7 : int = constant @"2";
79 %8 : int = add %1 %7;
80 branch ^block_2(%0, %8);
81
82 ^block_2(%9 : int, %10 : int):
83 %11 : int = add %9 %10;
84 return %11;
85 };
86 """;
87
88 @Test
89 public void testIfElse() {
90 Op op = OpParser.fromString(CoreOp.FACTORY, IF_ELSE).getFirst();
91
92 var actual = liveness(op);
93 var expected = Map.of(
94 0, List.of(Set.of(), Set.of(0, 1)),
95 1, List.of(Set.of(0, 1), Set.of()),
96 2, List.of(Set.of(0, 1), Set.of()),
97 3, List.of(Set.of(), Set.of())
98 );
99 Assert.assertEquals(actual, expected);
100 }
101
102 static final String LOOP = """
103 func @"loop" (%0 : int)int -> {
104 %1 : int = constant @"0";
105 %2 : int = constant @"0";
106 branch ^block_0(%1, %2);
107
108 ^block_0(%3 : int, %4 : int):
109 %5 : boolean = lt %4 %0;
110 cbranch %5 ^block_1 ^block_2;
111
112 ^block_1:
113 %6 : int = add %3 %4;
114 branch ^block_3;
115
116 ^block_3:
117 %7 : int = constant @"1";
118 %8 : int = add %4 %7;
119 branch ^block_0(%6, %8);
120
121 ^block_2:
122 return %3;
123 };
124 """;
125
126 @Test
127 public void testLoop() {
128 Op op = OpParser.fromString(CoreOp.FACTORY, LOOP).getFirst();
129
130 var actual = liveness(op);
131 var expected = Map.of(
132 0, List.of(Set.of(), Set.of(0)),
133 1, List.of(Set.of(0), Set.of(0, 3, 4)),
134 2, List.of(Set.of(0, 3, 4), Set.of(0, 4, 6)),
135 3, List.of(Set.of(3), Set.of()),
136 4, List.of(Set.of(0, 4, 6), Set.of(0))
137 );
138 Assert.assertEquals(actual, expected);
139 }
140
141 static final String IF_ELSE_NESTED = """
142 func @"ifelseNested" (%0 : int, %1 : int, %2 : int, %3 : int, %4 : int)int -> {
143 %5 : int = constant @"20";
144 %6 : boolean = lt %4 %5;
145 cbranch %6 ^block_0 ^block_1;
146
147 ^block_0:
148 %7 : int = constant @"10";
149 %8 : boolean = lt %4 %7;
150 cbranch %8 ^block_2 ^block_3;
151
152 ^block_2:
153 %9 : int = constant @"1";
154 %10 : int = add %0 %9;
155 branch ^block_4(%10, %1);
156
157 ^block_3:
158 %11 : int = constant @"2";
159 %12 : int = add %1 %11;
160 branch ^block_4(%0, %12);
161
162 ^block_4(%13 : int, %14 : int):
163 %15 : int = constant @"3";
164 %16 : int = add %2 %15;
165 branch ^block_5(%13, %14, %16, %3);
166
167 ^block_1:
168 %17 : int = constant @"20";
169 %18 : boolean = gt %4 %17;
170 cbranch %18 ^block_6 ^block_7;
171
172 ^block_6:
173 %19 : int = constant @"4";
174 %20 : int = add %0 %19;
175 branch ^block_8(%20, %1);
176
177 ^block_7:
178 %21 : int = constant @"5";
179 %22 : int = add %1 %21;
180 branch ^block_8(%0, %22);
181
182 ^block_8(%23 : int, %24 : int):
183 %25 : int = constant @"6";
184 %26 : int = add %3 %25;
185 branch ^block_5(%23, %24, %2, %26);
186
187 ^block_5(%27 : int, %28 : int, %29 : int, %30 : int):
188 %31 : int = add %27 %28;
189 %32 : int = add %31 %29;
190 %33 : int = add %32 %30;
191 return %33;
192 };
193 """;
194
195 @Test
196 public void testIfElseNested() {
197 Op op = OpParser.fromString(CoreOp.FACTORY, IF_ELSE_NESTED).getFirst();
198
199 var actual = liveness(op);
200 var expected = Map.of(
201 0, List.of(Set.of(), Set.of(0, 1, 2, 3, 4)),
202 1, List.of(Set.of(0, 1, 2, 3, 4), Set.of(0, 1, 2, 3)),
203 2, List.of(Set.of(0, 1, 2, 3, 4), Set.of(0, 1, 2, 3)),
204 3, List.of(Set.of(0, 1, 2, 3), Set.of(2, 3)),
205 4, List.of(Set.of(0, 1, 2, 3), Set.of(2, 3)),
206 5, List.of(Set.of(2, 3), Set.of()),
207 6, List.of(Set.of(), Set.of()),
208 7, List.of(Set.of(0, 1, 2, 3), Set.of(2, 3)),
209 8, List.of(Set.of(0, 1, 2, 3), Set.of(2, 3)),
210 9, List.of(Set.of(2, 3), Set.of())
211 );
212 Assert.assertEquals(actual, expected);
213 }
214
215 static final String LOOP_NESTED = """
216 func @"loopNested" (%0 : int)int -> {
217 %1 : int = constant @"0";
218 %2 : int = constant @"0";
219 branch ^block_0(%1, %2);
220
221 ^block_0(%3 : int, %4 : int):
222 %5 : boolean = lt %4 %0;
223 cbranch %5 ^block_1 ^block_2;
224
225 ^block_1:
226 %6 : int = constant @"0";
227 branch ^block_3(%3, %6);
228
229 ^block_3(%7 : int, %8 : int):
230 %9 : boolean = lt %8 %0;
231 cbranch %9 ^block_4 ^block_5;
232
233 ^block_4:
234 %10 : int = add %7 %4;
235 %11 : int = add %10 %8;
236 branch ^block_6;
237
238 ^block_6:
239 %12 : int = constant @"1";
240 %13 : int = add %8 %12;
241 branch ^block_3(%11, %13);
242
243 ^block_5:
244 branch ^block_7;
245
246 ^block_7:
247 %14 : int = constant @"1";
248 %15 : int = add %4 %14;
249 branch ^block_0(%7, %15);
250
251 ^block_2:
252 return %3;
253 };
254 """;
255
256 @Test
257 public void testLoopNested() {
258 Op op = OpParser.fromString(CoreOp.FACTORY, LOOP_NESTED).getFirst();
259
260 var actual = liveness(op);
261 var expected = Map.of(
262 0, List.of(Set.of(), Set.of(0)),
263 1, List.of(Set.of(0), Set.of(0, 3, 4)),
264 2, List.of(Set.of(0, 3, 4), Set.of(0, 4)),
265 3, List.of(Set.of(3), Set.of()),
266 4, List.of(Set.of(0, 4), Set.of(0, 4, 7, 8)),
267 5, List.of(Set.of(0, 4, 7, 8), Set.of(0, 4, 8, 11)),
268 6, List.of(Set.of(0, 4, 7), Set.of(0, 4, 7)),
269 7, List.of(Set.of(0, 4, 8, 11), Set.of(0, 4)),
270 8, List.of(Set.of(0, 4, 7), Set.of(0))
271 );
272 Assert.assertEquals(actual, expected);
273 }
274
275 static Map<Integer, List<Set<Integer>>> liveness(Op op) {
276 Liveness l = new Liveness(op);
277 System.out.println(l);
278
279 Map<Value, Integer> valueMap = valueNameMapping(op);
280 Map<Block, Integer> blockMap = blockNameMapping(op);
281
282 return op.traverse(new HashMap<>(),
283 CodeElement.blockVisitor((m, b) -> {
284 if (b.parentBody().parentOp() == op) {
285 Liveness.BlockInfo lbi = l.getLiveness(b);
286 m.put(blockMap.get(b),
287 List.of(
288 lbi.liveIn().stream().map(valueMap::get).collect(Collectors.toSet()),
289 lbi.liveOut().stream().map(valueMap::get).collect(Collectors.toSet())
290 ));
291 }
292 return m;
293 }));
294 }
295
296 static Map<Block, Integer> blockNameMapping(Op top) {
297 AtomicInteger i = new AtomicInteger();
298 return top.traverse(new HashMap<>(), CodeElement.blockVisitor((m, b) -> {
299 if (b.parentBody().parentOp() != top) {
300 return m;
301 }
302
303 m.computeIfAbsent(b, _ -> i.getAndIncrement());
304 for (Block.Reference s : b.successors()) {
305 m.computeIfAbsent(s.targetBlock(), _ -> i.getAndIncrement());
306 }
307
308 return m;
309 }));
310 }
311
312 static Map<Value, Integer> valueNameMapping(Op top) {
313 AtomicInteger i = new AtomicInteger();
314 return top.traverse(new HashMap<>(), (m, e) -> {
315 switch (e) {
316 case Block b -> {
317 for (Block.Parameter p : b.parameters()) {
318 m.put(p, i.getAndIncrement());
319 }
320 }
321 case Op op -> {
322 Op.Result r = op.result();
323 if (r != null && !r.type().equals(JavaType.VOID)) {
324 m.put(r, i.getAndIncrement());
325 }
326 }
327 default -> {
328 }
329 }
330 return m;
331 });
332 }
333 }