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 */
23package org.graalvm.compiler.java;
24
25import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD;
26import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_0;
27import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_1;
28import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_2;
29import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_3;
30import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE;
31import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_0;
32import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_1;
33import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_2;
34import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_3;
35import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD;
36import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_0;
37import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_1;
38import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_2;
39import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_3;
40import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE;
41import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_0;
42import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_1;
43import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_2;
44import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_3;
45import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD;
46import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_0;
47import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_1;
48import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_2;
49import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_3;
50import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE;
51import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_0;
52import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_1;
53import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_2;
54import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_3;
55import static org.graalvm.compiler.bytecode.Bytecodes.IINC;
56import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD;
57import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_0;
58import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_1;
59import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_2;
60import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_3;
61import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE;
62import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_0;
63import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_1;
64import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_2;
65import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_3;
66import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD;
67import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_0;
68import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_1;
69import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_2;
70import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_3;
71import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE;
72import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_0;
73import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_1;
74import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_2;
75import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_3;
76import static org.graalvm.compiler.bytecode.Bytecodes.RET;
77
78import org.graalvm.compiler.bytecode.BytecodeStream;
79import org.graalvm.compiler.debug.DebugContext;
80import 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 */
86public abstract class LocalLiveness {
87    protected final BciBlock[] blocks;
88
89    public static LocalLiveness compute(DebugContext debug, 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(debug, stream);
92        return liveness;
93    }
94
95    protected LocalLiveness(BciBlock[] blocks) {
96        this.blocks = blocks;
97    }
98
99    void computeLiveness(DebugContext debug, 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(debug, 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(debug, 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(debug, sux);
119                        propagateLiveness(blockID, sux.getId());
120                    }
121                    blockChanged |= (oldCardinality != liveOutCardinality(blockID));
122                }
123
124                if (blockChanged) {
125                    updateLiveness(blockID);
126                    assert traceEnd(debug, block, blockID);
127                }
128                changed |= blockChanged;
129            }
130            iteration++;
131        } while (changed);
132    }
133
134    private static boolean traceIteration(DebugContext debug, int iteration) {
135        debug.log("Iteration %d", iteration);
136        return true;
137    }
138
139    private boolean traceEnd(DebugContext debug, 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(DebugContext debug, 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(DebugContext debug, 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}
343