Bug 19224 - [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)?
Summary: [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolu...
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.0.0
: P2 normal
Target Milestone: 4.0.0
Assignee: Zdenek Dvorak
URL:
Keywords: ice-on-valid-code, memory-hog, patch
Depends on:
Blocks:
 
Reported: 2005-01-02 07:44 UTC by Andreas Jaeger
Modified: 2005-01-09 15:56 UTC (History)
3 users (show)

See Also:
Host: x86_64-linux-gnu
Target: x86_64-linux-gnu
Build: x86_64-linux-gnu
Known to work:
Known to fail:
Last reconfirmed: 2005-01-02 11:53:19


Attachments
Preprocessed source file (4.40 KB, text/plain)
2005-01-02 07:45 UTC, Andreas Jaeger
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Andreas Jaeger 2005-01-02 07:44:46 UTC
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
Comment 1 Andreas Jaeger 2005-01-02 07:45:30 UTC
Created attachment 7861 [details]
Preprocessed source file
Comment 2 Steven Bosscher 2005-01-02 11:53:19 UTC
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. 
 
Comment 3 Andreas Jaeger 2005-01-02 12:05:26 UTC
 
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); 
} 
 
Comment 4 Zdenek Dvorak 2005-01-02 18:48:16 UTC
The loop probably is not infinite (after removing a few commands from the loop,
compilation finishes after a long time).  Investigating further.
Comment 5 Zdenek Dvorak 2005-01-02 18:55:29 UTC
Caused by an exponential time complexity of instantiate_parameters.
I am working on a patch.
Comment 6 sebastian.pop@cri.ensmp.fr 2005-01-02 20:37:03 UTC
(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)
Comment 7 Zdenek Dvorak 2005-01-02 20:56:17 UTC
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.  
Comment 8 sebastian.pop@cri.ensmp.fr 2005-01-02 21:46:19 UTC
(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.
Comment 9 sebastian.pop@cri.ensmp.fr 2005-01-02 23:15:12 UTC
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)
Comment 11 GCC Commits 2005-01-09 08:22:39 UTC
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

Comment 12 Andrew Pinski 2005-01-09 15:56:24 UTC
Fixed.