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

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]

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