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

4(a). It is computationally optimal. At rst sight this suggests that the ISE-
transformation is interprocedurally sound and complete, i.e., admissible and in-
terprocedurally computationally optimal. In the following we will investigate the
validity of this conjecture in more detail. We will start our considerations on
safety and completeness of interprocedural optimization on the analysis level
because the successful extension of the program analyses computing the proper-
ties involved in a transformation is a prerequisite for the successful reuse of an
optimization strategy. Concerning our running example, this means reuse of the
as-early-as-possible placing strategy in the interprocedural setting.

a) π π π π

: a, b, x, y, z

1 2 4

3

call π 3

call π 2 call π call π 3

y := a+b

x := a+b

4

y := a+b

z := a+b

b)

π π π π

: a, b, x, y, z

1 2 3 4

:= a+b := a+b

h h

call π 3

call π 4 call π 2 call π

y := h

x := h

3

y :=

h

Up-safe Points
Down-safe Points
Insertion Points

z := h

Fig. 4. Illustrating the ISE-transformation.

4.1 Analysis Level

Conceptually, the most important dierence between the intraprocedural and
interprocedural setting is due to local variables and parameters of (mutually) re-
cursive procedures. At run-time there can exist an unbounded number of copies
of local variables and parameters belonging to dynamically nested invocations
of recursive procedures which have been called but not yet nished. The proper