Optimization Under the Perspective of Soundness, Completeness, and Reusability - Correct System Design: Recent Insights and Advances - page 293

important dierence between PRE in the intraprocedural and interprocedural
setting. In contrast to the intraprocedural setting, it turns out that in the inter-
procedural one computationally optimal results in general do not exist. For illus-
tration, consider the example of Figure 5. Obviously, the IPRE-transformations
producing the programs of Figure 5(b) and Figure 5(c) are sound, and improve
on the performance of the program of Figure 5(a). However, both transforma-
tions are incomparable with respect to the relation \computationally better,"
and it is easy to check that there is no program, and hence no transformation
either, which uniformly improves on both the programs of Figure 5(b) and (c).

a)

π : a, b, x, y, z π π

π

1 3

2

4

x := a+b

call π 2 call π 4

y := a+b

call π 3

call π 3

a := ...

y := a+b

z := a+b

b)

π

π π

: a, b, x, y, z π

3

1 2 4

:= a+b h := a+b

h

x := h

call π 3

call π 4

call π 2 y := h

call π 3

h := a+b

a := ... y := h

z := h

c)

π π π

π : a, b, x, y, z

2 3

4

1

:= a+b

h

x := h h := a+b

call π 3

call π 3

call π 2

call π 4

y := h

h := a+b

y := h

a := ...

z := h

Fig. 5. Incomparable computationally minimal programs.