* * v = regV
* s = insn
* M = visitedBlocks
*/
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