Kerberos is miscompiled by gcc-4.8. The impact is detailed at https://bugs.launchpad.net/bugs/1347147, but here is a reduced test case. The expected return is 0, but when compiled with gcc-4.8 -O2, it returns 1. $ cat bug.c struct node { struct node *next, *prev; } node; struct head { struct node *first; } heads[5]; int k = 2; struct head *head = &heads[2]; int main() { node.prev = (void *)head; head->first = &node; struct node *n = head->first; struct head *h = &heads[k]; if (n->prev == (void *)h) h->first = n->next; else n->prev->next = n->next; n->next = h->first; return n->next == &node; } $ gcc-4.7 -Wall -O2 bug.c -o bug; ./bug; echo $? 0 $ gcc-4.8 -Wall -O2 bug.c -o bug; ./bug; echo $? 1 $ gcc-4.9 -Wall -O2 bug.c -o bug; ./bug; echo $? 0 $ dpkg -l gcc-4.7 gcc-4.8 gcc-4.9 […] ii gcc-4.7 4.7.4-2ubuntu1 amd64 GNU C compiler ii gcc-4.8 4.8.3-6ubuntu1 amd64 GNU C compiler ii gcc-4.9 4.9.1-3ubuntu2 amd64 GNU C compiler I bisected the point where the problem disappeared between 4.8 and 4.9 at r202525. However, I don’t understand why. I’m scared by the fact that r202525 was intended to fix a “missed-optimization” bug (bug 58404).
The testcase is violating strict-aliasing rules as you access a struct head as struct node here: if (n->prev == (void *)h) h->first = n->next; else n->prev->next = n->next; as n->prev points to &heads[0] while h is &heads[2] (an out-of-bound pointer). So n->prev is a struct head and you access a next field of a struct node of it. Changing k to 0 makes the testcase pass (now you don't run into the bogus path).
How do you conclude that n->prev points to &heads[0]? node.prev receives the value (void *)head, where head is initialized to &heads[2]. I cannot see any uses of &heads[0] in the test program.
(In reply to Richard Biener from comment #1) > The testcase is violating strict-aliasing rules as you access a struct head > as struct node here: Agree with ghudson here: n->prev points to &heads[2], not &heads[0]. Although assigning a casted struct head * to a struct node * is arguably sloppy, the standard does not prohibit it, as long as it is never dereferenced in that form.
Another bisect between 4.7 and 4.8 shows that the bug appeared with r189321 (bug 52009). My test case has triggers the bug in more versions than Kerberos does: as far as I can tell, Kerberos was unaffected until r192604.
I've been staring as this test case, and I cannot find any dereference of a wrong-typed pointer value. The only oddity I can find is that at if (n->prev == (void *)h) n == &node, n->prev == (struct node *)&heads[2] (so wrong-typed), h == &heads[2], so there is a '==' being applied to a wrong-typed pointer. Is that undefined behaviour? I'll note that changing the test to if ((void *)n->prev == (void *)h) still reproduces the wrong-code while looking technically Ok. Also, there is no out-of-bounds error.
Equality test against pointer to void is explicitly allowed by the standard and implicitly converts the other pointer to void*.
(In reply to Anders Kaseorg from comment #4) > Another bisect between 4.7 and 4.8 shows that the bug appeared with r189321 > (bug 52009). > > My test case has triggers the bug in more versions than Kerberos does: as > far as I can tell, Kerberos was unaffected until r192604. Thanks - that pin-points it. tail-merging concludes that <bb 3>: _11 = n_7->next; MEM[(struct head *)_10].first = _11; goto <bb 5>; and <bb 4>: _13 = n_7->next; _10->next = _13; are equivalent. But they are not - the stores are performed using different alias sets. Note that the actual miscompile happens during RTL instruction scheduling. In 4.9 and trunk tail-merging is faced with <bb 3>: _11 = n_7->next; MEM[(struct head *)&heads][k.1_8].first = _11; goto <bb 5>; <bb 4>: _13 = n_7->next; _10->next = _13; instead but I bet the issue is still there. So it simply does (on the 4.8 branch): case GIMPLE_ASSIGN: lhs1 = gimple_get_lhs (s1); lhs2 = gimple_get_lhs (s2); if (TREE_CODE (lhs1) != SSA_NAME && TREE_CODE (lhs2) != SSA_NAME) return (vn_valueize (gimple_vdef (s1)) == vn_valueize (gimple_vdef (s2))); which shows that we value-number the VDEFs the same. IMHO VDEF value-numbering is dangerous here. I have a patch.
Using this patch on the example from the description field, I can modify the example on the command line: ... $ diff -u bug-orig.c bug-mod.c --- bug-orig.c 2014-07-31 14:00:50.663275717 +0200 +++ bug-mod.c 2014-07-31 14:01:49.403276412 +0200 @@ -11,7 +11,7 @@ struct node *n = head->first; struct head *h = &heads[k]; - if (n->prev == (void *)h) + if (FORCE n->prev == (void *)h) h->first = n->next; else n->prev->next = n->next; ... 1. -DFORCE="" gives the original 2. -DFORCE="1 ||" forces the condition to true 3. -DFORCE="0 &&" forces the confition to false In this experiment, we don't use tree-tail-merge: ... $ gcc -DFORCE="1 ||" bug-mod.c -O2 -fno-strict-aliasing -fno-tree-tail-merge && ./a.out ; echo $? 0 $ gcc -DFORCE="1 ||" bug-mod.c -O2 -fstrict-aliasing -fno-tree-tail-merge && ./a.out ; echo $? 0 $ gcc -DFORCE="0 &&" bug-mod.c -O2 -fno-strict-aliasing -fno-tree-tail-merge && ./a.out ; echo $? 0 $ gcc -DFORCE="0 &&" bug-mod.c -O2 -fstrict-aliasing -fno-tree-tail-merge && ./a.out ; echo $? 1 ... The last result seems to suggest that the example is not type-safe. My understanding is that the problem is in the line: n->prev->next = n->next; where we effectively do: /* ((struct node*)&heads[2])->next = node.next */ which is type-unsafe.
On Thu, 31 Jul 2014, vries at gcc dot gnu.org wrote: > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964 > > vries at gcc dot gnu.org changed: > > What |Removed |Added > ---------------------------------------------------------------------------- > CC| |vries at gcc dot gnu.org > > --- Comment #8 from vries at gcc dot gnu.org --- > Using this patch on the example from the description field, I can modify the > example on the command line: > ... > $ diff -u bug-orig.c bug-mod.c > --- bug-orig.c 2014-07-31 14:00:50.663275717 +0200 > +++ bug-mod.c 2014-07-31 14:01:49.403276412 +0200 > @@ -11,7 +11,7 @@ > struct node *n = head->first; > struct head *h = &heads[k]; > > - if (n->prev == (void *)h) > + if (FORCE n->prev == (void *)h) > h->first = n->next; > else > n->prev->next = n->next; > ... > > 1. -DFORCE="" gives the original > 2. -DFORCE="1 ||" forces the condition to true > 3. -DFORCE="0 &&" forces the confition to false > > In this experiment, we don't use tree-tail-merge: > ... > $ gcc -DFORCE="1 ||" bug-mod.c -O2 -fno-strict-aliasing -fno-tree-tail-merge && > ./a.out ; echo $? > 0 > $ gcc -DFORCE="1 ||" bug-mod.c -O2 -fstrict-aliasing -fno-tree-tail-merge && > ./a.out ; echo $? > 0 > $ gcc -DFORCE="0 &&" bug-mod.c -O2 -fno-strict-aliasing -fno-tree-tail-merge && > ./a.out ; echo $? > 0 > $ gcc -DFORCE="0 &&" bug-mod.c -O2 -fstrict-aliasing -fno-tree-tail-merge && > ./a.out ; echo $? > 1 > ... > > The last result seems to suggest that the example is not type-safe. > > My understanding is that the problem is in the line: > n->prev->next = n->next; > where we effectively do: > /* ((struct node*)&heads[2])->next = node.next */ > which is type-unsafe. But that line is never executed at runtime (well, unless tail merging comes along and makes it the only version present). Richard.
Author: rguenth Date: Thu Jul 31 14:06:59 2014 New Revision: 213375 URL: https://gcc.gnu.org/viewcvs?rev=213375&root=gcc&view=rev Log: 2014-07-31 Richard Biener <rguenther@suse.de> PR tree-optimization/61964 * tree-ssa-tail-merge.c (gimple_equal_p): Handle non-SSA LHS solely by structural equality. * gcc.dg/torture/pr61964.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/torture/pr61964.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-tail-merge.c
Fixed on trunk sofar.
Created attachment 33220 [details] Alternative patch > But that line is never executed at runtime (well, unless tail > merging comes along and makes it the only version present). Ah, right, we consider a program with dead type-unsafe code valid. This follow-up patch attempts to fix things less conservatively on trunk. Shall I put this through testing or do you see a problem with this approach? Furthermore, I suspect that a similar issue exists for loads, I'll look into that.
(In reply to vries from comment #12) > Created attachment 33220 [details] > Alternative patch > > > But that line is never executed at runtime (well, unless tail > > merging comes along and makes it the only version present). > > Ah, right, we consider a program with dead type-unsafe code valid. > > This follow-up patch attempts to fix things less conservatively on trunk. > Shall I put this through testing or do you see a problem with this approach? Hum. I don't like guarding optimizations with !flag_strict_aliasing, that is, -fno-strict-aliasing shouldn't get us more optimization. Also on trunk I'd like to rip out the use of the SCCVN lattice from tail-merging as there FRE/PRE value-replace every SSA name which means we don't need it. The tight entanglement between PRE and tail-merge has given me more headaches recently. > Furthermore, I suspect that a similar issue exists for loads, I'll look into > that. I don't think so.
Author: rguenth Date: Fri Aug 1 07:36:16 2014 New Revision: 213404 URL: https://gcc.gnu.org/viewcvs?rev=213404&root=gcc&view=rev Log: 2014-08-01 Richard Biener <rguenther@suse.de> PR tree-optimization/61964 * tree-ssa-tail-merge.c (gimple_equal_p): Handle non-SSA LHS solely by structural equality. * gcc.dg/torture/pr61964.c: New testcase. * gcc.dg/pr51879-18.c: XFAIL. Added: branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/torture/pr61964.c Modified: branches/gcc-4_9-branch/gcc/ChangeLog branches/gcc-4_9-branch/gcc/testsuite/ChangeLog branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/pr51879-18.c branches/gcc-4_9-branch/gcc/tree-ssa-tail-merge.c
Author: rguenth Date: Fri Aug 1 07:40:01 2014 New Revision: 213405 URL: https://gcc.gnu.org/viewcvs?rev=213405&root=gcc&view=rev Log: 2014-08-01 Richard Biener <rguenther@suse.de> PR tree-optimization/61964 * tree-ssa-tail-merge.c (gimple_operand_equal_value_p): New function merged from trunk. (gimple_equal_p): Handle non-SSA LHS solely by structural equality. * gcc.dg/torture/pr61964.c: New testcase. * gcc.dg/pr51879-18.c: XFAIL. Added: branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/torture/pr61964.c Modified: branches/gcc-4_8-branch/gcc/ChangeLog branches/gcc-4_8-branch/gcc/testsuite/ChangeLog branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/pr51879-18.c branches/gcc-4_8-branch/gcc/tree-ssa-tail-merge.c
Fixed.
Thanks. I verified that GCC 4.8 r213405 fixes my test case and the original Kerberos problem.
(In reply to Richard Biener from comment #13) > (In reply to vries from comment #12) > > Furthermore, I suspect that a similar issue exists for loads, I'll look into > > that. > > I don't think so. How about PR62004 ?