001/*
002 * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.java;
024
025import static com.oracle.graal.bytecode.Bytecodes.*;
026import com.oracle.graal.debug.*;
027
028import com.oracle.graal.bytecode.*;
029import com.oracle.graal.java.BciBlockMapping.BciBlock;
030
031/**
032 * Encapsulates the liveness calculation, so that subclasses for locals ≤ 64 and locals > 64
033 * can be implemented.
034 */
035public abstract class LocalLiveness {
036    protected final BciBlock[] blocks;
037
038    public static LocalLiveness compute(BytecodeStream stream, BciBlock[] blocks, int maxLocals, int loopCount) {
039        LocalLiveness liveness = maxLocals <= 64 ? new SmallLocalLiveness(blocks, maxLocals, loopCount) : new LargeLocalLiveness(blocks, maxLocals, loopCount);
040        liveness.computeLiveness(stream);
041        return liveness;
042    }
043
044    protected LocalLiveness(BciBlock[] blocks) {
045        this.blocks = blocks;
046    }
047
048    void computeLiveness(BytecodeStream stream) {
049        for (BciBlock block : blocks) {
050            computeLocalLiveness(stream, block);
051        }
052
053        boolean changed;
054        int iteration = 0;
055        do {
056            assert traceIteration(iteration);
057            changed = false;
058            for (int i = blocks.length - 1; i >= 0; i--) {
059                BciBlock block = blocks[i];
060                int blockID = block.getId();
061                assert traceStart(block, blockID);
062
063                boolean blockChanged = (iteration == 0);
064                if (block.getSuccessorCount() > 0) {
065                    int oldCardinality = liveOutCardinality(blockID);
066                    for (BciBlock sux : block.getSuccessors()) {
067                        assert traceSuccessor(sux);
068                        propagateLiveness(blockID, sux.getId());
069                    }
070                    blockChanged |= (oldCardinality != liveOutCardinality(blockID));
071                }
072
073                if (blockChanged) {
074                    updateLiveness(blockID);
075                    assert traceEnd(block, blockID);
076                }
077                changed |= blockChanged;
078            }
079            iteration++;
080        } while (changed);
081    }
082
083    private static boolean traceIteration(int iteration) {
084        Debug.log("Iteration %d", iteration);
085        return true;
086    }
087
088    private boolean traceEnd(BciBlock block, int blockID) {
089        if (Debug.isLogEnabled()) {
090            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),
091                            debugLiveKill(blockID));
092        }
093        return true;
094    }
095
096    private boolean traceSuccessor(BciBlock sux) {
097        if (Debug.isLogEnabled()) {
098            Debug.log("    Successor B%d: %s", sux.getId(), debugLiveIn(sux.getId()));
099        }
100        return true;
101    }
102
103    private boolean traceStart(BciBlock block, int blockID) {
104        if (Debug.isLogEnabled()) {
105            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),
106                            debugLiveKill(blockID));
107        }
108        return true;
109    }
110
111    /**
112     * Returns whether the local is live at the beginning of the given block.
113     */
114    public abstract boolean localIsLiveIn(BciBlock block, int local);
115
116    /**
117     * Returns whether the local is set in the given loop.
118     */
119    public abstract boolean localIsChangedInLoop(int loopId, int local);
120
121    /**
122     * Returns whether the local is live at the end of the given block.
123     */
124    public abstract boolean localIsLiveOut(BciBlock block, int local);
125
126    /**
127     * Returns a string representation of the liveIn values of the given block.
128     */
129    protected abstract String debugLiveIn(int blockID);
130
131    /**
132     * Returns a string representation of the liveOut values of the given block.
133     */
134    protected abstract String debugLiveOut(int blockID);
135
136    /**
137     * Returns a string representation of the liveGen values of the given block.
138     */
139    protected abstract String debugLiveGen(int blockID);
140
141    /**
142     * Returns a string representation of the liveKill values of the given block.
143     */
144    protected abstract String debugLiveKill(int blockID);
145
146    /**
147     * Returns the number of live locals at the end of the given block.
148     */
149    protected abstract int liveOutCardinality(int blockID);
150
151    /**
152     * Adds all locals the are in the liveIn of the successor to the liveOut of the block.
153     */
154    protected abstract void propagateLiveness(int blockID, int successorID);
155
156    /**
157     * Calculates a new liveIn for the given block from liveOut, liveKill and liveGen.
158     */
159    protected abstract void updateLiveness(int blockID);
160
161    /**
162     * Adds the local to liveGen if it wasn't already killed in this block.
163     */
164    protected abstract void loadOne(int blockID, int local);
165
166    /**
167     * Add this local to liveKill if it wasn't already generated in this block.
168     */
169    protected abstract void storeOne(int blockID, int local);
170
171    private void computeLocalLiveness(BytecodeStream stream, BciBlock block) {
172        if (block.startBci < 0 || block.endBci < 0) {
173            return;
174        }
175        int blockID = block.getId();
176        int localIndex;
177        stream.setBCI(block.startBci);
178        while (stream.currentBCI() <= block.endBci) {
179            switch (stream.currentBC()) {
180                case LLOAD:
181                case DLOAD:
182                    loadTwo(blockID, stream.readLocalIndex());
183                    break;
184                case LLOAD_0:
185                case DLOAD_0:
186                    loadTwo(blockID, 0);
187                    break;
188                case LLOAD_1:
189                case DLOAD_1:
190                    loadTwo(blockID, 1);
191                    break;
192                case LLOAD_2:
193                case DLOAD_2:
194                    loadTwo(blockID, 2);
195                    break;
196                case LLOAD_3:
197                case DLOAD_3:
198                    loadTwo(blockID, 3);
199                    break;
200                case IINC:
201                    localIndex = stream.readLocalIndex();
202                    loadOne(blockID, localIndex);
203                    storeOne(blockID, localIndex);
204                    break;
205                case ILOAD:
206                case FLOAD:
207                case ALOAD:
208                case RET:
209                    loadOne(blockID, stream.readLocalIndex());
210                    break;
211                case ILOAD_0:
212                case FLOAD_0:
213                case ALOAD_0:
214                    loadOne(blockID, 0);
215                    break;
216                case ILOAD_1:
217                case FLOAD_1:
218                case ALOAD_1:
219                    loadOne(blockID, 1);
220                    break;
221                case ILOAD_2:
222                case FLOAD_2:
223                case ALOAD_2:
224                    loadOne(blockID, 2);
225                    break;
226                case ILOAD_3:
227                case FLOAD_3:
228                case ALOAD_3:
229                    loadOne(blockID, 3);
230                    break;
231
232                case LSTORE:
233                case DSTORE:
234                    storeTwo(blockID, stream.readLocalIndex());
235                    break;
236                case LSTORE_0:
237                case DSTORE_0:
238                    storeTwo(blockID, 0);
239                    break;
240                case LSTORE_1:
241                case DSTORE_1:
242                    storeTwo(blockID, 1);
243                    break;
244                case LSTORE_2:
245                case DSTORE_2:
246                    storeTwo(blockID, 2);
247                    break;
248                case LSTORE_3:
249                case DSTORE_3:
250                    storeTwo(blockID, 3);
251                    break;
252                case ISTORE:
253                case FSTORE:
254                case ASTORE:
255                    storeOne(blockID, stream.readLocalIndex());
256                    break;
257                case ISTORE_0:
258                case FSTORE_0:
259                case ASTORE_0:
260                    storeOne(blockID, 0);
261                    break;
262                case ISTORE_1:
263                case FSTORE_1:
264                case ASTORE_1:
265                    storeOne(blockID, 1);
266                    break;
267                case ISTORE_2:
268                case FSTORE_2:
269                case ASTORE_2:
270                    storeOne(blockID, 2);
271                    break;
272                case ISTORE_3:
273                case FSTORE_3:
274                case ASTORE_3:
275                    storeOne(blockID, 3);
276                    break;
277            }
278            stream.next();
279        }
280    }
281
282    private void loadTwo(int blockID, int local) {
283        loadOne(blockID, local);
284        loadOne(blockID, local + 1);
285    }
286
287    private void storeTwo(int blockID, int local) {
288        storeOne(blockID, local);
289        storeOne(blockID, local + 1);
290    }
291}