Re: partial redundancy

hmcnair@pacific.urbana.mcd.mot.com (Henry McNair) writes:
> [re partial redundancy elimination, I have a refrence to]
>
> "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.


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. It appeared in ACM
Transactions on Programming Languages and Systems, Vol. 11, No. 4, Oct.
'89.


> 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?


Partial redundancies does invariant hoisting as well as common
subexpressions. It is a kind of generalization of invariant hoisting, yes.


> 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.)


The algorithm will suppress all redundant calculations that are exposed to
it. Of course, if your intermediate form is too high level and an
"instruction" in your intermediate form generates lots of code, you can
miss redundant computations there, but that is not unique to partial
redundancies.


The primary problem (with a possible solution) with partial redundancies
is outlined in the article I cited. 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, and we haven't noted any serious
loss in optimization effectiveness.
--
Bill Leonard
Harris Computer Systems Division
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
bill@ssd.csd.harris.com
--

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