Wed, 9 Nov 1994 06:14:49 GMT

Related articles |
---|

nuances of Copy Propagation? johnmce@world.std.com (1994-11-03) |

Re: nuances of Copy Propagation? c1venkat@watson.ibm.com (K.S. Venkatesh) (1994-11-09) |

Re: nuances of Copy Propagation? wjs@VNET.IBM.COM (William Schmidt) (1994-11-09) |

Re: nuances of Copy Propagation? joris@eunet.be (1994-11-06) |

Re: nuances of Copy Propagation? davidm@Rational.COM (1994-11-08) |

Re: nuances of Copy Propagation? bill@amber.ssd.csd.harris.com (1994-11-14) |

Newsgroups: | comp.compilers |

From: | William Schmidt <wjs@VNET.IBM.COM> |

Keywords: | optimize |

Organization: | Compilers Central |

References: | 94-11-028 |

Date: | Wed, 9 Nov 1994 06:14:49 GMT |

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.