On Sun, Aug 22, 2021 at 4:03 PM Roger Sayle <ro...@nextmovesoftware.com> wrote: > > > > 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. > > > > 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?
OK. Thanks, Richard. > > > > > 2021-08-22 Roger Sayle <ro...@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. > > > > > > Roger > > -- > > >
