FileDocCategorySizeDatePackage
LivenessAnalyzer.javaAPI DocAndroid 5.1 API8690Thu Mar 12 22:18:30 GMT 2015com.android.dx.ssa.back

LivenessAnalyzer

public class LivenessAnalyzer extends Object
From Appel "Modern Compiler Implementation in Java" algorithm 19.17 Calculate the live ranges for register {@code reg}.

v = regV

s = insn

M = visitedBlocks

Fields Summary
private final BitSet
visitedBlocks
{@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
liveOutBlocks
{@code non-null;} set of blocks remaing to visit as "live out as block"
private final int
regV
{@code >=0;} SSA register currently being analyzed. "v" in the original Appel algorithm.
private final com.android.dx.ssa.SsaMethod
ssaMeth
method to process
private final InterferenceGraph
interference
interference graph being updated
private com.android.dx.ssa.SsaBasicBlock
blockN
block "n" in Appel 19.17
private int
statementIndex
index of statement {@code s} in {@code blockN}
private NextFunction
nextFunction
the next function to call
Constructors Summary
private LivenessAnalyzer(com.android.dx.ssa.SsaMethod ssaMeth, int reg, InterferenceGraph 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

        int blocksSz = ssaMeth.getBlocks().size();

        this.ssaMeth = ssaMeth;
        this.regV = reg;
        visitedBlocks = new BitSet(blocksSz);
        liveOutBlocks = new BitSet(blocksSz);
        this.interference = interference;
Methods Summary
private static voidcoInterferePhis(com.android.dx.ssa.SsaMethod ssaMeth, InterferenceGraph interference)
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

        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());
                }
            }
        }
public static InterferenceGraphconstructInterferenceGraph(com.android.dx.ssa.SsaMethod ssaMeth)
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

        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;
private voidhandleTailRecursion()
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.

        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:
            }
        }
private voidliveInAtStatement()
"v is live-in at s."

        // 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;
        }
private voidliveOutAtBlock()
"v is live-out at n."

        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;
        }
private voidliveOutAtStatement()
"v is live-out at s."

        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;
        }
public voidrun()
From Appel algorithm 19.17.

        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();
        }