[Bug tree-optimization/61964] New: [4.8 regression] krb5 database propagation enters infinite loop; reduced test case

[Bug tree-optimization/61964] New: [4.8 regression] krb5 database propagation enters infinite loop; reduced test case

[andersk at mit dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

            Bug ID: 61964
           Summary: [4.8 regression] krb5 database propagation enters
                    infinite loop; reduced test case
           Product: gcc
           Version: 4.8.3
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: andersk at mit dot edu

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).
>From gcc-bugs-return-457388-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Jul 30 13:39:45 2014
Return-Path: <gcc-bugs-return-457388-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 26090 invoked by alias); 30 Jul 2014 13:39:45 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 26061 invoked by uid 48); 30 Jul 2014 13:39:40 -0000
From: "rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/61964] [4.8 regression] krb5 database propagation enters infinite loop; reduced test case
Date: Wed, 30 Jul 2014 13:39:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 4.8.3
X-Bugzilla-Keywords:
X-Bugzilla-Severity: major
X-Bugzilla-Who: rguenth at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: cf_known_to_work cf_known_to_fail
Message-ID: <bug-61964-4-Ldd9IwreIh@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-61964-4@http.gcc.gnu.org/bugzilla/>
References: <bug-61964-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-07/txt/msg01979.txt.bz2
Content-length: 836

https://gcc.gnu.org/bugzilla/show_bug.cgi?ida964

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|4.7.4, 4.9.0                |
      Known to fail|4.8.3                       |

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
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).

[Bug tree-optimization/61964] [4.8 regression] krb5 database propagation enters infinite loop; reduced test case

[ghudson at mit dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

ghudson at mit dot edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ghudson at mit dot edu

--- Comment #2 from ghudson at mit dot edu ---
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.

[Bug tree-optimization/61964] [4.8 regression] krb5 database propagation enters infinite loop; reduced test case

[andersk at mit dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #3 from Anders Kaseorg <andersk at mit dot edu> ---
(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.

[Bug tree-optimization/61964] [4.8 regression] krb5 database propagation enters infinite loop; reduced test case

[andersk at mit dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #4 from Anders Kaseorg <andersk at mit dot edu> ---
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.

[Bug tree-optimization/61964] [4.8 regression] krb5 database propagation enters infinite loop; reduced test case

[mikpelinux at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

Mikael Pettersson <mikpelinux at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mikpelinux at gmail dot com

--- Comment #5 from Mikael Pettersson <mikpelinux at gmail dot com> ---
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.

[Bug tree-optimization/61964] [4.8 regression] krb5 database propagation enters infinite loop; reduced test case

[schwab@linux-m68k.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #6 from Andreas Schwab <schwab@linux-m68k.org> ---
Equality test against pointer to void is explicitly allowed by the standard and
implicitly converts the other pointer to void*.

[Bug tree-optimization/61964] [4.8/4.9/4.10 regression] krb5 database propagation enters infinite loop; reduced test case

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
           Keywords|                            |wrong-code
   Last reconfirmed|                            |2014-07-31
                 CC|                            |tom at codesourcery dot com
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
     Ever confirmed|0                           |1
            Summary|[4.8 regression] krb5       |[4.8/4.9/4.10 regression]
                   |database propagation enters |krb5 database propagation
                   |infinite loop; reduced test |enters infinite loop;
                   |case                        |reduced test case
   Target Milestone|---                         |4.8.4

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
(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.

[Bug tree-optimization/61964] [4.8/4.9/4.10 regression] krb5 database propagation enters infinite loop; reduced test case

[vries at gcc dot gnu.org]

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.

[Bug tree-optimization/61964] [4.8/4.9/4.10 regression] krb5 database propagation enters infinite loop; reduced test case

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #9 from rguenther at suse dot de <rguenther at suse dot de> ---
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.

[Bug tree-optimization/61964] [4.8/4.9/4.10 regression] krb5 database propagation enters infinite loop; reduced test case

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
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

[Bug tree-optimization/61964] [4.8/4.9 regression] krb5 database propagation enters infinite loop; reduced test case

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.10.0
            Summary|[4.8/4.9/4.10 regression]   |[4.8/4.9 regression] krb5
                   |krb5 database propagation   |database propagation enters
                   |enters infinite loop;       |infinite loop; reduced test
                   |reduced test case           |case

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.

[Bug tree-optimization/61964] [4.8/4.9 regression] krb5 database propagation enters infinite loop; reduced test case

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #12 from vries at gcc dot gnu.org ---
Created attachment 33220
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=33220&action=edit
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.

[Bug tree-optimization/61964] [4.8/4.9 regression] krb5 database propagation enters infinite loop; reduced test case

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
(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.

[Bug tree-optimization/61964] [4.8/4.9 regression] krb5 database propagation enters infinite loop; reduced test case

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
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

[Bug tree-optimization/61964] [4.8/4.9 regression] krb5 database propagation enters infinite loop; reduced test case

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
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

[Bug tree-optimization/61964] [4.8/4.9 regression] krb5 database propagation enters infinite loop; reduced test case

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |4.8.4, 4.9.2
         Resolution|---                         |FIXED
      Known to fail|                            |4.8.3

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.

[Bug tree-optimization/61964] [4.8/4.9 regression] krb5 database propagation enters infinite loop; reduced test case

[andersk at mit dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #17 from Anders Kaseorg <andersk at mit dot edu> ---
Thanks.  I verified that GCC 4.8 r213405 fixes my test case and the original
Kerberos problem.

[Bug tree-optimization/61964] [4.8/4.9 regression] krb5 database propagation enters infinite loop; reduced test case

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964

--- Comment #18 from vries at gcc dot gnu.org ---
(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 ?

[Bug tree-optimization/61964] [4.8/4.9 regression] krb5 database propagation enters infinite loop; reduced test case

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964
Bug 61964 depends on bug 62030, which changed state.

Bug 62030 Summary: wrong code due to ifcvt merging two stores which have different aliasing sets
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62030

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED