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

its entry to its exit at most as many computations as the program produced by
T 0 on the corresponding path. A sound PRE-transformation is computation-

ally optimal , if and only if it is computationally better than any other sound
PRE-transformation. In this article we dene completeness of PRE in the sense
of computational optimality, i.e., a sound PRE-transformation is called complete ,
if and only if it is computationally optimal. 5

T

The SE-Transformation. As recalled in Section 1, the SE-transformation in-
serts computations at their earliest safe computation points. Intuitively, this as-
early-as-possible placing strategy maximizes the potential for redundancy elimi-
nation in a program. Formally, it is dened by specifying the set of edges where
computations have to be inserted and replaced. Note that h is a fresh variable
introduced for the computation pattern t under consideration.

{ Insertions : Insert on every edge ending in an earliest safe node an assignment
of the form h := . If such an edge is already labeled by a statement, the new

one is inserted behind the already present one. 6
{ Replacements : Replace every original computation of

t

t by h .

We have (cf. [20,21]):

Theorem 1 (Soundness and Completeness).
The SE-transformation is sound and complete, i.e., it is admissible and compu-
tationally optimal.

Obviously, an implementation of the SE-transformation requires to compute
its insertion points, which, in turn, requires to compute the set of program points
n ). The key to the algorithmic solution of this

problem lies in the decomposition of safety into the properties of up-safety and
down-safety , which are dual to each other. 7 A program point

being safe, in symbols Safe ( n

n is up-safe for a

computation t ,insymbols Up-Safe ( n ), if on every path from the program's entry

to n , t is computed without a subsequent modication of any of its operands.

Dually, n is down-safe for t ,insymbols Dn-Safe ( n ), if t is computed on every

path originating in n and reaching the program's exit before any of its operands

is modied.
The notions of down-safety and up-safety lead to an equivalent characteriza-
tion of the insertion points of the SE-transformation: a program point is earliest
safe if and only if it is down-safe but not up-safe and it is either the start node

5 Advanced PRE-techniques like lazy code motion or sparse code motion take addi-
tional quality criteria into account like the lifetimes of temporaries introduced by
PRE (cf. [20,21]), the lifetimes of all program variables (cf. [41,42]), or the code
size (cf. [43]). For the purposes of this article it suces to consider the number of
computations performed, whose minimization is in fact the primary goal of PRE.
6 We assume that the start node s is reached by a \virtual" edge, where in case of
need the required insertions are made.
7 Up-safety and down-safety are also known as availability and very busyness

or an-

ticipability , respectively (cf. [8,35]).