Re: nuances of Copy Propagation?

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

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