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