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

public Class SCCP

extends Object
Class Inheritance
Imports
org.droidparts.dexmaker.dx.rop.code.*, org.droidparts.dexmaker.dx.rop.cst.Constant, .CstInteger, .TypedConstant, org.droidparts.dexmaker.dx.rop.type.Type, .TypeBearer, java.util.ArrayList, .BitSet
A small variant of Wegman and Zadeck's Sparse Conditional Constant Propagation algorithm.

Field Summary

Modifier and TypeField and Description
private ArrayList<SsaInsn>
branchWorklist

Worklist of potential branches to convert to gotos

private ArrayList<SsaBasicBlock>
cfgPhiWorklist

Worklist of executed basic blocks with phis to be processed

private ArrayList<SsaBasicBlock>
cfgWorklist

Worklist of basic blocks to be processed

private static final int
CONSTANT

private BitSet
executableBlocks

Bitset containing bits for each block that has been found executable

private Constant[]
latticeConstants

For those registers that are constant, this is the constant value

private int[]
latticeValues

Lattice values for each SSA register

private int
regCount

ssaMeth.getRegCount()

private SsaMethod
ssaMeth

method we're processing

private ArrayList<SsaInsn>
ssaWorklist

Worklist for SSA edges.

private static final int
TOP

Lattice values

private static final int
VARYING

private ArrayList<SsaInsn>
varyingWorklist

Worklist for SSA edges that represent varying values.

Constructor Summary

AccessConstructor and Description
private
SCCP(SsaMethod ssaMeth)

Method Summary

Modifier and TypeMethod and Description
private void
addBlockToWorklist(SsaBasicBlock
Block to add
ssaBlock)

Adds a SSA basic block to the CFG worklist if it's unexecuted, or to the CFG phi worklist if it's already executed.

private void
addUsersToWorklist(int
SSA register
reg, int
new lattice value for @param reg.
latticeValue)

Adds an SSA register's uses to the SSA worklist.

private static String
latticeValName(int latticeVal)

public static void
process(SsaMethod
Method to process
ssaMethod)

Performs sparse conditional constant propagation on a method.

private void
replaceBranches()

Replaces branches that have constant conditions with gotos

private void
replaceConstants()

Replaces TypeBearers in source register specs with constant type bearers if possible.

private void
run()

private boolean

Returns:

true if the lattice value changed.
setLatticeValueTo(int
SSA register
reg, int
Lattice value
value, Constant
Constant value (may be null)
cst)

Sets a lattice value for a register to value.

private void
simulateBlock(SsaBasicBlock
Block to visit
block)

Simulate a block and note the results in the lattice.

private void
simulateBranch(SsaInsn
branch to simulate
insn)

Simulates branch insns, if possible.

private Constant

Returns:

constant result or null if not simulatable.
simulateMath(SsaInsn
non-null insn to simulate
insn, int
basic type of the result
resultType)

Simulates math insns, if possible.

private void
simulatePhi(PhiInsn
PHI to simulate.
insn)

Simulates a PHI node and set the lattice for the result to the appropriate value.

private void
simulatePhiBlock(SsaBasicBlock
Block to visit
block)

Simulate the phis in a block and note the results in the lattice.

private void
simulateStmt(SsaInsn
instruction to simulate
insn)

Simulates a statement and set the result lattice value.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

branchWorklistback to summary
private ArrayList<SsaInsn> branchWorklist

Worklist of potential branches to convert to gotos

cfgPhiWorklistback to summary
private ArrayList<SsaBasicBlock> cfgPhiWorklist

Worklist of executed basic blocks with phis to be processed

cfgWorklistback to summary
private ArrayList<SsaBasicBlock> cfgWorklist

Worklist of basic blocks to be processed

CONSTANTback to summary
private static final int CONSTANT
executableBlocksback to summary
private BitSet executableBlocks

Bitset containing bits for each block that has been found executable

latticeConstantsback to summary
private Constant[] latticeConstants

For those registers that are constant, this is the constant value

latticeValuesback to summary
private int[] latticeValues

Lattice values for each SSA register

regCountback to summary
private int regCount

ssaMeth.getRegCount()

ssaMethback to summary
private SsaMethod ssaMeth

method we're processing

ssaWorklistback to summary
private ArrayList<SsaInsn> ssaWorklist

Worklist for SSA edges. This is a list of registers to process

TOPback to summary
private static final int TOP

Lattice values

VARYINGback to summary
private static final int VARYING
varyingWorklistback to summary
private ArrayList<SsaInsn> varyingWorklist

Worklist for SSA edges that represent varying values. It makes the algorithm much faster if you move all values to VARYING as fast as possible.

Constructor Detail

SCCPback to summary
private SCCP(SsaMethod ssaMeth)

Method Detail

addBlockToWorklistback to summary
private void addBlockToWorklist(SsaBasicBlock ssaBlock)

Adds a SSA basic block to the CFG worklist if it's unexecuted, or to the CFG phi worklist if it's already executed.

Parameters
ssaBlock:SsaBasicBlock

Block to add

addUsersToWorklistback to summary
private void addUsersToWorklist(int reg, int latticeValue)

Adds an SSA register's uses to the SSA worklist.

Parameters
reg:int

SSA register

latticeValue:int

new lattice value for @param reg.

latticeValNameback to summary
private static String latticeValName(int latticeVal)
processback to summary
public static void process(SsaMethod ssaMethod)

Performs sparse conditional constant propagation on a method.

Parameters
ssaMethod:SsaMethod

Method to process

replaceBranchesback to summary
private void replaceBranches()

Replaces branches that have constant conditions with gotos

replaceConstantsback to summary
private void replaceConstants()

Replaces TypeBearers in source register specs with constant type bearers if possible. These are then referenced in later optimization steps.

runback to summary
private void run()
setLatticeValueToback to summary
private boolean setLatticeValueTo(int reg, int value, Constant cst)

Sets a lattice value for a register to value.

Parameters
reg:int

SSA register

value:int

Lattice value

cst:Constant

Constant value (may be null)

Returns:boolean

true if the lattice value changed.

simulateBlockback to summary
private void simulateBlock(SsaBasicBlock block)

Simulate a block and note the results in the lattice.

Parameters
block:SsaBasicBlock

Block to visit

simulateBranchback to summary
private void simulateBranch(SsaInsn insn)

Simulates branch insns, if possible. Adds reachable successor blocks to the CFG worklists.

Parameters
insn:SsaInsn

branch to simulate

simulateMathback to summary
private Constant simulateMath(SsaInsn insn, int resultType)

Simulates math insns, if possible.

Parameters
insn:SsaInsn

non-null insn to simulate

resultType:int

basic type of the result

Returns:Constant

constant result or null if not simulatable.

simulatePhiback to summary
private void simulatePhi(PhiInsn insn)

Simulates a PHI node and set the lattice for the result to the appropriate value. Meet values: TOP x anything = TOP VARYING x anything = VARYING CONSTANT x CONSTANT = CONSTANT if equal constants, VARYING otherwise

Parameters
insn:PhiInsn

PHI to simulate.

simulatePhiBlockback to summary
private void simulatePhiBlock(SsaBasicBlock block)

Simulate the phis in a block and note the results in the lattice.

Parameters
block:SsaBasicBlock

Block to visit

simulateStmtback to summary
private void simulateStmt(SsaInsn insn)

Simulates a statement and set the result lattice value.

Parameters
insn:SsaInsn

instruction to simulate