Definition - A call graph
is a directed graph, G = (V, E). The finite set of nodes, V,
consists of the procedures that may be called in the program. For any two
procedures f, g in V if there is a potential call to
g
by f then the arc (f, g) appears on the graph. The complete
collection of arcs is denoted by E.
(Back)
Definition - A root node
of a call graph G = (V, E) is a procedure which is not called by
any other procedure.
(Back)
Definition - If
f
in V is a root node of the call graph and procedures g, h
in deG(f),
the descendents of f on G, then procedure g dominates
h
if and only if every path f -> h on G intersects
g.
We say that g directly dominates h if and only if all procedures
that dominate h dominate g. g strongly directly dominates
h
if and only if g directly dominates
h and is the only procedure
that calls h.
(Back)
Definition - The dominance
tree corresponding to a root node f is the graph GD_f
= ({f} + deG(f), ED_f)
formed from the call graph G = (V, E). For any two nodes g,
h
in deG(f),
(g,
h) in ED_f
if g directly dominates h. The node h is shaded if
g
only directly dominates h.
(Back)
Definition - The
moral dominance tree corresponding to a root node f is the graph
GD_f
= ({f} + de(f), ED_f)
formed from the call graph G = (V, E). For any two nodes g,
h
in deG(f),
(g,
h) in ED_f
if g either directly or strongly directly dominates h. If
g
strongly directly dominates h, then the node h is unshaded
and h is shaded if g only directly dominates it. Two shadings
are used to distinguish nodes directly dominated by one of their parents
on G and those directly dominated by a non-parent. If deG(h)
= deGD_f(h)
then the node is a rectangular box with rounded corners. If only chG(h)
= chGD_f(h)
then the node is an ellipse. If neither of these occur, then the node is
a rectangular box.
(Back)
| Last revision:
14/03/02 |
University home | Statistics home | Statistics people | Top of page |