[gcc r12-2964] Improved handling of MINUS_EXPR in bit CCP.

[gcc r12-2964] Improved handling of MINUS_EXPR in bit CCP.

[Roger Sayle]

https://gcc.gnu.org/g:897a15f355632bdc31871554892eca5512b3c370

commit r12-2964-g897a15f355632bdc31871554892eca5512b3c370
Author: Roger Sayle <roger@nextmovesoftware.com>
Date:   Tue Aug 17 14:59:14 2021 +0100

    Improved handling of MINUS_EXPR in bit CCP.
    
    This patch improves the bit bounds for MINUS_EXPR during tree-ssa's
    conditional constant propagation (CCP) pass (and as an added bonus
    adds support for POINTER_DIFF_EXPR).
    
    The pessimistic assumptions made by the current algorithm are
    demonstrated by considering 1 - (x&1).  Intuitively this should
    have possible values 0 and 1, and therefore an unknown mask of 1.
    Alas by treating subtraction as a negation followed by addition,
    the second operand first becomes 0 or -1, with an unknown mask
    of all ones, which results in the addition containing no known bits.
    
    Improved bounds are achieved by using the same approach used for
    PLUS_EXPR, determining the result with the minimum number of borrows,
    the result from the maximum number of borrows, and examining the bits
    they have in common.  One additional benefit of this approach
    is that it is applicable to POINTER_DIFF_EXPR, where previously the
    negation of a pointer didn't/doesn't make sense.
    
    A more convincing example, where a transformation missed by .032t.cpp
    isn't caught a few passes later by .038t.evrp, is the expression
    (7 - (x&5)) & 2, which (in the new test case) currently survives the
    tree-level optimizers but with this patch is now simplified to the
    constant value 2.
    
    2021-08-17  Roger Sayle  <roger@nextmovesoftware.com>
    
    gcc/ChangeLog
            * tree-ssa-ccp.c (bit_value_binop) [MINUS_EXPR]: Use same
            algorithm as PLUS_EXPR to improve subtraction bit bounds.
            [POINTER_DIFF_EXPR]: Treat as synonymous with MINUS_EXPR.
    
    gcc/testsuite/ChangeLog
            * gcc.dg/tree-ssa/ssa-ccp-40.c: New test case.

Diff:
---
 gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-40.c | 11 +++++++++++
 gcc/tree-ssa-ccp.c                         | 21 ++++++++++++---------
 2 files changed, 23 insertions(+), 9 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-40.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-40.c
new file mode 100644
index 00000000000..aa7349e15d6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-40.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int foo(int x)
+{
+  int p = 7;
+  int q = p - (x & 5);
+  return q & 2;
+}
+
+/* { dg-final { scan-tree-dump "return 2;" "optimized" } } */
diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c
index 8e4d8aeb69b..1a63ae5f104 100644
--- a/gcc/tree-ssa-ccp.c
+++ b/gcc/tree-ssa-ccp.c
@@ -1458,7 +1458,7 @@ bit_value_binop (enum tree_code code, signop sgn, int width,
 		 widest_int *val, widest_int *mask,
 		 signop r1type_sgn, int r1type_precision,
 		 const widest_int &r1val, const widest_int &r1mask,
-		 signop r2type_sgn, int r2type_precision,
+		 signop r2type_sgn, int r2type_precision ATTRIBUTE_UNUSED,
 		 const widest_int &r2val, const widest_int &r2mask)
 {
   bool swap_p = false;
@@ -1505,7 +1505,7 @@ bit_value_binop (enum tree_code code, signop sgn, int width,
 	    }
 	  else
 	    {
-	      if (wi::neg_p (shift))
+	      if (wi::neg_p (shift, r2type_sgn))
 		{
 		  shift = -shift;
 		  if (code == RROTATE_EXPR)
@@ -1542,7 +1542,7 @@ bit_value_binop (enum tree_code code, signop sgn, int width,
 	    }
 	  else
 	    {
-	      if (wi::neg_p (shift))
+	      if (wi::neg_p (shift, r2type_sgn))
 		break;
 	      if (code == RSHIFT_EXPR)
 		{
@@ -1582,13 +1582,16 @@ bit_value_binop (enum tree_code code, signop sgn, int width,
       }
 
     case MINUS_EXPR:
+    case POINTER_DIFF_EXPR:
       {
-	widest_int temv, temm;
-	bit_value_unop (NEGATE_EXPR, r2type_sgn, r2type_precision, &temv, &temm,
-			  r2type_sgn, r2type_precision, r2val, r2mask);
-	bit_value_binop (PLUS_EXPR, sgn, width, val, mask,
-			 r1type_sgn, r1type_precision, r1val, r1mask,
-			 r2type_sgn, r2type_precision, temv, temm);
+	/* Subtraction is derived from the addition algorithm above.  */
+	widest_int lo = wi::bit_and_not (r1val, r1mask) - (r2val | r2mask);
+	lo = wi::ext (lo, width, sgn);
+	widest_int hi = (r1val | r1mask) - wi::bit_and_not (r2val, r2mask);
+	hi = wi::ext (hi, width, sgn);
+	*mask = r1mask | r2mask | (lo ^ hi);
+	*mask = wi::ext (*mask, width, sgn);
+	*val = lo;
 	break;
       }