[VectorCombine] Handle shuffle of selects

[RKSimon]

VectorCombine can't currently fold shuffle(select(c0,t0,f0), select(c1,t1,f1)) -> select(shuffle(c0,c1),shuffle(t0,t1),shuffle(f0,f1)) - although foldShuffleToIdentity can fold some very basic cases.

This is trickier than foldShuffleOfBinops etc. as the default increase in instruction count will likely prevent basic fold from succeeding (from a cost:benefit), so we will need to just handle cases where at least one of the folded inner shuffles gets simplified away.

[ParkHanbum]

https://alive2.llvm.org/ce/z/JKWwRr
Is this example appropriate for this issue?

[RKSimon]

That's the general idea, although I think that case is already handled as vector-combine can already handle smin intrinsics, which instcombine will create from the icmp+select:

define <8 x i16> @src(<4 x i16> %a, <4 x i16> %b, <4 x i16> %c, <4 x i16> %d) {
  %cmp.a.b = icmp slt <4 x i16> %a, %b
  %cmp.c.d = icmp slt <4 x i16> %c, %d
  %select.a.b = select <4 x i1> %cmp.a.b, <4 x i16> %a, <4 x i16> %b
  %select.c.d = select <4 x i1> %cmp.c.d, <4 x i16> %c, <4 x i16> %d
  %res = shufflevector <4 x i16> %select.a.b, <4 x i16> %select.c.d, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
  ret <8 x i16> %res 
}

opt -passes=instcombine

define <8 x i16> @src(<4 x i16> %a, <4 x i16> %b, <4 x i16> %c, <4 x i16> %d) {
  %select.a.b = call <4 x i16> @llvm.smin.v4i16(<4 x i16> %a, <4 x i16> %b)
  %select.c.d = call <4 x i16> @llvm.smin.v4i16(<4 x i16> %c, <4 x i16> %d)
  %res = shufflevector <4 x i16> %select.a.b, <4 x i16> %select.c.d, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
  ret <8 x i16> %res
}

(and then) opt -passes=vector-combine

define <8 x i16> @src(<4 x i16> %a, <4 x i16> %b, <4 x i16> %c, <4 x i16> %d) {
  %shuffle.true = shufflevector <4 x i16> %a, <4 x i16> %c, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
  %shuffle.false = shufflevector <4 x i16> %b, <4 x i16> %d, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
  %select = call <8 x i16> @llvm.smin.v8i16(<8 x i16> %shuffle.true, <8 x i16> %shuffle.false)
  ret <8 x i16> %select
}

[ParkHanbum]

It is a sample that is not optimized in InstCombin Pass. May I ask you a question? For Combine you explained, it seems that 3 instructions are increased to 4. Can we benefit from this case as well?
https://alive2.llvm.org/ce/z/bk7jtA

[dtcxzyw]

It is a sample that is not optimized in InstCombin Pass. May I ask you a question? For Combine you explained, it seems that 3 instructions are increased to 4. Can we benefit from this case as well? https://alive2.llvm.org/ce/z/bk7jtA

For vector instructions, we usually estimate the effect of a transformation with a target-specific cost model in VectorCombine.
In this case, you can see that the codegen of the latter form is better (https://alive2.llvm.org/ce/z/pAHdUZ), even if the latter form has more instructions than the former in LLVM IR.

[RKSimon]

VectorCombine tend to allow increases in vector instruction counts if we know the total cost has decreased (if old/new costs are equal we do expect an instruction count equal/decrease though).