Copy Propagation

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]

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