[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

1 files changed, 20 insertions, 0 deletions

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
index 5493b4a85b3..467c6d9453b 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -3830,6 +3830,26 @@ Instruction *InstCombiner::foldICmpEquality(ICmpInst &I) {
        match(Op1, m_BitReverse(m_Value(B)))))
     return new ICmpInst(Pred, A, B);
 
+  // Canonicalize checking for a power-of-2-or-zero value:
+  // (A & -A) == A --> (A & (A - 1)) == 0
+  // (-A & A) == A --> (A & (A - 1)) == 0
+  // A == (A & -A) --> (A & (A - 1)) == 0
+  // A == (-A & A) --> (A & (A - 1)) == 0
+  // TODO: This could be reduced by using the popct intrinsic.
+  A = nullptr;
+  if (match(Op0, m_OneUse(m_c_And(m_OneUse(m_Neg(m_Specific(Op1))),
+                                  m_Specific(Op1)))))
+    A = Op1;
+  else if (match(Op1, m_OneUse(m_c_And(m_OneUse(m_Neg(m_Specific(Op0))),
+                                       m_Specific(Op0)))))
+    A = Op0;
+  if (A) {
+    Type *Ty = A->getType();
+    Value *Dec = Builder.CreateAdd(A, ConstantInt::getAllOnesValue(Ty));
+    Value *And = Builder.CreateAnd(A, Dec);
+    return new ICmpInst(Pred, And, ConstantInt::getNullValue(Ty));
+  }
+
   return nullptr;
 }