Index: include/llvm/CodeGen/BasicTTIImpl.h =================================================================== --- include/llvm/CodeGen/BasicTTIImpl.h +++ include/llvm/CodeGen/BasicTTIImpl.h @@ -927,16 +927,70 @@ 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(this)->getArithmeticInstrCost(Opcode, Ty); - // Assume the pairwise shuffles add a cost. - unsigned ShuffleCost = - NumReduxLevels * (IsPairwise + 1) * - static_cast(this) - ->getShuffleCost(TTI::SK_ExtractSubvector, Ty, NumVecElts / 2, 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 %val, %undef, + // + // \----------------v-------------/ \----------v------------/ + // n/2 elements n/2 elements + // %red1 = op %val, 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 %red1, %undef, + // + // \----------------v-------------/ \----------v------------/ + // n/4 elements 3*n/4 elements + // %red2 = op %red1, 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 %val, %undef, + // + // \-------------v----------/ \----------v------------/ + // n/2 elements n/2 elements + // %val2 = shufflevector %val, %undef, + // + // \-------------v----------/ \----------v------------/ + // n/2 elements n/2 elements + // %red1 = op %val1, val2 + // Again, the operation is performed on vector, but the resulting + // vector %red1 is 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(this); + std::pair LT = + ConcreteTTI->getTLI()->getTypeLegalizationCost(DL, Ty); + unsigned LongVectorCount = 0; + while (LT.first > 4) { + NumVecElts /= 2; + // Assume the pairwise shuffles add a cost. + ShuffleCost += (IsPairwise + 1) * + ConcreteTTI->getShuffleCost(TTI::SK_ExtractSubvector, Ty, + NumVecElts, Ty); + ArithCost += ConcreteTTI->getArithmeticInstrCost(Opcode, Ty); + Ty = VectorType::get(ScalarTy, NumVecElts); + LT.first /= 2; + ++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); } Index: lib/Transforms/Vectorize/SLPVectorizer.cpp =================================================================== --- lib/Transforms/Vectorize/SLPVectorizer.cpp +++ lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -4283,7 +4283,7 @@ int VecReduxCost = IsPairwiseReduction ? PairwiseRdxCost : SplittingRdxCost; int ScalarReduxCost = - ReduxWidth * TTI->getArithmeticInstrCost(ReductionOpcode, VecTy); + ReduxWidth * TTI->getArithmeticInstrCost(ReductionOpcode, ScalarTy); DEBUG(dbgs() << "SLP: Adding cost " << VecReduxCost - ScalarReduxCost << " for reduction that starts with " << *FirstReducedVal Index: test/Transforms/SLPVectorizer/AArch64/gather-root.ll =================================================================== --- test/Transforms/SLPVectorizer/AArch64/gather-root.ll +++ test/Transforms/SLPVectorizer/AArch64/gather-root.ll @@ -1,5 +1,6 @@ -; RUN: opt < %s -slp-vectorizer -S | FileCheck %s --check-prefix=DEFAULT -; RUN: opt < %s -slp-schedule-budget=0 -slp-min-tree-size=0 -slp-threshold=-30 -slp-vectorizer -S | FileCheck %s --check-prefix=GATHER +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -slp-vectorizer -slp-threshold=-6 -S | FileCheck %s --check-prefix=DEFAULT +; RUN: opt < %s -slp-schedule-budget=0 -slp-min-tree-size=0 -slp-threshold=-38 -slp-vectorizer -S | FileCheck %s --check-prefix=GATHER ; RUN: opt < %s -slp-schedule-budget=0 -slp-threshold=-30 -slp-vectorizer -S | FileCheck %s --check-prefix=MAX-COST target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128" @@ -8,43 +9,56 @@ @a = common global [80 x i8] zeroinitializer, align 16 ; DEFAULT-LABEL: @PR28330( -; DEFAULT: %tmp17 = phi i32 [ %tmp34, %for.body ], [ 0, %entry ] -; DEFAULT: %[[S0:.+]] = select <8 x i1> %1, <8 x i32> , <8 x i32> -; DEFAULT: %[[R0:.+]] = shufflevector <8 x i32> %[[S0]], <8 x i32> undef, <8 x i32> -; DEFAULT: %[[R1:.+]] = add <8 x i32> %[[S0]], %[[R0]] -; DEFAULT: %[[R2:.+]] = shufflevector <8 x i32> %[[R1]], <8 x i32> undef, <8 x i32> -; DEFAULT: %[[R3:.+]] = add <8 x i32> %[[R1]], %[[R2]] -; DEFAULT: %[[R4:.+]] = shufflevector <8 x i32> %[[R3]], <8 x i32> undef, <8 x i32> -; DEFAULT: %[[R5:.+]] = add <8 x i32> %[[R3]], %[[R4]] -; DEFAULT: %[[R6:.+]] = extractelement <8 x i32> %[[R5]], i32 0 -; DEFAULT: %tmp34 = add i32 %[[R6]], %tmp17 -; -; GATHER-LABEL: @PR28330( -; GATHER: %tmp17 = phi i32 [ %tmp34, %for.body ], [ 0, %entry ] -; GATHER: %tmp19 = select i1 %tmp1, i32 -720, i32 -80 -; GATHER: %tmp21 = select i1 %tmp3, i32 -720, i32 -80 -; GATHER: %tmp23 = select i1 %tmp5, i32 -720, i32 -80 -; GATHER: %tmp25 = select i1 %tmp7, i32 -720, i32 -80 -; GATHER: %tmp27 = select i1 %tmp9, i32 -720, i32 -80 -; GATHER: %tmp29 = select i1 %tmp11, i32 -720, i32 -80 -; GATHER: %tmp31 = select i1 %tmp13, i32 -720, i32 -80 -; GATHER: %tmp33 = select i1 %tmp15, i32 -720, i32 -80 -; GATHER: %[[I0:.+]] = insertelement <8 x i32> undef, i32 %tmp19, i32 0 -; GATHER: %[[I1:.+]] = insertelement <8 x i32> %[[I0]], i32 %tmp21, i32 1 -; GATHER: %[[I2:.+]] = insertelement <8 x i32> %[[I1]], i32 %tmp23, i32 2 -; GATHER: %[[I3:.+]] = insertelement <8 x i32> %[[I2]], i32 %tmp25, i32 3 -; GATHER: %[[I4:.+]] = insertelement <8 x i32> %[[I3]], i32 %tmp27, i32 4 -; GATHER: %[[I5:.+]] = insertelement <8 x i32> %[[I4]], i32 %tmp29, i32 5 -; GATHER: %[[I6:.+]] = insertelement <8 x i32> %[[I5]], i32 %tmp31, i32 6 -; GATHER: %[[I7:.+]] = insertelement <8 x i32> %[[I6]], i32 %tmp33, i32 7 -; GATHER: %[[R0:.+]] = shufflevector <8 x i32> %[[I7]], <8 x i32> undef, <8 x i32> -; GATHER: %[[R1:.+]] = add <8 x i32> %[[I7]], %[[R0]] -; GATHER: %[[R2:.+]] = shufflevector <8 x i32> %[[R1]], <8 x i32> undef, <8 x i32> -; GATHER: %[[R3:.+]] = add <8 x i32> %[[R1]], %[[R2]] -; GATHER: %[[R4:.+]] = shufflevector <8 x i32> %[[R3]], <8 x i32> undef, <8 x i32> -; GATHER: %[[R5:.+]] = add <8 x i32> %[[R3]], %[[R4]] -; GATHER: %[[R6:.+]] = extractelement <8 x i32> %[[R5]], i32 0 -; GATHER: %tmp34 = add i32 %[[R6]], %tmp17 +; GATHER: [[TMP1:%.*]] = icmp eq <8 x i8> %{{.*}}, zeroinitializer +; GATHER: [[TMPHI:%.*]] = phi i32 [ [[TMP34ADD:%.*]], %for.body ], [ 0, %entry ] +; GATHER-NEXT: [[TMP2:%.*]] = extractelement <8 x i1> [[TMP1]], i32 0 +; GATHER-NEXT: [[TMP3:%.*]] = insertelement <8 x i1> undef, i1 [[TMP2]], i32 0 +; GATHER-NEXT: [[TMP4:%.*]] = extractelement <8 x i1> [[TMP1]], i32 1 +; GATHER-NEXT: [[TMP5:%.*]] = insertelement <8 x i1> [[TMP3]], i1 [[TMP4]], i32 1 +; GATHER-NEXT: [[TMP6:%.*]] = extractelement <8 x i1> [[TMP1]], i32 2 +; GATHER-NEXT: [[TMP7:%.*]] = insertelement <8 x i1> [[TMP5]], i1 [[TMP6]], i32 2 +; GATHER-NEXT: [[TMP8:%.*]] = extractelement <8 x i1> [[TMP1]], i32 3 +; GATHER-NEXT: [[TMP9:%.*]] = insertelement <8 x i1> [[TMP7]], i1 [[TMP8]], i32 3 +; GATHER-NEXT: [[TMP10:%.*]] = extractelement <8 x i1> [[TMP1]], i32 4 +; GATHER-NEXT: [[TMP11:%.*]] = insertelement <8 x i1> [[TMP9]], i1 [[TMP10]], i32 4 +; GATHER-NEXT: [[TMP12:%.*]] = extractelement <8 x i1> [[TMP1]], i32 5 +; GATHER-NEXT: [[TMP13:%.*]] = insertelement <8 x i1> [[TMP11]], i1 [[TMP12]], i32 5 +; GATHER-NEXT: [[TMP14:%.*]] = extractelement <8 x i1> [[TMP1]], i32 6 +; GATHER-NEXT: [[TMP15:%.*]] = insertelement <8 x i1> [[TMP13]], i1 [[TMP14]], i32 6 +; GATHER-NEXT: [[TMP16:%.*]] = extractelement <8 x i1> [[TMP1]], i32 7 +; GATHER-NEXT: [[TMP17:%.*]] = insertelement <8 x i1> [[TMP15]], i1 [[TMP16]], i32 7 +; GATHER-NEXT: [[TMP18:%.*]] = select <8 x i1> [[TMP17]], <8 x i32> , <8 x i32> +; GATHER-NEXT: [[TMP19:%.*]] = extractelement <8 x i32> [[TMP18]], i32 0 +; GATHER-NEXT: [[TMP20ADD:%.*]] = add i32 [[TMPHI]], [[TMP19]] +; GATHER-NEXT: [[TMP20:%.*]] = extractelement <8 x i32> [[TMP18]], i32 1 +; GATHER-NEXT: [[TMP22:%.*]] = add i32 [[TMP20ADD]], [[TMP20]] +; GATHER-NEXT: [[TMP21:%.*]] = extractelement <8 x i32> [[TMP18]], i32 2 +; GATHER-NEXT: [[TMP24:%.*]] = add i32 [[TMP22]], [[TMP21]] +; GATHER-NEXT: [[TMP22:%.*]] = extractelement <8 x i32> [[TMP18]], i32 3 +; GATHER-NEXT: [[TMP26:%.*]] = add i32 [[TMP24]], [[TMP22]] +; GATHER-NEXT: [[TMP23:%.*]] = extractelement <8 x i32> [[TMP18]], i32 4 +; GATHER-NEXT: [[TMP28:%.*]] = add i32 [[TMP26]], [[TMP23]] +; GATHER-NEXT: [[TMP24:%.*]] = extractelement <8 x i32> [[TMP18]], i32 5 +; GATHER-NEXT: [[TMP30:%.*]] = add i32 [[TMP28]], [[TMP24]] +; GATHER-NEXT: [[TMP25:%.*]] = extractelement <8 x i32> [[TMP18]], i32 6 +; GATHER-NEXT: [[TMP32:%.*]] = add i32 [[TMP30]], [[TMP25]] +; GATHER-NEXT: [[TMP26:%.*]] = insertelement <8 x i32> undef, i32 [[TMP19]], i32 0 +; GATHER-NEXT: [[TMP27:%.*]] = insertelement <8 x i32> [[TMP26]], i32 [[TMP20]], i32 1 +; GATHER-NEXT: [[TMP28:%.*]] = insertelement <8 x i32> [[TMP27]], i32 [[TMP21]], i32 2 +; GATHER-NEXT: [[TMP29:%.*]] = insertelement <8 x i32> [[TMP28]], i32 [[TMP22]], i32 3 +; GATHER-NEXT: [[TMP30:%.*]] = insertelement <8 x i32> [[TMP29]], i32 [[TMP23]], i32 4 +; GATHER-NEXT: [[TMP31:%.*]] = insertelement <8 x i32> [[TMP30]], i32 [[TMP24]], i32 5 +; GATHER-NEXT: [[TMP32:%.*]] = insertelement <8 x i32> [[TMP31]], i32 [[TMP25]], i32 6 +; GATHER-NEXT: [[TMP33:%.*]] = extractelement <8 x i32> [[TMP18]], i32 7 +; GATHER-NEXT: [[TMP34:%.*]] = insertelement <8 x i32> [[TMP32]], i32 [[TMP33]], i32 7 +; GATHER-NEXT: [[RDX_SHUF:%.*]] = shufflevector <8 x i32> [[TMP34]], <8 x i32> undef, <8 x i32> +; GATHER-NEXT: [[BIN_RDX:%.*]] = add <8 x i32> [[TMP34]], [[RDX_SHUF]] +; GATHER-NEXT: [[RDX_SHUF1:%.*]] = shufflevector <8 x i32> [[BIN_RDX]], <8 x i32> undef, <8 x i32> +; GATHER-NEXT: [[BIN_RDX2:%.*]] = add <8 x i32> [[BIN_RDX]], [[RDX_SHUF1]] +; GATHER-NEXT: [[RDX_SHUF3:%.*]] = shufflevector <8 x i32> [[BIN_RDX2]], <8 x i32> undef, <8 x i32> +; GATHER-NEXT: [[BIN_RDX4:%.*]] = add <8 x i32> [[BIN_RDX2]], [[RDX_SHUF3]] +; GATHER-NEXT: [[TMP35:%.*]] = extractelement <8 x i32> [[BIN_RDX4]], i32 0 +; GATHER-NEXT: [[TMP34ADD]] = add i32 [[TMP35]], [[TMPHI]] ; ; MAX-COST-LABEL: @PR28330( ; MAX-COST-NOT: shufflevector