Re: Questions about partial redundancy elimination

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

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