2012-04-12 Richard Guenther <rguenther@suse.de>

	PR tree-optimization/52943
	* tree-chrec.h (chrec_is_positive): Remove.
	* tree-scalar-evolution.c (chrec_is_positive): Move ...
	* tree-data-ref.c (chrec_is_positive): ... here.  Make static.
	Return false for a constant zero instead of negative.
	(analyze_siv_subscript_cst_affine): Handle zero difference
	in the initial condition explicitely.

	* gcc.dg/torture/pr52943.c: New testcase.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/gcc-4_7-branch@186377 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a8d3d59..6f030d0 100644 (file)
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2012-04-12  Richard Guenther  <rguenther@suse.de>
+
+       PR tree-optimization/52943
+       * tree-chrec.h (chrec_is_positive): Remove.
+       * tree-scalar-evolution.c (chrec_is_positive): Move ...
+       * tree-data-ref.c (chrec_is_positive): ... here.  Make static.
+       Return false for a constant zero instead of negative.
+       (analyze_siv_subscript_cst_affine): Handle zero difference
+       in the initial condition explicitely.
+

 2012-04-10  John David Anglin  <dave.anglin@nrc-cnrc.gc.ca>
 
        PR middle-end/52894
 2012-04-10  John David Anglin  <dave.anglin@nrc-cnrc.gc.ca>
 
        PR middle-end/52894

diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index cf750f5..032a013 100644 (file)
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2012-04-12  Richard Guenther  <rguenther@suse.de>
+
+       PR tree-optimization/52943
+       * gcc.dg/torture/pr52943.c: New testcase.
+

 2012-04-09  Mike Stump  <mikestump@comcast.net>
 
        * g++.dg/cpp0x/udlit-raw-op.C: Don't use CRLF endings.
 2012-04-09  Mike Stump  <mikestump@comcast.net>
 
        * g++.dg/cpp0x/udlit-raw-op.C: Don't use CRLF endings.

diff --git a/gcc/testsuite/gcc.dg/torture/pr52943.c b/gcc/testsuite/gcc.dg/torture/pr52943.c
new file mode 100644 (file)
index 0000000..da35c9d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr52943.c
@@ -0,0 +1,20 @@
+/* { dg-do run } */
+
+extern void abort (void);
+int a[] = { 0, 0, 0, 6 };
+
+int b;
+int
+main ()
+{
+  for (;;)
+    {
+      b = 3;
+      for (; b; b -= 1)
+       a[b] = a[3] > 1;
+      break;
+    }
+  if (a[1] != 0)
+    abort ();
+  return 0;
+}

diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h
index bf9bff0..8367802 100644 (file)
--- a/gcc/tree-chrec.h
+++ b/gcc/tree-chrec.h
@@ -77,7 +77,6 @@ extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *);
 /* Observers.  */
 extern bool eq_evolutions_p (const_tree, const_tree);
 extern bool is_multivariate_chrec (const_tree);
 /* Observers.  */
 extern bool eq_evolutions_p (const_tree, const_tree);
 extern bool is_multivariate_chrec (const_tree);

-extern bool chrec_is_positive (tree, bool *);

 extern bool chrec_contains_symbols (const_tree);
 extern bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned);
 extern bool chrec_contains_undetermined (const_tree);
 extern bool chrec_contains_symbols (const_tree);
 extern bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned);
 extern bool chrec_contains_undetermined (const_tree);

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 0e98fb4..4d2572a 100644 (file)
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1753,6 +1753,76 @@ max_stmt_executions_tree (struct loop *loop)
   return double_int_to_tree (unsigned_type_node, nit);
 }
 
   return double_int_to_tree (unsigned_type_node, nit);
 }
 

+/* Determine whether the CHREC is always positive/negative.  If the expression
+   cannot be statically analyzed, return false, otherwise set the answer into
+   VALUE.  */
+
+static bool
+chrec_is_positive (tree chrec, bool *value)
+{
+  bool value0, value1, value2;
+  tree end_value, nb_iter;
+
+  switch (TREE_CODE (chrec))
+    {
+    case POLYNOMIAL_CHREC:
+      if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
+         || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
+       return false;
+
+      /* FIXME -- overflows.  */
+      if (value0 == value1)
+       {
+         *value = value0;
+         return true;
+       }
+
+      /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
+        and the proof consists in showing that the sign never
+        changes during the execution of the loop, from 0 to
+        loop->nb_iterations.  */
+      if (!evolution_function_is_affine_p (chrec))
+       return false;
+
+      nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
+      if (chrec_contains_undetermined (nb_iter))
+       return false;
+
+#if 0
+      /* TODO -- If the test is after the exit, we may decrease the number of
+        iterations by one.  */
+      if (after_exit)
+       nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
+#endif
+
+      end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
+
+      if (!chrec_is_positive (end_value, &value2))
+       return false;
+
+      *value = value0;
+      return value0 == value1;
+
+    case INTEGER_CST:
+      switch (tree_int_cst_sgn (chrec))
+       {
+       case -1:
+         *value = false;
+         break;
+       case 1:
+         *value = true;
+         break;
+       default:
+         return false;
+       }
+      return true;
+
+    default:
+      return false;
+    }
+}
+
+

 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
    *OVERLAPS_B are initialized to the functions that describe the
 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
    *OVERLAPS_B are initialized to the functions that describe the


@@ -1776,6 +1846,15 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
   chrec_b = chrec_convert (type, chrec_b, NULL);
   difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
 
   chrec_b = chrec_convert (type, chrec_b, NULL);
   difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
 

+  /* Special case overlap in the first iteration.  */
+  if (integer_zerop (difference))
+    {
+      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+      *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+      *last_conflicts = integer_one_node;
+      return;
+    }
+

   if (!chrec_is_positive (initial_condition (difference), &value0))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
   if (!chrec_is_positive (initial_condition (difference), &value0))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))

diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index 2077c8d..06fd39e 100644 (file)
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -499,65 +499,6 @@ compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
     return chrec_dont_know;
 }
 
     return chrec_dont_know;
 }
 

-/* Determine whether the CHREC is always positive/negative.  If the expression
-   cannot be statically analyzed, return false, otherwise set the answer into
-   VALUE.  */
-
-bool
-chrec_is_positive (tree chrec, bool *value)
-{
-  bool value0, value1, value2;
-  tree end_value, nb_iter;
-
-  switch (TREE_CODE (chrec))
-    {
-    case POLYNOMIAL_CHREC:
-      if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
-         || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
-       return false;
-
-      /* FIXME -- overflows.  */
-      if (value0 == value1)
-       {
-         *value = value0;
-         return true;
-       }
-
-      /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
-        and the proof consists in showing that the sign never
-        changes during the execution of the loop, from 0 to
-        loop->nb_iterations.  */
-      if (!evolution_function_is_affine_p (chrec))
-       return false;
-
-      nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
-      if (chrec_contains_undetermined (nb_iter))
-       return false;
-
-#if 0
-      /* TODO -- If the test is after the exit, we may decrease the number of
-        iterations by one.  */
-      if (after_exit)
-       nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
-#endif
-
-      end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
-
-      if (!chrec_is_positive (end_value, &value2))
-       return false;
-
-      *value = value0;
-      return value0 == value1;
-
-    case INTEGER_CST:
-      *value = (tree_int_cst_sgn (chrec) == 1);
-      return true;
-
-    default:
-      return false;
-    }
-}
-

 /* Associate CHREC to SCALAR.  */
 
 static void
 /* Associate CHREC to SCALAR.  */
 
 static void