Mon, 3 May 1993 14:55:22 GMT

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

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.