[InstCombine] ctpop(X) + ctpop(Y) => ctpop(X | Y) if X and Y have no common bits (PR48999)

[xbolva00]

Summary

For example:

int src(unsigned int a, unsigned int b)
{
    return __builtin_popcount(a << 16) + __builtin_popcount(b >> 16);
}

int tgt(unsigned int a, unsigned int b)
{
    return __builtin_popcount((a << 16)  | (b >> 16));
}

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1453

As the pattern on both sides is the same, you don't need to use m_c_BinOp, you can just directly match LHS and RHS against ctpop.

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1453

I am bit confused now. Not same?
I can match lhs and rhs but then I need 2x mode code to handle ctpop(B) + ctpop(A) too.

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1453

Ignore me, got it :)

[xbolva00]

Code simplified. Thanks nikic

[nikic]

LGTM

llvm/test/Transforms/InstCombine/ctpop.ll

208

We could optimize ctpop(rot(X)) -> ctpop(X).

[nikic]

llvm/test/Transforms/InstCombine/ctpop.ll

208

Though I'm not sure that was actually the case you wanted to test. As you still have the %a argument, maybe this was just a typo :)

[xbolva00]

llvm/test/Transforms/InstCombine/ctpop.ll

208

Yeah, typo, but ctpop(rot(X)) -> ctpop(X) is good idea.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
   // usub.sat(A, B) + B => umax(A, B)
   if (match(&I, m_c_BinOp(
           m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Value(A), m_Value(B))),
           m_Deferred(B)))) {
     return replaceInstUsesWith(I,
         Builder.CreateIntrinsic(Intrinsic::umax, {I.getType()}, {A, B}));
   }
 
+  // ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common.
+  if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) &&
+      match(RHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(B)))) &&
+      haveNoCommonBitsSet(A, B, DL, &AC, &I, &DT))
+    return replaceInstUsesWith(
+        I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
+                                   {Builder.CreateOr(A, B)}));
+
   return Changed ? &I : nullptr;
 }
 
 /// Eliminate an op from a linear interpolation (lerp) pattern.
 static Instruction *factorizeLerp(BinaryOperator &I,
                                   InstCombiner::BuilderTy &Builder) {
   Value *X, *Y, *Z;
   if (!match(&I, m_c_FAdd(m_OneUse(m_c_FMul(m_Value(Y),

llvm/test/Transforms/InstCombine/ctpop.ll

;
   %and2 = and i32 %b, 2
   %ctpop2 = tail call i32 @llvm.ctpop.i32(i32 %and2)
   %res = add i32 %ctpop1, %ctpop2
   ret i32 %res
 }
 
 define i32 @ctpop_add_no_common_bits(i32 %a, i32 %b) {
 ; CHECK-LABEL: @ctpop_add_no_common_bits(
-; CHECK-NEXT:    [[SHL16:%.*]] = shl i32 [[B:%.*]], 16
-; CHECK-NEXT:    [[CTPOP1:%.*]] = tail call i32 @llvm.ctpop.i32(i32 [[SHL16]]), !range [[RNG3:![0-9]+]]
-; CHECK-NEXT:    [[LSHL16:%.*]] = lshr i32 [[B]], 16
-; CHECK-NEXT:    [[CTPOP2:%.*]] = tail call i32 @llvm.ctpop.i32(i32 [[LSHL16]]), !range [[RNG3]]
-; CHECK-NEXT:    [[RES:%.*]] = add nuw nsw i32 [[CTPOP1]], [[CTPOP2]]
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.fshl.i32(i32 [[B:%.*]], i32 [[B]], i32 16)
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP1]]), !range [[RNG1]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %shl16 = shl i32 %b, 16
   %ctpop1 = tail call i32 @llvm.ctpop.i32(i32 %shl16)
   %lshl16 = lshr i32 %b, 16
   %ctpop2 = tail call i32 @llvm.ctpop.i32(i32 %lshl16)
   %res = add i32 %ctpop1, %ctpop2
   ret i32 %res
 }
 
 define <2 x i32> @ctpop_add_no_common_bits_vec(<2 x i32> %a, <2 x i32> %b) {
 ; CHECK-LABEL: @ctpop_add_no_common_bits_vec(
-; CHECK-NEXT:    [[SHL16:%.*]] = shl <2 x i32> [[A:%.*]], <i32 16, i32 16>
-; CHECK-NEXT:    [[CTPOP1:%.*]] = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[SHL16]])
-; CHECK-NEXT:    [[LSHL16:%.*]] = lshr <2 x i32> [[B:%.*]], <i32 16, i32 16>
-; CHECK-NEXT:    [[CTPOP2:%.*]] = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[LSHL16]])
-; CHECK-NEXT:    [[RES:%.*]] = add nuw nsw <2 x i32> [[CTPOP1]], [[CTPOP2]]
-; CHECK-NEXT:    ret <2 x i32> [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i32> @llvm.fshl.v2i32(<2 x i32> [[A:%.*]], <2 x i32> [[B:%.*]], <2 x i32> <i32 16, i32 16>)
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[TMP1]])
+; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %shl16 = shl <2 x i32> %a, <i32 16, i32 16>
   %ctpop1 = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %shl16)
   %lshl16 = lshr <2 x i32> %b, <i32 16, i32 16>
   %ctpop2 = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %lshl16)
   %res = add <2 x i32> %ctpop1, %ctpop2
   ret <2 x i32> %res
 }