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)
>
davidm@Rational.COM (David Moore) writes:
> 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).


Well..... I think this statement oversimplifies things just a *little*
bit. For instance, in going from (1) to the second case of (2) we have
lengthened the lifetime of variable y; in fact, its lifetime overlaps that
of variable x in the transformed code whereas it did not in the original.


However, this example is perhaps too simplistic, because the change in
lifetime is not very significant. In real-life examples, that is not the
case at all. Copy propagation can easily make things worse regarding
instruction scheduling by lengthening the lifetime of "the wrong" variable.
(To put this another way, inserting a seemingly extraneous yet strategic
copy into a long code sequence can occasionally allow a fortuitous register
allocation and instruction schedule that makes the code better than it is
without the copy.)


In the general case, this is probably too hard an interaction to worry
about for most compilers. Nevertheless, a professional should be aware of
them, if for no other reason than to avoid surprise.


--
Bill Leonard
Harris Computer Systems Corporation
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
Bill.Leonard@mail.csd.harris.com
--

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