public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
* [Bug rtl-optimization/28772] New: Infinite loop in scheduler @ 2006-08-18 11:48 schwab at suse dot de 2006-08-18 11:49 ` [Bug rtl-optimization/28772] " schwab at suse dot de ` (7 more replies) 0 siblings, 8 replies; 9+ messages in thread From: schwab at suse dot de @ 2006-08-18 11:48 UTC (permalink / raw) To: gcc-bugs 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/28772] Infinite loop in scheduler 2006-08-18 11:48 [Bug rtl-optimization/28772] New: Infinite loop in scheduler schwab at suse dot de @ 2006-08-18 11:49 ` schwab at suse dot de 2006-08-18 12:48 ` bonzini at gnu dot org ` (6 subsequent siblings) 7 siblings, 0 replies; 9+ messages in thread From: schwab at suse dot de @ 2006-08-18 11:49 UTC (permalink / raw) To: gcc-bugs ------- 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/28772] Infinite loop in scheduler 2006-08-18 11:48 [Bug rtl-optimization/28772] New: Infinite loop in scheduler schwab at suse dot de 2006-08-18 11:49 ` [Bug rtl-optimization/28772] " schwab at suse dot de @ 2006-08-18 12:48 ` bonzini at gnu dot org 2006-08-18 14:50 ` schwab at suse dot de ` (5 subsequent siblings) 7 siblings, 0 replies; 9+ messages in thread From: bonzini at gnu dot org @ 2006-08-18 12:48 UTC (permalink / raw) To: gcc-bugs ------- 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/28772] Infinite loop in scheduler 2006-08-18 11:48 [Bug rtl-optimization/28772] New: Infinite loop in scheduler schwab at suse dot de 2006-08-18 11:49 ` [Bug rtl-optimization/28772] " schwab at suse dot de 2006-08-18 12:48 ` bonzini at gnu dot org @ 2006-08-18 14:50 ` schwab at suse dot de 2007-01-25 11:42 ` [Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64 mkuvyrkov at gcc dot gnu dot org ` (4 subsequent siblings) 7 siblings, 0 replies; 9+ messages in thread From: schwab at suse dot de @ 2006-08-18 14:50 UTC (permalink / raw) To: gcc-bugs ------- 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64 2006-08-18 11:48 [Bug rtl-optimization/28772] New: Infinite loop in scheduler schwab at suse dot de ` (2 preceding siblings ...) 2006-08-18 14:50 ` schwab at suse dot de @ 2007-01-25 11:42 ` mkuvyrkov at gcc dot gnu dot org 2007-02-13 13:20 ` patchapp at dberlin dot org ` (3 subsequent siblings) 7 siblings, 0 replies; 9+ messages in thread From: mkuvyrkov at gcc dot gnu dot org @ 2007-01-25 11:42 UTC (permalink / raw) To: gcc-bugs ------- 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64 2006-08-18 11:48 [Bug rtl-optimization/28772] New: Infinite loop in scheduler schwab at suse dot de ` (3 preceding siblings ...) 2007-01-25 11:42 ` [Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64 mkuvyrkov at gcc dot gnu dot org @ 2007-02-13 13:20 ` patchapp at dberlin dot org 2007-02-13 15:59 ` ebotcazou at gcc dot gnu dot org ` (2 subsequent siblings) 7 siblings, 0 replies; 9+ messages in thread From: patchapp at dberlin dot org @ 2007-02-13 13:20 UTC (permalink / raw) To: gcc-bugs ------- 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64 2006-08-18 11:48 [Bug rtl-optimization/28772] New: Infinite loop in scheduler schwab at suse dot de ` (4 preceding siblings ...) 2007-02-13 13:20 ` patchapp at dberlin dot org @ 2007-02-13 15:59 ` ebotcazou at gcc dot gnu dot org 2007-02-14 20:51 ` ebotcazou at gcc dot gnu dot org 2007-02-14 20:53 ` ebotcazou at gcc dot gnu dot org 7 siblings, 0 replies; 9+ messages in thread From: ebotcazou at gcc dot gnu dot org @ 2007-02-13 15:59 UTC (permalink / raw) To: gcc-bugs ------- 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64 2006-08-18 11:48 [Bug rtl-optimization/28772] New: Infinite loop in scheduler schwab at suse dot de ` (5 preceding siblings ...) 2007-02-13 15:59 ` ebotcazou at gcc dot gnu dot org @ 2007-02-14 20:51 ` ebotcazou at gcc dot gnu dot org 2007-02-14 20:53 ` ebotcazou at gcc dot gnu dot org 7 siblings, 0 replies; 9+ messages in thread From: ebotcazou at gcc dot gnu dot org @ 2007-02-14 20:51 UTC (permalink / raw) To: gcc-bugs ------- 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64 2006-08-18 11:48 [Bug rtl-optimization/28772] New: Infinite loop in scheduler schwab at suse dot de ` (6 preceding siblings ...) 2007-02-14 20:51 ` ebotcazou at gcc dot gnu dot org @ 2007-02-14 20:53 ` ebotcazou at gcc dot gnu dot org 7 siblings, 0 replies; 9+ messages in thread From: ebotcazou at gcc dot gnu dot org @ 2007-02-14 20:53 UTC (permalink / raw) To: gcc-bugs ------- 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2007-02-14 20:53 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2006-08-18 11:48 [Bug rtl-optimization/28772] New: Infinite loop in scheduler schwab at suse dot de 2006-08-18 11:49 ` [Bug rtl-optimization/28772] " schwab at suse dot de 2006-08-18 12:48 ` bonzini at gnu dot org 2006-08-18 14:50 ` schwab at suse dot de 2007-01-25 11:42 ` [Bug rtl-optimization/28772] scheduler is too slow and O(n^2) for ia64 mkuvyrkov at gcc dot gnu dot org 2007-02-13 13:20 ` patchapp at dberlin dot org 2007-02-13 15:59 ` ebotcazou at gcc dot gnu dot org 2007-02-14 20:51 ` ebotcazou at gcc dot gnu dot org 2007-02-14 20:53 ` ebotcazou at gcc dot gnu dot org
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).