Bug 61964

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 ?