[InstCombine] reduce checks for power-of-2-or-zero using ctpop

[spatel]

Summary

This follows up the transform from rL363956 to use the ctpop intrinsic when checking for power-of-2-or-zero.

This is matching the isPowerOf2() patterns used in PR42314:
https://bugs.llvm.org/show_bug.cgi?id=42314

But there's at least 1 instcombine follow-up needed to match the alternate form:

(v & (v - 1)) == 0;

We should have all of the backend expansions handled with:
rL364319
(x86-specific changes still needed for optimal code based on subtarget)

And the larger patterns to exclude zero as a power-of-2 are joining with this change after:
rL364153 ( D63660 )
rL364246

[xbolva00]

Looks fine

[lebedev.ri]

LG

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::foldICmpEquality(ICmpInst &I) {
   // TODO: Move this to a function similar to foldICmpIntrinsicWithConstant()
   // and handle more intrinsics.
   if ((match(Op0, m_BSwap(m_Value(A))) && match(Op1, m_BSwap(m_Value(B)))) ||
       (match(Op0, m_BitReverse(m_Value(A))) &&
        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 ctpop intrinsic.
+  // (A & -A) == A --> ctpop(A) < 2 (four commuted variants)
+  // (-A & A) != A --> ctpop(A) > 1 (four commuted variants)
   A = nullptr;
-  if (match(Op0, m_OneUse(m_c_And(m_OneUse(m_Neg(m_Specific(Op1))),
-                                  m_Specific(Op1)))))
+  if (match(Op0, m_OneUse(m_c_And(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)))))
+  else if (match(Op1,
+                 m_OneUse(m_c_And(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));
+    CallInst *CtPop = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, A);
+    return Pred == ICmpInst::ICMP_EQ
+        ? new ICmpInst(ICmpInst::ICMP_ULT, CtPop, ConstantInt::get(Ty, 2))
+        : new ICmpInst(ICmpInst::ICMP_UGT, CtPop, ConstantInt::get(Ty, 1));
   }
 
   return nullptr;
 }
 
 /// Handle icmp (cast x to y), (cast/cst). We only handle extending casts so
 /// far.
 Instruction *InstCombiner::foldICmpWithCastAndCast(ICmpInst &ICmp) {

llvm/test/Transforms/InstCombine/ispow2.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define i1 @is_pow2or0_negate_op(i32 %x) {
 ; CHECK-LABEL: @is_pow2or0_negate_op(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X:%.*]]), !range !0
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[TMP1]], 2
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %neg = sub i32 0, %x
   %and = and i32 %neg, %x
   %cmp = icmp eq i32 %and, %x
   ret i1 %cmp
 }
 
 define <2 x i1> @is_pow2or0_negate_op_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @is_pow2or0_negate_op_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = add <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[X:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <2 x i32> [[TMP1]], <i32 2, i32 2>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %neg = sub <2 x i32> zeroinitializer, %x
   %and = and <2 x i32> %neg, %x
   %cmp = icmp eq <2 x i32> %and, %x
   ret <2 x i1> %cmp
 }
 
;
   %dec = add <2 x i8> %x, <i8 -1, i8 -1>
   %and = and <2 x i8> %dec, %x
   %cmp = icmp eq <2 x i8> %and, zeroinitializer
   ret <2 x i1> %cmp
 }
 
 define i1 @isnot_pow2or0_negate_op(i32 %x) {
 ; CHECK-LABEL: @isnot_pow2or0_negate_op(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X:%.*]]), !range !0
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[TMP1]], 1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %neg = sub i32 0, %x
   %and = and i32 %neg, %x
   %cmp = icmp ne i32 %and, %x
   ret i1 %cmp
 }
 
 define <2 x i1> @isnot_pow2or0_negate_op_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @isnot_pow2or0_negate_op_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = add <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[X:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt <2 x i32> [[TMP1]], <i32 1, i32 1>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %neg = sub <2 x i32> zeroinitializer, %x
   %and = and <2 x i32> %neg, %x
   %cmp = icmp ne <2 x i32> %and, %x
   ret <2 x i1> %cmp
 }
 
;
   %and = and <2 x i8> %dec, %x
   %cmp = icmp ne <2 x i8> %and, zeroinitializer
   ret <2 x i1> %cmp
 }
 
 define i1 @is_pow2or0_negate_op_commute1(i32 %p) {
 ; CHECK-LABEL: @is_pow2or0_negate_op_commute1(
 ; CHECK-NEXT:    [[X:%.*]] = srem i32 42, [[P:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[X]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[X]], [[TMP1]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range !1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[TMP1]], 2
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %x = srem i32 42, %p ; thwart complexity-based canonicalization
   %neg = sub i32 0, %x
   %and = and i32 %x, %neg
   %cmp = icmp eq i32 %and, %x
   ret i1 %cmp
 }
 
 ; x can't be <= complexity of the 'neg' but >= complexity of the 'and'.
 
 define i1 @isnot_pow2or0_negate_op_commute2(i32 %p) {
 ; CHECK-LABEL: @isnot_pow2or0_negate_op_commute2(
 ; CHECK-NEXT:    [[X:%.*]] = urem i32 42, [[P:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[X]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[X]], [[TMP1]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range !2
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[TMP1]], 1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %x = urem i32 42, %p ; thwart complexity-based canonicalization
   %neg = sub i32 0, %x
   %and = and i32 %neg, %x
   %cmp = icmp ne i32 %x, %and
   ret i1 %cmp
 }
 
 define i1 @isnot_pow2or0_negate_op_commute3(i32 %p) {
 ; CHECK-LABEL: @isnot_pow2or0_negate_op_commute3(
 ; CHECK-NEXT:    [[X:%.*]] = urem i32 42, [[P:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[X]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[X]], [[TMP1]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range !2
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[TMP1]], 1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %x = urem i32 42, %p ; thwart complexity-based canonicalization
   %neg = sub i32 0, %x
   %and = and i32 %x, %neg
   %cmp = icmp ne i32 %x, %and
   ret i1 %cmp
 }
 
 declare void @use(i32)
 
 define i1 @is_pow2or0_negate_op_extra_use1(i32 %x) {
 ; CHECK-LABEL: @is_pow2or0_negate_op_extra_use1(
 ; CHECK-NEXT:    [[NEG:%.*]] = sub i32 0, [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i32 [[NEG]])
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NEG]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range !0
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[TMP1]], 2
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %neg = sub i32 0, %x
   call void @use(i32 %neg)
   %and = and i32 %neg, %x
   %cmp = icmp eq i32 %and, %x
   ret i1 %cmp
 }
;
   %cmp = icmp ugt i32 %t0, 1
   %cmp2 = icmp slt i32 %x, 0
   %r = or i1 %cmp2, %cmp
   ret i1 %r
 }
 
 define i1 @is_pow2_negate_op(i32 %x) {
 ; CHECK-LABEL: @is_pow2_negate_op(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP2]], 0
-; CHECK-NEXT:    [[NOTZERO:%.*]] = icmp ne i32 [[X]], 0
-; CHECK-NEXT:    [[R:%.*]] = and i1 [[NOTZERO]], [[CMP]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X:%.*]]), !range !0
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 1
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %neg = sub i32 0, %x
   %and = and i32 %neg, %x
   %cmp = icmp eq i32 %and, %x
   %notzero = icmp ne i32 %x, 0
   %r = and i1 %notzero, %cmp
   ret i1 %r
 }
 
 define <2 x i1> @is_pow2_negate_op_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @is_pow2_negate_op_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = add <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[TMP2]], zeroinitializer
-; CHECK-NEXT:    [[NOTZERO:%.*]] = icmp ne <2 x i32> [[X]], zeroinitializer
-; CHECK-NEXT:    [[R:%.*]] = and <2 x i1> [[CMP]], [[NOTZERO]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[X:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq <2 x i32> [[TMP1]], <i32 1, i32 1>
+; CHECK-NEXT:    ret <2 x i1> [[TMP2]]
 ;
   %neg = sub <2 x i32> zeroinitializer, %x
   %and = and <2 x i32> %neg, %x
   %cmp = icmp eq <2 x i32> %and, %x
   %notzero = icmp ne <2 x i32> %x, zeroinitializer
   %r = and <2 x i1> %cmp, %notzero
   ret <2 x i1> %r
 }
;
   %cmp = icmp eq <2 x i8> %and, zeroinitializer
   %notzero = icmp ne <2 x i8> %x, zeroinitializer
   %r = and <2 x i1> %notzero, %cmp
   ret <2 x i1> %r
 }
 
 define i1 @isnot_pow2_negate_op(i32 %x) {
 ; CHECK-LABEL: @isnot_pow2_negate_op(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP2]], 0
-; CHECK-NEXT:    [[ISZERO:%.*]] = icmp eq i32 [[X]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP]], [[ISZERO]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X:%.*]]), !range !0
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 1
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %neg = sub i32 0, %x
   %and = and i32 %neg, %x
   %cmp = icmp ne i32 %and, %x
   %iszero = icmp eq i32 %x, 0
   %r = or i1 %cmp, %iszero
   ret i1 %r
 }
 
 define <2 x i1> @isnot_pow2_negate_op_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @isnot_pow2_negate_op_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = add <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer
-; CHECK-NEXT:    [[ISZERO:%.*]] = icmp eq <2 x i32> [[X]], zeroinitializer
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i1> [[ISZERO]], [[CMP]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[X:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne <2 x i32> [[TMP1]], <i32 1, i32 1>
+; CHECK-NEXT:    ret <2 x i1> [[TMP2]]
 ;
   %neg = sub <2 x i32> zeroinitializer, %x
   %and = and <2 x i32> %neg, %x
   %cmp = icmp ne <2 x i32> %and, %x
   %iszero = icmp eq <2 x i32> %x, zeroinitializer
   %r = or <2 x i1> %iszero, %cmp
   ret <2 x i1> %r
 }