# Re: Common subexpression elimination (CSE) using value numbering?

## torbenm@diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)26 May 2005 23:08:22 -0400

From comp.compilers

Related articles
Common subexpression elimination (CSE) using value numbering? Hu.YuehWei@gmail.com (2005-05-26)
Re: Common subexpression elimination (CSE) using value numbering? torbenm@diku.dk (2005-05-26)
Re: Common subexpression elimination (CSE) using value numbering? vidar.hokstad@gmail.com (2005-05-26)
Re: Common subexpression elimination (CSE) using value numbering? stevenb@suse.de (Steven Bosscher) (2005-05-26)
| List of all articles for this month |

 From: torbenm@diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=) Newsgroups: comp.compilers Date: 26 May 2005 23:08:22 -0400 Organization: Department of Computer Science, University of Copenhagen References: 05-05-211 Keywords: analysis Posted-Date: 26 May 2005 23:08:22 EDT

Hu.YuehWei@gmail.com writes:

> After transfering to the SSA form:
>
> A0 = B0 + C0
> A1 = D0
> E0 = B0 + C0
>
> After applying the value numbering, I can say that A0 and E0 have the
> same value. After applying AVAIL common subexpression elimination, I
> can replace the last expression with "E0 = A0". Thus, the whole codes
> become this one:
>
> A0 = B0 + C0
> A1 = D0
> E0 = A0 <--
>
> However, because both "A0" and "A1" have the same memory address, so
> that I will get a wrong value when I execute the last expression after
> the second expression.

Why do you think A0 and A1 must share the same location? Sure, they
were originally the same variable, but one of the points of SSA form
is to remove such constraints, so different instances of what usd to
be the same variable can be in different locations. This is one of
the properties that allow simple copy propagation and such in the SSA
form.

After optimisations have been applied to the SSA form, you run
register allocation, which may try to coalesce variables that share a
phi-node. This can be done with biased colouring or conservative
coaslescing.

Torben
[Many other people wrote to point out that A0 and A1 needn't live in
the same place. -John]

Post a followup to this message