Re: Copy Propagation

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

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