[autovect] [patch] vectorize in cases when number of iterations may be zero

[Sebastian Pop]

Sebastian Pop wrote:
> I have started on such a patch but didn't finished it last weekend.
> I'll try to get it done for Monday.
> 

Here is a possible patch for trunk.  While bootstrapping, there were
no "proved_one_more" outputs, but using this patch, the compiler
correctly proves the may_be_zero condition is false for your example.

Sebastian

	* tree-ssa-loop-niter.c (expand_simple_operations): Symetrically
	also check is_gimple_min_invariant for operand 0.
	(simplify_using_initial_conditions): Call may_contain_eq_values.
	* tree-chrec.c (may_contain_eq_values_aff_cst,
	may_contain_eq_values): New.
	* tree-chrec.h (may_contain_eq_values): Declared.

Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c	(revision 114678)
+++ tree-ssa-loop-niter.c	(working copy)
@@ -758,7 +758,8 @@ expand_simple_operations (tree expr)
       /* And increments and decrements by a constant are simple.  */
       && !((TREE_CODE (e) == PLUS_EXPR
 	    || TREE_CODE (e) == MINUS_EXPR)
-	   && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
+	   && (is_gimple_min_invariant (TREE_OPERAND (e, 0))
+	       || is_gimple_min_invariant (TREE_OPERAND (e, 1)))))
     return expr;
 
   return expand_simple_operations (e);
@@ -890,7 +891,7 @@ tree_simplify_using_condition (tree cond
 /* Tries to simplify EXPR using the conditions on entry to LOOP.
    Record the conditions used for simplification to CONDS_USED.
    Returns the simplified expression (or EXPR unchanged, if no
-   simplification was possible).*/
+   simplification was possible).  */
 
 static tree
 simplify_using_initial_conditions (struct loop *loop, tree expr,
@@ -928,6 +929,26 @@ simplify_using_initial_conditions (struc
       expr = exp;
     }
 
+  /* The test above can fail as the condition before the loop can have
+     been removed by VRP.  It is thus possible to prove more precise
+     informations by using the SCEV algorithm.  */
+  if (TREE_CODE (expr) == EQ_EXPR)
+    {
+      tree op0 = analyze_scalar_evolution (loop, TREE_OPERAND (expr, 0));
+      tree op1 = analyze_scalar_evolution (loop, TREE_OPERAND (expr, 1));
+
+      op0 = instantiate_parameters (loop, op0);
+      op1 = instantiate_parameters (loop, op1);
+
+      if (may_contain_eq_values (op0, op1))
+	return expr;
+      else
+	{
+	  fprintf (stderr, "\n proved_one_more \n");
+	  return boolean_false_node;
+	}
+    }
+
   return expr;
 }
 
Index: tree-chrec.c
===================================================================
--- tree-chrec.c	(revision 114678)
+++ tree-chrec.c	(working copy)
@@ -1386,3 +1386,80 @@ scev_direction (tree chrec)
   else
     return EV_DIR_GROWS;
 }
+
+/* Helper function.  CHREC0 is supposed to be an affine function,
+   CHREC1 a constant.  */
+
+static bool
+may_contain_eq_values_aff_cst (tree chrec0, tree chrec1)
+{
+  struct loop *loop = current_loops->parray[CHREC_VARIABLE (chrec0)];
+  tree niter = number_of_iterations_in_loop (loop);
+
+  gcc_assert (evolution_function_is_affine_p (chrec0));
+  gcc_assert (evolution_function_is_constant_p (chrec1));
+
+  if (niter && TREE_CODE (niter) == INTEGER_CST)
+    {
+      tree lb, ub;
+
+      switch (scev_direction (chrec0))
+	{
+	case EV_DIR_GROWS:
+	  lb = initial_condition (chrec0);
+	  ub = chrec_apply (CHREC_VARIABLE (chrec0), chrec0, niter);
+	  break;
+
+	case EV_DIR_DECREASES:
+	  ub = initial_condition (chrec0);
+	  lb = chrec_apply (CHREC_VARIABLE (chrec0), chrec0, niter);
+	  break;
+
+	default:
+	  return true;
+	}
+
+      if (zero_p (fold_build2 (GE_EXPR, boolean_type_node, lb, chrec1))
+	  && zero_p (fold_build2 (GE_EXPR, boolean_type_node, chrec1, ub)))
+	return true;
+      else
+	return false;
+    }
+
+  /* Conservative answer.  */
+  return true;
+}
+
+/* Returns true when at least one of the values of CHREC0 and CHREC1
+   is equal, or when it is impossible to determine this property.  */
+
+bool 
+may_contain_eq_values (tree chrec0, tree chrec1)
+{
+  bool cst0, cst1;
+
+  if (automatically_generated_chrec_p (chrec0)
+      || automatically_generated_chrec_p (chrec1))
+    return true;
+ 
+  cst0 = evolution_function_is_constant_p (chrec0);
+  cst1 = evolution_function_is_constant_p (chrec1);
+
+  if (cst0 && cst1)
+    {
+      if (zero_p (fold_build2 (EQ_EXPR, boolean_type_node, chrec0, chrec1)))
+	return true;
+      else
+	return false;
+    }
+
+  if (cst1 && evolution_function_is_affine_p (chrec0))
+    return may_contain_eq_values_aff_cst (chrec0, chrec1);
+
+  if (cst0 && evolution_function_is_affine_p (chrec1))
+    return may_contain_eq_values_aff_cst (chrec1, chrec0);
+
+  /* Conservative answer.  */
+  return true;
+}
+
Index: tree-chrec.h
===================================================================
--- tree-chrec.h	(revision 114678)
+++ tree-chrec.h	(working copy)
@@ -91,6 +91,7 @@ extern bool tree_contains_chrecs (tree, 
 extern bool evolution_function_is_affine_multivariate_p (tree);
 extern bool evolution_function_is_univariate_p (tree);
 extern unsigned nb_vars_in_chrec (tree);
+extern bool may_contain_eq_values (tree, tree);