Improve x % y to x VRP optimization (PR tree-optimization/79408)

Hi!

While looking at the RTL problem when combiner optimizes away
(x & 0xfffe) % 0xffff into just (x & 0xfffe), I've looked at VRP
which optimizes that case well (-O2 only, the PR is -O1), but discovered
that it isn't generic enough, we actually don't need op1 to be constant
in this case, a range whose (positive) minimum satisfies it can be handled
the same.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk (or
shall I defer it for GCC8)?

2017-02-07  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/79408
	* tree-vrp.c (simplify_div_or_mod_using_ranges): If op1 is not
	constant, but SSA_NAME with a known integer range, use the minimum
	of that range instead of op1 to determine if modulo can be replaced
	with its first operand.

	* gcc.dg/tree-ssa/pr79408.c: New test.


	Jakub

On Tue, 7 Feb 2017, Jakub Jelinek wrote:

> Hi!
> 
> While looking at the RTL problem when combiner optimizes away
> (x & 0xfffe) % 0xffff into just (x & 0xfffe), I've looked at VRP
> which optimizes that case well (-O2 only, the PR is -O1), but discovered
> that it isn't generic enough, we actually don't need op1 to be constant
> in this case, a range whose (positive) minimum satisfies it can be handled
> the same.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk (or
> shall I defer it for GCC8)?

Ok for trunk if you adjust the function comment accordingly.

Thanks,
Richard.

> 2017-02-07  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/79408
> 	* tree-vrp.c (simplify_div_or_mod_using_ranges): If op1 is not
> 	constant, but SSA_NAME with a known integer range, use the minimum
> 	of that range instead of op1 to determine if modulo can be replaced
> 	with its first operand.
> 
> 	* gcc.dg/tree-ssa/pr79408.c: New test.
> 
> --- gcc/tree-vrp.c.jj	2017-01-30 19:10:50.000000000 +0100
> +++ gcc/tree-vrp.c	2017-02-07 12:33:32.721482609 +0100
> @@ -9241,17 +9241,25 @@ simplify_div_or_mod_using_ranges (gimple
>    tree val = NULL;
>    tree op0 = gimple_assign_rhs1 (stmt);
>    tree op1 = gimple_assign_rhs2 (stmt);
> +  tree op1min = op1;
>    value_range *vr = get_value_range (op0);
>  
>    if (rhs_code == TRUNC_MOD_EXPR
> -      && TREE_CODE (op1) == INTEGER_CST
> -      && tree_int_cst_sgn (op1) == 1
> +      && TREE_CODE (op1) == SSA_NAME)
> +    {
> +      value_range *vr1 = get_value_range (op1);
> +      if (range_int_cst_p (vr1))
> +	op1min = vr1->min;
> +    }
> +  if (rhs_code == TRUNC_MOD_EXPR
> +      && TREE_CODE (op1min) == INTEGER_CST
> +      && tree_int_cst_sgn (op1min) == 1
>        && range_int_cst_p (vr)
> -      && tree_int_cst_lt (vr->max, op1))
> +      && tree_int_cst_lt (vr->max, op1min))
>      {
>        if (TYPE_UNSIGNED (TREE_TYPE (op0))
>  	  || tree_int_cst_sgn (vr->min) >= 0
> -	  || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1), op1),
> -			      vr->min))
> +	  || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1min),
> +					  op1min), vr->min))
>  	{
>  	  /* If op0 already has the range op0 % op1 has,
> --- gcc/testsuite/gcc.dg/tree-ssa/pr79408.c.jj	2017-02-07 16:30:42.439774777 +0100
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr79408.c	2017-02-07 16:32:37.653282317 +0100
> @@ -0,0 +1,40 @@
> +/* PR tree-optimization/79408 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +void link_error (void);
> +
> +void
> +foo (unsigned int x, unsigned int y)
> +{
> +  if (x > 7312)
> +    return;
> +  if (y <= 7312)
> +    return;
> +  if (x % y != x)
> +    link_error ();
> +}
> +
> +void
> +bar (int x, int y)
> +{
> +  if (x > 7312 || x < 0)
> +    return;
> +  if (y <= 7312)
> +    return;
> +  if (x % y != x)
> +    link_error ();
> +}
> +
> +void
> +baz (int x, int y)
> +{
> +  if (x > 7312 || x < -7312)
> +    return;
> +  if (y <= 7312)
> +    return;
> +  if (x % y != x)
> +    link_error ();
> +}
> +
> +/* { dg-final { scan-tree-dump-times "link_error" 0 "optimized"} } */
> 
> 	Jakub
> 
>

On 8 February 2017 09:41:47 CET, Richard Biener <rguenther@suse.de> wrote:
>On Tue, 7 Feb 2017, Jakub Jelinek wrote:

>> +/* { dg-final { scan-tree-dump-times "link_error" 0 "optimized"} }
>*/

scan-tree-dump-not would have been more expressive, FWIW.

On Tue, 7 Feb 2017, Jakub Jelinek wrote:

> 	* tree-vrp.c (simplify_div_or_mod_using_ranges): If op1 is not
> 	constant, but SSA_NAME with a known integer range, use the minimum
> 	of that range instead of op1 to determine if modulo can be replaced
> 	with its first operand.

Would it make sense to use something like the operand_less_p helper so we 
would also handle an INTEGER_CST lhs?

unsigned f(unsigned x){
   if(x<42)return 18;
   return 33%x;
}

On Sun, 12 Feb 2017, Marc Glisse wrote:

> On Tue, 7 Feb 2017, Jakub Jelinek wrote:
>
>> 	* tree-vrp.c (simplify_div_or_mod_using_ranges): If op1 is not
>> 	constant, but SSA_NAME with a known integer range, use the minimum
>> 	of that range instead of op1 to determine if modulo can be replaced
>> 	with its first operand.
>
> Would it make sense to use something like the operand_less_p helper so we 
> would also handle an INTEGER_CST lhs?

Oops, operand_less_p is just a helper for compare_values_warnv and even 
that one doesn't seem to use ranges, so there may not already be a nice 
function we can call (?). The idea remains that reusing such code would 
help handle more cases (it may even handle a few symbolic cases).

> unsigned f(unsigned x){
>  if(x<42)return 18;
>  return 33%x;
> }

On Sun, 12 Feb 2017, Marc Glisse wrote:

> On Sun, 12 Feb 2017, Marc Glisse wrote:
> 
> > On Tue, 7 Feb 2017, Jakub Jelinek wrote:
> > 
> > > 	* tree-vrp.c (simplify_div_or_mod_using_ranges): If op1 is not
> > > 	constant, but SSA_NAME with a known integer range, use the minimum
> > > 	of that range instead of op1 to determine if modulo can be replaced
> > > 	with its first operand.
> > 
> > Would it make sense to use something like the operand_less_p helper so we
> > would also handle an INTEGER_CST lhs?
> 
> Oops, operand_less_p is just a helper for compare_values_warnv and even that
> one doesn't seem to use ranges, so there may not already be a nice function we
> can call (?). The idea remains that reusing such code would help handle more
> cases (it may even handle a few symbolic cases).

Yeah, we only have the compare_range_with_value / compare_ranges functions
and those require you to "expand" the value you have a range for first.

Richard.

> > unsigned f(unsigned x){
> >  if(x<42)return 18;
> >  return 33%x;
> > }
> 
>