Java Reference
In-Depth Information
18. Consider a DFST
T
and the right-to-left preorder traversal given in Fig-
ure 14.11. Prove that nodes are visited in the same order by a
reverse
postorder traversal
. Such a traversal is accomplished by first listing
the nodes in postorder and then visiting the nodes in reverse of their
appearance on that listing.
19. Marker
31
initializes
dom
(
X
) (the dominators of node
X
)tobe
N
f
(all
nodes in the flow graph). Based on the relationship between a node's
dominators and a graph's DFST, what set of nodes is more suitable for
initializing
dom
(
X
)?
20. Prove Lemma 14.12. For intuition, consult the example in Figure 14.23.
21. Prove Lemma 14.13.
22. Prove the correctness of Marker
55
in the algorithm of Figure 14.24.
23. Show how to adapt the algorithm in Figure 14.35 so that irreducible
intervals are resolved in favor of strong connectivity, at the expense of
having multiple entries to irreducible loops.
24. Show how to adapt the algorithm in Figure 14.35 so that irreducible
intervals are resolved in favor of being single-entry, at the expense of
losing strong connectivity of irreducible loops.
25. Recall the transformation experienced by the inner loops as the program
in Figure 14.1 was optimized into the program shown in Figure 14.5.
Apply these same transformations to the outer loops of Figure 14.5.
26.
Dead code elimination
removes computations from a program that do
not a
ect the program's output. Consider a simple programming lan-
guagewith the usual assignment and arithmetic operations. There are no
looping or conditional statements. The language includes the statement
print
var
, which prints the contents of the specified variable.
Every statement of the form print
var
is live, and so are all statements
that contribute to the computation of variables whose values are printed.
Design a data flow framework that determines those computations that
can be removed as dead code.
ff
