Improved handling of MULT_EXPR in bit CCP.
authorRoger Sayle <roger@nextmovesoftware.com>
Tue, 17 Aug 2021 13:50:54 +0000 (14:50 +0100)
committerRoger Sayle <roger@nextmovesoftware.com>
Tue, 17 Aug 2021 13:53:04 +0000 (14:53 +0100)
commit408579c9c9b8fee20e1d8114489ce2b93872767c
tree4283a897742f5041bb10b4778665e29420188a39
parentf8d535f3fec81c1cc84e22df5500e693544ec65b
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.
gcc/testsuite/gcc.dg/fold-ior-5.c [new file with mode: 0644]
gcc/tree-ssa-ccp.c