From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-io1-xd31.google.com (mail-io1-xd31.google.com [IPv6:2607:f8b0:4864:20::d31]) by sourceware.org (Postfix) with ESMTPS id 5CA8F385D0C0 for ; Fri, 28 Oct 2022 14:46:44 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5CA8F385D0C0 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org Received: by mail-io1-xd31.google.com with SMTP id h206so1247348iof.10 for ; Fri, 28 Oct 2022 07:46:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=SgiolAB3E5i/PukFkuFIaNnCK+KkGJI2jpHXGJRt7uE=; b=n21dLsQi0M2+CcWP1bvN9dohuR+rtTUoiTqSSwodgIMMCOMqV8lfa6YRB6cGe+IwTM OZtmOKcYfsa9LvQS1MtgMo1rIEho9zI8PT9Hn32vUEv9zoFNFQUmJ8u96GToHdbLVFww UnJaP9ZWULiAXR6pBkKJ99R+FuFf3PjNEOSI/utCQ98+OEvBTPa++k2dZpo+IJPUgTal GQy8AMvMslB2NLFEUTGdZQnxKqSPe/+ah5g4u4zdR3yIvPQPD5Qm2lbAT8tkS/4IPff6 RylG2+rrhT9mLaop26QZpAjD/kcWfpUO9xXIaZt7jGCHFA7QxUf1A3DwG6aUAjnlliYK akYA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=SgiolAB3E5i/PukFkuFIaNnCK+KkGJI2jpHXGJRt7uE=; b=gldYtiBN+puYt8Oezd9HWOW/d/DuNdOqz9I03WJoZbKzhnaSzWVnrqzkjSIdTPqm8C f1EslEIanpPXBetAGw8dwBXLsqTV2q9H9xrnagL3Jm54YGTJiBh9zRPvPbpJYMuJKVwU ueScfLFuC/Xm/MajZr3xtnHKH2U6Cl4htlPKtQ3BbwucKThQOAewvYlQ+jwPeKAHm1jq RTjCv4qpq7ajdbNcaZLq2sVN2NyPshwMxZTPpyY+iAzE/lSoUEPdukoDSQX2g+V61gg/ bhnTgrrxUYLCpej4g4p/hX0rsBYH2lWQONNxukzfhJPnRMveEAZNDWF7lgUNsqq740Hv ocTA== X-Gm-Message-State: ACrzQf0OLdlLcbMdfng5QvUXRPl5loa/leltRN4AgxxbV2AQhkuINKYv Q346dhsX6GlGUflYirJxa5APHb3+1Camn3dV6axVZQ== X-Google-Smtp-Source: AMsMyM4IAYVtb0Y2LqOTKbn1Fr/ne1DJaWj7qv4Ox7v+osFqtH+340INQFwItFEMW2CVFiVKneyd6tMx9tTQ5eubeI8= X-Received: by 2002:a05:6638:1186:b0:36f:ae2e:a396 with SMTP id f6-20020a056638118600b0036fae2ea396mr19615455jas.89.1666968403436; Fri, 28 Oct 2022 07:46:43 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Prathamesh Kulkarni Date: Fri, 28 Oct 2022 20:16:07 +0530 Message-ID: Subject: Re: Extend fold_vec_perm to fold VEC_PERM_EXPR in VLA manner To: Prathamesh Kulkarni , gcc Patches , Richard Biener , richard.sandiford@arm.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-3.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Wed, 26 Oct 2022 at 21:07, Richard Sandiford wrote: > > Sorry for the slow response. I wanted to find some time to think > about this a bit more. > > Prathamesh Kulkarni writes: > > On Fri, 30 Sept 2022 at 21:38, Richard Sandiford > > wrote: > >> > >> Richard Sandiford via Gcc-patches writes: > >> > Prathamesh Kulkarni 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. 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