Re: PRE information needed (John McEnerney)
28 Oct 1999 01:57:07 -0400

          From comp.compilers

Related articles
PRE information needed (Vikram V Asrani) (1999-10-27)
Re: PRE information needed (1999-10-28)
Re: PRE information needed (David Greene) (1999-10-28)
Re: PRE information needed (Andrew Tucker) (1999-10-28)
| List of all articles for this month |

From: (John McEnerney)
Newsgroups: comp.compilers
Date: 28 Oct 1999 01:57:07 -0400
Organization: Giganews.Com - Premium News Outsourcing
References: 99-10-119
Keywords: optimize

"Vikram.V.Asrani" <> wrote:

> I am planning to do my compiler project on Partial Redundancy
> Elimination. I have only a brief idea on what this topic covers and
> am trying to get more information on this topic. I believe that there
> are a couple of algorithms, one of which is a standard one but is more
> restrictive. I am searching information about the other algorithm
> which I believe is called PRE.

The initial paper is by Morel & Renvoise. The later revision is called
Lazy Code Motion by Knoop, Ruthing, & Steffen. The "standard"
algorithm these days is the improvement to the KRS approach by
Dreschler & Stadel.

The D&S paper can be found in SIGPLAN notices 28:5 May 1993.

There's also a good summary of this approach in Morgan's text, and an
interesting variation that combines PRE with Global Value Numbering in
L. Taylor Simpson's PhD thesis, titled "Value-Driven Redundancy

Also, Preston Briggs did a nice summary of PRE. You can find the
Briggs and Simpson stuff if you poke around at looking
for the Massively Scalar Compiler Project. There's a page where all of
the papers are available in postscript form.

John McEnerney (

Post a followup to this message

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