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).