[InstCombine] C - ctpop(a) - > ctpop(~a)) if C is bitwidth (PR50104)

[xbolva00]

Summary

Proof: https://alive2.llvm.org/ce/z/mncA9K
Solves https://bugs.llvm.org/show_bug.cgi?id=50104

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (Instruction *V =
     return V;
 
   // X - usub.sat(X, Y) => umin(X, Y)
   if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Specific(Op0),
                                                            m_Value(Y)))))
     return replaceInstUsesWith(
         I, Builder.CreateIntrinsic(Intrinsic::umin, {I.getType()}, {Op0, Y}));
 
+  // C - ctpop(X) => ctpop(~X) if C is bitwidth
+  if (match(Op0, m_SpecificInt(Ty->getScalarSizeInBits())) &&
+      match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(X)))))
+    return replaceInstUsesWith(
+        I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
+                                   {Builder.CreateNot(X)}));
+
   return TryToNarrowDeduceFlags();
 }
 
 /// This eliminates floating-point negation in either 'fneg(X)' or
 /// 'fsub(-0.0, X)' form by combining into a constant operand.
 static Instruction *foldFNegIntoConstant(Instruction &I) {
   Value *X;
   Constant *C;

llvm/test/Transforms/InstCombine/ctpop-cttz.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -instcombine | FileCheck %s
 
 declare i32 @llvm.ctpop.i32(i32)
 declare <2 x i32> @llvm.ctpop.v2i32(<2 x i32>)
 
 ; PR43513
 ; __builtin_popcount(i | -i) -> 32 - __builtin_cttz(i, false)
 define i32 @ctpop1(i32 %0) {
 ; CHECK-LABEL: @ctpop1(
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0:%.*]], i1 false), !range !0
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0:%.*]], i1 false), !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %2 = sub i32 0, %0
   %3 = or i32 %0, %2
   %4 = tail call i32 @llvm.ctpop.i32(i32 %3)
   %5 = sub i32 32, %4
   ret i32 %5
 }
;
   %4 = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %3)
   ret <2 x i32> %4
 }
 
 define i32 @ctpop1_multiuse(i32 %0) {
 ; CHECK-LABEL: @ctpop1_multiuse(
 ; CHECK-NEXT:    [[TMP2:%.*]] = sub i32 0, [[TMP0:%.*]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP2]], [[TMP0]]
-; CHECK-NEXT:    [[TMP4:%.*]] = tail call i32 @llvm.ctpop.i32(i32 [[TMP3]]), !range !0
-; CHECK-NEXT:    [[TMP5:%.*]] = sub nuw nsw i32 32, [[TMP4]]
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i32 [[TMP3]], -1
+; CHECK-NEXT:    [[TMP5:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP4]]), !range [[RNG0]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[TMP5]], [[TMP3]]
 ; CHECK-NEXT:    ret i32 [[TMP6]]
 ;
   %2 = sub i32 0, %0
   %3 = or i32 %0, %2
   %4 = tail call i32 @llvm.ctpop.i32(i32 %3)
   %5 = sub i32 32, %4
   %6 = add i32 %5, %3
   ret i32 %6
 }
 
 ; PR43513
 ; __builtin_popcount(~i & (i-1)) -> __builtin_cttz(i, false)
 define i32 @ctpop2(i32 %0) {
 ; CHECK-LABEL: @ctpop2(
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0:%.*]], i1 false), !range !0
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0:%.*]], i1 false), !range [[RNG0]]
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %2 = xor i32 %0, -1
   %3 = sub i32 %0, 1
   %4 = and i32 %3, %2
   %5 = tail call i32 @llvm.ctpop.i32(i32 %4)
   ret i32 %5
 }
;
   ret <2 x i32> %5
 }
 
 define i32 @ctpop2_multiuse(i32 %0) {
 ; CHECK-LABEL: @ctpop2_multiuse(
 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP0:%.*]], -1
 ; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP0]], -1
 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], [[TMP2]]
-; CHECK-NEXT:    [[TMP5:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0]], i1 false), !range !0
+; CHECK-NEXT:    [[TMP5:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0]], i1 false), !range [[RNG0]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[TMP5]], [[TMP4]]
 ; CHECK-NEXT:    ret i32 [[TMP6]]
 ;
   %2 = xor i32 %0, -1
   %3 = sub i32 %0, 1
   %4 = and i32 %3, %2
   %5 = tail call i32 @llvm.ctpop.i32(i32 %4)
   %6 = add i32 %5, %4
   ret i32 %6
 }

llvm/test/Transforms/InstCombine/ctpop.ll

;
   ret i8 %res
 }
 
 declare i8 @llvm.fshl.i8(i8, i8, i8)
 declare i8 @llvm.fshr.i8(i8, i8, i8)
 
 define i8 @sub_ctpop(i8 %a)  {
 ; CHECK-LABEL: @sub_ctpop(
-; CHECK-NEXT:    [[CNT:%.*]] = tail call i8 @llvm.ctpop.i8(i8 [[A:%.*]]), !range [[RNG0]]
-; CHECK-NEXT:    [[RES:%.*]] = sub nuw nsw i8 8, [[CNT]]
-; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.ctpop.i8(i8 [[TMP1]]), !range [[RNG0]]
+; CHECK-NEXT:    ret i8 [[TMP2]]
 ;
   %cnt = tail call i8 @llvm.ctpop.i8(i8 %a)
   %res = sub i8 8, %cnt
   ret i8 %res
 }
 
 define i8 @sub_ctpop_wrong_cst(i8 %a)  {
 ; CHECK-LABEL: @sub_ctpop_wrong_cst(

 ;
   %cnt = tail call i8 @llvm.ctpop.i8(i8 %a)
   %res = sub i8 %b, %cnt
   ret i8 %res
 }
 
 define <2 x i32> @sub_ctpop_vec(<2 x i32> %a) {
 ; CHECK-LABEL: @sub_ctpop_vec(
-; CHECK-NEXT:    [[CNT:%.*]] = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[A:%.*]])
-; CHECK-NEXT:    [[RES:%.*]] = sub nuw nsw <2 x i32> <i32 32, i32 32>, [[CNT]]
-; CHECK-NEXT:    ret <2 x i32> [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i32> [[A:%.*]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[TMP1]])
+; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %cnt = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %a)
   %res = sub <2 x i32> <i32 32, i32 32>, %cnt
   ret <2 x i32> %res
 }
 
 define <2 x i32> @sub_ctpop_vec_extra_use(<2 x i32> %a, <2 x i32>* %p) {
 ; CHECK-LABEL: @sub_ctpop_vec_extra_use(