[InstCombine] ctpop(X) ^ ctpop(Y) & 1 --> ctpop(X^Y) & 1 (PR50094)

[xbolva00]

Summary

Original pattern: (builtin_parity(x) ^ builtin_parity(y))

LLVM rewrites it as: (builtin_popcount(x) ^ builtin_popcount(y)) & 1

Optimized form: __builtin_popcount(X^Y) & 1

Alive proof: https://alive2.llvm.org/ce/z/-GdWFr

[RKSimon]

LGTM with one minor

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

227

// (ctpop(X) ^ ctpop(Y)) & 1 --> ctpop(X^Y) & 1

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

227

Yeah, thx

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

if (ShrinkDemandedConstant(I, 1, DemandedMask))
       return I;
 
     break;
   }
   case Instruction::Xor: {
     if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
         SimplifyDemandedBits(I, 0, DemandedMask, LHSKnown, Depth + 1))
       return I;
+    Value *LHS, *RHS;
+    if (DemandedMask == 1 &&
+        match(I->getOperand(0), m_Intrinsic<Intrinsic::ctpop>(m_Value(LHS))) &&
+        match(I->getOperand(1), m_Intrinsic<Intrinsic::ctpop>(m_Value(RHS)))) {
+      // (ctpop(X) ^ ctpop(Y)) & 1 --> ctpop(X^Y) & 1
+      IRBuilderBase::InsertPointGuard Guard(Builder);
+      Builder.SetInsertPoint(I);
+      auto *Xor = Builder.CreateXor(LHS, RHS);
+      return Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Xor);
+    }
+
     assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
     assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
 
     Known = LHSKnown ^ RHSKnown;
 
     // If the client is only demanding bits that we know, return the known
     // constant.
     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))

llvm/test/Transforms/InstCombine/ctpop.ll

;
   %z = zext i16 %x to i32
   store i32 %z, i32* %q
   %p = call i32 @llvm.ctpop.i32(i32 %z)
   ret i32 %p
 }
 
 define i32 @parity_xor(i32 %arg, i32 %arg1) {
 ; CHECK-LABEL: @parity_xor(
-; CHECK-NEXT:    [[I:%.*]] = tail call i32 @llvm.ctpop.i32(i32 [[ARG:%.*]]), !range [[RNG1]]
-; CHECK-NEXT:    [[I2:%.*]] = tail call i32 @llvm.ctpop.i32(i32 [[ARG1:%.*]]), !range [[RNG1]]
-; CHECK-NEXT:    [[I3:%.*]] = xor i32 [[I2]], [[I]]
-; CHECK-NEXT:    [[I4:%.*]] = and i32 [[I3]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[ARG1:%.*]], [[ARG:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP1]]), !range [[RNG1]]
+; CHECK-NEXT:    [[I4:%.*]] = and i32 [[TMP2]], 1
 ; CHECK-NEXT:    ret i32 [[I4]]
 ;
   %i = tail call i32 @llvm.ctpop.i32(i32 %arg)
   %i2 = tail call i32 @llvm.ctpop.i32(i32 %arg1)
   %i3 = xor i32 %i2, %i
   %i4 = and i32 %i3, 1
   ret i32 %i4
 }
 
 define i32 @parity_xor_trunc(i64 %arg, i64 %arg1) {
 ; CHECK-LABEL: @parity_xor_trunc(
-; CHECK-NEXT:    [[I:%.*]] = tail call i64 @llvm.ctpop.i64(i64 [[ARG:%.*]]), !range [[RNG5:![0-9]+]]
-; CHECK-NEXT:    [[I2:%.*]] = tail call i64 @llvm.ctpop.i64(i64 [[ARG1:%.*]]), !range [[RNG5]]
-; CHECK-NEXT:    [[I3:%.*]] = xor i64 [[I2]], [[I]]
-; CHECK-NEXT:    [[I4:%.*]] = trunc i64 [[I3]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i64 [[ARG1:%.*]], [[ARG:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.ctpop.i64(i64 [[TMP1]]), !range [[RNG5:![0-9]+]]
+; CHECK-NEXT:    [[I4:%.*]] = trunc i64 [[TMP2]] to i32
 ; CHECK-NEXT:    [[I5:%.*]] = and i32 [[I4]], 1
 ; CHECK-NEXT:    ret i32 [[I5]]
 ;
   %i = tail call i64 @llvm.ctpop.i64(i64 %arg)
   %i2 = tail call i64 @llvm.ctpop.i64(i64 %arg1)
   %i3 = xor i64 %i2, %i
   %i4 = trunc i64 %i3 to i32
   %i5 = and i32 %i4, 1
   ret i32 %i5
 }
 
 define <2 x i32> @parity_xor_vec(<2 x i32> %arg, <2 x i32> %arg1) {
 ; CHECK-LABEL: @parity_xor_vec(
-; CHECK-NEXT:    [[I:%.*]] = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[ARG:%.*]])
-; CHECK-NEXT:    [[I2:%.*]] = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[ARG1:%.*]])
-; CHECK-NEXT:    [[I3:%.*]] = xor <2 x i32> [[I2]], [[I]]
-; CHECK-NEXT:    [[I4:%.*]] = and <2 x i32> [[I3]], <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i32> [[ARG1:%.*]], [[ARG:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[TMP1]])
+; CHECK-NEXT:    [[I4:%.*]] = and <2 x i32> [[TMP2]], <i32 1, i32 1>
 ; CHECK-NEXT:    ret <2 x i32> [[I4]]
 ;
   %i = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %arg)
   %i2 = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %arg1)
   %i3 = xor <2 x i32> %i2, %i
   %i4 = and <2 x i32> %i3, <i32 1, i32 1>
   ret <2 x i32> %i4
 }