path: root/dx/src/com/android/dx/ssa/back/LivenessAnalyzer.java

/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.ssa.back;

import com.android.dx.ssa.SsaMethod;
import com.android.dx.ssa.SsaBasicBlock;
import com.android.dx.ssa.SsaInsn;
import com.android.dx.ssa.PhiInsn;
import com.android.dx.rop.code.RegisterSpec;

import java.util.BitSet;
import java.util.List;
import java.util.ArrayList;

/**
 * From Appel "Modern Compiler Implementation in Java" algorithm 19.17
 * Calculate the live ranges for register {@code reg}.<p>
 *
 * v = regV <p>
 * s = insn <p>
 * M = visitedBlocks <p>
 */
public class LivenessAnalyzer {
    /**
     * {@code non-null;} index by basic block indexed set of basic blocks
     * that have already been visited. "M" as written in the original Appel
     * algorithm.
     */
    private final BitSet visitedBlocks;

    /**
     * {@code non-null;} set of blocks remaing to visit as "live out as block"
     */
    private final BitSet liveOutBlocks;

    /**
     * {@code >=0;} SSA register currently being analyzed.
     * "v" in the original Appel algorithm.
     */
    private final int regV;

    /** method to process */
    private final SsaMethod ssaMeth;

    /** interference graph being updated */
    private final InterferenceGraph interference;

    /** block "n" in Appel 19.17 */
    private SsaBasicBlock blockN;

    /** index of statement {@code s} in {@code blockN} */
    private int statementIndex;

    /** the next function to call */
    private NextFunction nextFunction;

    /** constants for {@link #nextFunction} */
    private static enum NextFunction {
        LIVE_IN_AT_STATEMENT,
            LIVE_OUT_AT_STATEMENT,
            LIVE_OUT_AT_BLOCK,
            DONE;
    }

    /**
     * Runs register liveness algorithm for a method, updating the
     * live in/out information in {@code SsaBasicBlock} instances and
     * returning an interference graph.
     *
     * @param ssaMeth {@code non-null;} method to process
     * @return {@code non-null;} interference graph indexed by SSA
     * registers in both directions
     */
    public static InterferenceGraph constructInterferenceGraph(
            SsaMethod ssaMeth) {
        int szRegs = ssaMeth.getRegCount();
        InterferenceGraph interference = new InterferenceGraph(szRegs);

        for (int i = 0; i < szRegs; i++) {
            new LivenessAnalyzer(ssaMeth, i, interference).run();
        }

        coInterferePhis(ssaMeth, interference);

        return interference;
    }

    /**
     * Makes liveness analyzer instance for specific register.
     *
     * @param ssaMeth {@code non-null;} method to process
     * @param reg register whose liveness to analyze
     * @param interference {@code non-null;} indexed by SSA reg in
     * both dimensions; graph to update
     *
     */
    private LivenessAnalyzer(SsaMethod ssaMeth, int reg,
            InterferenceGraph interference) {
        int blocksSz = ssaMeth.getBlocks().size();

        this.ssaMeth = ssaMeth;
        this.regV = reg;
        visitedBlocks = new BitSet(blocksSz);
        liveOutBlocks = new BitSet(blocksSz);
        this.interference = interference;
    }

    /**
     * The algorithm in Appel is presented in partial tail-recursion
     * form. Obviously, that's not efficient in java, so this function
     * serves as the dispatcher instead.
     */
    private void handleTailRecursion() {
        while (nextFunction != NextFunction.DONE) {
            switch (nextFunction) {
                case LIVE_IN_AT_STATEMENT:
                    nextFunction = NextFunction.DONE;
                    liveInAtStatement();
                    break;

                case LIVE_OUT_AT_STATEMENT:
                    nextFunction = NextFunction.DONE;
                    liveOutAtStatement();
                    break;

                case LIVE_OUT_AT_BLOCK:
                    nextFunction = NextFunction.DONE;
                    liveOutAtBlock();
                    break;

                default:
            }
        }
    }

    /**
     * From Appel algorithm 19.17.
     */
    public void run() {
        List<SsaInsn> useList = ssaMeth.getUseListForRegister(regV);

        for (SsaInsn insn : useList) {
            nextFunction = NextFunction.DONE;

            if (insn instanceof PhiInsn) {
                // If s is a phi-function with V as it's ith argument.
                PhiInsn phi = (PhiInsn) insn;

                for (SsaBasicBlock pred :
                         phi.predBlocksForReg(regV, ssaMeth)) {
                    blockN = pred;

                    nextFunction = NextFunction.LIVE_OUT_AT_BLOCK;
                    handleTailRecursion();
                }
            } else {
                blockN = insn.getBlock();
                statementIndex = blockN.getInsns().indexOf(insn);

                if (statementIndex < 0) {
                    throw new RuntimeException(
                            "insn not found in it's own block");
                }

                nextFunction = NextFunction.LIVE_IN_AT_STATEMENT;
                handleTailRecursion();
            }
        }

        int nextLiveOutBlock;
        while ((nextLiveOutBlock = liveOutBlocks.nextSetBit(0)) >= 0) {
            blockN = ssaMeth.getBlocks().get(nextLiveOutBlock);
            liveOutBlocks.clear(nextLiveOutBlock);
            nextFunction = NextFunction.LIVE_OUT_AT_BLOCK;
            handleTailRecursion();
        }
    }

    /**
     * "v is live-out at n."
     */
    private void liveOutAtBlock() {
        if (! visitedBlocks.get(blockN.getIndex())) {
            visitedBlocks.set(blockN.getIndex());

            blockN.addLiveOut(regV);

            ArrayList<SsaInsn> insns;

            insns = blockN.getInsns();

            // Live out at last statement in blockN
            statementIndex = insns.size() - 1;
            nextFunction = NextFunction.LIVE_OUT_AT_STATEMENT;
        }
    }

    /**
     * "v is live-in at s."
     */
    private void liveInAtStatement() {
        // if s is the first statement in block N
        if (statementIndex == 0) {
            // v is live-in at n
            blockN.addLiveIn(regV);

            BitSet preds = blockN.getPredecessors();

            liveOutBlocks.or(preds);
        } else {
            // Let s' be the statement preceeding s
            statementIndex -= 1;
            nextFunction = NextFunction.LIVE_OUT_AT_STATEMENT;
        }
    }

    /**
     * "v is live-out at s."
     */
    private void liveOutAtStatement() {
        SsaInsn statement = blockN.getInsns().get(statementIndex);
        RegisterSpec rs = statement.getResult();

        if (!statement.isResultReg(regV)) {
            if (rs != null) {
                interference.add(regV, rs.getReg());
            }
            nextFunction = NextFunction.LIVE_IN_AT_STATEMENT;
        }
    }

    /**
     * Ensures that all the phi result registers for all the phis in the
     * same basic block interfere with each other. This is needed since
     * the dead code remover has allowed through "dead-end phis" whose
     * results are not used except as local assignments. Without this step,
     * a the result of a dead-end phi might be assigned the same register
     * as the result of another phi, and the phi removal move scheduler may
     * generate moves that over-write the live result.
     *
     * @param ssaMeth {@code non-null;} method to pricess
     * @param interference {@code non-null;} interference graph
     */
    private static void coInterferePhis(SsaMethod ssaMeth,
            InterferenceGraph interference) {
        for (SsaBasicBlock b : ssaMeth.getBlocks()) {
            List<SsaInsn> phis = b.getPhiInsns();

            int szPhis = phis.size();

            for (int i = 0; i < szPhis; i++) {
                for (int j = 0; j < szPhis; j++) {
                    if (i == j) {
                        continue;
                    }

                    interference.add(phis.get(i).getResult().getReg(),
                        phis.get(j).getResult().getReg());
                }
            }
        }
    }
}