1 Mar 2005 15:52:15 -0500

Related articles |
---|

Copy Propagation aaron.keen@gmail.com (Aaroneous) (2005-02-28) |

Re: Copy Propagation dberlin@dberlin.org (Daniel Berlin) (2005-03-01) |

Re: Copy Propagation gneuner2@comcast.net (George Neuner) (2005-03-01) |

Re: Copy Propagation dnovillo@redhat.com (Diego Novillo) (2005-03-04) |

From: | Daniel Berlin <dberlin@dberlin.org> |

Newsgroups: | comp.compilers |

Date: | 1 Mar 2005 15:52:15 -0500 |

Organization: | Compilers Central |

References: | 05-02-102 |

Keywords: | optimize, analysis |

Posted-Date: | 01 Mar 2005 15:52:15 EST |

On Mon, 28 Feb 2005, Aaroneous wrote:

*> This may be a stupid question, but I have been unable to find the*

*> answer thus far. First a little(?) lead-in.*

*>*

*> I've looked at the algorithms for copy propagation as described in a*

*> number of books (most notably, the Dragon book and Muchnick's book)*

*> and I have a question about one of the specific requirements of the*

*> analysis.*

*>*

*> Consider the following code (though a CFG picture would be better):*

*>*

*> if ( ... )*

*> {*

*> b = x;*

*> }*

*> else*

*> {*

*> b = x;*

*> }*

*> a = b + c; /* s */*

*>*

*> It would seem that 'b' could be replaced by 'x' since neither 'b' nor*

*> 'x' is defined between the copy and the use of 'b'.*

Yes, you could.

However, this is not copy-propagation.

It is value numbering or code hoisting/sinking, depending on what you want

to do.

*>*

*> Finally, to the question. Why? Certainly this specific example isn't*

*> intended to cover all possible scenarios, but I've been unable to see*

*> why such copies must be considered distinct.*

Because they are distinct from the perspective of copies. They are

each seperate copies of the same value. They happen to have the same

value, but this is *only* because there is no modification of x before

b, or modification of b prior to b. IE they are really distinct

copies, but they have the same value.

As for why you wouldn't try to handle this in a copy propagation

algorithm, the answer is that you could, if you did it in ssa form.

You could, of course, subsume your copy propagation with some value

numbering optimization if you really want.

In order to see this as a copy propagation problem + value numbering

problem, view the code as it would be in ssa

form:

if ( .... )

{

b_1 = x_1;

*}*

else

{

b_2 = x_1;

*}*

b_3 = PHI (b_1, b_2);

a_4 = b_3 + c_5;

*}*

You can see clearly that it is only a copy if b_1 and b_2 have the same

value.

You could teach an ssa copy propagator to handle the above case, first by

transforming it into

...

b_3 = PHI (x_1, x_1);

Then by seeing that b_3 = x_1 for all edges (ie value numbering the phi

and determining all values are equivalent), and copy propagating b_3 =

x_1.

--Dan

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.