Java Reference
In-Depth Information
root
X
a
b
Y
(a)
(b)
Figure 14.70: (a) Control flow graph; (b) Data flow lattice.
62. Another approach to constantpropagation is to compute reachingdefi-
nitions (Exercise 37) for each variable. The potentially constant value of
a given use of a variable
v
is determined by computing the
meet
of the
reaching definitions' solutions for constantpropagation.
(a) Consider the control flow graph shown in Figure 14.69. Compute
reaching definitions for the flow graph and then analyze where
meets are required for constantpropagation.
(b) Now compute SSA form for Figure 14.69 and recompute a solution
for constantpropagationusing reachingdefinitions.
(c) How many meets are computed in each approach? What property
of SSA form makes problems like constant propagation easier to
solve?
63. Many optimizations and transformations have been proposed in litera-
ture that rely on SSA form. Some examples include the following:
•
The constantpropagationproblemwith consideration for branches
that cannot be taken [WZ91].
•
A valuenumbering algorithm [AWZ88].
Using a digital library [ACM], investigate these and other algorithms
that compute or use SSA form.
64. SSA formhas been implemented in the
GNUCompiler Collection
(GCC)
suite. Investigate the implementation and compare the algorithms that
construct and use SSA form to the classic algorithms given in this topic.
