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

Optimization Under the Perspective of
Soundness, Completeness, and Reusability

Jens Knoop and Oliver Ruthing

Universitat Dortmund, Baroper Str. 301, D-44221 Dortmund, Germany
f knoop,ruething g @ls5.cs.uni-dortmund.de
http://sunshine.cs.uni-dortmund.de/

Abstract. While soundness and completeness are unchallengedly the
surveyor's rod for evaluating the worthiness of proof calculi in program
verication, it is not common to refer to these terms for rating the worthi-
ness of performance improving transformations in program optimization.
In this article we reconsider optimization under the perspective of sound-
ness, completeness, and, additionally, reusability. Soundness can here be
interpreted as semantics preservation, completeness as optimality in a
specic, well-dened sense, and reusability as paradigm-transcending ro-
bustness of the rationale guaranteeing soundness and completeness of an
optimization for a specic setting. Using partial redundancy elimination
( PRE ) for illustration, we demonstrate that these rationales are usually
quite sensitive to paradigm changes. Neither completeness nor sound-
ness are generally preserved. Hence, the reuse of optimization strategies
in new paradigms requires usually paradigm-specic adaptations in order
to accommodate their specics. We exemplify this for PRE, and demon-
strate that it is generally worth the eort, and an eective means for
mastering the complexity of compiler construction in the specic eld of
code optimization.
Keywords:

Programming paradigms (imperative, explicitly parallel,
object-oriented), program optimization, data-flow analysis, safety and
coincidence theorems, optimizer generators, code motion, soundness, com-
pleteness, reusability, admissibility, optimality.

1 Motivation

Partial redundancy elimination ( PRE ) (cf. [32]), often also referred to as code
motion ( CM ), is a powerful classical optimization which is widely used in prac-
tice. 1 Intuitively, it improves the performance of a program by avoiding un-
1 An early example is the PL.8 compiler [1]. It performs code motion based on an
extension of Morel and Renvoise's pioneering algorithm of [32] for partial redun-
dancy elimination. A current example is the Sun SPARCompiler language systems
(SPARCompiler is a registered trademark of SPARC International, Inc., licensed
exclusively to Sun Microsystems, Inc.). It performs partial redundancy elimination
based on the algorithm for lazy code motion of [20,21]. A variant of this algorithm
has been developed at Siemens-Nixdorf [7]. Throughout this article we consider its
basic version for busy code motion as running example.