Package soot.jimple.toolkits.scalar.pre

Class EarliestnessComputation

java.lang.Object

soot.jimple.toolkits.scalar.pre.EarliestnessComputation

public class EarliestnessComputation
extends Object

Computes the earliest points for the given expressions.
This basically finds the highest point in the flow-graph where we can put each computation, without introducing new computations on any path.
More technically: A computation is earliest, if at the current point the computation is down-safe, and if either:

• any of the predecessors is not transparent, or
• if any predecessors is not "safe" (ie. the insertion of this computation would insert it on a path, where it was not before).

Intuitively: If the one predecessor is not transparent, we can't push the computation further up. If one of the predecessor is not safe, we would introduce a new computation on its path. Hence we can't push further up.

Note that this computation is linear in the number of units, as we don't need to find any fixed-point.

See Also:

UpSafetyAnalysis, DownSafetyAnalysis

Constructor Summary

Constructors

Constructor	Description
EarliestnessComputation(UnitGraph unitGraph, UpSafetyAnalysis upSafe, DownSafetyAnalysis downSafe, SideEffectTester sideEffect)	given an UpSafetyAnalysis and a DownSafetyAnalysis, performs the earliest-computation.
EarliestnessComputation(UnitGraph unitGraph, UpSafetyAnalysis upSafe, DownSafetyAnalysis downSafe, SideEffectTester sideEffect, FlowSet<EquivalentValue> set)	given an UpSafetyAnalysis and a DownSafetyAnalysis, performs the earliest-computation. allows to share sets over multiple analyses (set-operations are usually more efficient, if the sets come from the same source).

Method Summary

Modifier and Type	Method	Description
FlowSet<EquivalentValue>	getFlowBefore(Object node)	returns the FlowSet of expressions, that have their earliest computation just before node.

Methods inherited from class java.lang.Object

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

Constructor Detail

EarliestnessComputation

public EarliestnessComputation(UnitGraph unitGraph,
                               UpSafetyAnalysis upSafe,
                               DownSafetyAnalysis downSafe,
                               SideEffectTester sideEffect)

given an UpSafetyAnalysis and a DownSafetyAnalysis, performs the earliest-computation.

Parameters:

unitGraph - the Unitgraph we'll work on.

upSafe - a UpSafetyAnalysis of unitGraph

downSafe - a DownSafetyAnalysis of unitGraph

sideEffect - the SideEffectTester that will tell if a node is transparent or not.

EarliestnessComputation

public EarliestnessComputation(UnitGraph unitGraph,
                               UpSafetyAnalysis upSafe,
                               DownSafetyAnalysis downSafe,
                               SideEffectTester sideEffect,
                               FlowSet<EquivalentValue> set)

given an UpSafetyAnalysis and a DownSafetyAnalysis, performs the earliest-computation.
allows to share sets over multiple analyses (set-operations are usually more efficient, if the sets come from the same source).

Parameters:

unitGraph - the Unitgraph we'll work on.

upSafe - a UpSafetyAnalysis of unitGraph

downSafe - a DownSafetyAnalysis of unitGraph

sideEffect - the SideEffectTester that will tell if a node is transparent or not.

set - the shared set.

Method Detail

getFlowBefore

public FlowSet<EquivalentValue> getFlowBefore(Object node)

returns the FlowSet of expressions, that have their earliest computation just before node.

Parameters:

node - a Object of the flow-graph (in our case always a Unit).

Returns:

a FlowSet containing the expressions.