issue

Summary

The safe integer-log2 idiom

(W - 1) - ctlz(x, false)

returns -1 for x = 0. On x86_64 without lzcnt, LLVM currently lowers the i32 form to a 4-instruction bsr + xor + add sequence. A shorter 3-instruction form exists using bsr plus cmovz with -1 as the fallback.

This is a codegen quality issue, not a correctness issue.

Reproducer

declare i32 @llvm.ctlz.i32(i32, i1 immarg)
 
define i32 @ilog2_safe(i32 %x) {
  %lz = call i32 @llvm.ctlz.i32(i32 %x, i1 false)
  %r  = sub i32 31, %lz
  ret i32 %r
}

Run:

~/llvm-project/build/bin/llc -O2 -mtriple=x86_64-unknown-linux-gnu

Current output

ilog2_safe:
    movl  $63, %eax
    bsrl  %edi, %eax
    xorl  $-32, %eax
    addl  $32, %eax

Better output

ilog2_safe:
    bsrl   %edi, %eax
    movl   $-1, %ecx
    cmovzl %ecx, %eax

Why this is valid

• For x != 0, bsr(x) already computes 31 - ctlz(x).
• For x == 0, bsr sets ZF and the result is architecturally undefined, but cmovz overwrites it unconditionally with -1.
• So the destination value from bsr is never observed in the zero case.

This avoids relying on the current backend trick of seeding %eax with a magic constant and repairing it with xor / add.

Caveat

This is a plausible improvement rather than an indisputable “single obvious idiom” miss. It still seems worth tracking privately because the shorter form is clear and does not rely on undefined destination behavior.

Likely fix area

• llvm/lib/Target/X86/X86ISelLowering.cpp
• llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

Potentially as a combine for (W-1) - ctlz(x, false) when lzcnt is not available.

Local references

• Source note: llvm-validation/ch11-elementary-functions/bug-ilog2-safe.md
• Harness: llvm-validation/ch11-elementary-functions/ch11_ilog2_safe.ll