* [Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
@ 2005-02-26 15:28 ` pinskia at gcc dot gnu dot org
2005-02-26 16:13 ` fjahanian at apple dot com
` (12 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-02-26 15:28 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
2005-02-26 15:28 ` [Bug tree-optimization/20216] [4.0/4.1 Regression] " pinskia at gcc dot gnu dot org
@ 2005-02-26 16:13 ` fjahanian at apple dot com
2005-02-26 16:25 ` pinskia at gcc dot gnu dot org
` (11 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: fjahanian at apple dot com @ 2005-02-26 16:13 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
2005-02-26 15:28 ` [Bug tree-optimization/20216] [4.0/4.1 Regression] " pinskia at gcc dot gnu dot org
2005-02-26 16:13 ` fjahanian at apple dot com
@ 2005-02-26 16:25 ` pinskia at gcc dot gnu dot org
2005-02-27 4:32 ` hp at gcc dot gnu dot org
` (10 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-02-26 16:25 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (2 preceding siblings ...)
2005-02-26 16:25 ` pinskia at gcc dot gnu dot org
@ 2005-02-27 4:32 ` hp at gcc dot gnu dot org
2005-02-27 4:37 ` hp at gcc dot gnu dot org
` (9 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: hp at gcc dot gnu dot org @ 2005-02-27 4:32 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (3 preceding siblings ...)
2005-02-27 4:32 ` hp at gcc dot gnu dot org
@ 2005-02-27 4:37 ` hp at gcc dot gnu dot org
2005-02-27 8:45 ` dberlin at gcc dot gnu dot org
` (8 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: hp at gcc dot gnu dot org @ 2005-02-27 4:37 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (4 preceding siblings ...)
2005-02-27 4:37 ` hp at gcc dot gnu dot org
@ 2005-02-27 8:45 ` dberlin at gcc dot gnu dot org
2005-02-27 13:06 ` fjahanian at apple dot com
` (7 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: dberlin at gcc dot gnu dot org @ 2005-02-27 8:45 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (5 preceding siblings ...)
2005-02-27 8:45 ` dberlin at gcc dot gnu dot org
@ 2005-02-27 13:06 ` fjahanian at apple dot com
2005-02-27 13:21 ` dberlin at dberlin dot org
` (6 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: fjahanian at apple dot com @ 2005-02-27 13:06 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (6 preceding siblings ...)
2005-02-27 13:06 ` fjahanian at apple dot com
@ 2005-02-27 13:21 ` dberlin at dberlin dot org
2005-02-27 21:03 ` pinskia at gcc dot gnu dot org
` (5 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: dberlin at dberlin dot org @ 2005-02-27 13:21 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (7 preceding siblings ...)
2005-02-27 13:21 ` dberlin at dberlin dot org
@ 2005-02-27 21:03 ` pinskia at gcc dot gnu dot org
2005-03-01 2:44 ` cvs-commit at gcc dot gnu dot org
` (4 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-02-27 21:03 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0/4.1 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (8 preceding siblings ...)
2005-02-27 21:03 ` pinskia at gcc dot gnu dot org
@ 2005-03-01 2:44 ` cvs-commit at gcc dot gnu dot org
2005-03-01 15:13 ` [Bug tree-optimization/20216] [4.0 " pinskia at gcc dot gnu dot org
` (3 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: cvs-commit at gcc dot gnu dot org @ 2005-03-01 2:44 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (9 preceding siblings ...)
2005-03-01 2:44 ` cvs-commit at gcc dot gnu dot org
@ 2005-03-01 15:13 ` pinskia at gcc dot gnu dot org
2005-03-01 16:23 ` cvs-commit at gcc dot gnu dot org
` (2 subsequent siblings)
13 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-03-01 15:13 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (10 preceding siblings ...)
2005-03-01 15:13 ` [Bug tree-optimization/20216] [4.0 " pinskia at gcc dot gnu dot org
@ 2005-03-01 16:23 ` cvs-commit at gcc dot gnu dot org
2005-03-01 16:28 ` cvs-commit at gcc dot gnu dot org
2005-03-01 17:06 ` pinskia at gcc dot gnu dot org
13 siblings, 0 replies; 16+ messages in thread
From: cvs-commit at gcc dot gnu dot org @ 2005-03-01 16:23 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (11 preceding siblings ...)
2005-03-01 16:23 ` cvs-commit at gcc dot gnu dot org
@ 2005-03-01 16:28 ` cvs-commit at gcc dot gnu dot org
2005-03-01 17:06 ` pinskia at gcc dot gnu dot org
13 siblings, 0 replies; 16+ messages in thread
From: cvs-commit at gcc dot gnu dot org @ 2005-03-01 16:28 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [Bug tree-optimization/20216] [4.0 Regression] Simple loop runs out of stack at -O1
2005-02-26 14:26 [Bug tree-optimization/20216] New: Simple loop runs out of stack at -O1 fjahanian at apple dot com
` (12 preceding siblings ...)
2005-03-01 16:28 ` cvs-commit at gcc dot gnu dot org
@ 2005-03-01 17:06 ` pinskia at gcc dot gnu dot org
13 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-03-01 17:06 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 16+ messages in thread