------- Comment #7 from matz at suse dot de 2007-11-22 13:58 -------
Subject: Re: [4.3 Regression] SCCVN breaks
gettext
Hi,
On Thu, 22 Nov 2007, dberlin at dberlin dot org wrote:
> Right, but this is the optimistic set of hash tables, so that is okay.
I initially thought so too, but it really isn't.
> At the end of SCC iteration, it is okay to keep optimistic
> assumptions in the optimistic table, even if they turned out to be
> wrong.
It's okay only as long as you haven't proven them wrong. I.e. it's okay
to have unproven but _consistent_ entries in the hash table. It is not
okay to have inconsistent data in there, because it ripples through the
whole SCC then. As in this case.
> > ergo it enters (int)dest_9 into the hashtable, as having destptr.2_15 as
> > value. I.e. (int)dest_9 == destptr.2_15. From there on everything breaks
> > apart, because nobody is ever removing this association from the hash-table.
> > In particular we still (wrongly) think that nitems_19 is zero.
>
> I don't see where above it has set nitems_19 to zero.
I'll attach the complete dump. nitems_19 is zero because it is computed
like so:
Value numbering dest.3_16 stmt = dest.3_16 = (int) dest_9;
Setting value number of dest.3_16 to destptr.2_15
Value numbering D.1214_17 stmt = D.1214_17 = destptr.2_15 - dest.3_16;
RHS destptr.2_15 - dest.3_16 simplified to 0 has constants 0
Setting value number of D.1214_17 to 0
Value numbering D.1215_18 stmt = D.1215_18 = D.1214_17 /[ex] 8;
RHS D.1214_17 /[ex] 8 simplified to 0 has constants 0
Setting value number of D.1215_18 to 0
Value numbering nitems_19 stmt = nitems_19 = (size_t) D.1215_18;
RHS (size_t) D.1215_18 simplified to 0 has constants 0
Setting value number of nitems_19 to 0
So, because of the (in later passes invalid (!)) association of
(int)dest_9 == destptr.2_15
--> D.1214_17 = destptr.2_15 - dest.3_16
== destptr.2_15 - destptr.2_15
== 0
--> D.1215_18 == 0
--> nitems_19 == 0
As the initial problem is the association of (int)dest_9 and destptr.2_15,
and that stays in the hash table forever more we never notice that
nitems_19 (and the other values in between) are _not_ zero. Not during
the optimistic iterations at least.
When we switch to valid_info (equivalent to deleting the hash table) we do
notice that (we don't "discover" the invalid (int)dest_9 == destptr.2_15),
nitems_19 isn't zero anymore. But nitems_19 happens to be traversed later
than nitems_1 (later that nitems_20), so the now correct value of
nitems_19 isn't used anymore.
> There should be no need, as the fixpoint iteration of the optimistc
> table should eventually end up with the values you want to insert into
> the valid table.
> That's in fact, the whole point.
But as shown above it doesn't work that way.
>
> > so there has to be a way to either cleanup the hashtable after iterations
> > (this also doesn't seem to be designed in this way),
>
> Again, it's okay for the optimistic assumptions to remain in the
> table, and in fact, is designed for it to happen.
> The paper goes into why this is so.
The paper conveniently proves the algorithm which _deletes_ the hash table
between iterations. And then handwaves over why it's also okay to not
delete it. It's wrong.
> No, this is also okay.
> Again, it is fine for the optimistic hashtable to have invalid info.
No, it's not. unproven but consistent is okay. provably false is not.
> > version in it), but this canonicalization needs to happen when looking up
> > the hash table, not when _inserting_ into it, as canonicalization is
> > transient
> > and changes from iteration to iteration.
> >
> Again, this isn't right. The paper goes into detail as to why it is
> okay for the optimistic talbe to behave this way,
It goes not. The RPO algorithm (the one proven) uses hash table deletes
per iteration. About the SCC algorithm they have to say this:
" º ¥ «¤´
¥¤ · § ¼´ ¯§¯ ¦ Â¥ © ± ¯§ ¥¤ · Â¥ ® ¯ ¸± ® ¤ « ª
¦ © § ¥¤
vc§1Y8Ey²cÂ|v(1¢Â¨d¾¨vÂÂ1c¦Yv6c§v1c©Â
and why it is okay
> to do algebraic simplification/etc on insert.
>
> The real problem seems to me, at least unless you guys haven't pasted
> that part of the trace, that nitems_19 isn't part of the SCC but
> should be. By the time iteration of the SCC finishes, we should have
> discovered that nitems_19 does not have the value 0.
>
> The one in a real compiler I have of SCCVN both do canonicalization on
> insert, as does the original code from Rice's massively scalar
> compiler (which is where the algorithm comes from).
>
> Maybe we aren't traversing uses in function arguments during DFS walk?
>
> Given the code
>
> size_t new_max = nitems + len2;
>
> if (new_max != len2)
> break;
> dest = foo (new_max);
>
> destptr = dest;
> while (len2--)
> destptr++;
>
> nitems = destptr - dest;
>
> the SCC we get should consist of destptr, dest, nitems, len2, and new_max
>
> I could see if we were not DFS walking the argument to foo for some
> reason, we would never get new_max/nitems/len2 into the SCC.
>
> --Dan
>
>
>
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
