[Bug tree-optimization/17552] New: Infinite recursion in analyze_scalar_evolution

[Bug tree-optimization/17552] New: Infinite recursion in analyze_scalar_evolution

[jakub at gcc dot gnu dot org]

/* { dg-do compile } */
/* { dg-options "-Os" } */

typedef __SIZE_TYPE__ size_t;

struct S1
{
  void *s1a;
  void **s1b;
};

struct S2
{
  void *s2a;
  unsigned int s2b;
  struct S1 *s2c;
};

extern void *memset (void *__s, int __c, size_t __n);
extern void *fn1 (void *, void *);
void fn2 (unsigned long *);
void *fn3 (void *, size_t);
extern int fn4 (void *, void *);

static int
f1 (struct S2 *x, unsigned int y)
{
  register struct S1 *t;
  unsigned int v;
  struct S1 *w;

  if (y >= x->s2b)
    {
      v = x->s2b;
      if (v == 0)
        v = 4;
      while (y >= v)
        v *= 2;
      x->s2c = ((struct S1 *) fn3 (x->s2c, v * sizeof *x->s2c));
      memset (x->s2c + x->s2b, 0,
              (v - x->s2b) * sizeof *x->s2c);
      w = x->s2c + v;
      for (t = x->s2c + x->s2b; t < w; t++)
        t->s1a = 0;
      x->s2b = v;
    }
  return 1;
}

int
test (struct S2 *x, const unsigned char **y)
{
  unsigned char u;

  u = **y;
  ++*y;
  if (u == 4)
    {
      unsigned long k;
      void *l;

      fn2 (&k);
      k -= 256;
      if (!f1 (x, k))
        return 0;
      l = x->s2c[k].s1a;
      if (fn4 (x->s2a, l) == 10)
        l = fn1 (x->s2a, l);
    }
  return 1;
}

causes segfault on x86-64 at -Os, apparently because of infinite recursion
eats all of stack.
#0  0x0000000000957153 in eq_scev_info (e1=Cannot access memory at address
0x7fbf3ffff8
) at ../../gcc/tree-scalar-evolution.c:317
#1  0x0000000000a0719a in htab_find_slot_with_hash (htab=0xd364d0,
element=0x7fbf400070, hash=104, insert=INSERT)
    at ../../libiberty/hashtab.c:660
#2  0x00000000009571c2 in find_var_scev_info (var=0x2a97d80be0) at
../../gcc/tree-scalar-evolution.c:344
#3  0x0000000000958351 in get_scalar_evolution (scalar=0x2a97d80be0) at
../../gcc/tree-scalar-evolution.c:655
#4  0x000000000095c558 in analyze_scalar_evolution (loop=0xd34e30,
var=0x2a97d80be0) at ../../gcc/tree-scalar-evolution.c:1913
#5  0x000000000095c00a in interpret_rhs_modify_expr (loop=0xd34e30,
opnd1=0x2a97d7c370, type=0x2a97c0ba80)
    at ../../gcc/tree-scalar-evolution.c:1757
#6  0x000000000095c433 in analyze_scalar_evolution_1 (loop=0xd34e30,
var=0x2a97d8a320, res=0x0)
    at ../../gcc/tree-scalar-evolution.c:1856
#7  0x000000000095c568 in analyze_scalar_evolution (loop=0xd34e30,
var=0x2a97d8a320) at ../../gcc/tree-scalar-evolution.c:1913
#8  0x000000000095b96e in interpret_condition_phi (loop=0xd34e30,
condition_phi=0x2a97c0d800)
    at ../../gcc/tree-scalar-evolution.c:1700
#9  0x000000000095c466 in analyze_scalar_evolution_1 (loop=0xd34e30,
var=0x2a97d899b0, res=0x0)
    at ../../gcc/tree-scalar-evolution.c:1863
#10 0x000000000095c568 in analyze_scalar_evolution (loop=0xd34e30,
var=0x2a97d899b0) at ../../gcc/tree-scalar-evolution.c:1913
#11 0x000000000095b96e in interpret_condition_phi (loop=0xd34e30,
condition_phi=0x2a97c0da00)
    at ../../gcc/tree-scalar-evolution.c:1700

-- 
           Summary: Infinite recursion in analyze_scalar_evolution
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: jakub at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org
GCC target triplet: x86_64-redhat-linux


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

[Bug tree-optimization/17552] Infinite recursion in analyze_scalar_evolution

[arjanv at redhat dot com]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |arjanv at redhat dot com


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

[Bug tree-optimization/17552] [4.0 Regression] Infinite recursion in analyze_scalar_evolution

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |spop at gcc dot gnu dot org
  BugsThisDependsOn|                            |17520
           Keywords|                            |compile-time-hog
            Summary|Infinite recursion in       |[4.0 Regression] Infinite
                   |analyze_scalar_evolution    |recursion in
                   |                            |analyze_scalar_evolution
   Target Milestone|---                         |4.0.0


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

[Bug tree-optimization/17552] [4.0 Regression] Infinite recursion in analyze_scalar_evolution

[reichelt at gcc dot gnu dot org]

------- Additional Comments From reichelt at gcc dot gnu dot org  2004-09-20 02:28 -------
Here's a reduced testcase.

======================================
void foo()
{
    int i, j, k;

    if (k > i)
    {
        j = i;
        if (j) j++;
        while (k >= j) j++;
        for (k = i; k < j; k++) ;
    }
}
======================================

Most probably a duplicate of PR 17560.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |reichelt at gcc dot gnu dot
                   |                            |org
  BugsThisDependsOn|                            |17560
           Severity|normal                      |critical
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
           Keywords|                            |monitored
   Last reconfirmed|0000-00-00 00:00:00         |2004-09-20 02:28:00
               date|                            |


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

[Bug tree-optimization/17552] [4.0 Regression] Infinite recursion in analyze_scalar_evolution

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-09-27 20:57 -------
This is not fixed by the patch which fixes PR 17520.

-- 


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

[Bug tree-optimization/17552] [4.0 Regression] Infinite recursion in analyze_scalar_evolution

[jgrimm2 at us dot ibm dot com]

------- Additional Comments From jgrimm2 at us dot ibm dot com  2004-10-07 19:15 -------
FWIW, I've reproduced this on linux ppc64 (both -m32 & -m64) too. Besides seeing
with the testcase, I believe I"m seeing in the wild when building busybox
(1.00rc3).  

Looking at the sc-ev code (woefully ignorant of scalar evolution & details of
its implementation): 

Is there a need for some check over in analyze_scalar_1()? I see the same cycle
of vars getting looked at again and again. 

---------- test.c.t26.tailr---------------
;; Function foo (foo)

foo ()
{
  int k;
  int j;
  int i;

<bb 0>:
  if (k_3 > i_4) goto <L0>; else goto <L8>;

<L0>:;
  if (i_4 != 0) goto <L1>; else goto <L3>;

<L1>:;
  j_9 = i_4 + 1;
  goto <bb 4> (<L4>);

  # j_12 = PHI <i_4(1), j_11(4)>;
<L3>:;
  j_8 = j_12 + 1;

  # j_11 = PHI <j_9(2), j_8(3)>;
<L4>:;
  if (k_3 >= j_11) goto <L3>; else goto <L7>;

<L6>:;
  k_7 = k_1 + 1;

  # k_1 = PHI <i_4(4), k_7(5)>;
<L7>:;

<L8>:;
  return;

}
--------- end test.c.t26.tailr --------------



--------- excerpt from dump --------------
....
....
(instantiate_parameters
  (loop_nb = 1)
  (chrec = j_11 == -2147483648)
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = j_11)
(get_scalar_evolution
  (scalar = j_11)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = j_9)
(get_scalar_evolution
  (scalar = j_9)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = i_4)
(get_scalar_evolution
  (scalar = i_4)
  (scalar_evolution = ))
)
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = 1)
(get_scalar_evolution
  (scalar = 1)
  (scalar_evolution = 1))
)
(set_scalar_evolution
  (scalar = j_9)
  (scalar_evolution = i_4 + 1))
)
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = j_8)
 (get_scalar_evolution
  (scalar = j_8)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = j_12)
(get_scalar_evolution
  (scalar = j_12)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = i_4)
(get_scalar_evolution
  (scalar = i_4)
  (scalar_evolution = ))
)
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = j_11)
(get_scalar_evolution
  (scalar = j_11)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = j_9)
(get_scalar_evolution
  (scalar = j_9)
  (scalar_evolution = i_4 + 1))
(set_scalar_evolution
  (scalar = j_9)
  (scalar_evolution = i_4 + 1))
)
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = j_8)
(get_scalar_evolution
  (scalar = j_8)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = j_12)

..... and keeps cycling through the same vars ..........


Posting in case this triggers an A-HA in folks that understand this code and
theories that back it.  Please ignore if the above is worthless detail/comments. 

Either way, I'm willing to test any patches to see if affects the busybox compile.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jgrimm2 at us dot ibm dot
                   |                            |com


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

[Bug tree-optimization/17552] [4.0 Regression] Infinite recursion in analyze_scalar_evolution

[sebastian dot pop at cri dot ensmp dot fr]

------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr  2004-10-08 12:24 -------
Subject: Re:  [4.0 Regression] Infinite recursion in analyze_scalar_evolution

Same problem as in PR17560: there is a recursive definition outside
any loop, "j_12 -> j_11 -> j_8 -> j_12".  Here is the IR with loop
structures that scev has to analyze.

loop_0
{
  bb_0 (preds = {bb_-1}, succs = {bb_0bb_0})
  {
  <bb 0>:
    if (k_3 > i_4) goto <L0>; else goto <L8>;

  }
  bb_1 (preds = {bb_0}, succs = {bb_1bb_1})
  {
  <L0>:;
    if (i_4 != 0) goto <L1>; else goto <L3>;

  }
  bb_2 (preds = {bb_1}, succs = {bb_2})
  {
  <L1>:;
    j_9 = i_4 + 1;
    goto <bb 4> (<L4>);

  }
  bb_3 (preds = {bb_1bb_4}, succs = {bb_3})
  {
    # j_12 = PHI <i_4(1), j_11(4)>;
  <L3>:;
    j_8 = j_12 + 1;

  }
  bb_4 (preds = {bb_2bb_3}, succs = {bb_4bb_4})
  {
    # j_11 = PHI <j_9(2), j_8(3)>;
  <L4>:;
    if (k_3 >= j_11) goto <L3>; else goto <L7>;

  }
  bb_7 (preds = {bb_6bb_0}, succs = {bb_7})
  {
  <L8>:;
    return;

  }
  loop_1
  {
    bb_5 (preds = {bb_6}, succs = {bb_5})
    {
    <L6>:;
      k_7 = k_1 + 1;

    }
    bb_6 (preds = {bb_4bb_5}, succs = {bb_6bb_6})
    {
      # k_1 = PHI <i_4(4), k_7(5)>;
    <L7>:;
      if (k_1 < j_11) goto <L6>; else goto <L8>;

    }
  }
}


-- 


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

[Bug tree-optimization/17552] [4.0 Regression] Infinite recursion in analyze_scalar_evolution

[reichelt at gcc dot gnu dot org]

------- Additional Comments From reichelt at gcc dot gnu dot org  2004-10-17 19:16 -------
This is indeed fixed by the patch that fixes PR 17560.

*** This bug has been marked as a duplicate of 17560 ***

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|17560                       |
              nThis|                            |
             Status|NEW                         |RESOLVED
         Resolution|                            |DUPLICATE


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