Bug 56490 - [4.7 Regression] -Wall triggering infinite loop
[4.7 Regression] -Wall triggering infinite loop
Status: RESOLVED FIXED
Product: gcc
Classification: Unclassified
Component: tree-optimization
4.7.2
: P2 normal
: 4.8.3
Assigned To: Not yet assigned to anyone
: compile-time-hog, diagnostic
Depends on:
Blocks: 47344
  Show dependency treegraph
 
Reported: 2013-03-01 09:23 UTC by Olaf Flebbe
Modified: 2014-06-12 13:25 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.5.2, 4.8.3, 4.9.0
Known to fail: 4.6.3, 4.7.2, 4.7.4, 4.8.0
Last reconfirmed: 2013-03-01 00:00:00


Attachments
Testcase: Loops forever with -O2 -Wall (30.04 KB, text/x-fortran)
2013-03-01 09:23 UTC, Olaf Flebbe
Details
gcc49-pr56490.patch (6.69 KB, patch)
2014-02-20 19:04 UTC, Jakub Jelinek
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Olaf Flebbe 2013-03-01 09:23:59 UTC
Created attachment 29559 [details]
Testcase: Loops forever with -O2 -Wall

Compiling testcase, gfortran seems to loop forever.

gfortran -c -O -Wall testcase.f 

leaving out -Wall seems to compile o.k.


Have to problem on several independent gcc distros: This one for instance:

COLLECT_GCC=/usr/local/gcc-4.6.3/bin/gcc
COLLECT_LTO_WRAPPER=/usr/local/gcc-4.6.3/libexec/gcc/x86_64-unknown-linux-gnu/4.6.3/lto-wrapper
Ziel: x86_64-unknown-linux-gnu
Konfiguriert mit: /soft/os/gcc/gcc-4.6.3/gcc-4.6.3/configure --srcdir=/soft/os/gcc/gcc-4.6.3/gcc-4.6.3 --prefix=/usr/local/gcc-4.6.3 --with-included-gettext --enable-__cxa_atexit --enable-threads --enable-shared --enable-languages=c,c++,fortran --enable-libgcj --enable-ssp --disable-libssp --with-gmp-include=/usr/local/devel/gmp/5.0.1-static/include --with-gmp-lib=/usr/local/devel/gmp/5.0.1-static/lib64 --with-mpfr-include=/usr/local/devel/mpfr/2.4.2-static/include --with-mpfr-lib=/usr/local/devel/mpfr/2.4.2-static/lib64 --with-mpc-include=/usr/local/devel/mpc/0.8.1-static/include --with-mpc-lib=/usr/local/devel/mpc/0.8.1-static/lib64
Thread-Modell: posix
gcc-Version 4.6.3 (GCC)
Comment 1 Richard Biener 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.
Comment 2 davidxl 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.
Comment 3 Richard Biener 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.
Comment 4 Richard Biener 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.
Comment 5 davidxl 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.
Comment 6 Jakub Jelinek 2013-04-12 15:15:57 UTC
GCC 4.6.4 has been released and the branch has been closed.
Comment 7 Jakub Jelinek 2014-02-20 17:14:05 UTC
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.
Comment 8 Jakub Jelinek 2014-02-20 19:04:24 UTC
Created attachment 32184 [details]
gcc49-pr56490.patch

Untested fix (cleanups plus the limiting param).
Comment 9 Jakub Jelinek 2014-02-21 09:54:28 UTC
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
Comment 10 Jakub Jelinek 2014-02-21 10:00:49 UTC
Hopefully fixed/worked around on the trunk.
Comment 11 Jakub Jelinek 2014-03-06 08:12:34 UTC
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
Comment 12 Richard Biener 2014-06-12 13:25:13 UTC
Fixed in 4.8.3.