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

On Mon, Feb 13, 2017 at 09:59:12AM +0100, Richard Biener wrote:
> 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.

I think we can do something like following, but not sure how you want to
actually simplify it using helpers.  The only thing I can think of is
something like get_value_range that works on both SSA_NAMEs and
INTEGER_CSTs, but then it either has to allocate a new value range struct
for the INTEGER_CST case, or be more like extract_range_from_tree and
then it would copy the range for the SSA_NAME case, penalizing the code.

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

	PR tree-optimization/79408
	* tree-vrp.c (simplify_div_or_mod_using_ranges): Handle also the
	case when on TRUNC_MOD_EXPR op0 is INTEGER_CST.
	(simplify_stmt_using_ranges): Call simplify_div_or_mod_using_ranges
	also if rhs1 is INTEGER_CST.

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



	Jakub

On Mon, 13 Feb 2017, Jakub Jelinek wrote:

> On Mon, Feb 13, 2017 at 09:59:12AM +0100, Richard Biener wrote:
> > 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.
> 
> I think we can do something like following, but not sure how you want to
> actually simplify it using helpers.  The only thing I can think of is
> something like get_value_range that works on both SSA_NAMEs and
> INTEGER_CSTs, but then it either has to allocate a new value range struct
> for the INTEGER_CST case, or be more like extract_range_from_tree and
> then it would copy the range for the SSA_NAME case, penalizing the code.

You'd of course allocate it on the stack.  But yeah, sth like your patch
works for me.

Richard.

> 2017-02-13  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/79408
> 	* tree-vrp.c (simplify_div_or_mod_using_ranges): Handle also the
> 	case when on TRUNC_MOD_EXPR op0 is INTEGER_CST.
> 	(simplify_stmt_using_ranges): Call simplify_div_or_mod_using_ranges
> 	also if rhs1 is INTEGER_CST.
> 
> 	* gcc.dg/tree-ssa/pr79408-2.c: New test.
> 
> --- gcc/tree-vrp.c.jj	2017-02-08 10:21:31.000000000 +0100
> +++ gcc/tree-vrp.c	2017-02-13 10:55:00.755070795 +0100
> @@ -9241,8 +9241,24 @@ simplify_div_or_mod_using_ranges (gimple
>    tree val = NULL;
>    tree op0 = gimple_assign_rhs1 (stmt);
>    tree op1 = gimple_assign_rhs2 (stmt);
> +  tree op0min = NULL_TREE, op0max = NULL_TREE;
>    tree op1min = op1;
> -  value_range *vr = get_value_range (op0);
> +  value_range *vr = NULL;
> +
> +  if (TREE_CODE (op0) == INTEGER_CST)
> +    {
> +      op0min = op0;
> +      op0max = op0;
> +    }
> +  else
> +    {
> +      vr = get_value_range (op0);
> +      if (range_int_cst_p (vr))
> +	{
> +	  op0min = vr->min;
> +	  op0max = vr->max;
> +	}
> +    }
>  
>    if (rhs_code == TRUNC_MOD_EXPR
>        && TREE_CODE (op1) == SSA_NAME)
> @@ -9254,13 +9270,13 @@ simplify_div_or_mod_using_ranges (gimple
>    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, op1min))
> +      && op0max
> +      && tree_int_cst_lt (op0max, op1min))
>      {
>        if (TYPE_UNSIGNED (TREE_TYPE (op0))
> -	  || tree_int_cst_sgn (vr->min) >= 0
> +	  || tree_int_cst_sgn (op0min) >= 0
>  	  || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1min), op1min),
> -			      vr->min))
> +			      op0min))
>  	{
>  	  /* If op0 already has the range op0 % op1 has,
>  	     then TRUNC_MOD_EXPR won't change anything.  */
> @@ -9269,6 +9285,9 @@ simplify_div_or_mod_using_ranges (gimple
>  	}
>      }
>  
> +  if (TREE_CODE (op0) != SSA_NAME)
> +    return false;
> +
>    if (!integer_pow2p (op1))
>      {
>        /* X % -Y can be only optimized into X % Y either if
> @@ -10377,7 +10396,8 @@ simplify_stmt_using_ranges (gimple_stmt_
>  	 range.  */
>  	case TRUNC_DIV_EXPR:
>  	case TRUNC_MOD_EXPR:
> -	  if (TREE_CODE (rhs1) == SSA_NAME
> +	  if ((TREE_CODE (rhs1) == SSA_NAME
> +	       || TREE_CODE (rhs1) == INTEGER_CST)
>  	      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
>  	    return simplify_div_or_mod_using_ranges (gsi, stmt);
>  	  break;
> --- gcc/testsuite/gcc.dg/tree-ssa/pr79408-2.c.jj	2017-02-13 10:51:13.939063664 +0100
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr79408-2.c	2017-02-13 10:52:33.868008990 +0100
> @@ -0,0 +1,34 @@
> +/* PR tree-optimization/79408 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +void link_error (void);
> +
> +void
> +foo (unsigned int y)
> +{
> +  if (y <= 7312)
> +    return;
> +  if (7312 % y != 7312)
> +    link_error ();
> +}
> +
> +void
> +bar (int x, int y)
> +{
> +  if (y <= 7312)
> +    return;
> +  if (7312 % y != 7312)
> +    link_error ();
> +}
> +
> +void
> +baz (int x, int y)
> +{
> +  if (y <= 7312)
> +    return;
> +  if (-7312 % y != -7312)
> +    link_error ();
> +}
> +
> +/* { dg-final { scan-tree-dump-times "link_error" 0 "optimized"} } */
> 
> 
> 	Jakub
> 
>

On Mon, 13 Feb 2017, Jakub Jelinek wrote:

> On Mon, Feb 13, 2017 at 09:59:12AM +0100, Richard Biener wrote:
>> 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.

Nice, I was looking for them but I'd missed those functions.

> I think we can do something like following, but not sure how you want to
> actually simplify it using helpers.  The only thing I can think of is
> something like get_value_range that works on both SSA_NAMEs and
> INTEGER_CSTs, but then it either has to allocate a new value range struct
> for the INTEGER_CST case, or be more like extract_range_from_tree and
> then it would copy the range for the SSA_NAME case, penalizing the code.

If allocating a new range for INTEGER_CST is too expensive (I wouldn't 
expect it to matter, but I never profiled gcc), we could have it on the 
stack:

value_range tmp;
value_range* vr0;
if(TREE_CODE(op0)==INTEGER_CST){
   tmp.max=tmp.min=op0;
   tmp.type=VR_RANGE;
   vr0=&tmp;
} else {
   vr0=get_value_range(op0);
}
// same for op1
if(TYPE_UNSIGNED(TREE_TYPE(op0))&&compare_ranges(LT_EXPR,vr0,vr1,&ovf))
   // op0 % op1 is just op0
etc.

That's not so different from what you did, but compare_ranges doesn't 
dismiss symbolic ranges (I am not sure there are any cases where that 
would help here), and it feels like it is duplicating less code. On the 
other hand I haven't tried to write the signed case, which may be uglier 
with this version since we would have to generate a range for -op1, so 
maybe your version is better?

(thanks for the patch)

On Mon, Feb 13, 2017 at 12:24:08PM +0100, Richard Biener wrote:
> You'd of course allocate it on the stack.  But yeah, sth like your patch
> works for me.

Now bootstrapped/regtested successfully on x86_64-linux and i686-linux.
So is this ok for trunk and perhaps we can add new APIs later?

> > 2017-02-13  Jakub Jelinek  <jakub@redhat.com>
> > 
> > 	PR tree-optimization/79408
> > 	* tree-vrp.c (simplify_div_or_mod_using_ranges): Handle also the
> > 	case when on TRUNC_MOD_EXPR op0 is INTEGER_CST.
> > 	(simplify_stmt_using_ranges): Call simplify_div_or_mod_using_ranges
> > 	also if rhs1 is INTEGER_CST.
> > 
> > 	* gcc.dg/tree-ssa/pr79408-2.c: New test.

	Jakub

On Mon, 13 Feb 2017, Jakub Jelinek wrote:

> On Mon, Feb 13, 2017 at 12:24:08PM +0100, Richard Biener wrote:
> > You'd of course allocate it on the stack.  But yeah, sth like your patch
> > works for me.
> 
> Now bootstrapped/regtested successfully on x86_64-linux and i686-linux.
> So is this ok for trunk and perhaps we can add new APIs later?

Yes.

Thanks,
Richard.

> > > 2017-02-13  Jakub Jelinek  <jakub@redhat.com>
> > > 
> > > 	PR tree-optimization/79408
> > > 	* tree-vrp.c (simplify_div_or_mod_using_ranges): Handle also the
> > > 	case when on TRUNC_MOD_EXPR op0 is INTEGER_CST.
> > > 	(simplify_stmt_using_ranges): Call simplify_div_or_mod_using_ranges
> > > 	also if rhs1 is INTEGER_CST.
> > > 
> > > 	* gcc.dg/tree-ssa/pr79408-2.c: New test.
> 
> 	Jakub
> 
>