diff mbox series

Improved handling of division/modulus in bit CCP.

Message ID 004701d79765$0a351120$1e9f3360$@nextmovesoftware.com
State New
Headers show
Series Improved handling of division/modulus in bit CCP. | expand

Commit Message

Roger Sayle Aug. 22, 2021, 2:50 p.m. UTC 
This patch implements support for TRUNC_MOD_EXPR and TRUNC_DIV_EXPR
in tree-ssa's bit CCP pass.  This is mostly for completeness, as the
VRP pass already provides better bounds for these operations, but
seeing mask values of all_ones in my debugging/instrumentation logs
seemed overly pessimistic.  With this patch, the expression X%10
has a nonzero bits of 0x0f (for unsigned X), likewise (X&1)/3 has
a known value of zero, and (X&3)/3 has a nonzero bits mask of 0x1.

This patch has been tested on x86_64-pc-linux-gnu with "make bootstrap"
and "make -k check" with no new failures.  Ok for mainline?


2021-08-22  Roger Sayle  <roger@nextmovesoftware.com>

gcc/ChangeLog
 	* tree-ssa-ccp.c (bit_value_binop) [TRUNC_MOD_EXPR, TRUNC_DIV_EXPR]:
 	Provide bounds for unsigned (and signed with non-negative operands)
 	division and modulus.

Roger
--

Comments

Jeff Law Aug. 23, 2021, 1:25 a.m. UTC | #1 
On 8/22/2021 8:50 AM, Roger Sayle wrote:
> This patch implements support for TRUNC_MOD_EXPR and TRUNC_DIV_EXPR
> in tree-ssa's bit CCP pass.  This is mostly for completeness, as the
> VRP pass already provides better bounds for these operations, but
> seeing mask values of all_ones in my debugging/instrumentation logs
> seemed overly pessimistic.  With this patch, the expression X%10
> has a nonzero bits of 0x0f (for unsigned X), likewise (X&1)/3 has
> a known value of zero, and (X&3)/3 has a nonzero bits mask of 0x1.
>
> This patch has been tested on x86_64-pc-linux-gnu with "make bootstrap"
> and "make -k check" with no new failures.  Ok for mainline?
>
>
> 2021-08-22  Roger Sayle  <roger@nextmovesoftware.com>
>
> gcc/ChangeLog
>   	* tree-ssa-ccp.c (bit_value_binop) [TRUNC_MOD_EXPR, TRUNC_DIV_EXPR]:
>   	Provide bounds for unsigned (and signed with non-negative operands)
>   	division and modulus.
OK
jeff
diff mbox series

Patch

diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c
index 1a63ae5..1a94aeb 100644
--- a/gcc/tree-ssa-ccp.c
+++ b/gcc/tree-ssa-ccp.c
@@ -1736,6 +1736,68 @@  bit_value_binop (enum tree_code code, signop sgn, int width,
 	break;
       }
 
+    case TRUNC_MOD_EXPR:
+      {
+	widest_int r1max = r1val | r1mask;
+	widest_int r2max = r2val | r2mask;
+	if (sgn == UNSIGNED
+	    || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
+	  {
+	    /* Confirm R2 has some bits set, to avoid division by zero.  */
+	    widest_int r2min = wi::bit_and_not (r2val, r2mask);
+	    if (r2min != 0)
+	      {
+		/* R1 % R2 is R1 if R1 is always less than R2.  */
+		if (wi::ltu_p (r1max, r2min))
+		  {
+		    *mask = r1mask;
+		    *val = r1val;
+		  }
+		else
+		  {
+		    /* R1 % R2 is always less than the maximum of R2.  */
+		    unsigned int lzcount = wi::clz (r2max);
+		    unsigned int bits = wi::get_precision (r2max) - lzcount;
+		    if (r2max == wi::lshift (1, bits))
+		      bits--;
+		    *mask = wi::mask <widest_int> (bits, false);
+		    *val = 0;
+		  }
+	       }
+	    }
+	}
+      break;
+
+    case TRUNC_DIV_EXPR:
+      {
+	widest_int r1max = r1val | r1mask;
+	widest_int r2max = r2val | r2mask;
+	if (sgn == UNSIGNED
+	    || (!wi::neg_p (r1max) && !wi::neg_p (r2max)))
+	  {
+	    /* Confirm R2 has some bits set, to avoid division by zero.  */
+	    widest_int r2min = wi::bit_and_not (r2val, r2mask);
+	    if (r2min != 0)
+	      {
+		/* R1 / R2 is zero if R1 is always less than R2.  */
+		if (wi::ltu_p (r1max, r2min))
+		  {
+		    *mask = 0;
+		    *val = 0;
+		  }
+		else
+		  {
+		    widest_int upper = wi::udiv_trunc (r1max, r2min);
+		    unsigned int lzcount = wi::clz (upper);
+		    unsigned int bits = wi::get_precision (upper) - lzcount;
+		    *mask = wi::mask <widest_int> (bits, false);
+		    *val = 0;
+		  }
+	       }
+	    }
+	}
+      break;
+
     default:;
     }
 }