Bug 19698 - [3.4/4.0 Regression] Infinite loop in update_life_info
Summary: [3.4/4.0 Regression] Infinite loop in update_life_info
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: middle-end (show other bugs)
Version: 4.0.0
: P2 normal
Target Milestone: 4.0.0
Assignee: Not yet assigned to anyone
URL:
Keywords: compile-time-hog, patch
Depends on:
Blocks:
 
Reported: 2005-01-29 19:17 UTC by Andreas Schwab
Modified: 2005-02-20 13:34 UTC (History)
6 users (show)

See Also:
Host:
Target: ia64-linux
Build:
Known to work: 4.0.0
Known to fail: 3.0.4 3.1.2 3.2.3 3.3.6 3.4.4
Last reconfirmed: 2005-01-30 03:30:25


Attachments
Test case (725 bytes, text/plain)
2005-01-29 19:18 UTC, Andreas Schwab
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Andreas Schwab 2005-01-29 19:17:19 UTC
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.
Comment 1 Andreas Schwab 2005-01-29 19:18:09 UTC
Created attachment 8102 [details]
Test case
Comment 2 Andreas Schwab 2005-01-30 02:33:22 UTC
This is broken since the tree-ssa merge. 
Comment 3 Andrew Pinski 2005-01-30 02:43:45 UTC
(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.
Comment 4 Andrew Pinski 2005-01-30 03:30:25 UTC
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;
  }
}
Comment 5 Andrew Pinski 2005-01-30 04:09:23 UTC
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);
}


Comment 6 Andreas Schwab 2005-01-30 13:47:44 UTC
The test case from comment #5 triggers the bug in all branches since 3.3 (but 
not on the hammer branch).  
Comment 7 Andreas Schwab 2005-01-30 22:25:06 UTC
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. 
 
Comment 8 Andrew Pinski 2005-01-30 23:00:53 UTC
(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;
  }
}
Comment 9 Andrew Pinski 2005-01-30 23:07:39 UTC
(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);
}
Comment 10 Andreas Schwab 2005-01-31 00:12:44 UTC
Ok, so this is a _very_ old bug, reproducable even with 3.0. 
Comment 11 Andrew Pinski 2005-01-31 00:15:06 UTC
(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.
Comment 12 Andreas Schwab 2005-01-31 00:19:21 UTC
The hammer branch still does not exhibit the problem. 
Comment 13 Eric Botcazou 2005-01-31 07:22:16 UTC
> 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.
Comment 14 Steven Bosscher 2005-01-31 07:33:18 UTC
You probably mean this patch??? 
http://gcc.gnu.org/ml/gcc-patches/2003-01/msg02059.html 
Comment 15 Eric Botcazou 2005-01-31 07:38:46 UTC
> You probably mean this patch??? 
> http://gcc.gnu.org/ml/gcc-patches/2003-01/msg02059.html 

Yep.
Comment 16 Steven Bosscher 2005-02-12 15:33:36 UTC
More context on this bug: 
http://gcc.gnu.org/ml/gcc-patches/2003-12/msg01946.html 
Comment 17 Steven Bosscher 2005-02-13 21:24:39 UTC
...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. 
Comment 19 CVS Commits 2005-02-20 11:09:38 UTC
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

Comment 20 Steven Bosscher 2005-02-20 11:11:17 UTC
Should be fixed now...