[Instcombine]Transform reduction+(sext/zext(<n x i1>) to <n x im>) to [-]zext/trunc(ctpop(bitcast <n x i1> to in)) to im.

[ABataev]

Summary

Some of the SPEC tests end up with reduction+(sext/zext(<n x i1>) to <n x im>) pattern, which can be transformed to [-]zext/trunc(ctpop(bitcast <n x i1> to in)) to im.

https://alive2.llvm.org/ce/z/TBZbdZ
https://alive2.llvm.org/ce/z/N6qJGz

[RKSimon]

Seems to be correct: https://alive2.llvm.org/ce/z/TBZbdZ

[ABataev]

In D105587#2864251, @RKSimon wrote:

Seems to be correct: https://alive2.llvm.org/ce/z/TBZbdZ

Yes, checked it via alive2 before uploading

[lebedev.ri]

In D105587#2864252, @ABataev wrote:

In D105587#2864251, @RKSimon wrote:

Seems to be correct: https://alive2.llvm.org/ce/z/TBZbdZ

Yes, checked it via alive2 before uploading

While not required, since you already had it, it is really good to make patch description more useful by adding such details there.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2006

Extension is optional: https://alive2.llvm.org/ce/z/N6qJGz
Please either use m_ZExtOrSExtOrSelf(), or if it's already handled elsewhere add a comment about that.

[ABataev]

In D105587#2864256, @lebedev.ri wrote:

In D105587#2864252, @ABataev wrote:

In D105587#2864251, @RKSimon wrote:

Seems to be correct: https://alive2.llvm.org/ce/z/TBZbdZ

Yes, checked it via alive2 before uploading

While not required, since you already had it, it is really good to make patch description more useful by adding such details there.

Sure.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2006

Did not see such a pattern but will check if it is handled already and use add m_ZExtOrSExtOrSelf.

[ABataev]

Address comments

[lebedev.ri]

llvm/test/Transforms/InstCombine/reduction-add-sext-zext-i1.ll

1

Please precommit

65

Could use a test where the zext/sext has extra use and doesn't go away.

[lebedev.ri]

LG with nits

[ABataev]

llvm/test/Transforms/InstCombine/reduction-add-sext-zext-i1.ll

1

Will do.

65

Will add

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2020

Seems to be a recurring pattern in these folds, but why does this call replaceInstUsesWith and eraseInstFromInstruction, rather than doing just return replaceInstUsesWith()?

[ABataev]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2020

I'm not quite familiar with these interfaces, just copied from other places. Do you suggest replacing it with just return replaceInstUsesWith(CI, Res);?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2020

Yeah, that should be sufficient.

[ABataev]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2020

Ok, thanks for the advice, will do

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (RetTy == Builder.getInt1Ty())
                  "Expected or reduction.");
           Res = Builder.CreateIsNotNull(Res);
         }
         replaceInstUsesWith(CI, Res);
         return eraseInstFromFunction(CI);
       }
     LLVM_FALLTHROUGH;
   }
-  case Intrinsic::vector_reduce_add:
+  case Intrinsic::vector_reduce_add: {
+    if (IID == Intrinsic::vector_reduce_add) {
+      // Convert vector_reduce_add(ZExt(<n x i1>)) to
+      // ZExtOrTrunc(ctpop(bitcast <n x i1> to in)).
+      // Convert vector_reduce_add(SExt(<n x i1>)) to
+      // -ZExtOrTrunc(ctpop(bitcast <n x i1> to in)).
+      // Convert vector_reduce_add(<n x i1>) to
+      // Trunc(ctpop(bitcast <n x i1> to in)).
+      Value *Arg = II->getArgOperand(0);
+      Value *Vect;
+      if (match(Arg, m_ZExtOrSExtOrSelf(m_Value(Vect)))) {
+        if (auto *FTy = dyn_cast<FixedVectorType>(Vect->getType()))
+          if (FTy->getElementType() == Builder.getInt1Ty()) {
+            Value *V = Builder.CreateBitCast(
+                Vect, Builder.getIntNTy(FTy->getNumElements()));
+            Value *Res = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, V);
+            if (Res->getType() != II->getType())
+              Res = Builder.CreateZExtOrTrunc(Res, II->getType());
+            if (Arg != Vect &&
+                cast<Instruction>(Arg)->getOpcode() == Instruction::SExt)
+              Res = Builder.CreateNeg(Res);
+            replaceInstUsesWith(CI, Res);
+            return eraseInstFromFunction(CI);
+          }
+      }
+    }
+    LLVM_FALLTHROUGH;
+  }
   case Intrinsic::vector_reduce_mul:
   case Intrinsic::vector_reduce_xor:
   case Intrinsic::vector_reduce_umax:
   case Intrinsic::vector_reduce_umin:
   case Intrinsic::vector_reduce_smax:
   case Intrinsic::vector_reduce_smin:
   case Intrinsic::vector_reduce_fmax:
   case Intrinsic::vector_reduce_fmin:

llvm/test/Transforms/InstCombine/reduction-add-sext-zext-i1.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define i1 @reduce_add_self(<8 x i1> %x) {
 ; CHECK-LABEL: @reduce_add_self(
-; CHECK-NEXT:    [[RES:%.*]] = call i1 @llvm.vector.reduce.add.v8i1(<8 x i1> [[X:%.*]])
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <8 x i1> [[X:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.ctpop.i8(i8 [[TMP1]]), !range [[RNG0:![0-9]+]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i8 [[TMP2]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i8 [[TMP3]], 0
+; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %res = call i1 @llvm.vector.reduce.add.v8i32(<8 x i1> %x)
   ret i1 %res
 }
 
 define i32 @reduce_add_sext(<4 x i1> %x) {
 ; CHECK-LABEL: @reduce_add_sext(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext <4 x i1> [[X:%.*]] to <4 x i32>
-; CHECK-NEXT:    [[RES:%.*]] = call i32 @llvm.vector.reduce.add.v4i32(<4 x i32> [[SEXT]])
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <4 x i1> [[X:%.*]] to i4
+; CHECK-NEXT:    [[TMP2:%.*]] = call i4 @llvm.ctpop.i4(i4 [[TMP1]]), !range [[RNG1:![0-9]+]]
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i4 [[TMP2]] to i32
+; CHECK-NEXT:    [[TMP4:%.*]] = sub nsw i32 0, [[TMP3]]
+; CHECK-NEXT:    ret i32 [[TMP4]]
 ;
   %sext = sext <4 x i1> %x to <4 x i32>
   %res = call i32 @llvm.vector.reduce.add.v4i32(<4 x i32> %sext)
   ret i32 %res
 }
 
 define i64 @reduce_add_zext(<8 x i1> %x) {
 ; CHECK-LABEL: @reduce_add_zext(
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext <8 x i1> [[X:%.*]] to <8 x i64>
-; CHECK-NEXT:    [[RES:%.*]] = call i64 @llvm.vector.reduce.add.v8i64(<8 x i64> [[ZEXT]])
-; CHECK-NEXT:    ret i64 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <8 x i1> [[X:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.ctpop.i8(i8 [[TMP1]]), !range [[RNG0]]
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[TMP2]] to i64
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %zext = zext <8 x i1> %x to <8 x i64>
   %res = call i64 @llvm.vector.reduce.add.v8i64(<8 x i64> %zext)
   ret i64 %res
 }
 
 define i16 @reduce_add_sext_same(<16 x i1> %x) {
 ; CHECK-LABEL: @reduce_add_sext_same(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext <16 x i1> [[X:%.*]] to <16 x i16>
-; CHECK-NEXT:    [[RES:%.*]] = call i16 @llvm.vector.reduce.add.v16i16(<16 x i16> [[SEXT]])
-; CHECK-NEXT:    ret i16 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <16 x i1> [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = call i16 @llvm.ctpop.i16(i16 [[TMP1]]), !range [[RNG2:![0-9]+]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub nsw i16 0, [[TMP2]]
+; CHECK-NEXT:    ret i16 [[TMP3]]
 ;
   %sext = sext <16 x i1> %x to <16 x i16>
   %res = call i16 @llvm.vector.reduce.add.v16i16(<16 x i16> %sext)
   ret i16 %res
 }
 
 define i8 @reduce_add_zext_long(<128 x i1> %x) {
 ; CHECK-LABEL: @reduce_add_zext_long(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext <128 x i1> [[X:%.*]] to <128 x i8>
-; CHECK-NEXT:    [[RES:%.*]] = call i8 @llvm.vector.reduce.add.v128i8(<128 x i8> [[SEXT]])
-; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <128 x i1> [[X:%.*]] to i128
+; CHECK-NEXT:    [[TMP2:%.*]] = call i128 @llvm.ctpop.i128(i128 [[TMP1]]), !range [[RNG3:![0-9]+]]
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc i128 [[TMP2]] to i8
+; CHECK-NEXT:    [[TMP4:%.*]] = sub i8 0, [[TMP3]]
+; CHECK-NEXT:    ret i8 [[TMP4]]
 ;
   %sext = sext <128 x i1> %x to <128 x i8>
   %res = call i8 @llvm.vector.reduce.add.v128i8(<128 x i8> %sext)
   ret i8 %res
 }
 
 @glob = external global i8, align 1
 define i8 @reduce_add_zext_long_external_use(<128 x i1> %x) {
 ; CHECK-LABEL: @reduce_add_zext_long_external_use(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext <128 x i1> [[X:%.*]] to <128 x i8>
-; CHECK-NEXT:    [[RES:%.*]] = call i8 @llvm.vector.reduce.add.v128i8(<128 x i8> [[SEXT]])
-; CHECK-NEXT:    [[EXT:%.*]] = extractelement <128 x i8> [[SEXT]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <128 x i1> [[X:%.*]] to i128
+; CHECK-NEXT:    [[TMP2:%.*]] = call i128 @llvm.ctpop.i128(i128 [[TMP1]]), !range [[RNG3]]
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc i128 [[TMP2]] to i8
+; CHECK-NEXT:    [[TMP4:%.*]] = sub i8 0, [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <128 x i1> [[X]], i32 0
+; CHECK-NEXT:    [[EXT:%.*]] = sext i1 [[TMP5]] to i8
 ; CHECK-NEXT:    store i8 [[EXT]], i8* @glob, align 1
-; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK-NEXT:    ret i8 [[TMP4]]
 ;
   %sext = sext <128 x i1> %x to <128 x i8>
   %res = call i8 @llvm.vector.reduce.add.v128i8(<128 x i8> %sext)
   %ext = extractelement <128 x i8> %sext, i32 0
   store i8 %ext, i8* @glob, align 1
   ret i8 %res
 }
 
 @glob1 = external global i64, align 8
 define i64 @reduce_add_zext_external_use(<8 x i1> %x) {
 ; CHECK-LABEL: @reduce_add_zext_external_use(
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext <8 x i1> [[X:%.*]] to <8 x i64>
-; CHECK-NEXT:    [[RES:%.*]] = call i64 @llvm.vector.reduce.add.v8i64(<8 x i64> [[ZEXT]])
-; CHECK-NEXT:    [[EXT:%.*]] = extractelement <8 x i64> [[ZEXT]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <8 x i1> [[X:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.ctpop.i8(i8 [[TMP1]]), !range [[RNG0]]
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[TMP2]] to i64
+; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <8 x i1> [[X]], i32 0
+; CHECK-NEXT:    [[EXT:%.*]] = zext i1 [[TMP4]] to i64
 ; CHECK-NEXT:    store i64 [[EXT]], i64* @glob1, align 8
-; CHECK-NEXT:    ret i64 [[RES]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %zext = zext <8 x i1> %x to <8 x i64>
   %res = call i64 @llvm.vector.reduce.add.v8i64(<8 x i64> %zext)
   %ext = extractelement <8 x i64> %zext, i32 0
   store i64 %ext, i64* @glob1, align 8
   ret i64 %res
 }
 
 declare i1 @llvm.vector.reduce.add.v8i32(<8 x i1> %a)
 declare i32 @llvm.vector.reduce.add.v4i32(<4 x i32> %a)
 declare i64 @llvm.vector.reduce.add.v8i64(<8 x i64> %a)
 declare i16 @llvm.vector.reduce.add.v16i16(<16 x i16> %a)
 declare i8 @llvm.vector.reduce.add.v128i8(<128 x i8> %a)