Compilers - Copy Propagation

Author

Copy Propagation

Aaroneous

2005-02-28, 3:59 am

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]

Daniel Berlin

2005-03-01, 8:59 pm

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

George Neuner

2005-03-01, 8:59 pm

On 28 Feb 2005 00:55:21 -0500, "Aaroneous" <aaron.keen@gmail.com>
wrote:

>Consider the following code ...
> :
> <snip>
> :
>... 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.

As John mentioned, you can try recognizing the identical assignment
and hoisting it above the branch.

More generally, you should look into value numbering and single static
assignment (SSA).

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

In general it is not obvious that two assignments are identical - or
even that an assignment has taken place. In a more complex example
"x" might be assignable through a pointer or passed by reference to an
external function. The compiler can't always see all uses and
sometimes has to make assumptions. The algorithm must guarantee that
any assumptions about the code are always safe - sometimes at the
expense of efficiency.

SSA and value numbering are annotation methods which allow the
compiler to identify and track uses of values rather than identifiers.
The general idea behind both methods is to add subscripts to
identifiers and to create a new subscript each time the value the
identifier refers to might have been changed. Once annotation is
complete, each unique value has a unique name, making it obvious that
different uses of the same identifier really refer to the same value.

Neither method is covered in the dragon books - you need newer books.
The term "value numbering" is used, but only in passing as a
historical note. With careful reading you can infer what it means
from the discussion surrounding it, but there's no direct mention in
the book of how it might be used for code optimization.

George

Diego Novillo

2005-03-04, 8:58 pm

Daniel Berlin wrote:

> You could teach an ssa copy propagator to handle the above case, first by
> transforming it into
> b_3 = PHI (x_1, x_1);
>
Which is exactly what GCC does, but I guess you already knew that ;)

Diego.

Sponsored Links