/*
 * Copyright (c) 2009, 2018, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */


package org.graalvm.compiler.java;

import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD;
import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_0;
import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_1;
import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_2;
import static org.graalvm.compiler.bytecode.Bytecodes.ALOAD_3;
import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE;
import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_0;
import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_1;
import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_2;
import static org.graalvm.compiler.bytecode.Bytecodes.ASTORE_3;
import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD;
import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_0;
import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_1;
import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_2;
import static org.graalvm.compiler.bytecode.Bytecodes.DLOAD_3;
import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE;
import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_0;
import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_1;
import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_2;
import static org.graalvm.compiler.bytecode.Bytecodes.DSTORE_3;
import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD;
import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_0;
import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_1;
import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_2;
import static org.graalvm.compiler.bytecode.Bytecodes.FLOAD_3;
import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE;
import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_0;
import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_1;
import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_2;
import static org.graalvm.compiler.bytecode.Bytecodes.FSTORE_3;
import static org.graalvm.compiler.bytecode.Bytecodes.IINC;
import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD;
import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_0;
import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_1;
import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_2;
import static org.graalvm.compiler.bytecode.Bytecodes.ILOAD_3;
import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE;
import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_0;
import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_1;
import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_2;
import static org.graalvm.compiler.bytecode.Bytecodes.ISTORE_3;
import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD;
import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_0;
import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_1;
import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_2;
import static org.graalvm.compiler.bytecode.Bytecodes.LLOAD_3;
import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE;
import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_0;
import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_1;
import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_2;
import static org.graalvm.compiler.bytecode.Bytecodes.LSTORE_3;
import static org.graalvm.compiler.bytecode.Bytecodes.RET;

import org.graalvm.compiler.bytecode.BytecodeStream;
import org.graalvm.compiler.debug.DebugContext;
import org.graalvm.compiler.java.BciBlockMapping.BciBlock;

Encapsulates the liveness calculation, so that subclasses for locals ≤ 64 and locals > 64 can be implemented.
/** * Encapsulates the liveness calculation, so that subclasses for locals ≤ 64 and locals > 64 * can be implemented. */
public abstract class LocalLiveness { protected final BciBlock[] blocks; public static LocalLiveness compute(DebugContext debug, BytecodeStream stream, BciBlock[] blocks, int maxLocals, int loopCount) { LocalLiveness liveness = maxLocals <= 64 ? new SmallLocalLiveness(blocks, maxLocals, loopCount) : new LargeLocalLiveness(blocks, maxLocals, loopCount); liveness.computeLiveness(debug, stream); return liveness; } protected LocalLiveness(BciBlock[] blocks) { this.blocks = blocks; } void computeLiveness(DebugContext debug, BytecodeStream stream) { for (BciBlock block : blocks) { computeLocalLiveness(stream, block); } boolean changed; int iteration = 0; do { assert traceIteration(debug, iteration); changed = false; for (int i = blocks.length - 1; i >= 0; i--) { BciBlock block = blocks[i]; int blockID = block.getId(); assert traceStart(debug, block, blockID); boolean blockChanged = (iteration == 0); if (block.getSuccessorCount() > 0) { int oldCardinality = liveOutCardinality(blockID); for (BciBlock sux : block.getSuccessors()) { assert traceSuccessor(debug, sux); propagateLiveness(blockID, sux.getId()); } blockChanged |= (oldCardinality != liveOutCardinality(blockID)); } if (blockChanged) { updateLiveness(blockID); assert traceEnd(debug, block, blockID); } changed |= blockChanged; } iteration++; } while (changed); } private static boolean traceIteration(DebugContext debug, int iteration) { debug.log("Iteration %d", iteration); return true; } private boolean traceEnd(DebugContext debug, BciBlock block, int blockID) { if (debug.isLogEnabled()) { 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), debugLiveKill(blockID)); } return true; } private boolean traceSuccessor(DebugContext debug, BciBlock sux) { if (debug.isLogEnabled()) { debug.log(" Successor B%d: %s", sux.getId(), debugLiveIn(sux.getId())); } return true; } private boolean traceStart(DebugContext debug, BciBlock block, int blockID) { if (debug.isLogEnabled()) { 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), debugLiveKill(blockID)); } return true; }
Returns whether the local is live at the beginning of the given block.
/** * Returns whether the local is live at the beginning of the given block. */
public abstract boolean localIsLiveIn(BciBlock block, int local);
Returns whether the local is set in the given loop.
/** * Returns whether the local is set in the given loop. */
public abstract boolean localIsChangedInLoop(int loopId, int local);
Returns whether the local is live at the end of the given block.
/** * Returns whether the local is live at the end of the given block. */
public abstract boolean localIsLiveOut(BciBlock block, int local);
Returns a string representation of the liveIn values of the given block.
/** * Returns a string representation of the liveIn values of the given block. */
protected abstract String debugLiveIn(int blockID);
Returns a string representation of the liveOut values of the given block.
/** * Returns a string representation of the liveOut values of the given block. */
protected abstract String debugLiveOut(int blockID);
Returns a string representation of the liveGen values of the given block.
/** * Returns a string representation of the liveGen values of the given block. */
protected abstract String debugLiveGen(int blockID);
Returns a string representation of the liveKill values of the given block.
/** * Returns a string representation of the liveKill values of the given block. */
protected abstract String debugLiveKill(int blockID);
Returns the number of live locals at the end of the given block.
/** * Returns the number of live locals at the end of the given block. */
protected abstract int liveOutCardinality(int blockID);
Adds all locals the are in the liveIn of the successor to the liveOut of the block.
/** * Adds all locals the are in the liveIn of the successor to the liveOut of the block. */
protected abstract void propagateLiveness(int blockID, int successorID);
Calculates a new liveIn for the given block from liveOut, liveKill and liveGen.
/** * Calculates a new liveIn for the given block from liveOut, liveKill and liveGen. */
protected abstract void updateLiveness(int blockID);
Adds the local to liveGen if it wasn't already killed in this block.
/** * Adds the local to liveGen if it wasn't already killed in this block. */
protected abstract void loadOne(int blockID, int local);
Add this local to liveKill if it wasn't already generated in this block.
/** * Add this local to liveKill if it wasn't already generated in this block. */
protected abstract void storeOne(int blockID, int local); private void computeLocalLiveness(BytecodeStream stream, BciBlock block) { if (block.isExceptionDispatch()) { return; } int blockID = block.getId(); int localIndex; stream.setBCI(block.startBci); while (stream.currentBCI() <= block.endBci) { switch (stream.currentBC()) { case LLOAD: case DLOAD: loadTwo(blockID, stream.readLocalIndex()); break; case LLOAD_0: case DLOAD_0: loadTwo(blockID, 0); break; case LLOAD_1: case DLOAD_1: loadTwo(blockID, 1); break; case LLOAD_2: case DLOAD_2: loadTwo(blockID, 2); break; case LLOAD_3: case DLOAD_3: loadTwo(blockID, 3); break; case IINC: localIndex = stream.readLocalIndex(); loadOne(blockID, localIndex); storeOne(blockID, localIndex); break; case ILOAD: case FLOAD: case ALOAD: case RET: loadOne(blockID, stream.readLocalIndex()); break; case ILOAD_0: case FLOAD_0: case ALOAD_0: loadOne(blockID, 0); break; case ILOAD_1: case FLOAD_1: case ALOAD_1: loadOne(blockID, 1); break; case ILOAD_2: case FLOAD_2: case ALOAD_2: loadOne(blockID, 2); break; case ILOAD_3: case FLOAD_3: case ALOAD_3: loadOne(blockID, 3); break; case LSTORE: case DSTORE: storeTwo(blockID, stream.readLocalIndex()); break; case LSTORE_0: case DSTORE_0: storeTwo(blockID, 0); break; case LSTORE_1: case DSTORE_1: storeTwo(blockID, 1); break; case LSTORE_2: case DSTORE_2: storeTwo(blockID, 2); break; case LSTORE_3: case DSTORE_3: storeTwo(blockID, 3); break; case ISTORE: case FSTORE: case ASTORE: storeOne(blockID, stream.readLocalIndex()); break; case ISTORE_0: case FSTORE_0: case ASTORE_0: storeOne(blockID, 0); break; case ISTORE_1: case FSTORE_1: case ASTORE_1: storeOne(blockID, 1); break; case ISTORE_2: case FSTORE_2: case ASTORE_2: storeOne(blockID, 2); break; case ISTORE_3: case FSTORE_3: case ASTORE_3: storeOne(blockID, 3); break; } stream.next(); } } private void loadTwo(int blockID, int local) { loadOne(blockID, local); loadOne(blockID, local + 1); } private void storeTwo(int blockID, int local) { storeOne(blockID, local); storeOne(blockID, local + 1); } }