soot.shimple.internal
Class ShimpleBodyBuilder

java.lang.Object
  soot.shimple.internal.ShimpleBodyBuilder

public class ShimpleBodyBuilder
extends Object

This class does the real high-level work. It takes a Jimple body or Jimple/Shimple hybrid body and produces pure Shimple.

The work is done in two main steps:

1. Trivial Phi nodes are added.
2. A renaming algorithm is executed.

This class can also translate out of Shimple by producing an equivalent Jimple body with all Phi nodes removed.

Note that this is an internal class, understanding it should not be necessary from a user point-of-view and relying on it directly is not recommended.

Author:

Navindra Umanee

See Also:

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

Field Summary

protected int[]	assignmentCounters
protected ShimpleBody	body
protected BlockGraph	cfg
protected DominatorTree	dt
protected Stack[]	namingStacks
protected Map<String,Local>	newLocals Maps new name Strings to Locals.
protected Map<Local,Local>	newLocalsToOldLocal Maps renamed Locals to original Locals.
protected List<Local>	origLocals A fixed list of all original Locals.
PhiNodeManager	phi
PiNodeManager	pi
protected ShimpleFactory	sf

Constructor Summary

ShimpleBodyBuilder(ShimpleBody body)
Transforms the provided body to pure SSA form.

Method Summary

void	eliminatePhiNodes() Remove Phi nodes from current body, high probablity this destroys SSA form.
void	eliminatePiNodes()
protected Local	fetchNewLocal(Local local, Integer subscript) Clever convenience function to fetch or create new Local's given a Local and the desired subscript.
protected int	indexOfLocal(Value local) Convenient function that maps new Locals to the originating Local, and finds the appropriate array index into the naming structures.
String	makeUniqueLocalName(String dupName, Set<String> localNames) Given a set of Strings, return a new name for dupName that is not currently in the set.
void	makeUniqueLocalNames() Make sure the locals in the given body all have unique String names.
void	postElimOpt()
void	preElimOpt()
void	renameLocals() Variable Renaming Algorithm from Cytron et al 91, P26-8, implemented in various bits and pieces by the next functions.
void	renameLocalsSearch(Block block) Driven by renameLocals().
void	transform()
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

cfg

protected BlockGraph cfg

origLocals

protected List<Local> origLocals

A fixed list of all original Locals.

phi

public PhiNodeManager phi

pi

public PiNodeManager pi

newLocals

protected Map<String,Local> newLocals

Maps new name Strings to Locals.

newLocalsToOldLocal

protected Map<Local,Local> newLocalsToOldLocal

Maps renamed Locals to original Locals.

assignmentCounters

protected int[] assignmentCounters

namingStacks

protected Stack[] namingStacks

Constructor Detail

ShimpleBodyBuilder

public ShimpleBodyBuilder(ShimpleBody body)

Transforms the provided body to pure SSA form.

Method Detail

update

public void update()

transform

public void transform()

preElimOpt

public void preElimOpt()

postElimOpt

public void postElimOpt()

eliminatePhiNodes

public void eliminatePhiNodes()

Remove Phi nodes from current body, high probablity this destroys SSA form.

Dead code elimination + register aggregation are performed as recommended by Cytron. The Aggregator looks like it could use some improvements.

See Also:

ShimpleOptions

eliminatePiNodes

public void eliminatePiNodes()

renameLocals

public void renameLocals()

Variable Renaming Algorithm from Cytron et al 91, P26-8, implemented in various bits and pieces by the next functions. Must be called after trivial nodes have been added.

renameLocalsSearch

public void renameLocalsSearch(Block block)

Driven by renameLocals().

fetchNewLocal

protected Local fetchNewLocal(Local local,
                              Integer subscript)

Clever convenience function to fetch or create new Local's given a Local and the desired subscript.

indexOfLocal

protected int indexOfLocal(Value local)

Convenient function that maps new Locals to the originating Local, and finds the appropriate array index into the naming structures.

makeUniqueLocalNames

public void makeUniqueLocalNames()

Make sure the locals in the given body all have unique String names. Renaming is done if necessary.

makeUniqueLocalName

public String makeUniqueLocalName(String dupName,
                                  Set<String> localNames)

Given a set of Strings, return a new name for dupName that is not currently in the set.