[Bug middle-end/19698] New: [4.0 regression] Infinite loop in update_life_info

[Bug middle-end/19698] New: [4.0 regression] Infinite loop in update_life_info

[schwab at suse dot de]

The attached test causes the compiler to hang in update_life_info (called from 
rest_of_handle_life) while compiling the FFT function with -O2.

-- 
           Summary: [4.0 regression] Infinite loop in update_life_info
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: schwab at suse dot de
                CC: gcc-bugs at gcc dot gnu dot org
GCC target triplet: ia64-linux


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

[Bug middle-end/19698] [4.0 regression] Infinite loop in update_life_info

[schwab at suse dot de]

------- Additional Comments From schwab at suse dot de  2005-01-29 19:18 -------
Created an attachment (id=8102)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=8102&action=view)
Test case


-- 


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

[Bug middle-end/19698] [4.0 regression] Infinite loop in update_life_info

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog
   Target Milestone|---                         |4.0.0


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

[Bug middle-end/19698] [4.0 regression] Infinite loop in update_life_info

[schwab at suse dot de]

------- Additional Comments From schwab at suse dot de  2005-01-30 02:33 -------
This is broken since the tree-ssa merge. 

-- 


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

[Bug middle-end/19698] [4.0 regression] Infinite loop in update_life_info

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-30 02:43 -------
(In reply to comment #2)
> This is broken since the tree-ssa merge. 

Then this most likely just a latent bug and you can generate a testcase which fails before the tree-ssa 
merge.  I will try to reduce this testcase further and inline more.

-- 


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

[Bug middle-end/19698] [4.0 regression] Infinite loop in update_life_info

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-30 03:30 -------
And here is the interesting part, PRE does not move a redundant expression out of a loop (well it does 
but it is only out of the inner most loop).

Confirmed, reduced testcase, doing -fno-tree-PRE causes us not to create the infinite loop but that is 
because we are not pulling out the redundant expression out of the inner loop:
void FFT(int NumSamples, float *RealOut, float ar1)
{
  int i, j, n;
  int BlockSize, BlockEnd;
  if (NumSamples <= 1)
    __builtin_exit(1);

  i = 0;
  L1:
    RealOut[i] = (RealOut == 0) ? 0.0 : RealOut[i];
    i++;
  if (NumSamples <= i) goto L1;
  
  BlockEnd = 1;
  for (BlockSize = 2; BlockSize <= NumSamples; BlockSize *=2)
  {
    float cm1 = __builtin_cosf(-1.0);
    for (i = 0; i < NumSamples; i += BlockSize)
      for (j = i, n = 0; n < BlockEnd; j++, n++)
	RealOut[j] =  cm1 * ar1;
    BlockEnd = BlockSize;
  }
}


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-01-30 03:30:25
               date|                            |


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

[Bug middle-end/19698] [4.0 regression] Infinite loop in update_life_info

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-30 04:09 -------
This testcase might or might not also cause the problem on before the tree-ssa merge but it is the 
reduced from .optimize tree dump:
void FFT(int NumSamples, float *RealOut, float ar1)
{
  int i5, n, j, i, BlockEnd, BlockSize;
  float pretmp2, cm1;
  i = 0;
  do {
    RealOut[i++] = ar1 ? ar1 : 0.0;
  } while (NumSamples <= i);
  BlockEnd = 1;
  BlockSize = 2;
  do {
    cm1 = __builtin_cosf (-1.0e+0);
    j = 0;
    i5 = 0;
    goto L10;
    while (1) {
      do {
	RealOut[j++] = pretmp2;
      } while (BlockEnd > n++);
      do {
	j = i5 += BlockSize;
	if (NumSamples <= i5)
	{
	  BlockEnd = BlockSize;
	  BlockSize <<= 1;
	  goto L23432;
	}
L10:;
      } while (BlockEnd <= 0);
      pretmp2 = cm1 * ar1;
      n = 0;
    }
    L23432:;
  } while (NumSamples >= BlockSize);
}




-- 


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

[Bug middle-end/19698] [3.3/3.4/4.0 regression] Infinite loop in update_life_info

[schwab at suse dot de]

------- Additional Comments From schwab at suse dot de  2005-01-30 13:47 -------
The test case from comment #5 triggers the bug in all branches since 3.3 (but 
not on the hammer branch).  

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |3.3.6 3.4.4 4.0.0
      Known to work|                            |3.0.4 3.1.2 3.2.3
            Summary|[4.0 regression] Infinite   |[3.3/3.4/4.0 regression]
                   |loop in update_life_info    |Infinite loop in
                   |                            |update_life_info


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

[Bug middle-end/19698] [3.3/3.4/4.0 regression] Infinite loop in update_life_info

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
   Target Milestone|4.0.0                       |3.4.4


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

[Bug middle-end/19698] [3.3/3.4/4.0 regression] Infinite loop in update_life_info

[schwab at suse dot de]

------- Additional Comments From schwab at suse dot de  2005-01-30 22:25 -------
Triggered by this change: 
 
2002-07-05  Roger Sayle  <roger@eyesopen.com> 
 
	PR c++/7099 
	* builtin-attrs.def: Define new attribute lists for use in 
	builtins.def. 
	* builtins.def [DEF_BUILTIN]: Modify to take an additional 
	ATTRS argument, an enumerated value defined in builtin-attrs.def 
	that represents the attribute list for the builtins.  Modify 
	all builtin functions to pass an appropriate attribute list. 
	Specify "abort", "exit", "_exit" and "_Exit" builtins here with 
	their required noreturn attributes. 
	* tree.h (enum_builtin_function): Ignore the additional parameter 
	to DEF_BUILTIN. 
	* builtins.c (built_in_names): Likewise. 
	* c-common.c: (builtin_function_2): Replace the "int noreturn_p" 
	argument with a tree representing the functions attribute list. 
	Pass this "attrs" argument to builtin_function.  No longer handle 
	the noreturn_p processing manually. 
	(built_in_attributes): Move the definitions from builtin-attrs.def 
	before c_common_nodes_and_builtins. 
	(c_common_nodes_and_builtins): Handle the new ATTRS parameter in 
	DEF_BUILTIN, passing it to both builtin_function and the changed 
	builtin_function_2. 
 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |roger at eyesopen dot com


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

[Bug middle-end/19698] [3.3/3.4/4.0 regression] Infinite loop in update_life_info

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-30 23:00 -------
(In reply to comment #7)
> Triggered by this change: 
I think that only added the pure attribute on __builtin_cos.
You might want to try this testcase which shows the problem without a builtin:
float f(float) __attribute__((__pure__));
void FFT(int NumSamples, float *RealOut, float ar1)
{
  int i, j, n;
  int BlockSize, BlockEnd;
  if (NumSamples <= 1)
    return;

  i = 0;
  L1:
    RealOut[i] = (RealOut == 0) ? 0.0 : RealOut[i];
    i++;
  if (NumSamples <= i) goto L1;

  BlockEnd = 1;
  for (BlockSize = 2; BlockSize <= NumSamples; BlockSize *=2)
  {
    float cm1 = f(-1.0);
    for (i = 0; i < NumSamples; i += BlockSize)
      for (j = i, n = 0; n < BlockEnd; j++, n++)
        RealOut[j] =  cm1 * ar1;
    BlockEnd = BlockSize;
  }
}

-- 


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

[Bug middle-end/19698] [3.3/3.4/4.0 regression] Infinite loop in update_life_info

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-30 23:07 -------
(In reply to comment #8)
> (In reply to comment #7)
> > Triggered by this change: 
> I think that only added the pure attribute on __builtin_cos.
> You might want to try this testcase which shows the problem without a builtin:
Obvoiusly I mean the following (which is comment #5 changing __builtin_cos to a function with the 
attribute pure added):
loat f(float) __attribute__((__pure__));
void FFT(int NumSamples, float *RealOut, float ar1)
{
  int i5, n, j, i, BlockEnd, BlockSize;
  float pretmp2, cm1;
  i = 0;
  do {
    RealOut[i++] = ar1 ? ar1 : 0.0;
  } while (NumSamples <= i);
  BlockEnd = 1;
  BlockSize = 2;
  do {
    cm1 = f (-1.0e+0);
    j = 0;
    i5 = 0;
    goto L10;
    while (1) {
      do {
        RealOut[j++] = pretmp2;
      } while (BlockEnd > n++);
      do {
        j = i5 += BlockSize;
        if (NumSamples <= i5)
        {
          BlockEnd = BlockSize;
          BlockSize <<= 1;
          goto L23432;
        }
L10:;
      } while (BlockEnd <= 0);
      pretmp2 = cm1 * ar1;
      n = 0;
    }
    L23432:;
  } while (NumSamples >= BlockSize);
}

-- 


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

[Bug middle-end/19698] Infinite loop in update_life_info

[schwab at suse dot de]

------- Additional Comments From schwab at suse dot de  2005-01-31 00:12 -------
Ok, so this is a _very_ old bug, reproducable even with 3.0. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|roger at eyesopen dot com   |
      Known to fail|3.3.6 3.4.4 4.0.0           |3.0.4 3.1.2 3.2.3 3.3.6
                   |                            |3.4.4 4.0.0
      Known to work|3.0.4 3.1.2 3.2.3           |
            Summary|[3.3/3.4/4.0 regression]    |Infinite loop in
                   |Infinite loop in            |update_life_info
                   |update_life_info            |


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-31 00:15 -------
(In reply to comment #10)
> Ok, so this is a _very_ old bug, reproducable even with 3.0. 
Yes but it still an user visible regression and will most likely show up more and more with the 
optimizations happen on the tree level.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Infinite loop in            |[3.4/4.0 Regression]
                   |update_life_info            |Infinite loop in
                   |                            |update_life_info


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[schwab at suse dot de]

------- Additional Comments From schwab at suse dot de  2005-01-31 00:19 -------
The hammer branch still does not exhibit the problem. 

-- 


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[ebotcazou at gcc dot gnu dot org]

------- Additional Comments From ebotcazou at gcc dot gnu dot org  2005-01-31 07:22 -------
> The hammer branch still does not exhibit the problem. 

Ask Zdenek, he had a patch for this long-standing problem.  I even tried to have
it included in the FSF tree at some point, but failed.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu dot
                   |                            |org


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-31 07:33 -------
You probably mean this patch??? 
http://gcc.gnu.org/ml/gcc-patches/2003-01/msg02059.html 

-- 


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[ebotcazou at gcc dot gnu dot org]

------- Additional Comments From ebotcazou at gcc dot gnu dot org  2005-01-31 07:38 -------
> You probably mean this patch??? 
> http://gcc.gnu.org/ml/gcc-patches/2003-01/msg02059.html 

Yep.


-- 


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-12 15:33 -------
More context on this bug: 
http://gcc.gnu.org/ml/gcc-patches/2003-12/msg01946.html 

-- 


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-13 21:24 -------
...and the hammer branch does not fail this test case because it has Zdenek's 
patch on it.  Well, that explains - and gives me some more confidence to 
submit it for GCC 4.0 too. 

-- 


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-13 23:44 -------
http://gcc.gnu.org/ml/gcc-patches/2005-02/msg00655.html 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-02-20 11:09 -------
Subject: Bug 19698

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	steven@gcc.gnu.org	2005-02-20 11:09:16

Modified files:
	gcc            : ChangeLog cfgloop.c flow.c function.h 

Log message:
	PR middle-end/19698
	* function.h (struct function): New field `max_loop_depth'.
	* cfgloop.c (establish_preds): Update maximum loop depth seen so far.
	(flow_loops_find): Reset the max loop depth count before finding loops.
	* flow.c (MAX_LIVENESS_ROUNDS): New constant.
	(update_life_info_in_dirty_blocks): Remove 2002-05-28 workaround.
	(calculate_global_regs_live): Make sure the loop will terminate
	when the initial sets are not empty.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7538&r2=2.7539
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/cfgloop.c.diff?cvsroot=gcc&r1=1.47&r2=1.48
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/flow.c.diff?cvsroot=gcc&r1=1.618&r2=1.619
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/function.h.diff?cvsroot=gcc&r1=1.139&r2=1.140



-- 


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-20 11:11 -------
Should be fixed now... 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
      Known to fail|3.0.4 3.1.2 3.2.3 3.3.6     |3.0.4 3.1.2 3.2.3 3.3.6
                   |3.4.4 4.0.0                 |3.4.4
      Known to work|                            |4.0.0
         Resolution|                            |FIXED


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

[Bug middle-end/19698] [3.4/4.0 Regression] Infinite loop in update_life_info

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4.4                       |4.0.0


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