Re: partial redundancy (Preston Briggs)
Wed, 2 Feb 1994 00:07:10 GMT

          From comp.compilers

Related articles
partial redundancy (1994-01-28)
Re: partial redundancy (1994-01-31)
Re: partial redundancy (1994-01-31)
Re: partial redundancy (1994-02-02)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Preston Briggs)
Keywords: optimize, bibliography
Organization: Rice University, Houston
References: 94-01-121
Date: Wed, 2 Feb 1994 00:07:10 GMT (Henry McNair) writes:
>partial redundancy elimination. I began reading the notes more closely and
>found it interesting. I'm in the process of getting the original articles:
> "Global Optimization by Suppression of Partial
> Redundancies" by Morel and Renvoise in CACM 2/79, and
> "Lazy Code Motion" by Koop, Ruthing and Steffen in
>What I was wondering about is how effective is this (type of) algorithm
>for global code motion verses something like 'invariant hoisting' in
>loops. Could partial redundancy suppression be considered as a
>generalization of invariant hoisting?
>For compilers writers that have implemented one or both of these
>algorithms, which technique produces better code in terms of loops and
>straight line code - i.e. does the theory match the reality? (With all
>the data flow calculations going on I wonder how many redundant
>expressions are really suppressed with this algorithm verses simpler

There's a pretty extensive literature on the subject; the papers you
mention are the current end points. Others include

    title="A Solution to a Problem with {Morel} and {Renvoise's}
                                  ``{Global} Optimization by Suppression of Partial
    author="Karl-Heinz Drechsler and Manfred P. Stadel",

    title="Some Comments on ``{A} Solution to a Problem with {Morel} and
                                  {Renvoise's} `{Global} Optimization by Suppression of
                                  Partial Redundancies'\,''",
    author="Arthur Sorkin",

    title="Practical Adaptation of the Global Optimization Algorithm of
                                  {Morel} and {Renvoise}",
    author="Dhananjay M. Dhamdhere",

    author="Dhananjay M. Dhamdhere and Harish Patil",
    title="An Elimination Algorithm for Bidirectional Data Flow Problems
                                  Using Edge Placement",

    author="Dhananjay M. Dhamdhere and Uday P. Khedker",
    title="Complexity of Bidirectional Data Flow Analysis",
    address="Charleston, South Carolina",

Dhamdhere has several others in more obscure places.
I'm sure they'll appear in the bibliographies.

Anyway, it does work, though I've never seen experimental comparisons
published. It includes loop-invariant code motion and global common
subexpression elimination. However, it only works on expressions. If you
want to hoist invariant control flow, you need other mechanisms. E.g.
something like,

    title="Code Motion of Control Structures in High-Level Languages",
    author="Ron Cytron and Andy Lowry and F. Kenneth Zadeck",
    address="St.~Petersburg Beach, Florida",

You might also examine

    title="Global Value Numbers and Redundant Computations",
    author="Barry K. Rosen and Mark N. Wegman and F. Kenneth Zadeck",
    address="San Diego, California",

PRE is actually fairly simple to implement; the hard part is deriving all
those data-flow equations (which the authors have kindly done for you).
Oh, and choosing which version to implement!

We have an implementation (of Morel and Renvoise, as modified by Drechsler
and Stadel) that you (or others) can examine. It's available via
anonymous ftp from, in the directory public/preston

Grab the file, and perhaps the file (explains a lot
of the shared library calls we use).

Preston Briggs

Post a followup to this message

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