Re: [patch] (-fstrict-overflow) optimize counted loops on signed iv

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> This allows to optimize loops like :
> for (i = start; i <= start+1; i++) ...

> -      niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
> -					iv1->base, iv0->base);

I sort of do not understand why you need this change.  fold is (or
should be) able to derive that start < start + 1, if the computation
is performed in TYPE_OVERFLOW_UNDEFINED type.

> Index: gcc/tree-ssa-loop-niter.c
> ===================================================================
> --- gcc/tree-ssa-loop-niter.c	(.../vendor/tags/4.3.20070209)	(revision 77)
> +++ gcc/tree-ssa-loop-niter.c	(.../branches/4.3_devs_loop_overflow)	(revision 77)
> @@ -169,6 +169,80 @@
>    return true;
>  }
>  
> +/* Checks whether the number of iterations is a constant value if iv1 is relative
> +   to iv0. If we are allowed to optimize overflows, it may be a constant when the
> +   control variable wraps.
> +   iv0 is the chrec for the initial value of the control variable.
> +   iv1 is the chrec for the stop value.
> +   Optimizes loops like (i = v; i <= v+cst; i++).  */
> +
> +static bool 
> +relative_count_iv (affine_iv *iv0, affine_iv *iv1)
> +{
> +  enum tree_code code_base0;
> +  enum tree_code code_base1;
> +
> +  tree op0 = iv0->base;
> +  tree op1 = iv1->base;
> +
> +  if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))
> +      || !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op1)))
> +    return false;
> +
> +  STRIP_SIGN_NOPS (op0);
> +  STRIP_SIGN_NOPS (op1);
> +
> +  code_base0 = TREE_CODE (op0);
> +  code_base1 = TREE_CODE (op1);
> +
> +  /* iv0 -> {a+cst, +/-, cst}, iv1 -> {a+cst, +/-, cst}.  */
> +  if ((code_base0 == PLUS_EXPR && code_base1 == PLUS_EXPR)
> +      || (code_base0 == MINUS_EXPR && code_base1 == MINUS_EXPR))
> +    {
> +      tree opb0 = TREE_OPERAND (op0, 0);
> +      tree opb1 = TREE_OPERAND (op1, 0);
> +
> +      STRIP_SIGN_NOPS (opb0);
> +      STRIP_SIGN_NOPS (opb1);
> +
> +      if (TREE_CODE (opb0) == SSA_NAME && TREE_CODE (opb1) == SSA_NAME
> +	  && SSA_NAME_DEF_STMT(opb0) == SSA_NAME_DEF_STMT(opb1)

you want to check opb0 == opb1, here.  Or more likely, not to check that
opb0 and opb1 are ssa names, and just use operand_equal_p

> +	  && TREE_CONSTANT (TREE_OPERAND (op0, 1))
> +	  && TREE_CONSTANT (TREE_OPERAND (op1, 1)))
> +	return true;


>  /* Checks whether we can determine the final value of the control variable
>     of the loop with ending condition IV0 < IV1 (computed in TYPE).
>     DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
> @@ -236,7 +310,8 @@
>      niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
>  				      niter->assumptions,
>  				      assumption);
> -  if (!integer_zerop (noloop))
> +
> +  if (!integer_zerop (noloop) && !relative_count_iv (iv0, iv1))
>      niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
>  				      niter->may_be_zero,
>  				      noloop);
> @@ -367,7 +442,8 @@
>    if (!integer_nonzerop (assumption))
>      niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
>  				      niter->assumptions, assumption);
> -  if (!integer_zerop (mbz))
> +
> +  if (!integer_zerop (mbz) && !relative_count_iv (iv0, iv1))
>      niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
>  				      niter->may_be_zero, mbz);
>  }
> @@ -413,8 +489,9 @@
>  	     
>  	 In both cases # of iterations is iv1->base - iv0->base, assuming that
>  	 iv1->base >= iv0->base.  */
> -      niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
> -					iv1->base, iv0->base);
> +      if (!relative_count_iv (iv0, iv1))
> +	niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
> +					  iv1->base, iv0->base);
>        niter->niter = delta;
>        return true;
>      }

Nevertheless, this looks just wrong.  relative_count_iv does not compare
the relative values of the bases of the induction variables, hence
this would also make you eliminate the the may_be_zero assumptions in
cases like

for (i = a + 17; i < a + 5; i++)

which is obviously wrong.

Zdenek