| /* |
| * Copyright (c) 2013, 2016, 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.lir; |
| |
| import static jdk.vm.ci.code.ValueUtil.isRegister; |
| import static jdk.vm.ci.code.ValueUtil.isStackSlot; |
| |
| import java.util.Arrays; |
| import java.util.Collections; |
| import java.util.EnumSet; |
| import java.util.List; |
| import java.util.Map; |
| |
| import org.graalvm.compiler.core.common.CollectionsFactory; |
| import org.graalvm.compiler.core.common.LIRKind; |
| import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; |
| import org.graalvm.compiler.debug.Debug; |
| import org.graalvm.compiler.debug.DebugCounter; |
| import org.graalvm.compiler.debug.Indent; |
| import org.graalvm.compiler.lir.LIRInstruction.OperandFlag; |
| import org.graalvm.compiler.lir.LIRInstruction.OperandMode; |
| import org.graalvm.compiler.lir.StandardOp.MoveOp; |
| import org.graalvm.compiler.lir.StandardOp.ValueMoveOp; |
| import org.graalvm.compiler.lir.framemap.FrameMap; |
| import org.graalvm.compiler.lir.gen.LIRGenerationResult; |
| import org.graalvm.compiler.lir.phases.PostAllocationOptimizationPhase; |
| |
| import jdk.vm.ci.code.Register; |
| import jdk.vm.ci.code.RegisterArray; |
| import jdk.vm.ci.code.RegisterValue; |
| import jdk.vm.ci.code.StackSlot; |
| import jdk.vm.ci.code.TargetDescription; |
| import jdk.vm.ci.meta.Value; |
| |
| /** |
| * Removes move instructions, where the destination value is already in place. |
| */ |
| public final class RedundantMoveElimination extends PostAllocationOptimizationPhase { |
| |
| private static final DebugCounter deletedMoves = Debug.counter("RedundantMovesEliminated"); |
| |
| @Override |
| protected void run(TargetDescription target, LIRGenerationResult lirGenRes, PostAllocationOptimizationContext context) { |
| Optimization redundantMoveElimination = new Optimization(lirGenRes.getFrameMap()); |
| redundantMoveElimination.doOptimize(lirGenRes.getLIR()); |
| } |
| |
| /** |
| * Holds the entry and exit states for each block for dataflow analysis. The state is an array |
| * with an element for each relevant location (register or stack slot). Each element holds the |
| * global number of the location's definition. A location definition is simply an output of an |
| * instruction. Note that because instructions can have multiple outputs it is not possible to |
| * use the instruction id for value numbering. In addition, the result of merging at block |
| * entries (= phi values) get unique value numbers. |
| * |
| * The value numbers also contain information if it is an object kind value or not: if the |
| * number is negative it is an object kind value. |
| */ |
| private static final class BlockData { |
| |
| BlockData(int stateSize) { |
| entryState = new int[stateSize]; |
| exitState = new int[stateSize]; |
| } |
| |
| /* |
| * The state at block entry for global dataflow analysis. It contains a global value number |
| * for each location to optimize. |
| */ |
| int[] entryState; |
| |
| /* |
| * The state at block exit for global dataflow analysis. It contains a global value number |
| * for each location to optimize. |
| */ |
| int[] exitState; |
| |
| /* |
| * The starting number for global value numbering in this block. |
| */ |
| int entryValueNum; |
| } |
| |
| private static final class Optimization { |
| |
| Map<AbstractBlockBase<?>, BlockData> blockData = CollectionsFactory.newMap(); |
| |
| RegisterArray callerSaveRegs; |
| |
| /** |
| * Contains the register number for registers which can be optimized and -1 for the others. |
| */ |
| int[] eligibleRegs; |
| |
| /** |
| * A map from the {@link StackSlot} {@link #getOffset offset} to an index into the state. |
| * StackSlots of different kinds that map to the same location will map to the same index. |
| */ |
| Map<Integer, Integer> stackIndices = CollectionsFactory.newMap(); |
| |
| int numRegs; |
| |
| private final FrameMap frameMap; |
| |
| /* |
| * Pseudo value for a not yet assigned location. |
| */ |
| static final int INIT_VALUE = 0; |
| |
| Optimization(FrameMap frameMap) { |
| this.frameMap = frameMap; |
| } |
| |
| /** |
| * The main method doing the elimination of redundant moves. |
| */ |
| @SuppressWarnings("try") |
| private void doOptimize(LIR lir) { |
| |
| try (Indent indent = Debug.logAndIndent("eliminate redundant moves")) { |
| |
| callerSaveRegs = frameMap.getRegisterConfig().getCallerSaveRegisters(); |
| |
| initBlockData(lir); |
| |
| // Compute a table of the registers which are eligible for move optimization. |
| // Unallocatable registers should never be optimized. |
| eligibleRegs = new int[numRegs]; |
| Arrays.fill(eligibleRegs, -1); |
| for (Register reg : frameMap.getRegisterConfig().getAllocatableRegisters()) { |
| if (reg.number < numRegs) { |
| eligibleRegs[reg.number] = reg.number; |
| } |
| } |
| |
| if (!solveDataFlow(lir)) { |
| return; |
| } |
| |
| eliminateMoves(lir); |
| } |
| } |
| |
| /** |
| * The maximum number of locations * blocks. This is a complexity limit for the inner loop |
| * in {@link #mergeState} (assuming a small number of iterations in {@link #solveDataFlow}. |
| */ |
| private static final int COMPLEXITY_LIMIT = 30000; |
| |
| private void initBlockData(LIR lir) { |
| |
| AbstractBlockBase<?>[] blocks = lir.linearScanOrder(); |
| numRegs = 0; |
| |
| int maxStackLocations = COMPLEXITY_LIMIT / blocks.length; |
| |
| /* |
| * Search for relevant locations which can be optimized. These are register or stack |
| * slots which occur as destinations of move instructions. |
| */ |
| for (AbstractBlockBase<?> block : blocks) { |
| List<LIRInstruction> instructions = lir.getLIRforBlock(block); |
| for (LIRInstruction op : instructions) { |
| if (isEligibleMove(op)) { |
| Value dest = ((MoveOp) op).getResult(); |
| if (isRegister(dest)) { |
| int regNum = ((RegisterValue) dest).getRegister().number; |
| if (regNum >= numRegs) { |
| numRegs = regNum + 1; |
| } |
| } else if (isStackSlot(dest)) { |
| StackSlot stackSlot = (StackSlot) dest; |
| Integer offset = getOffset(stackSlot); |
| if (!stackIndices.containsKey(offset) && stackIndices.size() < maxStackLocations) { |
| stackIndices.put(offset, stackIndices.size()); |
| } |
| } |
| } |
| } |
| } |
| |
| /* |
| * Now we know the number of locations to optimize, so we can allocate the block states. |
| */ |
| int numLocations = numRegs + stackIndices.size(); |
| Debug.log("num locations = %d (regs = %d, stack = %d)", numLocations, numRegs, stackIndices.size()); |
| for (AbstractBlockBase<?> block : blocks) { |
| BlockData data = new BlockData(numLocations); |
| blockData.put(block, data); |
| } |
| } |
| |
| private int getOffset(StackSlot stackSlot) { |
| return stackSlot.getOffset(frameMap.totalFrameSize()); |
| } |
| |
| /** |
| * Calculates the entry and exit states for all basic blocks. |
| * |
| * @return Returns true on success and false if the the control flow is too complex. |
| */ |
| @SuppressWarnings("try") |
| private boolean solveDataFlow(LIR lir) { |
| |
| try (Indent indent = Debug.logAndIndent("solve data flow")) { |
| |
| AbstractBlockBase<?>[] blocks = lir.linearScanOrder(); |
| |
| int numIter = 0; |
| |
| /* |
| * Iterate until there are no more changes. |
| */ |
| int currentValueNum = 1; |
| boolean firstRound = true; |
| boolean changed; |
| do { |
| changed = false; |
| try (Indent indent2 = Debug.logAndIndent("new iteration")) { |
| |
| for (AbstractBlockBase<?> block : blocks) { |
| |
| BlockData data = blockData.get(block); |
| /* |
| * Initialize the number for global value numbering for this block. It |
| * is essential that the starting number for a block is consistent at |
| * all iterations and also in eliminateMoves(). |
| */ |
| if (firstRound) { |
| data.entryValueNum = currentValueNum; |
| } |
| int valueNum = data.entryValueNum; |
| assert valueNum > 0; |
| boolean newState = false; |
| |
| if (block == blocks[0] || block.isExceptionEntry()) { |
| /* |
| * The entry block has undefined values. And also exception handler |
| * blocks: the LinearScan can insert moves at the end of an |
| * exception handler predecessor block (after the invoke, which |
| * throws the exception), and in reality such moves are not in the |
| * control flow in case of an exception. So we assume a save default |
| * for exception handler blocks. |
| */ |
| Debug.log("kill all values at entry of block %d", block.getId()); |
| clearValues(data.entryState, valueNum); |
| } else { |
| /* |
| * Merge the states of predecessor blocks |
| */ |
| for (AbstractBlockBase<?> predecessor : block.getPredecessors()) { |
| BlockData predData = blockData.get(predecessor); |
| newState |= mergeState(data.entryState, predData.exitState, valueNum); |
| } |
| } |
| // Advance by the value numbers which are "consumed" by |
| // clearValues and mergeState |
| valueNum += data.entryState.length; |
| |
| if (newState || firstRound) { |
| try (Indent indent3 = Debug.logAndIndent("update block %d", block.getId())) { |
| |
| /* |
| * Derive the exit state from the entry state by iterating |
| * through all instructions of the block. |
| */ |
| int[] iterState = data.exitState; |
| copyState(iterState, data.entryState); |
| List<LIRInstruction> instructions = lir.getLIRforBlock(block); |
| |
| for (LIRInstruction op : instructions) { |
| valueNum = updateState(iterState, op, valueNum); |
| } |
| changed = true; |
| } |
| } |
| if (firstRound) { |
| currentValueNum = valueNum; |
| } |
| } |
| firstRound = false; |
| } |
| numIter++; |
| |
| if (numIter > 5) { |
| /* |
| * This is _very_ seldom. |
| */ |
| return false; |
| } |
| |
| } while (changed); |
| |
| } |
| |
| return true; |
| } |
| |
| /** |
| * Deletes all move instructions where the target location already contains the source |
| * value. |
| */ |
| @SuppressWarnings("try") |
| private void eliminateMoves(LIR lir) { |
| |
| try (Indent indent = Debug.logAndIndent("eliminate moves")) { |
| |
| AbstractBlockBase<?>[] blocks = lir.linearScanOrder(); |
| |
| for (AbstractBlockBase<?> block : blocks) { |
| |
| try (Indent indent2 = Debug.logAndIndent("eliminate moves in block %d", block.getId())) { |
| |
| List<LIRInstruction> instructions = lir.getLIRforBlock(block); |
| BlockData data = blockData.get(block); |
| boolean hasDead = false; |
| |
| // Reuse the entry state for iteration, we don't need it later. |
| int[] iterState = data.entryState; |
| |
| // Add the values which are "consumed" by clearValues and |
| // mergeState in solveDataFlow |
| int valueNum = data.entryValueNum + data.entryState.length; |
| |
| int numInsts = instructions.size(); |
| for (int idx = 0; idx < numInsts; idx++) { |
| LIRInstruction op = instructions.get(idx); |
| if (isEligibleMove(op)) { |
| ValueMoveOp moveOp = (ValueMoveOp) op; |
| int sourceIdx = getStateIdx(moveOp.getInput()); |
| int destIdx = getStateIdx(moveOp.getResult()); |
| if (sourceIdx >= 0 && destIdx >= 0 && iterState[sourceIdx] == iterState[destIdx]) { |
| assert iterState[sourceIdx] != INIT_VALUE; |
| Debug.log("delete move %s", op); |
| instructions.set(idx, null); |
| hasDead = true; |
| if (deletedMoves.isEnabled()) { |
| deletedMoves.increment(); |
| } |
| } |
| } |
| // It doesn't harm if updateState is also called for a deleted move |
| valueNum = updateState(iterState, op, valueNum); |
| } |
| if (hasDead) { |
| instructions.removeAll(Collections.singleton(null)); |
| } |
| } |
| } |
| } |
| } |
| |
| /** |
| * Updates the state for one instruction. |
| */ |
| @SuppressWarnings("try") |
| private int updateState(final int[] state, LIRInstruction op, int initValueNum) { |
| |
| try (final Indent indent = Debug.logAndIndent("update state for op %s, initial value num = %d", op, initValueNum)) { |
| if (isEligibleMove(op)) { |
| /* |
| * Handle the special case of a move instruction |
| */ |
| ValueMoveOp moveOp = (ValueMoveOp) op; |
| int sourceIdx = getStateIdx(moveOp.getInput()); |
| int destIdx = getStateIdx(moveOp.getResult()); |
| if (sourceIdx >= 0 && destIdx >= 0) { |
| assert isObjectValue(state[sourceIdx]) || LIRKind.isValue(moveOp.getInput()) : "move op moves object but input is not defined as object"; |
| state[destIdx] = state[sourceIdx]; |
| Debug.log("move value %d from %d to %d", state[sourceIdx], sourceIdx, destIdx); |
| return initValueNum; |
| } |
| } |
| |
| int valueNum = initValueNum; |
| |
| if (op.destroysCallerSavedRegisters()) { |
| Debug.log("kill all caller save regs"); |
| |
| for (Register reg : callerSaveRegs) { |
| if (reg.number < numRegs) { |
| // Kind.Object is the save default |
| state[reg.number] = encodeValueNum(valueNum++, true); |
| } |
| } |
| } |
| |
| /* |
| * Value procedure for the instruction's output and temp values |
| */ |
| class OutputValueConsumer implements ValueConsumer { |
| |
| int opValueNum; |
| |
| OutputValueConsumer(int opValueNum) { |
| this.opValueNum = opValueNum; |
| } |
| |
| @Override |
| public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { |
| int stateIdx = getStateIdx(operand); |
| if (stateIdx >= 0) { |
| /* |
| * Assign a unique number to the output or temp location. |
| */ |
| state[stateIdx] = encodeValueNum(opValueNum++, !LIRKind.isValue(operand)); |
| Debug.log("set def %d for register %s(%d): %d", opValueNum, operand, stateIdx, state[stateIdx]); |
| } |
| } |
| } |
| |
| OutputValueConsumer outputValueConsumer = new OutputValueConsumer(valueNum); |
| |
| op.visitEachTemp(outputValueConsumer); |
| /* |
| * Semantically the output values are written _after_ the temp values |
| */ |
| op.visitEachOutput(outputValueConsumer); |
| |
| valueNum = outputValueConsumer.opValueNum; |
| |
| if (op.hasState()) { |
| /* |
| * All instructions with framestates (mostly method calls), may do garbage |
| * collection. GC will rewrite all object references which are live at this |
| * point. So we can't rely on their values. It would be sufficient to just kill |
| * all values which are referenced in the state (or all values which are not), |
| * but for simplicity we kill all values. |
| */ |
| Debug.log("kill all object values"); |
| clearValuesOfKindObject(state, valueNum); |
| valueNum += state.length; |
| } |
| |
| return valueNum; |
| } |
| } |
| |
| /** |
| * The state merge function for dataflow joins. |
| */ |
| private static boolean mergeState(int[] dest, int[] source, int defNum) { |
| assert dest.length == source.length; |
| boolean changed = false; |
| for (int idx = 0; idx < source.length; idx++) { |
| int phiNum = defNum + idx; |
| int dst = dest[idx]; |
| int src = source[idx]; |
| if (dst != src && src != INIT_VALUE && dst != encodeValueNum(phiNum, isObjectValue(dst))) { |
| if (dst != INIT_VALUE) { |
| dst = encodeValueNum(phiNum, isObjectValue(dst) || isObjectValue(src)); |
| } else { |
| dst = src; |
| } |
| dest[idx] = dst; |
| changed = true; |
| } |
| } |
| return changed; |
| } |
| |
| private static void copyState(int[] dest, int[] source) { |
| assert dest.length == source.length; |
| for (int idx = 0; idx < source.length; idx++) { |
| dest[idx] = source[idx]; |
| } |
| } |
| |
| private static void clearValues(int[] state, int defNum) { |
| for (int idx = 0; idx < state.length; idx++) { |
| int phiNum = defNum + idx; |
| // Let the killed values assume to be object references: it's the save default. |
| state[idx] = encodeValueNum(phiNum, true); |
| } |
| } |
| |
| private static void clearValuesOfKindObject(int[] state, int defNum) { |
| for (int idx = 0; idx < state.length; idx++) { |
| int phiNum = defNum + idx; |
| if (isObjectValue(state[idx])) { |
| state[idx] = encodeValueNum(phiNum, true); |
| } |
| } |
| } |
| |
| /** |
| * Returns the index to the state arrays in BlockData for a specific location. |
| */ |
| private int getStateIdx(Value location) { |
| if (isRegister(location)) { |
| int regNum = ((RegisterValue) location).getRegister().number; |
| if (regNum < numRegs) { |
| return eligibleRegs[regNum]; |
| } |
| return -1; |
| } |
| if (isStackSlot(location)) { |
| StackSlot slot = (StackSlot) location; |
| Integer index = stackIndices.get(getOffset(slot)); |
| if (index != null) { |
| return index.intValue() + numRegs; |
| } |
| } |
| return -1; |
| } |
| |
| /** |
| * Encodes a value number + the is-object information to a number to be stored in a state. |
| */ |
| private static int encodeValueNum(int valueNum, boolean isObjectKind) { |
| assert valueNum > 0; |
| if (isObjectKind) { |
| return -valueNum; |
| } |
| return valueNum; |
| } |
| |
| /** |
| * Returns true if an encoded value number (which is stored in a state) refers to an object |
| * reference. |
| */ |
| private static boolean isObjectValue(int encodedValueNum) { |
| return encodedValueNum < 0; |
| } |
| |
| /** |
| * Returns true for a move instruction which is a candidate for elimination. |
| */ |
| private static boolean isEligibleMove(LIRInstruction op) { |
| if (op instanceof ValueMoveOp) { |
| ValueMoveOp moveOp = (ValueMoveOp) op; |
| Value source = moveOp.getInput(); |
| Value dest = moveOp.getResult(); |
| /* |
| * Moves with mismatching kinds are not moves, but memory loads/stores! |
| */ |
| return source.getValueKind().equals(dest.getValueKind()); |
| } |
| return false; |
| } |
| } |
| } |
