FileDocCategorySizeDatePackage
LivenessAnalyzer.javaAPI DocAndroid 1.5 API8496Wed May 06 22:41:02 BST 2009com.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 reg.

v = regV

s = insn

M = visitedBlocks

Fields Summary
private final BitSet
visitedBlocks
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
non-null; set of blocks remaing to visit as "live out as block"
private final int
regV
>=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
com.android.dx.ssa.SsaBasicBlock
blockN
block "n" in Appel 19.17
private int
statementIndex
index of statement s in blockN
private int
nextFunction
the next function to call. one of the four constants below
static final int
LIVE_IN_AT_STATEMENT
constants for nextFunction
static final int
LIVE_OUT_AT_STATEMENT
static final int
LIVE_OUT_AT_BLOCK
static final int
DONE
Constructors Summary
private LivenessAnalyzer(com.android.dx.ssa.SsaMethod ssaMeth, int reg, InterferenceGraph interference)
Makes liveness analyzer instance for specific register.

param
ssaMeth non-null; method to process
param
reg register whose liveness to analyze
param
interference non-null; indexed by SSA reg in both dimensions; graph to update

        this.ssaMeth = ssaMeth;
        this.regV = reg;
        visitedBlocks = new BitSet(ssaMeth.getBlocks().size());
        liveOutBlocks = new BitSet(ssaMeth.getBlocks().size());
        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 non-null; method to pricess
param
interference 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 SsaBasicBlock instances and returning an interference graph.

param
ssaMeth non-null; Method to process.
return
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 != DONE) {
            switch (nextFunction) {
                case LIVE_IN_AT_STATEMENT:
                    nextFunction = DONE;
                    liveInAtStatement();
                    break;

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

                case LIVE_OUT_AT_BLOCK:
                    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 = 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 = 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 = LIVE_IN_AT_STATEMENT;
        }
public voidrun()
From Appel algorithm 19.17

        List<SsaInsn> useList = ssaMeth.getUseListForRegister(regV);

        for (SsaInsn insn: useList) {
            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 = 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 = LIVE_IN_AT_STATEMENT;
                handleTailRecursion();
            }
        }

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