[X86] Failure to use PHADDD on Intel CPUs on the second to last step of a v8i32 pairwise reduction

[topperc]

Bugzilla Link	39920
Resolution	FIXED
Resolved on	May 09, 2019 11:14
Version	trunk
OS	Windows NT
Blocks	#35132
CC	@adibiagio,@topperc,@RKSimon,@rotateright
Fixed by commit(s)	r360360

Extended Description

I think we should use HADDPS for the first reduction step of this on Intel CPUs

define fastcc i32 @​pairwise_reduction4i32(<4 x i32> %rdx, i32 %f1) {
%rdx.shuf.1.0 = shufflevector <4 x i32> %rdx, <4 x i32> undef,<4 x i32> <i32 0, i32 2, i32 undef, i32 undef>
%rdx.shuf.1.1 = shufflevector <4 x i32> %rdx, <4 x i32> undef,<4 x i32> <i32 1, i32 3, i32 undef, i32 undef>
%bin.rdx8 = add <4 x i32> %rdx.shuf.1.0, %rdx.shuf.1.1
%rdx.shuf.2.0 = shufflevector <4 x i32> %bin.rdx8, <4 x i32> undef,<4 x i32> <i32 0, i32 undef, i32 undef, i32 undef>
%rdx.shuf.2.1 = shufflevector <4 x i32> %bin.rdx8, <4 x i32> undef,<4 x i32> <i32 1, i32 undef, i32 undef, i32 undef>
%bin.rdx9 = add <4 x i32> %rdx.shuf.2.0, %rdx.shuf.2.1

%r = extractelement <4 x i32> %bin.rdx9, i32 0
ret i32 %r
}

This is the assembly we get on sse4.1

    pshufd  $232, %xmm0, %xmm1      # xmm1 = xmm0[0,2,2,3]
    pshufd  $237, %xmm0, %xmm0      # xmm0 = xmm0[1,3,2,3]
    paddd   %xmm1, %xmm0
    pshufd  $229, %xmm0, %xmm1      # xmm1 = xmm0[1,1,2,3]
    paddd   %xmm0, %xmm1
    movd    %xmm1, %eax
    retq

PHADDD uses 2 shuffles internally on Intel CPus, but as you can see the assembly we emitted also uses 2 shuffles. So I don't think we saved anything by avoiding PHADDD.

[adibiagio]

It is a win to use HADDPS/PHADDD for the first reduction step even on AMD Jaguar too.

(BtVer2, not using horizontal adds)

    85,119,758  cycles:u                                   ( +-  0.02% )  (75.52%)
   169,314,759  instructions:u    #  1.99  insn per cycle  ( +-  0.10% )  (76.22%)

(BtVer2, with horizontal adds)

    50,645,155  cycles:u                                   ( +-  0.02% )  (75.40%)
   102,534,112  instructions:u    #  2.02  insn per cycle  ( +-  0.33% )  (74.08%)

On other AMD CPUs, using PHADDD/HADDPS for that first reduction step may not be cheaper (or equally fast).

Out of curiosty, I had a look at the "instruction latency" xsl spreadsheet released by AMD for their amdfam17h; it looks like the latency of horizontal adds is "acceptable" for PHADDD, but not for HADDPS.
It is likely to be expanded into 2 shuffle uops internally. However, the recriprocal throughput suggests that it may not be a win to use PHADDD over normal shuffles... I suspect that it is only convenient for Jaguar to always do that step using horizontal operations; PHADDD might be a (not too bad) compromise for modern AMD CPUs. However, HADDPS should be always avoided.

It would be interesting to get some perf numbers for Bulldozer/Piledriver. I suspect that Jaguar is kind of a "special case" for AMD though..

On a slightly different topic: if PHADDD is a relatively good compromise for most AMD processors, then we should consider using it always for when optimising for size. Just an idea..

[RKSimon]

This is what we have the FeatureFastHorizontalOps tag for (currently just set for btver2).

But really this seems like an obvious use case for a scheduler driven combine pass that happens later on (around post-ra) - we'd always just combine to PHADD/HADDP* in the DAG and then the pass re-expands if the scheduler indicates better performance.

[RKSimon]

This is the assembly we get on sse4.1

    pshufd  $232, %xmm0, %xmm1      # xmm1 = xmm0[0,2,2,3]
    pshufd  $237, %xmm0, %xmm0      # xmm0 = xmm0[1,3,2,3]
    paddd   %xmm1, %xmm0
    pshufd  $229, %xmm0, %xmm1      # xmm1 = xmm0[1,1,2,3]
    paddd   %xmm0, %xmm1
    movd    %xmm1, %eax
    retq

PHADDD uses 2 shuffles internally on Intel CPus, but as you can see the
assembly we emitted also uses 2 shuffles. So I don't think we saved anything
by avoiding PHADDD.

https://reviews.llvm.org/D61308 should fold this to:

phaddd %xmm0, %xmm0
pshufd $229, %xmm0, %xmm1 # xmm1 = xmm0[1,1,2,3]
paddd %xmm0, %xmm1
movd %xmm1, %eax
retq

[RKSimon]

Fixed in rL360360