[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
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
index 5493b4a..467c6d9 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -3830,6 +3830,26 @@
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;
}