[Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1

[Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1

[fjahanian at apple dot com]

Following test case runs out of stack space when
gcc tries to compute factorial (1599999). I have a patch which does two simple things. 1) it rewrites 
tree_fold_factorial
function into its non-recursive version, and 2) it sets a limit before deciding to call chrec_evaluate. This 
limit is arbitrary in this
patch. Author of the algorithm may want to decide when to stop evaluating feasibility of this 
optimization. Note that even with this limit,
the computed factorial overflows. So, even a much smaller limit is needed if this value is significant.

/* bad.c */
static unsigned int *buffer;

void FUNC (void)
{
 unsigned int *base;
 int i, j;

 for (i = 0; i < 4; i++)
  for (j = 0; j < 1600000; j++)
   *base++ = buffer[j];
}

% mygccm5 -c -O1 bad.c
Out of stack space.
Try running 'limit stacksize unlimited' in the shell to raise its limit.

-- 
           Summary: Simple loop runs out of stack at -O1
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: fjahanian at apple dot com
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: powerpc-apple-darwin
  GCC host triplet: powerpc-apple-darwin
GCC target triplet: powerpc-apple-darwin


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

[Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-25 21:30 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog, memory-hog
            Summary|Simple loop runs out of     |[4.0/4.1 Regression] Simple
                   |stack at -O1                |loop runs out of stack at -
                   |                            |O1
   Target Milestone|---                         |4.0.0


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

[Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1

[fjahanian at apple dot com]

------- Additional Comments From fjahanian at apple dot com  2005-02-25 21:32 -------
Created an attachment (id=8286)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=8286&action=view)
A proposed patch to fix this

Note that patch I attached is against the apple-ppc-branch. So, it may not
apply to the mainline
as is. 

-- 


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

[Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-25 21:36 -------
(In reply to comment #2)
> Note that patch I attached is against the apple-ppc-branch. So, it may not
> apply to the mainline as is. 

It looks like it should from my updated sources.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-02-25 21:36:07
               date|                            |


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

[Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1

[hp at gcc dot gnu dot org]

------- Additional Comments From hp at gcc dot gnu dot org  2005-02-26 11:22 -------
The pointer "base" looks a bit uninitialized.  Fix the test-case?

-- 


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

[Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1

[hp at gcc dot gnu dot org]

------- Additional Comments From hp at gcc dot gnu dot org  2005-02-26 11:24 -------
Ignore comment #4, sorry (misread this as being about run-time behavior).

-- 


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

[Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1

[dberlin at gcc dot gnu dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-02-26 19:20 -------
The first part of the patch seems fine.
We should make tree_fold_binomial non-recursive.
Note, however, that once you do that, the other part of the patch isn't actually
doing anything (the change to chrec_apply).

Then all the memory usage comes from fold (all 600 meg of memory usage, i mean)
creating new trees.
It also doesn't recurse int hat case.

In any case, limiting the input to chrec_apply to <1024 is uh, wrong, as it's
not really fixing anything.


-- 


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

[Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1

[fjahanian at apple dot com]

------- Additional Comments From fjahanian at apple dot com  2005-02-27 00:51 -------
(In reply to comment #6)
> The first part of the patch seems fine.
> We should make tree_fold_binomial non-recursive.
You meant tree_fold_factorial? tree_fold_binomial is not recursive as is.

> Note, however, that once you do that, the other part of the patch isn't actually
> doing anything (the change to chrec_apply).
I agree. checking for 1024 is arbitrary and I did not propose it as a final solution.
I think a better solution would be to compute the factorial of the array upper bound,
as currently is done. If it cannot be evaluated, due to overflow, chrec_evaluate 
which depends on computation of tree_fold_binomial returns chrec_dont_know. In other words, we
do this optimization only when factorial can be computed. This prevents
setting an arbitrary limit and will let the implmentation limitations dicides feasibility
of this optimization. What do you think on a patch along this line?

> 
> Then all the memory usage comes from fold (all 600 meg of memory usage, i mean)
> creating new trees.
> It also doesn't recurse int hat case.
> 
> In any case, limiting the input to chrec_apply to <1024 is uh, wrong, as it's
> not really fixing anything.
> 

-- 


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

[Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-02-27 02:09 -------
Subject: Re:  [4.0/4.1 Regression] Simple loop
	runs out of stack at -O1

On Sun, 2005-02-27 at 00:51 +0000, fjahanian at apple dot com wrote:
> ------- Additional Comments From fjahanian at apple dot com  2005-02-27 00:51 -------
> (In reply to comment #6)
> > The first part of the patch seems fine.
> > We should make tree_fold_binomial non-recursive.
> You meant tree_fold_factorial? tree_fold_binomial is not recursive as is.
> 
> > Note, however, that once you do that, the other part of the patch isn't actually
> > doing anything (the change to chrec_apply).
> I agree. checking for 1024 is arbitrary and I did not propose it as a final solution.
> I think a better solution would be to compute the factorial of the array upper bound,
> as currently is done. If it cannot be evaluated, due to overflow, chrec_evaluate 
> which depends on computation of tree_fold_binomial returns chrec_dont_know. In other words, we
> do this optimization only when factorial can be computed. This prevents
> setting an arbitrary limit and will let the implmentation limitations dicides feasibility
> of this optimization. What do you think on a patch along this line?


I believe Roger Sayle was considering simply rewriting this code to not
use fold at all, for starters, and then doing the smart thing about
evaluation of binomial.

Let's see what he has to say.





-- 


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

[Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-27 15:40 -------
Patch here: <http://gcc.gnu.org/ml/gcc-patches/2005-02/msg01723.html>.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
           Keywords|                            |patch


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

[Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-03-01 02:44 -------
Subject: Bug 20216

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	sayle@gcc.gnu.org	2005-03-01 02:43:50

Modified files:
	gcc            : ChangeLog tree-chrec.c 

Log message:
	PR tree-optimization/20216
	* tree-chrec.c (tree_fold_factorial): Delete.
	(tree_fold_binomial): Change argument list to take a return type
	and change the type of K to unsigned int.  Rewrite to avoid explicit
	evaluation of factorials, and (recursively) calling fold to perform
	compile-time arithmetic.  Return NULL on (internal) overflow.
	(chrec_evaluate): Change type of K to an unsigned int.  Avoid
	calling tree_fold_binomial unnecessarily.  Return chrec_dont_know
	if any intermediate calculation overflows.
	(chrec_apply): Update call to chrec_evaluate.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7617&r2=2.7618
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-chrec.c.diff?cvsroot=gcc&r1=2.12&r2=2.13



-- 


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

[Bug tree-optimization/20216] [4.0 Regression] Simple loop runs out of stack at -O1

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-01 15:12 -------
Fixed at least on the mainline.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |3.4.0 4.1.0
            Summary|[4.0/4.1 Regression] Simple |[4.0 Regression] Simple loop
                   |loop runs out of stack at - |runs out of stack at -O1
                   |O1                          |


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

[Bug tree-optimization/20216] [4.0 Regression] Simple loop runs out of stack at -O1

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-03-01 16:22 -------
Subject: Bug 20216

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	apple-ppc-branch
Changes by:	fjahanian@gcc.gnu.org	2005-03-01 16:21:44

Modified files:
	gcc            : tree-chrec.c 
Added files:
	gcc/testsuite/gcc.dg: pr20216.c 

Log message:
	Radar 4022005
	PR tree-optimization/20216
	* tree-chrec.c (tree_fold_factorial): Delete.
	(tree_fold_binomial): Change argument list to take a return type
	and change the type of K to unsigned int.  Rewrite to avoid explicit
	evaluation of factorials, and (recursively) calling fold to perform
	compile-time arithmetic.  Return NULL on (internal) overflow.
	(chrec_evaluate): Change type of K to an unsigned int.  Avoid
	calling tree_fold_binomial unnecessarily.  Return chrec_dont_know
	if any intermediate calculation overflows.
	(chrec_apply): Update call to chrec_evaluate.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/pr20216.c.diff?cvsroot=gcc&only_with_tag=apple-ppc-branch&r1=NONE&r2=1.1.2.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-chrec.c.diff?cvsroot=gcc&only_with_tag=apple-ppc-branch&r1=1.1.4.9&r2=1.1.4.10



-- 


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

[Bug tree-optimization/20216] [4.0 Regression] Simple loop runs out of stack at -O1

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-03-01 16:28 -------
Subject: Bug 20216

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-4_0-branch
Changes by:	sayle@gcc.gnu.org	2005-03-01 16:27:51

Modified files:
	gcc            : ChangeLog tree-chrec.c 

Log message:
	PR tree-optimization/20216
	* tree-chrec.c (tree_fold_factorial): Delete.
	(tree_fold_binomial): Change argument list to take a return type
	and change the type of K to unsigned int.  Rewrite to avoid explicit
	evaluation of factorials, and (recursively) calling fold to perform
	compile-time arithmetic.  Return NULL on (internal) overflow.
	(chrec_evaluate): Change type of K to an unsigned int.  Avoid
	calling tree_fold_binomial unnecessarily.  Return chrec_dont_know
	if any intermediate calculation overflows.
	(chrec_apply): Update call to chrec_evaluate.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.7592.2.15&r2=2.7592.2.16
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-chrec.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.12&r2=2.12.12.1



-- 


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

[Bug tree-optimization/20216] [4.0 Regression] Simple loop runs out of stack at -O1

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-01 17:06 -------
And now fixed on the 4.0 branch also.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


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