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

public Class DeadCodeRemover

extends Object
Class Inheritance
Imports
org.droidparts.dexmaker.dx.rop.code.RegisterSpec, .RegisterSpecList, java.util.ArrayList, .BitSet, .HashSet
A variation on Appel Algorithm 19.12 "Dead code elimination in SSA form". TODO this algorithm is more efficient if run in reverse from exit block to entry block.

Nested and Inner Type Summary

Modifier and TypeClass and Description
private static class
DeadCodeRemover.NoSideEffectVisitor

A callback class used to build up the initial worklist of registers defined by an instruction with no side effect.

Field Summary

Modifier and TypeField and Description
private final int
regCount

ssaMeth.getRegCount()

private final SsaMethod
ssaMeth

method we're processing

private final ArrayList<SsaInsn>[]
useList

use list indexed by register; modified during operation

private final BitSet
worklist

indexed by register: whether reg should be examined (does it correspond to a no-side-effect insn?)

Constructor Summary

AccessConstructor and Description
private
DeadCodeRemover(SsaMethod
method to process
ssaMethod)

Constructs an instance.

Method Summary

Modifier and TypeMethod and Description
private static boolean

Returns:

true if it has a side-effect
hasSideEffect(SsaInsn
null-ok; instruction in question
insn)

Returns true if this insn has a side-effect.

private boolean

Returns:

true if usage is circular without side effect
isCircularNoSideEffect(int
register to examine
regV, BitSet
a set of registers that we've already determined are only used as sources in operations with no side effect or null if this is the first recursion
set)

Returns true if the only uses of this register form a circle of operations with no side effects.

public static void
process(SsaMethod
method to process
ssaMethod)

Process a method with the dead-code remver

private void
pruneDeadInstructions()

Removes all instructions from every unreachable block.

private void
run()

Runs the dead code remover.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

regCountback to summary
private final int regCount

ssaMeth.getRegCount()

ssaMethback to summary
private final SsaMethod ssaMeth

method we're processing

useListback to summary
private final ArrayList<SsaInsn>[] useList

use list indexed by register; modified during operation

worklistback to summary
private final BitSet worklist

indexed by register: whether reg should be examined (does it correspond to a no-side-effect insn?)

Constructor Detail

DeadCodeRemoverback to summary
private DeadCodeRemover(SsaMethod ssaMethod)

Constructs an instance.

Parameters
ssaMethod:SsaMethod

method to process

Method Detail

hasSideEffectback to summary
private static boolean hasSideEffect(SsaInsn insn)

Returns true if this insn has a side-effect. Returns true if the insn is null for reasons stated in the code block.

Parameters
insn:SsaInsn

null-ok; instruction in question

Returns:boolean

true if it has a side-effect

isCircularNoSideEffectback to summary
private boolean isCircularNoSideEffect(int regV, BitSet set)

Returns true if the only uses of this register form a circle of operations with no side effects.

Parameters
regV:int

register to examine

set:BitSet

a set of registers that we've already determined are only used as sources in operations with no side effect or null if this is the first recursion

Returns:boolean

true if usage is circular without side effect

processback to summary
public static void process(SsaMethod ssaMethod)

Process a method with the dead-code remver

Parameters
ssaMethod:SsaMethod

method to process

pruneDeadInstructionsback to summary
private void pruneDeadInstructions()

Removes all instructions from every unreachable block.

runback to summary
private void run()

Runs the dead code remover.

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

private Class DeadCodeRemover.NoSideEffectVisitor

extends Object
implements Visitor
Class Inheritance
  • java.lang.Object
  • org.droidparts.dexmaker.dx.ssa.DeadCodeRemover.NoSideEffectVisitor
All Implemented Interfaces
org.droidparts.dexmaker.dx.ssa.SsaInsn.Visitor
A callback class used to build up the initial worklist of registers defined by an instruction with no side effect.

Field Summary

Modifier and TypeField and Description
pack-priv BitSet
noSideEffectRegs

Constructor Summary

AccessConstructor and Description
public
NoSideEffectVisitor(BitSet
to-build bitset of regs that are results of regs with no side effects
noSideEffectRegs)

Passes in data structures that will be filled out after ssaMeth.forEachInsn() is called with this instance.

Method Summary

Modifier and TypeMethod and Description
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
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
Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

noSideEffectRegsback to summary
pack-priv BitSet noSideEffectRegs

Constructor Detail

NoSideEffectVisitorback to summary
public NoSideEffectVisitor(BitSet noSideEffectRegs)

Passes in data structures that will be filled out after ssaMeth.forEachInsn() is called with this instance.

Parameters
noSideEffectRegs:BitSet

to-build bitset of regs that are results of regs with no side effects

Method Detail

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

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).

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

Parameters
phi:PhiInsn

non-null; the instruction to visit