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;


|> 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;


I ran into this same problem awhile back. The solution is
actually quite simple, once you see it. In your first
example, after propagating y=x to z=y, it is only legal to
propagate the resulting z=x to uses of z if both copies y=x
and z=y are "available" (in the sense of reaching copies) at
those uses of z.


In my code, with each copy I keep a list of "subsumed copies"
(couldn't think of a better term). So after propagating y=x
to z=y, the subsumed copy list for the modified copy z=x
contains a pointer to y=x. Now whenever I want to propagate
z=x to a use of z, I can do so iff my dataflow equations say
that I could propagate y=x AND z=y to that location.


Of course, for this to work you have to visit copies in order
in the forward direction according to your dfo numbers.


As your third example shows, this is definitely useful in
cleaning up long chains of register copies. This can be
important, since many intermediate code generators find it
convenient to put out a lot of extraneous copies, rather than
go to the trouble of trying to avoid them when unnecessary.


Hope this helps,
Bill


--
William Schmidt (507) 253-0852 t/l 553-0852
4B4/005-2 wills@rchland.ibm.com (internal)
IBM Rochester wjs@vnet.ibm.com (external)
--

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