[PATCH] Fix PR52943

[Richard Guenther <rguenther at suse dot de>]

Data-dependence analysis gets analyzing a[3] vs. a[{3, +, -1}_1] wrong
where it claims there is no dependence.  That is because
analyze_siv_subscript_cst_affine uses chrec_is_positive to distinguish
cases but that returns "always negative" for zero (zero, in this case
being the distance between 3 and 3).  The following patch makes
chrec_is_positive fail for zero, which is neither positive nor
negative.  It also special-cases the zero distance case because it
can be handled independently on the direction or value of the increment.
For the questionable handling of 'zero' I moved chrec_is_positive to
a private place.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.  I will
apply this to the trunk and the 4.7 branch where this latent bug
shows up first.

Thanks,
Richard.

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.

Index: gcc/tree-chrec.h
===================================================================
*** gcc/tree-chrec.h	(revision 186372)
--- gcc/tree-chrec.h	(working copy)
*************** extern void for_each_scev_op (tree *, bo
*** 77,83 ****
  /* 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);
--- 77,82 ----
Index: gcc/tree-scalar-evolution.c
===================================================================
*** gcc/tree-scalar-evolution.c	(revision 186372)
--- gcc/tree-scalar-evolution.c	(working copy)
*************** compute_overall_effect_of_inner_loop (st
*** 501,565 ****
      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
--- 501,506 ----
Index: gcc/tree-data-ref.c
===================================================================
*** gcc/tree-data-ref.c	(revision 186372)
--- gcc/tree-data-ref.c	(working copy)
*************** max_stmt_executions_tree (struct loop *l
*** 1718,1723 ****
--- 1718,1793 ----
    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_siv_subscript_cst_affine (tree c
*** 1741,1746 ****
--- 1811,1825 ----
    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))
Index: gcc/testsuite/gcc.dg/torture/pr52943.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr52943.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr52943.c	(revision 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;
+ }