[4.8/4.9 Regression] Infinite loop generated with >=O2

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.

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.

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;
}

Started with r188776 or r188780.

I will have a looksee.

Created attachment 31350
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.

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).

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

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

Fixed.

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