/*
 * 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.
/**
 * 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.
/**
     * 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.
/**
         * Contains the register number for registers which can be optimized and -1 for the others.
         */
        int[] eligibleRegs;

        
A map from the StackSlot offset to an index into the state. StackSlots of different kinds that map to the same location will map to the same index. /**
         * 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.
/**
         * 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 mergeState (assuming a small number of iterations in solveDataFlow. /**
         * 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.
Returns:
Returns true on success and false if the the control flow is too complex./**
         * 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.
/**
         * 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.
/**
         * 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.
/**
         * 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.
/**
         * 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.
/**
         * 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.
/**
         * 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.
/**
         * 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;
        }
    }
}