Bug 22442 - [4.1 regression] scev cprop causes wrong code
Summary: [4.1 regression] scev cprop causes wrong code
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.1.0
: P2 critical
Target Milestone: 4.1.0
Assignee: Zdenek Dvorak
URL:
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2005-07-12 14:20 UTC by Serge Belyshev
Modified: 2005-07-13 10:38 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.0.1
Known to fail: 4.1.0
Last reconfirmed: 2005-07-12 14:59:52


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Serge Belyshev 2005-07-12 14:20:54 UTC
// 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.

*/
Comment 1 Zdenek Dvorak 2005-07-12 14:58:09 UTC
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.
Comment 2 Andrew Pinski 2005-07-12 14:59:52 UTC
Confirmed.
Comment 3 Zdenek Dvorak 2005-07-12 15:14:17 UTC
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

Comment 4 CVS Commits 2005-07-13 10:08:48 UTC
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

Comment 5 CVS Commits 2005-07-13 10:37:30 UTC
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

Comment 6 Zdenek Dvorak 2005-07-13 10:38:11 UTC
Fixed.