[Bug rtl-optimization/28772] New: Infinite loop in scheduler

[Bug rtl-optimization/28772] New: Infinite loop in scheduler

[schwab at suse dot de]

The scheduler apparently infloops on the attached test case when compiling with
-O2.

#0  internal_state_transition (insn_code=114, chip=0x600000000019ed70)
    at ../../gcc/config/ia64/itanium2.md:125927
#1  0x40000000006e81d0 in schedule_block (b=<value optimized out>, 
    rgn_n_insns=20657) at ../../gcc/haifa-sched.c:1758
#2  0x40000000007928c0 in schedule_region (rgn=0) at ../../gcc/sched-rgn.c:2394
#3  0x4000000000796f40 in schedule_insns (dump_file=<value optimized out>)
    at ../../gcc/sched-rgn.c:2543
#4  0x400000000059ca00 in execute_one_pass (pass=0x60000000000410e8)
    at ../../gcc/passes.c:827
#5  0x400000000059cd00 in execute_pass_list (pass=0x60000000000410e8)
    at ../../gcc/passes.c:859
#6  0x400000000059cd40 in execute_pass_list (pass=0x600000000003fab8)
    at ../../gcc/passes.c:860
#7  0x40000000000feb60 in tree_rest_of_compilation (fndecl=0x2000000000457a00)
    at ../../gcc/tree-optimize.c:419
#8  0x400000000001ca40 in c_expand_body (fndecl=0x2000000000457a00)
    at ../../gcc/c-decl.c:6690
#9  0x400000000060e3d0 in cgraph_expand_function (node=0x200000000045d1e0)
    at ../../gcc/cgraphunit.c:1058
#10 0x4000000000610e80 in cgraph_optimize () at ../../gcc/cgraphunit.c:1124
#11 0x400000000002cb10 in c_write_global_declarations ()
    at ../../gcc/c-decl.c:7698
#12 0x400000000054b850 in toplev_main (argc=<value optimized out>, 
    argv=<value optimized out>) at ../../gcc/toplev.c:1004
#13 0x40000000000d6fd0 in main (argc=4, argv=0x607ffffffeaf2738)
    at ../../gcc/main.c:35


-- 
           Summary: Infinite loop in scheduler
           Product: gcc
           Version: 4.2.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: schwab at suse dot de
GCC target triplet: ia64-*-*


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

[Bug rtl-optimization/28772] Infinite loop in scheduler

[schwab at suse dot de]

------- Comment #1 from schwab at suse dot de  2006-08-18 11:49 -------
Created an attachment (id=12092)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=12092&action=view)
Testcase


-- 


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

[Bug rtl-optimization/28772] Infinite loop in scheduler

[bonzini at gnu dot org]

------- Comment #2 from bonzini at gnu dot org  2006-08-18 12:47 -------
Not an infinite loop.

100 lines => 0.47 sec
200 lines => 0.95 sec
1000 lines => 6.16 sec
1500 lines => 11.19 sec
2000 lines => 18.11 sec
2500 lines => 27.26 sec
3000 lines => 37.83 sec
3200 lines => 42.72 sec
3340 lines => 46.00 sec


-- 


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

[Bug rtl-optimization/28772] Infinite loop in scheduler

[schwab at suse dot de]

------- Comment #3 from schwab at suse dot de  2006-08-18 14:50 -------
 scheduling            :6473.35 (100%) usr   0.60 (88%) sys6473.98 (100%) wall 
499608 kB (90%) ggc


-- 


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

[Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64

[mkuvyrkov at gcc dot gnu dot org]

------- Comment #4 from mkuvyrkov at gcc dot gnu dot org  2007-01-25 11:41 -------
(In reply to comment #3)
>  scheduling            :6473.35 (100%) usr   0.60 (88%) sys6473.98 (100%) wall 
> 499608 kB (90%) ggc
> 

On which revision of gcc-4_2-branch or trunk have you seen it?  It looks to me
that this issue was fixed in rev. 112936 on April 14 2006.

On current trunk scheduler is accounted for 12% of total compile time:

Execution times (seconds)
 garbage collection    :   0.42 ( 1%) usr   0.00 ( 0%) sys   0.44 ( 1%) wall   
   0 kB ( 0%) ggc
 callgraph construction:   0.02 ( 0%) usr   0.00 ( 0%) sys   0.03 ( 0%) wall   
 322 kB ( 0%) ggc
 callgraph optimization:   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   1 kB ( 0%) ggc
 CFG verifier          :   0.11 ( 0%) usr   0.00 ( 0%) sys   0.10 ( 0%) wall   
   0 kB ( 0%) ggc
 trivially dead code   :   0.06 ( 0%) usr   0.00 ( 0%) sys   0.04 ( 0%) wall   
   0 kB ( 0%) ggc
 life analysis         :   1.01 ( 2%) usr   0.00 ( 0%) sys   1.02 ( 2%) wall   
2595 kB ( 4%) ggc
 life info update      :   0.06 ( 0%) usr   0.00 ( 0%) sys   0.08 ( 0%) wall   
   0 kB ( 0%) ggc
 alias analysis        :   0.21 ( 0%) usr   0.00 ( 0%) sys   0.22 ( 0%) wall   
3461 kB ( 5%) ggc
 register scan         :   0.05 ( 0%) usr   0.00 ( 0%) sys   0.04 ( 0%) wall   
   0 kB ( 0%) ggc
 rebuild jump labels   :   0.01 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 preprocessing         :   0.03 ( 0%) usr   0.02 ( 8%) sys   0.04 ( 0%) wall   
1066 kB ( 1%) ggc
 lexical analysis      :   0.04 ( 0%) usr   0.02 ( 8%) sys   0.08 ( 0%) wall   
   0 kB ( 0%) ggc
 parser                :   0.07 ( 0%) usr   0.03 (13%) sys   0.09 ( 0%) wall   
1832 kB ( 3%) ggc
 inline heuristics     :   0.03 ( 0%) usr   0.00 ( 0%) sys   0.03 ( 0%) wall   
   0 kB ( 0%) ggc
 tree gimplify         :   0.03 ( 0%) usr   0.00 ( 0%) sys   0.03 ( 0%) wall   
 322 kB ( 0%) ggc
 tree VRP              :   0.02 ( 0%) usr   0.00 ( 0%) sys   0.02 ( 0%) wall   
   1 kB ( 0%) ggc
 tree copy propagation :   0.02 ( 0%) usr   0.00 ( 0%) sys   0.03 ( 0%) wall   
   1 kB ( 0%) ggc
 tree store copy prop  :   0.01 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 tree find ref. vars   :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 tree PTA              :   0.03 ( 0%) usr   0.00 ( 0%) sys   0.02 ( 0%) wall   
   6 kB ( 0%) ggc
 tree alias analysis   :   0.02 ( 0%) usr   0.03 (12%) sys   0.07 ( 0%) wall   
   0 kB ( 0%) ggc
 tree SSA rewrite      :   0.05 ( 0%) usr   0.00 ( 0%) sys   0.04 ( 0%) wall   
 900 kB ( 1%) ggc
 tree SSA other        :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 tree SSA incremental  :   0.03 ( 0%) usr   0.00 ( 0%) sys   0.05 ( 0%) wall   
   0 kB ( 0%) ggc
 tree operand scan     :   0.38 ( 1%) usr   0.05 (21%) sys   0.38 ( 1%) wall   
4839 kB ( 7%) ggc
 dominator optimization:   0.38 ( 1%) usr   0.00 ( 0%) sys   0.38 ( 1%) wall   
5794 kB ( 8%) ggc
 tree STORE-CCP        :   0.01 ( 0%) usr   0.00 ( 0%) sys   0.02 ( 0%) wall   
 256 kB ( 0%) ggc
 tree CCP              :   0.02 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 tree PRE              :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 tree forward propagate:   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 tree conservative DCE :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.04 ( 0%) wall   
   0 kB ( 0%) ggc
 tree aggressive DCE   :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 tree DSE              :   0.02 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   5 kB ( 0%) ggc
 tree SSA to normal    :   0.01 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 tree rename SSA copies:   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 tree SSA verifier     :   0.75 ( 1%) usr   0.00 ( 0%) sys   0.75 ( 1%) wall   
   0 kB ( 0%) ggc
 tree STMT verifier    :   0.93 ( 2%) usr   0.00 ( 0%) sys   0.88 ( 2%) wall   
   0 kB ( 0%) ggc
 callgraph verifier    :   0.02 ( 0%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall   
   0 kB ( 0%) ggc
 dominance computation :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 expand                :   0.30 ( 1%) usr   0.01 ( 4%) sys   0.29 ( 1%) wall  
11970 kB (16%) ggc
 jump                  :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 forward prop          :   0.09 ( 0%) usr   0.01 ( 4%) sys   0.10 ( 0%) wall   
 602 kB ( 1%) ggc
 CSE                   :   1.90 ( 3%) usr   0.00 ( 0%) sys   1.92 ( 3%) wall   
2433 kB ( 3%) ggc
 loop analysis         :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 CSE 2                 :   1.07 ( 2%) usr   0.00 ( 0%) sys   1.08 ( 2%) wall   
 703 kB ( 1%) ggc
 flow analysis         :   0.01 ( 0%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall   
   0 kB ( 0%) ggc
 combiner              :   0.19 ( 0%) usr   0.00 ( 0%) sys   0.19 ( 0%) wall   
 655 kB ( 1%) ggc
 regmove               :   0.08 ( 0%) usr   0.00 ( 0%) sys   0.07 ( 0%) wall   
   0 kB ( 0%) ggc
 scheduling            :   3.84 ( 7%) usr   0.00 ( 0%) sys   3.85 ( 7%) wall   
5176 kB ( 7%) ggc
 local alloc           :  11.69 (21%) usr   0.01 ( 4%) sys  11.79 (21%) wall   
2340 kB ( 3%) ggc
 global alloc          :  27.39 (49%) usr   0.04 (17%) sys  27.76 (49%) wall   
6809 kB ( 9%) ggc
 reload CSE regs       :   1.50 ( 3%) usr   0.00 ( 0%) sys   1.49 ( 3%) wall   
1553 kB ( 2%) ggc
 flow 2                :   0.03 ( 0%) usr   0.00 ( 0%) sys   0.02 ( 0%) wall   
 958 kB ( 1%) ggc
 peephole 2            :   0.03 ( 0%) usr   0.00 ( 0%) sys   0.02 ( 0%) wall   
   0 kB ( 0%) ggc
 rename registers      :   0.18 ( 0%) usr   0.00 ( 0%) sys   0.19 ( 0%) wall   
   0 kB ( 0%) ggc
 scheduling 2          :   2.80 ( 5%) usr   0.02 ( 8%) sys   2.85 ( 5%) wall  
15552 kB (21%) ggc
 machine dep reorg     :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall   
   0 kB ( 0%) ggc
 final                 :   0.10 ( 0%) usr   0.00 ( 0%) sys   0.11 ( 0%) wall   
   0 kB ( 0%) ggc
 TOTAL                 :  56.08             0.24            56.85             
72607 kB
Extra diagnostic checks enabled; compiler may run slowly.
Configure with --disable-checking to disable checks.

real    0m56.870s
user    0m56.089s
sys     0m0.256s


-- 

mkuvyrkov at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mkuvyrkov at gcc dot gnu dot
                   |                            |org


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

[Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64

[patchapp at dberlin dot org]

------- Comment #5 from patchapp at dberlin dot org  2007-02-13 13:20 -------
Subject: Bug number PR28772

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2007-02/msg01137.html


-- 


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

[Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64

[ebotcazou at gcc dot gnu dot org]

------- Comment #6 from ebotcazou at gcc dot gnu dot org  2007-02-13 15:59 -------
The algorithm is O(n^2) in the number of ready insns at any given time in the
worst case.


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-02-13 15:59:00
               date|                            |


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

[Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64

[ebotcazou at gcc dot gnu dot org]

------- Comment #7 from ebotcazou at gcc dot gnu dot org  2007-02-14 20:51 -------
Subject: Bug 28772

Author: ebotcazou
Date: Wed Feb 14 20:51:12 2007
New Revision: 121964

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=121964
Log:
        PR rtl-optimization/28772
        * Makefile.in (haifa-sched.o): Add dependency on $(PARAMS_H).

        Backport from mainline:
        2006-04-13  Eric Botcazou  <ebotcazou@adacore.com>

        * params.def (PARAM_MAX_SCHED_READY_INSNS): New parameter,
        defaulting to 100.
        * params.h (MAX_SCHED_READY_INSNS): New macro.
        * haifa-sched.c: (queue_to_ready): Re-queue insns for the next cycle
        past MAX_SCHED_READY_INSNS during the first scheduling pass.
        (schedule_block): Delay insns past MAX_SCHED_READY_INSNS in
        the ready list for 1 cycle during the first scheduling pass.
        * doc/invoke.texi (--param): New parameter max-sched-ready-insns.


Modified:
    branches/gcc-4_1-branch/gcc/ChangeLog
    branches/gcc-4_1-branch/gcc/Makefile.in
    branches/gcc-4_1-branch/gcc/doc/invoke.texi
    branches/gcc-4_1-branch/gcc/haifa-sched.c
    branches/gcc-4_1-branch/gcc/params.def
    branches/gcc-4_1-branch/gcc/params.h


-- 


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

[Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64

[ebotcazou at gcc dot gnu dot org]

------- Comment #8 from ebotcazou at gcc dot gnu dot org  2007-02-14 20:53 -------
Fixed on 4.1 branch and up.


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
      Known to fail|3.1.2 3.2.3 3.3.6 4.0.4     |3.1.2 3.2.3 3.3.6 4.0.4
                   |4.1.2 4.2.0                 |4.1.2
      Known to work|                            |4.2.0
         Resolution|                            |FIXED
   Target Milestone|---                         |4.1.3


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