https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127748
Bug ID: 127748
Summary: [17 Regression] wrong code with popcnt emitted on
almost-Hacker's Delight popcnt pattern
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Keywords: wrong-code
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: gabravier at gmail dot com
CC: Reshma.Roy at amd dot com
Target Milestone: ---
unsigned f(unsigned x, unsigned z) {
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
return (z & 0xffff) + (x >> 16);
}
For this code, GCC 16.2 with -O2 -mpopcnt emits:
f:
mov eax, edi
shr edi
movzx esi, si
and eax, 1431655765
and edi, 1431655765
add edi, eax
mov eax, edi
shr edi, 2
and eax, 858993459
and edi, 858993459
add eax, edi
mov edx, eax
shr eax, 4
and eax, 252645135
and edx, 252645135
add edx, eax
mov eax, edx
shr edx, 8
and eax, 16711935
and edx, 16711935
add eax, edx
shr eax, 16
add eax, esi
ret
GCC trunk emits:
f:
xor eax, eax
popcnt eax, edi
ret
This is incorrect - the result should incorporate the value of z correctly. For
instance, f(0, 1) returns 0 instead of 1.
The cause looks to me to be this:
/* To recognize the popcnt pattern for 32-bit from Hacker's Delight
int Gia_WordCountOnes32c ( uint32_t uword)
{
uword = (uword & 0x55555555) + ((uword>>1) & 0x55555555);
uword = (uword & 0x33333333) + ((uword>>2) & 0x33333333);
uword = (uword & 0x0f0f0f0f) + ((uword>>4) & 0x0f0f0f0f);
uword = (uword & 0x00ff00ff) + ((uword>>8) & 0x00ff00ff);
return (uword & 0x0000ffff) + (uword>>16);
or
return (uword & 0x0000ffff) + ((uword>>16) & 0x0000ffff);
}
*/
(simplify
(plus:c
(bit_and @step_4 INTEGER_CST@9)
(rshift
(plus:c@step4
(bit_and @step3 INTEGER_CST@7)
(bit_and
(rshift
(plus:c@step3
(bit_and @step2 INTEGER_CST@5)
(bit_and
(rshift
(plus:c@step2
(bit_and @step1 INTEGER_CST@3)
(bit_and
(rshift
(plus:c@step1
(bit_and @0 INTEGER_CST@1)
(bit_and (rshift @0 INTEGER_CST@2) @1))
INTEGER_CST@4)
INTEGER_CST@3))
INTEGER_CST@6)
INTEGER_CST@5))
INTEGER_CST@8)
INTEGER_CST@7))
INTEGER_CST@10))
(with {
unsigned prec = TYPE_PRECISION (type);
}
(if (prec == 32
&& TYPE_UNSIGNED (type)
&& compare_tree_int (@2, 1) == 0
&& compare_tree_int (@4, 2) == 0
&& compare_tree_int (@6, 4) == 0
&& compare_tree_int (@8, 8) == 0
&& compare_tree_int (@10, 16) == 0
&& compare_tree_int (@1, 0x55555555) == 0
&& compare_tree_int (@3, 0x33333333) == 0
&& compare_tree_int (@5, 0x0F0F0F0F) == 0
&& compare_tree_int (@7, 0x00FF00FF) == 0
&& compare_tree_int (@9, 0x0000FFFF) == 0)
(if (direct_internal_fn_supported_p (IFN_POPCOUNT, type,
OPTIMIZE_FOR_BOTH))
(convert (IFN_POPCOUNT:type @0))))))
...where "step_4" should be "step4". I presume the fact step_4 doesn't actually
exists makes it degenerate into a wildcard match? At least that's the result
functionally. (perhaps genmatch should warn for this x))
It appears to have been originally caused by r17-489-g8ca1e887847e2f
PS: The ideal output I think would be smth like this:
f:
movzx eax, si
shr edi, 16
popcnt edi, edi
add eax, edi
ret
(untested, but I believe it to be correct)
...although I certainly would not exactly expect it to be a common pattern :p
(I suppose GCC could split the pattern in pieces for `popcnt(x & 0xFFFF)` and
`popcnt(x >> 16)`, leaving this one as `(z & 0xffff) + popcount(x >> 16)` and
then have a separate rule for `popcnt(x & 0xFFFF) + popcount(x >> 16)` - that
latter pattern would perhaps have non-nil other users, even if the former alone
isn't exactly gonna be common)
