[Bug tree-optimization/22442] New: scev cprop causes wrong code

[Bug tree-optimization/22442] New: scev cprop causes wrong code

[belyshev at depni dot sinp dot msu dot ru]

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

*/

-- 
           Summary: scev cprop causes wrong code
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: critical
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: belyshev at depni dot sinp dot msu dot ru
                CC: gcc-bugs at gcc dot gnu dot org,rakdver at gcc dot gnu
                    dot org
GCC target triplet: x86_64-*-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22442

[Bug tree-optimization/22442] [4.1 regression] scev cprop causes wrong code

[belyshev at depni dot sinp dot msu dot ru]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
 GCC target triplet|x86_64-*-linux-gnu          |
      Known to fail|                            |4.1.0
      Known to work|                            |4.0.1
            Summary|scev cprop causes wrong code|[4.1 regression] scev cprop
                   |                            |causes wrong code
   Target Milestone|---                         |4.1.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22442

[Bug tree-optimization/22442] [4.1 regression] scev cprop causes wrong code

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2005-07-12 14:58 -------
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.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22442

[Bug tree-optimization/22442] [4.1 regression] scev cprop causes wrong code

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-07-12 14:59 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |spop at gcc dot gnu dot org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-07-12 14:59:52
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22442

[Bug tree-optimization/22442] [4.1 regression] scev cprop causes wrong code

[rakdver at gcc dot gnu dot org]

-- 
           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=22442

[Bug tree-optimization/22442] [4.1 regression] scev cprop causes wrong code

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2005-07-12 15:14 -------
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



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22442

[Bug tree-optimization/22442] [4.1 regression] scev cprop causes wrong code

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-07-13 10:08 -------
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



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22442

[Bug tree-optimization/22442] [4.1 regression] scev cprop causes wrong code

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-07-13 10:37 -------
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



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22442

[Bug tree-optimization/22442] [4.1 regression] scev cprop causes wrong code

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2005-07-13 10:38 -------
Fixed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22442