[InstCombine] If there is a known-bit transform is_pow2 check to just check for any other bits

[goldstein.w.n]

Summary

in ctpop(X) eq/ne 1 or ctpop(X) ugt/ule 1, if there is any
known-bit in X, instead of going through ctpop, we can just test
if there are any other known bits in X. If there are, X is not a
power of 2. If there aren't, X is a power of 2.

https://alive2.llvm.org/ce/z/eLMJgU

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6973

Shouldn't this code be in foldICmpIntrinsicWithConstant?

6975

Do you think it would make sense to canonicalize ctpop(X) < 2 to ctpop(X) == 1 if isKnownNonZero(X)? Or does this run into the issue that ctpop(X) < 2 is actually the cheaper check once expanded, and we might not recover the non-zero fact at that point anymore?

6992

[goldstein.w.n]

Move to helper used in intrinsic folding function

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

6975

ctpop(X) < 2 is cheaper for the backend and indeed isknownnonzero is often 'lost' by the backend.

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

ping.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3777–3796

If you rebase, there should be a switch here where you can handle both equality and non-equality comparisons in one place.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3777–3796

Hmm? Don't see any change to the function signiture on master.

[goldstein.w.n]

Rebase

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3777–3796

I'm referring to the switch directly above.

[goldstein.w.n]

Rebase

[nikic]

LGTM, but the attached proof is for the wrong transform.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3428

Unnecessary llvm prefix.

3433

[goldstein.w.n]

In D152677#4510722, @nikic wrote:

LGTM, but the attached proof is for the wrong transform.

Bah, sorry must have copied wrong link. Updated summary with: https://alive2.llvm.org/ce/z/eLMJgU

[goldstein.w.n]

Remove unnecesary llvm:: ns

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

case Instruction::SDiv:
     }
     break;
   default:
     break;
   }
   return nullptr;
 }
 
+static Instruction *foldCtpopPow2Test(ICmpInst &I, IntrinsicInst *CtpopLhs,
+                                      const APInt &CRhs,
+                                      InstCombiner::BuilderTy &Builder,
+                                      const SimplifyQuery &Q) {
+  assert(CtpopLhs->getIntrinsicID() == Intrinsic::ctpop &&
+         "Non-ctpop intrin in ctpop fold");
+  if (!CtpopLhs->hasOneUse())
+    return nullptr;
+
+  // Power of 2 test:
+  //    isPow2OrZero : ctpop(X) u< 2
+  //    isPow2       : ctpop(X) == 1
+  //    NotPow2OrZero: ctpop(X) u> 1
+  //    NotPow2      : ctpop(X) != 1
+  // If we know any bit of X can be folded to:
+  //    IsPow2       : X & (~Bit) == 0
+  //    NotPow2      : X & (~Bit) != 0
+  const ICmpInst::Predicate Pred = I.getPredicate();
+  if (((I.isEquality() || Pred == ICmpInst::ICMP_UGT) && CRhs == 1) ||
+      (Pred == ICmpInst::ICMP_ULT && CRhs == 2)) {
+    Value *Op = CtpopLhs->getArgOperand(0);
+    KnownBits OpKnown = computeKnownBits(Op, Q.DL,
+                                         /*Depth*/ 0, Q.AC, Q.CxtI, Q.DT);
+    // No need to check for count > 1, that should be already constant folded.
+    if (OpKnown.countMinPopulation() == 1) {
+      Value *And = Builder.CreateAnd(
+          Op, Constant::getIntegerValue(Op->getType(), ~(OpKnown.One)));
+      return new ICmpInst(
+          (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_ULT)
+              ? ICmpInst::ICMP_EQ
+              : ICmpInst::ICMP_NE,
+          And, Constant::getNullValue(Op->getType()));
+    }
+  }
+
+  return nullptr;
+}
+
 /// Fold an equality icmp with LLVM intrinsic and constant operand.
 Instruction *InstCombinerImpl::foldICmpEqIntrinsicWithConstant(
     ICmpInst &Cmp, IntrinsicInst *II, const APInt &C) {
   Type *Ty = II->getType();
   unsigned BitWidth = C.getBitWidth();
   const ICmpInst::Predicate Pred = Cmp.getPredicate();
 
   switch (II->getIntrinsicID()) {
return new ICmpInst(
       EquivPred,
       Builder.CreateAdd(Op0, ConstantInt::get(Op1->getType(), EquivOffset)),
       ConstantInt::get(Op1->getType(), EquivInt));
 }
 
 /// Fold an icmp with LLVM intrinsic and constant operand: icmp Pred II, C.
 Instruction *InstCombinerImpl::foldICmpIntrinsicWithConstant(ICmpInst &Cmp,
                                                              IntrinsicInst *II,
                                                              const APInt &C) {
   ICmpInst::Predicate Pred = Cmp.getPredicate();
 
   // Handle folds that apply for any kind of icmp.
   switch (II->getIntrinsicID()) {
   default:
     break;
   case Intrinsic::uadd_sat:
   case Intrinsic::usub_sat:
     if (auto *Folded = foldICmpUSubSatOrUAddSatWithConstant(
             Pred, cast<SaturatingInst>(II), C, Builder))
       return Folded;
     break;
+  case Intrinsic::ctpop: {
+    const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
+    if (Instruction *R = foldCtpopPow2Test(Cmp, II, C, Builder, Q))
+      return R;
+  } break;
   }
 
   if (Cmp.isEquality())
     return foldICmpEqIntrinsicWithConstant(Cmp, II, C);
 
   Type *Ty = II->getType();
   unsigned BitWidth = C.getBitWidth();
   switch (II->getIntrinsicID()) {
   case Intrinsic::ctpop: {
     // (ctpop X > BitWidth - 1) --> X == -1
Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
   }
 
   if (Instruction *Res = foldICmpEquality(I))
     return Res;
 
   if (Instruction *Res = foldICmpPow2Test(I, Builder))
     return Res;
 
   if (Instruction *Res = foldICmpOfUAddOv(I))
     return Res;
 
   // The 'cmpxchg' instruction returns an aggregate containing the old value and
   // an i1 which indicates whether or not we successfully did the swap.
   //
   // Replace comparisons between the old value and the expected value with the
   // indicator that 'cmpxchg' returns.
   //
   // N.B.  This transform is only valid when the 'cmpxchg' is not permitted to
   // spuriously fail.  In those cases, the old value may equal the expected
   // value but it is possible for the swap to not occur.
   if (I.getPredicate() == ICmpInst::ICMP_EQ)
     if (auto *EVI = dyn_cast<ExtractValueInst>(Op0))
       if (auto *ACXI = dyn_cast<AtomicCmpXchgInst>(EVI->getAggregateOperand()))
         if (EVI->getIndices()[0] == 0 && ACXI->getCompareOperand() == Op1 &&
             !ACXI->isWeak())
           return ExtractValueInst::Create(ACXI, 1);
 
   {
     Value *X;
     const APInt *C;
     // icmp X+Cst, X
     if (match(Op0, m_Add(m_Value(X), m_APInt(C))) && Op1 == X)
       return foldICmpAddOpConst(X, *C, I.getPredicate());
 
     // icmp X, X+Cst
     if (match(Op1, m_Add(m_Value(X), m_APInt(C))) && Op0 == X)

llvm/test/Transforms/InstCombine/ispow2.ll

;
   %y = xor i32 %x, %xm1
   %r = icmp uge i32 %y, %z
   ret i1 %r
 }
 
 declare <2 x i32> @llvm.ctpop.2xi32(<2 x i32>)
 define i1 @is_pow2_nz_known_bits(i32 %xin) {
 ; CHECK-LABEL: @is_pow2_nz_known_bits(
-; CHECK-NEXT:    [[X:%.*]] = or i32 [[XIN:%.*]], 64
-; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range [[RNG3:![0-9]+]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[CNT]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[XIN:%.*]], -65
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = or i32 %xin, 64
   %cnt = call i32 @llvm.ctpop.i32(i32 %x)
   %r = icmp eq i32 %cnt, 1
   ret i1 %r
 }
 
 define i1 @is_pow2_nz_known_bits_fail_multiuse(i32 %xin) {
 ; CHECK-LABEL: @is_pow2_nz_known_bits_fail_multiuse(
 ; CHECK-NEXT:    [[X:%.*]] = or i32 [[XIN:%.*]], 64
-; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range [[RNG3]]
+; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range [[RNG3:![0-9]+]]
 ; CHECK-NEXT:    call void @use.i32(i32 [[CNT]])
 ; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[CNT]], 1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = or i32 %xin, 64
   %cnt = call i32 @llvm.ctpop.i32(i32 %x)
   call void @use.i32(i32 %cnt)
   %r = icmp eq i32 %cnt, 1
   ret i1 %r
 }
 
 define i1 @not_pow2_nz_known_bits(i32 %xin) {
 ; CHECK-LABEL: @not_pow2_nz_known_bits(
-; CHECK-NEXT:    [[X:%.*]] = or i32 [[XIN:%.*]], 1
-; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range [[RNG3]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[CNT]], 1
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i32 [[XIN:%.*]], 1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = or i32 %xin, 1
   %cnt = call i32 @llvm.ctpop.i32(i32 %x)
   %r = icmp ne i32 %cnt, 1
   ret i1 %r
 }
 
 define i1 @not_pow2_nz_known_bits_fail_not_p2_test(i32 %xin) {
 ; CHECK-LABEL: @not_pow2_nz_known_bits_fail_not_p2_test(
 ; CHECK-NEXT:    [[X:%.*]] = or i32 [[XIN:%.*]], 1
 ; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range [[RNG3]]
 ; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[CNT]], 2
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = or i32 %xin, 1
   %cnt = call i32 @llvm.ctpop.i32(i32 %x)
   %r = icmp ne i32 %cnt, 2
   ret i1 %r
 }
 
 define i1 @is_pow2_or_z_known_bits(i32 %xin) {
 ; CHECK-LABEL: @is_pow2_or_z_known_bits(
-; CHECK-NEXT:    [[X:%.*]] = or i32 [[XIN:%.*]], -2147483648
-; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range [[RNG3]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i32 [[CNT]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[XIN:%.*]], 2147483647
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = or i32 %xin, 2147483648
   %cnt = call i32 @llvm.ctpop.i32(i32 %x)
   %r = icmp ult i32 %cnt, 2
   ret i1 %r
 }
 
 define <2 x i1> @not_pow2_or_z_known_bits(<2 x i32> %xin) {
 ; CHECK-LABEL: @not_pow2_or_z_known_bits(
-; CHECK-NEXT:    [[X:%.*]] = or <2 x i32> [[XIN:%.*]], <i32 64, i32 64>
-; CHECK-NEXT:    [[CNT:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[X]]), !range [[RNG3]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt <2 x i32> [[CNT]], <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[XIN:%.*]], <i32 -65, i32 -65>
+; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i32> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %x = or <2 x i32> %xin, <i32 64, i32 64>
   %cnt = call <2 x i32> @llvm.ctpop.2xi32(<2 x i32> %x)
   %r = icmp ugt <2 x i32> %cnt, <i32 1, i32 1>
   ret <2 x i1> %r
 }