28 Feb 2005 00:55:21 -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: | "Aaroneous" <aaron.keen@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 28 Feb 2005 00:55:21 -0500 |

Organization: | Compilers Central |

Keywords: | analysis, question |

Posted-Date: | 28 Feb 2005 00:55:21 EST |

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'. However, the

algorithm in Muchnick considers each copy as distinct (defining a

quadruple of the source, target, block number, and position within the

block). As such, the intersection of the copyOut from the predecessors

will be empty. Muchnick gives a similar example and explicitly states

that the algorithm will not propagate this copy.

Moreover, the discussion in the Dragon book states as a requirement

that only a single definition of 'b' can reach the statement labeled

"s". This also precludes propagating 'x' in the above example. In

fact, the red Dragon book added the following sentence to the

discussion from the green Dragon book:

"Note the important consequence of the fact that different

assignments x := y kill each other; in[B] can contain only one copy

statement with x on the left."

This implies that the copy statements are also considered to be

distinct.

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.

Any discussion would be greatly appreciated.

Thanks,

Aaron

[Looks to me like you need to figure out some way to recognize the identical

assignment in both halves of the branch and hoist it up above the if. -John]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.