Improved handling of MULT_EXPR in bit CCP.
This patch allows GCC to constant fold (i | (i<<16)) | ((i<<24) | (i<<8)),
where i is an unsigned char, or the equivalent (i*65537) | (i*
16777472), to
i*
16843009. The trick is to teach tree_nonzero_bits which bits may be
set in the result of a multiplication by a constant given which bits are
potentially set in the operands. This allows the optimizations recently
added to match.pd to catch more cases.
The required mask/value pair from a multiplication may be calculated using
a classical shift-and-add algorithm, given we already have implementations
for both addition and shift by constant. To keep this optimization "cheap",
this functionality is only used if the constant multiplier has a few bits
set (unless flag_expensive_optimizations), and we provide a special case
fast-path implementation for the common case where the (non-constant)
operand has no bits that are guaranteed to be set. I have no evidence
that this functionality causes performance issues, it's just that sparse
multipliers provide the largest benefit to CCP.
2021-08-17 Roger Sayle <roger@nextmovesoftware.com>
gcc/ChangeLog
* tree-ssa-ccp.c (bit_value_mult_const): New helper function to
calculate the mask-value pair result of a multiplication by an
unsigned constant.
(bit_value_binop) [MULT_EXPR]: Call it from here for
multiplications by (sparse) non-negative constants.
gcc/testsuite/ChangeLog
* gcc.dg/fold-ior-5.c: New test case.