[PATCH] match.pd: optimize unsigned mul overflow check

[Alexander Monakov]

Hello,

For unsigned A, B, 'A > -1 / B' is a nice predicate for checking whether 'A*B'
overflows (or 'B && A > -1 / B' if B may be zero).  Let's optimize it to an
invocation of __builtin_mul_overflow to avoid the divide operation.

The following patch implements that as a match.pd transformation.  It looks
like there's a similar thing going on for add/sub overflow check in
tree-ssa-math-opts, but handling this in match.pd seems reasonable.

(user code using the above test would probably also compute 'A*B' a few
statements later; notably, today GCC cannot CSE plain 'A*B' to REALPART_EXPR
of the builtin call on GIMPLE; on x86 it gets cleaned up on RTL)

Thanks to Marc for helping get this in shape on the Bugzilla.

Bootstrapped and regtested on x86_64, OK for trunk?

gcc/
2016-05-28  Alexander Monakov  <amona...@ispras.ru>
        Marc Glisse  <marc.gli...@inria.fr>

        PR tree-optimization/71289
        * match.pd (-1 / B < A, A > -1 / B): New transformations.

gcc/testsuite/
2016-05-28  Alexander Monakov  <amona...@ispras.ru>

        PR tree-optimization/71289
        * gcc.dg/pr71289.c: New test.

diff --git a/gcc/match.pd b/gcc/match.pd
index 8d05e86..953c070 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2657,6 +2657,25 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
        && types_match (TREE_TYPE (@0), TREE_TYPE (@1)))
    (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); }))))
 
+/* For unsigned operands, A > -1 / B checks whether A * B would overflow.
+   Simplify it to __builtin_mul_overflow (A, B, <unused>).  */
+/* -1 / B < A */
+(for cmp (lt ge)
+     out (ne eq)
+ (simplify
+  (cmp (trunc_div:s integer_all_onesp @1) @0)
+  (if (TYPE_UNSIGNED (TREE_TYPE (@0)) && !VECTOR_TYPE_P (TREE_TYPE (@0)))
+   (with { tree t = TREE_TYPE (@0), cpx = build_complex_type (t); }
+    (out (imagpart (IFN_MUL_OVERFLOW:cpx @0 @1)) { build_zero_cst (t); })))))
+
+/* A > -1 / B */
+(for cmp (gt le)
+     out (ne eq)
+ (simplify
+  (cmp @0 (trunc_div:s integer_all_onesp @1))
+  (if (TYPE_UNSIGNED (TREE_TYPE (@0)) && !VECTOR_TYPE_P (TREE_TYPE (@0)))
+   (with { tree t = TREE_TYPE (@0), cpx = build_complex_type (t); }
+    (out (imagpart (IFN_MUL_OVERFLOW:cpx @0 @1)) { build_zero_cst (t); })))))
 
 /* Simplification of math builtins.  These rules must all be optimizations
    as well as IL simplifications.  If there is a possibility that the new
diff --git a/gcc/testsuite/gcc.dg/pr71289.c b/gcc/testsuite/gcc.dg/pr71289.c
new file mode 100644
index 0000000..39837b9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr71289.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized-raw" } */
+
+int f(unsigned a, unsigned b, unsigned *c)
+{
+  if (a > -1 / b)
+    return -1;
+  *c = a * b;
+  return 0;
+}
+
+void g(unsigned long long a, unsigned long long b, unsigned long long *c)
+{
+  if (a <= -1 / b)
+    *c = a * b;
+}
+
+/* { dg-final { scan-tree-dump-not "trunc_div_expr" "optimized" } } */