Java Reference
In-Depth Information
11. Consider the following definition of
control dependence
:
Definition 14.32
•
AnodeZis
control dependent
on a node X (using edge e
=
(
X
,
Y
)
)if
Z postdominates a successor Y of X but Z does not strictly postdomi-
nate X.
•
Let CD
(
X
)
denote the set of nodes that are control dependent on X:
Z
∈
CD
(
X
)
⇐⇒ ∃
Y
|
Z is control dependent on X using edge
(
X
,
Y
)
•
A
control dependence graph
for
G
cf
=
(
N
cf
,
E
cf
)isdefinedas
G
cd
=
(
N
cf
,{
(
X
,
Z
)
|
Z
∈
CD
(
X
)
}
)
Build a control dependence graph for each of the graphs shown in Fig-
ure 14.15.
12. Based on the Definitions 14.15, 14.30, and 14.32, investigate the relation-
ship between dominance frontiers and the control dependence graph.
Show how to construct control dependence graphs using some simple
graph transformations and the algorithm given in Figure 14.29.
13. Prove Theorem 14.2.
14. The table shown in Figure 14.14 uses
dfn
(
X
)
≥
dfn
(
Y
)aspartofthetest
for determining a cross edge. What happens if that test is changed to
dfn
(
X
)
>
dfn
(
Y
)?
15. Devise an algorithm that computes semidominators for the control flow
graphs of
structured programs
.
16. Devise an algorithm that computes the dominator tree for the control
flow graphs of
structured programs
.
17. Nodes are not considered in any particular order by Marker
33
in the
dominators algorithm given in Figure 14.17.
(a) Devise a node ordering that generally provides for the best e
-
ciency.
(b) Compare the e
ciency of your better node ordering with the eval-
uation shown in Figure 14.18.
(c) For reducible flow graphs, how many passes are needed for your
node ordering to converge for the dominance computation?
