------- 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 <[EMAIL PROTECTED]> 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
