Re: [07/13] Make vec_perm_indices use new vector encoding

[Richard Sandiford <richard.sandiford@linaro.org>]

Richard Biener <richard.guenther@gmail.com> writes:
> On Tue, Dec 12, 2017 at 4:46 PM, Richard Sandiford
> <richard.sandiford@linaro.org> wrote:
>> Richard Biener <richard.guenther@gmail.com> writes:
>>> On Sun, Dec 10, 2017 at 12:20 AM, Richard Sandiford
>>> <richard.sandiford@linaro.org> wrote:
>>>> This patch changes vec_perm_indices from a plain vec<> to a class
>>>> that stores a canonicalised permutation, using the same encoding
>>>> as for VECTOR_CSTs.  This means that vec_perm_indices now carries
>>>> information about the number of vectors being permuted (currently
>>>> always 1 or 2) and the number of elements in each input vector.
>>>
>>> Before I dive into  the C++ details can you explain why it needs this
>>> info and how it encodes it for variable-length vectors?  To interleave
>>> two vectors you need sth like { 0, N, 1, N+1, ... }, I'm not sure we
>>> can directly encode N here, can we?  extract even/odd should just
>>> work as { 0, 2, 4, 6, ...} without knowledge of whether we permute
>>> one or two vectors (the one vector case just has two times the same
>>> vector) or how many elements each of the vectors (or the result) has.
>>
>> One of the later patches switches the element types to HOST_WIDE_INT,
>> so that we can represent all ssizetypes.  Then there's a poly_int
>> patch (not yet posted) to make that poly_int64, so that we can
>> represent the N even for variable-length vectors.
>>
>> The class needs to know the number of elements because that affects
>> the canonical representation.  E.g. extract even on fixed-length
>> vectors with both inputs the same should be { 0, 2, 4, ..., 0, 2, 4 ... },
>> which we can't encode as a simple series.  Interleave low with both
>> inputs the same should be { 0, 0, 1, 1, ... } for both fixed-length and
>> variable-length vectors.
>
> Huh?  extract even is { 0, 2, 4, 6, 8 ... } indexes in the selection vector
> are referencing concat'ed input vectors.  So yes, for two same vectors
> that's effectively { 0, 2, 4, ..., 0, 2, 4, ... } but I don't see why
> that should
> be the canonical form?

Current practice is to use the single-input form where possible,
if both inputs are the same (see e.g. the VEC_PERM_EXPR handling
in fold-const.c).  It means that things like:

    _1 = VEC_PERM_EXPR <a, a, { 0, 2, 4, 6, 0, 2, 4, 6 }>;
    _2 = VEC_PERM_EXPR <a, a, { 0, 2, 4, 6, 8, 10, 12, 14 }>;
    _3 = VEC_PERM_EXPR <a, b, { 0, 2, 4, 6, 0, 2, 4, 6 }>;

get folded to the same sequence, and so can be CSEd.

We could instead convert the single-input form to use the two-input
selector, but that would be harder.  The advantage of treating the
single-input form as canonical is that it works even for irregular
permutes.

Thanks,
Richard

>> Also, operator[] is supposed to return an in-range selector even if
>> the selector element is only implicitly encoded.  So we need to know
>> the number of input elements there.
>>
>> Separating the number of input elements into the number of inputs
>> and the number of elements per input isn't really necessary, but made
>> it easier to provide routines for testing whether all selected
>> elements come from a particular input, and for rotating the selector
>> by a whole number of inputs.
>>
>> Thanks,
>> Richard