public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2
       [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
@ 2013-12-01 12:12 ` glisse at gcc dot gnu.org
  2013-12-02 11:07 ` jakub at gcc dot gnu.org
                   ` (8 subsequent siblings)
  9 siblings, 0 replies; 10+ messages in thread
From: glisse at gcc dot gnu.org @ 2013-12-01 12:12 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59358

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-12-01
          Component|c                           |tree-optimization
   Target Milestone|---                         |4.8.3
            Summary|Infinite loop generated     |[4.8/4.9 Regression]
                   |with >=O2                   |Infinite loop generated
                   |                            |with >=O2
     Ever confirmed|0                           |1
           Severity|major                       |normal

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
void smartlist_ensure_capacity(int *capacity, int size) {
  int higher = *capacity;
  if (size > higher) {
    if (size <= 16) {
      while (size > higher) {
    higher *= 2;
      }
    }
  }
}

compiled with -O2, VRP1 seems guilty.


^ permalink raw reply	[flat|nested] 10+ messages in thread
* [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2
       [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
  2013-12-01 12:12 ` [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2 glisse at gcc dot gnu.org
@ 2013-12-02 11:07 ` jakub at gcc dot gnu.org
  2013-12-02 11:11 ` jakub at gcc dot gnu.org
                   ` (7 subsequent siblings)
  9 siblings, 0 replies; 10+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-12-02 11:07 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59358

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Full runtime testcase:
__attribute__((noinline, noclone)) int
foo (int *x, int y)
{
  int z = *x;
  if (y > z && y <= 16)
    while (y > z)
      z *= 2;
  return z;
}

int
main ()
{
  int i;
  for (i = 1; i < 17; i++)
    {
      int j = foo (&i, 16);
      int k;
      if (i >= 8 && i <= 15)
        k = 16 + (i - 8) * 2;
      else if (i >= 4 && i <= 7)
        k = 16 + (i - 4) * 4;
      else if (i == 3)
        k = 24;
      else
        k = 16;
      if (j != k)
        __builtin_abort ();
      j = foo (&i, 7);
      if (i >= 7)
        k = i;
      else if (i >= 4)
        k = 8 + (i - 4) * 2;
      else if (i == 3)
        k = 12;
      else
        k = 8;
      if (j != k)
        __builtin_abort ();
    }
  return 0;
}


^ permalink raw reply	[flat|nested] 10+ messages in thread
* [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2
       [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
  2013-12-01 12:12 ` [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2 glisse at gcc dot gnu.org
  2013-12-02 11:07 ` jakub at gcc dot gnu.org
@ 2013-12-02 11:11 ` jakub at gcc dot gnu.org
  2013-12-02 12:42 ` rguenth at gcc dot gnu.org
                   ` (6 subsequent siblings)
  9 siblings, 0 replies; 10+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-12-02 11:11 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59358

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r188776 or r188780.


^ permalink raw reply	[flat|nested] 10+ messages in thread
* [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2
       [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
                   ` (2 preceding siblings ...)
  2013-12-02 11:11 ` jakub at gcc dot gnu.org
@ 2013-12-02 12:42 ` rguenth at gcc dot gnu.org
  2013-12-02 13:09 ` jakub at gcc dot gnu.org
                   ` (5 subsequent siblings)
  9 siblings, 0 replies; 10+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-12-02 12:42 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59358

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a looksee.


^ permalink raw reply	[flat|nested] 10+ messages in thread
* [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2
       [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
                   ` (3 preceding siblings ...)
  2013-12-02 12:42 ` rguenth at gcc dot gnu.org
@ 2013-12-02 13:09 ` jakub at gcc dot gnu.org
  2013-12-02 13:11 ` rguenth at gcc dot gnu.org
                   ` (4 subsequent siblings)
  9 siblings, 0 replies; 10+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-12-02 13:09 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59358

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|rguenth at gcc dot gnu.org         |jakub at gcc dot gnu.org

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 31350
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31350&action=edit
gcc49-pr59358.patch

Untested fix.  The problem is with:
Meeting
  [-INF, y_5(D) + -1]  EQUIVALENCES: { z_4 } (1 elements)
and
  [-INF(OVF), 30]
to
  [-INF(OVF), y_5(D) + -1]  EQUIVALENCES: { } (0 elements)
Found new range for z_1: [-INF(OVF), y_5(D) + -1]

Because one of the maximum is symbolic, y_5(D) + -1 and 30 are effectively
uncomparable (operand_less_p doesn't return 1 for either order of those).
Apparently union_ranges implicitly assumes certain ordering based on earlier
tests, like from
  else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
           && (mineq || operand_less_p (*vr0min, vr1min) == 1))
being false it assumes that if
  else if ((operand_less_p (vr1min, *vr0max) == 1
            || operand_equal_p (vr1min, *vr0max, 0))
           && operand_less_p (*vr0min, vr1min) == 1
is true then operand_less_p (*vr0max, vr1max) == 1, but that is not guaranteed.


^ permalink raw reply	[flat|nested] 10+ messages in thread
* [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2
       [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
                   ` (4 preceding siblings ...)
  2013-12-02 13:09 ` jakub at gcc dot gnu.org
@ 2013-12-02 13:11 ` rguenth at gcc dot gnu.org
  2013-12-02 22:41 ` jakub at gcc dot gnu.org
                   ` (3 subsequent siblings)
  9 siblings, 0 replies; 10+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-12-02 13:11 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59358

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Meeting
  [-INF, y_6(D) + -1]  EQUIVALENCES: { z_5 } (1 elements)
and
  [-INF(OVF), 30]
to
  [-INF(OVF), y_6(D) + -1]  EQUIVALENCES: { } (0 elements)
Found new range for z_1: [-INF(OVF), y_6(D) + -1]

is obviously wrong.  We run into

  else if ((operand_less_p (*vr0min, vr1max) == 1
            || operand_equal_p (*vr0min, vr1max, 0))
           && operand_less_p (vr1min, *vr0min) == 1)
    {
      /* (  [  )  ] or (   )[   ] */
      if (*vr0type == VR_RANGE
          && vr1type == VR_RANGE)
        *vr0min = vr1min;

where -INF < 30 and -INF(OVF) < -INF.  But we have vr0max and vr1max unordered.

Thus we fail to verify that, assuming we've catched this case via

  else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
           && (mineq || operand_less_p (*vr0min, vr1min) == 1))
    {
      /* [ (  ) ] or [(  ) ] or [ (  )] */
...
  else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
           && (mineq || operand_less_p (vr1min, *vr0min) == 1))
    {
      /* ( [  ] ) or ([  ] ) or ( [  ]) */

Fixing that does

Meeting
  [-INF, y_6(D) + -1]  EQUIVALENCES: { z_5 } (1 elements)
and
  [-INF(OVF), 30]
to
  VARYING

optimally we'd be able to extract a conservative integer range from
the symbolic range - [-INF, +INF - 1] in this case - and meet them
to [-INF(OVF), +INF - 1] (assuming that y_6 did not overflow).


^ permalink raw reply	[flat|nested] 10+ messages in thread
* [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2
       [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
                   ` (5 preceding siblings ...)
  2013-12-02 13:11 ` rguenth at gcc dot gnu.org
@ 2013-12-02 22:41 ` jakub at gcc dot gnu.org
  2013-12-02 22:44 ` jakub at gcc dot gnu.org
                   ` (2 subsequent siblings)
  9 siblings, 0 replies; 10+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-12-02 22:41 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59358

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Mon Dec  2 22:41:23 2013
New Revision: 205607

URL: http://gcc.gnu.org/viewcvs?rev=205607&root=gcc&view=rev
Log:
    PR tree-optimization/59358
    * tree-vrp.c (union_ranges): To check for the partially
    overlapping ranges or adjacent ranges, also compare *vr0max
    with vr1max.

    * gcc.c-torture/execute/pr59358.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr59358.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c


^ permalink raw reply	[flat|nested] 10+ messages in thread
* [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2
       [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
                   ` (6 preceding siblings ...)
  2013-12-02 22:41 ` jakub at gcc dot gnu.org
@ 2013-12-02 22:44 ` jakub at gcc dot gnu.org
  2013-12-02 23:12 ` jakub at gcc dot gnu.org
  2013-12-03  7:30 ` jakub at gcc dot gnu.org
  9 siblings, 0 replies; 10+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-12-02 22:44 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59358

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Mon Dec  2 22:44:05 2013
New Revision: 205608

URL: http://gcc.gnu.org/viewcvs?rev=205608&root=gcc&view=rev
Log:
    PR tree-optimization/59358
    * tree-vrp.c (union_ranges): To check for the partially
    overlapping ranges or adjacent ranges, also compare *vr0max
    with vr1max.

    * gcc.c-torture/execute/pr59358.c: New test.

Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-vrp.c


^ permalink raw reply	[flat|nested] 10+ messages in thread
* [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2
       [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
                   ` (7 preceding siblings ...)
  2013-12-02 22:44 ` jakub at gcc dot gnu.org
@ 2013-12-02 23:12 ` jakub at gcc dot gnu.org
  2013-12-03  7:30 ` jakub at gcc dot gnu.org
  9 siblings, 0 replies; 10+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-12-02 23:12 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59358

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.


^ permalink raw reply	[flat|nested] 10+ messages in thread
* [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2
       [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
                   ` (8 preceding siblings ...)
  2013-12-02 23:12 ` jakub at gcc dot gnu.org
@ 2013-12-03  7:30 ` jakub at gcc dot gnu.org
  9 siblings, 0 replies; 10+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-12-03  7:30 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59358

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Tue Dec  3 07:30:48 2013
New Revision: 205619

URL: http://gcc.gnu.org/viewcvs?rev=205619&root=gcc&view=rev
Log:
    PR tree-optimization/59358
    * tree-vrp.c (union_ranges): To check for the partially
    overlapping ranges or adjacent ranges, also compare *vr0max
    with vr1max.

    * gcc.c-torture/execute/pr59358.c: New test.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/gcc.c-torture/execute/pr59358.c


^ permalink raw reply	[flat|nested] 10+ messages in thread
end of thread, other threads:[~2013-12-03  7:30 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <bug-59358-4@http.gcc.gnu.org/bugzilla/>
2013-12-01 12:12 ` [Bug tree-optimization/59358] [4.8/4.9 Regression] Infinite loop generated with >=O2 glisse at gcc dot gnu.org
2013-12-02 11:07 ` jakub at gcc dot gnu.org
2013-12-02 11:11 ` jakub at gcc dot gnu.org
2013-12-02 12:42 ` rguenth at gcc dot gnu.org
2013-12-02 13:09 ` jakub at gcc dot gnu.org
2013-12-02 13:11 ` rguenth at gcc dot gnu.org
2013-12-02 22:41 ` jakub at gcc dot gnu.org
2013-12-02 22:44 ` jakub at gcc dot gnu.org
2013-12-02 23:12 ` jakub at gcc dot gnu.org
2013-12-03  7:30 ` jakub at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).