Main Page   Packages   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members  

BuildPDG Class Reference

List of all members.

Public Methods

 BuildPDG (MethodInfo mdInfo, AnnotationManager cfanns)
BitSet controlNodesOf (Stmt st)
Set controlSuccNodesOf (Stmt stmt)
Set dataNodesOf (Stmt st)
Set dataSuccNodesOf (Stmt stmt)
Map getCdMap ()
Map getDdMap ()
Set getInstanceFieldDefStmtList ()
Map getInterferenceMap ()
LockAnalysis getLockAnalysis ()
Map getReadyDependMap ()
int immediatePostdominatorOf (int stmtIndex)
int immediatePostdominatorOf (Stmt stmt)
BitSet postdominatorsOf (Stmt stmt)
BitSet postdominatorsOf (Integer stmtIndex)
BitSet preDivergencePointsOf (Stmt stmt)
void setInterferenceMap (Map iterMap)
void setLockAnalysis (LockAnalysis la)
void setReadyDependMap (Map rm)
BitSet succDivergencePointsOf (Stmt stmt)
String toString ()

Static Public Methods

Set fieldRefToSootField (Set refSet)
Integer indefiniteFrom (AnnotationManager cfanns, MethodInfo mdInfo)
boolean mayPointToTheSameRef (Value v1, Value v2, SootMethod enclosingMethod1, SootMethod enclosingMethod2)
boolean mayPointToTheSameRef (Value v1, Set vs, SootMethod enclosingMethod1, SootMethod enclosingMethod2)

Private Methods

void cdAnalysisForReturnOfInit ()
void cdAnalysisForStmtsInCatch ()
void collectInstanceFieldDefStmt ()
Set collectVarsDefined (Set defStmtList)
Map computeImmedDom (Map stmtToBitSet)
void controlDependAnalysis ()
boolean dataBoxesContains (Set dataBoxes, Stmt stmt)
void dataDependAnalysis ()
void dataDependOfInstanceFieldRef (InstanceFieldRef insfr, Stmt stmt, Set ddList)
void dataDependOfStaticFieldRef (StaticFieldRef staticVariable, Stmt stmt, Set ddList)
void ddForArray (Set ddList, Stmt stmt, Local arrayLocal)
void ddForParameters ()
void ddForStaticAndInstanceFd ()
Set defsNotPreserves (int staticDefIndex)
void dependency ()
void divergenceDependenceAnalysis ()
void domination ()
Stmt getConditionalStmtFrom (Stmt[] testStmts)
Map getDivergenceMap ()
Set getHandlerStmtSet ()
int getInstanceDefIndexOf (Stmt s)
Set getRefsWithCommonField (Set vars, SootField sootField)
Stmt getSpecialInvokeStmtOf (DataBox ddBoxWithNewExpr, SootClass newClass)
Stmt getSpecialInvokeStmtOf (DataBox ddBoxWithNewExpr, String typeOfNewExpr)
int getStaticDefIndexOf (Stmt s)
void immediateDominators ()
LinkedList initializeWorkList (AnnotationManager cfanns)
Set instanceDefsNotPreserves (int instanceDefIndex)
void postDomAnalysis ()
void postdomFixPoint (LinkedList workList)
BitSet postdominatorsOf (int index)
void prepareToBuild (MethodInfo mdInfo)
void reachingDefOfInstanceField ()
void reachingDefOfStaticField ()
List removeExceptionCaught (List actualSuccs)
void specialInvokeDdAnalysis ()

Static Private Methods

Set cloneAndChangeBase (Set original, Value base)

Private Attributes

BitSet exitNodes
MethodInfo methodInfo
Map stmtToPostdoms
Map stmtToImmedPostdom
StmtList stmtList
StmtGraph stmtGraph
JimpleBody jimpleBody
BitSet staticReachDef []
BitSet instanceReachDef []
LockAnalysis lockAnalysis = null
Map readyDependMap = null
Map interferenceMap = null
Map callSiteMap = null
BitSet exitNodesNoThrow
Set instanceFieldDefStmtList = new ArraySet()
Set staticFieldDefStmtList = null
Map stmtToDdOn
Integer indefiniteNode = null
Map stmtToCdOn
Map divergenceMap
AnnotationManager annotationManager = null

Detailed Description

A class calculating data-dependence, control-dependence for one method.
This class includes analysis like reaching definitions for local variables and fields, postdominators, immediate postdominators, and control-dependence.

Definition at line 54 of file BuildPDG.java.

Constructor & Destructor Documentation

BuildPDG::BuildPDG (  MethodInfo   mdInfo,
AnnotationManager   cfanns
)  [inline]
 

Build dependency graph for one method in three steps:

  • Initialization
  • Dominators calculation
  • Dependencies calculation

Parameters:
mdInfo   method to be analysed.
cfanns   annotation manager.

Definition at line 148 of file BuildPDG.java.

Member Function Documentation

void BuildPDG::cdAnalysisForReturnOfInit (    )  [inline, private]
 

Insert the method's description here. Creation date: (00-11-1 16:22:46) This is for control analysis of init method. We assume that return statement of init method control dependent on init invoke of its super class. For example, public void init(int) { int b, size; Buffer JJJCTEMP$0; Object[] JJJCTEMP$1;

JJJCTEMP$0 := @this; b :=

ameter0;
specialinvoke JJJCTEMP$0.[java.lang.Object.init():void](); JJJCTEMP$1 = new Object[b]; JJJCTEMP$0.[Buffer.array:Object[]] = JJJCTEMP$1; JJJCTEMP$0.[Buffer.putPtr:int] = 0; JJJCTEMP$0.[Buffer.getPtr:int] = 0; JJJCTEMP$0.[Buffer.usedSlots:int] = 0; return; } Then, the return is control dependent on specialinvoke JJJCTEMP$0.[java.lang.Object.init():void]();

Definition at line 179 of file BuildPDG.java.

Referenced by controlDependAnalysis().

void BuildPDG::cdAnalysisForStmtsInCatch (    )  [inline, private]
 

Analyse control dependence for statements in catch block.
Store the result in stmtToCdOn.

Given no any information on exception flow, all statements in catch block are considered control dependent on all statements in try block.

Definition at line 218 of file BuildPDG.java.

Referenced by controlDependAnalysis().

Set BuildPDG::cloneAndChangeBase (  Set   original,
Value   base
)  [inline, static, private]
 

Clone and change base value for a set of instance field references.
For example, a.f can be cloned and changed its base value to a new value, saying b. Then a.f will be transformed to a new instance field reference b.f.

Parameters:
original   a set of InstanceFieldRef need changing their base values.
base   new base value for those references in original.
Returns:
a set of new InstanceFieldRef with the new base value base. Empty set is returned, if original is empty.

Definition at line 266 of file BuildPDG.java.

void BuildPDG::collectInstanceFieldDefStmt (    )  [inline, private]
 

Collect all statements such that they assign values to instance field references, including all indirect assignments by method calls.
Store the result in instanceFieldDefStmtList.

Definition at line 280 of file BuildPDG.java.

Referenced by prepareToBuild().

Set BuildPDG::collectVarsDefined (  Set   defStmtList )  [inline, private]
 

Collect all static field references ever defined in the method.

Returns:
a set of StaticFieldRef. Empty set is returned, if there is no static field reference defined.
See also:
staticFieldDefStmtList

Definition at line 363 of file BuildPDG.java.

Referenced by dataDependOfInstanceFieldRef(), and dataDependOfStaticFieldRef().

Map BuildPDG::computeImmedDom (  Map   stmtToBitSet )  [inline, private]
 

Compute immediate (post)dominator for each statement in the method.
The alorithm of this method is from the book "Advanced compiler design and implementation" by Steven S. Muchnick, 1997

Parameters:
stmtToBitSet   a map of Stmt to BitSet of (post)dominators.
Returns:
a map of Stmt to Integer of immediate (post)dominator.
Exceptions:
DomOrPostdomNotUniqueException   if there are more than one immediate (post)dominators.

Definition at line 385 of file BuildPDG.java.

Referenced by immediateDominators().

void BuildPDG::controlDependAnalysis (    )  [inline, private]
 

Analyse control dependence for each statement in the method
Store the result in stmtToCdOn.

The algorithm of this method is from the compiler news group:

From href="http://compilers.iecc.com/comparch/article/92-12-065" target="_top"> comp.compilers</a>.
=== Begin Algorithm ===

1. For a given flow node X, let P(X) denote the nodes that post-dominate X, along with X itself. Compute P(X) by using any of the standard techniques to solve the following backward data flow equations: P(X) = X | (P(Y1) & ... & P(Yn)), P(Stop) = {} where Y1 ... Yn are the successors of X, "|" denotes set union, "&" denotes set intersection, and Stop is a unique exit node for the flow graph. (This part is pretty much straight out of the red dragon book.)

2. Assume that each node in the flow graph has no more than 2 successors, and that if a node does have 2 successors, one is the "true" successor and the other the "false" successor. For a given flow node X, let CD(X) denote the nodes that are control dependent on X. If X has fewer than 2 successors, CD(X) is empty. Otherwise, we can find CD(X) as follows: CD(X) = P(X-true) ^ P(X-false) where X-true and X-false are respectively the true and false successors, and "^" denotes symmetric difference (i.e., A ^ B = (A | B) - (A & B)). Furthermore, the edges that should be labelled "true" in the control dependence graph are the ones from X to the nodes in CD(X) & P(X-true); and "false", the ones to the nodes in CD(X) & P(X-false).

=== End Algorithm ===

From href="http://compilers.iecc.com/comparch/article/92-12-068" target="_top"> comp.compilers</a>.
It looks like the correct solution for a node X with 3 successors, say A, B, and C, would be

CD(X) = (P(A) ^ (P(B) | P(C))) | (P(B) ^ (P(A) | P(C))) | (P(C) ^ (P(A) | P(B)))

From href="http://compilers.iecc.com/comparch/article/92-12-070" target="_top"> comp.compilers</a>.
The general case of more than 2 succesoors is handled like this...
CD(X) = union(P(S)) - intersection(P(S)), for S in successors(X)
(This is a much simpler version of another answer I posted earlier)

From href="http://compilers.iecc.com/comparch/article/92-12-079" target="_top"> comp.compilers</a>.
This can be simplified (also with less computation) further:
CD(X) = union(P(S)) - P(X)
I think it is not difficut to prove that
{intersection(P(S)), for S in successors(X)}=P(X)

Definition at line 477 of file BuildPDG.java.

Referenced by dependency().

BitSet BuildPDG::controlNodesOf (  Stmt   st )  [inline]
 

Get control dependent predecessors, from stmtToCdOn, for the statement st.

Parameters:
st   query statement.
Returns:
a set of statements represented in indexes with BitSet.

Definition at line 529 of file BuildPDG.java.

Referenced by SlicingMethod::slicingMethod(), and SlicingMethod::slicingMethodAgain().

Set BuildPDG::controlSuccNodesOf (  Stmt   stmt )  [inline]
 

Get control dependent successors for the statement stmt.

Parameters:
stmt   query statement.
Returns:
a set of Stmt that are control dependent on stmt. Emtpy set is returned if there is no control dependent successor.

Definition at line 541 of file BuildPDG.java.

boolean BuildPDG::dataBoxesContains (  Set   dataBoxes,
Stmt   stmt
)  [inline, private]
 

See if there is a DataBox in dataBoxes with a statement stmt.

Parameters:
dataBoxes   a set of DataBox.
stmt   query statement.
Returns:
true is returned, if contains. false is returned, if not.

Definition at line 560 of file BuildPDG.java.

Referenced by dataSuccNodesOf().

void BuildPDG::dataDependAnalysis (    )  [inline, private]
 

Analyse data dependence for each statement in the method. Analysis includes data data dependence of instance field references, data dependence of static or static based field references, and data dependence of parameters for method invokes.
Store the result in stmtToDdOn.

See also:
ddForStaticAndInstanceFd() , ddForParameters()

Definition at line 580 of file BuildPDG.java.

Referenced by dependency().

void BuildPDG::dataDependOfInstanceFieldRef (  InstanceFieldRef   insfr,
Stmt   stmt,
Set   ddList
)  [inline, private]
 

Get data dependences for one instance field reference insfr using information on reaching definition of instance field references intanceReachDef and instanceFieldDefStmtList.
Store the result in ddList.

Parameters:
insfr   query field reference.
stmt   the statement where insfr is used.
ddList   a set of DataBox.

Definition at line 632 of file BuildPDG.java.

Referenced by dataDependAnalysis(), ddForParameters(), and ddForStaticAndInstanceFd().

void BuildPDG::dataDependOfStaticFieldRef (  StaticFieldRef   staticVariable,
Stmt   stmt,
Set   ddList
)  [inline, private]
 

Get data dependences for one static field reference staticVariable using information on reaching definition of static field references staticReachDef and staticFieldDefStmtList.
Store the result in ddList.

Parameters:
staticVariable   query field reference.
stmt   the statement where staticVariable is used.
ddList   a set of DataBox.

Definition at line 688 of file BuildPDG.java.

Referenced by ddForStaticAndInstanceFd().

Set BuildPDG::dataNodesOf (  Stmt   st )  [inline]
 

Get data dependent predecessors, from stmtToDdOn for the statement st.

Parameters:
st   query statement.
Returns:
a set of DataBox.

Definition at line 723 of file BuildPDG.java.

Referenced by SlicingMethod::slicingMethod(), and SlicingMethod::slicingMethodAgain().

Set BuildPDG::dataSuccNodesOf (  Stmt   stmt )  [inline]
 

Get data dependent successors for the statement st.

Parameters:
stmt   query statement.
Returns:
a set of Stmt.

Definition at line 734 of file BuildPDG.java.

void BuildPDG::ddForArray (  Set   ddList,
Stmt   stmt,
Local   arrayLocal
)  [inline, private]
 

Insert the method's description here. Creation date: (7/10/2001 1:52:43 PM)

Parameters:
ddList   ca.mcgill.sable.util.Set
stmt   ca.mcgill.sable.soot.jimple.Stmt

Definition at line 752 of file BuildPDG.java.

Referenced by dataDependAnalysis().

void BuildPDG::ddForParameters (    )  [inline, private]
 

Analyse data dependence for parameters (field references) of each call site in the method using REF/MOD information.
Store the result in stmtToDdOn.

Definition at line 798 of file BuildPDG.java.

Referenced by dataDependAnalysis().

void BuildPDG::ddForStaticAndInstanceFd (    )  [inline, private]
 

Analyse data dependence for static field, static based field and intance field references using REF/MOD information.
Store the result in stmtToDdOn.

See also:
dataDependOfStaticFieldRef(StaticFieldRef,Stmt,Set) , dataDependOfInstanceFieldRef(InstanceFieldRef,Stmt,Set)

Definition at line 829 of file BuildPDG.java.

Referenced by dataDependAnalysis().

Set BuildPDG::defsNotPreserves (  int   staticDefIndex )  [inline, private]
 

Get the set of statements that define some mutual static field references with the statement staticDefIndex using staticFieldDefStmtList.

Parameters:
staticDefIndex   the index of a statement in staticFieldDefStmtList which defines a static field reference.
Returns:
a set of Integer which is index of a statement in staticFieldDefStmtList. Empty set is returned, if there is no such statement.

Definition at line 874 of file BuildPDG.java.

Referenced by reachingDefOfStaticField().

void BuildPDG::dependency (    )  [inline, private]
 

Analyse control and data dependence for the method.

See also:
reachingDefOfStaticField() , reachingDefOfInstanceField() , controlDependAnalysis() , dataDependAnalysis() , specialInvokeDdAnalysis()

Definition at line 917 of file BuildPDG.java.

Referenced by BuildPDG().

void BuildPDG::divergenceDependenceAnalysis (    )  [inline, private]
 

Insert the method's description here. Creation date: (4/20/2001 10:21:10 AM)

Definition at line 934 of file BuildPDG.java.

Referenced by dependency().

void BuildPDG::domination (    )  [inline, private]
 

Calculate postdominators and immediate postdominators.

See also:
postDomAnalysis() , immediateDominators()

Definition at line 979 of file BuildPDG.java.

Referenced by BuildPDG().

Set BuildPDG::fieldRefToSootField (  Set   refSet )  [inline, static]
 

Insert the method's description here. Creation date: (6/15/2001 11:02:44 PM)

Returns:
ca.mcgill.sable.util.Set
Parameters:
refSet   ca.mcgill.sable.util.Set

Definition at line 991 of file BuildPDG.java.

Referenced by dataDependOfInstanceFieldRef().

Map BuildPDG::getCdMap (    )  [inline]
 

Get the map of control dependency.

Returns:
stmtToCdOn.

Definition at line 1004 of file BuildPDG.java.

Stmt BuildPDG::getConditionalStmtFrom (  Stmt   testStmts[] )  [inline, private]
 

Insert the method's description here. Creation date: (4/20/2001 11:25:56 AM)

Returns:
ca.mcgill.sable.soot.jimple.Stmt
Parameters:
testStmts   ca.mcgill.sable.soot.jimple.Stmt[]

Definition at line 1014 of file BuildPDG.java.

Referenced by divergenceDependenceAnalysis().

Map BuildPDG::getDdMap (    )  [inline]
 

Get the map of data dependency.

Returns:
stmtToDdOn.

Definition at line 1026 of file BuildPDG.java.

Map BuildPDG::getDivergenceMap (    )  [inline, private]
 

Insert the method's description here. Creation date: (4/20/2001 10:27:38 AM)

Returns:
ca.mcgill.sable.util.Map

Definition at line 1035 of file BuildPDG.java.

Set BuildPDG::getHandlerStmtSet (    )  [inline, private]
 

Get all statements in handlers in the method.

Returns:
a set of Stmt. Empty set is returned, if there is no such statement.

Definition at line 1044 of file BuildPDG.java.

Referenced by removeExceptionCaught().

int BuildPDG::getInstanceDefIndexOf (  Stmt   s )  [inline, private]
 

Get the index of statement s from instanceFieldDefStmtList.

Returns:
index of s. -1 is returned, if s is not in instanceFieldDefStmtList.

Definition at line 1060 of file BuildPDG.java.

Referenced by reachingDefOfInstanceField().

Set BuildPDG::getInstanceFieldDefStmtList (    )  [inline]
 

Get instanceFieldDefStmtList.

Returns:
instanceFieldDefStmtList.

Definition at line 1082 of file BuildPDG.java.

Map BuildPDG::getInterferenceMap (    )  [inline]
 

Get interferenceMap.

Returns:
interferenceMap.

Definition at line 1091 of file BuildPDG.java.

Referenced by SlicingMethod::slicingMethod(), and SlicingMethod::slicingMethodAgain().

LockAnalysis BuildPDG::getLockAnalysis (    )  [inline]
 

Get lockAnalysis.

Returns:
lockAnalysis.

Definition at line 1100 of file BuildPDG.java.

Referenced by InterClassAnalysis::lookupReadyDependStmt(), InterClassAnalysis::readyDependence(), SlicingMethod::slicingMethod(), and SlicingMethod::slicingMethodAgain().

Map BuildPDG::getReadyDependMap (    )  [inline]
 

Get readyDependMap.

Returns:
readyDependMap.

Definition at line 1109 of file BuildPDG.java.

Referenced by SlicingMethod::slicingMethod(), and SlicingMethod::slicingMethodAgain().

Set BuildPDG::getRefsWithCommonField (  Set   vars,
SootField   sootField
)  [inline, private]
 

Insert the method's description here. Creation date: (7/11/2001 3:18:54 PM)

Returns:
ca.mcgill.sable.util.Set
Parameters:
vars   ca.mcgill.sable.util.Set
sootField   ca.mcgill.sable.soot.SootField

Definition at line 1120 of file BuildPDG.java.

Referenced by dataDependOfInstanceFieldRef().

Stmt BuildPDG::getSpecialInvokeStmtOf (  DataBox   ddBoxWithNewExpr,
String   typeOfNewExpr
)  [inline, private]
 

Find out the special invoke &lt init &gt statement corresponding to the new expression. For example, there is a fragment of Jimple code like

[1] p = new Power;
[2] specialinvoke p.[Power. &lt init &gt ():void]();
[3] i = virtualinvoke p.[Power.power(int,int):int](5, 3);

Suppose slice it from statement [3]. Then apparently [3] is data dependent on [1] by p. Statement [2] will not be in the slice, since there is no explicit definition in [2]. In fact, [2] is an initialization for p. So it can be and should be considered as a definition of p. In other words, [1] and [2] together should be the definition of p other than only [1]. So statement [3] is data dependent on both [1] and [2].
However, the traditional data dependence analysis dose not cover this condition, since [2] is not a definition statement.

Given a statement with new expression, e.g., [1], this method will search out the corresponding special &lt init &gt invoke for it, e.g., [2]. This method is called by specialInvokeDdAnalysis().

Parameters:
ddBoxWithNewExpr   DataBox which includes a statement with new expression.
typeOfNewExpr   type of the new expression.
Returns:
the corresponding special init invoke.
Exceptions:
NoInitStmtException   if can not find the special init invoke for ddBoxWithNewExpr.

Definition at line 1223 of file BuildPDG.java.

Stmt BuildPDG::getSpecialInvokeStmtOf (  DataBox   ddBoxWithNewExpr,
SootClass   newClass
)  [inline, private]
 

Find out the special invoke &lt init &gt statement corresponding to the new expression. For example, there is a fragment of Jimple code like

[1] p = new Power;
[2] specialinvoke p.[Power. &lt init &gt ():void]();
[3] i = virtualinvoke p.[Power.power(int,int):int](5, 3);

Suppose slice it from statement [3]. Then apparently [3] is data dependent on [1] by p. Statement [2] will not be in the slice, since there is no explicit definition in [2]. In fact, [2] is an initialization for p. So it can be and should be considered as a definition of p. In other words, [1] and [2] together should be the definition of p other than only [1]. So statement [3] is data dependent on both [1] and [2].
However, the traditional data dependence analysis dose not cover this condition, since [2] is not a definition statement.

Given a statement with new expression, e.g., [1], this method will search out the corresponding special &lt init &gt invoke for it, e.g., [2]. This method is called by specialInvokeDdAnalysis().

Parameters:
ddBoxWithNewExpr   DataBox which includes a statement with new expression.
typeOfNewExpr   type of the new expression.
Returns:
the corresponding special init invoke.
Exceptions:
NoInitStmtException   if can not find the special init invoke for ddBoxWithNewExpr.

Definition at line 1164 of file BuildPDG.java.

Referenced by specialInvokeDdAnalysis().

int BuildPDG::getStaticDefIndexOf (  Stmt   s )  [inline, private]
 

Get the index of statement s from staticFieldDefStmtList

Returns:
index of s. -1 is returned, if s is not in staticFieldDefStmtList.

Definition at line 1257 of file BuildPDG.java.

Referenced by reachingDefOfStaticField().

void BuildPDG::immediateDominators (    )  [inline, private]
 

Compute immediate (post)dominators for stmtToPostdoms.
This method is only called by domination().
The result is stored in stmtToImmedPostdom.

Definition at line 1279 of file BuildPDG.java.

Referenced by domination().

int BuildPDG::immediatePostdominatorOf (  Stmt   stmt )  [inline]
 

Get immediate postdominator for a statement stmt, using stmtToImmedPostdom.

Parameters:
stmt   query statement.
Returns:
index of the postdominator for stmt.

Definition at line 1303 of file BuildPDG.java.

int BuildPDG::immediatePostdominatorOf (  int   stmtIndex )  [inline]
 

Get immediate postdominator for a statement represented by an index stmtIndex, using stmtToImmedPostdom.

Parameters:
stmtIndex   index of a statement.
Returns:
index of the postdominator for stmtIndex.

Definition at line 1291 of file BuildPDG.java.

Referenced by PostProcess::getNewJumpTarget().

Integer BuildPDG::indefiniteFrom (  AnnotationManager   cfanns,
MethodInfo   mdInfo
)  [inline, static]
 

Get a back point for the method if there is an indefinite loop in the method.
The back point is, for example,

[1] label-a: stmt1;
[2] ..... ;
..... ;
[n] goto label-a;

statement [n], assumming that statement [1] to [n] is an indefinite loop.

Parameters:
cfanns   annotation manager.
mdInfo   method information.
Returns:
the index of back point of an indefinite loop, if any. IndexMaps.specialExitNode is returned, if there is no such back point.

Definition at line 1325 of file BuildPDG.java.

Referenced by initializeWorkList().

LinkedList BuildPDG::initializeWorkList (  AnnotationManager   cfanns )  [inline, private]
 

Initialize workList and stmtToPostdoms for postdomination analysis which is done by postDomAnalysis().
This initialization is required by the algorithm in Muchnick book "Advanced compiler design and implementation" by Steven S. Muchnick, 1997.

Parameters:
cfanns   annotation manager.
Returns:
a linked list of Integer which is the index of statement in stmtList.
Exceptions:
NoExitNodeException   if can not find out an exit node for the method.

Definition at line 1357 of file BuildPDG.java.

Referenced by postDomAnalysis().

Set BuildPDG::instanceDefsNotPreserves (  int   instanceDefIndex )  [inline, private]
 

Get the set of statements that define some mutual instance field references with the statement instanceDefIndex using staticFieldDefStmtList.

Parameters:
instanceDefIndex   the index of a statement in instanceFieldDefStmtList which defines an instance field reference.
Returns:
a set of Integer which is index of a statement in instanceFieldDefStmtList. Empty set is returned, if there is no such statement.

Definition at line 1399 of file BuildPDG.java.

Referenced by reachingDefOfInstanceField().

boolean BuildPDG::mayPointToTheSameRef (  Value   v1,
Set   vs,
SootMethod   enclosingMethod1,
SootMethod   enclosingMethod2
)  [inline, static]
 

Insert the method's description here. Creation date: (7/10/2001 3:13:31 PM)

Returns:
boolean
Parameters:
v1   ca.mcgill.sable.soot.jimple.Value
v2   ca.mcgill.sable.soot.jimple.Value
enclosingMethod   ca.mcgill.sable.soot.SootMethod

Definition at line 1440 of file BuildPDG.java.

boolean BuildPDG::mayPointToTheSameRef (  Value   v1,
Value   v2,
SootMethod   enclosingMethod1,
SootMethod   enclosingMethod2
)  [inline, static]
 

Insert the method's description here. Creation date: (7/10/2001 3:13:31 PM)

Returns:
boolean
Parameters:
v1   ca.mcgill.sable.soot.jimple.Value
v2   ca.mcgill.sable.soot.jimple.Value
enclosingMethod   ca.mcgill.sable.soot.SootMethod

Definition at line 1422 of file BuildPDG.java.

Referenced by ddForArray().

void BuildPDG::postDomAnalysis (    )  [inline, private]
 

Analyse postdomination for the method.

See also:
initializeWorkList(AnnotationManager) , postdomFixPoint(LinkedList)

Definition at line 1454 of file BuildPDG.java.

Referenced by domination().

void BuildPDG::postdomFixPoint (  LinkedList   workList )  [inline, private]
 

Calculate postdominators for each statement in the method starting from ininialized workList.
The result is stored in stmtToPostdoms.

The alorithm is from the book "Advanced compiler design and implementation" by Steven S. Muchnick, 1997.

Definition at line 1468 of file BuildPDG.java.

Referenced by postDomAnalysis().

BitSet BuildPDG::postdominatorsOf (  Integer   stmtIndex )  [inline]
 

Get postdominators of a statement represented by the Integer index in stmtList using stmtToPostdoms.

Parameters:
stmtIndex   Integer index of the query statement.
Returns:
a set of postdominators of stmtIndex represented by BitSet.

Definition at line 1582 of file BuildPDG.java.

BitSet BuildPDG::postdominatorsOf (  Stmt   stmt )  [inline]
 

Get postdominators of a statement using stmtToPostdoms.

Parameters:
stmt   query statement.
Returns:
a set of postdominators of stmt represented by BitSet.

Definition at line 1571 of file BuildPDG.java.

BitSet BuildPDG::postdominatorsOf (  int   index )  [inline, private]
 

Get postdominators of a statement represented by the int index in stmtList using stmtToPostdoms.

Parameters:
index   int index of the query statement.
Returns:
a set of postdominators of index represented by BitSet.

Definition at line 1560 of file BuildPDG.java.

Referenced by controlDependAnalysis().

BitSet BuildPDG::preDivergencePointsOf (  Stmt   stmt )  [inline]
 

Insert the method's description here. Creation date: (4/20/2001 11:33:42 AM)

Returns:
java.util.BitSet
Parameters:
stmt   ca.mcgill.sable.soot.jimple.Stmt

Definition at line 1593 of file BuildPDG.java.

Referenced by SlicingMethod::slicingMethod(), and SlicingMethod::slicingMethodAgain().

void BuildPDG::prepareToBuild (  MethodInfo   mdInfo )  [inline, private]
 

Prepare to analyse data and control dependence.

Parameters:
mdInfo   method information.

Definition at line 1611 of file BuildPDG.java.

Referenced by BuildPDG().

void BuildPDG::reachingDefOfInstanceField (    )  [inline, private]
 

Implement reaching definition for instance field references.
There is no reaching definition analysis for field references in Jimple. It only provides the reaching analysis for simple local variables.
This method is a modified implementation of Bit Vector algorithm in the book "Advanced compiler design and implementation" by Steven S. Muchnick, 1997. Page 218.
The result is store in instanceReachDef.

Definition at line 1638 of file BuildPDG.java.

Referenced by dependency().

void BuildPDG::reachingDefOfStaticField (    )  [inline, private]
 

Implement reaching definition for static field references.
There is no reaching definition analysis for field references in Jimple. It only provides the reaching analysis for simple local variables.
This method is a modified implementation of Bit Vector algorithm in the book "Advanced compiler design and implementation" by Steven S. Muchnick, 1997. Page 218.
The result is store in staticReachDef.

Definition at line 1741 of file BuildPDG.java.

Referenced by dependency().

List BuildPDG::removeExceptionCaught (  List   actualSuccs )  [inline, private]
 

Remove, from actualSuccs, statements which are in exception handlers.

Parameters:
actualSuccs   a list of Stmt.
Returns:
a listStmt without statements in any handler.
See also:
getHandlerStmtSet()

Definition at line 1830 of file BuildPDG.java.

Referenced by controlDependAnalysis(), and postdomFixPoint().

void BuildPDG::setInterferenceMap (  Map   iterMap )  [inline]
 

Set interferenceMap.

Parameters:
iterMap   interference map.

Definition at line 1845 of file BuildPDG.java.

Referenced by InterClassAnalysis::interferenceDependence().

void BuildPDG::setLockAnalysis (  LockAnalysis   la )  [inline]
 

Set lockAnalysis.

Parameters:
la   an instance of LockAnalysis.

Definition at line 1854 of file BuildPDG.java.

Referenced by LockAnalysis::LockAnalysis().

void BuildPDG::setReadyDependMap (  Map   rm )  [inline]
 

Set readyDependMap.

Parameters:
rm   ready dependent map.

Definition at line 1863 of file BuildPDG.java.

Referenced by InterClassAnalysis::readyDependence().

void BuildPDG::specialInvokeDdAnalysis (    )  [inline, private]
 

Analyse data dependence for special invoke expressions.
For example, there is a fragment of Jimple code like

[1] p = new Power;
[2] specialinvoke p.[Power. &lt init &gt ():void]();
[3] i = virtualinvoke p.[Power.power(int,int):int](5, 3);

Suppose slice it from statement [3]. Then apparently [3] is data dependent on [1] by p. Statement [2] will not be in the slice, since there is no explicit definition in [2]. In fact, [2] is an initialization for p. So it can be and should be considered as a definition of p. In other words, [1] and [2] together should be the definition of p other than only [1]. So statement [3] is data dependent on both [1] and [2].
However, the traditional data dependence analysis dose not cover this condition, since [2] is not a definition statement.

Given a statement with new expression, e.g., [1], this method will search out the corresponding special &lt init &gt invoke for it, e.g., [2].

Definition at line 1891 of file BuildPDG.java.

Referenced by dependency().

BitSet BuildPDG::succDivergencePointsOf (  Stmt   stmt )  [inline]
 

Insert the method's description here. Creation date: (4/20/2001 11:33:42 AM)

Returns:
java.util.BitSet
Parameters:
stmt   ca.mcgill.sable.soot.jimple.Stmt

Definition at line 1941 of file BuildPDG.java.

Member Data Documentation

Map BuildPDG::callSiteMap = null [private]
 

a map from CallSite to SootMethod where SootMethod is called in the CallSite.

Definition at line 104 of file BuildPDG.java.

Map BuildPDG::divergenceMap [private]
 

The map of divergence dependence from pre-divergence point to reachable statement set (from that point): (

Definition at line 135 of file BuildPDG.java.

BitSet BuildPDG::exitNodes [private]
 

a list of exit nodes (index) in the method which are stored as BitSet.

Definition at line 58 of file BuildPDG.java.

BitSet BuildPDG::exitNodesNoThrow [private]
 

exit nodes without throw statements.

Definition at line 108 of file BuildPDG.java.

Set BuildPDG::instanceFieldDefStmtList = new ArraySet() [private]
 

a set of DataBox.

Definition at line 112 of file BuildPDG.java.

BitSet BuildPDG::instanceReachDef[] [private]
 

the result of reaching definition analysis for instance field references.

Definition at line 83 of file BuildPDG.java.

Map BuildPDG::interferenceMap = null [private]
 

a map from Stmt to a List of InterferStmt for interference dependence of each statement in the method.

Definition at line 99 of file BuildPDG.java.

LockAnalysis BuildPDG::lockAnalysis = null [private]
 

an instance of LockAnalysis.

Definition at line 87 of file BuildPDG.java.

Map BuildPDG::readyDependMap = null [private]
 

a map from Stmt to a List of ReadyDependStmt for ready dependence of each statement in the method.

Definition at line 93 of file BuildPDG.java.

Set BuildPDG::staticFieldDefStmtList = null [private]
 

a set of DataBox.

Definition at line 116 of file BuildPDG.java.

BitSet BuildPDG::staticReachDef[] [private]
 

the result of reaching definition analysis for static field references.

Definition at line 79 of file BuildPDG.java.

StmtList BuildPDG::stmtList [private]
 

statement list of the method.

Definition at line 73 of file BuildPDG.java.

Map BuildPDG::stmtToCdOn [private]
 

The map of control dependence: Stmt to BitSet.

Definition at line 130 of file BuildPDG.java.

Map BuildPDG::stmtToDdOn [private]
 

The map of data dependence: Stmt to a Set of DataBox.

Definition at line 122 of file BuildPDG.java.

Map BuildPDG::stmtToImmedPostdom [private]
 

a map from Stmt to Integer for immediate postdominator of each statement in the method.

Definition at line 69 of file BuildPDG.java.

Map BuildPDG::stmtToPostdoms [private]
 

a map from Stmt to BitSet for postdominators of each statement in the method.

Definition at line 64 of file BuildPDG.java.

The documentation for this class was generated from the following file:
Generated at Thu Feb 7 07:05:45 2002 for Bandera by doxygen1.2.10 written by Dimitri van Heesch, © 1997-2001