Missed optimization for extract/insertelements equivalent to movhps

[efriedma-quic]

Bugzilla Link	2109
Resolution	FIXED
Resolved on	Dec 28, 2015 13:09
Version	unspecified
OS	Linux
CC	@rotateright

Extended Description

Take the following bitcode

define <4 x float> @​_mm_loadh_pi22(<4 x float> %__A, <2 x i32>* %__P) nounwind {
entry:
load <2 x i32>* %__P
bitcast <2 x i32> %0 to <2 x float>
extractelement <2 x float> %1, i32 0
extractelement <2 x float> %1, i32 1
insertelement <4 x float> %__A, float %2, i32 2
insertelement <4 x float> %4, float %3, i32 3
ret <4 x float> %5
}

This currently codegens to the following:
_mm_loadh_pi22:
subl $8, %esp
movl 12(%esp), %eax
movl 4(%eax), %ecx
movl %ecx, 4(%esp)
movl (%eax), %eax
movl %eax, (%esp)
movss (%esp), %xmm1
movaps %xmm0, %xmm2
shufps $3, %xmm1, %xmm2
shufps $36, %xmm2, %xmm0
movss 4(%esp), %xmm1
movaps %xmm0, %xmm2
shufps $2, %xmm1, %xmm2
shufps $132, %xmm2, %xmm0
addl $8, %esp
ret

Unless I've made a mistake, this should codegen to the following:
_mm_loadh_pi22:
movl 4(%esp), %eax
movhps (%eax), %xmm0
ret

Note that LLVM does know how to generate movhps... it does in fact generate it for the following, which is functionally equivalent:
define <4 x float> @​_mm_loadh_pi22(<4 x float> %__A, <1 x i64>* %__P) nounwind {
entry:
%tmp4 = bitcast <1 x i64>* %__P to double*
%tmp5 = load double* %tmp4
%tmp6 = insertelement <2 x double> undef, double %tmp5, i32 0
%tmp8 = bitcast <2 x double> %tmp6 to <4 x float>
%tmp9 = shufflevector <4 x float> %__A, <4 x float> %tmp8, <4 x i32> < i32 0, i32 1, i32 4, i32 5 >
ret <4 x float> %tmp9
}

[efriedma-quic]

assigned to @rotateright

[lattner]

This seems a similar issue to 2110: use of <2 x i32> instead of double leads to ugly code because 2 x i32 is not legal. clang should generate code that uses legal types for intrinsics where possible.

[llvmbot]

The new LegalizeTypes machinery gives slightly better code:

_mm_loadh_pi22:
subl $12, %esp
movl 16(%esp), %eax
movq (%eax), %mm0
movq %mm0, (%esp)
movss (%esp), %xmm1
movaps %xmm0, %xmm2
shufps $3, %xmm1, %xmm2
shufps $36, %xmm2, %xmm0
movss 4(%esp), %xmm1
movaps %xmm0, %xmm2
shufps $2, %xmm1, %xmm2
shufps $132, %xmm2, %xmm0
addl $12, %esp
ret

There are some strange things though: v2i32 is legal but v2f32 is not,
which seems rather strange.

After type legalization the DAG is:

0x8b93608: ch = EntryToken
0x8b936b8: i32 = FrameIndex <0>
0x8b93608:
0x8b93608:
0x8b93f30: i32 = FrameIndex <-1>
0x8b94030:
0x8b93758: i32,ch = load 0x8b93608, 0x8b93f30, 0x8b94030 <0x8b93f9c:-1> alignment=8
0x8b94030:
0x8b93c88: v2i32,ch = load 0x8b93608, 0x8b93758, 0x8b94030 <0x8b81988:0> alignment=8
0x8b94030: i32 = undef
0x8b93608:
0x8b93c88:
0x8b936b8:
0x8b94030:
0x8b94088: ch = store 0x8b93608, 0x8b93c88, 0x8b936b8, 0x8b94030 null:0 alignment=8
0x8b93c88:
0x8b93608:
0x8b93e40: v4f32 = Register #​1024
0x8b93ea8: v4f32,ch = CopyFromReg 0x8b93608, 0x8b93e40
0x8b94088:
0x8b936b8:
0x8b94030:
0x8b95e00: f32,ch = load 0x8b94088, 0x8b936b8, 0x8b94030 null:0 alignment=8
0x8b94288: i32 = Constant <2>
0x8b942f0: v4f32 = insert_vector_elt 0x8b93ea8, 0x8b95e00, 0x8b94288
0x8b94088:
0x8b936b8:
0x8b94130: i32 = Constant <4>
0x8b937f0: i32 = add 0x8b936b8, 0x8b94130
0x8b94030:
0x8b95d00: f32,ch = load 0x8b94088, 0x8b937f0, 0x8b94030 null:4 alignment=4
0x8b94368: i32 = Constant <3>
0x8b943d0: v4f32 = insert_vector_elt 0x8b942f0, 0x8b95d00, 0x8b94368
0x8b939c0: i32 = Constant <0>
0x8b94448: ch = ret 0x8b93c88:1, 0x8b943d0, 0x8b939c0

It then gets passed to LegalizeDAG (which should only be legalizing
operations). LegalizeDAG introduces a ton of vector shuffles. But why?

Here it is after LegalizeDAG:

0x8b93608: ch = EntryToken
0x8b936b8: i32 = FrameIndex <0>
0x8b93608:
0x8b93608:
0x8b93f30: i32 = FrameIndex <-1>
0x8b94030:
0x8b93758: i32,ch = load 0x8b93608, 0x8b93f30, 0x8b94030 <0x8b93f9c:-1> alignment=8
0x8b94030:
0x8b93ae8: v1i64,ch = load 0x8b93608, 0x8b93758, 0x8b94030 <0x8b81988:0> alignment=8
0x8b93d20: i16 = Constant <1>
0x8b93d88: i16 = Constant <4>
0x8b93608:
0x8b93e40: v4f32 = Register #​1024
0x8b93ea8: v4f32,ch = CopyFromReg 0x8b93608, 0x8b93e40
0x8b94030: i32 = undef
0x8b93608:
0x8b93ae8:
0x8b93a40: v2i32 = bit_convert 0x8b93ae8
0x8b936b8:
0x8b94030:
0x8b94088: ch = store 0x8b93608, 0x8b93a40, 0x8b936b8, 0x8b94030 null:0 alignment=8
0x8b94220: i16 = Constant <0>
0x8b952d8: i16 = undef
0x8b95560: i16 = Constant <6>
0x8b93ea8:
0x8b93ea8:
0x8b94088:
0x8b936b8:
0x8b94030:
0x8b95e00: f32,ch = load 0x8b94088, 0x8b936b8, 0x8b94030 null:0 alignment=8
0x8b941b8: v4f32 = scalar_to_vector 0x8b95e00
0x8b93858: i16 = Constant <3>
0x8b952d8:
0x8b93d88:
0x8b952d8:
0x8b95428: v4i16 = BUILD_VECTOR 0x8b93858, 0x8b952d8, 0x8b93d88, 0x8b952d8
0x8b954c8: v4f32 = vector_shuffle 0x8b93ea8, 0x8b941b8, 0x8b95428<3,u,4,u>
0x8b94220:
0x8b93d20:
0x8b95560:
0x8b93d88:
0x8b955c8: v4i16 = BUILD_VECTOR 0x8b94220, 0x8b93d20, 0x8b95560, 0x8b93d88
0x8b95648: v4f32 = vector_shuffle 0x8b93ea8, 0x8b954c8, 0x8b955c8<0,1,6,4>
0x8b93ae8:
0x8b95b70: v4f32 = Register XMM0
0x8b95648:
0x8b95648:
0x8b94088:
0x8b936b8:
0x8b94130: i32 = Constant <4>
0x8b937f0: i32 = add 0x8b936b8, 0x8b94130
0x8b94030:
0x8b95d00: f32,ch = load 0x8b94088, 0x8b937f0, 0x8b94030 null:4 alignment=4
0x8b956c0: v4f32 = scalar_to_vector 0x8b95d00
0x8b95728: i16 = Constant <2>
0x8b952d8:
0x8b93d88:
0x8b952d8:
0x8b95960: v4i16 = BUILD_VECTOR 0x8b95728, 0x8b952d8, 0x8b93d88, 0x8b952d8
0x8b959e0: v4f32 = vector_shuffle 0x8b95648, 0x8b956c0, 0x8b95960<2,u,4,u>
0x8b94220:
0x8b93d20:
0x8b93d88:
0x8b95560:
0x8b95a78: v4i16 = BUILD_VECTOR 0x8b94220, 0x8b93d20, 0x8b93d88, 0x8b95560
0x8b95af8: v4f32 = vector_shuffle 0x8b95648, 0x8b959e0, 0x8b95a78<0,1,4,6>
0x8b95bd8: ch,flag = CopyToReg 0x8b93ae8:1, 0x8b95b70, 0x8b95af8
0x8b95bd8:
0x8b94220:
0x8b95bd8:
0x8b95c50: ch = X86ISD::RET_FLAG 0x8b95bd8, 0x8b94220, 0x8b95bd8:1

[llvmbot]

Juice up bit_convert of a legal to an illegal vector type.

[llvmbot]

[In which I discover that creating an attachment wipes out any comments
made at the same time...]

With the previous patch (not applied, because it results in worse
code for 2007-05-05-VecCastExpand.ll), the result of type legalization
is:

0x8b93608: ch = EntryToken
0x8b939c0: i32 = Constant <0>
0x8b93608:
0x8b93608:
0x8b93f30: i32 = FrameIndex <-1>
0x8b94030:
0x8b93758: i32,ch = load 0x8b93608, 0x8b93f30, 0x8b94030 <0x8b93f9c:-1> alignment=8
0x8b94030:
0x8b93c88: v2i32,ch = load 0x8b93608, 0x8b93758, 0x8b94030 <0x8b81988:0> alignment=8
0x8b94030: i32 = undef
0x8b93c88:
0x8b93608:
0x8b93e40: v4f32 = Register #​1024
0x8b93ea8: v4f32,ch = CopyFromReg 0x8b93608, 0x8b93e40
0x8b93c88:
0x8b939c0:
0x8b93858: i32 = extract_vector_elt 0x8b93c88, 0x8b939c0
0x8b93928: f32 = bit_convert 0x8b93858
0x8b94288: i32 = Constant <2>
0x8b942f0: v4f32 = insert_vector_elt 0x8b93ea8, 0x8b93928, 0x8b94288
0x8b93c88:
0x8b941b8: i32 = Constant <1>
0x8b93a58: i32 = extract_vector_elt 0x8b93c88, 0x8b941b8
0x8b937f0: f32 = bit_convert 0x8b93a58
0x8b94368: i32 = Constant <3>
0x8b943d0: v4f32 = insert_vector_elt 0x8b942f0, 0x8b937f0, 0x8b94368
0x8b939c0:
0x8b94448: ch = ret 0x8b93c88:1, 0x8b943d0, 0x8b939c0

This seems pretty good to me, but as before LegalizeDAG then expands
extract_vector_elt and insert_vector_elt into crazy code sequences.

[efriedma-quic]

v2i32 is legal because you can use one in an MMX register. That said, we try to avoid generating MMX instructions because of the difficulty of efficiently dealing with the requirements for when emms needs to be generated.

[lattner]

Right. In fact, for clients that use generic vectors, we should really add an option/-mattr to the x86 backend that disables MMX entirely. Not generating EMMS breaks code that uses generic vectors.

[lattner]

Ok, this codegen suboptimality is real, but can be solved in other ways for
most uses. Do you mind if I move this to the README file and close this bug?

[efriedma-quic]

I suppose it would be okay to move... it would really be nice if this sort of stuff just worked, though, it wouldn't be so sensitive to how exactly the code is written. The bitcasts aren't the only issue here; this sort of stuff generates ugly results even without the presence of weird bitcasts, like the following examples:

typedef float vi attribute((vector_size(16)));
typedef float vi2 attribute((vector_size(8)));
vi x(vi2 a, vi b) {return (vi) {a[0],a[1],b[2],b[3]};}

typedef int vi attribute((vector_size(16)));
typedef int vi2 attribute((vector_size(8)));
vi x(vi2 a, vi b) {return (vi) {a[0],a[1],b[2],b[3]};}

And, also, writing code that actually generates movhps using vector intrinsics is relatively painful; this is what's needed to get the ideal codegen for the original example (I couldn't come up with anything shorter):

typedef float v4f attribute((vector_size(16)));
typedef int v2i attribute((vector_size(8)));
typedef double v2d attribute((vector_size(16)));
v4f x(v4f b, v2i* a) {
double undef;
v2d x = (v2d){(double)a, undef}, y = (v2d)b;
return __builtin_shufflevector((v4f)x, (v4f)y, 4, 5, 0, 1);
}

And for the examples with direct arguments, I couldn't get LLVM to generate the ideal code at all.

[efriedma-quic]

typedef float v4f attribute((vector_size(16)));
typedef int v2i attribute((vector_size(8)));
typedef double v2d attribute((vector_size(16)));
v4f x(v4f b, v2i* a) {
double undef;
v2d x = (v2d){(double)a, undef}, y = (v2d)b;
return __builtin_shufflevector((v4f)x, (v4f)y, 4, 5, 0, 1);
}

Oh, and on a side note, on certain architectures, this could actually end up crashing/corrupting data if, for example, (double)a happens to correspond to a QNaN.

[rotateright]

7.5 years pass...

And it still doesn't work (x86-64 target now):

$ cat 2109.ll
define <4 x float> @​_mm_loadh_pi22(<4 x float> %A, <2 x i32>* %P) {
%ld = load <2 x i32>, <2 x i32>* %P
%bc = bitcast <2 x i32> %ld to <2 x float>
%e1 = extractelement <2 x float> %bc, i32 0
%e2 = extractelement <2 x float> %bc, i32 1
%i1 = insertelement <4 x float> %A, float %e1, i32 2
%i2 = insertelement <4 x float> %i1, float %e2, i32 3
ret <4 x float> %i2
}

$ ./opt -O2 2109.ll -S | ./llc -o -
...
movq (%rdi), %xmm1 ## xmm1 = mem[0],zero
movdqa %xmm1, %xmm2
shufps $229, %xmm2, %xmm2 ## xmm2 = xmm2[1,1,2,3]
shufps $48, %xmm0, %xmm1 ## xmm1 = xmm1[0,0],xmm0[3,0]
shufps $132, %xmm1, %xmm0 ## xmm0 = xmm0[0,1],xmm1[0,2]
shufps $32, %xmm0, %xmm2 ## xmm2 = xmm2[0,0],xmm0[2,0]
shufps $36, %xmm2, %xmm0 ## xmm0 = xmm0[0,1],xmm2[2,0]
retq

[rotateright]

Treat this as an InstCombine problem as suggested in the original description? Bitcast + insert + shuffle or just two shuffles are better than two extracts + two inserts:

define <4 x float> @​_mm_loadh_pi22_4(<4 x float> %A, <2 x i32>* %P) {
%ld = load <2 x i32>, <2 x i32>* %P
%bc = bitcast <2 x i32> %ld to <2 x float>
%i1 = shufflevector <2 x float> undef, <2 x float> %bc, <4 x i32> < i32 0, i32 1, i32 2, i32 3 >
%i2 = shufflevector <4 x float> %A, <4 x float> %i1, <4 x i32> < i32 0, i32 1, i32 6, i32 7 >
ret <4 x float> %i2
}

That codegens to almost what we want:

movhpd	(%rdi), %xmm0
retq

[rotateright]

There's a comment in InstCombine's visitShuffleVectorInst():
"Here we are really conservative:
we are absolutely afraid of producing a shuffle mask not in the input program"

However, it seems we can enhance the insert/extract pattern matching slightly to account for this case. All of the hard work is already done there, but it bails out when it sees that the source vector is not the same size as the destination vector.

If we allow that extending a vector to a larger size with undef elements is a free operation, then we can create a shufflevector that does that, replace all of the extractelement uses of that vector, and let the existing code do what it already tries to do for vectors with equal types.

[rotateright]

Patch submitted for review:
http://reviews.llvm.org/D15096

[rotateright]

Fixed (enough?) with:
http://reviews.llvm.org/rL256394

We select 'movhpd' rather than 'movhps' (one byte smaller), but that's a separate bug IMO.