LLVM Chapter 3 reductions

1. Hacker’s Delight flp2 smear network not canonicalized to a bit-scan form

File: flp2_hd_to_bitscan.ll

Issue:

  • LLVM keeps the classic Hacker’s Delight “smear bits right, then subtract the half-shifted value” network intact.
  • On x86_64 with BMI1/BMI2/LZCNT available, this misses a much shorter bit-scan based lowering.

Observed current-head behavior:

movl  %edi, %eax
shrl  %eax
orl   %edi, %eax
...
shrl  %ecx
subl  %ecx, %eax
retq

Reference x86_64 shape from an explicit ctlz formulation:

lzcntl %edi, %eax
movl   $-2147483648, %ecx
shrxl  %eax, %ecx, %eax
cmovbl %edi, %eax
retq

Suggested bug report title:

  • InstCombine misses flp2 canonicalization for Hacker's Delight smear network

2. Hacker’s Delight clp2 smear network not canonicalized to a bit-scan form

File: clp2_hd_to_bitscan.ll

Issue:

  • LLVM keeps the standard “decrement, smear right, increment” network intact.
  • An equivalent ctlz formulation in the same Chapter 3 harness lowers to compact lzcnt + shlx code, so the manual network is missing an obvious canonicalization step.

Observed current-head behavior:

leal  -1(%rdi), %eax
movl  %eax, %ecx
shrl  %ecx
orl   %eax, %ecx
...
incl  %eax
retq

Reference x86_64 shape from an explicit ctlz formulation:

decl   %edi
movl   $1, %ecx
lzcntl %edi, %eax
negb   %al
shlxl  %eax, %ecx, %eax
retq

Suggested bug report title:

  • InstCombine misses clp2 canonicalization for Hacker's Delight smear network