Top Description Inners Fields Constructors Methods
org.droidparts.dexmaker.dx.ssa.back

public Class LivenessAnalyzer

extends Object
Class Inheritance
Imports
org.droidparts.dexmaker.dx.rop.code.RegisterSpec, org.droidparts.dexmaker.dx.ssa.PhiInsn, .SsaBasicBlock, .SsaInsn, .SsaMethod, java.util.ArrayList, .BitSet, .List
From Appel "Modern Compiler Implementation in Java" algorithm 19.17 Calculate the live ranges for register reg.

v = regV

s = insn

M = visitedBlocks

Nested and Inner Type Summary

Modifier and TypeClass and Description
private static enum
LivenessAnalyzer.NextFunction

constants for nextFunction

Field Summary

Modifier and TypeField and Description
private SsaBasicBlock
blockN

block "n" in Appel 19.17

private final InterferenceGraph
interference

interference graph being updated

private final BitSet
liveOutBlocks

non-null; set of blocks remaing to visit as "live out as block"

private LivenessAnalyzer.NextFunction
nextFunction

the next function to call

private final int
regV

>=0; SSA register currently being analyzed.

private final SsaMethod
ssaMeth

method to process

private int
statementIndex

index of statement s in blockN

private final BitSet
visitedBlocks

non-null; index by basic block indexed set of basic blocks that have already been visited.

Constructor Summary

AccessConstructor and Description
private
LivenessAnalyzer(SsaMethod
non-null; method to process
ssaMeth, int
register whose liveness to analyze
reg, InterferenceGraph
non-null; indexed by SSA reg in both dimensions; graph to update
interference)

Makes liveness analyzer instance for specific register.

Method Summary

Modifier and TypeMethod and Description
private static void
coInterferePhis(SsaMethod
non-null; method to pricess
ssaMeth, InterferenceGraph
non-null; interference graph
interference)

Ensures that all the phi result registers for all the phis in the same basic block interfere with each other.

public static InterferenceGraph

Returns:

non-null; interference graph indexed by SSA registers in both directions
constructInterferenceGraph(SsaMethod
non-null; method to process
ssaMeth)

Runs register liveness algorithm for a method, updating the live in/out information in SsaBasicBlock instances and returning an interference graph.

private void
handleTailRecursion()

The algorithm in Appel is presented in partial tail-recursion form.

private void
liveInAtStatement()

"v is live-in at s."

private void
liveOutAtBlock()

"v is live-out at n."

private void
liveOutAtStatement()

"v is live-out at s."

public void
run()

From Appel algorithm 19.17.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

blockNback to summary
private SsaBasicBlock blockN

block "n" in Appel 19.17

interferenceback to summary
private final InterferenceGraph interference

interference graph being updated

liveOutBlocksback to summary
private final BitSet liveOutBlocks

non-null; set of blocks remaing to visit as "live out as block"

nextFunctionback to summary
private LivenessAnalyzer.NextFunction nextFunction

the next function to call

regVback to summary
private final int regV

>=0; SSA register currently being analyzed. "v" in the original Appel algorithm.

ssaMethback to summary
private final SsaMethod ssaMeth

method to process

statementIndexback to summary
private int statementIndex

index of statement s in blockN

visitedBlocksback to 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.

Constructor Detail

LivenessAnalyzerback to summary
private LivenessAnalyzer(SsaMethod ssaMeth, int reg, InterferenceGraph interference)

Makes liveness analyzer instance for specific register.

Parameters
ssaMeth:SsaMethod

non-null; method to process

reg:int

register whose liveness to analyze

interference:InterferenceGraph

non-null; indexed by SSA reg in both dimensions; graph to update

Method Detail

coInterferePhisback to summary
private static void coInterferePhis(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.

Parameters
ssaMeth:SsaMethod

non-null; method to pricess

interference:InterferenceGraph

non-null; interference graph

constructInterferenceGraphback to summary
public static InterferenceGraph constructInterferenceGraph(SsaMethod ssaMeth)

Runs register liveness algorithm for a method, updating the live in/out information in SsaBasicBlock instances and returning an interference graph.

Parameters
ssaMeth:SsaMethod

non-null; method to process

Returns:InterferenceGraph

non-null; interference graph indexed by SSA registers in both directions

handleTailRecursionback to summary
private void handleTailRecursion()

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.

liveInAtStatementback to summary
private void liveInAtStatement()

"v is live-in at s."

liveOutAtBlockback to summary
private void liveOutAtBlock()

"v is live-out at n."

liveOutAtStatementback to summary
private void liveOutAtStatement()

"v is live-out at s."

runback to summary
public void run()

From Appel algorithm 19.17.

org.droidparts.dexmaker.dx.ssa.back back to summary

private final Enum LivenessAnalyzer.NextFunction

extends Enum<LivenessAnalyzer.NextFunction>
Class Inheritance
constants for nextFunction

Field Summary

Modifier and TypeField and Description
public static final LivenessAnalyzer.NextFunction
DONE

public static final LivenessAnalyzer.NextFunction
LIVE_IN_AT_STATEMENT

public static final LivenessAnalyzer.NextFunction
LIVE_OUT_AT_BLOCK

public static final LivenessAnalyzer.NextFunction
LIVE_OUT_AT_STATEMENT

Constructor Summary

AccessConstructor and Description
private
NextFunction()

Method Summary

Modifier and TypeMethod and Description
public static LivenessAnalyzer.NextFunction
valueOf(String name)

public static LivenessAnalyzer.NextFunction[]
values()

Inherited from java.lang.Enum:
clonecompareTodescribeConstableequalsfinalizegetDeclaringClasshashCodenameordinaltoStringvalueOf

Field Detail

DONEback to summary
public static final LivenessAnalyzer.NextFunction DONE
LIVE_IN_AT_STATEMENTback to summary
public static final LivenessAnalyzer.NextFunction LIVE_IN_AT_STATEMENT
LIVE_OUT_AT_BLOCKback to summary
public static final LivenessAnalyzer.NextFunction LIVE_OUT_AT_BLOCK
LIVE_OUT_AT_STATEMENTback to summary
public static final LivenessAnalyzer.NextFunction LIVE_OUT_AT_STATEMENT

Constructor Detail

NextFunctionback to summary
private NextFunction()

Method Detail

valueOfback to summary
public static LivenessAnalyzer.NextFunction valueOf(String name)
valuesback to summary
public static LivenessAnalyzer.NextFunction[] values()