[Instcombiner]Improve emission of logical or/and reductions.

[ABataev]

Summary

For logical or/and reductions we emit regular intrinsics @llvm.vector.reduce.or/and.vxi1 calls.
These intrinsics are not effective for the logical or/and reductions,
especially if the optimizer is able to emit short circuit versions of
the scalar or/and instructions and vector code gets less effective than
the scalar version.
Instead, or reduction for i1 can be represented as:

%val = bitcast <ReduxWidth x i1> to iReduxWidth
%res = cmp ne iReduxWidth %val, 0

and reduction for i1 can be represented as:

%val = bitcast <ReduxWidth x i1> to iReduxWidth
%res = cmp eq iReduxWidth %val, 11111

This improves perfromance of the vector code significantly and make it
to outperform short circuit scalar code.

[ABataev]

Summary improvements

[sdesmalen]

Hi @ABataev, I saw this patch come by and left some comments, hope that's alright!

llvm/lib/Transforms/Utils/LoopUtils.cpp

1031 ↗

(On Diff #326187)

Can you add the condition that && isa<FixedVectorType>(Src)? (same request for LoopVectorize.cpp and SLPVectorize.cpp)

We're starting to make the LoopVectorizer vectorize for scalable VFs. This means we're currently fixing up cases like this where assumptions are made that are only valid for fixed-width vectors. For scalable vectors it might be possible to do the <vscale x N x i1> reduction as a compare on <vscale x 1 x iN>, but at least for SVE I know that we never want that.

1034–1036 ↗

(On Diff #326187)

nit: cast<FixedVectorType>(Src->getType())->getNumElements()

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6949–6964

Should this be part of BasicTTImpl::getArithmeticReductionCost? That way you don't have to implement it twice.

[lebedev.ri]

Why can't we just do the costmodel change, and then canonicalize to the right variant (i.e. away from @llvm.vector.reduce.?.v?i1) in instcombine?

[RKSimon]

In D97406#2587071, @lebedev.ri wrote:

Why can't we just do the costmodel change, and then canonicalize to the right variant (i.e. away from @llvm.vector.reduce.?.v?i1) in instcombine?

+1 I'd prefer to avoid yet more special cases in the vectorizers.

[ABataev]

Yeah, I also thought about moving this to instcombiner. This patch originally is more a question where it is better to implement it. I'll move the transformation to the instcombiner.

llvm/lib/Transforms/Utils/LoopUtils.cpp

1031 ↗

(On Diff #326187)

Sure, will do.

[ABataev]

Address comments.

[RKSimon]

Can't all the vectorizer code be removed now? X86TTIImpl::getArithmeticReductionCost already has bool reduction costs - not sure if we need to improve the default costs ?

[ABataev]

In D97406#2590716, @RKSimon wrote:

Can't all the vectorizer code be removed now? X86TTIImpl::getArithmeticReductionCost already has bool reduction costs - not sure if we need to improve the default costs ?

Looks like the bool reduction costs are too high because they still rely on some vector instructions. The cost of bitcast + cmp is much lower than even AVX512 bool reductions, for example. What we can do, is to check ащкall targets that we have or/and bool reduction and fallback to the BasicTTI cost. And teach BasicTTI that the cost of bool or/and reductions is actually just bitcast+cmp.

[ABataev]

Rebase

[lebedev.ri]

llvm/lib/Transforms/Vectorize/ changes should not be there, the costmodel itself should be fixed.

[ABataev]

In D97406#2597397, @lebedev.ri wrote:

llvm/lib/Transforms/Vectorize/ changes should not be there, the costmodel itself should be fixed.

So, do you suggest modifying getArithmeticReductionCost to return the correct cost for logical reductions?

[lebedev.ri]

In D97406#2597419, @ABataev wrote:

In D97406#2597397, @lebedev.ri wrote:

llvm/lib/Transforms/Vectorize/ changes should not be there, the costmodel itself should be fixed.

So, do you suggest modifying getArithmeticReductionCost to return the correct cost for logical reductions?

Something along those lines, yes.

Also, could you please split off the instcombine change? That is basically LG.

llvm/test/Transforms/InstCombine/vector-logical-reductions.ll

4–30

These tests are too complex, they should be just:

[ABataev]

In D97406#2597430, @lebedev.ri wrote:

In D97406#2597419, @ABataev wrote:

In D97406#2597397, @lebedev.ri wrote:

llvm/lib/Transforms/Vectorize/ changes should not be there, the costmodel itself should be fixed.

So, do you suggest modifying getArithmeticReductionCost to return the correct cost for logical reductions?

Something along those lines, yes.

Also, could you please split off the instcombine change? That is basically LG.

Ok.

llvm/test/Transforms/InstCombine/vector-logical-reductions.ll

4–30

Will fix

[ABataev]

Removed cost update

[lebedev.ri]

Hm, actually, are we sure this is universally true/better?
For aarch64 this seems to result in larger codegen: https://godbolt.org/z/hczeMo

[RKSimon]

In D97406#2597601, @lebedev.ri wrote:

Hm, actually, are we sure this is universally true/better?
For aarch64 this seems to result in larger codegen: https://godbolt.org/z/hczeMo

Is this the same as these?
https://bugs.llvm.org/show_bug.cgi?id=41636
https://bugs.llvm.org/show_bug.cgi?id=41635
https://bugs.llvm.org/show_bug.cgi?id=41634

[ABataev]

In D97406#2597705, @RKSimon wrote:

In D97406#2597601, @lebedev.ri wrote:

Hm, actually, are we sure this is universally true/better?
For aarch64 this seems to result in larger codegen: https://godbolt.org/z/hczeMo

Is this the same as these?
https://bugs.llvm.org/show_bug.cgi?id=41636
https://bugs.llvm.org/show_bug.cgi?id=41635
https://bugs.llvm.org/show_bug.cgi?id=41634

Yes, looks so.

[lebedev.ri]

Okay, let's call this canonicalization.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (DstTy && VecTy) {
 
       Value *Shuffle =
           Builder.CreateShuffleVector(Vec, UndefValue::get(VecTy), Mask);
       replaceInstUsesWith(CI, Shuffle);
       return eraseInstFromFunction(CI);
     }
     break;
   }
+  case Intrinsic::vector_reduce_or:
+  case Intrinsic::vector_reduce_and: {
+    // Canonicalize logical or/and reductions:
+    // Or reduction for i1 is represented as:
+    // %val = bitcast <ReduxWidth x i1> to iReduxWidth
+    // %res = cmp ne iReduxWidth %val, 0
+    // And reduction for i1 is represented as:
+    // %val = bitcast <ReduxWidth x i1> to iReduxWidth
+    // %res = cmp eq iReduxWidth %val, 11111
+    Value *Arg = II->getArgOperand(0);
+    Type *RetTy = II->getType();
+    if (RetTy == Builder.getInt1Ty())
+      if (auto *FVTy = dyn_cast<FixedVectorType>(Arg->getType())) {
+        Value *Res = Builder.CreateBitCast(
+            Arg, Builder.getIntNTy(FVTy->getNumElements()));
+        if (IID == Intrinsic::vector_reduce_and) {
+          Res = Builder.CreateICmpEQ(
+              Res, ConstantInt::getAllOnesValue(Res->getType()));
+        } else {
+          assert(IID == Intrinsic::vector_reduce_or &&
+                 "Expected or reduction.");
+          Res = Builder.CreateIsNotNull(Res);
+        }
+        replaceInstUsesWith(CI, Res);
+        return eraseInstFromFunction(CI);
+      }
+    break;
+  }
   default: {
     // Handle target specific intrinsics
     Optional<Instruction *> V = targetInstCombineIntrinsic(*II);
     if (V.hasValue())
       return V.getValue();
     break;
   }
   }

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

InstructionCost LoopVectorizationCostModel::getReductionPatternCost(
   // the reduction on its own.
   Instruction *LastChain = InLoopReductionImmediateChains[RetI];
   Instruction *ReductionPhi = LastChain;
   while (!isa<PHINode>(ReductionPhi))
     ReductionPhi = InLoopReductionImmediateChains[ReductionPhi];
 
   RecurrenceDescriptor RdxDesc =
       Legal->getReductionVars()[cast<PHINode>(ReductionPhi)];
-  unsigned BaseCost = TTI.getArithmeticReductionCost(RdxDesc.getOpcode(),
-                                                     VectorTy, false, CostKind);
+  unsigned BaseCost;
+  RecurKind RdxKind = RdxDesc.getRecurrenceKind();
+  RdxDesc.getRecurrenceType();
+  if ((RdxKind == RecurKind::Or || RdxKind == RecurKind::And) &&
+      isa<FixedVectorType>(VectorTy) &&
+      VectorTy->getElementType() ==
+          IntegerType::getInt1Ty(VectorTy->getContext())) {
+    // Or reduction for i1 is represented as:
+    // %val = bitcast <ReduxWidth x i1> to iReduxWidth
+    // %res = cmp ne iReduxWidth %val, 0
+    // And reduction for i1 is represented as:
+    // %val = bitcast <ReduxWidth x i1> to iReduxWidth
+    // %res = cmp eq iReduxWidth %val, 11111
+    Type *ValTy = IntegerType::get(VectorTy->getContext(),
+                                   VectorTy->getElementCount().getFixedValue());
+    BaseCost = TTI.getCastInstrCost(Instruction::BitCast, ValTy, VectorTy,
+                                    TTI::CastContextHint::None,
+                                    TTI::TCK_RecipThroughput) +
+               TTI.getCmpSelInstrCost(Instruction::ICmp, ValTy,
+                                      CmpInst::makeCmpResultType(ValTy));
+  } else {
+    BaseCost =
+        TTI.getArithmeticReductionCost(RdxDesc.getOpcode(), VectorTy,
+                                       /*IsPairwiseForm=*/false, CostKind);
+  }
 
   // Get the operand that was not the reduction chain and match it to one of the
   // patterns, returning the better cost if it is found.
   Instruction *RedOp = RetI->getOperand(1) == LastChain
                            ? dyn_cast<Instruction>(RetI->getOperand(0))
                            : dyn_cast<Instruction>(RetI->getOperand(1));
 
   VectorTy = VectorType::get(I->getOperand(0)->getType(), VectorTy);

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

InstructionCost getReductionCost(TargetTransformInfo *TTI,
     case RecurKind::Add:
     case RecurKind::Mul:
     case RecurKind::Or:
     case RecurKind::And:
     case RecurKind::Xor:
     case RecurKind::FAdd:
     case RecurKind::FMul: {
       unsigned RdxOpcode = RecurrenceDescriptor::getOpcode(RdxKind);
+      if ((RdxKind == RecurKind::Or || RdxKind == RecurKind::And) &&
+          ScalarTy == IntegerType::getInt1Ty(FirstReducedVal->getContext())) {
+        // Or reduction for i1 is represented as:
+        // %val = bitcast <ReduxWidth x i1> to iReduxWidth
+        // %res = cmp ne iReduxWidth %val, 0
+        // And reduction for i1 is represented as:
+        // %val = bitcast <ReduxWidth x i1> to iReduxWidth
+        // %res = cmp eq iReduxWidth %val, 11111
+        Type *ValTy =
+            IntegerType::get(FirstReducedVal->getContext(), ReduxWidth);
+        VectorCost = TTI->getCastInstrCost(Instruction::BitCast, ValTy,
+                                           VectorTy, TTI::CastContextHint::None,
+                                           TTI::TCK_RecipThroughput) +
+                     TTI->getCmpSelInstrCost(Instruction::ICmp, ValTy,
+                                             CmpInst::makeCmpResultType(ValTy));
+      } else {
         VectorCost = TTI->getArithmeticReductionCost(RdxOpcode, VectorTy,
                                                      /*IsPairwiseForm=*/false);
+      }
       ScalarCost = TTI->getArithmeticInstrCost(RdxOpcode, ScalarTy);
       break;
     }
     case RecurKind::FMax:
     case RecurKind::FMin: {
       auto *VecCondTy = cast<VectorType>(CmpInst::makeCmpResultType(VectorTy));
       VectorCost =
           TTI->getMinMaxReductionCost(VectorTy, VecCondTy,

llvm/test/Transforms/InstCombine/vector-logical-reductions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define float @reduction_logical_or(<4 x float> %x) {
 ; CHECK-LABEL: @reduction_logical_or(
 ; CHECK-NEXT:    [[TMP1:%.*]] = fcmp ogt <4 x float> [[X:%.*]], <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>
-; CHECK-NEXT:    [[TMP2:%.*]] = call i1 @llvm.vector.reduce.or.v4i1(<4 x i1> [[TMP1]])
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP2]], float -1.000000e+00, float 1.000000e+00
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast <4 x i1> [[TMP1]] to i4
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i4 [[TMP2]], 0
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[DOTNOT]], float 1.000000e+00, float -1.000000e+00
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %1 = fcmp ogt <4 x float> %x, <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>
   %2 = call i1 @llvm.vector.reduce.or.v4i1(<4 x i1> %1)
   %r = select i1 %2, float -1.000000e+00, float 1.000000e+00
   ret float %r
 }
 
 define float @reduction_logical_and(<4 x float> %x) {
 ; CHECK-LABEL: @reduction_logical_and(
 ; CHECK-NEXT:    [[TMP1:%.*]] = fcmp ogt <4 x float> [[X:%.*]], <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>
-; CHECK-NEXT:    [[TMP2:%.*]] = call i1 @llvm.vector.reduce.and.v4i1(<4 x i1> [[TMP1]])
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP2]], float -1.000000e+00, float 1.000000e+00
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast <4 x i1> [[TMP1]] to i4
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i4 [[TMP2]], -1
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP3]], float -1.000000e+00, float 1.000000e+00
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %1 = fcmp ogt <4 x float> %x, <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>
   %2 = call i1 @llvm.vector.reduce.and.v4i1(<4 x i1> %1)
   %r = select i1 %2, float -1.000000e+00, float 1.000000e+00
   ret float %r
 }
 
 declare i1 @llvm.vector.reduce.or.v4i1(<4 x i1>)
 declare i1 @llvm.vector.reduce.and.v4i1(<4 x i1>)