[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #20 from rguenth at gcc dot gnu dot org 2007-11-23 14:29 --- Fixed. -- rguenth at gcc dot gnu dot org changed: What|Removed |Added Status|NEW |RESOLVED Resolution||FIXED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #19 from rguenth at gcc dot gnu dot org 2007-11-23 14:29 --- Subject: Bug 34176 Author: rguenth Date: Fri Nov 23 14:28:59 2007 New Revision: 130379 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=130379 Log: 2007-11-23 Richard Guenther <[EMAIL PROTECTED]> Michael Matz <[EMAIL PROTECTED]> PR tree-optimization/34176 * alloc-pool.h (empty_alloc_pool): Declare. * alloc-pool.c (empty_alloc_pool): New function. * tree-ssa-sccvn.c (vn_reference_lookup): Also lookup from the valid table if a lookup from the optimistic table failed. (vn_unary_op_lookup): Likewise. (vn_binary_op_lookup): Likewise. (vn_phi_lookup): Likewise. (process_scc): Clear optimistic tables before every iteration. * gcc.c-torture/execute/pr34176.c: New testcase. Added: trunk/gcc/testsuite/gcc.c-torture/execute/pr34176.c Modified: trunk/gcc/ChangeLog trunk/gcc/alloc-pool.c trunk/gcc/alloc-pool.h trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-sccvn.c -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #18 from dberlin at gcc dot gnu dot org 2007-11-22 23:02 --- Subject: Re: [4.3 Regression] SCCVN breaks gettext On 22 Nov 2007 22:51:12 -, matz at gcc dot gnu dot org <[EMAIL PROTECTED]> wrote: > > > --- Comment #17 from matz at gcc dot gnu dot org 2007-11-22 22:51 --- > We could also save the deletes by using a tick counter, but with that patch > the hash tables will be mostly small anyway, so emptying them should be fast > enough I hope. And of course we won't get as optimal results as the RPO > algorithm from the paper, no idea if that's possible without having this > bug. > As long as we fallback to querying the valid table, we should get as optimal results (because by the time it is deleted the results will have been entered in the valid table as the RPO algorithm would have. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #17 from matz at gcc dot gnu dot org 2007-11-22 22:51 --- We could also save the deletes by using a tick counter, but with that patch the hash tables will be mostly small anyway, so emptying them should be fast enough I hope. And of course we won't get as optimal results as the RPO algorithm from the paper, no idea if that's possible without having this bug. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #16 from rguenth at gcc dot gnu dot org 2007-11-22 22:24 --- ... Indeed - wrong types in the testcase :) -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #15 from rguenth at gcc dot gnu dot org 2007-11-22 22:19 --- Bootstrapped / tested on x86_64, interestingly we manage to miscompile the testcase at -O0 now :( (but this _must_ be unrelated to this fix!) -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #14 from rguenth at gcc dot gnu dot org 2007-11-22 20:54 --- Created an attachment (id=14615) --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14615&action=view) prototype patch Patch clearing the optimistic tables before every iteration and doing a fallback lookup on the valid tables if the optimistic table lookup failed. Also has a testcase that aborts if it is miscompiled rather than looping forever. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- 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 -, 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
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #12 from rguenther at suse dot de 2007-11-22 15:08 --- Subject: Re: [4.3 Regression] SCCVN breaks gettext On Thu, 22 Nov 2007, matz at gcc dot gnu dot org wrote: > --- Comment #11 from matz at gcc dot gnu dot org 2007-11-22 14:13 --- > Btw. canonicalization/rewriting on INSERT is indeed okay. As long as the hash > tables are deleted after every iteration (or otherwise invalidated). At least > the now provably false information needs to be removed, which is a bit > difficult to track when you do general rewriting, so invalidating the whole > thing is probably easiest. Though in the paper they state that they'd want to use the optimistic hashtable entries for further SCC processing. In which case you'd either have to invalidate only those entries you added during the current iteration or maybe instead of invalidating it, initialize it with the correct table contents. Richard. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #11 from matz at gcc dot gnu dot org 2007-11-22 14:13 --- Btw. canonicalization/rewriting on INSERT is indeed okay. As long as the hash tables are deleted after every iteration (or otherwise invalidated). At least the now provably false information needs to be removed, which is a bit difficult to track when you do general rewriting, so invalidating the whole thing is probably easiest. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #10 from matz at gcc dot gnu dot org 2007-11-22 14:07 --- Created an attachment (id=14608) --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14608&action=view) my dump (without patch) This is the dump I'm talking about. Richard uses a different compiler, so our SSA version numbers are sometimes different. But his above paste of the problematic part is as good as any, so this is just for completeness. Just with -O from the testcase. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- 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. > > Maybe we aren't traversing uses in function arguments during DFS walk? No, that's not the problem. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
-- rguenth at gcc dot gnu dot org changed: What|Removed |Added Target Milestone|--- |4.3.0 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #8 from rguenth at gcc dot gnu dot org 2007-11-22 14:00 --- If you go through the SCCVN dump you realize that Michas analysis of the problem is correct btw: SCC consists of: nitems_21 nitems_1 new_max_9 dest_10 destptr_3 destptr.2_16 dest.3_17 D.1581_18 D.1582_19 nitems_20 destptr_15 Value numbering nitems_21 stmt = nitems_21 = PHI <0(2), nitems_20(9)> Setting value number of nitems_21 to 0 -- fine. nitems_20 is still VTOP --- Value numbering nitems_1 stmt = nitems_1 = PHI Setting value number of nitems_1 to 0 Value numbering new_max_9 stmt = new_max_9 = nitems_1 + len2_8; RHS nitems_1 + len2_8 simplified to len2_8 has constants 0 Setting value number of new_max_9 to len2_8 Value numbering dest_10 stmt = dest_10 = foo (new_max_9); Setting value number of dest_10 to dest_10 Value numbering destptr_3 stmt = destptr_3 = PHI Setting value number of destptr_3 to dest_10 --- also fine, destptr_15 is still VTOP --- Value numbering destptr.2_16 stmt = destptr.2_16 = (long int) destptr_3; Setting value number of destptr.2_16 to destptr.2_16 Value numbering dest.3_17 stmt = dest.3_17 = (long int) dest_10; Setting value number of dest.3_17 to destptr.2_16 Value numbering D.1581_18 stmt = D.1581_18 = destptr.2_16 - dest.3_17; RHS destptr.2_16 - dest.3_17 simplified to 0 has constants 0 Setting value number of D.1581_18 to 0 Value numbering D.1582_19 stmt = D.1582_19 = D.1581_18 /[ex] 8; RHS D.1581_18 /[ex] 8 simplified to 0 has constants 0 Setting value number of D.1582_19 to 0 Value numbering nitems_20 stmt = nitems_20 = (size_t) D.1582_19; RHS (size_t) D.1582_19 simplified to 0 has constants 0 Setting value number of nitems_20 to 0 --- also ok, this should be corrected later --- Value numbering destptr_15 stmt = destptr_15 = destptr_3 + 8; Setting value number of destptr_15 to destptr_15 --- now, destptr_15 is no longer VTOP! --- Value numbering nitems_21 stmt = nitems_21 = PHI <0(2), nitems_20(9)> Setting value number of nitems_21 to 0 Value numbering nitems_1 stmt = nitems_1 = PHI Setting value number of nitems_1 to 0 Value numbering new_max_9 stmt = new_max_9 = nitems_1 + len2_8; RHS nitems_1 + len2_8 simplified to len2_8 has constants 0 Setting value number of new_max_9 to len2_8 Value numbering dest_10 stmt = dest_10 = foo (new_max_9); Setting value number of dest_10 to dest_10 Value numbering destptr_3 stmt = destptr_3 = PHI Setting value number of destptr_3 to destptr_3 --- correct, destptr_3 is no longer dest_10 --- Value numbering destptr.2_16 stmt = destptr.2_16 = (long int) destptr_3; Setting value number of destptr.2_16 to destptr.2_16 Value numbering dest.3_17 stmt = dest.3_17 = (long int) dest_10; Setting value number of dest.3_17 to destptr.2_16 --- but whoops - why this? exactly because of the hashtable problem --- Value numbering D.1581_18 stmt = D.1581_18 = destptr.2_16 - dest.3_17; RHS destptr.2_16 - dest.3_17 simplified to 0 has constants 1 Setting value number of D.1581_18 to 0 Value numbering D.1582_19 stmt = D.1582_19 = D.1581_18 /[ex] 8; RHS D.1581_18 /[ex] 8 simplified to 0 has constants 1 Setting value number of D.1582_19 to 0 Value numbering nitems_20 stmt = nitems_20 = (size_t) D.1582_19; RHS (size_t) D.1582_19 simplified to 0 has constants 1 Setting value number of nitems_20 to 0 --- oh well - so we didn't correct nitems_20 to be non-null --- Value numbering destptr_15 stmt = destptr_15 = destptr_3 + 8; Setting value number of destptr_15 to destptr_15 Value numbering nitems_21 stmt = nitems_21 = PHI <0(2), nitems_20(9)> Setting value number of nitems_21 to 0 --- and thus now are converged to a wrong solution. --- Value numbering nitems_1 stmt = nitems_1 = PHI Setting value number of nitems_1 to 0 Value numbering new_max_9 stmt = new_max_9 = nitems_1 + len2_8; RHS nitems_1 + len2_8 simplified to len2_8 has constants 0 Setting value number of new_max_9 to len2_8 Value numbering dest_10 stmt = dest_10 = foo (new_max_9); Setting value number of dest_10 to dest_10 Value numbering destptr_3 stmt = destptr_3 = PHI Setting value number of destptr_3 to destptr_3 Value numbering destptr.2_16 stmt = destptr.2_16 = (long int) destptr_3; Setting value number of destptr.2_16 to destptr.2_16 Value numbering dest.3_17 stmt = dest.3_17 = (long int) dest_10; Setting value number of dest.3_17 to destptr.2_16 Value numbering D.1581_18 stmt = D.1581_18 = destptr.2_16 - dest.3_17; RHS destptr.2_16 - dest.3_17 simplified to 0 has constants 1 Setting value number of D.1581_18 to 0 Value numbering D.1582_19 stmt = D.1582_19 = D.1581_18 /[ex] 8; RHS D.1581_18 /[ex] 8 simplified to 0 has constants 1 Setting value number of D.1582_19 to 0 Value numbering nitems_20 stmt = nitems_20 = (size_t) D.1582_19; RHS (size_t) D.1582_19 simplified to 0 has constants 1 Setting value number of nitems_20 to 0 Value numbering destptr_15 stmt = destptr_15 = destptr_3 + 8; Setting value number of destptr_15 to destptr_15 --- no changes. Now the final run with the correct table --- Va
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- 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; > wh
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #6 from rguenther at suse dot de 2007-11-22 09:35 --- Subject: Re: [4.3 Regression] SCCVN breaks gettext On Thu, 22 Nov 2007, dberlin at dberlin dot org wrote: > --- Comment #4 from dberlin at gcc dot gnu dot org 2007-11-22 04:48 > --- > Subject: Re: [4.3 Regression] SCCVN breaks gettext > > 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 SCC looks complete. The IL before FRE is : : # nitems_21 = PHI <0(2), nitems_20(9)> : # nitems_1 = PHI D.1574_5 = hash_find_entry (&list); if (D.1574_5 == 0) goto ; else goto ; : list.0_6 = list; D.1576_7 = *list.0_6; len2_8 = (size_t) D.1576_7; new_max_9 = nitems_1 + len2_8; if (new_max_9 != len2_8) goto ; else goto ; : dest_10 = foo (new_max_9); goto ; : destptr_15 = destptr_3 + 8; : # destptr_3 = PHI # len2_2 = PHI len2_14 = len2_2 + 0x0; if (len2_2 != 0) goto ; else goto ; : destptr.2_16 = (long int) destptr_3; dest.3_17 = (long int) dest_10; D.1581_18 = destptr.2_16 - dest.3_17; D.1582_19 = D.1581_18 /[ex] 8; nitems_20 = (size_t) D.1582_19; goto ; : return 0; and the offending SCC contains: SCC consists of: nitems_21 nitems_1 new_max_9 dest_10 destptr_3 destptr.2_16 dest.3_17 D.1581_18 D.1582_19 nitems_20 destptr_15 where it goes wrong is in the 2nd iteration where it doesn't figure that destptr_3 != dest_10. Note that I also don't believe arbitrary wrong information in the optimistic table can ever lead to always correct information with a new table in just one iteration. Because in our case we set the value number of nitems_20 to zero (and thus the VN of nitems_21), so even with the correct tables we start (and thus never change) with nitems_21 == 0. Richard. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #5 from steven at gcc dot gnu dot org 2007-11-22 07:10 --- > 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). "The one"? "real compiler"? "both"? Parse error! :-) -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #4 from dberlin at gcc dot gnu dot org 2007-11-22 04:48 --- Subject: Re: [4.3 Regression] SCCVN breaks gettext On 22 Nov 2007 04:26:57 -, matz at gcc dot gnu dot org <[EMAIL PROTECTED]> wrote: > > > --- Comment #2 from matz at gcc dot gnu dot org 2007-11-22 04:26 --- > The problem starts already in the first iteration: > Value numbering destptr_3 stmt = destptr_3 = PHI > Setting value number of destptr_3 to dest_9 > > So, for now we assume dest_9 == destptr_3, quite okay, lets assume so. Next > statement: > Value numbering destptr.2_15 stmt = destptr.2_15 = (int) destptr_3; > Setting value number of destptr.2_15 to destptr.2_15 > > Looks innocent, but what this actually does is entering the RHS > ((int)destptr_3) into the unary hash-table, but with translated (!) ssa names, Right, but this is the optimistic set of hash tables, so that is okay. 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. However, at the end of SCC iteration, SSA_VAL should always be correct for everything. > 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. > This can be worked around with also iterating until nothing changes with > the new hash table (with valid_info). That's obviously not what is wanted, 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. > 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. > information into the hash tables which might become invalid in later > iterations. No, this is also okay. Again, it is fine for the optimistic hashtable to have invalid info. It is not okay for SSA_VAL to end up with invalid value numbers at the end of iteration. | > 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, 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
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #3 from matz at gcc dot gnu dot org 2007-11-22 04:31 --- Created an attachment (id=14600) --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14600&action=view) incomplete fix Concept patch touching only the unary case. binary, phi nodes and maybe references would need something similar. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #2 from matz at gcc dot gnu dot org 2007-11-22 04:26 --- The problem starts already in the first iteration: Value numbering destptr_3 stmt = destptr_3 = PHI Setting value number of destptr_3 to dest_9 So, for now we assume dest_9 == destptr_3, quite okay, lets assume so. Next statement: Value numbering destptr.2_15 stmt = destptr.2_15 = (int) destptr_3; Setting value number of destptr.2_15 to destptr.2_15 Looks innocent, but what this actually does is entering the RHS ((int)destptr_3) into the unary hash-table, but with translated (!) ssa names, 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. So, from then on, whenever we are going to process this insn: Value numbering dest.3_16 stmt = dest.3_16 = (int) dest_9; Setting value number of dest.3_16 to destptr.2_15 We are looking up "(int)dest_9" in the unary hash-table, find it, see it's associated value destptr.2_15 in there and happily use it. Even in the later iterations where the initial dest_9 == destptr_3 association isn't generated anymore. But the hashtable still contains the (then invalid) RHS (int)dest_9. So, during the optimistic iterations we come to a fix point, but a completely wrong one. In particular we still (wrongly) think that nitems_19 is zero. As the valid_info only iterates once over the SCC this isn't enough to fix the problem. It has a clean hash-table again, so the above breakage isn't reintroduced, but as it started with wrong info it still is wrong afterwards (in particular when it sees that nitems_19 is not zero it won't reiterate). This can be worked around with also iterating until nothing changes with the new hash table (with valid_info). That's obviously not what is wanted, 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), or to not enter information into the hash tables which might become invalid in later iterations. The reason for inserting the translated expressions into the hash table obviously is for optimization purposes (so that we are sure we have a canonical 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. Proof of concept patch fixing only the unary case (and hence this particular bug) comes. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
[Bug tree-optimization/34176] [4.3 Regression] SCCVN breaks gettext
--- Comment #1 from rguenth at gcc dot gnu dot org 2007-11-21 23:02 --- If you look at what SCCVN does for the affected SCC then you see that iteration converges to Setting value number of dest_7 to dest_7 Setting value number of list_23 to list_23 Value numbering destptr_3 stmt = destptr_3 = PHI Setting value number of destptr_3 to destptr_3 Value numbering destptr.3_13 stmt = destptr.3_13 = (int) destptr_3; Setting value number of destptr.3_13 to destptr.3_13 Value numbering dest.4_14 stmt = dest.4_14 = (int) dest_7; Setting value number of dest.4_14 to destptr.3_13 Value numbering D.1217_15 stmt = D.1217_15 = destptr.3_13 - dest.4_14; RHS destptr.3_13 - dest.4_14 simplified to 0 has constants 1 ... that is, destptr.3_13 == dest.4_14 -- but, in the final run with the correct table in place we get Setting value number of dest_7 to dest_7 Setting value number of list_23 to list_23 Value numbering destptr_3 stmt = destptr_3 = PHI Setting value number of destptr_3 to destptr_3 Value numbering destptr.3_13 stmt = destptr.3_13 = (int) destptr_3; Setting value number of destptr.3_13 to destptr.3_13 Value numbering dest.4_14 stmt = dest.4_14 = (int) dest_7; Setting value number of dest.4_14 to dest.4_14 Value numbering D.1217_15 stmt = D.1217_15 = destptr.3_13 - dest.4_14; Setting value number of D.1217_15 to D.1217_15 increasing the number of iterations doesn't "fix" it. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34176
