[Bug rtl-optimization/36365] New: [4.3/4.4 Regression] Hang in df_analyze

[Bug rtl-optimization/36365] New: [4.3/4.4 Regression] Hang in df_analyze

[jakub at gcc dot gnu dot org]

On the attached testcase with -O1 cc1plus either hangs, or spends enormous
amount of time in:
#7  0x00000000007d9a4b in df_analyze () at ../../gcc/df-core.c:1265
#8  0x00000000009a7935 in find_defs (loop=0x7f67f7de3dc0, body=0x669f640) at
../../gcc/loop-invariant.c:644
#9  0x00000000009a861e in find_invariants (loop=0x7f67f7de3dc0) at
../../gcc/loop-invariant.c:945
#10 0x00000000009a9365 in move_single_loop_invariants (loop=0x7f67f7de3dc0) at
../../gcc/loop-invariant.c:1317
#11 0x00000000009a93d8 in move_loop_invariants () at
../../gcc/loop-invariant.c:1347
#12 0x00000000009a60f3 in rtl_move_loop_invariants () at
../../gcc/loop-init.c:243

(so far I've been waiting 10 minutes).


-- 
           Summary: [4.3/4.4 Regression] Hang in df_analyze
           Product: gcc
           Version: 4.3.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: jakub at gcc dot gnu dot org
GCC target triplet: x86_64-linux


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[jakub at gcc dot gnu dot org]

-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.3.1


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[jakub at gcc dot gnu dot org]

------- Comment #1 from jakub at gcc dot gnu dot org  2008-05-29 10:55 -------
Created an attachment (id=15698)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=15698&action=view)
rh448273.ii.bz2


-- 


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[bonzini at gnu dot org]

------- Comment #2 from bonzini at gnu dot org  2008-05-29 13:31 -------
looks like a loop with 5000 basic blocks...


-- 

bonzini at gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-05-29 13:31:05
               date|                            |


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[zadeck at naturalbridge dot com]

------- Comment #3 from zadeck at naturalbridge dot com  2008-05-29 13:49 -------
Subject: Re:  [4.3/4.4 Regression] Hang in df_analyze

bonzini at gnu dot org wrote:
> ------- Comment #2 from bonzini at gnu dot org  2008-05-29 13:31 -------
> looks like a loop with 5000 basic blocks...
>
>
>   
there was a patch that spark wanted to get in at the end of 4.3 that 
changes the order that we traverse blocks, but it had a problem.   I 
think that we may want to get that patch correct and see if it improves 
this.

kenny


-- 


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[spark at gcc dot gnu dot org]

------- Comment #4 from spark at gcc dot gnu dot org  2008-05-30 18:28 -------
I'm still building the compiler to reproduce the problem.
But can somebody try compiling with --param df-double-queue-threshold-factor=0
and see if it helps ?


-- 


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2008-06-06 14:59 -------
4.3.1 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.1                       |4.3.2


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[jakub at gcc dot gnu dot org]

------- Comment #6 from jakub at gcc dot gnu dot org  2008-06-09 13:33 -------
--param df-double-queue-threshold-factor=0 helps, at -O1 with it the testcase
compiled under 45seconds (with standard trunk checking).


-- 


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[jakub at gcc dot gnu dot org]

------- Comment #7 from jakub at gcc dot gnu dot org  2008-07-30 10:22 -------
Any progress with this?  Stage 1 will end soon...


-- 


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[jsm28 at gcc dot gnu dot org]

------- Comment #8 from jsm28 at gcc dot gnu dot org  2008-08-27 22:04 -------
4.3.2 is released, changing milestones to 4.3.3.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.2                       |4.3.3


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[steven at gcc dot gnu dot org]

------- Comment #9 from steven at gcc dot gnu dot org  2008-11-16 12:17 -------
Advice to folks caring about compiler stability instead of supposedly faster:
Always use double-queue instead of overeager.  The overeager solver is just not
reliable enough, and I have never found any proof for the speed benefit that
Seongbae claimed it has.

The theoretical worst-case time for the overeager algorithm is exponential in
the number of basic blocks, for densely connected CFGs.  I have argued before
that such an algorithm should *never* have been selected as the default for
GCC, even if it is, say, 0.5% faster for a GCC bootstrap (but I did the
comparison last year and I have never actually measured any benefits of
overeager over double queue).

For the double queue, and also for the hybrid search, the number of passes has
a reasonable proven upper bound for any CFG, so these algorithms are much more
reliable.

See also the discussion in PR34400, esp. comments 25-28:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34400#c25
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34400#c28


-- 


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[spark at gcc dot gnu dot org]

------- Comment #10 from spark at gcc dot gnu dot org  2008-11-17 06:13 -------
I agree that the overeager has the worse worst-case bound. I'll happily approve
a patch that drops overeager and leave double-queuing only, provided we have
empirical data over some known programs to show that it is a compile time
neutral change (I bet it will be so, or worst case, only a very slight
slowdown). 


-- 


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[steven at gcc dot gnu dot org]

------- Comment #11 from steven at gcc dot gnu dot org  2008-12-06 20:17 -------
Created an attachment (id=16842)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16842&action=view)
Remove overeager solver

Bootstrapped and tested on ia64-unknown-linux-gnu.

Time-tested by compiling cc1-i/cc1plus-i files for ia64, CSiBE, and various
test cases for old PRs about slow data flow solving.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |steven at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[steven at gcc dot gnu dot org]

------- Comment #12 from steven at gcc dot gnu dot org  2008-12-06 21:25 -------
Patch here:
http://gcc.gnu.org/ml/gcc-patches/2008-12/msg00409.html

Approval mail never made it through, but you can see traces of it here:
http://gcc.gnu.org/ml/gcc-patches/2008-12/msg00410.html


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |http://gcc.gnu.org/ml/gcc-
                   |                            |patches/2008-
                   |                            |12/msg00409.html
           Keywords|                            |patch


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

[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[zadeck at naturalbridge dot com]

------- Comment #13 from zadeck at naturalbridge dot com  2008-12-06 22:33 -------
Subject: Re:  [4.3/4.4 Regression] Hang in df_analyze

steven at gcc dot gnu dot org wrote:
> ------- Comment #12 from steven at gcc dot gnu dot org  2008-12-06 21:25 -------
> Patch here:
> http://gcc.gnu.org/ml/gcc-patches/2008-12/msg00409.html
>
> Approval mail never made it through, but you can see traces of it here:
> http://gcc.gnu.org/ml/gcc-patches/2008-12/msg00410.html
>
>
>   
just to make it official, approved.

kenny


-- 


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

[Bug rtl-optimization/36365] [4.3 Regression] Hang in df_analyze

[steven at gcc dot gnu dot org]

------- Comment #15 from steven at gcc dot gnu dot org  2008-12-06 22:54 -------
Subject: Bug 36365

Author: steven
Date: Sat Dec  6 22:52:43 2008
New Revision: 142529

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=142529
Log:
        PR rtl-optimization/36365
        * df-core.c (df_worklist_dataflow_overeager): Remove.
        (df_worklist_dataflow): Don't call it, use double-queue only.
        * params.def (PARAM_DF_DOUBLE_QUQUQ_THRESHOLD_FACTOR): Remove.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/df-core.c
    trunk/gcc/params.def


-- 


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

[Bug rtl-optimization/36365] [4.3 Regression] Hang in df_analyze

[steven at gcc dot gnu dot org]

------- Comment #14 from steven at gcc dot gnu dot org  2008-12-06 22:54 -------
Fixed in GCC 4.4.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|steven at gcc dot gnu dot   |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW
            Summary|[4.3/4.4 Regression] Hang in|[4.3 Regression] Hang in
                   |df_analyze                  |df_analyze


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

[Bug rtl-optimization/36365] [4.3 Regression] Hang in df_analyze

[rguenth at gcc dot gnu dot org]

------- Comment #16 from rguenth at gcc dot gnu dot org  2009-01-24 10:20 -------
GCC 4.3.3 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.3                       |4.3.4


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

[Bug rtl-optimization/36365] [4.3 Regression] Hang in df_analyze

[zadeck at naturalbridge dot com]

------- Comment #17 from zadeck at naturalbridge dot com  2009-01-24 20:28 -------
Subject: Re:  [4.3 Regression] Hang in df_analyze

rguenth at gcc dot gnu dot org wrote:
> ------- Comment #16 from rguenth at gcc dot gnu dot org  2009-01-24 10:20 -------
> GCC 4.3.3 is being released, adjusting target milestone.
>
>
>   
steven,

did you fix this and forget to close it?


-- 


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

[Bug rtl-optimization/36365] [4.3 Regression] Hang in df_analyze

[steven at gcc dot gnu dot org]

------- Comment #18 from steven at gcc dot gnu dot org  2009-01-24 20:51 -------
The patch could be backported GCC 4.3 if folks want to have it fixed  there.


-- 


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

[Bug rtl-optimization/36365] [4.3 Regression] Hang in df_analyze

[bonzini at gnu dot org]

------- Comment #19 from bonzini at gnu dot org  2009-01-25 07:39 -------
no, it's waiting for a backport.


-- 


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

[Bug rtl-optimization/36365] [4.3 Regression] Hang in df_analyze

[rguenth at gcc dot gnu dot org]

------- Comment #20 from rguenth at gcc dot gnu dot org  2009-08-04 12:29 -------
GCC 4.3.4 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.4                       |4.3.5


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

[Bug rtl-optimization/36365] [4.3 Regression] Hang in df_analyze

[rguenth at gcc dot gnu dot org]

------- Comment #21 from rguenth at gcc dot gnu dot org  2010-05-22 18:12 -------
GCC 4.3.5 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.5                       |4.3.6


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

[Bug rtl-optimization/36365] [4.3 Regression] Hang in df_analyze

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|4.3.6                       |4.4.0

--- Comment #22 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-27 11:26:12 UTC ---
Fixed for 4.4.0.