RFH and fix for PR32367

["Sebastian Pop" <sebpop at gmail dot com>]

Hi,

Here is a first fix for this bug.  The patch ensures that the initial
value is not varying in the loop in which we build the polynomial
evolution.  The number of cases that contained this pattern is small
enough, and it does not occur during the bootstrap of gcc, only the
following testcases triggered that pattern:
gcc.c-torture/compile/pr14692.c
gcc.dg/tree-ssa/predcom-5.c
gcc.dg/tree-ssa/tailrecursion-5.c
gfortran.dg/array_constructor_7.f90
gfortran.dg/stfunc_4.f90

The attached patch passed bootstrap and testing on i686-linux.
Committed to trunk.

A further fix would improve fold to distribute the multiplication in
the case of an (unsigned int) MULT_EXPR with a PLUS_EXPR already
casted to (unsigned int), i.e.

#0  fold_build2_stat (code=MULT_EXPR, type=0xb7c41000, op0=0xb7cda6a0,
op1=0xb7c32444) at ../../gcc/fold-const.c:12944
(gdb)  call debug_generic_expr (type)
unsigned int
(gdb)  call debug_generic_expr (op0)
(unsigned int) (n_20 + 65535)
(gdb)  call debug_generic_expr (op1)
4
(gdb)  call debug_generic_expr (tem)
(unsigned int) (n_20 + 65535) * 4

I would expect to see the result in "tem" to be:
(unsigned int) (n_20 * 4 + 262140)

As I'm not familiar with fold, I'd appreciate your help and suggestions
on how to implement this transform.

Thanks,
Sebastian

	PR tree-optimization/32367
	* tree-chrec.h (build_polynomial_chrec): Verify that the left hand side
	of the chrec has no evolution in that loop.
	* testsuite/gcc.dg/tree-ssa/pr32367.c: New.

Index: tree-chrec.h
===================================================================
--- tree-chrec.h	(revision 125854)
+++ tree-chrec.h	(working copy)
@@ -83,6 +83,7 @@ extern bool tree_contains_chrecs (tree, 
 extern bool evolution_function_is_affine_multivariate_p (tree, int);
 extern bool evolution_function_is_univariate_p (tree);
 extern unsigned nb_vars_in_chrec (tree);
+extern bool evolution_function_is_invariant_p (tree, int);
 
 /* Determines whether CHREC is equal to zero.  */
 
@@ -98,6 +99,24 @@ chrec_zerop (tree chrec)
   return false;
 }
 
+/* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.  
+   Set the result in RES and return true when the property can be computed.  */
+
+static inline bool
+no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
+{
+  tree scev;
+  
+  if (chrec == chrec_not_analyzed_yet
+      || chrec == chrec_dont_know
+      || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
+    return false;
+
+  scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
+  *res = !tree_is_chrec (scev);
+  return true;
+}
+
 /* Build a polynomial chain of recurrence.  */
 
 static inline tree 
@@ -105,10 +124,15 @@ build_polynomial_chrec (unsigned loop_nu
 			tree left, 
 			tree right)
 {
+  bool val;
+
   if (left == chrec_dont_know
       || right == chrec_dont_know)
     return chrec_dont_know;
 
+  if (no_evolution_in_loop_p (left, loop_num, &val) && !val)
+    return chrec_dont_know;
+
   if (POINTER_TYPE_P (TREE_TYPE (left)))
     gcc_assert (sizetype == TREE_TYPE (right));
   else
@@ -140,7 +164,6 @@ evolution_function_is_constant_p (tree c
     }
 }
 
-extern bool evolution_function_is_invariant_p (tree, int);
 /* Determine whether the given tree is an affine evolution function or not.  */
 
 static inline bool 
@@ -183,24 +206,6 @@ tree_does_not_contain_chrecs (tree expr)
   return !tree_contains_chrecs (expr, NULL);
 }
 
-/* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.  
-   Set the result in RES and return true when the property can be computed.  */
-
-static inline bool
-no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
-{
-  tree scev;
-  
-  if (chrec == chrec_not_analyzed_yet
-      || chrec == chrec_dont_know
-      || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
-    return false;
-
-  scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
-  *res = !tree_is_chrec (scev);
-  return true;
-}
-
 /* Returns the type of the chrec.  */
 
 static inline tree
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 125854)
+++ ChangeLog	(working copy)
@@ -1,3 +1,10 @@
+2007-04-11  Sebastian Pop  <sebpop@gmail.com>
+
+	PR tree-optimization/32367
+	* tree-chrec.h (build_polynomial_chrec): Verify that the left hand side 
+	of the chrec has no evolution in that loop.
+	* testsuite/gcc.dg/tree-ssa/pr32367.c: New.
+
 2007-06-19  Bob Wilson  <bob.wilson@acm.org>
 
 	* config/xtensa/xtensa.c: Include "df.h".
Index: testsuite/gcc.dg/tree-ssa/pr32367.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/pr32367.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/pr32367.c	(revision 0)
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+int BinomialCoefficientsInited = 0;
+int BinomialCoefficients[17 * 35];
+double Evaluate_TPat (void)
+{
+        unsigned short n, k;
+        if (BinomialCoefficientsInited == 0)
+        {
+                int *ptr = BinomialCoefficients;
+                for (n = 1; n <= 33; ++n)
+                {
+                        for (k = 1; k < n; ++k)
+                                ++ptr;
+                        *ptr = 1;
+                }
+        }
+}
+