|nuances of Copy Propagation? email@example.com (1994-11-03)|
|Re: nuances of Copy Propagation? firstname.lastname@example.org (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? email@example.com (1994-11-06)|
|Re: nuances of Copy Propagation? davidm@Rational.COM (1994-11-08)|
|Re: nuances of Copy Propagation? firstname.lastname@example.org (1994-11-14)|
|From:||davidm@Rational.COM (David Moore)|
|Organization:||Rational Software Corporation|
|Date:||Tue, 8 Nov 1994 00:16:41 GMT|
email@example.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
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).
Return to the
Search the comp.compilers archives again.