soot.shimple.internal
Class PhiNodeManager

java.lang.Object
  soot.shimple.internal.PhiNodeManager

public class PhiNodeManager
extends Object

Author:

Navindra Umanee

See Also:

ShimpleBody, Efficiently Computing Static Single Assignment Form and the Control Dependence Graph

Field Summary

protected ShimpleBody	body
protected BlockGraph	cfg
protected DominanceFrontier	df
protected DominatorTree	dt
protected GuaranteedDefs	gd
protected ShimpleFactory	sf
protected Map<Unit,Block>	unitToBlock
protected MultiMap	varToBlocks

Constructor Summary

PhiNodeManager(ShimpleBody body)

Method Summary

boolean	doEliminatePhiNodes() Eliminate Phi nodes in block by naively replacing them with shimple assignment statements in the control flow predecessors.
boolean	dominates(Unit champ, Unit challenger) Returns true if champ dominates challenger.
Map<Unit,Block>	getUnitToBlockMap(BlockGraph blocks) Convenience function that maps units to blocks.
boolean	insertTrivialPhiNodes() Phi node Insertion Algorithm from Cytron et al 91, P24-5,
protected boolean	needsPhiNode(Local local, Block block) Function that allows us to weed out special cases where we do not require Phi nodes.
void	prependTrivialPhiNode(Local local, Block frontierBlock) Inserts a trivial Phi node with the appropriate number of arguments.
void	trimExceptionalPhiNodes() Exceptional Phi nodes have a huge number of arguments and control flow predecessors by default.
void	trimPhiNode(PhiExpr phiExpr)
void	update()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

body

protected ShimpleBody body

sf

protected ShimpleFactory sf

dt

protected DominatorTree dt

df

protected DominanceFrontier df

cfg

protected BlockGraph cfg

gd

protected GuaranteedDefs gd

varToBlocks

protected MultiMap varToBlocks

unitToBlock

protected Map<Unit,Block> unitToBlock

Constructor Detail

PhiNodeManager

public PhiNodeManager(ShimpleBody body)

Method Detail

update

public void update()

insertTrivialPhiNodes

public boolean insertTrivialPhiNodes()

Phi node Insertion Algorithm from Cytron et al 91, P24-5,

Special Java case: If a variable is not defined along all paths of entry to a node, a Phi node is not needed.

prependTrivialPhiNode

public void prependTrivialPhiNode(Local local,
                                  Block frontierBlock)

Inserts a trivial Phi node with the appropriate number of arguments.

needsPhiNode

protected boolean needsPhiNode(Local local,
                               Block block)

Function that allows us to weed out special cases where we do not require Phi nodes.

Temporary implementation, with much room for improvement.

trimExceptionalPhiNodes

public void trimExceptionalPhiNodes()

Exceptional Phi nodes have a huge number of arguments and control flow predecessors by default. Since it is useless trying to keep the number of arguments and control flow predecessors in synch, we might as well trim out all redundant arguments and eliminate a huge number of copy statements when we get out of SSA form in the process.

trimPhiNode

public void trimPhiNode(PhiExpr phiExpr)

See Also:

trimExceptionalPhiNodes()

dominates

public boolean dominates(Unit champ,
                         Unit challenger)

Returns true if champ dominates challenger. Note that false doesn't necessarily mean that challenger dominates champ.

doEliminatePhiNodes

public boolean doEliminatePhiNodes()

Eliminate Phi nodes in block by naively replacing them with shimple assignment statements in the control flow predecessors. Returns true if new locals were added to the body during the process, false otherwise.

getUnitToBlockMap

public Map<Unit,Block> getUnitToBlockMap(BlockGraph blocks)

Convenience function that maps units to blocks. Should probably be in BlockGraph.