Re: partial redundancy

hmcnair@pacific.urbana.mcd.mot.com (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
> SIGPLAN PLDI '92.
>
>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
>methods.)


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
                                  Redundancies''",
    author="Karl-Heinz Drechsler and Manfred P. Stadel",
    pages="635--640",
    journal=toplas,
    year=1988,
    month=oct,
    volume=10,
    number=4


    title="Some Comments on ``{A} Solution to a Problem with {Morel} and
                                  {Renvoise's} `{Global} Optimization by Suppression of
                                  Partial Redundancies'\,''",
    author="Arthur Sorkin",
    pages="666--668",
    journal=toplas,
    year=1989,
    month=oct,
    volume=11,
    number=4


    title="Practical Adaptation of the Global Optimization Algorithm of
                                  {Morel} and {Renvoise}",
    author="Dhananjay M. Dhamdhere",
    pages="291--294",
    journal=toplas,
    year=1991,
    month=apr,
    volume=13,
    number=2


    author="Dhananjay M. Dhamdhere and Harish Patil",
    title="An Elimination Algorithm for Bidirectional Data Flow Problems
                                  Using Edge Placement",
    pages="312--336",
    journal=toplas,
    year=1993,
    month=apr,
    volume=15,
    number=2


    author="Dhananjay M. Dhamdhere and Uday P. Khedker",
    title="Complexity of Bidirectional Data Flow Analysis",
    pages="397--408",
    booktitle=popl20,
    address="Charleston, South Carolina",
    year=1993,
    month=jan


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",
    booktitle=popl13,
    address="St.~Petersburg Beach, Florida",
    year=1986,
    month=jan,
    pages="70--85"


You might also examine


    title="Global Value Numbers and Redundant Computations",
    author="Barry K. Rosen and Mark N. Wegman and F. Kenneth Zadeck",
    booktitle=popl15,
    address="San Diego, California",
    year=1988,
    month=jan,
    pages="12--27"


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 cs.rice.edu, in the directory public/preston


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


Preston Briggs
--

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