Modifier and Type	Class and Description
public static class	SsaBasicBlock.LabelComparator Label comparator.
public static interface	SsaBasicBlock.Visitor Visitor interface for basic blocks.

Modifier and Type	Field and Description
private final ArrayList<SsaBasicBlock>	domChildren list of dom children
private int	index our index into parent.getBlock()
private ArrayList<SsaInsn>	insns `non-null;` insn list associated with this instance
public static final Comparator<SsaBasicBlock>	LABEL_COMPARATOR `non-null;` comparator for instances of this class that just compares block labels
private IntSet	liveIn `null-ok;` indexed by reg: the regs that are live-in at this block
private IntSet	liveOut `null-ok;` indexed by reg: the regs that are live-out at this block
private int	movesFromPhisAtBeginning the number of moves added to the beginning of the block during the phi-removal process.
private int	movesFromPhisAtEnd the number of moves added to the end of the block during the phi-removal process.
private SsaMethod	parent `non-null;` method we belong to
private BitSet	predecessors `non-null;` predecessor set (by block list index)
private int	primarySuccessor block list index of primary successor, or `-1` for no primary successor
private int	reachable contains last computed value of reachability of this block, or -1 if reachability hasn't been calculated yet
private int	ropLabel label of block in rop form
private IntList	successorList `non-null;` ordered successor list (same block may be listed more than once)
private BitSet	successors `non-null;` successor set (by block list index)

Access	Constructor and Description
public	SsaBasicBlock(final int index this block will have basicBlockIndex, final int original rop-form label ropLabel, final SsaMethod method of this block parent) Creates a new empty basic block.

Method Summary

Modifier and Type	Method and Description
public void	addDomChild(SsaBasicBlock `non-null;` new dom child child) Adds a basic block as a dom child for this block.
public void	addInsnToHead(Insn `non-null;` rop-form insn to add insn) Adds an insn to the head of this basic block, just after any phi insns.
public void	addLiveIn(int register that is live-in for this block. regV) Adds `regV` to the live-in list for this block.
public void	addLiveOut(int register that is live-out for this block. regV) Adds `regV` to the live-out list for this block.
public void	addMoveToBeginning(RegisterSpec move destination result, RegisterSpec move source source) Adds a move instruction after the phi insn block.
public void	addMoveToEnd(RegisterSpec move destination result, RegisterSpec move source source) Adds a move instruction to the end of this basic block, just before the last instruction.
public void	addPhiInsnForReg(int `>=0;` result reg reg) Adds a phi insn to the beginning of this block.
public void	addPhiInsnForReg(RegisterSpec `non-null;` reg resultSpec) Adds a phi insn to the beginning of this block.
private static boolean	Returns: true if register is fully or partially (for the case of wide registers) used. checkRegUsed(BitSet set, indexed by register number regsUsed, RegisterSpec register to mark as used rs) Checks to see if the register is used in a bitset, taking into account its category/width.
public void	exitBlockFixup(SsaBasicBlock `non-null;` exit block exitBlock) Attaches block to an exit block if necessary.
public void	forEachInsn(SsaInsn.Visitor `non-null;` callback interface visitor) Visits all insns in this block.
public void	forEachPhiInsn(PhiInsn.Visitor `non-null;` the callback v) Visits each phi insn.
private int	Returns: count of phi insns getCountPhiInsns() Gets the number of phi insns at the top of this basic block.
public ArrayList<SsaBasicBlock>	Returns: `non-null;` list of dom children getDomChildren() Gets the dom children for this node.
public int	Returns: the block index of this block getIndex()
public ArrayList<SsaInsn>	Returns: `non-null;` the (mutable) instruction list for this block, with phi insns at the beginning getInsns()
public IntSet	Returns: `non-null;` live-in register set. getLiveInRegs() Returns the set of live-in registers.
public IntSet	Returns: `non-null;` live-out register set getLiveOutRegs() Returns the set of live-out registers.
public SsaMethod	Returns: `non-null;` method that contains this block getParent()
public List<SsaInsn>	Returns: `non-null;` the (mutable) list of phi insns for this block getPhiInsns()
public BitSet	Returns: `non-null;` predecessors set, indexed by block index getPredecessors()
public SsaBasicBlock	Returns: `null-ok;` the primary successor block or `null` if there is none getPrimarySuccessor()
public int	Returns: `>= -1;` block index of primary successor or `-1` if no primary successor getPrimarySuccessorIndex()
public int	Returns: rop label of primary successor getPrimarySuccessorRopLabel()
public int	Returns: the label of this block in rop form getRopLabel()
public String	Returns: the label of this block in rop form as a hex string getRopLabelString()
public IntList	Returns: successor list of rop labels getRopLabelSuccessorList()
public IntList	Returns: `non-null;` ordered successor list, containing block indicies getSuccessorList()
public BitSet	Returns: `non-null;` successors set, indexed by block index getSuccessors()
public SsaBasicBlock	Returns: `non-null;` an appropriately-constructed instance insertNewPredecessor() Inserts a new empty GOTO block as a predecessor to this block.
public SsaBasicBlock	Returns: `non-null;` an appropriately-constructed instance insertNewSuccessor(SsaBasicBlock current successor (B) other) Constructs and inserts a new empty GOTO block `Z` between this block (`A`) and a current successor block (`B`).
public boolean	Returns: true if this is the one-and-only exit block for this method isExitBlock()
public boolean	Returns: `true` if reachable isReachable() Returns true if this block was last calculated to be reachable.
public static SsaBasicBlock	Returns: new instance newFromRop(RopMethod original method rmeth, int index this block will have basicBlockIndex, final SsaMethod method of this block predecessor set will be updated parent) Creates a new SSA basic block from a ROP form basic block.
public void	removeAllPhiInsns() Deletes all phi insns.
public void	removeSuccessor(int index of successor block to remove oldIndex) Removes a successor from this block's successor list.
public void	replaceLastInsn(Insn `non-null;` rop-form insn to add, which must branch. insn) Replaces the last insn in this block.
public void	replaceSuccessor(int index of old successor block oldIndex, int index of new successor block newIndex) Replaces an old successor with a new successor.
public void	scheduleMovesFromPhis() Sorts move instructions added via `addMoveToEnd` during phi removal so that results don't overwrite sources that are used.
private void	scheduleUseBeforeAssigned(List<SsaInsn> List of instructions. Must consist only of moves. toSchedule) Ensures that all move operations in this block occur such that reads of any register happen before writes to that register.
public void	setReachable(int new value of reachability for block reach) Sets reachability of block to specified value
private static void	setRegsUsed(BitSet set, indexed by register number regsUsed, RegisterSpec register to mark as used rs) Sets the register as used in a bitset, taking into account its category/width.
public String	toString() Overrides java.lang.Object.toString. Returns a string representation of the object.

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

Field Detail

domChildren	back to summary
private final ArrayList<SsaBasicBlock> domChildren list of dom children

index	back to summary
private int index our index into parent.getBlock()

insns	back to summary
private ArrayList<SsaInsn> insns `non-null;` insn list associated with this instance

LABEL_COMPARATOR	back to summary
public static final Comparator<SsaBasicBlock> LABEL_COMPARATOR `non-null;` comparator for instances of this class that just compares block labels

liveIn	back to summary
private IntSet liveIn `null-ok;` indexed by reg: the regs that are live-in at this block

liveOut	back to summary
private IntSet liveOut `null-ok;` indexed by reg: the regs that are live-out at this block

movesFromPhisAtBeginning	back to summary
private int movesFromPhisAtBeginning the number of moves added to the beginning of the block during the phi-removal process. Retained for subsequent move scheduling.

movesFromPhisAtEnd	back to summary
private int movesFromPhisAtEnd the number of moves added to the end of the block during the phi-removal process. Retained for subsequent move scheduling.

parent	back to summary
private SsaMethod parent `non-null;` method we belong to

predecessors	back to summary
private BitSet predecessors `non-null;` predecessor set (by block list index)

primarySuccessor	back to summary
private int primarySuccessor block list index of primary successor, or `-1` for no primary successor

reachable	back to summary
private int reachable contains last computed value of reachability of this block, or -1 if reachability hasn't been calculated yet

ropLabel	back to summary
private int ropLabel label of block in rop form

successorList	back to summary
private IntList successorList `non-null;` ordered successor list (same block may be listed more than once)

successors	back to summary
private BitSet successors `non-null;` successor set (by block list index)

Constructor Detail

SsaBasicBlock	back to summary
public SsaBasicBlock(final int basicBlockIndex, final int ropLabel, final SsaMethod parent) Creates a new empty basic block. Parameters basicBlockIndex:int index this block will have ropLabel:int original rop-form label parent:SsaMethod method of this block

SsaBasicBlock

back to summary

public SsaBasicBlock(final int basicBlockIndex, final int ropLabel, final SsaMethod parent)

Creates a new empty basic block.

Parameters

basicBlockIndex:int: index this block will have
ropLabel:int: original rop-form label
parent:SsaMethod: method of this block

Method Detail

addDomChild back to summary

addDomChild	back to summary
public void addDomChild(SsaBasicBlock child) Adds a basic block as a dom child for this block. Used when constructing the dom tree. Parameters child:SsaBasicBlock `non-null;` new dom child

public void addDomChild(SsaBasicBlock child)

Adds a basic block as a dom child for this block. Used when constructing the dom tree.

Parameters

child:SsaBasicBlock: non-null; new dom child

addInsnToHead back to summary

addInsnToHead	back to summary
public void addInsnToHead(Insn insn) Adds an insn to the head of this basic block, just after any phi insns. Parameters insn:Insn `non-null;` rop-form insn to add

public void addInsnToHead(Insn insn)

Adds an insn to the head of this basic block, just after any phi insns.

Parameters

insn:Insn: non-null; rop-form insn to add

addLiveIn back to summary

addLiveIn	back to summary
public void addLiveIn(int regV) Adds `regV` to the live-in list for this block. This is called by the liveness analyzer. Parameters regV:int register that is live-in for this block.

public void addLiveIn(int regV)

Adds regV to the live-in list for this block. This is called by the liveness analyzer.

Parameters

regV:int: register that is live-in for this block.

addLiveOut back to summary

addLiveOut	back to summary
public void addLiveOut(int regV) Adds `regV` to the live-out list for this block. This is called by the liveness analyzer. Parameters regV:int register that is live-out for this block.

public void addLiveOut(int regV)

Adds regV to the live-out list for this block. This is called by the liveness analyzer.

Parameters

regV:int: register that is live-out for this block.

addMoveToBeginning	back to summary
public void addMoveToBeginning(RegisterSpec result, RegisterSpec source) Adds a move instruction after the phi insn block. Parameters result:RegisterSpec move destination source:RegisterSpec move source

addMoveToBeginning

back to summary

public void addMoveToBeginning(RegisterSpec result, RegisterSpec source)

Adds a move instruction after the phi insn block.

Parameters

result:RegisterSpec: move destination
source:RegisterSpec: move source

addMoveToEnd	back to summary
public void addMoveToEnd(RegisterSpec result, RegisterSpec source) Adds a move instruction to the end of this basic block, just before the last instruction. If the result of the final instruction is the source in question, then the move is placed at the beginning of the primary successor block. This is for unversioned registers. Parameters result:RegisterSpec move destination source:RegisterSpec move source

addMoveToEnd

back to summary

public void addMoveToEnd(RegisterSpec result, RegisterSpec source)

Adds a move instruction to the end of this basic block, just before the last instruction. If the result of the final instruction is the source in question, then the move is placed at the beginning of the primary successor block. This is for unversioned registers.

Parameters

result:RegisterSpec: move destination
source:RegisterSpec: move source

addPhiInsnForReg back to summary

addPhiInsnForReg	back to summary
public void addPhiInsnForReg(int reg) Adds a phi insn to the beginning of this block. The result type of the phi will be set to void, to indicate that it's currently unknown. Parameters reg:int `>=0;` result reg

public void addPhiInsnForReg(int reg)

Adds a phi insn to the beginning of this block. The result type of the phi will be set to void, to indicate that it's currently unknown.

Parameters

reg:int: >=0; result reg

addPhiInsnForReg back to summary

addPhiInsnForReg	back to summary
public void addPhiInsnForReg(RegisterSpec resultSpec) Adds a phi insn to the beginning of this block. This is to be used when the result type or local-association can be determined at phi insert time. Parameters resultSpec:RegisterSpec `non-null;` reg

public void addPhiInsnForReg(RegisterSpec resultSpec)

Adds a phi insn to the beginning of this block. This is to be used when the result type or local-association can be determined at phi insert time.

Parameters

resultSpec:RegisterSpec: non-null; reg

checkRegUsed	back to summary
private static boolean checkRegUsed(BitSet regsUsed, RegisterSpec rs) Checks to see if the register is used in a bitset, taking into account its category/width. Parameters regsUsed:BitSet set, indexed by register number rs:RegisterSpec register to mark as used Returns:boolean true if register is fully or partially (for the case of wide registers) used.

checkRegUsed

back to summary

private static boolean checkRegUsed(BitSet regsUsed, RegisterSpec rs)

Checks to see if the register is used in a bitset, taking into account its category/width.

Parameters

regsUsed:BitSet: set, indexed by register number
rs:RegisterSpec: register to mark as used

Returns:boolean

true if register is fully or partially (for the case of wide registers) used.

exitBlockFixup back to summary

exitBlockFixup	back to summary
public void exitBlockFixup(SsaBasicBlock exitBlock) Attaches block to an exit block if necessary. If this block is not an exit predecessor or is the exit block, this block does nothing. For use by `org.droidparts.dexmaker.dx.ssa.SsaMethod#makeExitBlock` Parameters exitBlock:SsaBasicBlock `non-null;` exit block

public void exitBlockFixup(SsaBasicBlock exitBlock)

Attaches block to an exit block if necessary. If this block is not an exit predecessor or is the exit block, this block does nothing. For use by org.droidparts.dexmaker.dx.ssa.SsaMethod#makeExitBlock

Parameters

exitBlock:SsaBasicBlock: non-null; exit block

forEachInsn back to summary

forEachInsn	back to summary
public void forEachInsn(SsaInsn.Visitor visitor) Visits all insns in this block. Parameters visitor:SsaInsn.Visitor `non-null;` callback interface

public void forEachInsn(SsaInsn.Visitor visitor)

Visits all insns in this block.

Parameters

visitor:SsaInsn.Visitor: non-null; callback interface

forEachPhiInsn back to summary

forEachPhiInsn	back to summary
public void forEachPhiInsn(PhiInsn.Visitor v) Visits each phi insn. Parameters v:PhiInsn.Visitor `non-null;` the callback

public void forEachPhiInsn(PhiInsn.Visitor v)

Visits each phi insn.

Parameters

v:PhiInsn.Visitor: non-null; the callback

getCountPhiInsns	back to summary
private int getCountPhiInsns() Gets the number of phi insns at the top of this basic block. Returns:int count of phi insns

getCountPhiInsns

back to summary

private int getCountPhiInsns()

Gets the number of phi insns at the top of this basic block.

Returns:int: count of phi insns

getDomChildren back to summary

getDomChildren	back to summary
public ArrayList<SsaBasicBlock> getDomChildren() Gets the dom children for this node. Don't modify this list. Returns:ArrayList<SsaBasicBlock> `non-null;` list of dom children

public ArrayList<SsaBasicBlock> getDomChildren()

Gets the dom children for this node. Don't modify this list.

Returns:ArrayList<SsaBasicBlock>: non-null; list of dom children

getIndex	back to summary
public int getIndex() Returns:int the block index of this block

getInsns	back to summary
public ArrayList<SsaInsn> getInsns() Returns:ArrayList<SsaInsn> `non-null;` the (mutable) instruction list for this block, with phi insns at the beginning

getLiveInRegs back to summary

getLiveInRegs	back to summary
public IntSet getLiveInRegs() Returns the set of live-in registers. Valid after register interference graph has been generated, otherwise empty. Returns:IntSet `non-null;` live-in register set.

public IntSet getLiveInRegs()

Returns the set of live-in registers. Valid after register interference graph has been generated, otherwise empty.

Returns:IntSet: non-null; live-in register set.

getLiveOutRegs back to summary

getLiveOutRegs	back to summary
public IntSet getLiveOutRegs() Returns the set of live-out registers. Valid after register interference graph has been generated, otherwise empty. Returns:IntSet `non-null;` live-out register set

public IntSet getLiveOutRegs()

Returns the set of live-out registers. Valid after register interference graph has been generated, otherwise empty.

Returns:IntSet: non-null; live-out register set

getParent	back to summary
public SsaMethod getParent() Returns:SsaMethod `non-null;` method that contains this block

getPhiInsns	back to summary
public List<SsaInsn> getPhiInsns() Returns:List<SsaInsn> `non-null;` the (mutable) list of phi insns for this block

getPredecessors	back to summary
public BitSet getPredecessors() Returns:BitSet `non-null;` predecessors set, indexed by block index

getPrimarySuccessor	back to summary
public SsaBasicBlock getPrimarySuccessor() Returns:SsaBasicBlock `null-ok;` the primary successor block or `null` if there is none

getPrimarySuccessorIndex	back to summary
public int getPrimarySuccessorIndex() Returns:int `>= -1;` block index of primary successor or `-1` if no primary successor

getPrimarySuccessorRopLabel	back to summary
public int getPrimarySuccessorRopLabel() Returns:int rop label of primary successor

getRopLabel	back to summary
public int getRopLabel() Returns:int the label of this block in rop form

getRopLabelString	back to summary
public String getRopLabelString() Returns:String the label of this block in rop form as a hex string

getRopLabelSuccessorList	back to summary
public IntList getRopLabelSuccessorList() Returns:IntList successor list of rop labels

getSuccessorList	back to summary
public IntList getSuccessorList() Returns:IntList `non-null;` ordered successor list, containing block indicies

getSuccessors	back to summary
public BitSet getSuccessors() Returns:BitSet `non-null;` successors set, indexed by block index

insertNewPredecessor back to summary

insertNewPredecessor	back to summary
public SsaBasicBlock insertNewPredecessor() Inserts a new empty GOTO block as a predecessor to this block. All previous predecessors will be predecessors to the new block. Returns:SsaBasicBlock `non-null;` an appropriately-constructed instance

public SsaBasicBlock insertNewPredecessor()

Inserts a new empty GOTO block as a predecessor to this block. All previous predecessors will be predecessors to the new block.

Returns:SsaBasicBlock: non-null; an appropriately-constructed instance

insertNewSuccessor back to summary

public SsaBasicBlock insertNewSuccessor(SsaBasicBlock other)

Constructs and inserts a new empty GOTO block Z between this block (A) and a current successor block (B). The new block will replace B as A's successor and A as B's predecessor. A and B will no longer be directly connected. If B is listed as a successor multiple times, all references are replaced.

Parameters

other:SsaBasicBlock: current successor (B)

Returns:SsaBasicBlock

non-null; an appropriately-constructed instance

isExitBlock	back to summary
public boolean isExitBlock() Returns:boolean true if this is the one-and-only exit block for this method

isReachable back to summary

public boolean isReachable()

Returns true if this block was last calculated to be reachable. Recalculates reachability if value has never been computed.

Returns:boolean: true if reachable

newFromRop

back to summary

public static SsaBasicBlock newFromRop(RopMethod rmeth, int basicBlockIndex, final SsaMethod parent)

Creates a new SSA basic block from a ROP form basic block.

Parameters

rmeth:RopMethod: original method
basicBlockIndex:int: index this block will have
parent:SsaMethod: method of this block predecessor set will be updated

Returns:SsaBasicBlock

new instance

removeAllPhiInsns	back to summary
public void removeAllPhiInsns() Deletes all phi insns. Do this after adding appropriate move insns.

removeSuccessor

back to summary

public void removeSuccessor(int oldIndex)

Removes a successor from this block's successor list.

Parameters

oldIndex:int: index of successor block to remove

replaceLastInsn back to summary

public void replaceLastInsn(Insn insn)

Replaces the last insn in this block. The provided insn must have some branchingness.

Parameters

insn:Insn: non-null; rop-form insn to add, which must branch.

replaceSuccessor back to summary

public void replaceSuccessor(int oldIndex, int newIndex)

Replaces an old successor with a new successor. This will throw RuntimeException if oldIndex was not a successor.

Parameters

oldIndex:int: index of old successor block
newIndex:int: index of new successor block

scheduleMovesFromPhis back to summary

public void scheduleMovesFromPhis()

Sorts move instructions added via addMoveToEnd during phi removal so that results don't overwrite sources that are used. For use after all phis have been removed and all calls to addMoveToEnd() have been made.

This is necessary because copy-propogation may have left us in a state where the same basic block has the same register as a phi operand and a result. In this case, the register in the phi operand always refers value before any other phis have executed.

scheduleUseBeforeAssigned

back to summary

private void scheduleUseBeforeAssigned(List<SsaInsn> toSchedule)

Ensures that all move operations in this block occur such that reads of any register happen before writes to that register.

Note

caller is expected to returnSpareRegisters()! TODO: See Briggs, et al "Practical Improvements to the Construction and Destruction of Static Single Assignment Form" section 5. a) This can be done in three passes.

Parameters

toSchedule:List<SsaInsn>: List of instructions. Must consist only of moves.

setReachable

back to summary

public void setReachable(int reach)

Sets reachability of block to specified value

Parameters

reach:int: new value of reachability for block

setRegsUsed

back to summary

private static void setRegsUsed(BitSet regsUsed, RegisterSpec rs)

Sets the register as used in a bitset, taking into account its category/width.

Parameters

regsUsed:BitSet: set, indexed by register number
rs:RegisterSpec: register to mark as used

toString

back to summary

public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object.

Returns:String

a string representation of the object

Annotations

@Override

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

public final Class SsaBasicBlock.LabelComparator

Class Inheritance

extends Object
implements Comparator<SsaBasicBlock>

java.lang.Object
org.droidparts.dexmaker.dx.ssa.SsaBasicBlock.LabelComparator

All Implemented Interfaces

java.util.Comparator

Label comparator.

Constructor Summary

Access	Constructor and Description
public	LabelComparator()

Method Summary

Modifier and Type	Method and Description
public int	compare(SsaBasicBlock the first object to be compared. b1, SsaBasicBlock the second object to be compared. b2) Implements java.util.Comparator.compare. Compares its two arguments for order.

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

Constructor Detail

LabelComparator	back to summary
public LabelComparator()

Method Detail

compare back to summary

public int compare(SsaBasicBlock b1, SsaBasicBlock b2)

Implements java.util.Comparator.compare.

Doc from java.util.Comparator.compare.

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

The implementor must ensure that signum(compare(x, y)) == -signum(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that signum(compare(x, z))==signum(compare(y, z)) for all z.

Parameters

b1:SsaBasicBlock: the first object to be compared.
b2:SsaBasicBlock: the second object to be compared.

Returns:int

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

public final Class SsaBasicBlock

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

public final Class SsaBasicBlock.LabelComparator

Constructor Summary

Method Summary

Constructor Detail

Method Detail

public Interface SsaBasicBlock.Visitor

Method Summary

Method Detail