// fork from bug 22230 // fails with -O1 // doesn't fail with -O1 -fno-tree-ccp -fno-tree-dominator-opts // introduced between 2005-05-17 2005-05-18 void abort (void); int main (void) { int a, i; for (i = 0; i < 5; i++) a = i * i; if (a != 16) abort (); return 0; } /* --- 2005-05-17/bug22230-5.c.t28.phiopt1 2005-07-12 17:40:19.000000000 +0400 +++ 2005-05-18/bug22230-5.c.t28.phiopt1 2005-07-12 17:40:32.000000000 +0400 @@ -1,6 +1,8 @@ ;; Function main (main) +Merging blocks 0 and 6 +Merging blocks 1 and 2 main () { int i; @@ -8,20 +10,15 @@ int D.1571; <bb 0>: - goto <bb 6> (<L6>); - # i_9 = PHI <i_1(2), i_3(6)>; + # i_9 = PHI <i_8(1), 0(0)>; <L0>:; a_7 = i_9 * i_9; i_8 = i_9 + 1; - - # a_2 = PHI <a_7(1)>; - # i_1 = PHI <i_8(1)>; -<L1>:; - if (i_1 <= 4) goto <L0>; else goto <L2>; + if (i_8 <= 4) goto <L0>; else goto <L2>; <L2>:; - if (a_2 != 16) goto <L3>; else goto <L4>; + if (a_7 != 16) goto <L3>; else goto <L4>; <L3>:; abort (); @@ -29,11 +26,6 @@ <L4>:; return 0; - # a_5 = PHI <a_4(0)>; - # i_3 = PHI <0(0)>; -<L6>:; - goto <bb 1> (<L0>); - } Caused by this patch: 2005-05-17 Zdenek Dvorak <dvorakz@suse.cz> * timevar.def (TV_SCEV_CONST): New timevar. * tree-optimize.c (init_tree_optimization_passes): Add pass_scev_cprop. * tree-pass.h (pass_scev_cprop): Declare. * tree-scalar-evolution.c (scev_const_prop): New function. * tree-scalar-evolution.h (scev_const_prop): Declare. * tree-ssa-loop.c (gate_scev_const_prop, pass_scev_cprop): New. * tree-cfg.c (replace_uses_by): Export. * tree-flow.h (replace_uses_by): Declare. */
Subject: Re: New: scev cprop causes wrong code > // fork from bug 22230 > // fails with -O1 > // doesn't fail with -O1 -fno-tree-ccp -fno-tree-dominator-opts > // introduced between 2005-05-17 2005-05-18 > > void abort (void); > > int main (void) > { > int a, i; > > for (i = 0; i < 5; i++) > a = i * i; > if (a != 16) > abort (); > return 0; > } this seems to be a bug in scev. It claims that evolution of a is {{0, +, 1}_1, +, 2}_1. However, the evolution should be {0, +, {1, +, 2}_1}_1, as far as I can tell.
Confirmed.
The following patch fixes the problem, I am just testing it: Index: tree-chrec.c =================================================================== RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v retrieving revision 2.21 diff -c -3 -p -r2.21 tree-chrec.c *** tree-chrec.c 25 Jun 2005 02:01:15 -0000 2.21 --- tree-chrec.c 12 Jul 2005 15:11:08 -0000 *************** chrec_fold_multiply_poly_poly (tree type *** 167,172 **** --- 167,175 ---- tree poly0, tree poly1) { + tree t0, t1, t2; + int var; + gcc_assert (poly0); gcc_assert (poly1); gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); *************** chrec_fold_multiply_poly_poly (tree type *** 191,218 **** /* poly0 and poly1 are two polynomials in the same variable, {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ ! return ! build_polynomial_chrec ! (CHREC_VARIABLE (poly0), ! build_polynomial_chrec ! (CHREC_VARIABLE (poly0), ! ! /* "a*c". */ ! chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)), ! ! /* "a*d + b*c + b*d". */ ! chrec_fold_plus ! (type, chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)), ! ! chrec_fold_plus ! (type, ! chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_LEFT (poly1)), ! chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1))))), ! ! /* "2*b*d". */ ! chrec_fold_multiply ! (type, build_int_cst (NULL_TREE, 2), ! chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)))); } /* When the operands are automatically_generated_chrec_p, the fold has --- 194,218 ---- /* poly0 and poly1 are two polynomials in the same variable, {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ ! ! /* "a*c". */ ! t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); ! ! /* "a*d + b*c + b*d". */ ! t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)); ! t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, ! CHREC_RIGHT (poly0), ! CHREC_LEFT (poly1))); ! t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, ! CHREC_RIGHT (poly0), ! CHREC_RIGHT (poly1))); ! /* "2*b*d". */ ! t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); ! t2 = chrec_fold_multiply (type, build_int_cst_type (type, 2), t2); ! ! var = CHREC_VARIABLE (poly0); ! return build_polynomial_chrec (var, t0, ! build_polynomial_chrec (var, t1, t2)); } /* When the operands are automatically_generated_chrec_p, the fold has
Subject: Bug 22442 CVSROOT: /cvs/gcc Module name: gcc Changes by: rakdver@gcc.gnu.org 2005-07-13 10:08:38 Modified files: gcc : ChangeLog tree-chrec.c Log message: PR tree-optimization/22442 * tree-chrec.c (chrec_fold_multiply_poly_poly): Associate chrecs correctly. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.9427&r2=2.9428 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-chrec.c.diff?cvsroot=gcc&r1=2.21&r2=2.22
Subject: Bug 22442 CVSROOT: /cvs/gcc Module name: gcc Changes by: rakdver@gcc.gnu.org 2005-07-13 10:37:25 Modified files: gcc/testsuite : ChangeLog Added files: gcc/testsuite/gcc.dg/tree-ssa: loop-11.c Log message: PR tree-optimizatio/22442 * gcc.dg/tree-ssa/loop-11.c: New test. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.5759&r2=1.5760 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/loop-11.c.diff?cvsroot=gcc&r1=NONE&r2=1.1
Fixed.