Takashi's Notes

bug-negabinary-fold

3 min read

Bug: InstCombine misses (x & ~C) - (x & C) → (x ^ C) - C

Title

InstCombine: (x & ~C) - (x & C) should simplify to (x ^ C) - C for any constant C

Summary

When a word is split into complementary bit groups and the groups are subtracted, InstCombine does not fold the expression to the algebraically simpler 2-operation form. This manifests concretely in the Schroeppel negabinary-to-binary conversion (§12-1 of Hacker’s Delight), where three equivalent forms generate 4, 5, and 2 instructions respectively, but only the last form is written in the 2-operation canonical style.

Reproducer

; Form 1: (N & 0x55555555) − (N & 0xAAAAAAAA)    [4 insns]
define i32 @negabin2bin_form1(i32 %n) {
  %a = and i32 %n, 1431655765   ; 0x55555555
  %b = and i32 %n, -1431655766  ; 0xAAAAAAAA  (= ~0x55555555)
  %r = sub i32 %a, %b
  ret i32 %r
}
 
; Form 2: N − ((N & 0xAAAAAAAA) << 1)             [5 insns]
define i32 @negabin2bin_form2(i32 %n) {
  %a = and i32 %n, -1431655766
  %s = shl i32 %a, 1
  %r = sub i32 %n, %s
  ret i32 %r
}
 
; Form 3: (N ^ 0xAAAAAAAA) − 0xAAAAAAAA           [2 insns, already optimal]
define i32 @negabin2bin_form3(i32 %n) {
  %x = xor i32 %n, -1431655766
  %r = sub i32 %x, -1431655766
  ret i32 %r
}
opt -S -passes='default<O2>' | llc -O2 -mtriple=x86_64-pc-linux-gnu

Current output

negabin2bin_form1:                      ; 4 instructions
    movl  %edi, %eax
    andl  $1431655765, %eax
    andl  $-1431655766, %edi
    subl  %edi, %eax
    retq
 
negabin2bin_form2:                      ; 5 instructions
    movl  %edi, %eax
    movl  %edi, %ecx
    andl  $715827882, %ecx
    addl  %ecx, %ecx
    subl  %ecx, %eax
    retq
 
negabin2bin_form3:                      ; 2 instructions (already optimal)
    xorl  $-1431655766, %edi
    leal  1431655766(%rdi), %eax
    retq

Expected output (forms 1 and 2 should equal form 3)

negabin2bin_form1:                      ; 2 instructions
    xorl  $-1431655766, %edi
    leal  1431655766(%rdi), %eax
    retq

Why they are equivalent

Let C = 0xAAAAAAAA, E = x & ~C (even-index bits), O = x & C (odd-index bits).

  • Form 1: E − O
  • Form 2: (E + O) − 2O = E − O
  • Form 3: (x ^ C) − C = (C − O + E) − C = E − O ✓ (XOR with C flips the C-bit positions: O → C − O, since O ⊆ C)

Verified exhaustively for 32-bit integers.

Missing InstCombine rules

Rule A: (x & ~C) - (x & C) ==> (x ^ C) - C

Rule B: x - ((x & C) << 1) ==> (x ^ C) - C (applicable when C & 1 == 0, so that the shift stays within C’s bit positions; here C = 0xAAAAAAAA has bit 0 clear)

Rule A is the cleaner and more general case. The left-hand side of Rule A is exactly the pattern for “sum of even-position bits minus sum of odd-position bits,” which arises in negabinary arithmetic, base-4 digit extraction, and several other bit-manipulation contexts.

Where to fix

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp or InstCombineAndOrXor.cpp: add a fold for (x & C1) - (x & C2) when C1 & C2 == 0 and C1 | C2 == allones (i.e., C1 and C2 partition the bits) → (x ^ C2) - C2.

Graph View