Improve niters brute force (PR tree-optimization/77975)

Hi!

As you know, this is mostly your patch, I've just added some comments,
testcase and a small optimization; I believe the fix is right, if next[j]
is constant in addition to val[j] (for both args or op[1-j] is constant),
the loop can have 0(1), 1(2) or infinite iterations, and we can just brute
force that one or 2 iterations to find out the outcome.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2017-03-09  Richard Biener  <rguenther@suse.de>
	    Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/77975
	* tree-ssa-loop-niter.c (get_base_for): Allow phi argument from latch
	edge to be constant.
	(get_val_for): For constant x return it.  Formatting fix.
	(loop_niter_by_eval): Avoid pointless looping if the next iteration
	would use the same bases as the current one.

	* gcc.dg/pr77975.c: New test.


	Jakub

On Thu, 9 Mar 2017, Jakub Jelinek wrote:

> Hi!
> 
> As you know, this is mostly your patch, I've just added some comments,
> testcase and a small optimization; I believe the fix is right, if next[j]
> is constant in addition to val[j] (for both args or op[1-j] is constant),
> the loop can have 0(1), 1(2) or infinite iterations, and we can just brute
> force that one or 2 iterations to find out the outcome.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Ok.

Thanks,
Richard.

> 2017-03-09  Richard Biener  <rguenther@suse.de>
> 	    Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/77975
> 	* tree-ssa-loop-niter.c (get_base_for): Allow phi argument from latch
> 	edge to be constant.
> 	(get_val_for): For constant x return it.  Formatting fix.
> 	(loop_niter_by_eval): Avoid pointless looping if the next iteration
> 	would use the same bases as the current one.
> 
> 	* gcc.dg/pr77975.c: New test.
> 
> --- gcc/tree-ssa-loop-niter.c.jj	2017-02-25 09:32:11.000000000 +0100
> +++ gcc/tree-ssa-loop-niter.c	2017-03-09 14:28:28.826948753 +0100
> @@ -2521,7 +2521,8 @@ chain_of_csts_start (struct loop *loop,
>     * the derivation of X consists only from operations with constants
>     * the initial value of the phi node is constant
>     * the value of the phi node in the next iteration can be derived from the
> -     value in the current iteration by a chain of operations with constants.
> +     value in the current iteration by a chain of operations with constants,
> +     or is also a constant
>  
>     If such phi node exists, it is returned, otherwise NULL is returned.  */
>  
> @@ -2541,13 +2542,11 @@ get_base_for (struct loop *loop, tree x)
>    init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
>    next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
>  
> -  if (TREE_CODE (next) != SSA_NAME)
> -    return NULL;
> -
>    if (!is_gimple_min_invariant (init))
>      return NULL;
>  
> -  if (chain_of_csts_start (loop, next) != phi)
> +  if (TREE_CODE (next) == SSA_NAME
> +      && chain_of_csts_start (loop, next) != phi)
>      return NULL;
>  
>    return phi;
> @@ -2556,6 +2555,7 @@ get_base_for (struct loop *loop, tree x)
>  /* Given an expression X, then
>  
>     * if X is NULL_TREE, we return the constant BASE.
> +   * if X is a constant, we return the constant X.
>     * otherwise X is a SSA name, whose value in the considered loop is derived
>       by a chain of operations with constant from a result of a phi node in
>       the header of the loop.  Then we return value of X when the value of the
> @@ -2570,6 +2570,8 @@ get_val_for (tree x, tree base)
>  
>    if (!x)
>      return base;
> +  else if (is_gimple_min_invariant (x))
> +    return x;
>  
>    stmt = SSA_NAME_DEF_STMT (x);
>    if (gimple_code (stmt) == GIMPLE_PHI)
> @@ -2584,11 +2586,9 @@ get_val_for (tree x, tree base)
>      return get_val_for (gimple_assign_rhs1 (stmt), base);
>    else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
>  	   && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
> -    {
> -      return fold_build1 (gimple_assign_rhs_code (stmt),
> -			  gimple_expr_type (stmt),
> -			  get_val_for (gimple_assign_rhs1 (stmt), base));
> -    }
> +    return fold_build1 (gimple_assign_rhs_code (stmt),
> +			gimple_expr_type (stmt),
> +			get_val_for (gimple_assign_rhs1 (stmt), base));
>    else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
>      {
>        tree rhs1 = gimple_assign_rhs1 (stmt);
> @@ -2687,6 +2687,7 @@ loop_niter_by_eval (struct loop *loop, e
>  
>        for (j = 0; j < 2; j++)
>  	{
> +	  aval[j] = val[j];
>  	  val[j] = get_val_for (next[j], val[j]);
>  	  if (!is_gimple_min_invariant (val[j]))
>  	    {
> @@ -2694,6 +2695,12 @@ loop_niter_by_eval (struct loop *loop, e
>  	      return chrec_dont_know;
>  	    }
>  	}
> +
> +      /* If the next iteration would use the same base values
> +	 as the current one, there is no point looping further,
> +	 all following iterations will be the same as this one.  */
> +      if (val[0] == aval[0] && val[1] == aval[1])
> +	break;
>      }
>  
>    fold_undefer_and_ignore_overflow_warnings ();
> --- gcc/testsuite/gcc.dg/pr77975.c.jj	2017-03-09 14:04:38.072778030 +0100
> +++ gcc/testsuite/gcc.dg/pr77975.c	2017-03-09 14:04:23.000000000 +0100
> @@ -0,0 +1,31 @@
> +/* PR tree-optimization/77975 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-ivcanon-details" } */
> +
> +/* { dg-final { scan-tree-dump-times "Proved that loop 1 iterates 1 times using brute force" 1 "ivcanon" } } */
> +
> +unsigned int
> +foo (unsigned int *b)
> +{
> +  unsigned int a = 3;
> +  while (a)
> +    {
> +      a >>= 1;
> +      *b += a;
> +    }
> +  return a; 
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Proved that loop 1 iterates 2 times using brute force" 1 "ivcanon" } } */
> +
> +unsigned int
> +bar (unsigned int *b)
> +{
> +  unsigned int a = 7;
> +  while (a)
> +    {
> +      a >>= 1;
> +      *b += a;
> +    }
> +  return a; 
> +}
> 
> 	Jakub
> 
>