This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Fix PR40460, exponential behavior in SCEV


This fixes another exponential behavior in SCEV.  The issue is that
we create arbitrarily complex exponential CHRECs during
chrec_fold_multiply_poly_poly because we do not bail out from
build_polynomial_chrec with the no_evolution_in_loop_p test if
that cannot compute its property.

Maybe the following is then the correct fix.

Bootstrapped on x86_64-unknown-linux-gnu, tests still running.

Sebastian, does this look like the correct approach?  (See the PR
for more details).

Thanks,
Richard.


2009-06-16  Richard Guenther  <rguenther@suse.de>

	PR middle-end/40460
	* tree-chrec.h (build_polynomial_chrec): If we cannot determine
	if there is no evolution of left in the loop bail out.
	* tree-chrec.c (chrec_fold_multiply_poly_poly): CSE one
	chrec_fold_multiply.

	* g++.dg/torture/pr40460.C: New testcase.

Index: gcc/tree-chrec.h
===================================================================
*** gcc/tree-chrec.h	(revision 148523)
--- gcc/tree-chrec.h	(working copy)
*************** build_polynomial_chrec (unsigned loop_nu
*** 132,138 ****
        || right == chrec_dont_know)
      return chrec_dont_know;
  
!   if (no_evolution_in_loop_p (left, loop_num, &val) && !val)
      return chrec_dont_know;
  
    /* Pointer types should occur only on the left hand side, i.e. in
--- 132,139 ----
        || right == chrec_dont_know)
      return chrec_dont_know;
  
!   if (!no_evolution_in_loop_p (left, loop_num, &val)
!       || !val)
      return chrec_dont_know;
  
    /* Pointer types should occur only on the left hand side, i.e. in
Index: gcc/tree-chrec.c
===================================================================
*** gcc/tree-chrec.c	(revision 148523)
--- gcc/tree-chrec.c	(working copy)
*************** chrec_fold_multiply_poly_poly (tree type
*** 220,235 ****
    /* "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, SCALAR_FLOAT_TYPE_P (type)
  			    ? build_real (type, dconst2)
  			    : build_int_cst (type, 2), t2);
--- 220,235 ----
    /* "a*c".  */
    t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
  
!   /* "a*d + b*c".  */
    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)));
!   /* "b*d".  */
    t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
+   /* "a*d + b*c + b*d".  */
+   t1 = chrec_fold_plus (type, t1, t2);
+   /* "2*b*d".  */
    t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
  			    ? build_real (type, dconst2)
  			    : build_int_cst (type, 2), t2);
Index: gcc/testsuite/g++.dg/torture/pr40460.C
===================================================================
*** gcc/testsuite/g++.dg/torture/pr40460.C	(revision 0)
--- gcc/testsuite/g++.dg/torture/pr40460.C	(revision 0)
***************
*** 0 ****
--- 1,9 ----
+ /* { dg-do compile } */
+ 
+ void bar(int);
+ void foo(void)
+ {
+   for (int i = 0; i<1; ++i)
+     bar (i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i*i);
+ }
+ 


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]