[InstCombine] canonicalize check for power-of-2
authorSanjay Patel <spatel@rotateright.com>
Thu, 20 Jun 2019 17:41:15 +0000 (17:41 +0000)
committerSanjay Patel <spatel@rotateright.com>
Thu, 20 Jun 2019 17:41:15 +0000 (17:41 +0000)
commit63311bfb8334c8365f959b2a4af2f0563327ab97
tree198688792800709e3869e7e8e153dea04d8ebe39
parent801c0f12b0a3132d833c53c8e911245725674110
[InstCombine] canonicalize check for power-of-2

The form that compares against 0 is better because:
1. It removes a use of the input value.
2. It's the more standard form for this pattern: https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
3. It results in equal or better codegen (tested with x86, AArch64, ARM, PowerPC, MIPS).

This is a root cause for PR42314, but probably doesn't completely answer the codegen request:
https://bugs.llvm.org/show_bug.cgi?id=42314

Alive proof:
https://rise4fun.com/Alive/9kG

  Name: is power-of-2
  %neg = sub i32 0, %x
  %a = and i32 %neg, %x
  %r = icmp eq i32 %a, %x
  =>
  %dec = add i32 %x, -1
  %a2 = and i32 %dec, %x
  %r = icmp eq i32 %a2, 0

  Name: is not power-of-2
  %neg = sub i32 0, %x
  %a = and i32 %neg, %x
  %r = icmp ne i32 %a, %x
  =>
  %dec = add i32 %x, -1
  %a2 = and i32 %dec, %x
  %r = icmp ne i32 %a2, 0

llvm-svn: 363956
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
llvm/test/Transforms/InstCombine/ispow2.ll