Tue, 8 Nov 1994 00:16:41 GMT

Related articles |
---|

nuances of Copy Propagation? johnmce@world.std.com (1994-11-03) |

Re: nuances of Copy Propagation? c1venkat@watson.ibm.com (K.S. Venkatesh) (1994-11-09) |

Re: nuances of Copy Propagation? wjs@VNET.IBM.COM (William Schmidt) (1994-11-09) |

Re: nuances of Copy Propagation? joris@eunet.be (1994-11-06) |

Re: nuances of Copy Propagation? davidm@Rational.COM (1994-11-08) |

Re: nuances of Copy Propagation? bill@amber.ssd.csd.harris.com (1994-11-14) |

Newsgroups: | comp.compilers |

From: | davidm@Rational.COM (David Moore) |

Keywords: | optimize |

Organization: | Rational Software Corporation |

References: | 94-11-028 |

Date: | Tue, 8 Nov 1994 00:16:41 GMT |

johnmce@world.std.com (John McEnerney) writes:

*>I'm implementing the Copy Propagation optimization as described in the*

*>new Dragon Book, pp. 636-638, and I've run into an interesting problem*

*>motivated by the following case:*

y=x; z=y; x=3; w=z+100; (1)

*>The dataflow computation tells me that I can propagate 'x' to 'z=y', and*

*>that I can propagate 'y' to 'w=z+100', but obviously I can't eliminate*

*>both 'y=x' and 'z=y' because of the assignment to x. So I can choose one*

*>or the other:*

z=x; x=3; w=z+100; -OR- y=x; x=3; w=y+100; (2)

*>At the moment I've decided not to propagate copies to other copies, on*

*>the assumption that that potentially invalidates the dataflow information.*

*>On the other hand, I'd sure like to catch this case:*

y=x; z=y; r=3; w=z+100; => r=3; w=x+100; (3)

You can look at this problem as either that of eliminating copies, or

else of "assignment path shortening" followed by unused variable elimination.

So that (1) above would be replaced by

y=x;z=x;x=3;w=(one of y or z)+100;

Followed by a scan for unused variables, which would delete whichever of

y and z was now unused. (Is selecting which to use potentially difficult?)

You end up with one of (2)

For (3), one gets y=x;z=x;r=3;w=x+100; and y and z get eliminated for

r=3;w=x+100;

This "assignment path shortening" can be done while eliminating global

cse's (available expressions), in which keeping track of the changes

you have made is quite easy.

Also, assignment path shortening is worth doing for itself since it

promotes instruction scheduling and can help locality of reference

as well (eg, reducing spilling and filling of multiple copies of a value).

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.