widening_mul: Recognize another form of ADD_OVERFLOW [PR96272]

The following patch recognizes another form of hand written
__builtin_add_overflow (this time _p), in particular when
the code does unsigned
if (x > ~0U - y)
or
if (x <= ~0U - y)
it can be optimized (if the subtraction turned into ~y is single use)
into
if (__builtin_add_overflow_p (x, y, 0U))
or
if (!__builtin_add_overflow_p (x, y, 0U))
and generate better code, e.g. for the first function in the testcase:
-       movl    %esi, %eax
        addl    %edi, %esi
-       notl    %eax
-       cmpl    %edi, %eax
-       movl    $-1, %eax
-       cmovnb  %esi, %eax
+       jc      .L3
+       movl    %esi, %eax
+       ret
+.L3:
+       orl     $-1, %eax
        ret
on x86_64.  As for the jumps vs. conditional move case, that is some CE
issue with complex branch patterns we should fix up no matter what, but
in this case I'm actually not sure if branchy code isn't better, overflow
is something that isn't that common.

2020-12-12  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/96272
	* tree-ssa-math-opts.c (uaddsub_overflow_check_p): Add OTHER argument.
	Handle BIT_NOT_EXPR.
	(match_uaddsub_overflow): Optimize unsigned a > ~b into
	__imag__ .ADD_OVERFLOW (a, b).
	(math_opts_dom_walker::after_dom_children): Call match_uaddsub_overflow
	even for BIT_NOT_EXPR.

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

2 files changed, 111 insertions, 21 deletions

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr96272.c b/gcc/testsuite/gcc.dg/tree-ssa/pr96272.c
new file mode 100644
index 0000000..4c9fa63
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr96272.c
@@ -0,0 +1,37 @@
+/* PR tree-optimization/96272 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-widening_mul" } */
+
+unsigned
+foo (unsigned a, unsigned b)
+{
+  if (a > ~0U - b)
+    return ~0U;
+  return a + b;
+}
+
+unsigned
+bar (unsigned a, unsigned b)
+{
+  if (a <= ~0U - b)
+    return ~0U;
+  return a + b;
+}
+
+unsigned
+baz (unsigned a, unsigned b)
+{
+  if (~0U - b < a)
+    return ~0U;
+  return a + b;
+}
+
+unsigned
+qux (unsigned a, unsigned b)
+{
+  if (~0U - b >= a)
+    return ~0U;
+  return a + b;
+}
+
+/* { dg-final { scan-tree-dump-times "ADD_OVERFLOW" 4 "widening_mul" { target { i?86-*-* x86_64-*-* } } } } */
diff --git a/gcc/tree-ssa-math-opts.c b/gcc/tree-ssa-math-opts.c
index 4ade0b6..b8cdce9 100644
--- a/gcc/tree-ssa-math-opts.c
+++ b/gcc/tree-ssa-math-opts.c
@@ -3457,7 +3457,8 @@ convert_mult_to_fma (gimple *mul_stmt, tree op1, tree op2,
    and 0 otherwise.  */
 
 static int
-uaddsub_overflow_check_p (gimple *stmt, gimple *use_stmt, tree maxval)
+uaddsub_overflow_check_p (gimple *stmt, gimple *use_stmt, tree maxval,
+			  tree *other)
 {
   enum tree_code ccode = ERROR_MARK;
   tree crhs1 = NULL_TREE, crhs2 = NULL_TREE;
@@ -3520,6 +3521,13 @@ uaddsub_overflow_check_p (gimple *stmt, gimple *use_stmt, tree maxval)
 	  || (code == PLUS_EXPR && (crhs1 == rhs1 || crhs1 == rhs2)
 	      && crhs2 == lhs))
 	return ccode == GT_EXPR ? 1 : -1;
+      /* r = ~a; b > r or b <= r.  */
+      if (code == BIT_NOT_EXPR && crhs2 == lhs)
+	{
+	  if (other)
+	    *other = crhs1;
+	  return ccode == GT_EXPR ? 1 : -1;
+	}
       break;
     case LT_EXPR:
     case GE_EXPR:
@@ -3531,6 +3539,13 @@ uaddsub_overflow_check_p (gimple *stmt, gimple *use_stmt, tree maxval)
 	  || (code == PLUS_EXPR && crhs1 == lhs
 	      && (crhs2 == rhs1 || crhs2 == rhs2)))
 	return ccode == LT_EXPR ? 1 : -1;
+      /* r = ~a; r < b or r >= b.  */
+      if (code == BIT_NOT_EXPR && crhs1 == lhs)
+	{
+	  if (other)
+	    *other = crhs2;
+	  return ccode == LT_EXPR ? 1 : -1;
+	}
       break;
     default:
       break;
@@ -3560,7 +3575,15 @@ uaddsub_overflow_check_p (gimple *stmt, gimple *use_stmt, tree maxval)
    _9 = REALPART_EXPR <_7>;
    _8 = IMAGPART_EXPR <_8>;
    if (_8)
-   and replace (utype) x with _9.  */
+   and replace (utype) x with _9.
+
+   Also recognize:
+   x = ~z;
+   if (y > x)
+   and replace it with
+   _7 = ADD_OVERFLOW (y, z);
+   _8 = IMAGPART_EXPR <_8>;
+   if (_8)  */
 
 static bool
 match_uaddsub_overflow (gimple_stmt_iterator *gsi, gimple *stmt,
@@ -3576,34 +3599,49 @@ match_uaddsub_overflow (gimple_stmt_iterator *gsi, gimple *stmt,
   gimple *add_stmt = NULL;
   bool add_first = false;
 
-  gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR);
+  gcc_checking_assert (code == PLUS_EXPR
+		       || code == MINUS_EXPR
+		       || code == BIT_NOT_EXPR);
   if (!INTEGRAL_TYPE_P (type)
       || !TYPE_UNSIGNED (type)
       || has_zero_uses (lhs)
-      || (code == MINUS_EXPR
-	  && optab_handler (usubv4_optab,
+      || (code != PLUS_EXPR
+	  && optab_handler (code == MINUS_EXPR ? usubv4_optab : uaddv4_optab,
 			    TYPE_MODE (type)) == CODE_FOR_nothing))
     return false;
 
+  tree rhs1 = gimple_assign_rhs1 (stmt);
+  tree rhs2 = gimple_assign_rhs2 (stmt);
   FOR_EACH_IMM_USE_FAST (use_p, iter, lhs)
     {
       use_stmt = USE_STMT (use_p);
       if (is_gimple_debug (use_stmt))
 	continue;
 
-      if (uaddsub_overflow_check_p (stmt, use_stmt, NULL_TREE))
-	ovf_use_seen = true;
+      tree other = NULL_TREE;
+      if (uaddsub_overflow_check_p (stmt, use_stmt, NULL_TREE, &other))
+	{
+	  if (code == BIT_NOT_EXPR)
+	    {
+	      gcc_assert (other);
+	      if (TREE_CODE (other) != SSA_NAME)
+		return false;
+	      if (rhs2 == NULL)
+		rhs2 = other;
+	      else if (rhs2 != other)
+		return false;
+	    }
+	  ovf_use_seen = true;
+	}
       else
 	use_seen = true;
       if (ovf_use_seen && use_seen)
 	break;
     }
 
-  tree rhs1 = gimple_assign_rhs1 (stmt);
-  tree rhs2 = gimple_assign_rhs2 (stmt);
   tree maxval = NULL_TREE;
   if (!ovf_use_seen
-      || !use_seen
+      || (code == BIT_NOT_EXPR ? use_seen : !use_seen)
       || (code == PLUS_EXPR
 	  && optab_handler (uaddv4_optab,
 			    TYPE_MODE (type)) == CODE_FOR_nothing))
@@ -3664,7 +3702,7 @@ match_uaddsub_overflow (gimple_stmt_iterator *gsi, gimple *stmt,
 	  if (is_gimple_debug (use_stmt))
 	    continue;
 
-	  if (uaddsub_overflow_check_p (stmt, use_stmt, maxval))
+	  if (uaddsub_overflow_check_p (stmt, use_stmt, maxval, NULL))
 	    {
 	      ovf_use_seen = true;
 	      use_bb = gimple_bb (use_stmt);
@@ -3781,23 +3819,27 @@ match_uaddsub_overflow (gimple_stmt_iterator *gsi, gimple *stmt,
     }
 
   tree ctype = build_complex_type (type);
-  gcall *g = gimple_build_call_internal (code == PLUS_EXPR
+  gcall *g = gimple_build_call_internal (code != MINUS_EXPR
 					 ? IFN_ADD_OVERFLOW : IFN_SUB_OVERFLOW,
 					 2, rhs1, rhs2);
   tree ctmp = make_ssa_name (ctype);
   gimple_call_set_lhs (g, ctmp);
   gsi_insert_before (gsi, g, GSI_SAME_STMT);
   tree new_lhs = maxval ? make_ssa_name (type) : lhs;
-  gassign *g2 = gimple_build_assign (new_lhs, REALPART_EXPR,
-				     build1 (REALPART_EXPR, type, ctmp));
-  if (maxval)
+  gassign *g2;
+  if (code != BIT_NOT_EXPR)
     {
-      gsi_insert_before (gsi, g2, GSI_SAME_STMT);
-      if (add_first)
-	*gsi = gsi_for_stmt (stmt);
+      g2 = gimple_build_assign (new_lhs, REALPART_EXPR,
+				build1 (REALPART_EXPR, type, ctmp));
+      if (maxval)
+	{
+	  gsi_insert_before (gsi, g2, GSI_SAME_STMT);
+	  if (add_first)
+	    *gsi = gsi_for_stmt (stmt);
+	}
+      else
+	gsi_replace (gsi, g2, true);
     }
-  else
-    gsi_replace (gsi, g2, true);
   tree ovf = make_ssa_name (type);
   g2 = gimple_build_assign (ovf, IMAGPART_EXPR,
 			    build1 (IMAGPART_EXPR, type, ctmp));
@@ -3808,9 +3850,10 @@ match_uaddsub_overflow (gimple_stmt_iterator *gsi, gimple *stmt,
       if (is_gimple_debug (use_stmt))
 	continue;
 
-      int ovf_use = uaddsub_overflow_check_p (stmt, use_stmt, maxval);
+      int ovf_use = uaddsub_overflow_check_p (stmt, use_stmt, maxval, NULL);
       if (ovf_use == 0)
 	{
+	  gcc_assert (code != BIT_NOT_EXPR);
 	  if (maxval)
 	    {
 	      tree use_lhs = gimple_assign_lhs (use_stmt);
@@ -3863,6 +3906,12 @@ match_uaddsub_overflow (gimple_stmt_iterator *gsi, gimple *stmt,
 	  gsi_replace (&gsi2, g, true);
 	}
     }
+  else if (code == BIT_NOT_EXPR)
+    {
+      gimple_stmt_iterator gsi2 = gsi_for_stmt (stmt);
+      gsi_remove (&gsi2, true);
+      release_ssa_name (lhs);
+    }
   return true;
 }
 
@@ -4188,6 +4237,10 @@ math_opts_dom_walker::after_dom_children (basic_block bb)
 		match_uaddsub_overflow (&gsi, stmt, code);
 	      break;
 
+	    case BIT_NOT_EXPR:
+	      match_uaddsub_overflow (&gsi, stmt, code);
+	      break;
+
 	    case TRUNC_MOD_EXPR:
 	      convert_to_divmod (as_a<gassign *> (stmt));
 	      break;