* [PATCH] Improved handling of division/modulus in bit CCP.
@ 2021-08-22 14:50 Roger Sayle
2021-08-23 1:25 ` Jeff Law
0 siblings, 1 reply; 2+ messages in thread
From: Roger Sayle @ 2021-08-22 14:50 UTC (permalink / raw)
To: 'GCC Patches'
[-- Attachment #1: Type: text/plain, Size: 850 bytes --]
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
--
[-- Attachment #2: patchl2.txt --]
[-- Type: text/plain, Size: 1977 bytes --]
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:;
}
}
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] Improved handling of division/modulus in bit CCP.
2021-08-22 14:50 [PATCH] Improved handling of division/modulus in bit CCP Roger Sayle
@ 2021-08-23 1:25 ` Jeff Law
0 siblings, 0 replies; 2+ messages in thread
From: Jeff Law @ 2021-08-23 1:25 UTC (permalink / raw)
To: Roger Sayle, 'GCC Patches'
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
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2021-08-23 1:25 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-08-22 14:50 [PATCH] Improved handling of division/modulus in bit CCP Roger Sayle
2021-08-23 1:25 ` Jeff Law
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).