public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
* [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? @ 2005-01-02 7:44 aj at gcc dot gnu dot org 2005-01-02 7:45 ` [Bug tree-optimization/19224] " aj at gcc dot gnu dot org ` (13 more replies) 0 siblings, 14 replies; 15+ messages in thread From: aj at gcc dot gnu dot org @ 2005-01-02 7:44 UTC (permalink / raw) To: gcc-bugs On one of my x86_64-linux systems with GCC CVS from 20041231, the testcase uses in a minute all available memory and therefore the process is killed. This happens not only on x86_64 but also on ia64 and ppc - it seems to work on i386. On my other x86_64-linux system with GCC CVS from 20050101 the testcase uses constant memory - but seems to be in an endless loop. Note the compilers are not configured exactly the same. Here's some information with the later system: /opt/gcc/4.0-devel/libexec/gcc/x86_64-suse-linux-gnu/4.0.0/cc1 -fpreprocessed add.i -dumpbase add.c -mtune=k8 -auxbase add -O -version -o add.s GNU C version 4.0.0 20050101 (experimental) (x86_64-suse-linux-gnu) compiled by GNU C version 4.0.0 20050101 (experimental). GGC heuristics: --param ggc-min-expand=30 --param ggc-min-heapsize=4096 options passed: -fpreprocessed -mtune=k8 -auxbase -O options enabled: -falign-loops -fargument-alias -fasynchronous-unwind-tables -fbranch-count-reg -fcommon -fcprop-registers -fdefer-pop -feliminate-unused-debug-types -ffunction-cse -fgcse-lm -fguess-branch-probability -fident -fif-conversion -fif-conversion2 -fivopts -fkeep-static-consts -fleading-underscore -floop-optimize -floop-optimize2 -fmath-errno -fmerge-constants -fomit-frame-pointer -fpeephole -freg-struct-return -fsched-interblock -fsched-spec -fsched-stalled-insns-dep -fsplit-ivs-in-unroller -fthread-jumps -ftrapping-math -ftree-ccp -ftree-ch -ftree-copyrename -ftree-dce -ftree-dominator-opts -ftree-dse -ftree-fre -ftree-loop-im -ftree-loop-ivcanon -ftree-loop-optimize -ftree-lrs -ftree-pre -ftree-sra -ftree-ter -funwind-tables -fvar-tracking -fzero-initialized-in-bss -m80387 -mhard-float -mno-soft-float -mieee-fp -mfp-ret-in-387 -mno-fancy-math-387 -maccumulate-outgoing-args -mmmx -msse -msse2 -m128bit-long-double -m64 -mtls-direct-seg-refs -mtune=k8 -march=x86-64 vprintf getchar getc_unlocked getchar_unlocked putchar putc_unlocked putchar_unlocked strtod strtol strtoul atof atoi atol add_c add_double add_float add_long [killed by mself] Copyright 2004 Free Software Foundation, Inc. GDB is free software, covered by the GNU General Public License, and you are welcome to change it and/or distribute copies of it under certain conditions. Type "show copying" to see the conditions. There is absolutely no warranty for GDB. Type "show warranty" for details. This GDB was configured as "x86_64-suse-linux"...Using host libthread_db library "/lib64/tls/libthread_db.so.1". (gdb) r -fpreprocessed add.i -dumpbase add.c -mtune=k8 -auxbase add -O -version -o add.s GNU C version 4.0.0 20050101 (experimental) (x86_64-suse-linux-gnu) compiled by GNU C version 4.0.0 20050101 (experimental). GGC heuristics: --param ggc-min-expand=30 --param ggc-min-heapsize=4096 options passed: -fpreprocessed -mtune=k8 -auxbase -O options enabled: -falign-loops -fargument-alias -fasynchronous-unwind-tables -fbranch-count-reg -fcommon -fcprop-registers -fdefer-pop -feliminate-unused-debug-types -ffunction-cse -fgcse-lm -fguess-branch-probability -fident -fif-conversion -fif-conversion2 -fivopts -fkeep-static-consts -fleading-underscore -floop-optimize -floop-optimize2 -fmath-errno -fmerge-constants -fomit-frame-pointer -fpeephole -freg-struct-return -fsched-interblock -fsched-spec -fsched-stalled-insns-dep -fsplit-ivs-in-unroller -fthread-jumps -ftrapping-math -ftree-ccp -ftree-ch -ftree-copyrename -ftree-dce -ftree-dominator-opts -ftree-dse -ftree-fre -ftree-loop-im -ftree-loop-ivcanon -ftree-loop-optimize -ftree-lrs -ftree-pre -ftree-sra -ftree-ter -funwind-tables -fvar-tracking -fzero-initialized-in-bss -m80387 -mhard-float -mno-soft-float -mieee-fp -mfp-ret-in-387 -mno-fancy-math-387 -maccumulate-outgoing-args -mmmx -msse -msse2 -m128bit-long-double -m64 -mtls-direct-seg-refs -mtune=k8 -march=x86-64 vprintf getchar getc_unlocked getchar_unlocked putchar putc_unlocked putchar_unlocked strtod strtol strtoul atof atoi atol add_c add_double add_float add_long (gdb) bt #0 0x000000000095d547 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ac6e10, allow_superloop_chrecs=0 '\0') at tree-chrec.h:47 #1 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5eb0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #2 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5f50, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #3 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6140, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #4 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad65f0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #5 0x000000000095da95 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6640, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1956 #6 0x000000000095dd3f in instantiate_parameters_1 (loop=0xdd1a00, chrec=Variable "chrec" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1949 #7 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5dc0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #8 0x000000000095da95 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5e10, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1956 #9 0x000000000095dd3f in instantiate_parameters_1 (loop=0xdd1a00, chrec=Variable "chrec" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1949 #10 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5af0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #11 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5b90, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #12 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5c30, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #13 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad61e0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #14 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6500, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #15 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad65f0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #16 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad68c0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #17 0x000000000095da95 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6910, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1956 #18 0x000000000095dd3f in instantiate_parameters_1 (loop=0xdd1a00, chrec=Variable "chrec" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1949 #19 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5c30, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #20 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad61e0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #21 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6320, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #22 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6500, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #23 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad67d0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 ---Type <return> to continue, or q <return> to quit--- #24 0x000000000095da95 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6820, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1956 #25 0x000000000095dd3f in instantiate_parameters_1 (loop=0xdd1a00, chrec=Variable "chrec" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1949 #26 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5f50, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #27 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6050, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #28 0x000000000095da95 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad60a0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1956 #29 0x000000000095dd3f in instantiate_parameters_1 (loop=0xdd1a00, chrec=Variable "chrec" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1949 #30 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5eb0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #31 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5f50, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #32 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6050, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #33 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6140, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #34 0x000000000095da95 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6190, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1956 #35 0x000000000095dd3f in instantiate_parameters_1 (loop=0xdd1a00, chrec=Variable "chrec" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1949 #36 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5b90, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #37 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5c30, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #38 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad61e0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #39 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6320, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #40 0x000000000095da95 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad6370, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1956 #41 0x000000000095dd3f in instantiate_parameters_1 (loop=0xdd1a00, chrec=Variable "chrec" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1949 #42 0x000000000095d72d in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5d20, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1966 #43 0x000000000095d6f4 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5dc0, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1964 #44 0x000000000095da95 in instantiate_parameters_1 (loop=0xdd1a00, chrec=0x2a95ad5e10, allow_superloop_chrecs=Variable "allow_superloop_chrecs" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:1956 #45 0x000000000095e9c8 in simple_iv (loop=0xdd1a00, stmt=Variable "stmt" is not available. ) at /cvs/gcc/gcc/tree-scalar-evolution.c:2109 #46 0x00000000004f17d8 in tree_ssa_iv_optimize_loop (data=0x7fbfffda30, loop=Variable "loop" is not available. ) at /cvs/gcc/gcc/tree-ssa-loop-ivopts.c:782 #47 0x00000000004f2876 in tree_ssa_iv_optimize (loops=0xd8eed0) at /cvs/gcc/gcc/tree-ssa-loop-ivopts.c:5164 #48 0x000000000047bd26 in execute_pass_list (pass=0xcd2400) at /cvs/gcc/gcc/tree-optimize.c:525 ---Type <return> to continue, or q <return> to quit--- #49 0x000000000047bdbb in execute_pass_list (pass=0xcd2760) at /cvs/gcc/gcc/tree-optimize.c:563 #50 0x000000000047bdbb in execute_pass_list (pass=0xccd740) at /cvs/gcc/gcc/tree-optimize.c:563 #51 0x000000000047c019 in tree_rest_of_compilation (fndecl=0x2a95a40d00) at /cvs/gcc/gcc/tree-optimize.c:661 #52 0x0000000000419c7b in c_expand_body (fndecl=0x2a95a40d00) at /cvs/gcc/gcc/c-decl.c:6384 #53 0x0000000000953f20 in cgraph_expand_function (node=0x2a95a570d0) at /cvs/gcc/gcc/cgraphunit.c:822 #54 0x00000000009540a8 in cgraph_assemble_pending_functions () at /cvs/gcc/gcc/cgraphunit.c:305 #55 0x00000000009547d9 in cgraph_finalize_function (decl=0x2a95a40d00, nested=0 '\0') at /cvs/gcc/gcc/cgraphunit.c:388 #56 0x000000000041a2b4 in finish_function () at /cvs/gcc/gcc/c-decl.c:6356 #57 0x000000000040611f in yyparse () at c-parse.y:401 #58 0x0000000000407d99 in c_parse_file () at c-parse.y:2922 #59 0x000000000044c3d6 in c_common_parse_file (set_yydebug=Variable "set_yydebug" is not available. ) at /cvs/gcc/gcc/c-opts.c:1092 #60 0x00000000008f6ece in toplev_main (argc=Variable "argc" is not available. ) at /cvs/gcc/gcc/toplev.c:992 #61 0x0000002a9568900d in __libc_start_main () from /lib64/tls/libc.so.6 #62 0x00000000004025ea in _start () at start.S:113 -- Summary: Endless loop compiling simple file: Bug in tree-scalar- evolution.c (instantiate_parameters_1)? Product: gcc Version: 4.0.0 Status: UNCONFIRMED Severity: normal Priority: P2 Component: tree-optimization AssignedTo: unassigned at gcc dot gnu dot org ReportedBy: aj at gcc dot gnu dot org CC: gcc-bugs at gcc dot gnu dot org,rakdver at gcc dot gnu dot org GCC build triplet: x86_64-linux-gnu GCC host triplet: x86_64-linux-gnu GCC target triplet: x86_64-linux-gnu http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org @ 2005-01-02 7:45 ` aj at gcc dot gnu dot org 2005-01-02 11:53 ` [Bug tree-optimization/19224] [4.0 regression] " steven at gcc dot gnu dot org ` (12 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: aj at gcc dot gnu dot org @ 2005-01-02 7:45 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From aj at gcc dot gnu dot org 2005-01-02 07:45 ------- Created an attachment (id=7861) --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=7861&action=view) Preprocessed source file -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org 2005-01-02 7:45 ` [Bug tree-optimization/19224] " aj at gcc dot gnu dot org @ 2005-01-02 11:53 ` steven at gcc dot gnu dot org 2005-01-02 12:05 ` aj at gcc dot gnu dot org ` (11 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: steven at gcc dot gnu dot org @ 2005-01-02 11:53 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From steven at gcc dot gnu dot org 2005-01-02 11:53 ------- Pop probably wants to know about this too. Obviously a regression because pre-4.0 there was no scev, and so no infinite loop either. -- What |Removed |Added ---------------------------------------------------------------------------- CC| |sebastian dot pop at cri dot | |ensmp dot fr Status|UNCONFIRMED |NEW Ever Confirmed| |1 Last reconfirmed|0000-00-00 00:00:00 |2005-01-02 11:53:19 date| | Summary|Endless loop compiling |[4.0 regression] Endless |simple file: Bug in tree- |loop compiling simple file: |scalar-evolution.c |Bug in tree-scalar- |(instantiate_parameters_1)? |evolution.c | |(instantiate_parameters_1)? http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org 2005-01-02 7:45 ` [Bug tree-optimization/19224] " aj at gcc dot gnu dot org 2005-01-02 11:53 ` [Bug tree-optimization/19224] [4.0 regression] " steven at gcc dot gnu dot org @ 2005-01-02 12:05 ` aj at gcc dot gnu dot org 2005-01-02 12:13 ` rakdver at gcc dot gnu dot org ` (10 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: aj at gcc dot gnu dot org @ 2005-01-02 12:05 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From aj at gcc dot gnu dot org 2005-01-02 12:05 ------- I've reduced the testcase to the following loop: int add_long(long tl1, long tl2, long tloop_cnt, long *res) { int n; long l1, l2, l; l1 = tl1; l2 = tl2; l = 0; for (n = tloop_cnt; n > 0; n--) { l += l1; l1 += l2; l1 += l2; l2 += l; l2 += l; l += l1; l += l1; l1 += l2; l1 += l2; l2 += l; l2 += l; l += l1; } *res = l; return (0); } -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (2 preceding siblings ...) 2005-01-02 12:05 ` aj at gcc dot gnu dot org @ 2005-01-02 12:13 ` rakdver at gcc dot gnu dot org 2005-01-02 15:57 ` pinskia at gcc dot gnu dot org ` (9 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: rakdver at gcc dot gnu dot org @ 2005-01-02 12:13 UTC (permalink / raw) To: gcc-bugs -- What |Removed |Added ---------------------------------------------------------------------------- AssignedTo|unassigned at gcc dot gnu |rakdver at gcc dot gnu dot |dot org |org Status|NEW |ASSIGNED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (3 preceding siblings ...) 2005-01-02 12:13 ` rakdver at gcc dot gnu dot org @ 2005-01-02 15:57 ` pinskia at gcc dot gnu dot org 2005-01-02 18:48 ` rakdver at gcc dot gnu dot org ` (8 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: pinskia at gcc dot gnu dot org @ 2005-01-02 15:57 UTC (permalink / raw) To: gcc-bugs -- What |Removed |Added ---------------------------------------------------------------------------- Keywords| |ice-on-valid-code, memory- | |hog Target Milestone|--- |4.0.0 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (4 preceding siblings ...) 2005-01-02 15:57 ` pinskia at gcc dot gnu dot org @ 2005-01-02 18:48 ` rakdver at gcc dot gnu dot org 2005-01-02 18:55 ` rakdver at gcc dot gnu dot org ` (7 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: rakdver at gcc dot gnu dot org @ 2005-01-02 18:48 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-02 18:48 ------- The loop probably is not infinite (after removing a few commands from the loop, compilation finishes after a long time). Investigating further. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (5 preceding siblings ...) 2005-01-02 18:48 ` rakdver at gcc dot gnu dot org @ 2005-01-02 18:55 ` rakdver at gcc dot gnu dot org 2005-01-02 20:37 ` sebastian dot pop at cri dot ensmp dot fr ` (6 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: rakdver at gcc dot gnu dot org @ 2005-01-02 18:55 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-02 18:55 ------- Caused by an exponential time complexity of instantiate_parameters. I am working on a patch. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (6 preceding siblings ...) 2005-01-02 18:55 ` rakdver at gcc dot gnu dot org @ 2005-01-02 20:37 ` sebastian dot pop at cri dot ensmp dot fr 2005-01-02 20:56 ` rakdver at atrey dot karlin dot mff dot cuni dot cz ` (5 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: sebastian dot pop at cri dot ensmp dot fr @ 2005-01-02 20:37 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr 2005-01-02 20:37 ------- (In reply to comment #5) > Caused by an exponential time complexity of instantiate_parameters. > I am working on a patch. The following patch solves the exponential time complexity. Sorry for the inconvenient. Sebastian *************** instantiate_parameters_1 (struct loop *l *** 1946,1960 **** result again. Avoid the cyclic instantiation in mixers. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); ! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs); bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); return res; case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), allow_superloop_chrecs); if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); --- 2005,2026 ---- result again. Avoid the cyclic instantiation in mixers. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); ! if (res != chrec_dont_know) ! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs); bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); return res; case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1963,1970 **** --- 2029,2042 ---- case PLUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1973,1980 **** --- 2045,2058 ---- case MINUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1983,1990 **** --- 2061,2074 ---- case MULT_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 2018,2027 **** --- 2102,2120 ---- case 3: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), allow_superloop_chrecs); + if (op2 == chrec_dont_know) + return chrec_dont_know; + if (op0 == chrec_dont_know || op1 == chrec_dont_know || op2 == chrec_dont_know) *************** instantiate_parameters_1 (struct loop *l *** 2038,2047 **** case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); ! if (op0 == chrec_dont_know ! || op1 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0) --- 2131,2142 ---- case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); ! if (op1 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0) -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (7 preceding siblings ...) 2005-01-02 20:37 ` sebastian dot pop at cri dot ensmp dot fr @ 2005-01-02 20:56 ` rakdver at atrey dot karlin dot mff dot cuni dot cz 2005-01-02 21:46 ` sebastian dot pop at cri dot ensmp dot fr ` (4 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: rakdver at atrey dot karlin dot mff dot cuni dot cz @ 2005-01-02 20:56 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz 2005-01-02 20:56 ------- Subject: Re: [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? > (In reply to comment #5) > > Caused by an exponential time complexity of instantiate_parameters. > > I am working on a patch. > > The following patch solves the exponential time complexity. not really (well, maybe in this particular case, but not in general). Your patch definitely helps (and you should submit it anyway), but yhe problem is that even with your patch it may happen that instantiate_parameters is called recursively several times for one ssa name if the expression contains it several times, and if this happens for several expressions in a row, you get the exponential complexity. I am just testing the patch below that caches the results to avoid this problem. Index: tree-scalar-evolution.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v retrieving revision 2.14 diff -c -3 -p -r2.14 tree-scalar-evolution.c *** tree-scalar-evolution.c 31 Dec 2004 18:03:28 -0000 2.14 --- tree-scalar-evolution.c 2 Jan 2005 20:31:01 -0000 *************** analyze_scalar_evolution_in_loop (struct *** 1888,1906 **** } } /* Analyze all the parameters of the chrec that were left under a symbolic form, with respect to LOOP. CHREC is the chrec to instantiate. If ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with ! outer loop chrecs is done. */ static tree instantiate_parameters_1 (struct loop *loop, tree chrec, ! bool allow_superloop_chrecs) { tree res, op0, op1, op2; basic_block def_bb; struct loop *def_loop; ! if (chrec == NULL_TREE || automatically_generated_chrec_p (chrec)) return chrec; --- 1888,1942 ---- } } + /* Returns instantiated value for VERSION in CACHE. */ + + static tree + get_instantiated_value (htab_t cache, tree version) + { + struct scev_info_str *info, pattern; + + pattern.var = version; + info = htab_find (cache, &pattern); + + if (info) + return info->chrec; + else + return NULL_TREE; + } + + /* Sets instantiated value for VERSION to VAL in CACHE. */ + + static void + set_instantiated_value (htab_t cache, tree version, tree val) + { + struct scev_info_str *info, pattern; + PTR *slot; + + pattern.var = version; + slot = htab_find_slot (cache, &pattern, INSERT); + + if (*slot) + info = *slot; + else + info = *slot = new_scev_info_str (version); + info->chrec = val; + } + /* Analyze all the parameters of the chrec that were left under a symbolic form, with respect to LOOP. CHREC is the chrec to instantiate. If ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with ! outer loop chrecs is done. CACHE is the cache of already instantiated ! values. */ static tree instantiate_parameters_1 (struct loop *loop, tree chrec, ! bool allow_superloop_chrecs, ! htab_t cache) { tree res, op0, op1, op2; basic_block def_bb; struct loop *def_loop; ! if (chrec == NULL_TREE || automatically_generated_chrec_p (chrec)) return chrec; *************** instantiate_parameters_1 (struct loop *l *** 1920,1960 **** && !flow_bb_inside_loop_p (loop, def_bb))) return chrec; ! /* Don't instantiate the SSA_NAME if it is in a mixer structure. This is used for avoiding the instantiation of recursively defined functions, such as: | a_2 -> {0, +, 1, +, a_2}_1 */ ! if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec))) ! { ! if (!flow_bb_inside_loop_p (loop, def_bb)) ! { ! /* We may keep the loop invariant in symbolic form. */ ! return chrec; ! } ! else ! { ! /* Something with unknown behavior in LOOP. */ ! return chrec_dont_know; ! } ! } def_loop = find_common_loop (loop, def_bb->loop_father); /* If the analysis yields a parametric chrec, instantiate the ! result again. Avoid the cyclic instantiation in mixers. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); ! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs); bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); return res; case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), ! allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), ! allow_superloop_chrecs); if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); --- 1956,2007 ---- && !flow_bb_inside_loop_p (loop, def_bb))) return chrec; ! /* We cache the value of instantiated variable to avoid exponential ! time complexity due to reevaluations. We also store the convenient ! value in the cache in order to prevent infinite recursion -- we do ! not want to instantiate the SSA_NAME if it is in a mixer structure. This is used for avoiding the instantiation of recursively defined functions, such as: | a_2 -> {0, +, 1, +, a_2}_1 */ ! ! res = get_instantiated_value (cache, chrec); ! if (res) ! return res; ! ! /* Store the convenient value for chrec in the structure. If it ! is defined outside of the loop, we may just leave it in symbolic ! form, otherwise we need to admit that we do not know its behavior ! inside the loop. */ ! res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know; ! set_instantiated_value (cache, chrec, res); ! ! /* To make things even more complicated, instantiate_parameters_1 ! calls analyze_scalar_evolution that may call # of iterations ! analysis that may in turn call instantiate_parameters_1 again. ! To prevent the infinite recursion, keep also the bitmap of ! ssa names that are being instantiated globally. */ if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec))) ! return res; def_loop = find_common_loop (loop, def_bb->loop_father); /* If the analysis yields a parametric chrec, instantiate the ! result again. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); ! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs, cache); bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); + + /* Store the correct value to the cache. */ + set_instantiated_value (cache, chrec, res); return res; case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), ! allow_superloop_chrecs, cache); op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), ! allow_superloop_chrecs, cache); if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1962,1970 **** case PLUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), ! allow_superloop_chrecs); if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1); --- 2009,2017 ---- case PLUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs, cache); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), ! allow_superloop_chrecs, cache); if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1972,1980 **** case MINUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), ! allow_superloop_chrecs); if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1); --- 2019,2027 ---- case MINUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs, cache); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), ! allow_superloop_chrecs, cache); if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1982,1990 **** case MULT_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), ! allow_superloop_chrecs); if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1); --- 2029,2037 ---- case MULT_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs, cache); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), ! allow_superloop_chrecs, cache); if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1994,2000 **** case CONVERT_EXPR: case NON_LVALUE_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs); if (op0 == chrec_dont_know) return chrec_dont_know; --- 2041,2047 ---- case CONVERT_EXPR: case NON_LVALUE_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs, cache); if (op0 == chrec_dont_know) return chrec_dont_know; *************** instantiate_parameters_1 (struct loop *l *** 2017,2027 **** { case 3: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), ! allow_superloop_chrecs); op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), ! allow_superloop_chrecs); if (op0 == chrec_dont_know || op1 == chrec_dont_know || op2 == chrec_dont_know) --- 2064,2074 ---- { case 3: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs, cache); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), ! allow_superloop_chrecs, cache); op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), ! allow_superloop_chrecs, cache); if (op0 == chrec_dont_know || op1 == chrec_dont_know || op2 == chrec_dont_know) *************** instantiate_parameters_1 (struct loop *l *** 2037,2045 **** case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), ! allow_superloop_chrecs); if (op0 == chrec_dont_know || op1 == chrec_dont_know) return chrec_dont_know; --- 2084,2092 ---- case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs, cache); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), ! allow_superloop_chrecs, cache); if (op0 == chrec_dont_know || op1 == chrec_dont_know) return chrec_dont_know; *************** instantiate_parameters_1 (struct loop *l *** 2051,2057 **** case 1: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs); if (op0 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0)) --- 2098,2104 ---- case 1: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), ! allow_superloop_chrecs, cache); if (op0 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0)) *************** instantiate_parameters (struct loop *loo *** 2078,2083 **** --- 2125,2131 ---- tree chrec) { tree res; + htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); if (dump_file && (dump_flags & TDF_DETAILS)) { *************** instantiate_parameters (struct loop *loo *** 2088,2094 **** fprintf (dump_file, ")\n"); } ! res = instantiate_parameters_1 (loop, chrec, true); if (dump_file && (dump_flags & TDF_DETAILS)) { --- 2136,2142 ---- fprintf (dump_file, ")\n"); } ! res = instantiate_parameters_1 (loop, chrec, true, cache); if (dump_file && (dump_flags & TDF_DETAILS)) { *************** instantiate_parameters (struct loop *loo *** 2096,2101 **** --- 2144,2151 ---- print_generic_expr (dump_file, res, 0); fprintf (dump_file, "))\n"); } + + htab_delete (cache); return res; } *************** instantiate_parameters (struct loop *loo *** 2106,2112 **** static tree resolve_mixers (struct loop *loop, tree chrec) { ! return instantiate_parameters_1 (loop, chrec, false); } /* Entry point for the analysis of the number of iterations pass. --- 2156,2165 ---- static tree resolve_mixers (struct loop *loop, tree chrec) { ! htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); ! tree ret = instantiate_parameters_1 (loop, chrec, false, cache); ! htab_delete (cache); ! return ret; } /* Entry point for the analysis of the number of iterations pass. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (8 preceding siblings ...) 2005-01-02 20:56 ` rakdver at atrey dot karlin dot mff dot cuni dot cz @ 2005-01-02 21:46 ` sebastian dot pop at cri dot ensmp dot fr 2005-01-02 23:15 ` sebastian dot pop at cri dot ensmp dot fr ` (3 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: sebastian dot pop at cri dot ensmp dot fr @ 2005-01-02 21:46 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr 2005-01-02 21:46 ------- (In reply to comment #7) > Subject: Re: [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? > > not really (well, maybe in this particular case, but not in general). > Your patch definitely helps (and you should submit it anyway), but > yhe problem is that even with your patch it may happen that > instantiate_parameters is called recursively several times for one > ssa name if the expression contains it several times, and if this > happens for several expressions in a row, you get the exponential > complexity. I am just testing the patch below that caches the results > to avoid this problem. > Richtig. I'm just speeding the chrec_dont_know case, whereas your patch solves the more general problem of huge expressions that have to be instantiated and that don't necessarily lead to unknown evolutions. Thanks. PS: I'll test my patch separately and will post it to gcc-patches. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (9 preceding siblings ...) 2005-01-02 21:46 ` sebastian dot pop at cri dot ensmp dot fr @ 2005-01-02 23:15 ` sebastian dot pop at cri dot ensmp dot fr 2005-01-02 23:19 ` rakdver at gcc dot gnu dot org ` (2 subsequent siblings) 13 siblings, 0 replies; 15+ messages in thread From: sebastian dot pop at cri dot ensmp dot fr @ 2005-01-02 23:15 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr 2005-01-02 23:15 ------- Subject: Re: [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? rakdver at gcc dot gnu dot org wrote: > > ------- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-02 18:55 ------- > Caused by an exponential time complexity of instantiate_parameters. > I am working on a patch. > The following patch solves the exponential time complexity. Sorry for the inconvenient. Sebastian *************** instantiate_parameters_1 (struct loop *l *** 1946,1960 **** result again. Avoid the cyclic instantiation in mixers. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); ! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs); bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); return res; case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), allow_superloop_chrecs); if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); --- 2005,2026 ---- result again. Avoid the cyclic instantiation in mixers. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); ! if (res != chrec_dont_know) ! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs); bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); return res; case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1963,1970 **** --- 2029,2042 ---- case PLUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1973,1980 **** --- 2045,2058 ---- case MINUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 1983,1990 **** --- 2061,2074 ---- case MULT_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1); *************** instantiate_parameters_1 (struct loop *l *** 2018,2027 **** --- 2102,2120 ---- case 3: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); + if (op1 == chrec_dont_know) + return chrec_dont_know; + op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), allow_superloop_chrecs); + if (op2 == chrec_dont_know) + return chrec_dont_know; + if (op0 == chrec_dont_know || op1 == chrec_dont_know || op2 == chrec_dont_know) *************** instantiate_parameters_1 (struct loop *l *** 2038,2047 **** case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); ! if (op0 == chrec_dont_know ! || op1 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0) --- 2131,2142 ---- case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), allow_superloop_chrecs); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), allow_superloop_chrecs); ! if (op1 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0) -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (10 preceding siblings ...) 2005-01-02 23:15 ` sebastian dot pop at cri dot ensmp dot fr @ 2005-01-02 23:19 ` rakdver at gcc dot gnu dot org 2005-01-09 8:22 ` cvs-commit at gcc dot gnu dot org 2005-01-09 15:56 ` pinskia at gcc dot gnu dot org 13 siblings, 0 replies; 15+ messages in thread From: rakdver at gcc dot gnu dot org @ 2005-01-02 23:19 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-02 23:19 ------- http://gcc.gnu.org/ml/gcc-patches/2005-01/msg00052.html -- What |Removed |Added ---------------------------------------------------------------------------- Keywords| |patch http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (11 preceding siblings ...) 2005-01-02 23:19 ` rakdver at gcc dot gnu dot org @ 2005-01-09 8:22 ` cvs-commit at gcc dot gnu dot org 2005-01-09 15:56 ` pinskia at gcc dot gnu dot org 13 siblings, 0 replies; 15+ messages in thread From: cvs-commit at gcc dot gnu dot org @ 2005-01-09 8:22 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From cvs-commit at gcc dot gnu dot org 2005-01-09 08:22 ------- Subject: Bug 19224 CVSROOT: /cvs/gcc Module name: gcc Changes by: rakdver@gcc.gnu.org 2005-01-09 08:22:15 Modified files: gcc : ChangeLog tree-scalar-evolution.c Log message: PR tree-optimization/19224 * tree-scalar-evolution.c (get_instantiated_value, set_instantiated_value): New functions. (instantiate_parameters_1): Cache the results. (instantiate_parameters, resolve_mixers): Initialize and free the cache. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7072&r2=2.7073 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-scalar-evolution.c.diff?cvsroot=gcc&r1=2.14&r2=2.15 -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org ` (12 preceding siblings ...) 2005-01-09 8:22 ` cvs-commit at gcc dot gnu dot org @ 2005-01-09 15:56 ` pinskia at gcc dot gnu dot org 13 siblings, 0 replies; 15+ messages in thread From: pinskia at gcc dot gnu dot org @ 2005-01-09 15:56 UTC (permalink / raw) To: gcc-bugs ------- Additional Comments From pinskia at gcc dot gnu dot org 2005-01-09 15:56 ------- Fixed. -- What |Removed |Added ---------------------------------------------------------------------------- Status|ASSIGNED |RESOLVED Resolution| |FIXED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224 ^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2005-01-09 15:56 UTC | newest] Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2005-01-02 7:44 [Bug tree-optimization/19224] New: Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)? aj at gcc dot gnu dot org 2005-01-02 7:45 ` [Bug tree-optimization/19224] " aj at gcc dot gnu dot org 2005-01-02 11:53 ` [Bug tree-optimization/19224] [4.0 regression] " steven at gcc dot gnu dot org 2005-01-02 12:05 ` aj at gcc dot gnu dot org 2005-01-02 12:13 ` rakdver at gcc dot gnu dot org 2005-01-02 15:57 ` pinskia at gcc dot gnu dot org 2005-01-02 18:48 ` rakdver at gcc dot gnu dot org 2005-01-02 18:55 ` rakdver at gcc dot gnu dot org 2005-01-02 20:37 ` sebastian dot pop at cri dot ensmp dot fr 2005-01-02 20:56 ` rakdver at atrey dot karlin dot mff dot cuni dot cz 2005-01-02 21:46 ` sebastian dot pop at cri dot ensmp dot fr 2005-01-02 23:15 ` sebastian dot pop at cri dot ensmp dot fr 2005-01-02 23:19 ` rakdver at gcc dot gnu dot org 2005-01-09 8:22 ` cvs-commit at gcc dot gnu dot org 2005-01-09 15:56 ` pinskia 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).