[SLP] Fixed cost model for horizontal reduction.

[ABataev]

Summary

Currently when cost of scalar operations is evaluated the vector type is used for scalar operations. Patch fixes this issue and fixes evaluation of the vector operations cost.

[mkuper]

Thanks for catching this Alexey, computing the scalar reduction cost with the vector type does look very odd.

include/llvm/CodeGen/BasicTTIImpl.h

932–933

The computation is getting pretty hairy. Could you please add comments explaining what exactly it computes?

I understand you're trying to model the reduction steps performed on illegal vectors and steps performed on legal steps separately, but I'm not sure this computes precisely what we want.

936

Maybe save static_cast<T *>(this) in a temporary, for readability's sake, now that you're adding more uses?

938

I counts the number of illegal reduction steps, right?
Maybe give it a more meaningful name? It's not a regular loop counter where it's obvious what it counts up to.

[ABataev]

include/llvm/CodeGen/BasicTTIImpl.h

932–933

Added several lines of comments trying to explain the new code.

938

Changed to while loop.

[ABataev]

Updated after Michael's comments

[mkuper]

include/llvm/CodeGen/BasicTTIImpl.h

970

ThisT -> ConcreteTTI, or something conveying the same information?
(That's what this actually is, right?)

987

ont eh -> on the

992

Why the +1?
If the type is legal, LongVectorsCount is 0, Ty doesn't change, so this changes the behavior from multiplying by NumReduxLevel to NumReduxLevel + 1. Was the previous version wrong in that respect?

[ABataev]

Fixed after comments from Michael

[mkuper]

So, now, none of the costs on the tests actually change?
Does that mean that the changes in costs in the previous versions came from the +1?

Can you add a test that demonstrates the cost change? (Preferably in a way that shows what happened - e.g. commit a test with the "bad" cost, and then have a diff with the good one).

[ABataev]

Fixed some issues in previous implementation. More correct cost calculation

[ABataev]

In D26277#598814, @mkuper wrote:

So, now, none of the costs on the tests actually change?
Does that mean that the changes in costs in the previous versions came from the +1?

Can you add a test that demonstrates the cost change? (Preferably in a way that shows what happened - e.g. commit a test with the "bad" cost, and then have a diff with the good one).

Changed a code a little bit. Checked it, the calculated cost is very close to the real situation, but seems to me the BoUpSLP tree cost is too optimistic. Will look at it later.

[mkuper]

In D26277#599995, @ABataev wrote:

In D26277#598814, @mkuper wrote:

So, now, none of the costs on the tests actually change?
Does that mean that the changes in costs in the previous versions came from the +1?

Can you add a test that demonstrates the cost change? (Preferably in a way that shows what happened - e.g. commit a test with the "bad" cost, and then have a diff with the good one).

Changed a code a little bit. Checked it, the calculated cost is very close to the real situation, but seems to me the BoUpSLP tree cost is too optimistic. Will look at it later.

I'm sorry, but I'm still confused.
The original rationale for this patch was that the vector cost model is too optimistic, but the only test change seems to show the cost model becoming even more optimistic.

[ABataev]

Michael, added several test cases in r287801. Checked the test after my changes - no changes is found, the result is still the same as before this patch with fixes

[ABataev]

Updated to the latest version

[mkuper]

The point I'm trying to make is that there's still no adequate test coverage for this patch.

Could you please split this into two patches:

1. A patch that contains line 4286, and a test where the behavior actually changes due to that line.

2. A patch that contains getReductionCost() and a test where the behavior changes due to those changes. I assume (a) the change in reduction.ll you have in this patch is due to this part, and (b) 11 is a better cost here than 17, but it seems like <8 x i32> should be legal on AVX2, and illegal on SSE/AVX, so I wonder why we get the same cost for both case.

Would a smaller fix achieve the same result? If so, can you add a test that demonstrates where the logic you've added for illegal types matters.

[ABataev]

In D26277#604897, @mkuper wrote:

The point I'm trying to make is that there's still no adequate test coverage for this patch.

Could you please split this into two patches:

1. A patch that contains line 4286, and a test where the behavior actually changes due to that line.

2. A patch that contains getReductionCost() and a test where the behavior changes due to those changes. I assume (a) the change in reduction.ll you have in this patch is due to this part, and (b) 11 is a better cost here than 17, but it seems like <8 x i32> should be legal on AVX2, and illegal on SSE/AVX, so I wonder why we get the same cost for both case.

Would a smaller fix achieve the same result? If so, can you add a test that demonstrates where the logic you've added for illegal types matters.

1. Michael, I don't think this is a good idea. Actually, all these changes are required for cost model fix. I removed all optimizations from the patch, now it is a pure bug fix.
2. Yes, the patch may reduce the cost of vector operations, but also it reduces the cost of scalar operations because of use of ScalarTy instead of VectorTy.

Currently, this kind of reduction is also allowed. The vector cost of this operation is 17, but the scalar cost is 16 (because of using of VectorTy). With this patch, the vector cost is 11, but the scalar cost will be 7, so the difference even better than in the original code.

[mkuper]

Ok, now I see, in this case it doesn't make sense to separate the two.
(Sorry for the response time, I was on vacation)

LGTM, except that I would still like to see a test for the scalar cost as part of the final patch you commit. Having the test to begin with (showing 17 -> 11 and 16 -> 7 together) would have saved us some miscommunication.

include/llvm/CodeGen/BasicTTIImpl.h

unsigned getNumberOfParts(Type *Tp) {
     std::pair<unsigned, MVT> LT = getTLI()->getTypeLegalizationCost(DL, Tp);
     return LT.first;
   }
 
   unsigned getAddressComputationCost(Type *Ty, bool IsComplex) { return 0; }
 
   unsigned getReductionCost(unsigned Opcode, Type *Ty, bool IsPairwise) {
     assert(Ty->isVectorTy() && "Expect a vector type");
+    Type *ScalarTy = Ty->getVectorElementType();
     unsigned NumVecElts = Ty->getVectorNumElements();
     unsigned NumReduxLevels = Log2_32(NumVecElts);
-    unsigned ArithCost =
-        NumReduxLevels *
-        static_cast<T *>(this)->getArithmeticInstrCost(Opcode, Ty);
+    // Try to calculate arithmetic and shuffle op costs for reduction operations.
+    // We're assuming that reduction operation are performing the following way:
+    // 1. Non-pairwise reduction
+    // %val1 = shufflevector<n x t> %val, <n x t> %undef,
+    // <n x i32> <i32 n/2, i32 n/2 + 1, ..., i32 n, i32 undef, ..., i32 undef>
+    //            \----------------v-------------/  \----------v------------/
+    //                            n/2 elements               n/2 elements
+    // %red1 = op <n x t> %val, <n x t> val1
+    // After this operation we have a vector %red1 with only maningfull the
+    // first n/2 elements, the second n/2 elements are undefined and can be
+    // dropped. All other operations are actually working with the vector of
+    // length n/2, not n. though the real vector length is still n.
+    // %val2 = shufflevector<n x t> %red1, <n x t> %undef,
+    // <n x i32> <i32 n/4, i32 n/4 + 1, ..., i32 n/2, i32 undef, ..., i32 undef>
+    //            \----------------v-------------/  \----------v------------/
+    //                            n/4 elements               3*n/4 elements
+    // %red2 = op <n x t> %red1, <n x t> val2  - working with the vector of
+    // length n/2, the resulting vector has length n/4 etc.
+    // 2. Pairwise reduction:
+    // Everything is the same except for an additional shuffle operation which
+    // is used to produce operands for pairwise kind of reductions.
+    // %val1 = shufflevector<n x t> %val, <n x t> %undef,
+    // <n x i32> <i32 0, i32 2, ..., i32 n-2, i32 undef, ..., i32 undef>
+    //            \-------------v----------/  \----------v------------/
+    //                   n/2 elements               n/2 elements
+    // %val2 = shufflevector<n x t> %val, <n x t> %undef,
+    // <n x i32> <i32 1, i32 3, ..., i32 n-1, i32 undef, ..., i32 undef>
+    //            \-------------v----------/  \----------v------------/
+    //                   n/2 elements               n/2 elements
+    // %red1 = op <n x t> %val1, <n x t> val2
+    // Again, the operation is performed on <n x t> vector, but the resulting
+    // vector %red1 is <n/2 x t> vector.
+    //
+    // The cost model should take into account that the actual length of the
+    // vector is reduced on each iteration.
+    unsigned ArithCost = 0;
+    unsigned ShuffleCost = 0;
+    auto *ConcreteTTI = static_cast<T *>(this);
+    std::pair<unsigned, MVT> LT =
+        ConcreteTTI->getTLI()->getTypeLegalizationCost(DL, Ty);
+    unsigned LongVectorCount = 0;
+    unsigned MVTLen =
+        LT.second.isVector() ? LT.second.getVectorNumElements() : 1;
+    while (NumVecElts > MVTLen) {
+      NumVecElts /= 2;
       // Assume the pairwise shuffles add a cost.
-    unsigned ShuffleCost =
-        NumReduxLevels * (IsPairwise + 1) *
-        static_cast<T *>(this)
-            ->getShuffleCost(TTI::SK_ExtractSubvector, Ty, NumVecElts / 2, Ty);
+      ShuffleCost += (IsPairwise + 1) *
+                     ConcreteTTI->getShuffleCost(TTI::SK_ExtractSubvector, Ty,
+                                                 NumVecElts, Ty);
+      ArithCost += ConcreteTTI->getArithmeticInstrCost(Opcode, Ty);
+      Ty = VectorType::get(ScalarTy, NumVecElts);
+      ++LongVectorCount;
+    }
+    // The minimal length of the vector is limited by the real length of vector
+    // operations performed on the current platform. That's why several final
+    // reduction opertions are perfomed on the vectors with the same
+    // architecture-dependent length.
+    ShuffleCost += (NumReduxLevels - LongVectorCount) * (IsPairwise + 1) *
+                   ConcreteTTI->getShuffleCost(TTI::SK_ExtractSubvector, Ty,
+                                               NumVecElts, Ty);
+    ArithCost += (NumReduxLevels - LongVectorCount) *
+                 ConcreteTTI->getArithmeticInstrCost(Opcode, Ty);
     return ShuffleCost + ArithCost + getScalarizationOverhead(Ty, false, true);
   }
 
   unsigned getVectorSplitCost() { return 1; }
 
   /// @}
 };
 

lib/Transforms/Vectorize/SLPVectorizer.cpp

int getReductionCost(TargetTransformInfo *TTI, Value *FirstReducedVal) {
 
     int PairwiseRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, true);
     int SplittingRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, false);
 
     IsPairwiseReduction = PairwiseRdxCost < SplittingRdxCost;
     int VecReduxCost = IsPairwiseReduction ? PairwiseRdxCost : SplittingRdxCost;
 
     int ScalarReduxCost =
-        ReduxWidth * TTI->getArithmeticInstrCost(ReductionOpcode, VecTy);
+        (ReduxWidth - 1) *
+        TTI->getArithmeticInstrCost(ReductionOpcode, ScalarTy);
 
     DEBUG(dbgs() << "SLP: Adding cost " << VecReduxCost - ScalarReduxCost
                  << " for reduction that starts with " << *FirstReducedVal
                  << " (It is a "
                  << (IsPairwiseReduction ? "pairwise" : "splitting")
                  << " reduction)\n");
 
     return VecReduxCost - ScalarReduxCost;

test/Analysis/CostModel/X86/reduction.ll

<8 x i32> <i32 2    , i32 3,     i32 undef, i32 undef,
               i32 undef, i32 undef, i32 undef, i32 undef>
   %bin.rdx.2 = add <8 x i32> %bin.rdx, %rdx.shuf.2
   %rdx.shuf.3 = shufflevector <8 x i32> %bin.rdx.2, <8 x i32> undef,
    <8 x i32> <i32 1    , i32 undef, i32 undef, i32 undef,
               i32 undef, i32 undef, i32 undef, i32 undef>
   %bin.rdx.3 = add <8 x i32> %bin.rdx.2, %rdx.shuf.3
 
 ; CHECK-LABEL: reduction_cost_int
-; CHECK:  cost of 17 {{.*}} extractelement
+; CHECK:  cost of 11 {{.*}} extractelement
 
   %r = extractelement <8 x i32> %bin.rdx.3, i32 0
   ret i32 %r
 }
 
 define fastcc float @pairwise_hadd(<4 x float> %rdx, float %f1) {
   %rdx.shuf.0.0 = shufflevector <4 x float> %rdx, <4 x float> undef,
         <4 x i32> <i32 0, i32 2 , i32 undef, i32 undef>