alloc/trace/GlobalLivenessAnalysisPhase.java

/*
 * Copyright (c) 2016, 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.alloc.trace;

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

import java.util.ArrayList;
import java.util.BitSet;
import java.util.EnumSet;

import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
import org.graalvm.compiler.core.common.cfg.Loop;
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 org.graalvm.compiler.lir.Variable;
import org.graalvm.compiler.lir.gen.LIRGenerationResult;
import org.graalvm.compiler.lir.phases.AllocationPhase;
import org.graalvm.compiler.lir.ssa.SSAUtil;

import jdk.vm.ci.code.TargetDescription;
import jdk.vm.ci.meta.Value;

/**
 * Constructs {@link GlobalLivenessInfo global liveness information}.
 */
public final class GlobalLivenessAnalysisPhase extends AllocationPhase {

    @Override
    protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
        assert SSAUtil.verifySSAForm(lirGenRes.getLIR());
        Analyser ssiBuilder = new Analyser(lirGenRes.getLIR());
        ssiBuilder.build();
        ssiBuilder.finish();
        GlobalLivenessInfo livenessInfo = ssiBuilder.getLivenessInfo();
        assert livenessInfo.verify(lirGenRes.getLIR());
        context.contextAdd(livenessInfo);
    }

    private final class Analyser {

        private static final int LOG_LEVEL = Debug.INFO_LOG_LEVEL;

        /**
         * 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}.
         */
        private final BitSet[] liveIns;

        /**
         * 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}.
         */
        private final BitSet[] liveOuts;

        private final AbstractBlockBase<?>[] blocks;

        private final Value[] operands;

        private final LIR lir;

        private final GlobalLivenessInfo.Builder livenessInfoBuilder;

        Analyser(LIR lir) {
            int numBlocks = lir.getControlFlowGraph().getBlocks().length;
            this.liveIns = new BitSet[numBlocks];
            this.liveOuts = new BitSet[numBlocks];
            this.blocks = lir.getControlFlowGraph().getBlocks();
            this.lir = lir;
            this.operands = new Value[lir.numVariables()];
            this.livenessInfoBuilder = new GlobalLivenessInfo.Builder(lir);
        }

        private BitSet getLiveIn(final AbstractBlockBase<?> block) {
            return liveIns[block.getId()];
        }

        private BitSet getLiveOut(final AbstractBlockBase<?> block) {
            return liveOuts[block.getId()];
        }

        private void setLiveIn(final AbstractBlockBase<?> block, final BitSet liveIn) {
            liveIns[block.getId()] = liveIn;
        }

        private void setLiveOut(final AbstractBlockBase<?> block, final BitSet liveOut) {
            liveOuts[block.getId()] = liveOut;
        }

        private void buildIntern() {
            computeLiveness();
        }

        /**
         * Gets the size of the {@link #liveIns} and {@link #liveOuts} sets for a basic block.
         */
        private int liveSetSize() {
            return lir.numVariables();
        }

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

        /**
         * Computes live sets for each block.
         */
        @SuppressWarnings("try")
        private void computeLiveness() {
            // iterate all blocks
            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 liveIn = mergeLiveSets(block);
                    setLiveOut(block, (BitSet) liveIn.clone());

                    InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
                        @Override
                        public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
                            processUse(liveIn, operand);
                        }
                    };
                    InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
                        @Override
                        public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
                            processDef(liveIn, op, operand);
                        }
                    };
                    if (Debug.isLogEnabled()) {
                        Debug.log(LOG_LEVEL, "liveOut B%d %s", block.getId(), getLiveOut(block));
                    }

                    // iterate all instructions of the block
                    ArrayList<LIRInstruction> instructions = getLIR().getLIRforBlock(block);
                    for (int j = instructions.size() - 1; j >= 0; j--) {
                        final LIRInstruction op = instructions.get(j);

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

                    setLiveIn(block, liveIn);
                    if (block.isLoopHeader()) {
                        handleLoopHeader(block.getLoop(), liveIn);
                    }

                    if (Debug.isLogEnabled()) {
                        Debug.log(LOG_LEVEL, "liveIn  B%d %s", block.getId(), getLiveIn(block));
                    }

                }
            } // end of block iteration
        }

        /**
         * All variables live at the beginning of a loop are live throughout the loop.
         */
        private void handleLoopHeader(Loop<?> loop, BitSet live) {
            for (AbstractBlockBase<?> block : loop.getBlocks()) {
                getLiveIn(block).or(live);
                getLiveOut(block).or(live);
            }
        }

        private BitSet mergeLiveSets(final AbstractBlockBase<?> block) {
            assert block != null;
            final BitSet liveOut = new BitSet(liveSetSize());
            for (AbstractBlockBase<?> successor : block.getSuccessors()) {
                BitSet succLiveIn = getLiveIn(successor);
                if (succLiveIn != null) {
                    liveOut.or(succLiveIn);
                } else {
                    assert successor.isLoopHeader() : "Successor of " + block + " not yet processed and not loop header: " + successor;
                }
            }
            return liveOut;
        }

        private void processUse(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 void processDef(final BitSet liveGen, LIRInstruction op, Value operand) {
            if (isVariable(operand)) {
                recordVariable(op, asVariable(operand));
                int operandNum = operandNumber(operand);
                if (operands[operandNum] == null) {
                    operands[operandNum] = operand;
                }
                liveGen.clear(operandNum);
                if (Debug.isLogEnabled()) {
                    Debug.log(LOG_LEVEL, "liveKill for operand %d(%s)", operandNum, operand);
                }
            }
        }

        private LIR getLIR() {
            return lir;
        }

        public void build() {
            buildIntern();
            // check that the liveIn set of the first block is empty
            AbstractBlockBase<?> startBlock = getLIR().getControlFlowGraph().getStartBlock();
            if (getLiveIn(startBlock).cardinality() != 0) {
                // bailout if this occurs in product mode.
                throw new GraalError("liveIn set of first block must be empty: " + getLiveIn(startBlock));
            }
        }

        @SuppressWarnings("try")
        public void finish() {
            // iterate all blocks in reverse order
            for (AbstractBlockBase<?> block : (AbstractBlockBase<?>[]) lir.getControlFlowGraph().getBlocks()) {
                try (Indent indent = Debug.logAndIndent(LOG_LEVEL, "Finish Block %s", block)) {
                    buildIncoming(block);
                    buildOutgoing(block);
                }
            }
        }

        public GlobalLivenessInfo getLivenessInfo() {
            assert livenessInfoBuilder != null : "No liveness info collected";
            return livenessInfoBuilder.createLivenessInfo();
        }

        private void buildIncoming(AbstractBlockBase<?> block) {
            if (!GlobalLivenessInfo.storesIncoming(block)) {
                assert block.getPredecessorCount() == 1;
                assert GlobalLivenessInfo.storesOutgoing(block.getPredecessors()[0]) : "No incoming liveness info: " + block;
                return;
            }

            final int[] liveInArray;
            if (block.getPredecessorCount() == 0) {
                // start block
                assert getLiveIn(block).isEmpty() : "liveIn for start block is not empty? " + getLiveIn(block);
                liveInArray = livenessInfoBuilder.emptySet;
            } else {
                /*
                 * Collect live out of predecessors since there might be values not used in this
                 * block which might cause out/in mismatch. Per construction the live sets of all
                 * predecessors are equal.
                 */
                BitSet predLiveOut = getLiveOut(block.getPredecessors()[0]);
                liveInArray = predLiveOut.isEmpty() ? livenessInfoBuilder.emptySet : bitSetToIntArray(predLiveOut);
            }

            livenessInfoBuilder.setIncoming(block, liveInArray);
            // reuse the same array for outgoing variables in predecessors
            for (AbstractBlockBase<?> pred : block.getPredecessors()) {
                livenessInfoBuilder.setOutgoing(pred, liveInArray);
            }
        }

        private void buildOutgoing(AbstractBlockBase<?> block) {
            BitSet liveOut = getLiveOut(block);
            if (!GlobalLivenessInfo.storesOutgoing(block)) {
                assert GlobalLivenessInfo.storesOutgoing(block) || block.getSuccessorCount() == 1;
                assert GlobalLivenessInfo.storesOutgoing(block) || GlobalLivenessInfo.storesIncoming(block.getSuccessors()[0]) : "No outgoing liveness info: " + block;
                return;
            }
            int[] liveOutArray = liveOut.isEmpty() ? livenessInfoBuilder.emptySet : bitSetToIntArray(liveOut);

            livenessInfoBuilder.setOutgoing(block, liveOutArray);
            // reuse the same array for incoming variables in successors
            for (AbstractBlockBase<?> succ : block.getSuccessors()) {
                livenessInfoBuilder.setIncoming(succ, liveOutArray);
            }
        }

        private int[] bitSetToIntArray(BitSet live) {
            int[] vars = new int[live.cardinality()];
            int cnt = 0;
            for (int i = live.nextSetBit(0); i >= 0; i = live.nextSetBit(i + 1), cnt++) {
                vars[cnt] = i;
            }
            return vars;
        }

        private void recordVariable(LIRInstruction op, Variable var) {
            livenessInfoBuilder.addVariable(op, var);
        }
    }

}