Re: Extend fold_vec_perm to fold VEC_PERM_EXPR in VLA manner

[Prathamesh Kulkarni <prathamesh.kulkarni@linaro.org>]

On Mon, 21 Nov 2022 at 14:37, Prathamesh Kulkarni
<prathamesh.kulkarni@linaro.org> wrote:
>
> On Fri, 4 Nov 2022 at 14:00, Prathamesh Kulkarni
> <prathamesh.kulkarni@linaro.org> wrote:
> >
> > On Mon, 31 Oct 2022 at 15:27, Richard Sandiford
> > <richard.sandiford@arm.com> wrote:
> > >
> > > Prathamesh Kulkarni <prathamesh.kulkarni@linaro.org> writes:
> > > > On Wed, 26 Oct 2022 at 21:07, Richard Sandiford
> > > > <richard.sandiford@arm.com> wrote:
> > > >>
> > > >> Sorry for the slow response.  I wanted to find some time to think
> > > >> about this a bit more.
> > > >>
> > > >> Prathamesh Kulkarni <prathamesh.kulkarni@linaro.org> writes:
> > > >> > On Fri, 30 Sept 2022 at 21:38, Richard Sandiford
> > > >> > <richard.sandiford@arm.com> wrote:
> > > >> >>
> > > >> >> Richard Sandiford via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
> > > >> >> > Prathamesh Kulkarni <prathamesh.kulkarni@linaro.org> writes:
> > > >> >> >> Sorry to ask a silly question but in which case shall we select 2nd vector ?
> > > >> >> >> For num_poly_int_coeffs == 2,
> > > >> >> >> a1 /trunc n1 == (a1 + 0x) / (n1.coeffs[0] + n1.coeffs[1]*x)
> > > >> >> >> If a1/trunc n1 succeeds,
> > > >> >> >> 0 / n1.coeffs[1] == a1/n1.coeffs[0] == 0.
> > > >> >> >> So, a1 has to be < n1.coeffs[0] ?
> > > >> >> >
> > > >> >> > Remember that a1 is itself a poly_int.  It's not necessarily a constant.
> > > >> >> >
> > > >> >> > E.g. the TRN1 .D instruction maps to a VEC_PERM_EXPR with the selector:
> > > >> >> >
> > > >> >> >   { 0, 2 + 2x, 1, 4 + 2x, 2, 6 + 2x, ... }
> > > >> >>
> > > >> >> Sorry, should have been:
> > > >> >>
> > > >> >>   { 0, 2 + 2x, 2, 4 + 2x, 4, 6 + 2x, ... }
> > > >> > Hi Richard,
> > > >> > Thanks for the clarifications, and sorry for late reply.
> > > >> > I have attached POC patch that tries to implement the above approach.
> > > >> > Passes bootstrap+test on x86_64-linux-gnu and aarch64-linux-gnu for VLS vectors.
> > > >> >
> > > >> > For VLA vectors, I have only done limited testing so far.
> > > >> > It seems to pass couple of tests written in the patch for
> > > >> > nelts_per_pattern == 3,
> > > >> > and folds the following svld1rq test:
> > > >> > int32x4_t v = {1, 2, 3, 4};
> > > >> > return svld1rq_s32 (svptrue_b8 (), &v[0])
> > > >> > into:
> > > >> > return {1, 2, 3, 4, ...};
> > > >> > I will try to bootstrap+test it on SVE machine to test further for VLA folding.
> > > >> >
> > > >> > I have a couple of questions:
> > > >> > 1] When mask selects elements from same vector but from different patterns:
> > > >> > For eg:
> > > >> > arg0 = {1, 11, 2, 12, 3, 13, ...},
> > > >> > arg1 = {21, 31, 22, 32, 23, 33, ...},
> > > >> > mask = {0, 0, 0, 1, 0, 2, ... },
> > > >> > All have npatterns = 2, nelts_per_pattern = 3.
> > > >> >
> > > >> > With above mask,
> > > >> > Pattern {0, ...} selects arg0[0], ie {1, ...}
> > > >> > Pattern {0, 1, 2, ...} selects arg0[0], arg0[1], arg0[2], ie {1, 11, 2, ...}
> > > >> > While arg0[0] and arg0[2] belong to same pattern, arg0[1] belongs to different
> > > >> > pattern in arg0.
> > > >> > The result is:
> > > >> > res = {1, 1, 1, 11, 1, 2, ...}
> > > >> > In this case, res's 2nd pattern {1, 11, 2, ...} is encoded with:
> > > >> > with a0 = 1, a1 = 11, S = -9.
> > > >> > Is that expected tho ? It seems to create a new encoding which
> > > >> > wasn't present in the input vector. For instance, the next elem in
> > > >> > sequence would be -7,
> > > >> > which is not present originally in arg0.
> > > >>
> > > >> Yeah, you're right, sorry.  Going back to:
> > > >>
> > > >> (2) The explicit encoding can be used to produce a sequence of N*Ex*Px
> > > >>     elements for any integer N.  This extended sequence can be reencoded
> > > >>     as having N*Px patterns, with Ex staying the same.
> > > >>
> > > >> I guess we need to pick an N for the selector such that each new
> > > >> selector pattern (each one out of the N*Px patterns) selects from
> > > >> the *same pattern* of the same data input.
> > > >>
> > > >> So if a particular pattern in the selector has a step S, and the data
> > > >> input it selects from has Pi patterns, N*S must be a multiple of Pi.
> > > >> N must be a multiple of least_common_multiple(S,Pi)/S.
> > > >>
> > > >> I think that means that the total number of patterns in the result
> > > >> (Pr from previous messages) can safely be:
> > > >>
> > > >>   Ps * least_common_multiple(
> > > >>     least_common_multiple(S[1], P[input(1)]) / S[1],
> > > >>     ...
> > > >>     least_common_multiple(S[Ps], P[input(Ps)]) / S[Ps]
> > > >>   )
> > > >>
> > > >> where:
> > > >>
> > > >>   Ps = the number of patterns in the selector
> > > >>   S[I] = the step for selector pattern I (I being 1-based)
> > > >>   input(I) = the data input selected by selector pattern I (I being 1-based)
> > > >>   P[I] = the number of patterns in data input I
> > > >>
> > > >> That's getting quite complicated :-)  If we allow arbitrary P[...]
> > > >> and S[...] then it could also get large.  Perhaps we should finally
> > > >> give up on the general case and limit this to power-of-2 patterns and
> > > >> power-of-2 steps, so that least_common_multiple becomes MAX.  Maybe that
> > > >> simplifies other things as well.
> > > >>
> > > >> What do you think?
> > > > Hi Richard,
> > > > Thanks for the suggestions. Yeah I suppose we can initially add support for
> > > > power-of-2 patterns and power-of-2 steps and try to generalize it in
> > > > follow up patches if possible.
> > > >
> > > > Sorry if this sounds like a silly ques -- if we are going to have
> > > > pattern in selector, select *same pattern from same input vector*,
> > > > instead of re-encoding the selector to have N * Ps patterns, would it
> > > > make sense for elements in selector to denote pattern number itself
> > > > instead of element index
> > > > if input vectors are VLA ?
> > > >
> > > > For eg:
> > > > op0 = {1, 2, 3, 4, 1, 2, 3, 5, 1, 2, 3, 6, ...}
> > > > op1 = {...}
> > > > with npatterns == 4, nelts_per_pattern == 3,
> > > > sel = {0, 3} should pick pattern 0 and pattern 3 from op0,
> > > > so, res = {1, 4, 1, 5, 1, 6, ...}
> > > > Not sure if this is correct tho.
> > >
> > > This wouldn't allow us to represent things like a "duplicate one
> > > element", or "copy the leading N elements from the first input and
> > > the other elements from elements N+ of the second input", which we
> > > can with the current scheme.
> > >
> > > The restriction about each (unwound) selector pattern selecting from the
> > > same input pattern only applies to case where the selector pattern is
> > > stepped (and only applies to the stepped part of the pattern, not the
> > > leading element).  The restriction is also local to this code; it
> > > doesn't make other VEC_PERM_EXPRs invalid.
> > Hi Richard,
> > Thanks for the clarifications.
> > Just to clarify your approach with an eg:
> > Let selected input vector be:
> > arg0: {a0, b0, c0, d0,
> >           a0 + S, b0 + S, c0 + S, d0 + S,
> >           a0 + 2S, b0 + 2S, c0 + 2S, dd + 2S, ...}
> > where arg0 has npatterns = 4, and nelts_per_pattern = 3.
> >
> > Let sel = {0, 0, 1, 2, 2, 4, ...}
> > where sel_npatterns = 2 and sel_nelts_per_pattern = 3
> >
> > So, the first pattern in sel:
> > p1: {0, 1, 2, ...} which will select {a0, b0, c0, ...}
> > which would be incorrect, since they belong to different patterns in arg0.
> > So to select elements from same pattern in arg0, we need to divide p1
> > into at least N1 = P_arg0 / S0 = 4 distinct patterns.
> >
> > Similarly for second pattern in sel:
> > p2: {0, 2, 4, ...}, we need to divide it into
> > at least N2 = P_arg0 / S1 = 2 distinct patterns.
> >
> > Select N = max(N1, N2) = 4
> > So, the selector will be extended to N * Ps * Es = 4 * 2 * 3 == 24 elements,
> > and will be re-encoded with N*Ps = 8 patterns:
> >
> > re-encoded sel:
> > {a0, b0, c0, d0, a0 + S, b0 + S, c0 + S, d0 + S,
> > a0 + 2S, b0 + 2S, c0 + 2S, d0 + 2S, a0 + 3S, b0 + 3S, c0 + 3S, d0 + 3S,
> > a0 + 4S, b0 + 4S, c0 + 4s, d0 + 4S, a0 + 5S, b0 + 5S, c0 + 5S, d0 + 5S,
> > ...}
> >
> > with 8 patterns,
> > p1: {a0, a0 + 2S, a0 + 4S, ...}
> > p2: {b0, b0 + 2S, b0 + 4S, ...}
> > ...
> > which select elements from same pattern from same input vector.
> > Does this look correct ?
> >
> > For feasibility, we can check initially that sel_npatterns, arg0_npatterns,
> > arg1_npatterns are powers of 2 and for each stepped pattern,
> > it's stepped size S is a power of 2. I suppose this will be sufficient
> > to ensure that sel can be re-encoded with N*Ps npatterns
> > such that each new pattern selects elements from same pattern
> > of the input vector ?
> >
> > Then compute N:
> > N = 1;
> > for (every pattern p in sel)
> >   {
> >      op = corresponding input vector for pattern;
> >      S = step_size (p);
> >      N_pattern = max (S, npatterns (op)) / S;
> >      N = max(N, N_pattern)
> >   }
> >
> > and re-encode selector with N*Ps patterns.
> > I guess rest of the patch will mostly stay the same.
> Hi,
> I have attached a POC patch based on the above approach.
> For the above eg:
> arg0 = {1, 11, 2, 12, 3, 13, ...} // npatterns = 2, nelts_per_pattern = 3,
> and
> sel = {0, 0, 0, 1, 0, 2, ...}
> with sel_npatterns == 2 and sel_nelts_per_pattern == 3.
>
> For pattern, {0, 1, 2, ...} it will select elements from different
> patterns from arg0, which is incorrect.
> So we choose N = P1/S = 2/1 = 2, where P1 is number of elements in arg0.
> So re-encoded sel = { 0, 0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, ...}
> with following patterns:
> p1 = { 0, ... }
> p2 = { 0, 2, 4, ... }
> p3 = { 0, ... }
> p4 = { 1, 3, 5, ... }
> which should be correct since each element from the respective
> patterns in sel chooses
> elements from same pattern from arg0.
> So, res = { 1, 1, 1, 11, 1, 2, 1, 12, 1, 3, 1, 13, ... }
> Does this look correct ?
Hi Richard,
ping https://gcc.gnu.org/pipermail/gcc-patches/2022-November/606850.html

Thanks,
Prathamesh
>
> Thanks,
> Prathamesh
>
> >
> > Thanks,
> > Prathamesh
> >
> > >
> > > Thanks,
> > > Richard
> > >
> > > >
> > > > Thanks,
> > > > Prathamesh
> > > >>
> > > >> > I suppose it's fine since if the user defines mask to have pattern {0,
> > > >> > 1, 2, ...}
> > > >> > they intended result to have pattern with above encoding.
> > > >> > Just wanted to confirm if this is correct ?
> > > >> >
> > > >> > 2] Could you please suggest a test-case for S < 0 ?
> > > >> > I am not able to come up with one :/
> > > >>
> > > >> svrev is one way of creating negative steps.
> > > >>
> > > >> Thanks,
> > > >> Richard
> > > >>
> > > >> >
> > > >> > Thanks,
> > > >> > Prathamesh
> > > >> >>
> > > >> >> > which is an interleaving of the two patterns:
> > > >> >> >
> > > >> >> >   { 0, 2, 4, ... }                  a0 = 0, a1 = 2, S = 2
> > > >> >> >   { 2 + 2x, 4 + 2x, 6 + 2x }        a0 = 2 + 2x, a1 = 4 + 2x, S = 2