Improved handling of shifts/rotates in bit CCP.

This patch is the next in the series to improve bit bounds in tree-ssa's
bit CCP pass, this time: bounds for shifts and rotates by unknown amounts.
This allows us to optimize expressions such as ((x&15)<<(y&24))&64.
In this case, the expression (y&24) contains only two unknown bits,
and can therefore have only four possible values: 0, 8, 16 and 24.
From this (x&15)<<(y&24) has the nonzero bits 0x0f0f0f0f, and from
that ((x&15)<<(y&24))&64 must always be zero.

One clever use of computer science in this patch is the use of XOR
to efficiently enumerate bit patterns in Gray code order.  As the
order in which we generate values is not significant, it's faster
and more convenient to enumerate values by flipping one bit at a
time, rather than in numerical order [which would require carry
bits and additional logic].

There's a pre-existing ??? comment in tree-ssa-ccp.c that we should
eventually be able to optimize (x<<(y|8))&255, but this patch takes the
conservatively paranoid approach of only optimizing cases where the
shift/rotate is guaranteed to be less than the target precision, and
therefore avoids changing any cases that potentially might invoke
undefined behavior.  This patch does optimize (x<<((y&31)|8))&255.

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

gcc/ChangeLog
	* tree-ssa-ccp.c (get_individual_bits): Helper function to
	extract the individual bits from a widest_int constant (mask).
	(gray_code_bit_flips): New read-only table for effiently
	enumerating permutations/combinations of bits.
	(bit_value_binop) [LROTATE_EXPR, RROTATE_EXPR]: Handle rotates
	by unknown counts that are guaranteed less than the target
	precision and four or fewer unknown bits by enumeration.
	[LSHIFT_EXPR, RSHIFT_EXPR]: Likewise, also handle shifts by
	enumeration under the same conditions.  Handle remaining
	shifts as a mask based upon the minimum possible shift value.

gcc/testsuite/ChangeLog
	* gcc.dg/tree-ssa/ssa-ccp-41.c: New test case.

0 files changed, 0 insertions, 0 deletions