nuances of Copy Propagation?

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;


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;


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;


Has anyone encountered this problem before and hit upon a reasonable
solution? I'd hate to have to recompute the dataflow information or
anything like that. At the moment, I figure it is safest to not propagate
copies to other copies, and hope that register coalescing during coloring
will catch the leftover opportunities, but I'd love to hear of a better
solution.


-- John (johnmce@world.std.com)
--

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