[InstSimplify] Add transform ctpop(X) -> 1 iff X is non-zero power of 2

[goldstein.w.n]

Summary

Definitionally a non-zero power of 2 will only have 1 bit set so this
is a freebee.

[craig.topper]

Can this be in InstSimplify?

[goldstein.w.n]

new tests

[goldstein.w.n]

In D141990#4061264, @craig.topper wrote:

Can this be in InstSimplify?

Where in InstSimplify should it go? Looking around there didn't seem any fitting place.

[craig.topper]

In D141990#4062660, @goldstein.w.n wrote:

In D141990#4061264, @craig.topper wrote:

Can this be in InstSimplify?

Where in InstSimplify should it go? Looking around there didn't seem any fitting place.

I think you can add it to the ctpop handling in simplifyUnaryIntrinsic in llvm/lib/Analysis/InstructionSimplify.cpp

[majnemer]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

623–627 ↗

(On Diff #490198)

Should this be in simplifyIntrinsic?

[goldstein.w.n]

In D141990#4062665, @craig.topper wrote:

In D141990#4062660, @goldstein.w.n wrote:

In D141990#4061264, @craig.topper wrote:

Can this be in InstSimplify?

Where in InstSimplify should it go? Looking around there didn't seem any fitting place.

I think you can add it to the ctpop handling in simplifyUnaryIntrinsic in llvm/lib/Analysis/InstructionSimplify.cpp

Ah, got it (I was looking in lib/Transform)

[goldstein.w.n]

Move to instsimplify

[goldstein.w.n]

In D141990#4062665, @craig.topper wrote:

In D141990#4062660, @goldstein.w.n wrote:

In D141990#4061264, @craig.topper wrote:

Can this be in InstSimplify?

Where in InstSimplify should it go? Looking around there didn't seem any fitting place.

I think you can add it to the ctpop handling in simplifyUnaryIntrinsic in llvm/lib/Analysis/InstructionSimplify.cpp

Done, thank you for the helps!

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

623–627 ↗

(On Diff #490198)

Should this be in simplifyIntrinsic?

Moved.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

5893

Why change the parameter? The arg type must match the call return type for ctpop, so it shouldn't make a difference for this patch. If there's some other transform where it makes a difference, we could adjust it later?

5931–5932

Remove the "Maybe better..." statement because we can't do that in InstSimplify (can't create new instructions here). But that should happen in InstCombine if it's not already done there.

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

5895

Any particular reason for this change? It doesn't look like you make use of it (note that Call->getType() == Op0->getType() below).

[goldstein.w.n]

Don't change func decl

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

5895

Any particular reason for this change? It doesn't look like you make use of it (note that Call->getType() == Op0->getType() below).

Didn't know that was guranteed, fixed.

5931–5932

Remove the "Maybe better..." statement because we can't do that in InstSimplify (can't create new instructions here). But that should happen in InstCombine if it's not already done there.

Is this change needed at all then? Would just knownpow2 -> icmp ne 0 in InstCombine be better?

But can do regardless. One thing, assuming we keep this AND add InstCombine change. Should I duplicate the test file or just add instcombine as a second pass in the current tests?

[spatel]

LGTM

llvm/lib/Analysis/InstructionSimplify.cpp

5931–5932

It's a trade-off, and I'm not sure which way is better in this case. It's nice to make InstSimplify stronger because other passes (like EarlyCSE and GVN) use this as an analysis. But you're correct that it's also good to consolidate related folds. I don't think there's a real compile-time concern either way since ctpop should be too rare to make any difference to overall compile-time.

If you want to add the fold for known-pow2-or-zero to instcombine, add those tests to InstCombine rather than here. There shouldn't be a need to duplicate the ones that are already handled here. The regression tests are meant to be minimal, so we don't want to run multiple/different passes here.

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

5931–5932

It's a trade-off, and I'm not sure which way is better in this case. It's nice to make InstSimplify stronger because other passes (like EarlyCSE and GVN) use this as an analysis. But you're correct that it's also good to consolidate related folds. I don't think there's a real compile-time concern either way since ctpop should be too rare to make any difference to overall compile-time.

If you want to add the fold for known-pow2-or-zero to instcombine, add those tests to InstCombine rather than here. There shouldn't be a need to duplicate the ones that are already handled here. The regression tests are meant to be minimal, so we don't want to run multiple/different passes here.

Got it & Thanks!

Quick question about protocol when a code change is accepted but the test patch isn't. Is it assumed that NFC test changes are okay to just push in that case or should I wait on separate approval there?

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

5931–5932

D141989 is accepted too. Generally, you can add/adjust tests as an NFC patch without pre-commit approval if you already have commit access.

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyRelativeLoad(Constant *Ptr, Constant *Offset,
   if (!IsConstantOffsetFromGlobal(LoadedRHS, LoadedRHSSym, LoadedRHSOffset,
                                   DL) ||
       PtrSym != LoadedRHSSym || PtrOffset != LoadedRHSOffset)
     return nullptr;
 
   return ConstantExpr::getBitCast(LoadedLHSPtr, Int8PtrTy);
 }
 
 static Value *simplifyUnaryIntrinsic(Function *F, Value *Op0,
                                      const SimplifyQuery &Q) {
   // Idempotent functions return the same result when called repeatedly.
   Intrinsic::ID IID = F->getIntrinsicID();
   if (isIdempotent(IID))
     if (auto *II = dyn_cast<IntrinsicInst>(Op0))
       if (II->getIntrinsicID() == IID)
         return II;
 
   if (removesFPFraction(IID)) {
     // Converting from int or calling a rounding function always results in a
if (match(Op0, m_BSwap(m_Value(X))))
       return X;
     break;
   case Intrinsic::bitreverse:
     // bitreverse(bitreverse(x)) -> x
     if (match(Op0, m_BitReverse(m_Value(X))))
       return X;
     break;
   case Intrinsic::ctpop: {
+    // ctpop(X) -> 1 iff X is non-zero power of 2.
+    if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ false, 0, Q.AC, Q.CxtI,
+                               Q.DT))
+      return ConstantInt::get(Op0->getType(), 1);
     // If everything but the lowest bit is zero, that bit is the pop-count. Ex:
     // ctpop(and X, 1) --> and X, 1
     unsigned BitWidth = Op0->getType()->getScalarSizeInBits();
     if (MaskedValueIsZero(Op0, APInt::getHighBitsSet(BitWidth, BitWidth - 1),
                           Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
       return Op0;
     break;
   }

llvm/test/Transforms/InstSimplify/ctpop-pow2.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instsimplify -S | FileCheck %s
 
 declare i64 @llvm.ctpop.i64(i64)
 declare i32 @llvm.ctpop.i32(i32)
 declare i16 @llvm.ctpop.i16(i16)
 declare i8 @llvm.ctpop.i8(i8)
 declare <2 x i32> @llvm.ctpop.v2i32(<2 x i32>)
 declare void @llvm.assume(i1)
 
 define i64 @ctpop_1_shl(i64 %x) {
 ; CHECK-LABEL: @ctpop_1_shl(
-; CHECK-NEXT:    [[V:%.*]] = shl i64 1, [[X:%.*]]
-; CHECK-NEXT:    [[CNT:%.*]] = call i64 @llvm.ctpop.i64(i64 [[V]])
-; CHECK-NEXT:    ret i64 [[CNT]]
+; CHECK-NEXT:    ret i64 1
 ;
   %v = shl i64 1, %x
   %cnt = call i64 @llvm.ctpop.i64(i64 %v)
   ret i64 %cnt
 }
 
 define i32 @ctpop_imin_lshr(i32 %x) {
 ; CHECK-LABEL: @ctpop_imin_lshr(
-; CHECK-NEXT:    [[V:%.*]] = lshr i32 -2147483648, [[X:%.*]]
-; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.ctpop.i32(i32 [[V]])
-; CHECK-NEXT:    ret i32 [[CNT]]
+; CHECK-NEXT:    ret i32 1
 ;
   %v = lshr i32 2147483648, %x
   %cnt = call i32 @llvm.ctpop.i32(i32 %v)
   ret i32 %cnt
 }
 
 define i16 @ctpop_x_and_negx(i16 %x) {
 ; CHECK-LABEL: @ctpop_x_and_negx(
;
   %cmp = icmp ne i64 %v1, 0
   call void @llvm.assume(i1 %cmp)
   %cnt = call i64 @llvm.ctpop.i64(i64 %v1)
   ret i64 %cnt
 }
 
 define <2 x i32> @ctpop_shl1_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @ctpop_shl1_vec(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> <i32 1, i32 1>, [[X:%.*]]
-; CHECK-NEXT:    [[CNT:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[SHL]])
-; CHECK-NEXT:    ret <2 x i32> [[CNT]]
+; CHECK-NEXT:    ret <2 x i32> <i32 1, i32 1>
 ;
   %shl = shl <2 x i32> <i32 1 ,i32 1>, %x
   %cnt = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %shl)
   ret <2 x i32> %cnt
 }
 
 define <2 x i32> @ctpop_shl2_1_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @ctpop_shl2_1_vec(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> <i32 2, i32 1>, [[X:%.*]]
 ; CHECK-NEXT:    [[CNT:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[SHL]])
 ; CHECK-NEXT:    ret <2 x i32> [[CNT]]
 ;
   %shl = shl <2 x i32> <i32 2 ,i32 1>, %x
   %cnt = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %shl)
   ret <2 x i32> %cnt
 }
 
 define <2 x i32> @ctpop_lshr_intmin_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @ctpop_lshr_intmin_vec(
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i32> <i32 -2147483648, i32 -2147483648>, [[X:%.*]]
-; CHECK-NEXT:    [[CNT:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[SHR]])
-; CHECK-NEXT:    ret <2 x i32> [[CNT]]
+; CHECK-NEXT:    ret <2 x i32> <i32 1, i32 1>
 ;
   %shr = lshr <2 x i32> <i32 2147483648 ,i32 2147483648>, %x
   %cnt = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %shr)
   ret <2 x i32> %cnt
 }
 
 
 define <2 x i32> @ctpop_lshr_intmin_intmin_plus1_vec(<2 x i32> %x) {