Re: partial redundancy elimination

bill@ssd.csd.harris.com (Bill Leonard) writes


> "Lazy Code Motion" by Knoop, R\"uthing and Steffen in
> SIGPLAN PLDI '92.


> Be sure you also get a copy of the article "Some Comments on "A Solution
> to a Problem with Morel and Renvoise's 'Global Optimization by Suppression
> of Partial Redundancies'", by Arthur Sorkin, ACM TOPLAS, Vol. 11, No. 4,
> Oct. '89.


> ... We use partial redundancies in our
> compilers, modified according to that article. We used to use the
> unmodified form and found that it moved computations too far back in the
> code, thus extending the lifetime of temporaries. With the modified form,
> that problem is significantly lessened ...


Note that the lifetime anomaly, which according to Bill Leonard's
experience is significantly lessened using Sorkin's heuristics is
completely avoided by the algorithm for lazy code motion cited above. In
fact, this algorithm results in "computationally" and "lifetime" optimal
programs, i.e. the lifetimes of temporaries introduced by the
transformation are provably as short as possible, while every partial
redundancy that can be eliminated, it is eliminated.


An extended and revised version of the PLDI'92 paper is going to appear in
TOPLAS. Its title is "Optimal code motion: Theory and practice" by Oliver
R\"uthing, Bernhard Steffen and myself. The variant of the algorithm for
lazy code motion presented there directly works on flow graphs composed of
basic blocks rather than single statements. This supports its integration
in existing compiler environments. Moreover, the 4 purely uni-directional
analyses lazy code motion consists of (In fact, no bidirectional analysis
as in Sorkin's algorithm!) are reorganized such that the first and the
last two analyses can be computed in parallel.


You can get PostScript-versions of these papers via anonymous ftp. The
details are given below. In particular, in lsr-jpl-xx.ps.Z an extension of
lazy code motion to strength reduction is presented:


        ftp-address: ftp.uni-passau.de
        guest-login: anonymous
        password: email-address


        directory: /pub/local/parallel/papers
        files: ocm-9310-xx.ps.Z (Optimal code motion: Theory and practice)
                                  lcm-9208-xx.ps.Z (Lazy code motion)
                                  lsr-jpl-xx.ps.Z (Lazy strength reduction)


                                  with "xx" \in {a4,us} depending
                                  on the prefered paper format.
-----
Jens Knoop E-Mail: knoop@fmi.uni-passau.de
Department of Computer Science Phone: ++49-851-509-716
University of Passau Fax: ++49-851-509-346
Innstrasse 33
D-94032 Passau
Federal Republic of Germany
--

Return to the comp.compilers page.
Search the comp.compilers archives again.