/*
 * Copyright (c) 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.ssi;

import static org.graalvm.compiler.lir.LIRValueUtil.asVariable;
import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;

import java.util.BitSet;
import java.util.EnumSet;
import java.util.List;
import java.util.ListIterator;

import org.graalvm.compiler.common.PermanentBailoutException;
import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
import org.graalvm.compiler.core.common.cfg.BlockMap;
import org.graalvm.compiler.debug.Debug;
import org.graalvm.compiler.debug.GraalError;
import org.graalvm.compiler.debug.Indent;
import org.graalvm.compiler.lir.InstructionValueConsumer;
import org.graalvm.compiler.lir.LIR;
import org.graalvm.compiler.lir.LIRInstruction;
import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
import org.graalvm.compiler.lir.LIRInstruction.OperandMode;

import jdk.vm.ci.meta.Value;

public final class SSIBuilder extends SSIBuilderBase {

    private static class BlockData {

        
Bit map specifying which operands are live upon entry to this block. These are values used in this block or any of its successors where such value are not defined in this block. The bit index of an operand is its operand number. /**
         * Bit map specifying which operands are live upon entry to this block. These are values
         * used in this block or any of its successors where such value are not defined in this
         * block. The bit index of an operand is its {@linkplain #operandNumber operand number}.
         */
        public BitSet liveIn;

        
Bit map specifying which operands are live upon exit from this block. These are values used in a successor block that are either defined in this block or were live upon entry to this block. The bit index of an operand is its operand
number. /**
         * Bit map specifying which operands are live upon exit from this block. These are values
         * used in a successor block that are either defined in this block or were live upon entry
         * to this block. The bit index of an operand is its {@linkplain #operandNumber operand
         * number}.
         */
        public BitSet liveOut;

        
Bit map specifying which operands are used (before being defined) in this block. That is, these are the values that are live upon entry to the block. The bit index of an operand is its operand number. /**
         * Bit map specifying which operands are used (before being defined) in this block. That is,
         * these are the values that are live upon entry to the block. The bit index of an operand
         * is its {@linkplain #operandNumber operand number}.
         */
        public BitSet liveGen;

        
Bit map specifying which operands are defined/overwritten in this block. The bit index of an operand is its operand number. /**
         * Bit map specifying which operands are defined/overwritten in this block. The bit index of
         * an operand is its {@linkplain #operandNumber operand number}.
         */
        public BitSet liveKill;
    }

    private final BlockMap<SSIBuilder.BlockData> blockData;

    protected SSIBuilder(LIR lir) {
        super(lir);
        this.blockData = new BlockMap<>(lir.getControlFlowGraph());
    }

    @Override
    protected void buildIntern() {
        init();
        computeLocalLiveSets();
        computeGlobalLiveSets();
    }

    
Gets the size of the BlockData.liveIn and BlockData.liveOut sets for a basic block. /**
     * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic
     * block.
     */
    private int liveSetSize() {
        return getLIR().numVariables();
    }

    AbstractBlockBase<?>[] getBlocks() {
        return getLIR().getControlFlowGraph().getBlocks();
    }

    static int operandNumber(Value operand) {
        if (isVariable(operand)) {
            return asVariable(operand).index;
        }
        throw GraalError.shouldNotReachHere("Can only handle Variables: " + operand);
    }

    private SSIBuilder.BlockData getBlockData(AbstractBlockBase<?> block) {
        return blockData.get(block);
    }

    private void initBlockData(AbstractBlockBase<?> block) {
        blockData.put(block, new SSIBuilder.BlockData());
    }

    private void init() {
        for (AbstractBlockBase<?> block : getBlocks()) {
            initBlockData(block);
        }
    }

    
Computes local live sets (i.e. BlockData.liveGen and BlockData.liveKill) separately for each block. /**
     * Computes local live sets (i.e. {@link BlockData#liveGen} and {@link BlockData#liveKill})
     * separately for each block.
     */
    @SuppressWarnings("try")
    private void computeLocalLiveSets() {
        int liveSize = liveSetSize();

        // iterate all blocks
        AbstractBlockBase<?>[] blocks = getBlocks();
        for (int i = blocks.length - 1; i >= 0; i--) {
            final AbstractBlockBase<?> block = blocks[i];
            try (Indent indent = Debug.logAndIndent(LOG_LEVEL, "compute local live sets for block %s", block)) {

                final BitSet liveGen = new BitSet(liveSize);
                final BitSet liveKill = new BitSet(liveSize);

                InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
                    @Override
                    public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
                        processLocalUse(liveGen, operand);
                    }
                };
                InstructionValueConsumer aliveConsumer = new InstructionValueConsumer() {
                    @Override
                    public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
                        processLocalUse(liveGen, operand);
                    }
                };
                InstructionValueConsumer stateConsumer = new InstructionValueConsumer() {
                    @Override
                    public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
                        if (isVariable(operand)) {
                            int operandNum = operandNumber(operand);
                            if (!liveKill.get(operandNum)) {
                                liveGen.set(operandNum);
                                if (Debug.isLogEnabled()) {
                                    Debug.log(LOG_LEVEL, "liveGen in state for operand %d(%s)", operandNum, operand);
                                }
                            }
                        }
                    }
                };
                InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
                    @Override
                    public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
                        processLocalDef(liveGen, liveKill, operand, operands);
                    }
                };
                InstructionValueConsumer tempConsumer = new InstructionValueConsumer() {
                    @Override
                    public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
                        processLocalDef(liveGen, liveKill, operand, operands);
                    }
                };

                // iterate all instructions of the block
                List<LIRInstruction> instructions = getLIR().getLIRforBlock(block);
                ListIterator<LIRInstruction> instIt = instructions.listIterator(instructions.size());
                while (instIt.hasPrevious()) {
                    final LIRInstruction op = instIt.previous();

                    try (Indent indent2 = Debug.logAndIndent(LOG_LEVEL, "handle op %d: %s", op.id(), op)) {
                        op.visitEachOutput(defConsumer);
                        op.visitEachTemp(tempConsumer);
                        op.visitEachState(stateConsumer);
                        op.visitEachAlive(aliveConsumer);
                        op.visitEachInput(useConsumer);
                    }
                } // end of instruction iteration

                SSIBuilder.BlockData blockSets = getBlockData(block);
                blockSets.liveGen = liveGen;
                blockSets.liveKill = liveKill;
                blockSets.liveIn = new BitSet(liveSize);
                blockSets.liveOut = new BitSet(liveSize);

                if (Debug.isLogEnabled()) {
                    Debug.log(LOG_LEVEL, "liveGen  B%d %s", block.getId(), blockSets.liveGen);
                    Debug.log(LOG_LEVEL, "liveKill B%d %s", block.getId(), blockSets.liveKill);
                }

            }
        } // end of block iteration
    }

    private static void processLocalUse(final BitSet liveGen, Value operand) {
        if (isVariable(operand)) {
            int operandNum = operandNumber(operand);
            liveGen.set(operandNum);
            if (Debug.isLogEnabled()) {
                Debug.log(LOG_LEVEL, "liveGen for operand %d(%s)", operandNum, operand);
            }
        }
    }

    private static void processLocalDef(final BitSet liveGen, final BitSet liveKill, Value operand, Value[] operands) {
        if (isVariable(operand)) {
            int operandNum = operandNumber(operand);
            if (operands[operandNum] == null) {
                operands[operandNum] = operand;
            }
            liveKill.set(operandNum);
            liveGen.clear(operandNum);
            if (Debug.isLogEnabled()) {
                Debug.log(LOG_LEVEL, "liveKill for operand %d(%s)", operandNum, operand);
            }
        }
    }

    
Performs a backward dataflow analysis to compute global live sets (i.e. BlockData.liveIn and BlockData.liveOut) for each block. /**
     * Performs a backward dataflow analysis to compute global live sets (i.e.
     * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block.
     */
    @SuppressWarnings("try")
    private void computeGlobalLiveSets() {
        try (Indent indent = Debug.logAndIndent(LOG_LEVEL, "compute global live sets")) {
            boolean changeOccurred;
            boolean changeOccurredInBlock;
            int iterationCount = 0;
            BitSet liveOut = new BitSet(liveSetSize()); // scratch set for
                                                        // calculations

            /*
             * Perform a backward dataflow analysis to compute liveOut and liveIn for each block.
             * The loop is executed until a fixpoint is reached (no changes in an iteration).
             */
            do {
                changeOccurred = false;

                try (Indent indent2 = Debug.logAndIndent(LOG_LEVEL, "new iteration %d", iterationCount)) {

                    // iterate all blocks in reverse order
                    AbstractBlockBase<?>[] blocks = getBlocks();
                    for (int i = blocks.length - 1; i >= 0; i--) {
                        final AbstractBlockBase<?> block = blocks[i];
                        SSIBuilder.BlockData blockSets = getBlockData(block);

                        changeOccurredInBlock = false;

                        /*
                         * liveOut(block) is the union of liveIn(sux), for successors sux of block.
                         */
                        int n = block.getSuccessorCount();
                        if (n > 0) {
                            // block has successors
                            liveOut.clear();
                            for (AbstractBlockBase<?> successor : block.getSuccessors()) {
                                liveOut.or(getBlockData(successor).liveIn);
                            }

                            if (!blockSets.liveOut.equals(liveOut)) {
                                /*
                                 * A change occurred. Swap the old and new live out sets to avoid
                                 * copying.
                                 */
                                BitSet temp = blockSets.liveOut;
                                blockSets.liveOut = liveOut;
                                liveOut = temp;

                                changeOccurred = true;
                                changeOccurredInBlock = true;
                            }
                        }

                        if (iterationCount == 0 || changeOccurredInBlock) {
                            /*
                             * liveIn(block) is the union of liveGen(block) with (liveOut(block) &
                             * !liveKill(block)).
                             *
                             * Note: liveIn has to be computed only in first iteration or if liveOut
                             * has changed!
                             */
                            BitSet liveIn = blockSets.liveIn;
                            liveIn.clear();
                            liveIn.or(blockSets.liveOut);
                            liveIn.andNot(blockSets.liveKill);
                            liveIn.or(blockSets.liveGen);

                            if (Debug.isLogEnabled()) {
                                Debug.log(LOG_LEVEL, "block %d: livein = %s,  liveout = %s", block.getId(), liveIn, blockSets.liveOut);
                            }
                        }
                    }
                    iterationCount++;

                    if (changeOccurred && iterationCount > 50) {
                        /*
                         * Very unlikely should never happen: If it happens we cannot guarantee it
                         * won't happen again.
                         */
                        throw new PermanentBailoutException("too many iterations in computeGlobalLiveSets");
                    }
                }
            } while (changeOccurred);
        }
    }

    @Override
    BitSet getLiveIn(final AbstractBlockBase<?> block) {
        return getBlockData(block).liveIn;
    }

    @Override
    BitSet getLiveOut(final AbstractBlockBase<?> block) {
        return getBlockData(block).liveOut;
    }
}