https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128662
Bug ID: 128662
Summary: i386: bsr for __builtin_clz without lzcnt depends on
its destination
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: target
Assignee: unassigned at gcc dot gnu.org
Reporter: hongyuw at gcc dot gnu.org
Target Milestone: ---
Testcase:
#include <stdio.h>
#include <x86intrin.h>
/* 31 - clz is bsr without LZCNT. */
__attribute__((noipa)) void
f (const unsigned *s, unsigned char *o, unsigned n)
{
for (unsigned i = 0; i < n; i++)
o[i] = 31 - __builtin_clz (s[i]);
}
static unsigned s[1024];
static unsigned char o[1024];
int
main (void)
{
for (int i = 0; i < 1024; i++)
s[i] = (i * 2654435761u) | 1;
unsigned long long t0 = __rdtsc ();
for (int r = 0; r < 1000000; r++)
{
f (s, o, 1024);
__asm__ volatile ("" ::: "memory");
}
unsigned long long t1 = __rdtsc ();
printf ("%d %.2f tsc/elt\n", o[5], (t1 - t0) / 1024e6);
return 0;
}
trunk (17.0.0, r17-5731-g48d3efd1bf4) -O2:
.L3:
bsrl (%rdi,%rax,4), %ecx
movl $31, %esi
xorl $31, %ecx
subl %ecx, %esi
movb %sil, (%r8,%rax)
addq $1, %rax
cmpq %rax, %rdx
jne .L3
The sematic of bsr/bsf defined in Intel SDM was "if the content of the source
operand is zero, the destination operand is unmodified", so the dependency was
a true wait on its dest. For the loop, each iteration's bsrl writes %ecx, which
the previous iteration's "xorl $31, %ecx" wrote, so bsr -> xor -> bsr is a
loop-carried chain even though the elements are independent (s[i] is never
zero).
Clearing the destination before the bsr breaks it:
.L3:
xorl %ecx, %ecx
bsrl (%rdi,%rax,4), %ecx
...
Result tsc:
bsr xor;bsr
Alder Lake P (12900K) 2.50 0.86
Zen 5 (9950X) 1.54 1.18
As in GCC rtl the bsr/bsf patterns are defined as overwrite the dest, and
CLZ/CTZ_DEFINED_VALUE_AT_ZERO is 0 when no BMI/LZCNT - we take the src==0 value
as unspecified. So there's no risk to insert this clear via postreload splitter
unless src==dest.
