1 /*
2 * Copyright (c) 2024, 2026, 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 junit TestLiveness
28 */
29
30 import jdk.incubator.code.*;
31 import jdk.incubator.code.dialect.java.JavaOp;
32 import jdk.incubator.code.dialect.java.JavaType;
33 import jdk.incubator.code.extern.OpParser;
34 import jdk.incubator.code.extern.OpWriter;
35 import org.junit.jupiter.api.Assertions;
36 import org.junit.jupiter.api.Test;
37
38 import java.io.IOException;
39 import java.io.StringWriter;
40 import java.io.UncheckedIOException;
41 import java.io.Writer;
42 import java.util.*;
43 import java.util.concurrent.atomic.AtomicInteger;
44 import java.util.function.Function;
45 import java.util.stream.Collectors;
46
47 public class TestLiveness {
48
49 /**
50 * Provides liveness information for values declared in the bodies of an operation.
51 */
52 public static class Liveness {
53
54 /**
55 * Liveness information associated with a block.
56 * Each block has two sets of values, live-in values and live-out values.
57 */
58 public static final class BlockInfo {
59 final Block block;
60 final Deque<Value> inValues;
61 final Deque<Value> outValues;
62
63 BlockInfo(Block block) {
64 this.block = block;
65 this.inValues = new ArrayDeque<>();
66 this.outValues = new ArrayDeque<>();
67 }
68
69 /**
70 * {@return the block associated with the liveness information}
71 */
72 public Block getBlock() {
73 return block;
74 }
75
76 /**
77 * Returns true if a value is live-in for the associated block.
78 * <p>
79 * A value is live-in for a block if it is not declared in the block
80 * and is used in the block or (transitively) by some successor.
81 *
82 * @param value the value
83 * @return true if the value is live-in
84 */
85 public boolean isLiveIn(Value value) {
86 return inValues.contains(value);
87 }
88
89 /**
90 * {@return the set of live-in values}
91 */
92 public Set<Value> liveIn() {
93 return new HashSet<>(inValues);
94 }
95
96 /**
97 * Returns true if a value is live-out for the associated block.
98 * <p>
99 * A value is live-out for a block if it is used (transitively) by some successor.
100 *
101 * @param value the value
102 * @return true if the value is live-out
103 */
104 public boolean isLiveOut(Value value) {
105 return outValues.contains(value);
106 }
107
108 /**
109 * {@return the set of live-out values}
110 */
111 public Set<Value> liveOut() {
112 return new HashSet<>(outValues);
113 }
114
115 /**
116 * Returns the first operation associated with a value and the associated block.
117 * <p>
118 * If the value is live-in or a block argument then the blocks first operation
119 * is returned. Otherwise, the value is an operation result and its operation
120 * is returned.
121 *
122 * @param value the value
123 * @return first operation associated with a value and the associated block.
124 */
125 public Op getStartOperation(Value value) {
126 if (isLiveIn(value) || value instanceof Block.Parameter) {
127 // @@@ Check value is from this block
128 return block.firstOp();
129 } else {
130 // @@@ Check value is from block
131 Op.Result or = (Op.Result) value;
132 return or.op();
133 }
134 }
135
136 /**
137 * Returns the end operation associated with a value and the associated block.
138 * <p>
139 * If the value is live-out then the blocks last (and terminating) operation
140 * is returned. Otherwise, the value is dying in this block and the last
141 * operation to use this value is returned.
142 *
143 * @param value the value
144 * @return first operation associated with a value and the associated block.
145 */
146 public Op getEndOperation(Value value, Op startOp) {
147 // Value is used by some other operation
148 if (isLiveOut(value)) {
149 return block.terminatingOp();
150 }
151
152 // Value may be last used in this block, if so find it
153 // @@@ Check startOp is of this block
154 Op endOp = startOp;
155 for (Op.Result useOpr : value.uses()) {
156 Op useOp = useOpr.op();
157 // Find the operation in the current block
158 useOp = findChildAncestor(block, useOp);
159 // Update if after
160 if (useOp != null && isBeforeInBlock(endOp, useOp)) {
161 endOp = useOp;
162 }
163 }
164 return endOp;
165 }
166 }
167
168 final Op op;
169 final Map<Block, Liveness.BlockInfo> livenessMapping;
170
171 /**
172 * Constructs liveness information for values declared in the bodies
173 * of an operation.
174 *
175 * @param op the operation.
176 */
177 @SuppressWarnings("this-escape")
178 public Liveness(Op op) {
179 this.op = op;
180 this.livenessMapping = new HashMap<>();
181 for (Body cfg : op.bodies()) {
182 Compute_LiveSets_SSA_ByVar(cfg);
183 }
184 }
185
186 /*
187 The algorithm to compute liveness information is derived from
188 Domaine, & Brandner, Florian & Boissinot, Benoit & Darte, Alain & Dinechin, Benoit & Rastello, Fabrice.
189 (2011). Computing Liveness Sets for SSA-Form Programs.
190 https://inria.hal.science/inria-00558509v2/document
191 Specifically Algorithm 6 & 7, adapted to work with block arguments and
192 block parameters instead of phi operations.
193 This is a simple algorithm that is easy to understand. We may need to review
194 its usage within exception regions.
195 We also may revisit this later with a more performant implementation
196 perhaps based on the well known algorithm that uses fixpoint iteration.
197 */
198
199 void Compute_LiveSets_SSA_ByVar(Body CFG) {
200 for (Block b : CFG.blocks()) {
201 livenessMapping.put(b, new Liveness.BlockInfo(b));
202 }
203 for (Block b : CFG.blocks()) {
204 for (Block.Parameter p : b.parameters()) {
205 Compute_LiveSets_SSA_ByVar(CFG, p);
206 }
207
208 for (Op op : b.ops()) {
209 Compute_LiveSets_SSA_ByVar(CFG, op.result());
210 }
211 }
212 }
213
214 void Compute_LiveSets_SSA_ByVar(Body CFG, Value v) {
215 for (Op.Result use : v.uses()) {
216 Block B = findChildAncestor(CFG, use.declaringBlock());
217 Up_and_Mark_Stack(B, v);
218 }
219 }
220
221 void Up_and_Mark_Stack(Block B, Value v) {
222 if (v.declaringBlock() == B) {
223 return;
224 }
225 var lbi = livenessMapping.get(B);
226 if (lbi.inValues.peek() == v) {
227 return;
228 }
229 lbi.inValues.push(v);
230 for (Block P : B.predecessors()) {
231 lbi = livenessMapping.get(P);
232 if (lbi.outValues.peek() != v) {
233 lbi.outValues.push(v);
234 }
235 Up_and_Mark_Stack(P, v);
236 }
237 }
238
239 /**
240 * {@return the liveness information as a string}
241 */
242 public String toString() {
243 StringWriter w = new StringWriter();
244 writeTo(w);
245 return w.toString();
246 }
247
248 /**
249 * Writes the liveness information to the given writer.
250 *
251 * @param w the writer to write to.
252 */
253 public void writeTo(Writer w) {
254 OpWriter ow = new OpWriter(w);
255 ow.writeOp(op);
256 try {
257 w.write("\n");
258 } catch (IOException e) {
259 throw new UncheckedIOException(e);
260 }
261 Function<CodeItem, String> namer = ow.namer();
262 op.elements().forEach(e -> {
263 if (!(e instanceof Block b)) {
264 return;
265 }
266 Liveness.BlockInfo liveness = getLiveness(b);
267 try {
268 w.write("^" + namer.apply(b));
269 w.write("\n");
270 w.write(" Live-in values: ");
271 w.write(liveness.inValues.stream()
272 .map(v -> "%" + namer.apply(v))
273 .collect(Collectors.joining(",")));
274 w.write("\n");
275 w.write(" Live-out values: ");
276 w.write(liveness.outValues.stream()
277 .map(v -> "%" + namer.apply(v))
278 .collect(Collectors.joining(",")));
279 w.write("\n");
280 } catch (IOException ex) {
281 throw new UncheckedIOException(ex);
282 }
283 });
284 }
285
286 /**
287 * Returns true if a value is last used by an operation.
288 * <p>
289 * The liveness information for the operation's parent block
290 * is obtained. If the value is live-out then the value escapes
291 * the block and is therefore not the last use, and this method
292 * returns false.
293 * If the operation is the last to use the value, this method
294 * returns true. If the operation does not use the value and
295 * the {@link Liveness.BlockInfo#getEndOperation end operation}
296 * occurs before the operation, this method returns true.
297 * Otherwise, this method returns false.
298 *
299 * @param value the value
300 * @param op the operation
301 * @return true if a value is last used by an operation
302 */
303 public boolean isLastUse(Value value, Op op) {
304 Block block = op.ancestorBlock();
305 Liveness.BlockInfo liveness = getLiveness(block);
306
307 // Value is used by some successor
308 if (liveness.isLiveOut(value))
309 return false;
310
311 Op endOp = liveness.getEndOperation(value, op);
312 // Last use or operation is after last use
313 return endOp == op || isBeforeInBlock(endOp, op);
314 }
315
316 /**
317 * {@return the liveness information associated with a block}
318 *
319 * @param block the block
320 * @throws IllegalArgumentException if the block has no liveness information
321 */
322 public Liveness.BlockInfo getLiveness(Block block) {
323 Liveness.BlockInfo lbi = livenessMapping.get(block);
324 if (lbi == null) {
325 throw new IllegalArgumentException("Block has no liveness information");
326 }
327 return lbi;
328 }
329
330 private static boolean isBeforeInBlock(Op thisOp, Op thatOp) {
331 if (thisOp.result() == null || thatOp.result() == null) {
332 throw new IllegalArgumentException("This or the given operation is not assigned to a block");
333 }
334
335 if (thisOp.ancestorBlock() != thatOp.ancestorBlock()) {
336 throw new IllegalArgumentException("This and that operation are not assigned to the same blocks");
337 }
338
339 List<Op> ops = thisOp.ancestorBlock().ops();
340 return ops.indexOf(thisOp) < ops.indexOf(thatOp);
341 }
342
343 /**
344 * Finds the child of the parent element that is an ancestor of the given descendant element,
345 * otherwise returns the descendant element if a child of this element, otherwise
346 * returns {@code null} if there is no such child.
347 *
348 * @param parent the parent element
349 * @param descendant the descendant element
350 * @return the child that is an ancestor of the given descendant element, otherwise the descendant
351 * element if a child of this element, otherwise {@code null}.
352 * @throws IllegalStateException if an operation with unbuilt parent block is encountered.
353 */
354 private static <C extends CodeElement<C, ?>> C findChildAncestor(CodeElement<?, C> parent, CodeElement<?, ?> descendant) {
355 Objects.requireNonNull(descendant);
356
357 CodeElement<?, ?> e = descendant;
358 while (e != null && e.parent() != parent) {
359 e = e.parent();
360 }
361
362 @SuppressWarnings("unchecked")
363 C child = (C) e;
364 return child;
365 }
366 }
367
368
369
370 static final String F = """
371 func @"f" (%0 : java.type:"int", %1 : java.type:"int")java.type:"int" -> {
372 %2 : java.type:"int" = add %0 %1;
373 return %2;
374 };
375 """;
376
377 @Test
378 public void testF() {
379 Op op = OpParser.fromString(JavaOp.JAVA_DIALECT_FACTORY, F).getFirst();
380
381 var actual = liveness(op);
382 var expected = Map.of(
383 0, List.of(Set.of(), Set.of()));
384 Assertions.assertEquals(expected, actual);
385 }
386
387 static final String IF_ELSE = """
388 func @"ifelse" (%0 : java.type:"int", %1 : java.type:"int", %2 : java.type:"int")java.type:"int" -> {
389 %3 : java.type:"int" = constant @10;
390 %4 : java.type:"boolean" = lt %2 %3;
391 cbranch %4 ^block_0 ^block_1;
392
393 ^block_0:
394 %5 : java.type:"int" = constant @1;
395 %6 : java.type:"int" = add %0 %5;
396 branch ^block_2(%6, %1);
397
398 ^block_1:
399 %7 : java.type:"int" = constant @2;
400 %8 : java.type:"int" = add %1 %7;
401 branch ^block_2(%0, %8);
402
403 ^block_2(%9 : java.type:"int", %10 : java.type:"int"):
404 %11 : java.type:"int" = add %9 %10;
405 return %11;
406 };
407 """;
408
409 @Test
410 public void testIfElse() {
411 Op op = OpParser.fromString(JavaOp.JAVA_DIALECT_FACTORY, IF_ELSE).getFirst();
412
413 var actual = liveness(op);
414 var expected = Map.of(
415 0, List.of(Set.of(), Set.of(0, 1)),
416 1, List.of(Set.of(0, 1), Set.of()),
417 2, List.of(Set.of(0, 1), Set.of()),
418 3, List.of(Set.of(), Set.of())
419 );
420 Assertions.assertEquals(expected, actual);
421 }
422
423 static final String LOOP = """
424 func @"loop" (%0 : java.type:"int")java.type:"int" -> {
425 %1 : java.type:"int" = constant @0;
426 %2 : java.type:"int" = constant @0;
427 branch ^block_0(%1, %2);
428
429 ^block_0(%3 : java.type:"int", %4 : java.type:"int"):
430 %5 : java.type:"boolean" = lt %4 %0;
431 cbranch %5 ^block_1 ^block_2;
432
433 ^block_1:
434 %6 : java.type:"int" = add %3 %4;
435 branch ^block_3;
436
437 ^block_3:
438 %7 : java.type:"int" = constant @1;
439 %8 : java.type:"int" = add %4 %7;
440 branch ^block_0(%6, %8);
441
442 ^block_2:
443 return %3;
444 };
445 """;
446
447 @Test
448 public void testLoop() {
449 Op op = OpParser.fromString(JavaOp.JAVA_DIALECT_FACTORY, LOOP).getFirst();
450
451 var actual = liveness(op);
452 var expected = Map.of(
453 0, List.of(Set.of(), Set.of(0)),
454 1, List.of(Set.of(0), Set.of(0, 3, 4)),
455 2, List.of(Set.of(0, 3, 4), Set.of(0, 4, 6)),
456 3, List.of(Set.of(3), Set.of()),
457 4, List.of(Set.of(0, 4, 6), Set.of(0))
458 );
459 Assertions.assertEquals(expected, actual);
460 }
461
462 static final String IF_ELSE_NESTED = """
463 func @"ifelseNested" (%0 : java.type:"int", %1 : java.type:"int", %2 : java.type:"int", %3 : java.type:"int", %4 : java.type:"int")java.type:"int" -> {
464 %5 : java.type:"int" = constant @20;
465 %6 : java.type:"boolean" = lt %4 %5;
466 cbranch %6 ^block_0 ^block_1;
467
468 ^block_0:
469 %7 : java.type:"int" = constant @10;
470 %8 : java.type:"boolean" = lt %4 %7;
471 cbranch %8 ^block_2 ^block_3;
472
473 ^block_2:
474 %9 : java.type:"int" = constant @1;
475 %10 : java.type:"int" = add %0 %9;
476 branch ^block_4(%10, %1);
477
478 ^block_3:
479 %11 : java.type:"int" = constant @2;
480 %12 : java.type:"int" = add %1 %11;
481 branch ^block_4(%0, %12);
482
483 ^block_4(%13 : java.type:"int", %14 : java.type:"int"):
484 %15 : java.type:"int" = constant @3;
485 %16 : java.type:"int" = add %2 %15;
486 branch ^block_5(%13, %14, %16, %3);
487
488 ^block_1:
489 %17 : java.type:"int" = constant @20;
490 %18 : java.type:"boolean" = gt %4 %17;
491 cbranch %18 ^block_6 ^block_7;
492
493 ^block_6:
494 %19 : java.type:"int" = constant @4;
495 %20 : java.type:"int" = add %0 %19;
496 branch ^block_8(%20, %1);
497
498 ^block_7:
499 %21 : java.type:"int" = constant @5;
500 %22 : java.type:"int" = add %1 %21;
501 branch ^block_8(%0, %22);
502
503 ^block_8(%23 : java.type:"int", %24 : java.type:"int"):
504 %25 : java.type:"int" = constant @6;
505 %26 : java.type:"int" = add %3 %25;
506 branch ^block_5(%23, %24, %2, %26);
507
508 ^block_5(%27 : java.type:"int", %28 : java.type:"int", %29 : java.type:"int", %30 : java.type:"int"):
509 %31 : java.type:"int" = add %27 %28;
510 %32 : java.type:"int" = add %31 %29;
511 %33 : java.type:"int" = add %32 %30;
512 return %33;
513 };
514 """;
515
516 @Test
517 public void testIfElseNested() {
518 Op op = OpParser.fromString(JavaOp.JAVA_DIALECT_FACTORY, IF_ELSE_NESTED).getFirst();
519
520 var actual = liveness(op);
521 var expected = Map.of(
522 0, List.of(Set.of(), Set.of(0, 1, 2, 3, 4)),
523 1, List.of(Set.of(0, 1, 2, 3, 4), Set.of(0, 1, 2, 3)),
524 2, List.of(Set.of(0, 1, 2, 3, 4), Set.of(0, 1, 2, 3)),
525 3, List.of(Set.of(0, 1, 2, 3), Set.of(2, 3)),
526 4, List.of(Set.of(0, 1, 2, 3), Set.of(2, 3)),
527 5, List.of(Set.of(2, 3), Set.of()),
528 6, List.of(Set.of(), Set.of()),
529 7, List.of(Set.of(0, 1, 2, 3), Set.of(2, 3)),
530 8, List.of(Set.of(0, 1, 2, 3), Set.of(2, 3)),
531 9, List.of(Set.of(2, 3), Set.of())
532 );
533 Assertions.assertEquals(expected, actual);
534 }
535
536 static final String LOOP_NESTED = """
537 func @"loopNested" (%0 : java.type:"int")java.type:"int" -> {
538 %1 : java.type:"int" = constant @0;
539 %2 : java.type:"int" = constant @0;
540 branch ^block_0(%1, %2);
541
542 ^block_0(%3 : java.type:"int", %4 : java.type:"int"):
543 %5 : java.type:"boolean" = lt %4 %0;
544 cbranch %5 ^block_1 ^block_2;
545
546 ^block_1:
547 %6 : java.type:"int" = constant @0;
548 branch ^block_3(%3, %6);
549
550 ^block_3(%7 : java.type:"int", %8 : java.type:"int"):
551 %9 : java.type:"boolean" = lt %8 %0;
552 cbranch %9 ^block_4 ^block_5;
553
554 ^block_4:
555 %10 : java.type:"int" = add %7 %4;
556 %11 : java.type:"int" = add %10 %8;
557 branch ^block_6;
558
559 ^block_6:
560 %12 : java.type:"int" = constant @1;
561 %13 : java.type:"int" = add %8 %12;
562 branch ^block_3(%11, %13);
563
564 ^block_5:
565 branch ^block_7;
566
567 ^block_7:
568 %14 : java.type:"int" = constant @1;
569 %15 : java.type:"int" = add %4 %14;
570 branch ^block_0(%7, %15);
571
572 ^block_2:
573 return %3;
574 };
575 """;
576
577 @Test
578 public void testLoopNested() {
579 Op op = OpParser.fromString(JavaOp.JAVA_DIALECT_FACTORY, LOOP_NESTED).getFirst();
580
581 var actual = liveness(op);
582 var expected = Map.of(
583 0, List.of(Set.of(), Set.of(0)),
584 1, List.of(Set.of(0), Set.of(0, 3, 4)),
585 2, List.of(Set.of(0, 3, 4), Set.of(0, 4)),
586 3, List.of(Set.of(3), Set.of()),
587 4, List.of(Set.of(0, 4), Set.of(0, 4, 7, 8)),
588 5, List.of(Set.of(0, 4, 7, 8), Set.of(0, 4, 8, 11)),
589 6, List.of(Set.of(0, 4, 7), Set.of(0, 4, 7)),
590 7, List.of(Set.of(0, 4, 8, 11), Set.of(0, 4)),
591 8, List.of(Set.of(0, 4, 7), Set.of(0))
592 );
593 Assertions.assertEquals(expected, actual);
594 }
595
596 static Map<Integer, List<Set<Integer>>> liveness(Op op) {
597 Liveness l = new Liveness(op);
598 System.out.println(l);
599
600 Map<Value, Integer> valueMap = valueNameMapping(op);
601 Map<Block, Integer> blockMap = blockNameMapping(op);
602
603 Map<Integer, List<Set<Integer>>> m = new HashMap<>();
604 op.elements().forEach(e -> {
605 if (e instanceof Block b) {
606 if (b.ancestorOp() == op) {
607 Liveness.BlockInfo lbi = l.getLiveness(b);
608 m.put(blockMap.get(b),
609 List.of(
610 lbi.liveIn().stream().map(valueMap::get).collect(Collectors.toSet()),
611 lbi.liveOut().stream().map(valueMap::get).collect(Collectors.toSet())
612 ));
613 }
614 }
615 });
616 return m;
617 }
618
619 static Map<Block, Integer> blockNameMapping(Op top) {
620 AtomicInteger i = new AtomicInteger();
621 Map<Block, Integer> m = new HashMap<>();
622 top.elements().forEach(e -> {
623 if (e instanceof Block b) {
624 if (b.ancestorOp() != top) {
625 return;
626 }
627
628 m.computeIfAbsent(b, _ -> i.getAndIncrement());
629 for (Block.Reference s : b.successors()) {
630 m.computeIfAbsent(s.targetBlock(), _ -> i.getAndIncrement());
631 }
632 }
633 });
634 return m;
635 }
636
637 static Map<Value, Integer> valueNameMapping(Op top) {
638 AtomicInteger i = new AtomicInteger();
639 Map<Value, Integer> m = new HashMap<>();
640 top.elements().forEach(e -> {
641 switch (e) {
642 case Block b -> {
643 for (Block.Parameter p : b.parameters()) {
644 m.put(p, i.getAndIncrement());
645 }
646 }
647 case Op op -> {
648 Op.Result r = op.result();
649 if (r != null && !r.type().equals(JavaType.VOID)) {
650 m.put(r, i.getAndIncrement());
651 }
652 }
653 default -> {
654 }
655 }
656 });
657 return m;
658 }
659 }