[Soot-list] Ask for methods in soot

[Peng Jishan]

Dear sir or madam,

I am a new learner of soot, now I am using soot to develop project. I
want to ask if there are methods to solve the following problems:

Given a node k in a CFG, we should find nodes in the CFG that hold
properties:
k is control dependent(transitively control dependent) or data
dependent(transitively data dependent) on them.
And we also want to find variables nodes that k transitively reference to.


Here we define some concepts as following:

In a control flow graph (CFG), a node u *dominates* a node w if and only
if every path from the entry node to w contains u. A node w
*postdominates* a node u if and only if every path from u to the exit
node contains w.

In a CFG, a node y is *control dependent* on a node x if and only if x
has successors x’and x’’ such that y postdominates x’but y does not
postdominate x’’. In addition, we say that node y is *transitively
control dependent* on node v if there exists a sequence of nodes, v0 =
v, v1, v2,….., vn = y, in the control flow graph such that n ≥ 1 and vj
is control dependent on vj-1 for all j, 1 ≤ j ≤ n.

In a CFG, a node y is *data dependent on *a node x if there exists a
variable v such that x
defines v, y uses v and there is a path from x to y along which v is not
redefined. In addition, we say that node y is *transitively data
dependent* on node v if there exists a sequence of nodes, v0 = v, v1,
v2,….., vn = y, in the control flow graph such that n ≥ 1 and vj is data
dependent on vj-1 for all j, 1 ≤ j ≤ n.

Let v be an input variable received or referenced at a node x in a CFG
(“referenced”applies to the case when the input variable is a global
variable). A node y in the CFG *transitively references* to v if there
is a path from x to y, a sequence of nodes, y0 = x, y1, …, yn = y in the
path and a sequence of variables v0 = v, v1,…, vn, such that n ≥ 1, for
each j,
1 ≤ j ≤ n, yj defines variable vj and references to variable vj-1, and
the sub-path from yj-1 to yj is a definition- clear path with respect to
vj-1.

Thank you very much! Looking forward your kind reply

Best Regards
Peng Jishan


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20110217/24bde785/attachment.html