Re: Questions about partial redundancy elimination

baxter@Austin.slcs.slb.com (Ira Baxter) writes:
> There's an interesting paper in the most recent SIGPLAN on elimination of
> partial redundancies by computing where expressions can be moved in a
> control flow graph:
>
> The paper contains the remark: "It is assumed that commands computing
> expressions deliver their results to psuedo-registers, and that all
> computations of the same expression always use the same psuedo-register as
> the result register."
>
> This seems to imply that common subexpression *detection*, (if not
> elimination), complete with verification of identical control dependences
> has already taken place, or multiple instances of the same expression
> would have no such gaurantee.


I haven't seen the paper, but our optimizer uses Partial Redundancy
Elimination a la Morel and Renvoise, and we don't make such an assumption.
I suspect the difference lies in the intermediate form: this assumption
makes me believe that their intermediate form is tuples, so that each
operand is some psuedo-register; the linkage between result and use is
implied by the psuedo-register name.


Our intermediate form is a tree, so the linkage between the result of a
computation and its use is explicit in the tree. Therefore, we have no
need to maintain the same psuedo-register name in order to detect that two
computations are "the same". If two trees occurring on a given execution
path have the same shape, the same leaves, and the leaf operands of the
second tree have not been modified since the first tree was evaluated,
then the second tree computes the same result as the first. (Gee, I hope
that was clear enough. :-)


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