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

public Class SsaRenamer

extends Object
implements Runnable
Class Inheritance
All Implemented Interfaces
java.lang.Runnable
Imports
org.droidparts.dexmaker.dx.rop.code.*, org.droidparts.dexmaker.dx.rop.type.Type, org.droidparts.dexmaker.dx.util.IntList, java.util.ArrayList, .BitSet, .HashMap, .HashSet
Complete transformation to SSA form by renaming all registers accessed.

See Appel algorithm 19.7

Unlike the original algorithm presented in Appel, this renamer converts to a new flat (versionless) register space. The "version 0" registers, which represent the initial state of the Rop registers and should never actually be meaningfully accessed in a legal program, are represented as the first N registers in the SSA namespace. Subsequent assignments are assigned new unique names. Note that the incoming Rop representation has a concept of register widths, where 64-bit values are stored into two adjoining Rop registers. This adjoining register representation is ignored in SSA form conversion and while in SSA form, each register can be e either 32 or 64 bits wide depending on use. The adjoining-register represention is re-created later when converting back to Rop form.

But, please note, the SSA Renamer's ignoring of the adjoining-register ROP representation means that unaligned accesses to 64-bit registers are not supported. For example, you cannot do a 32-bit operation on a portion of a 64-bit register. This will never be observed to happen when coming from Java code, of course.

The implementation here, rather than keeping a single register version stack for the entire method as the dom tree is walked, instead keeps a mapping table for the current block being processed. Once the current block has been processed, this mapping table is then copied and used as the initial state for child blocks.

Nested and Inner Type Summary

Modifier and TypeClass and Description
private class
SsaRenamer.BlockRenamer

Processes all insns in a block and renames their registers as appropriate.

Field Summary

Modifier and TypeField and Description
private static final boolean
DEBUG

debug flag

private int
nextSsaReg

next available SSA register

private final int
ropRegCount

the number of original rop registers

private final SsaMethod
ssaMeth

method we're processing

private final ArrayList<LocalItem>
ssaRegToLocalItems

map of SSA register number to debug (local var names) or null of n/a

private IntList
ssaRegToRopReg

maps SSA registers back to the original rop number.

private final RegisterSpec[][]
startsForBlocks

indexed by block index; register version state for each block start.

private int
threshold

work only on registers above this value

Constructor Summary

AccessConstructor and Description
public
SsaRenamer(SsaMethod
non-null; un-renamed SSA method that will be renamed.
ssaMeth)

Constructs an instance of the renamer

public
SsaRenamer(SsaMethod
non-null; un-renamed SSA method that will be renamed.
ssaMeth, int
registers below this number are unchanged
thresh)

Constructs an instance of the renamer with threshold set

Method Summary

Modifier and TypeMethod and Description
private static RegisterSpec[]

Returns:

non-null; new instance
dupArray(RegisterSpec[]
non-null; array to duplicate
orig)

Duplicates a RegisterSpec array.

private static boolean

Returns:

Returns true if a and b are equal or are both null
equalsHandlesNulls(Object
null-ok
a, Object
null-ok
b)

Returns true if a and b are equal or are both null.

private LocalItem

Returns:

null-ok; Local variable name or null if none
getLocalForNewReg(int
register in SSA name space
ssaReg)

Gets a local variable item for a specified register.

private boolean

Returns:

true if its register number is below the threshold
isBelowThresholdRegister(int
the SSA register in question
ssaReg)

Returns true if this SSA register is below the specified threshold.

private boolean

Returns:

true if it is a version 0 register.
isVersionZeroRegister(int
the SSA register in question
ssaReg)

Returns true if this SSA register is a "version 0" register.

public void
run()

Implements java.lang.Runnable.run.

Performs renaming transformation, modifying the method's instructions in-place.
private void
setNameForSsaReg(RegisterSpec
non-null named register spec in SSA name space
ssaReg)

Records a debug (local variable) name for a specified register.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

DEBUGback to summary
private static final boolean DEBUG

debug flag

nextSsaRegback to summary
private int nextSsaReg

next available SSA register

ropRegCountback to summary
private final int ropRegCount

the number of original rop registers

ssaMethback to summary
private final SsaMethod ssaMeth

method we're processing

ssaRegToLocalItemsback to summary
private final ArrayList<LocalItem> ssaRegToLocalItems

map of SSA register number to debug (local var names) or null of n/a

ssaRegToRopRegback to summary
private IntList ssaRegToRopReg

maps SSA registers back to the original rop number. Used for debug only.

startsForBlocksback to summary
private final RegisterSpec[][] startsForBlocks

indexed by block index; register version state for each block start. This list is updated by each dom parent for its children. The only sub-arrays that exist at any one time are the start states for blocks yet to be processed by a BlockRenamer instance.

thresholdback to summary
private int threshold

work only on registers above this value

Constructor Detail

SsaRenamerback to summary
public SsaRenamer(SsaMethod ssaMeth)

Constructs an instance of the renamer

Parameters
ssaMeth:SsaMethod

non-null; un-renamed SSA method that will be renamed.

SsaRenamerback to summary
public SsaRenamer(SsaMethod ssaMeth, int thresh)

Constructs an instance of the renamer with threshold set

Parameters
ssaMeth:SsaMethod

non-null; un-renamed SSA method that will be renamed.

thresh:int

registers below this number are unchanged

Method Detail

dupArrayback to summary
private static RegisterSpec[] dupArray(RegisterSpec[] orig)

Duplicates a RegisterSpec array.

Parameters
orig:RegisterSpec[]

non-null; array to duplicate

Returns:RegisterSpec[]

non-null; new instance

equalsHandlesNullsback to summary
private static boolean equalsHandlesNulls(Object a, Object b)

Returns true if a and b are equal or are both null.

Parameters
a:Object

null-ok

b:Object

null-ok

Returns:boolean

Returns true if a and b are equal or are both null

getLocalForNewRegback to summary
private LocalItem getLocalForNewReg(int ssaReg)

Gets a local variable item for a specified register.

Parameters
ssaReg:int

register in SSA name space

Returns:LocalItem

null-ok; Local variable name or null if none

isBelowThresholdRegisterback to summary
private boolean isBelowThresholdRegister(int ssaReg)

Returns true if this SSA register is below the specified threshold. Used when most code is already in SSA form, and renaming is needed only for registers above a certain threshold.

Parameters
ssaReg:int

the SSA register in question

Returns:boolean

true if its register number is below the threshold

isVersionZeroRegisterback to summary
private boolean isVersionZeroRegister(int ssaReg)

Returns true if this SSA register is a "version 0" register. All version 0 registers are assigned the first N register numbers, where N is the count of original rop registers.

Parameters
ssaReg:int

the SSA register in question

Returns:boolean

true if it is a version 0 register.

runback to summary
public void run()

Implements java.lang.Runnable.run.

Performs renaming transformation, modifying the method's instructions in-place.

setNameForSsaRegback to summary
private void setNameForSsaReg(RegisterSpec ssaReg)

Records a debug (local variable) name for a specified register.

Parameters
ssaReg:RegisterSpec

non-null named register spec in SSA name space

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

private Class SsaRenamer.BlockRenamer

extends Object
implements Visitor
Class Inheritance
All Implemented Interfaces
org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor
Processes all insns in a block and renames their registers as appropriate.

Nested and Inner Type Summary

Modifier and TypeClass and Description
private class
SsaRenamer.BlockRenamer.RenamingMapper

Provides a register mapping between the old register space and the current renaming mapping.

Field Summary

Modifier and TypeField and Description
private final SsaBasicBlock
block

non-null; block we're processing.

private final RegisterSpec[]
currentMapping

non-null; indexed by old register name.

private final HashMap<SsaInsn, SsaInsn>
insnsToReplace

maps the set of insns to replace after renaming is finished on the block.

private final SsaRenamer.BlockRenamer.RenamingMapper
mapper

private final HashSet<SsaInsn>
movesToKeep

contains the set of moves we need to keep to preserve local var info.

Constructor Summary

AccessConstructor and Description
pack-priv
BlockRenamer(final SsaBasicBlock
non-null; block to process
block)

Constructs a block renamer instance.

Method Summary

Modifier and TypeMethod and Description
private void
addMapping(int
>= 0; rop register number
ropReg, RegisterSpec
non-null; an SSA register that has just been added to currentMapping
ssaReg)

Enforces a few contraints when a register mapping is added.

public void
process()

Renames all the variables in this block and inserts appriopriate phis in successor blocks.

pack-priv void
processResultReg(SsaInsn
insn to process.
insn)

Renames the result register of this insn and updates the current register mapping.

private void
updateSuccessorPhis()

Updates the phi insns in successor blocks with operands based on the current mapping of the rop register the phis represent.

public void
visitMoveInsn(NormalSsaInsn
non-null; the instruction to visit
insn)

Implements org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor.visitMoveInsn.

Any non-phi move instruction Move insns are treated as a simple mapping operation, and will later be removed unless they represent a local variable assignment.
public void
visitNonMoveInsn(NormalSsaInsn
non-null; the instruction to visit
insn)

Implements org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor.visitNonMoveInsn.

Any insn that isn't a move or a phi (which is also a move).
public void
visitPhiInsn(PhiInsn
non-null; the instruction to visit
phi)

Implements org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor.visitPhiInsn.

Any phi insn Phi insns have their result registers renamed.
Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

blockback to summary
private final SsaBasicBlock block

non-null; block we're processing.

currentMappingback to summary
private final RegisterSpec[] currentMapping

non-null; indexed by old register name. The current top of the version stack as seen by this block. It's initialized from the ending state of its dom parent, updated as the block's instructions are processed, and then copied to each one of its dom children.

insnsToReplaceback to summary
private final HashMap<SsaInsn, SsaInsn> insnsToReplace

maps the set of insns to replace after renaming is finished on the block.

mapperback to summary
private final SsaRenamer.BlockRenamer.RenamingMapper mapper
movesToKeepback to summary
private final HashSet<SsaInsn> movesToKeep

contains the set of moves we need to keep to preserve local var info. All other moves will be deleted.

Constructor Detail

BlockRenamerback to summary
pack-priv BlockRenamer(final SsaBasicBlock block)

Constructs a block renamer instance. Call process to process.

Parameters
block:SsaBasicBlock

non-null; block to process

Method Detail

addMappingback to summary
private void addMapping(int ropReg, RegisterSpec ssaReg)

Enforces a few contraints when a register mapping is added.

  1. Ensures that all new SSA registers specs in the mapping table with the same register number are identical. In effect, once an SSA register spec has received or lost a local variable name, then every old-namespace register that maps to it should gain or lose its local variable name as well.
  2. Records the local name associated with the register so that a register is never associated with more than one local.
  3. ensures that only one SSA register at a time is considered to be associated with a local variable. When currentMapping is updated and the newly added element is named, strip that name from any other SSA registers.
Parameters
ropReg:int

>= 0; rop register number

ssaReg:RegisterSpec

non-null; an SSA register that has just been added to currentMapping

processback to summary
public void process()

Renames all the variables in this block and inserts appriopriate phis in successor blocks.

processResultRegback to summary
pack-priv void processResultReg(SsaInsn insn)

Renames the result register of this insn and updates the current register mapping. Does nothing if this insn has no result. Applied to all non-move insns.

Parameters
insn:SsaInsn

insn to process.

updateSuccessorPhisback to summary
private void updateSuccessorPhis()

Updates the phi insns in successor blocks with operands based on the current mapping of the rop register the phis represent.

visitMoveInsnback to summary
public void visitMoveInsn(NormalSsaInsn insn)

Implements org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor.visitMoveInsn.

Doc from org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor.visitMoveInsn.

Any non-phi move instruction Move insns are treated as a simple mapping operation, and will later be removed unless they represent a local variable assignment. If they represent a local variable assignement, they are preserved.

Parameters
insn:NormalSsaInsn

non-null; the instruction to visit

visitNonMoveInsnback to summary
public void visitNonMoveInsn(NormalSsaInsn insn)

Implements org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor.visitNonMoveInsn.

Doc from org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor.visitNonMoveInsn.

Any insn that isn't a move or a phi (which is also a move). All insns that are not move or phi insns have their source registers mapped ot the current mapping. Their result registers are then renamed to a new SSA register which is then added to the current register mapping.

Parameters
insn:NormalSsaInsn

non-null; the instruction to visit

visitPhiInsnback to summary
public void visitPhiInsn(PhiInsn phi)

Implements org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor.visitPhiInsn.

Doc from org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor.visitPhiInsn.

Any phi insn Phi insns have their result registers renamed.

Parameters
phi:PhiInsn

non-null; the instruction to visit

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

private Class SsaRenamer.BlockRenamer.RenamingMapper

extends RegisterMapper
Class Inheritance
Provides a register mapping between the old register space and the current renaming mapping. The mapping is updated as the current block's instructions are processed.

Constructor Summary

AccessConstructor and Description
public
RenamingMapper()

Method Summary

Modifier and TypeMethod and Description
public int
getNewRegisterCount()

Implements abstract org.droidparts.dexmaker.dx.ssa.RegisterMapper.getNewRegisterCount.

Gets the count of registers (really, the total register width, since category width is counted) in the new namespace.
public RegisterSpec
map(RegisterSpec
old register
registerSpec)

Implements abstract org.droidparts.dexmaker.dx.ssa.RegisterMapper.map.

Inherited from org.droidparts.dexmaker.dx.ssa.RegisterMapper:
map

Constructor Detail

RenamingMapperback to summary
public RenamingMapper()

Method Detail

getNewRegisterCountback to summary
public int getNewRegisterCount()

Implements abstract org.droidparts.dexmaker.dx.ssa.RegisterMapper.getNewRegisterCount.

Doc from org.droidparts.dexmaker.dx.ssa.RegisterMapper.getNewRegisterCount.

Gets the count of registers (really, the total register width, since category width is counted) in the new namespace.

Returns:int

>= 0 width of new namespace.

Annotations
@Override
mapback to summary
public RegisterSpec map(RegisterSpec registerSpec)

Implements abstract org.droidparts.dexmaker.dx.ssa.RegisterMapper.map.

Parameters
registerSpec:RegisterSpec

Doc from org.droidparts.dexmaker.dx.ssa.RegisterMapper.map.

old register

Returns:RegisterSpec

Doc from org.droidparts.dexmaker.dx.ssa.RegisterMapper.map.

register in new space

Annotations
@Override