Transform (x / y) != 0 to x >=y and (x / y) == 0 to x < y if x, y are unsigned

Hi,
This patch adds the transforms mentioned in $subject.
Bootstrap+test in progress on x86_64-unknown-linux-gnu.
OK to commit if passes ?

Thanks,
Prathamesh
2017-09-15  Prathamesh Kulkarni  <prathamesh.kulkarni@linaro.org>

	* match.pd ((X / Y) == 0 -> X < Y): New pattern.
	((X / Y) != 0 -> X >= Y): Likewise.

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

On Fri, 15 Sep 2017, Prathamesh Kulkarni wrote:

+/* (X / Y) == 0 -> X < Y if X, Y are unsigned.  */
+(simplify
+  (eq (trunc_div @0 @1) integer_zerop)
+  (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1)))
+    (lt @0 @1)))
+
+/* (X / Y) != 0 -> X >= Y, if X, Y are unsigned.  */
+(simplify
+  (ne (trunc_div @0 @1) integer_zerop)
+  (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1)))
+    (ge @0 @1)))
+

Hello,

you can merge the 2 transforms using "for". Also, no need to test the type 
of @1 since you are already testing @0.

- do we want a single_use restriction on the result of the division?
- do we also want to handle (x>>4)==0?
- do we also want a special case when X is 1 that produces Y==1, as asked 
in a recent PR?
- once in a while, someone mentions that eq, on vectors, can either do 
elementwise comparison and return a vector, or return a single boolean, 
which would fail here. However, I don't remember ever seeing an example.

On 09/15/2017 07:09 AM, Marc Glisse wrote:
> On Fri, 15 Sep 2017, Prathamesh Kulkarni wrote:
> 
> +/* (X / Y) == 0 -> X < Y if X, Y are unsigned.  */
> +(simplify
> +  (eq (trunc_div @0 @1) integer_zerop)
> +  (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1)))
> +    (lt @0 @1)))
> +
> +/* (X / Y) != 0 -> X >= Y, if X, Y are unsigned.  */
> +(simplify
> +  (ne (trunc_div @0 @1) integer_zerop)
> +  (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1)))
> +    (ge @0 @1)))
> +
> 
> Hello,
> 
> you can merge the 2 transforms using "for". Also, no need to test the
> type of @1 since you are already testing @0.
Right.

> 
> - do we want a single_use restriction on the result of the division?
I think so.  If x/y is a common subexpression, then ideally we'd compute
it once.

> - do we also want to handle (x>>4)==0?
I think so, but that can be a follow-up IMHO.


> - do we also want a special case when X is 1 that produces Y==1, as
> asked in a recent PR?
Seems like a reasonable follow-up as well.

The other follow-up to consider is detecting these cases in VRP to
produce suitable ASSERT_EXPRs and ranges.

> - once in a while, someone mentions that eq, on vectors, can either do
> elementwise comparison and return a vector, or return a single boolean,
> which would fail here. However, I don't remember ever seeing an example.
We could always restrict to the integral types.  Probably wise to
explicitly do that anyway.

jeff

On Fri, 15 Sep 2017, Jeff Law wrote:

> On 09/15/2017 07:09 AM, Marc Glisse wrote:
>> On Fri, 15 Sep 2017, Prathamesh Kulkarni wrote:
>>
>> +/* (X / Y) == 0 -> X < Y if X, Y are unsigned.  */
>> +(simplify
>> +  (eq (trunc_div @0 @1) integer_zerop)
>> +  (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1)))
>> +    (lt @0 @1)))
>> +
>> +/* (X / Y) != 0 -> X >= Y, if X, Y are unsigned.  */
>> +(simplify
>> +  (ne (trunc_div @0 @1) integer_zerop)
>> +  (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1)))
>> +    (ge @0 @1)))
>> +
>>
>> Hello,
>>
>> you can merge the 2 transforms using "for". Also, no need to test the
>> type of @1 since you are already testing @0.
> Right.
>
>>
>> - do we want a single_use restriction on the result of the division?
> I think so.  If x/y is a common subexpression, then ideally we'd compute
> it once.

The question is whether, having computed c=a/b, it is cheaper to test a<b 
or c!=0. I think it is usually the second one, but not for all types on 
all targets. Although since you mention VRP, it is easier to do further 
optimizations using the information a<b.

>> - do we also want to handle (x>>4)==0?
> I think so, but that can be a follow-up IMHO.

Yes, I forgot to specify it in my email, but these are not meant as 
requirements for this patch to move forward.

>> - do we also want a special case when X is 1 that produces Y==1, as
>> asked in a recent PR?
> Seems like a reasonable follow-up as well.
>
> The other follow-up to consider is detecting these cases in VRP to
> produce suitable ASSERT_EXPRs and ranges.
>
>> - once in a while, someone mentions that eq, on vectors, can either do
>> elementwise comparison and return a vector, or return a single boolean,
>> which would fail here. However, I don't remember ever seeing an example.
> We could always restrict to the integral types.  Probably wise to
> explicitly do that anyway.

VECTOR_TYPE_P (type) || !VECTOR_TYPE_P (TREE_TYPE (@0))

should be enough to avoid the problematic case, the transformation can 
still be nice for vectors.

On 09/15/2017 09:55 AM, Marc Glisse wrote:
> On Fri, 15 Sep 2017, Jeff Law wrote:
> 
>> On 09/15/2017 07:09 AM, Marc Glisse wrote:
>>> On Fri, 15 Sep 2017, Prathamesh Kulkarni wrote:
>>>
>>> +/* (X / Y) == 0 -> X < Y if X, Y are unsigned.  */
>>> +(simplify
>>> +  (eq (trunc_div @0 @1) integer_zerop)
>>> +  (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1)))
>>> +    (lt @0 @1)))
>>> +
>>> +/* (X / Y) != 0 -> X >= Y, if X, Y are unsigned.  */
>>> +(simplify
>>> +  (ne (trunc_div @0 @1) integer_zerop)
>>> +  (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1)))
>>> +    (ge @0 @1)))
>>> +
>>>
>>> Hello,
>>>
>>> you can merge the 2 transforms using "for". Also, no need to test the
>>> type of @1 since you are already testing @0.
>> Right.
>>
>>>
>>> - do we want a single_use restriction on the result of the division?
>> I think so.  If x/y is a common subexpression, then ideally we'd compute
>> it once.
> 
> The question is whether, having computed c=a/b, it is cheaper to test
> a<b or c!=0. I think it is usually the second one, but not for all types
> on all targets. Although since you mention VRP, it is easier to do
> further optimizations using the information a<b.
The c != 0 is easier to test.

WRT VRP we're working to solve that problem.  The framework Andrew's
built allows us to see the c != 0 test and easily derive a < b or a >= b
for the two sides of the branch.  It falls out quite naturally, so I
wouldn't let which is easier for VRP to use play a significant role here.

>>> - do we also want a special case when X is 1 that produces Y==1, as
>>> asked in a recent PR?
>> Seems like a reasonable follow-up as well.
>>
>> The other follow-up to consider is detecting these cases in VRP to
>> produce suitable ASSERT_EXPRs and ranges.
>>
>>> - once in a while, someone mentions that eq, on vectors, can either do
>>> elementwise comparison and return a vector, or return a single boolean,
>>> which would fail here. However, I don't remember ever seeing an example.
>> We could always restrict to the integral types.  Probably wise to
>> explicitly do that anyway.
> 
> VECTOR_TYPE_P (type) || !VECTOR_TYPE_P (TREE_TYPE (@0))
> 
> should be enough to avoid the problematic case, the transformation can
> still be nice for vectors.
Seems reasonable to me.

Richi, further comments?

Prathamesh, I think you've got a few things to address, but hopefully
nothing terribly complex.

jeff-0
>