Takashi's Notes

issue

2 min read

Summary

InstCombine misses a useful algebraic fold:

(x & ~C) - (x & C)  ==>  (x ^ C) - C

for constant C.

This comes up directly in the Hacker’s Delight negabinary-to-binary conversion forms. Three equivalent expressions currently generate 4, 5, and 2 instructions respectively, but only the already-canonical (x ^ C) - C form gets the short code.

Reproducer

define i32 @negabin2bin_form1(i32 %n) {
  %a = and i32 %n, 1431655765
  %b = and i32 %n, -1431655766
  %r = sub i32 %a, %b
  ret i32 %r
}
 
define i32 @negabin2bin_form2(i32 %n) {
  %a = and i32 %n, -1431655766
  %s = shl i32 %a, 1
  %r = sub i32 %n, %s
  ret i32 %r
}
 
define i32 @negabin2bin_form3(i32 %n) {
  %x = xor i32 %n, -1431655766
  %r = sub i32 %x, -1431655766
  ret i32 %r
}

Run:

~/llvm-project/build/bin/opt -S -passes='default<O2>' | \
~/llvm-project/build/bin/llc -O2 -mtriple=x86_64-unknown-linux-gnu

Current output

negabin2bin_form1:
    movl  %edi, %eax
    andl  $1431655765, %eax
    andl  $-1431655766, %edi
    subl  %edi, %eax
    retq
 
negabin2bin_form2:
    movl  %edi, %eax
    movl  %edi, %ecx
    andl  $715827882, %ecx
    addl  %ecx, %ecx
    subl  %ecx, %eax
    retq
 
negabin2bin_form3:
    xorl  $-1431655766, %edi
    leal  1431655766(%rdi), %eax
    retq

Desired canonical form

Ideally forms 1 and 2 would both become form 3:

    xorl  $-1431655766, %edi
    leal  1431655766(%rdi), %eax
    retq

Why the fold is correct

Let C be the mask and split x into complementary bit groups:

  • E = x & ~C
  • O = x & C

Then:

  • form 1 is E - O
  • form 3 is (x ^ C) - C

Since XOR with C flips exactly the C-masked bit positions, (x ^ C) can be viewed as E + (C - O) in the complementary partition, so:

(x ^ C) - C = E - O

This is already spelled out in the local note and was exhaustively validated there for the 32-bit negabinary mask.

Why this seems worth tracking

  • This is target-independent.
  • One equivalent form is already much better, so the missed piece is canonicalization.
  • The pattern is not specific to negabinary; it applies any time a word is partitioned into complementary bit groups and then subtracted.

Likely fix area

  • llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
  • possibly InstCombineAndOrXor.cpp

Local references

  • Source note: llvm-validation/ch12-unusual-bases/bug-negabinary-fold.md
  • Harness: llvm-validation/ch12-unusual-bases/ch12_negabinary.ll

Graph View