Wed, 2 Feb 1994 15:24:32 GMT

Related articles |
---|

partial redundancy hmcnair@pacific.urbana.mcd.mot.com (1994-01-28) |

Re: partial redundancy bill@amber.csd.harris.com (1994-01-31) |

Re: partial redundancy elimination knoop@fmi.uni-passau.de (Jens Knoop) (1994-02-02) |

partial redundancy elimination mnaef@iiic.ethz.ch (Michael Naef) (1996-09-06) |

Re: partial redundancy elimination vijay@crhc.uiuc.edu (Vijay Gupta) (1996-09-15) |

Re: partial redundancy elimination bill@amber.ssd.csd.harris.com (1996-09-15) |

Re: partial redundancy elimination dejong@marengo.imec.be (1996-09-16) |

Re: partial redundancy elimination max@crusell.gac.edu (Max Hailperin) (1996-09-17) |

Newsgroups: | comp.compilers |

From: | Jens Knoop <knoop@fmi.uni-passau.de> |

Keywords: | optimize, bibliography, FTP |

Organization: | Compilers Central |

References: | 94-01-121 94-01-141 |

Date: | Wed, 2 Feb 1994 15:24:32 GMT |

bill@ssd.csd.harris.com (Bill Leonard) writes

*> "Lazy Code Motion" by Knoop, R\"uthing and Steffen in*

*> SIGPLAN PLDI '92.*

*> Be sure you also get a copy of the article "Some Comments on "A Solution*

*> to a Problem with Morel and Renvoise's 'Global Optimization by Suppression*

*> of Partial Redundancies'", by Arthur Sorkin, ACM TOPLAS, Vol. 11, No. 4,*

*> Oct. '89.*

*> ... We use partial redundancies in our*

*> compilers, modified according to that article. We used to use the*

*> unmodified form and found that it moved computations too far back in the*

*> code, thus extending the lifetime of temporaries. With the modified form,*

*> that problem is significantly lessened ...*

Note that the lifetime anomaly, which according to Bill Leonard's

experience is significantly lessened using Sorkin's heuristics is

completely avoided by the algorithm for lazy code motion cited above. In

fact, this algorithm results in "computationally" and "lifetime" optimal

programs, i.e. the lifetimes of temporaries introduced by the

transformation are provably as short as possible, while every partial

redundancy that can be eliminated, it is eliminated.

An extended and revised version of the PLDI'92 paper is going to appear in

TOPLAS. Its title is "Optimal code motion: Theory and practice" by Oliver

R\"uthing, Bernhard Steffen and myself. The variant of the algorithm for

lazy code motion presented there directly works on flow graphs composed of

basic blocks rather than single statements. This supports its integration

in existing compiler environments. Moreover, the 4 purely uni-directional

analyses lazy code motion consists of (In fact, no bidirectional analysis

as in Sorkin's algorithm!) are reorganized such that the first and the

last two analyses can be computed in parallel.

You can get PostScript-versions of these papers via anonymous ftp. The

details are given below. In particular, in lsr-jpl-xx.ps.Z an extension of

lazy code motion to strength reduction is presented:

ftp-address: ftp.uni-passau.de

guest-login: anonymous

password: email-address

directory: /pub/local/parallel/papers

files: ocm-9310-xx.ps.Z (Optimal code motion: Theory and practice)

lcm-9208-xx.ps.Z (Lazy code motion)

lsr-jpl-xx.ps.Z (Lazy strength reduction)

with "xx" \in {a4,us} depending

on the prefered paper format.

-----

Jens Knoop E-Mail: knoop@fmi.uni-passau.de

Department of Computer Science Phone: ++49-851-509-716

University of Passau Fax: ++49-851-509-346

Innstrasse 33

D-94032 Passau

Federal Republic of Germany

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.