[SLPVectorizer] Performance degradation with xor + fshl on X86

[annamthomas]

With SLP Vectorizer, a hot loop with 6 xors + 2 fshl get reduced to 3 xors + 1 fshl. We vectorize with a VF of 2.
The SLP cost model gives it a cost of -8.

This is the loop in question:

  %iv = phi i64 [ %add323, %vectorized_slp_bb ], [ 16, %bb2 ]
  %add288 = add nsw i64 %iv, -3
  %getelementptr289 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add288
  %load290 = load i32, ptr addrspace(1) %getelementptr289, align 4, !tbaa !28, !noundef !3
  %add291 = add nsw i64 %iv, -8
  %getelementptr292 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add291
  %load293 = load i32, ptr addrspace(1) %getelementptr292, align 4, !tbaa !28, !noundef !3
  %xor294 = xor i32 %load293, %load290
  %add295 = add nsw i64 %iv, -14 
  %getelementptr296 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add295
  %load297 = load i32, ptr addrspace(1) %getelementptr296, align 4, !tbaa !28, !noundef !3
  %xor298 = xor i32 %xor294, %load297
  %add299 = add nsw i64 %iv, -16 
  %getelementptr300 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add299
  %load301 = load i32, ptr addrspace(1) %getelementptr300, align 4, !tbaa !28, !noundef !3
  %xor302 = xor i32 %xor298, %load301
  %call303 = call i32 @llvm.fshl.i32(i32 %xor302, i32 %xor302, i32 1) #5
  %getelementptr304 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %iv 
  store i32 %call303, ptr addrspace(1) %getelementptr304, align 4, !tbaa !28 
  %add305 = add nuw nsw i64 %iv, 1
  %add306 = add nsw i64 %iv, -2
  %getelementptr307 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add306
  %load308 = load i32, ptr addrspace(1) %getelementptr307, align 4, !tbaa !28, !noundef !3
  %add309 = add nsw i64 %iv, -7
  %getelementptr310 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add309
  %load311 = load i32, ptr addrspace(1) %getelementptr310, align 4, !tbaa !28, !noundef !3
  %xor312 = xor i32 %load311, %load308
  %add313 = add nsw i64 %iv, -13 
  %getelementptr314 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add313
  %load315 = load i32, ptr addrspace(1) %getelementptr314, align 4, !tbaa !28, !noundef !3
  %xor316 = xor i32 %xor312, %load315
  %add317 = add nsw i64 %iv, -15
  %getelementptr318 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add317
  %load319 = load i32, ptr addrspace(1) %getelementptr318, align 4, !tbaa !28, !noundef !3
  %xor320 = xor i32 %xor316, %load319
  %call321 = call i32 @llvm.fshl.i32(i32 %xor320, i32 %xor320, i32 1) #5
  %getelementptr322 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add305
  store i32 %call321, ptr addrspace(1) %getelementptr322, align 4, !tbaa !28
  %add323 = add nuw nsw i64 %iv, 2
  %icmp324 = icmp ugt i64 %add305, 78
  br i1 %icmp324, label %6, label %vectorized_slp_bb

When we vectorize it, we get:

vectorized_slp_bb:                                ; preds = %vectorized_slp_bb, %bb2
  %iv = phi i64 [ %add323, %vectorized_slp_bb ], [ 16, %bb2 ]
  %add288 = add nsw i64 %iv, -3
  %getelementptr289 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add288
  %add291 = add nsw i64 %iv, -8
  %getelementptr292 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add291
  %add295 = add nsw i64 %iv, -14 
  %getelementptr296 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add295
  %add299 = add nsw i64 %iv, -16 
  %getelementptr300 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %add299
  %getelementptr304 = getelementptr inbounds i32, ptr addrspace(1) %getelementptr4, i64 %iv 
  %add305 = add nuw nsw i64 %iv, 1
  %25 = load <2 x i32>, ptr addrspace(1) %getelementptr289, align 4, !tbaa !28 
  %26 = load <2 x i32>, ptr addrspace(1) %getelementptr292, align 4, !tbaa !28 
  %27 = xor <2 x i32> %26, %25 
  %28 = load <2 x i32>, ptr addrspace(1) %getelementptr296, align 4, !tbaa !28 
  %29 = xor <2 x i32> %27, %28 
  %30 = load <2 x i32>, ptr addrspace(1) %getelementptr300, align 4, !tbaa !28 
  %31 = xor <2 x i32> %29, %30 
  %32 = call <2 x i32> @llvm.fshl.v2i32(<2 x i32> %31, <2 x i32> %31, <2 x i32> <i32 1, i32 1>) 
  store <2 x i32> %32, ptr addrspace(1) %getelementptr304, align 4, !tbaa !28 
  %add323 = add nuw nsw i64 %iv, 2
  %icmp324 = icmp ugt i64 %add305, 78
  br i1 %icmp324, label %6, label %vectorized_slp_bb

We see about a 40% degradation on benchmark that optimizes this hot loop.
The assembly for this loop shows we use 3 xor instead of vpxor and the fshl lowering using xmm registers:

 movq  -12(%rax,%rcx,4), %rdx 
  xorq  8(%rax,%rcx,4), %rdx 
  xorq  -36(%rax,%rcx,4), %rdx 
  xorq  -44(%rax,%rcx,4), %rdx 
  vmovq %rdx, %xmm0
  vpsrld  $31, %xmm0, %xmm1
  vpaddd  %xmm0, %xmm0, %xmm0
  vpor  %xmm1, %xmm0, %xmm0
  vmovq %xmm0, 20(%rax,%rcx,4)
  addq  $2, %rcx 
  cmpq  $78, %rcx 

While looking at cost model for X86 arithmetic instructions, I do not see anything for v2i32 for XOR. Should we actually vectorize this loop?

Will attach the IR reproducer and -slp-threshold=2 shows we only vectorize this tree and still see the 40% degradation.

[annamthomas]

Here is the reproducer: https://godbolt.org/z/s1PjYMs5a

[annamthomas]

@alexey-bataev @RKSimon any pointers here on what the issue might be?

[annamthomas]

So, I tried printing the cost-model for xor and fshl under different mattr:

opt chk.ll -passes="print<cost-model>" 2>&1 -disable-output -mtriple=x86_64-- -mattr=+avx512f,+avx512bw

Cost Model: Found an estimated cost of 1 for instruction:   %V2I32 = xor <2 x i32> undef, undef
Cost Model: Found an estimated cost of 1 for instruction:   %call303 = call <2 x i32> @llvm.fshl.v2i32(<2 x i32> %V2I32, <2 x i32> %V2I32, <2 x i32> <i32 1, i32 1>)
Cost Model: Found an estimated cost of 1 for instruction:   %V4I32 = xor <4 x i32> undef, undef
Cost Model: Found an estimated cost of 1 for instruction:   %call304 = call <4 x i32> @llvm.fshl.v4i32(<4 x i32> %V4I32, <4 x i32> %V4I32, <4 x i32> <i32 1, i32 1, i32 1, i32 1>)

opt chk.ll -passes="print" 2>&1 -disable-output -mtriple=x86_64-- -mattr=+avx2

Cost Model: Found an estimated cost of 1 for instruction:   %V2I32 = xor <2 x i32> undef, undef
Cost Model: Found an estimated cost of 4 for instruction:   %call303 = call <2 x i32> @llvm.fshl.v2i32(<2 x i32> %V2I32, <2 x i32> %V2I32, <2 x i32> <i32 1, i32 1>)
Cost Model: Found an estimated cost of 1 for instruction:   %V4I32 = xor <4 x i32> undef, undef
Cost Model: Found an estimated cost of 4 for instruction:   %call304 = call <4 x i32> @llvm.fshl.v4i32(<4 x i32> %V4I32, <4 x i32> %V4I32, <4 x i32> <i32 1, i32 1, i32 1, i32 1>)

Changing -mattr=+avx2 on the above testcase should increase the cost of the vector fshl from 1 to 4. However, debug shows SLP cost model as -11 ! Shouldn't it reduce from -8 to -5 instead?

SLP: Found cost = -11 for VF=2
SLP: Decided to vectorize cost = -11

[llvmbot]

@llvm/issue-subscribers-backend-x86

[RKSimon]

The v2i32 types should be legalized to v4i32 inside the TTI callbacks, AVX512 does have a cheap v4i32 rotate instruction which is what those fshl should lower to, but on AVX2 they will expand to shifts/or - hence the higher cost.

What I think is going on though is the high cost of the scalar rotate instructions - we don't cost constant rotate amounts as cheaper than the variable rotate instructions, despite being notably faster on almost all hardware.:

{ ISD::ROTL,       MVT::i32,     {  2,  3,  1,  3 } },

So we'd need to add lower costs for constant rotate amounts.

[alexey-bataev]

I don't think it is directly related to SLP vectorizer, but x86 cost model. And Simon, probably , identified the actual issue.

[annamthomas]

Yep, thank you. I was looking at the cost of the vector ones and trying to increase those.
@RKSimon I tried reducing the cost of ROTL and ROTR for i32 (scalar) to all ones - just as a quick check to see what happens.
We did reduce the benefit of SLP Vectorization, so it is in the right direction (but we still vectorize) :

SLP: Found cost = -6 for VF=2
SLP: Decided to vectorize cost = -6  

Earlier it was -8.

For reference, the scalar assembly is:

movl    8(%rcx,%rax,4), %esi
xorl    -12(%rcx,%rax,4), %esi
movl    -44(%rcx,%rax,4), %edi
xorl    -36(%rcx,%rax,4), %edi
xorl    %esi, %edi
rorxl   $31, %edi, %esi
movl    %esi, 20(%rcx,%rax,4)
incq    %rax
cmpq    $78, %rax
jbe     -38 

AVX512 does have a cheap v4i32 rotate instruction which is what those fshl should lower to

I tested this with couple of different mattr and I think the cost may not be reflecting the lowering.

cat chk.ll
declare <2 x i32> @llvm.fshl.v2i32(<2 x i32>, <2 x i32>, <2 x i32>)

define <2 x i32> @splatconstant_funnnel_v2i32(<2 x i32> %x) nounwind {
  %res = call <2 x i32> @llvm.fshl.v2i32(<2 x i32> %x, <2 x i32> %x, <2 x i32> <i32 1, i32 1>)
  ret <2 x i32> %res
}
llc -mtriple=x86_64-unknown-unknown -mattr=+avx512f,+avx512vbmi,+avx512vbmi2 -mcpu=cascadelake chk.ll 

splatconstant_funnnel_v2i32:            # @splatconstant_funnnel_v2i32
# %bb.0:
	vprold	$1, %xmm0, %xmm0
	retq

True for avx512 and for avx2 with +xop (lowers to single instruction: vprotd $1, %xmm0, %xmm0).

However, for the mattr from this repro.ll, we lowered fshl into three vector instructions:

llc -mattr=+avx512cd,-sha,+xsaveopt,-avxvnni,-mwaitx,+sse4.2,-cldemote,+avx512f,+lzcnt,+fsgsbase,+aes,-sse4a,+rtm,+fma,-avx512vp2intersect,-avxneconvert,+popcnt,-prefetchi,+avx2,-uintr,-ptwrite,+fxsr,-pconfig,-avx512er,+rdseed,+pku,-rdpid,-avx512vbmi,-avx512vbmi2,+sse3,+xsaves,-amx-tile,-fma4,+invpcid,-cmpccxadd,-prefetchwt1,+ssse3,+pclmul,+clflushopt,-tsxldtrk,+crc32,+rdrnd,+sse2,-kl,-clzero,+bmi,-raoint,+xsavec,-serialize,-avxvnniint8,+sse,-rdpru,-tbm,-avx512bf16,-waitpkg,-amx-fp16,-avx512ifma,-vaes,+f16c,+sahf,+xsave,+avx512bw,-amx-int8,-vpclmulqdq,-sgx,-avx512fp16,-gfni,-amx-bf16,+bmi2,-movdir64b,+avx512vl,-xop,+prfchw,+cx16,-enqcmd,+64bit,-amx-complex,-avx512pf,-lwp,-avx512vpopcntdq,+avx512dq,+mmx,-avxifma,+avx512vnni,+avx,+cmov,-hreset,+sse4.1,+movbe,+adx,+clwb,-widekl,-movdiri,+cx8,-shstk,-avx512bitalg,-wbnoinvd,-avx512f -mcpu=cascadelake -mtriple=x86_64-unknown-linux-gnu chk.ll 
splatconstant_funnnel_v2i32:            # @splatconstant_funnnel_v2i32
# %bb.0:
	vpsrlvd	.LCPI0_0(%rip), %xmm0, %xmm1
	vpsllvd	.LCPI0_1(%rip), %xmm0, %xmm0
	vpor	%xmm1, %xmm0, %xmm0
	retq

[RKSimon]

So there's a couple of problems to address:

• missing rotate/funnel-shift by constant scalar/vector costs
• pre-AVX512 the DAG fails to expand rotate-shift-by-imm to use vector-shift-by-imm

[annamthomas]

Thanks @RKSimon for taking this up! I instrumented the SLPVectorizer cost model and confirmed that the fshl costs correctly reflect what we get in the lowered code.