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


I am assuming that you are referring only to copy propagation within a
basic block. What I did, was to have a hashed table of copies for all
local variables, and on every use of a variable, look up the table and
replace it with its copy. In the example, when y=x is done, I will
hash to y and set its copy to x. when z = y is done, I will hash to z
and set its copy to y's copy(x). when w=z+100 is seen, I will hash
to z and realize that its copy is x. So I will replace z with x. I did
not get an oppurtunity to try this out fully, so think it out and tell
me whether you could poke a hole in it.


K.S.Venkatesh
e-mail: c1venkat@watson.ibm.com


--

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