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

Message ID CAAgBjMk7p7xR2Zk4uqWhyoXsAzehN+vo53yUoNb2RiXdxxs5MQ@mail.gmail.com
State New
Headers show
Series
  • Transform (x / y) != 0 to x >=y and (x / y) == 0 to x < y if x, y are unsigned
Related show

Commit Message

Prathamesh Kulkarni Sept. 15, 2017, 11 a.m.
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.

Comments

Marc Glisse Sept. 15, 2017, 1:09 p.m. | #1
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.

-- 
Marc Glisse
Jeff Law Sept. 15, 2017, 3:10 p.m. | #2
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
Marc Glisse Sept. 15, 2017, 3:55 p.m. | #3
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.

-- 
Marc Glisse
Jeff Law Sept. 15, 2017, 4:09 p.m. | #4
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
>

Patch

diff --git a/gcc/match.pd b/gcc/match.pd
index dbfceaf10a5..0e1b59c9c10 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1266,6 +1266,18 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	   || TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))))
    (op @1 @0))))
 
+/* (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)))
+
 /* X == C - X can never be true if C is odd.  */
 (for cmp (eq ne)
  (simplify
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cmpdiv.c b/gcc/testsuite/gcc.dg/tree-ssa/cmpdiv.c
new file mode 100644
index 00000000000..14161f5ea6f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cmpdiv.c
@@ -0,0 +1,18 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized-raw" } */
+
+_Bool f1(unsigned x, unsigned y)
+{
+  unsigned t1 = x / y;
+  _Bool t2 = (t1 != 0);
+  return t2;
+}
+
+_Bool f2(unsigned x, unsigned y)
+{
+  unsigned t1 = x / y;
+  _Bool t2 = (t1 == 0);
+  return t2;
+}
+
+/* { dg-final { scan-tree-dump-not "trunc_div_expr" "optimized" } } */