Bug 59358 - [4.8/4.9 Regression] Infinite loop generated with >=O2
Summary: [4.8/4.9 Regression] Infinite loop generated with >=O2
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.8.2
: P3 normal
Target Milestone: 4.8.3
Assignee: Jakub Jelinek
URL:
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2013-12-01 07:37 UTC by Jérôme Carretero
Modified: 2013-12-03 07:30 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2013-12-01 00:00:00


Attachments
gcc49-pr59358.patch (790 bytes, patch)
2013-12-02 13:08 UTC, Jakub Jelinek
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Jérôme Carretero 2013-12-01 07:37:04 UTC
So, we have the following code:

void *lst_realloc(void *, int);
 
typedef struct smartlist_t {
 void **list;
 int num_used;
 int capacity;
} smartlist_t;
 
#define MAX_CAPACITY 32

void smartlist_ensure_capacity(smartlist_t *sl, int size) {
	if (size > sl->capacity) {
		int higher = sl->capacity;
		if (size > (int)MAX_CAPACITY/2) {
			higher = MAX_CAPACITY;
		}
		else {
			while (size > higher) {
				higher *= 2;
			}
		}
		sl->capacity = higher;
		sl->list = lst_realloc(sl->list, sl->capacity);
	}
}

Compiling that:
$ x86_64-pc-linux-gnu-gcc-4.8.2 -Os -S -o test.s test.c

Gives:

	pushq	%rbx
	cmpl	12(%rdi), %esi
	movq	%rdi, %rbx
	jle	.L1
	cmpl	$16, %esi
	jg	.L3
.L4:
	jmp	.L4 <----- unexpected infinite loop if size <= capacity/2
.L3:
	movl	$32, 12(%rdi)
	movq	(%rdi), %rdi
	movl	$32, %esi
	call	lst_realloc
	movq	%rax, (%rbx)
.L1:
	popq	%rbx
	ret

Originally from the smartlist_ensure_capacity() function from TOR:
https://gitweb.torproject.org/tor.git/blob/e65b54ec75e3c9e9ada33c8f3ee868d1bea167f5:/src/common/container.c#l61
TOR bug: https://trac.torproject.org/projects/tor/ticket/10259

Reduced by o11c (https://gist.github.com/o11c/7729355) and got help from pinskia.
Comment 1 Marc Glisse 2013-12-01 12:12:44 UTC
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.
Comment 2 Jakub Jelinek 2013-12-02 11:07:48 UTC
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;
}
Comment 3 Jakub Jelinek 2013-12-02 11:11:30 UTC
Started with r188776 or r188780.
Comment 4 Richard Biener 2013-12-02 12:42:55 UTC
I will have a looksee.
Comment 5 Jakub Jelinek 2013-12-02 13:08:57 UTC
Created attachment 31350 [details]
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.
Comment 6 Richard Biener 2013-12-02 13:10:58 UTC
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).
Comment 7 Jakub Jelinek 2013-12-02 22:41:25 UTC
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
Comment 8 Jakub Jelinek 2013-12-02 22:44:07 UTC
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
Comment 9 Jakub Jelinek 2013-12-02 23:12:48 UTC
Fixed.
Comment 10 Jakub Jelinek 2013-12-03 07:30:50 UTC
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