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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package jdk.incubator.code.analysis;
26
27 import java.io.IOException;
28 import java.io.StringWriter;
29 import java.io.UncheckedIOException;
30 import java.io.Writer;
31 import jdk.incubator.code.*;
32 import jdk.incubator.code.writer.OpWriter;
33 import java.util.*;
34 import java.util.function.Function;
35 import java.util.stream.Collectors;
36
37 /**
38 * Provides liveness information for values declared in the bodies of an operation.
39 */
40 public class Liveness {
41
42 /**
43 * Liveness information associated with a block.
44 * Each block has two sets of values, live-in values and live-out values.
45 */
46 public static final class BlockInfo {
47 final Block block;
48 final Deque<Value> inValues;
49 final Deque<Value> outValues;
50
51 BlockInfo(Block block) {
52 this.block = block;
53 this.inValues = new ArrayDeque<>();
54 this.outValues = new ArrayDeque<>();
55 }
56
57 /**
58 * {@return the block associated with the liveness information}
59 */
60 public Block getBlock() {
61 return block;
62 }
63
64 /**
65 * Returns true if a value is live-in for the associated block.
66 * <p>
67 * A value is live-in for a block if it is not declared in the block
68 * and is used in the block or (transitively) by some successor.
69 *
70 * @param value the value
71 * @return true if the value is live-in
72 */
73 public boolean isLiveIn(Value value) {
74 return inValues.contains(value);
75 }
76
77 /**
78 * {@return the set of live-in values}
79 */
80 public Set<Value> liveIn() {
81 return new HashSet<>(inValues);
82 }
83
84 /**
85 * Returns true if a value is live-out for the associated block.
86 * <p>
87 * A value is live-out for a block if it is used (transitively) by some successor.
88 *
89 * @param value the value
90 * @return true if the value is live-out
91 */
92 public boolean isLiveOut(Value value) {
93 return outValues.contains(value);
94 }
95
96 /**
97 * {@return the set of live-out values}
98 */
99 public Set<Value> liveOut() {
100 return new HashSet<>(outValues);
101 }
102
103 /**
104 * Returns the first operation associated with a value and the associated block.
105 * <p>
106 * If the value is live-in or a block argument then the blocks first operation
107 * is returned. Otherwise, the value is an operation result and its operation
108 * is returned.
109 *
110 * @param value the value
111 * @return first operation associated with a value and the associated block.
112 */
113 public Op getStartOperation(Value value) {
114 if (isLiveIn(value) || value instanceof Block.Parameter) {
115 // @@@ Check value is from this block
116 return block.firstOp();
117 } else {
118 // @@@ Check value is from block
119 Op.Result or = (Op.Result) value;
120 return or.op();
121 }
122 }
123
124 /**
125 * Returns the end operation associated with a value and the associated block.
126 * <p>
127 * If the value is live-out then the blocks last (and terminating) operation
128 * is returned. Otherwise, the value is dying in this block and the last
129 * operation to use this value is returned.
130 *
131 * @param value the value
132 * @return first operation associated with a value and the associated block.
133 */
134 public Op getEndOperation(Value value, Op startOp) {
135 // Value is used by some other operation
136 if (isLiveOut(value)) {
137 return block.terminatingOp();
138 }
139
140 // Value may be last used in this block, if so find it
141 // @@@ Check startOp is of this block
142 Op endOp = startOp;
143 for (Op.Result useOpr : value.uses()) {
144 Op useOp = useOpr.op();
145 // Find the operation in the current block
146 useOp = block.findAncestorOpInBlock(useOp);
147 // Update if after
148 if (useOp != null && isBeforeInBlock(endOp, useOp)) {
149 endOp = useOp;
150 }
151 }
152 return endOp;
153 }
154 }
155
156 final Op op;
157 final Map<Block, BlockInfo> livenessMapping;
158
159 /**
160 * Constructs liveness information for values declared in the bodies
161 * of an operation.
162 *
163 * @param op the operation.
164 */
165 @SuppressWarnings("this-escape")
166 public Liveness(Op op) {
167 this.op = op;
168 this.livenessMapping = new HashMap<>();
169 for (Body cfg : op.bodies()) {
170 Compute_LiveSets_SSA_ByVar(cfg);
171 }
172 }
173
174 /*
175 The algorithm to compute liveness information is derived from
176 Domaine, & Brandner, Florian & Boissinot, Benoit & Darte, Alain & Dinechin, Benoit & Rastello, Fabrice.
177 (2011). Computing Liveness Sets for SSA-Form Programs.
178 https://inria.hal.science/inria-00558509v2/document
179 Specifically Algorithm 6 & 7, adapted to work with block arguments and
180 block parameters instead of phi operations.
181 This is a simple algorithm that is easy to understand. We may need to review
182 its usage within exception regions.
183 We also may revisit this later with a more performant implementation
184 perhaps based on the well known algorithm that uses fixpoint iteration.
185 */
186
187 void Compute_LiveSets_SSA_ByVar(Body CFG) {
188 for (Block b : CFG.blocks()) {
189 livenessMapping.put(b, new BlockInfo(b));
190 }
191 for (Block b : CFG.blocks()) {
192 for (Block.Parameter p : b.parameters()) {
193 Compute_LiveSets_SSA_ByVar(CFG, p);
194 }
195
196 for (Op op : b.ops()) {
197 Compute_LiveSets_SSA_ByVar(CFG, op.result());
198 }
199 }
200 }
201
202 void Compute_LiveSets_SSA_ByVar(Body CFG, Value v) {
203 for (Op.Result use : v.uses()) {
204 Block B = CFG.findAncestorBlockInBody(use.declaringBlock());
205 Up_and_Mark_Stack(B, v);
206 }
207 }
208
209 void Up_and_Mark_Stack(Block B, Value v) {
210 if (v.declaringBlock() == B) {
211 return;
212 }
213 var lbi = livenessMapping.get(B);
214 if (lbi.inValues.peek() == v) {
215 return;
216 }
217 lbi.inValues.push(v);
218 for (Block P : B.predecessors()) {
219 lbi = livenessMapping.get(P);
220 if (lbi.outValues.peek() != v) {
221 lbi.outValues.push(v);
222 }
223 Up_and_Mark_Stack(P, v);
224 }
225 }
226
227 /**
228 * {@return the liveness information as a string}
229 */
230 public String toString() {
231 StringWriter w = new StringWriter();
232 writeTo(w);
233 return w.toString();
234 }
235
236 /**
237 * Writes the liveness information to the given writer.
238 *
239 * @param w the writer to write to.
240 */
241 public void writeTo(Writer w) {
242 OpWriter ow = new OpWriter(w);
243 ow.writeOp(op);
244 try {
245 w.write("\n");
246 } catch (IOException e) {
247 throw new UncheckedIOException(e);
248 }
249 Function<CodeItem, String> namer = ow.namer();
250 op.traverse(null, CodeElement.blockVisitor((_, b) -> {
251 BlockInfo liveness = getLiveness(b);
252 try {
253 w.write("^" + namer.apply(b));
254 w.write("\n");
255 w.write(" Live-in values: ");
256 w.write(liveness.inValues.stream()
257 .map(v -> "%" + namer.apply(v))
258 .collect(Collectors.joining(",")));
259 w.write("\n");
260 w.write(" Live-out values: ");
261 w.write(liveness.outValues.stream()
262 .map(v -> "%" + namer.apply(v))
263 .collect(Collectors.joining(",")));
264 w.write("\n");
265 return null;
266 } catch (IOException e) {
267 throw new UncheckedIOException(e);
268 }
269 }));
270 }
271
272 /**
273 * Returns true if a value is last used by an operation.
274 * <p>
275 * The liveness information for the operation's parent block
276 * is obtained. If the value is live-out then the value escapes
277 * the block and is therefore not the last use, and this method
278 * returns false.
279 * If the operation is the last to use the value, this method
280 * returns true. If the operation does not use the value and
281 * the {@link BlockInfo#getEndOperation end operation}
282 * occurs before the operation, this method returns true.
283 * Otherwise, this method returns false.
284 *
285 * @param value the value
286 * @param op the operation
287 * @return true if a value is last used by an operation
288 */
289 public boolean isLastUse(Value value, Op op) {
290 Block block = op.parentBlock();
291 BlockInfo liveness = getLiveness(block);
292
293 // Value is used by some successor
294 if (liveness.isLiveOut(value))
295 return false;
296
297 Op endOp = liveness.getEndOperation(value, op);
298 // Last use or operation is after last use
299 return endOp == op || isBeforeInBlock(endOp, op);
300 }
301
302 /**
303 * {@return the liveness information associated with a block}
304 *
305 * @param block the block
306 * @throws IllegalArgumentException if the block has no liveness information
307 */
308 public BlockInfo getLiveness(Block block) {
309 BlockInfo lbi = livenessMapping.get(block);
310 if (lbi == null) {
311 throw new IllegalArgumentException("Block has no liveness information");
312 }
313 return lbi;
314 }
315
316 private static boolean isBeforeInBlock(Op thisOp, Op thatOp) {
317 if (thisOp.result() == null || thatOp.result() == null) {
318 throw new IllegalArgumentException("This or the given operation is not assigned to a block");
319 }
320
321 if (thisOp.parentBlock() != thatOp.parentBlock()) {
322 throw new IllegalArgumentException("This and that operation are not assigned to the same blocks");
323 }
324
325 List<Op> ops = thisOp.parentBlock().ops();
326 return ops.indexOf(thisOp) < ops.indexOf(thatOp);
327 }
328
329 }