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

[Victor Kaplansky]

Sebastian,

your patch worked for my original example, but gcc still fails to
calculate niter when counters are signed integers:

      1 int
      2 foo (short *in, short *out)
      3 {
      4   int i;
      5   int N;
      6   int M;
      7   int acc;
      8
      9   for (N = 0; N < 16; N++)
     10     {
     11       M = 500 - N;
     12       acc = 0;
     13
     14       for (i = 0; i < M; i++)
     15         {
     16           acc += in[i];
     17         }
     18
     19       out[N] = (short) acc;
     20     }
     21
     22   return acc;
     23 }

Can your patch to be modified to work with autovect branch as well?
-- Victor


Sebastian Pop <sebastian.pop@cri.ensmp.fr> wrote on 19.06.2006 11:42:33:

> 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);
>
>
>