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

[Prathamesh Kulkarni]

On 15 September 2017 at 22:09, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Fri, 15 Sep 2017, Wilco Dijkstra wrote:
>
>> Marc Glisse wrote:
>>
>>> 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.
>>
>>
>> No, a<b is always better. Division does have high latency and low
>> throughput on
>> all modern cores, so rather than having to wait until the division
>> finishes, you can
>> execute whatever depends on the comparison many cycles earlier.
>>
>> Generally you want to avoid division as much as possible and when that
>> fails
>> reduce any dependencies on the result of divisions.
>
>
> This would indicate that we do not need to check for single-use, makes the
> patch simpler, thanks.
> (let's ignore -Os)
Hi,
Thanks for the suggestions, I have updated the patch.
Is this OK ?
Bootstrap+test in progress on x86_64-unknown-linux-gnu.
I will try address the right shift by 4 case in follow up patch.

Thanks,
Prathamesh
>
> --
> Marc Glisse
-------------- next part --------------
2017-09-18  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.
diff --git a/gcc/match.pd b/gcc/match.pd
index dbfceaf10a5..a9008f2437e 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))))
 
+/* Transform:
+ * (X / Y) == 0 -> X < Y if X, Y are unsigned.
+ * (X / Y) != 0 -> X >= Y, if X, Y are unsigned.
+ */
+(for cmp (eq ne)
+     ocmp (lt ge)
+ (simplify
+  (cmp (trunc_div @0 @1) integer_zerop)
+  (if (TYPE_UNSIGNED (TREE_TYPE (@0))
+       && (VECTOR_TYPE_P (type) || !VECTOR_TYPE_P (TREE_TYPE (@0))))
+   (ocmp @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" } } */