[x86, SSE] only use phaddw / phaddd when optimizing for minsize?

[rotateright]

Bugzilla Link	26859
Resolution	FIXED
Resolved on	Oct 12, 2018 09:56
Version	trunk
OS	All
Depends On	#32148
Blocks	#29972
CC	@adibiagio,@RKSimon

Extended Description

Packed horizontal add - phaddd / phaddw:
These are SSSE3 (yes, 3 Ss) instructions that should probably never be generated for performance reasons, only to save on code size. They're just about guaranteed to be slow because they operate across vector lanes.

Here we're not only generating these things, but for a target that doesn't have SSSE3:

$ cat accum.c
int please_no_phaddd(int *x) {
int sum = 0;
for (int i=0; i<1024; ++i)
sum += x[i];
return sum;
}

short please_no_phaddw(short *x) {
short sum = 0;
for (int i=0; i<1024; ++i)
sum += x[i];
return sum;
}
bin $ ./clang -O2 -S -o - accum.c -msse -fno-unroll-loops|grep phadd
.globl _please_no_phaddd
_please_no_phaddd: ## @​please_no_phaddd
phaddd %xmm1, %xmm1
.globl _please_no_phaddw
_please_no_phaddw: ## @​please_no_phaddw
phaddw %xmm0, %xmm0

[rotateright]

The part about the target not having SSSE3 was wrong, so this is just a potential perf bug.

The default Darwin target has SSSE3, and specifying "-msse" is not to override that. You have to use a "no" option like "-mno-ssse3".

[rotateright]

I haven't done any perf tests, but a skim of Agner's tables says that AMD Bobcat and Jaguar managed to implement these as simple 1-cycle ops.

Everything else looks like it would be slower for a reduction case like this compared to the shift/shuffle + regular add alternative.

If this is correct, we'd have to do some subtarget-specific optimization. This would be another example of a machine-level combine.

[llvmbot]

Core2 IR, for completeness

[llvmbot]

Wrong bug, sorry! Please delete the attachment, if possible.

[rotateright]

No worries - not sure if it's possible to delete, but I've made the attachment obsolete.

[llvmbot]

Regardless of profitability (and I'm not sure whether it really is profitable or not), there's another wrinkle here, and it's that the AVX codegen clearly does the wrong thing.

Consider this code:
define i32 @​horizontal(<8 x i8>* %p) {
%v = load <8 x i8>, <8 x i8>* %p
%z = zext <8 x i8> %v to <8 x i32>
%sh1 = shufflevector <8 x i32> %z, <8 x i32> undef, <8 x i32> <i32 4, i32 5, i32 6, i32 7, i32 undef, i32 undef, i32 undef, i32 undef>
%add1 = add <8 x i32> %z, %sh1
%sh2 = shufflevector <8 x i32> %add1, <8 x i32> undef, <8 x i32> <i32 2, i32 3, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
%add2 = add <8 x i32> %add1, %sh2
%sh3 = shufflevector <8 x i32> %add2, <8 x i32> undef, <8 x i32> <i32 1, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
%add3 = add <8 x i32> %add2, %sh3
%res = extractelement <8 x i32> %add3, i32 0
ret i32 %res
}

For SSE4.2, we get:
pmovzxbd 4(%rdi), %xmm0
pmovzxbd (%rdi), %xmm1
paddd %xmm0, %xmm1
pshufd $78, %xmm1, %xmm0
paddd %xmm1, %xmm0
phaddd %xmm0, %xmm0
movd %xmm0, %eax
retq

AVX could do the same, but it fails to match the hadd after legalization, and we get:
vpmovzxbd 4(%rdi), %xmm0
vpmovzxbd (%rdi), %xmm1
vpaddd %xmm0, %xmm1, %xmm0
vpshufd $78, %xmm0, %xmm1
vpaddd %xmm1, %xmm0, %xmm0
vpshufd $229, %xmm0, %xmm1
vpaddd %xmm1, %xmm0, %xmm0
vmovd %xmm0, %eax
retq

And finally, AVX2 manages to match an hadd, but with the wrong width (!):
vpmovzxbd (%rdi), %ymm0
vextracti128 $1, %ymm0, %xmm1
vpaddd %ymm1, %ymm0, %ymm0
vpshufd $78, %xmm0, %xmm1 # xmm1 = xmm0[2,3,0,1]
vpaddd %ymm1, %ymm0, %ymm0
vphaddd %ymm0, %ymm0, %ymm0
vmovd %xmm0, %eax
vzeroupper
retq

[llvmbot]

Err, ignore the last comment about AVX2.

[RKSimon]

We're noticing this with haddps/haddpd as well as the integer horizontal ops.

[llvmbot]

Now we have a possibility to compare lattency/throughput for different alternatives of generated code. I used the following source for testing:

__v4si test_haddd(__v4si a, __v4si b) {
return
__builtin_shufflevector(a, b, 0, 2, 4, 6) +
__builtin_shufflevector(a, b, 1, 3, 5, 7);
}

__v8hi test_haddw(__v8hi a, __v8hi b) {
return
__builtin_shufflevector(a, b, 0, 2, 4, 6, 8, 10, 12, 14) +
__builtin_shufflevector(a, b, 1, 3, 5, 7, 9, 11, 13, 15);
}

I generated the corresponding llvm code:

; Function Attrs: norecurse nounwind readnone uwtable
define <4 x i32> @​test_haddd(<4 x i32> %a, <4 x i32> %b) local_unnamed_addr #​0 {
entry:
%shuffle = shufflevector <4 x i32> %a, <4 x i32> %b, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
%shuffle1 = shufflevector <4 x i32> %a, <4 x i32> %b, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
%add = add <4 x i32> %shuffle, %shuffle1
ret <4 x i32> %add
}

; Function Attrs: norecurse nounwind readnone uwtable
define <8 x i16> @​test_haddw(<8 x i16> %a, <8 x i16> %b) local_unnamed_addr #​0 {
entry:
%shuffle = shufflevector <8 x i16> %a, <8 x i16> %b, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
%shuffle1 = shufflevector <8 x i16> %a, <8 x i16> %b, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
%add = add <8 x i16> %shuffle, %shuffle1
ret <8 x i16> %add
}

and used the following commands to test:

2049 ./llc <test_hadd.ll -print-schedule -mcpu=btver2 -mattr=-ssse3
2050 ./llc <test_hadd.ll -print-schedule -mcpu=btver2 -mattr=+ssse3
2051 ./llc <test_hadd.ll -print-schedule -mcpu=haswell -mattr=+ssse3
2052 ./llc <test_hadd.ll -print-schedule -mcpu=haswell -mattr=-ssse3
2053 ./llc <test_hadd.ll -print-schedule -mcpu=btver2 -mattr=+ssse3
2054 ./llc <test_hadd.ll -print-schedule -mcpu=btver2 -mattr=-ssse3
2055 ./llc <test_hadd.ll -print-schedule -mcpu=haswell -mattr=-ssse3
2056 ./llc <test_hadd.ll -print-schedule -mcpu=haswell -mattr=+ssse3
2057 ./llc <test_hadd.ll -print-schedule -mcpu=sandybridge -mattr=+ssse3
2058 ./llc <test_hadd.ll -print-schedule -mcpu=sandybridge -mattr=-ssse3
2059 ./llc <test_hadd.ll -print-schedule -mcpu=slm -mattr=-ssse3
2060 ./llc <test_hadd.ll -print-schedule -mcpu=slm -mattr=+ssse3

For all CPUs I got the same result: the horizontal ops are better than the shuffle ones. For example:

without horizontal ops (./llc <test_hadd.ll -print-schedule -mcpu=btver2 -mattr=-ssse3)

test_haddd: # @​test_haddd
.cfi_startproc

BB#0: # %entry

    movaps  %xmm0, %xmm2            #  sched: [1:0.50]
    shufps  $221, %xmm1, %xmm0      # xmm0 = xmm0[1,3],xmm1[1,3] sched: [1:0.50]
    shufps  $136, %xmm1, %xmm2      # xmm2 = xmm2[0,2],xmm1[0,2] sched: [1:0.50]
    paddd   %xmm2, %xmm0            #  sched: [1:0.50]
    retq                            #  sched: [4:1.00]

with horizontal ops (./llc <test_hadd.ll -print-schedule -mcpu=btver2 -mattr=+ssse3)

test_haddd: # @​test_haddd
.cfi_startproc

BB#0: # %entry

    vphaddd %xmm1, %xmm0, %xmm0     #  sched: [1:0.50]
    retq                            #  sched: [4:1.00]

(for shorts the difference is more)
Do you still think we should avoid horizontal ops in generation?

[rotateright]

Let's look at Nehalem as an example because when I wrote this bug, I was probably thinking of that as the default CPU.

$ ./llc -o - hadd.ll -print-schedule -mcpu=nehalem -mattr=ssse3
phaddd %xmm1, %xmm0 ## sched: [1:0.50]
retq ## sched: [5:1.00]

$ ./llc -o - hadd.ll -print-schedule -mcpu=nehalem -mattr=-ssse3
movaps %xmm0, %xmm2 ## sched: [1:1.00]
shufps $136, %xmm1, %xmm2 ## xmm2 = xmm2[0,2],xmm1[0,2] sched: [1:1.00]
shufps $221, %xmm1, %xmm0 ## xmm0 = xmm0[1,3],xmm1[1,3] sched: [1:1.00]
paddd %xmm2, %xmm0 ## sched: [1:0.50]

---

The timing for 'phaddd' according to Agner's tables is latency = 3 with recip throughput = 1.5. So "[1:0.50]" is a bug in the LLVM sched table for Nehalem?

Assuming Agner's numbers are correct, then phaddd would take equivalent resources as 2 shuffles and 1 regular paddd, so it makes sense to choose phaddd here since it's smaller code?

But this isn't the same as the example in the problem description, right? In the summation reduction case, we only have one extra shuffle when we don't use phaddd. In that case, the phaddd actually costs more than pshufd+paddd.

If newer chips have all made phaddd cheaper than 1 shuf + 1 paddd, then maybe this doesn't matter any more?

[RKSimon]

I think the only recent architecture that prefers avoiding HADD/HSUB is Silvermont.

[llvmbot]

I fixed lattency/tp numbers for Jaguar only. I think we should create a new record to check all other CPUs. When it's done we'll see the proper numbers.

[RKSimon]

https://reviews.llvm.org/D53095

[rotateright]

https://reviews.llvm.org/D53095

Committed here:
https://reviews.llvm.org/rL344361

There's a stunning amount of vector duplication + unrolling in these tests currently:
$ clang -O2 accum.c -S -o - -mavx | grep padd | wc -l
155

...but that's not this bug.

This is the current behavior:

$ clang -Os accum.c -S -o - -mavx | grep phadd | grep mm
vphaddd %xmm0, %xmm0, %xmm0
vphaddw %xmm0, %xmm0, %xmm0
$ clang -O2 accum.c -S -o - -mavx | grep phadd | grep mm
$ clang -O2 accum.c -S -o - -mavx -march=btver2 | grep phadd | grep mm
vphaddd %xmm0, %xmm0, %xmm0
vphaddw %xmm0, %xmm0, %xmm0

Ie, if we are optimizing for size or Jaguar, we'll use horizontal ops, otherwise, we use regular ops and shuffles.

It's possible that our combiner predicate will need adjustments to optimize that decision depending on code pattern and uarch, but we now have that ability. Ideally, we can refine the choice using CPU instruction latency/throughput models rather than with the DAG heuristic in the patch, but that's also another bug.

[ZviRackover]

mentioned in issue #29972