Re: Copy Propagation

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

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