issue

Summary

For sdiv i32 %n, C where the signed Hacker’s Delight magic number M is positive (M < 2^31), x86_64 codegen extracts the sign correction from the 64-bit product with:

movq %rax, %rcx
shrq $63, %rcx

That works, but it is redundant. Because M > 0, sign(n * M) == sign(n), so the sign bit can be taken from the original input register before the multiply, saving one instruction.

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

Reproducer

define i32 @sdiv3(i32 %n) {
  %r = sdiv i32 %n, 3
  ret i32 %r
}

Run:

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

Current output

sdiv3:
    movslq  %edi, %rax
    imulq   $1431655766, %rax, %rax
    movq    %rax, %rcx
    shrq    $63, %rcx
    shrq    $32, %rax
    addl    %ecx, %eax
    retq

Better output

sdiv3:
    movslq  %edi, %rax
    shrl    $31, %edi
    imulq   $1431655766, %rax, %rax
    shrq    $32, %rax
    addl    %edi, %eax
    retq

Why this is valid

When M is positive, the 64-bit product cannot overflow its sign bit in a way that changes sign independently from the multiplicand:

• n is a sign-extended i32
• M < 2^31
• therefore |n * M| < 2^62
• so sign(n * M) == sign(n)

That means the correction term currently computed as (n * M) >> 63 is equal to n >> 31 for these divisors.

Affected divisors

Any divisor whose signed magic number is positive. The local note calls out:

• 3, 5, 6, 9, 10, 11, 12, 25, 125, 625

There are likely more; this should be derivable from the signed-div-by-constant lowering logic rather than hardcoded.

Likely fix area

• llvm/lib/Target/X86/X86ISelLowering.cpp
• or the DAG combine / selection logic used for signed division by constants

The backend should choose the sign source based on the sign of the magic number.

Local references

• Source note: llvm-validation/ch10-division-by-constants/bug-sdiv-positive-magic.md
• Harness: llvm-validation/ch10-division-by-constants/ch10_sdiv_posM.ll