1 /*
2 * Copyright (c) 2009, 2015, 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 package org.graalvm.compiler.java;
24
25 import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD;
26 import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_0;
27 import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_1;
28 import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_2;
29 import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_3;
30 import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE;
31 import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_0;
32 import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_1;
33 import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_2;
34 import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_3;
35 import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD;
36 import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_0;
37 import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_1;
38 import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_2;
39 import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_3;
40 import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE;
41 import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_0;
42 import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_1;
43 import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_2;
44 import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_3;
45 import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD;
46 import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_0;
47 import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_1;
48 import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_2;
49 import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_3;
50 import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE;
51 import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_0;
52 import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_1;
53 import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_2;
54 import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_3;
55 import static org.graalvm.compiler.bytecode.Bytecodes.IINC;
56 import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD;
57 import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_0;
58 import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_1;
59 import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_2;
60 import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_3;
61 import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE;
62 import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_0;
63 import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_1;
64 import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_2;
65 import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_3;
66 import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD;
67 import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_0;
68 import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_1;
69 import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_2;
70 import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_3;
71 import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE;
72 import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_0;
73 import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_1;
74 import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_2;
75 import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_3;
76 import static org.graalvm.compiler.bytecode.Bytecodes.RET;
77
78 import org.graalvm.compiler.bytecode.BytecodeStream;
79 import org.graalvm.compiler.debug.Debug;
80 import org.graalvm.compiler.java.BciBlockMapping.BciBlock;
81
82 /**
83 * Encapsulates the liveness calculation, so that subclasses for locals ≤ 64 and locals > 64
84 * can be implemented.
85 */
86 public abstract class LocalLiveness {
87 protected final BciBlock[] blocks;
88
89 public static LocalLiveness compute(BytecodeStream stream, BciBlock[] blocks, int maxLocals, int loopCount) {
90 LocalLiveness liveness = maxLocals <= 64 ? new SmallLocalLiveness(blocks, maxLocals, loopCount) : new LargeLocalLiveness(blocks, maxLocals, loopCount);
91 liveness.computeLiveness(stream);
92 return liveness;
93 }
94
95 protected LocalLiveness(BciBlock[] blocks) {
96 this.blocks = blocks;
97 }
98
99 void computeLiveness(BytecodeStream stream) {
100 for (BciBlock block : blocks) {
101 computeLocalLiveness(stream, block);
102 }
103
104 boolean changed;
105 int iteration = 0;
106 do {
107 assert traceIteration(iteration);
108 changed = false;
109 for (int i = blocks.length - 1; i >= 0; i--) {
110 BciBlock block = blocks[i];
111 int blockID = block.getId();
112 assert traceStart(block, blockID);
113
114 boolean blockChanged = (iteration == 0);
115 if (block.getSuccessorCount() > 0) {
116 int oldCardinality = liveOutCardinality(blockID);
117 for (BciBlock sux : block.getSuccessors()) {
118 assert traceSuccessor(sux);
119 propagateLiveness(blockID, sux.getId());
120 }
121 blockChanged |= (oldCardinality != liveOutCardinality(blockID));
122 }
123
124 if (blockChanged) {
125 updateLiveness(blockID);
126 assert traceEnd(block, blockID);
127 }
128 changed |= blockChanged;
129 }
130 iteration++;
131 } while (changed);
132 }
133
134 private static boolean traceIteration(int iteration) {
135 Debug.log("Iteration %d", iteration);
136 return true;
137 }
138
139 private boolean traceEnd(BciBlock block, int blockID) {
140 if (Debug.isLogEnabled()) {
141 Debug.logv(" end B%d [%d, %d] in: %s out: %s gen: %s kill: %s", block.getId(), block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID), debugLiveGen(blockID),
142 debugLiveKill(blockID));
143 }
144 return true;
145 }
146
147 private boolean traceSuccessor(BciBlock sux) {
148 if (Debug.isLogEnabled()) {
149 Debug.log(" Successor B%d: %s", sux.getId(), debugLiveIn(sux.getId()));
150 }
151 return true;
152 }
153
154 private boolean traceStart(BciBlock block, int blockID) {
155 if (Debug.isLogEnabled()) {
156 Debug.logv(" start B%d [%d, %d] in: %s out: %s gen: %s kill: %s", block.getId(), block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID), debugLiveGen(blockID),
157 debugLiveKill(blockID));
158 }
159 return true;
160 }
161
162 /**
163 * Returns whether the local is live at the beginning of the given block.
164 */
165 public abstract boolean localIsLiveIn(BciBlock block, int local);
166
167 /**
168 * Returns whether the local is set in the given loop.
169 */
170 public abstract boolean localIsChangedInLoop(int loopId, int local);
171
172 /**
173 * Returns whether the local is live at the end of the given block.
174 */
175 public abstract boolean localIsLiveOut(BciBlock block, int local);
176
177 /**
178 * Returns a string representation of the liveIn values of the given block.
179 */
180 protected abstract String debugLiveIn(int blockID);
181
182 /**
183 * Returns a string representation of the liveOut values of the given block.
184 */
185 protected abstract String debugLiveOut(int blockID);
186
187 /**
188 * Returns a string representation of the liveGen values of the given block.
189 */
190 protected abstract String debugLiveGen(int blockID);
191
192 /**
193 * Returns a string representation of the liveKill values of the given block.
194 */
195 protected abstract String debugLiveKill(int blockID);
196
197 /**
198 * Returns the number of live locals at the end of the given block.
199 */
200 protected abstract int liveOutCardinality(int blockID);
201
202 /**
203 * Adds all locals the are in the liveIn of the successor to the liveOut of the block.
204 */
205 protected abstract void propagateLiveness(int blockID, int successorID);
206
207 /**
208 * Calculates a new liveIn for the given block from liveOut, liveKill and liveGen.
209 */
210 protected abstract void updateLiveness(int blockID);
211
212 /**
213 * Adds the local to liveGen if it wasn't already killed in this block.
214 */
215 protected abstract void loadOne(int blockID, int local);
216
217 /**
218 * Add this local to liveKill if it wasn't already generated in this block.
219 */
220 protected abstract void storeOne(int blockID, int local);
221
222 private void computeLocalLiveness(BytecodeStream stream, BciBlock block) {
223 if (block.startBci < 0 || block.endBci < 0) {
224 return;
225 }
226 int blockID = block.getId();
227 int localIndex;
228 stream.setBCI(block.startBci);
229 while (stream.currentBCI() <= block.endBci) {
230 switch (stream.currentBC()) {
231 case LLOAD:
232 case DLOAD:
233 loadTwo(blockID, stream.readLocalIndex());
234 break;
235 case LLOAD_0:
236 case DLOAD_0:
237 loadTwo(blockID, 0);
238 break;
239 case LLOAD_1:
240 case DLOAD_1:
241 loadTwo(blockID, 1);
242 break;
243 case LLOAD_2:
244 case DLOAD_2:
245 loadTwo(blockID, 2);
246 break;
247 case LLOAD_3:
248 case DLOAD_3:
249 loadTwo(blockID, 3);
250 break;
251 case IINC:
252 localIndex = stream.readLocalIndex();
253 loadOne(blockID, localIndex);
254 storeOne(blockID, localIndex);
255 break;
256 case ILOAD:
257 case FLOAD:
258 case ALOAD:
259 case RET:
260 loadOne(blockID, stream.readLocalIndex());
261 break;
262 case ILOAD_0:
263 case FLOAD_0:
264 case ALOAD_0:
265 loadOne(blockID, 0);
266 break;
267 case ILOAD_1:
268 case FLOAD_1:
269 case ALOAD_1:
270 loadOne(blockID, 1);
271 break;
272 case ILOAD_2:
273 case FLOAD_2:
274 case ALOAD_2:
275 loadOne(blockID, 2);
276 break;
277 case ILOAD_3:
278 case FLOAD_3:
279 case ALOAD_3:
280 loadOne(blockID, 3);
281 break;
282
283 case LSTORE:
284 case DSTORE:
285 storeTwo(blockID, stream.readLocalIndex());
286 break;
287 case LSTORE_0:
288 case DSTORE_0:
289 storeTwo(blockID, 0);
290 break;
291 case LSTORE_1:
292 case DSTORE_1:
293 storeTwo(blockID, 1);
294 break;
295 case LSTORE_2:
296 case DSTORE_2:
297 storeTwo(blockID, 2);
298 break;
299 case LSTORE_3:
300 case DSTORE_3:
301 storeTwo(blockID, 3);
302 break;
303 case ISTORE:
304 case FSTORE:
305 case ASTORE:
306 storeOne(blockID, stream.readLocalIndex());
307 break;
308 case ISTORE_0:
309 case FSTORE_0:
310 case ASTORE_0:
311 storeOne(blockID, 0);
312 break;
313 case ISTORE_1:
314 case FSTORE_1:
315 case ASTORE_1:
316 storeOne(blockID, 1);
317 break;
318 case ISTORE_2:
319 case FSTORE_2:
320 case ASTORE_2:
321 storeOne(blockID, 2);
322 break;
323 case ISTORE_3:
324 case FSTORE_3:
325 case ASTORE_3:
326 storeOne(blockID, 3);
327 break;
328 }
329 stream.next();
330 }
331 }
332
333 private void loadTwo(int blockID, int local) {
334 loadOne(blockID, local);
335 loadOne(blockID, local + 1);
336 }
337
338 private void storeTwo(int blockID, int local) {
339 storeOne(blockID, local);
340 storeOne(blockID, local + 1);
341 }
342 }