[LLVMdev] Generalizing shuffle vector

[Eli Friedman]

On Mon, Sep 29, 2008 at 8:11 PM, Mon Ping Wang <wangmp at apple.com> wrote:
> The problem with generating insert and extracts is that we can generate poor
> code
>        %tmp16 = extractelement <4 x float> %f4b, i32 0
>        %f8a = insertelement <8 x float> %f8a, float %tmp16, i32 0
>        %tmp18 = extractelement <4 x float> %f4b, i32 1
>        %f8c = insertelement <8 x float> %f8b, float %tmp18, i32 1
>       ...
> For X86, legalize will convert each insertelement to become a vector
> shuffle.  We are very careful in combining vector shuffles because we don't
> want to produce a vector shuffle whose mask is illegal or hard to code gen
> so we end up in this code to generate a sequence of unpcks and movhlps for
> this.  With the new form, Legalize will divide the 8xf32 vector into two
> 4xf32 and since the two sides are the same, it will generate quad word moves
> to copy the values.

I think this specific issue can be fixed without extending the
IL-level syntax; DAGCombiner could easily be made a lot more clever
about cases like this.  For example, before legalization, we can
transform an INSERT_VECTOR_ELT inserting an element into a constant
vector or a SCALAR_TO_VECTOR into a BUILD_VECTOR, and we can transform
BUILD_VECTOR into CONCAT_VECTORS or EXTRACT_SUBVECTOR for relevant
cases.  We can also make the lowering significantly more clever about
dealing with insertelement.

If what we currently have isn't sufficient, I think the first step is
to extend VECTOR_SHUFFLE to be more flexible, and implement the
relevant combines to make that effective.  I don't think it makes
sense to add this extension to the IL before it's proven that we can
do CodeGen on it reasonably.

I'm not necessarily against this extension, but since we're talking
about constructs which can already represented in the IL without
losing too much semantic information, we really want to be going about
this from the bottom up.  It's going to be hard to properly see the
concrete benefits without a solid baseline to compare against.

-Eli