[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext

["dberlin at dberlin dot org" <gcc-bugzilla at gcc dot gnu dot org>]

------- Comment #13 from dberlin at gcc dot gnu dot org  2007-11-22 15:35 -------
Subject: Re:  [4.3 Regression] SCCVN breaks gettext

On 22 Nov 2007 14:03:35 -0000, matz at suse dot de
<gcc-bugzilla@gcc.gnu.org> wrote:
>
>
> ------- Comment #9 from matz at suse dot de  2007-11-22 14:03 -------
> Subject: Re:  [4.3 Regression] SCCVN breaks
>  gettext
>
> [sorry for the breakage in last response]
>
> It does not.  The RPO algorithm (the one proven) uses hash table deletes
> per iteration.  About the SCC algorithm they have to say this:
>
> "Since we cannot remove the entries from the hash table after each pass as
> the RPO algorithm does, we will use two hash tables.  The iterative phase
> uses an optimistic hash table.  Once the value numbers in the SCC
> stabilize, entries are added to the valid table."
>
> Without proof that this actually has the same properties as the RPO
> algorithm.  Had they gone through the hassle of trying to prove this they
> would have notived that it doesn't work.
Of course it does.
The only reason it wouldn't work is if you store side info that you
don't replace after SCC iteration.  It is quite careful to reset the
value of has_constants/etc when necessary (at least it was when i was
done :P).
The RPO algorithm keeps invalid info about things all the time, and by
deleting it at the end of each iteration, just gets it replaced by
later more valid info.
The SCC algorithm should be doing the same thing.
The reason is leaves info is the same reason the RPO algorithm doesn't
delete info after value numbering a given value for a given iteration,
but instead leaves it until the end of the iteration (which means it
will get invalid info for the iteration for a lot of values).

There is a longer version of the paper that actually goes through the
formal proofs somewhere, i'll find it for you.
In the meanwhile, i'm just going to fix the bug.
:)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176