Nested and Inner Type Summary

Modifier and Type	Class and Description
pack-priv static class	EscapeAnalysis.EscapeSet Struct used to generate and maintain escape analysis results.
public static enum	EscapeAnalysis.EscapeState Lattice values used to indicate escape state for an object.

Field Summary

Modifier and Type	Field and Description
private ArrayList<EscapeAnalysis.EscapeSet>	latticeValues Lattice values for each object register group
private int	regCount ssaMeth.getRegCount()
private SsaMethod	ssaMeth method we're processing

Constructor Summary

Access	Constructor and Description
private	EscapeAnalysis(SsaMethod method to process ssaMeth) Constructs an instance.

Method Summary

Modifier and Type	Method and Description
private void	addEdge(EscapeAnalysis.EscapeSet `non-null;` the EscapeSet for the object being put into parentSet, EscapeAnalysis.EscapeSet `non-null;` the EscapeSet for the object being put childSet) Creates a link in the lattice between two EscapeSets due to a put instruction.
private int	Returns: index of the register or size of the lattice if it wasn't found. findSetIndex(RegisterSpec `non-null;` register being looked up reg) Finds the index in the lattice for a particular register.
private SsaInsn	Returns: `non-null;` the instruction that produces the result for the move getInsnForMove(SsaInsn `non-null;` a move result instruction moveInsn) Finds the corresponding instruction for a given move result
private SsaInsn	Returns: `non-null;` the move result for the given instruction getMoveForInsn(SsaInsn `non-null;` an instruction that must always be followed by a move result insn) Finds the corresponding move result for a given instruction
private void	insertExceptionThrow(SsaInsn `non-null;` instruction causing the exception insn, RegisterSpec `non-null;` index value that is out of bounds index, HashSet<SsaInsn> `non-null;` set of instructions marked for deletion deletedInsns) Replaces instructions that trigger an ArrayIndexOutofBounds exception with an actual throw of the exception.
private void	insertPlainInsnBefore(SsaInsn `non-null;` instruction to insert before insn, RegisterSpecList `non-null;` sources of new instruction newSources, RegisterSpec `non-null;` result of new instruction newResult, int opcode of new instruction newOpcode, Constant `null-ok;` constant for new instruction, if any cst) Inserts a new PlainInsn before the given instruction.
private void	insertThrowingInsnBefore(SsaInsn `non-null;` instruction to insert before insn, RegisterSpecList `non-null;` sources of new instruction newSources, RegisterSpec `non-null;` result of new instruction newResult, int opcode of new instruction newOpcode, Constant `null-ok;` constant for new instruction, if any cst) Inserts a new ThrowingInsn before the given instruction.
private void	movePropagate() Identifies extra moves added by scalar replacement and propagates the source of the move to any users of the result.
public static void	process(SsaMethod `non-null;` method to process ssaMethod) Performs escape analysis on a method.
private void	processInsn(SsaInsn `non-null;` instruction to process insn) Process a single instruction, looking for new objects resulting from move result or move param.
private EscapeAnalysis.EscapeSet	Returns: `non-null;` an EscapeSet for the object referred to by the move result pseudo instruction processMoveResultPseudoInsn(SsaInsn `non-null;` move result pseudo instruction to process insn) Determine the origin of a move result pseudo instruction that generates an object.
private void	processPhiUse(SsaInsn `non-null;` phi use being processed use, EscapeAnalysis.EscapeSet `non-null;` EscapeSet for the object escSet, ArrayList<RegisterSpec> `non-null;` worklist of instructions left to process for this object regWorklist) Handles phi uses of new objects.
private void	processRegister(RegisterSpec `non-null;` register where new object is stored result, EscapeAnalysis.EscapeSet `non-null;` EscapeSet for the new object escSet) Iterate through all the uses of a new object.
private void	processUse(RegisterSpec `non-null;` register holding definition of new object def, SsaInsn `non-null;` use of object being processed use, EscapeAnalysis.EscapeSet `non-null;` EscapeSet for the object escSet, ArrayList<RegisterSpec> `non-null;` worklist of instructions left to process for this object regWorklist) Handles non-phi uses of new objects.
private void	replaceDef(SsaInsn `non-null;` move result instruction for array def, SsaInsn `non-null;` instruction for instantiating new array prev, int size of the new array length, ArrayList<RegisterSpec> `non-null;` mapping of array indices to new registers to be populated newRegs) Replaces the instructions that define an array with equivalent registers.
private void	replaceNode(EscapeAnalysis.EscapeSet `non-null;` the EscapeSet to merge all links into newNode, EscapeAnalysis.EscapeSet `non-null;` the EscapeSet to remove all links from oldNode) Merges all links in the lattice among two EscapeSets.
private void	replaceUse(SsaInsn `non-null;` move result instruction for array use, SsaInsn `non-null;` instruction for instantiating new array prev, ArrayList<RegisterSpec> `non-null;` mapping of array indices to new registers newRegs, HashSet<SsaInsn> `non-null;` set of instructions marked for deletion deletedInsns) Replaces the use for a scalar replaceable array.
private void	run() Runs escape analysis and scalar replacement of arrays.
private void	scalarReplacement() Performs scalar replacement on all eligible arrays.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

latticeValues	back to summary
private ArrayList<EscapeAnalysis.EscapeSet> latticeValues Lattice values for each object register group

regCount	back to summary
private int regCount ssaMeth.getRegCount()

ssaMeth	back to summary
private SsaMethod ssaMeth method we're processing

Constructor Detail

EscapeAnalysis	back to summary
private EscapeAnalysis(SsaMethod ssaMeth) Constructs an instance. Parameters ssaMeth:SsaMethod method to process

EscapeAnalysis

back to summary

private EscapeAnalysis(SsaMethod ssaMeth)

Constructs an instance.

Parameters

ssaMeth:SsaMethod: method to process

Method Detail

addEdge back to summary

addEdge	back to summary
private void addEdge(EscapeAnalysis.EscapeSet parentSet, EscapeAnalysis.EscapeSet childSet) Creates a link in the lattice between two EscapeSets due to a put instruction. The object being put is the child and the object being put into is the parent. A child set must always have an escape state at least as high as its parent. Parameters parentSet:EscapeAnalysis.EscapeSet `non-null;` the EscapeSet for the object being put into childSet:EscapeAnalysis.EscapeSet `non-null;` the EscapeSet for the object being put

private void addEdge(EscapeAnalysis.EscapeSet parentSet, EscapeAnalysis.EscapeSet childSet)

Creates a link in the lattice between two EscapeSets due to a put instruction. The object being put is the child and the object being put into is the parent. A child set must always have an escape state at least as high as its parent.

Parameters

parentSet:EscapeAnalysis.EscapeSet: non-null; the EscapeSet for the object being put into
childSet:EscapeAnalysis.EscapeSet: non-null; the EscapeSet for the object being put

findSetIndex back to summary

findSetIndex	back to summary
private int findSetIndex(RegisterSpec reg) Finds the index in the lattice for a particular register. Returns the size of the lattice if the register wasn't found. Parameters reg:RegisterSpec `non-null;` register being looked up Returns:int index of the register or size of the lattice if it wasn't found.

private int findSetIndex(RegisterSpec reg)

Finds the index in the lattice for a particular register. Returns the size of the lattice if the register wasn't found.

Parameters

reg:RegisterSpec: non-null; register being looked up

Returns:int

index of the register or size of the lattice if it wasn't found.

getInsnForMove back to summary

getInsnForMove	back to summary
private SsaInsn getInsnForMove(SsaInsn moveInsn) Finds the corresponding instruction for a given move result Parameters moveInsn:SsaInsn `non-null;` a move result instruction Returns:SsaInsn `non-null;` the instruction that produces the result for the move

private SsaInsn getInsnForMove(SsaInsn moveInsn)

Finds the corresponding instruction for a given move result

Parameters

moveInsn:SsaInsn: non-null; a move result instruction

Returns:SsaInsn

non-null; the instruction that produces the result for the move

getMoveForInsn back to summary

getMoveForInsn	back to summary
private SsaInsn getMoveForInsn(SsaInsn insn) Finds the corresponding move result for a given instruction Parameters insn:SsaInsn `non-null;` an instruction that must always be followed by a move result Returns:SsaInsn `non-null;` the move result for the given instruction

private SsaInsn getMoveForInsn(SsaInsn insn)

Finds the corresponding move result for a given instruction

Parameters

insn:SsaInsn: non-null; an instruction that must always be followed by a move result

Returns:SsaInsn

non-null; the move result for the given instruction

insertExceptionThrow back to summary

insertExceptionThrow	back to summary
private void insertExceptionThrow(SsaInsn insn, RegisterSpec index, HashSet<SsaInsn> deletedInsns) Replaces instructions that trigger an ArrayIndexOutofBounds exception with an actual throw of the exception. Parameters insn:SsaInsn `non-null;` instruction causing the exception index:RegisterSpec `non-null;` index value that is out of bounds deletedInsns:HashSet<SsaInsn> `non-null;` set of instructions marked for deletion

private void insertExceptionThrow(SsaInsn insn, RegisterSpec index, HashSet<SsaInsn> deletedInsns)

Replaces instructions that trigger an ArrayIndexOutofBounds exception with an actual throw of the exception.

Parameters

insn:SsaInsn: non-null; instruction causing the exception
index:RegisterSpec: non-null; index value that is out of bounds
deletedInsns:HashSet<SsaInsn>: non-null; set of instructions marked for deletion

insertPlainInsnBefore back to summary

insertPlainInsnBefore	back to summary
private void insertPlainInsnBefore(SsaInsn insn, RegisterSpecList newSources, RegisterSpec newResult, int newOpcode, Constant cst) Inserts a new PlainInsn before the given instruction. Todo move this somewhere more appropriate Parameters insn:SsaInsn `non-null;` instruction to insert before newSources:RegisterSpecList `non-null;` sources of new instruction newResult:RegisterSpec `non-null;` result of new instruction newOpcode:int opcode of new instruction cst:Constant `null-ok;` constant for new instruction, if any

private void insertPlainInsnBefore(SsaInsn insn, RegisterSpecList newSources, RegisterSpec newResult, int newOpcode, Constant cst)

Inserts a new PlainInsn before the given instruction.

Todo

move this somewhere more appropriate

Parameters

insn:SsaInsn: non-null; instruction to insert before
newSources:RegisterSpecList: non-null; sources of new instruction
newResult:RegisterSpec: non-null; result of new instruction
newOpcode:int: opcode of new instruction
cst:Constant: null-ok; constant for new instruction, if any

insertThrowingInsnBefore back to summary

insertThrowingInsnBefore	back to summary
private void insertThrowingInsnBefore(SsaInsn insn, RegisterSpecList newSources, RegisterSpec newResult, int newOpcode, Constant cst) Inserts a new ThrowingInsn before the given instruction. Todo move this somewhere more appropriate Parameters insn:SsaInsn `non-null;` instruction to insert before newSources:RegisterSpecList `non-null;` sources of new instruction newResult:RegisterSpec `non-null;` result of new instruction newOpcode:int opcode of new instruction cst:Constant `null-ok;` constant for new instruction, if any

private void insertThrowingInsnBefore(SsaInsn insn, RegisterSpecList newSources, RegisterSpec newResult, int newOpcode, Constant cst)

Inserts a new ThrowingInsn before the given instruction.

Todo

move this somewhere more appropriate

Parameters

insn:SsaInsn: non-null; instruction to insert before
newSources:RegisterSpecList: non-null; sources of new instruction
newResult:RegisterSpec: non-null; result of new instruction
newOpcode:int: opcode of new instruction
cst:Constant: null-ok; constant for new instruction, if any

movePropagate	back to summary
private void movePropagate() Identifies extra moves added by scalar replacement and propagates the source of the move to any users of the result.

process back to summary

process	back to summary
public static void process(SsaMethod ssaMethod) Performs escape analysis on a method. Finds scalar replaceable arrays and replaces them with equivalent registers. Parameters ssaMethod:SsaMethod `non-null;` method to process

public static void process(SsaMethod ssaMethod)

Performs escape analysis on a method. Finds scalar replaceable arrays and replaces them with equivalent registers.

Parameters

ssaMethod:SsaMethod: non-null; method to process

processInsn back to summary

processInsn	back to summary
private void processInsn(SsaInsn insn) Process a single instruction, looking for new objects resulting from move result or move param. Parameters insn:SsaInsn `non-null;` instruction to process

private void processInsn(SsaInsn insn)

Process a single instruction, looking for new objects resulting from move result or move param.

Parameters

insn:SsaInsn: non-null; instruction to process

processMoveResultPseudoInsn back to summary

processMoveResultPseudoInsn	back to summary
private EscapeAnalysis.EscapeSet processMoveResultPseudoInsn(SsaInsn insn) Determine the origin of a move result pseudo instruction that generates an object. Creates a new EscapeSet for the new object accordingly. Parameters insn:SsaInsn `non-null;` move result pseudo instruction to process Returns:EscapeAnalysis.EscapeSet `non-null;` an EscapeSet for the object referred to by the move result pseudo instruction

private EscapeAnalysis.EscapeSet processMoveResultPseudoInsn(SsaInsn insn)

Determine the origin of a move result pseudo instruction that generates an object. Creates a new EscapeSet for the new object accordingly.

Parameters

insn:SsaInsn: non-null; move result pseudo instruction to process

Returns:EscapeAnalysis.EscapeSet

non-null; an EscapeSet for the object referred to by the move result pseudo instruction

processPhiUse back to summary

processPhiUse	back to summary
private void processPhiUse(SsaInsn use, EscapeAnalysis.EscapeSet escSet, ArrayList<RegisterSpec> regWorklist) Handles phi uses of new objects. Will merge together the sources of a phi into a single EscapeSet. Adds the result of the phi to the worklist so its uses can be followed. Parameters use:SsaInsn `non-null;` phi use being processed escSet:EscapeAnalysis.EscapeSet `non-null;` EscapeSet for the object regWorklist:ArrayList<RegisterSpec> `non-null;` worklist of instructions left to process for this object

private void processPhiUse(SsaInsn use, EscapeAnalysis.EscapeSet escSet, ArrayList<RegisterSpec> regWorklist)

Handles phi uses of new objects. Will merge together the sources of a phi into a single EscapeSet. Adds the result of the phi to the worklist so its uses can be followed.

Parameters

use:SsaInsn: non-null; phi use being processed
escSet:EscapeAnalysis.EscapeSet: non-null; EscapeSet for the object
regWorklist:ArrayList<RegisterSpec>: non-null; worklist of instructions left to process for this object

processRegister back to summary

processRegister	back to summary
private void processRegister(RegisterSpec result, EscapeAnalysis.EscapeSet escSet) Iterate through all the uses of a new object. Parameters result:RegisterSpec `non-null;` register where new object is stored escSet:EscapeAnalysis.EscapeSet `non-null;` EscapeSet for the new object

private void processRegister(RegisterSpec result, EscapeAnalysis.EscapeSet escSet)

Iterate through all the uses of a new object.

Parameters

result:RegisterSpec: non-null; register where new object is stored
escSet:EscapeAnalysis.EscapeSet: non-null; EscapeSet for the new object

processUse back to summary

processUse	back to summary
private void processUse(RegisterSpec def, SsaInsn use, EscapeAnalysis.EscapeSet escSet, ArrayList<RegisterSpec> regWorklist) Handles non-phi uses of new objects. Checks to see how instruction is used and updates the escape state accordingly. Parameters def:RegisterSpec `non-null;` register holding definition of new object use:SsaInsn `non-null;` use of object being processed escSet:EscapeAnalysis.EscapeSet `non-null;` EscapeSet for the object regWorklist:ArrayList<RegisterSpec> `non-null;` worklist of instructions left to process for this object

private void processUse(RegisterSpec def, SsaInsn use, EscapeAnalysis.EscapeSet escSet, ArrayList<RegisterSpec> regWorklist)

Handles non-phi uses of new objects. Checks to see how instruction is used and updates the escape state accordingly.

Parameters

def:RegisterSpec: non-null; register holding definition of new object
use:SsaInsn: non-null; use of object being processed
escSet:EscapeAnalysis.EscapeSet: non-null; EscapeSet for the object
regWorklist:ArrayList<RegisterSpec>: non-null; worklist of instructions left to process for this object

replaceDef back to summary

replaceDef	back to summary
private void replaceDef(SsaInsn def, SsaInsn prev, int length, ArrayList<RegisterSpec> newRegs) Replaces the instructions that define an array with equivalent registers. For each entry in the array, a register is created, initialized to zero. A mapping between this register and the corresponding array index is added. Parameters def:SsaInsn `non-null;` move result instruction for array prev:SsaInsn `non-null;` instruction for instantiating new array length:int size of the new array newRegs:ArrayList<RegisterSpec> `non-null;` mapping of array indices to new registers to be populated

private void replaceDef(SsaInsn def, SsaInsn prev, int length, ArrayList<RegisterSpec> newRegs)

Replaces the instructions that define an array with equivalent registers. For each entry in the array, a register is created, initialized to zero. A mapping between this register and the corresponding array index is added.

Parameters

def:SsaInsn: non-null; move result instruction for array
prev:SsaInsn: non-null; instruction for instantiating new array
length:int: size of the new array
newRegs:ArrayList<RegisterSpec>: non-null; mapping of array indices to new registers to be populated

replaceNode back to summary

replaceNode	back to summary
private void replaceNode(EscapeAnalysis.EscapeSet newNode, EscapeAnalysis.EscapeSet oldNode) Merges all links in the lattice among two EscapeSets. On return, the newNode will have its old links as well as all links from the oldNode. The oldNode has all its links removed. Parameters newNode:EscapeAnalysis.EscapeSet `non-null;` the EscapeSet to merge all links into oldNode:EscapeAnalysis.EscapeSet `non-null;` the EscapeSet to remove all links from

private void replaceNode(EscapeAnalysis.EscapeSet newNode, EscapeAnalysis.EscapeSet oldNode)

Merges all links in the lattice among two EscapeSets. On return, the newNode will have its old links as well as all links from the oldNode. The oldNode has all its links removed.

Parameters

newNode:EscapeAnalysis.EscapeSet: non-null; the EscapeSet to merge all links into
oldNode:EscapeAnalysis.EscapeSet: non-null; the EscapeSet to remove all links from

replaceUse back to summary

replaceUse	back to summary
private void replaceUse(SsaInsn use, SsaInsn prev, ArrayList<RegisterSpec> newRegs, HashSet<SsaInsn> deletedInsns) Replaces the use for a scalar replaceable array. Gets and puts become move instructions, and array lengths and fills are handled. Can also identify ArrayIndexOutOfBounds exceptions and throw them if detected. Parameters use:SsaInsn `non-null;` move result instruction for array prev:SsaInsn `non-null;` instruction for instantiating new array newRegs:ArrayList<RegisterSpec> `non-null;` mapping of array indices to new registers deletedInsns:HashSet<SsaInsn> `non-null;` set of instructions marked for deletion

private void replaceUse(SsaInsn use, SsaInsn prev, ArrayList<RegisterSpec> newRegs, HashSet<SsaInsn> deletedInsns)

Replaces the use for a scalar replaceable array. Gets and puts become move instructions, and array lengths and fills are handled. Can also identify ArrayIndexOutOfBounds exceptions and throw them if detected.

Parameters

use:SsaInsn: non-null; move result instruction for array
prev:SsaInsn: non-null; instruction for instantiating new array
newRegs:ArrayList<RegisterSpec>: non-null; mapping of array indices to new registers
deletedInsns:HashSet<SsaInsn>: non-null; set of instructions marked for deletion

run	back to summary
private void run() Runs escape analysis and scalar replacement of arrays.

scalarReplacement	back to summary
private void scalarReplacement() Performs scalar replacement on all eligible arrays.

Modifier and Type	Field and Description
pack-priv ArrayList<EscapeAnalysis.EscapeSet>	childSets list of objects that are put into this object
pack-priv EscapeAnalysis.EscapeState	escape escape state of the object
pack-priv ArrayList<EscapeAnalysis.EscapeSet>	parentSets list of objects that this object is put into
pack-priv BitSet	regSet set containing all registers related to an object
pack-priv boolean	replaceableArray flag to indicate this object is a scalar replaceable array

Access	Constructor and Description
pack-priv	EscapeSet(int the SSA register that defines the object reg, int the number of registers in the method size, EscapeAnalysis.EscapeState the lattice value to initially set this to escState) Constructs an instance of an EscapeSet

Field Detail

childSets	back to summary
pack-priv ArrayList<EscapeAnalysis.EscapeSet> childSets list of objects that are put into this object

escape	back to summary
pack-priv EscapeAnalysis.EscapeState escape escape state of the object

parentSets	back to summary
pack-priv ArrayList<EscapeAnalysis.EscapeSet> parentSets list of objects that this object is put into

regSet	back to summary
pack-priv BitSet regSet set containing all registers related to an object

replaceableArray	back to summary
pack-priv boolean replaceableArray flag to indicate this object is a scalar replaceable array

Constructor Detail

EscapeSet	back to summary
pack-priv EscapeSet(int reg, int size, EscapeAnalysis.EscapeState escState) Constructs an instance of an EscapeSet Parameters reg:int the SSA register that defines the object size:int the number of registers in the method escState:EscapeAnalysis.EscapeState the lattice value to initially set this to

EscapeSet

back to summary

pack-priv EscapeSet(int reg, int size, EscapeAnalysis.EscapeState escState)

Constructs an instance of an EscapeSet

Parameters

reg:int: the SSA register that defines the object
size:int: the number of registers in the method
escState:EscapeAnalysis.EscapeState: the lattice value to initially set this to

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

public final Enum EscapeAnalysis.EscapeState

Class Inheritance

extends Enum<EscapeAnalysis.EscapeState>

java.lang.Object
java.lang.Enum
org.droidparts.dexmaker.dx.ssa.EscapeAnalysis.EscapeState

Lattice values used to indicate escape state for an object. Analysis can only raise escape state values, not lower them. TOP - Used for objects that haven't been analyzed yet NONE - Object does not escape, and is eligible for scalar replacement. METHOD - Object remains local to method, but can't be scalar replaced. INTER - Object is passed between methods. (treated as globally escaping since this is an intraprocedural analysis) GLOBAL - Object escapes globally.

Field Summary

Modifier and Type	Field and Description
public static final EscapeAnalysis.EscapeState	GLOBAL
public static final EscapeAnalysis.EscapeState	INTER
public static final EscapeAnalysis.EscapeState	METHOD
public static final EscapeAnalysis.EscapeState	NONE
public static final EscapeAnalysis.EscapeState	TOP

Constructor Summary

Access	Constructor and Description
private	EscapeState()

Method Summary

Modifier and Type	Method and Description
public static EscapeAnalysis.EscapeState	valueOf(String name)
public static EscapeAnalysis.EscapeState[]	values()

Inherited from java.lang.Enum:: clone compareTo describeConstable equals finalize getDeclaringClass hashCode name ordinal toString valueOf

Field Detail

GLOBAL	back to summary
public static final EscapeAnalysis.EscapeState GLOBAL

INTER	back to summary
public static final EscapeAnalysis.EscapeState INTER

METHOD	back to summary
public static final EscapeAnalysis.EscapeState METHOD

NONE	back to summary
public static final EscapeAnalysis.EscapeState NONE

TOP	back to summary
public static final EscapeAnalysis.EscapeState TOP

Constructor Detail

EscapeState	back to summary
private EscapeState()

Method Detail

valueOf	back to summary
public static EscapeAnalysis.EscapeState valueOf(String name)

values	back to summary
public static EscapeAnalysis.EscapeState[] values()

public Class EscapeAnalysis

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv Class EscapeAnalysis.EscapeSet

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

public final Enum EscapeAnalysis.EscapeState

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail