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.

0 files changed, 0 insertions, 0 deletions