* [Bug middle-end/56490] [4.6/4.7/4.8 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
@ 2013-03-01 12:10 ` rguenth at gcc dot gnu.org
2013-03-01 22:46 ` xinliangli at gmail dot com
` (10 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-03-01 12:10 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Keywords| |compile-time-hog,
| |diagnostic
Last reconfirmed| |2013-03-01
Component|fortran |middle-end
CC| |davidxl at google dot com
Ever Confirmed|0 |1
Summary|[4.6/4.7 Regression] -Wall |[4.6/4.7/4.8 Regression]
|triggering infinite loop |-Wall triggering infinite
| |loop
Target Milestone|--- |4.6.4
--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-01 12:09:40 UTC ---
Confirmed.
#0 0x0000000000d43262 in find_pdom (block=0x7ffff6b43340)
at /space/rguenther/src/svn/trunk/gcc/tree-ssa-uninit.c:170
#1 0x0000000000d4358a in compute_control_dep_chain (bb=0x7ffff6d32ea0,
dep_bb=0x7ffff6b4b820, cd_chains=0x1d67f20, num_chains=0x7fffffffd870,
cur_cd_chain=0x7fffffffd860)
at /space/rguenther/src/svn/trunk/gcc/tree-ssa-uninit.c:300
#2 0x0000000000d43574 in compute_control_dep_chain (bb=0x7ffff6b439c0,
dep_bb=0x7ffff6b4b820, cd_chains=0x1d67f20, num_chains=0x7fffffffd870,
cur_cd_chain=0x7fffffffd860)
at /space/rguenther/src/svn/trunk/gcc/tree-ssa-uninit.c:293
#3 0x0000000000d43574 in compute_control_dep_chain (bb=0x7ffff6d32c98,
dep_bb=0x7ffff6b4b820, cd_chains=0x1d67f20, num_chains=0x7fffffffd870,
cur_cd_chain=0x7fffffffd860)
at /space/rguenther/src/svn/trunk/gcc/tree-ssa-uninit.c:293
#4 0x0000000000d43574 in compute_control_dep_chain (bb=0x7ffff6d32a28,
dep_bb=0x7ffff6b4b820, cd_chains=0x1d67f20, num_chains=0x7fffffffd870,
cur_cd_chain=0x7fffffffd860)
at /space/rguenther/src/svn/trunk/gcc/tree-ssa-uninit.c:293
#5 0x0000000000d43574 in compute_control_dep_chain (bb=0x7ffff6d329c0,
dep_bb=0x7ffff6b4b820, cd_chains=0x1d67f20, num_chains=0x7fffffffd870,
cur_cd_chain=0x7fffffffd860)
at /space/rguenther/src/svn/trunk/gcc/tree-ssa-uninit.c:293
Uninit diagnostic not being properly limited and appearantly not being
linear in complexity.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug middle-end/56490] [4.6/4.7/4.8 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
2013-03-01 12:10 ` [Bug middle-end/56490] [4.6/4.7/4.8 " rguenth at gcc dot gnu.org
@ 2013-03-01 22:46 ` xinliangli at gmail dot com
2013-03-08 15:52 ` [Bug tree-optimization/56490] [4.6/4.7 " rguenth at gcc dot gnu.org
` (9 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: xinliangli at gmail dot com @ 2013-03-01 22:46 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
davidxl <xinliangli at gmail dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |xinliangli at gmail dot com
--- Comment #2 from davidxl <xinliangli at gmail dot com> 2013-03-01 22:45:48 UTC ---
The function has a control flow that post-dom chain is as long as 103. Limiting
the max post-dom walk length solve the problem.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug tree-optimization/56490] [4.6/4.7 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
2013-03-01 12:10 ` [Bug middle-end/56490] [4.6/4.7/4.8 " rguenth at gcc dot gnu.org
2013-03-01 22:46 ` xinliangli at gmail dot com
@ 2013-03-08 15:52 ` rguenth at gcc dot gnu.org
2013-03-08 16:04 ` [Bug tree-optimization/56490] [4.6/4.7/4.8 " rguenth at gcc dot gnu.org
` (8 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-03-08 15:52 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Priority|P3 |P2
Component|middle-end |tree-optimization
Known to work| |4.8.0
Blocks| |47344
Summary|[4.6/4.7/4.8 Regression] |[4.6/4.7 Regression] -Wall
|-Wall triggering infinite |triggering infinite loop
|loop |
--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-08 15:51:44 UTC ---
"Fixed" on trunk by
2013-03-01 Xinliang David Li <davidxl@google.com>
* tree-ssa-uninit.c (compute_control_dep_chain): Limit post-dom
walk length.
after the patch:
uninit var analysis : 1.05 (84%) usr
so it's still very expensive.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug tree-optimization/56490] [4.6/4.7/4.8 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
` (2 preceding siblings ...)
2013-03-08 15:52 ` [Bug tree-optimization/56490] [4.6/4.7 " rguenth at gcc dot gnu.org
@ 2013-03-08 16:04 ` rguenth at gcc dot gnu.org
2013-03-08 16:22 ` xinliangli at gmail dot com
` (7 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-03-08 16:04 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Known to work|4.8.0 |
Summary|[4.6/4.7 Regression] -Wall |[4.6/4.7/4.8 Regression]
|triggering infinite loop |-Wall triggering infinite
| |loop
Known to fail| |4.8.0
--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-08 16:03:30 UTC ---
Clearly the limiting is bougs ... the issue is with large fanout BBs
we recurse in compute_control_dep_chain which leads to exponential
complexity. Limiting that to 8^5 isn't really a fix ... (yes, you
can call that O(1)).
compute_control_dep_chain is called 65 million times(!) for the testcase
after the patch.
There has to be a better algorithmic way of implementing this.
IMHO still not fixed in 4.8.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug tree-optimization/56490] [4.6/4.7/4.8 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
` (3 preceding siblings ...)
2013-03-08 16:04 ` [Bug tree-optimization/56490] [4.6/4.7/4.8 " rguenth at gcc dot gnu.org
@ 2013-03-08 16:22 ` xinliangli at gmail dot com
2013-04-12 15:16 ` [Bug tree-optimization/56490] [4.7/4.8/4.9 " jakub at gcc dot gnu.org
` (6 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: xinliangli at gmail dot com @ 2013-03-08 16:22 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
--- Comment #5 from davidxl <xinliangli at gmail dot com> 2013-03-08 16:21:13 UTC ---
(In reply to comment #4)
> Clearly the limiting is bougs ... the issue is with large fanout BBs
> we recurse in compute_control_dep_chain which leads to exponential
> complexity. Limiting that to 8^5 isn't really a fix ... (yes, you
> can call that O(1)).
>
> compute_control_dep_chain is called 65 million times(!) for the testcase
> after the patch.
>
> There has to be a better algorithmic way of implementing this.
>
> IMHO still not fixed in 4.8.
Right.
However for on demand computation like this, limiting is still needed. For
this particular case, limiting the depth to 3 (or may be smaller) won't cause
any regressions.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug tree-optimization/56490] [4.7/4.8/4.9 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
` (4 preceding siblings ...)
2013-03-08 16:22 ` xinliangli at gmail dot com
@ 2013-04-12 15:16 ` jakub at gcc dot gnu.org
2014-02-20 17:14 ` jakub at gcc dot gnu.org
` (5 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-04-12 15:16 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|4.6.4 |4.7.4
--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-04-12 15:15:57 UTC ---
GCC 4.6.4 has been released and the branch has been closed.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug tree-optimization/56490] [4.7/4.8/4.9 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
` (5 preceding siblings ...)
2013-04-12 15:16 ` [Bug tree-optimization/56490] [4.7/4.8/4.9 " jakub at gcc dot gnu.org
@ 2014-02-20 17:14 ` jakub at gcc dot gnu.org
2014-02-20 19:04 ` jakub at gcc dot gnu.org
` (4 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: jakub at gcc dot gnu.org @ 2014-02-20 17:14 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |jakub at gcc dot gnu.org
--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
>From what I can see, the main problem is that on this testcase (and apparently
also on gcc/ada/par.adb) in a single toplevel compute_control_dep_chain call
(i.e. one with cur_chain_len == 0) we can end up with millions of nested
compute_control_dep_chain, and at least on the testcase from this PR all
unsuccessful (num_chains == 0 after the call).
The quick fix can be just to have a counter and return immediate once we reach
the counter (say 1000) during the nested invocations.
For something better, perhaps in addition to such limiting we could watch for
basic blocks on which we've already called compute_control_dep_chain, and if
that call has been unsuccesful previously, record the cur_chain_len at which it
has been called. If we call it on such a bb again at the same or higher
cur_chain_len level, we could assume it is likely going to fail again.
The reason why I'm saying likely is that there is the:
for (i = 0; i < cur_chain_len; i++)
{
edge e = (*cur_cd_chain)[i];
/* Cycle detected. */
if (e->src == bb)
return false;
}
loop and with different start of the cur_cd_chain perhaps it could succeed even
when it failed before.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug tree-optimization/56490] [4.7/4.8/4.9 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
` (6 preceding siblings ...)
2014-02-20 17:14 ` jakub at gcc dot gnu.org
@ 2014-02-20 19:04 ` jakub at gcc dot gnu.org
2014-02-21 9:54 ` jakub at gcc dot gnu.org
` (3 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: jakub at gcc dot gnu.org @ 2014-02-20 19:04 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 32184
--> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32184&action=edit
gcc49-pr56490.patch
Untested fix (cleanups plus the limiting param).
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug tree-optimization/56490] [4.7/4.8/4.9 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
` (7 preceding siblings ...)
2014-02-20 19:04 ` jakub at gcc dot gnu.org
@ 2014-02-21 9:54 ` jakub at gcc dot gnu.org
2014-02-21 10:00 ` [Bug tree-optimization/56490] [4.7/4.8 " jakub at gcc dot gnu.org
` (2 subsequent siblings)
11 siblings, 0 replies; 13+ messages in thread
From: jakub at gcc dot gnu.org @ 2014-02-21 9:54 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Fri Feb 21 09:53:56 2014
New Revision: 207988
URL: http://gcc.gnu.org/viewcvs?rev=207988&root=gcc&view=rev
Log:
PR tree-optimization/56490
* params.def (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS): New param.
* tree-ssa-uninit.c: Include params.h.
(compute_control_dep_chain): Add num_calls argument, return false
if it exceed PARAM_UNINIT_CONTROL_DEP_ATTEMPTS param, pass
num_calls to recursive call.
(find_predicates): Change dep_chain into normal array,
cur_chain into auto_vec<edge, MAX_CHAIN_LEN + 1>, add num_calls
variable and adjust compute_control_dep_chain caller.
(find_def_preds): Likewise.
Modified:
trunk/gcc/ChangeLog
trunk/gcc/params.def
trunk/gcc/tree-ssa-uninit.c
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug tree-optimization/56490] [4.7/4.8 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
` (8 preceding siblings ...)
2014-02-21 9:54 ` jakub at gcc dot gnu.org
@ 2014-02-21 10:00 ` jakub at gcc dot gnu.org
2014-03-06 8:12 ` jakub at gcc dot gnu.org
2014-06-12 13:25 ` [Bug tree-optimization/56490] [4.7 " rguenth at gcc dot gnu.org
11 siblings, 0 replies; 13+ messages in thread
From: jakub at gcc dot gnu.org @ 2014-02-21 10:00 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Known to work| |4.9.0
Summary|[4.7/4.8/4.9 Regression] |[4.7/4.8 Regression] -Wall
|-Wall triggering infinite |triggering infinite loop
|loop |
--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Hopefully fixed/worked around on the trunk.
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug tree-optimization/56490] [4.7/4.8 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
` (9 preceding siblings ...)
2014-02-21 10:00 ` [Bug tree-optimization/56490] [4.7/4.8 " jakub at gcc dot gnu.org
@ 2014-03-06 8:12 ` jakub at gcc dot gnu.org
2014-06-12 13:25 ` [Bug tree-optimization/56490] [4.7 " rguenth at gcc dot gnu.org
11 siblings, 0 replies; 13+ messages in thread
From: jakub at gcc dot gnu.org @ 2014-03-06 8:12 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Thu Mar 6 08:12:02 2014
New Revision: 208372
URL: http://gcc.gnu.org/viewcvs?rev=208372&root=gcc&view=rev
Log:
* Makefile.in (tree-ssa-uninit.o): Depend on $(PARAMS_H).
Backport from mainline
2014-02-21 Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/56490
* params.def (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS): New param.
* tree-ssa-uninit.c: Include params.h.
(compute_control_dep_chain): Add num_calls argument, return false
if it exceed PARAM_UNINIT_CONTROL_DEP_ATTEMPTS param, pass
num_calls to recursive call.
(find_predicates): Change dep_chain into normal array, add num_calls
variable and adjust compute_control_dep_chain caller.
(find_def_preds): Likewise.
Modified:
branches/gcc-4_8-branch/gcc/ChangeLog
branches/gcc-4_8-branch/gcc/Makefile.in
branches/gcc-4_8-branch/gcc/params.def
branches/gcc-4_8-branch/gcc/tree-ssa-uninit.c
^ permalink raw reply [flat|nested] 13+ messages in thread* [Bug tree-optimization/56490] [4.7 Regression] -Wall triggering infinite loop
2013-03-01 9:24 [Bug fortran/56490] New: [4.6/4.7 Regression] -Wall triggering infinite loop o.flebbe@science-computing.de
` (10 preceding siblings ...)
2014-03-06 8:12 ` jakub at gcc dot gnu.org
@ 2014-06-12 13:25 ` rguenth at gcc dot gnu.org
11 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-06-12 13:25 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56490
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|NEW |RESOLVED
Resolution|--- |FIXED
Target Milestone|4.7.4 |4.8.3
Known to fail| |4.7.4
--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed in 4.8.3.
^ permalink raw reply [flat|nested] 13+ messages in thread