Copy Propagation

"Aaroneous" <>
28 Feb 2005 00:55:21 -0500

          From comp.compilers

Related articles
Copy Propagation (Aaroneous) (2005-02-28)
Re: Copy Propagation (Daniel Berlin) (2005-03-01)
Re: Copy Propagation (George Neuner) (2005-03-01)
Re: Copy Propagation (Diego Novillo) (2005-03-04)
| List of all articles for this month |

From: "Aaroneous" <>
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

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

if ( ... )
        b = x;
        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

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.

[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.