Re: Questions about partial redundancy elimination

bill@amber.csd.harris.com (Bill Leonard)
Mon, 3 May 1993 14:55:22 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: bill@amber.csd.harris.com (Bill Leonard)
Keywords: optimize
Organization: Harris CSD, Ft. Lauderdale, FL
References: 93-05-008
Date: Mon, 3 May 1993 14:55:22 GMT

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


Post a followup to this message

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