Re: Questions about partial redundancy elimination

preston@dawn.cs.rice.edu (Preston Briggs)
Wed, 5 May 1993 13:15:53 GMT

          From comp.compilers

Related articles
Questions about partial redundancy elimination baxter@Austin.slcs.slb.com (1993-04-30)
Re: Questions about partial redundancy elimination preston@dawn.cs.rice.edu (1993-05-01)
Re: Questions about partial redundancy elimination bill@amber.csd.harris.com (1993-05-03)
Re: Questions about partial redundancy elimination max@nic.gac.edu (1993-05-04)
Re: Questions about partial redundancy elimination preston@dawn.cs.rice.edu (1993-05-05)
Questions about partial redundancy elimination jk@informatik.uni-kiel.dbp.de (1993-05-17)
Re: Questions about partial redundancy elimination uday@cse.iitb.ernet.in (1993-05-18)
| List of all articles for this month |

Newsgroups: comp.compilers
From: preston@dawn.cs.rice.edu (Preston Briggs)
Keywords: optimize
Organization: Rice University, Houston
References: 93-05-008 93-05-019
Date: Wed, 5 May 1993 13:15:53 GMT

I wrote:
> Here's our rules for intermediate code generation to support PRE:
>
> Whenever generating an expression (say r10 + r11), see if that
> expression has been generated before. If so, make the new
> expression assign to the same result register as the old one.
> Thus, whenever we see r10 + r11, it will always be assigned to
> the same register. This is easily accomplished by maintaining
> a hash table during code generation. ...


and Max Hailperin <max@nic.gac.edu> writes:
>Right. The earliest use I know of for this idea is the PL.8 compiler.


Yes, they're the source of almost everything I do...


>you never did explain the
>following (which looks like a start on rank ordering):
>
> Make the result of an expression have a higher register number
> than its operands (so, we get r12 = r10 + r11, never r1 = r2 + r3).


I believe I got this idea from Dreschler and Stadel, but I can't find it
in their papers right now. I don't believe it's necessary, but it made
the implementation of PRE simpler in a couple of respects. One example is
the insertion of complex expressions at the end of a basic block. In our
optimizer, instructions can only perform only one arithmetic operation
each, so a complex expression requires many instructions (or
subexpressions). After performing all the analysis, we use the results to
tell us which expressions should be inserted in each block. The numbering
ensures that they will be inserted in the correct order.


This is similar to the "rank" concept used by Rosen, Wegman, and Zadeck in
that they use their rank to control the orderering of instructions in a
block. However, their ranking is more sophisticated and is also used to
help control the whole algorithm.


Preston Briggs
--


Post a followup to this message

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