From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x229.google.com (mail-lj1-x229.google.com [IPv6:2a00:1450:4864:20::229]) by sourceware.org (Postfix) with ESMTPS id E2505385B53E for ; Mon, 28 Nov 2022 11:45:13 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E2505385B53E 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-lj1-x229.google.com with SMTP id h5so8588376ljk.11 for ; Mon, 28 Nov 2022 03:45:13 -0800 (PST) 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=NpmWqVUscSnE7p3sHu2mgmbUUM/+/a+42f+LFI4nTEc=; b=sfxAX8W9up2QR1OYkGIMYc0njWz6p2feNXxyjbuV8RLh44ANroc5KRc1sYAarFW3Q+ 5ulERfBv9PtH7xNZnLMaZMVYWQVsUF3HqdHLAvdu3VF5ahtMKN5NJAq0k64dF9UCDNVH X4yuhg98gGo7tUeC8OZkztVbiWIDLYlcWusoyrCnG+QJBPZDxmnDOsw8HhVsj6kSOwNB Ijl4uWloQetT+3/L5MfP97QwY4P1q9bflpsB0XceLdePRMkRn8vd2jqj8tI9tVtstohx kS0YKAf12qUdCCy+UUBMYf/6fCH5R9Hdc6Tf1W/WOhHiFguyfLeoFWVl1qQkpX+xcjLS TWxQ== 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=NpmWqVUscSnE7p3sHu2mgmbUUM/+/a+42f+LFI4nTEc=; b=5hNA+jF70uM0QmDU9UjfJ70mS//gIYWHv2QBPCBKwVJ9UDOLSgdQZ3rYx0UBqFbpc4 DUN61C5/8W3g+kXA7tIBbTkONPKiZYsV0CNJ0Xzlmz2rXM85frpevpqYrxhQFj0Zvpkp Uf5ilSWBKAJUGt7yhAHokCyLIzf11BPtiQIZyd6xxnnMB5slBQIqVyh4AGssT+wLtg1T 0cQDQiFRjqM361xod8a0a8Cr7Ro+lUJxRxHy9zdXhd2u+OPjy8N/acwqCb1Kd4XsSNiu st6WWF9aKuTaDVzRu+0iFFZicC6XQIwNceCXzjqqA5ixAeZ1uNJT/gehPJG3w4PKtEOT ZwkA== X-Gm-Message-State: ANoB5plIv+lmkiTe3O8Y+YUW13SHQPkqD/3yTAmb5bbSJM+bZg8+6Ekr Ipg2lwceMy43eaw5CAE6oz0jIXHOpfdGcRUQXGXIHw== X-Google-Smtp-Source: AA0mqf6emY+Maq5E/yqKbHf4vjP4JFn/U4QMpPBxTxpef0R4Mobw/ytZheq9lEei4R8q0oAffJbrsvKgfyneyTDXGDw= X-Received: by 2002:a05:651c:10c4:b0:277:21c8:aac1 with SMTP id l4-20020a05651c10c400b0027721c8aac1mr11998117ljn.430.1669635912296; Mon, 28 Nov 2022 03:45:12 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Prathamesh Kulkarni Date: Mon, 28 Nov 2022 17:14:35 +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=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,KAM_SHORT,RCVD_IN_DNSWL_NONE,SCC_5_SHORT_WORD_LINES,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=no 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 Mon, 21 Nov 2022 at 14:37, Prathamesh Kulkarni wrote: > > On Fri, 4 Nov 2022 at 14:00, Prathamesh Kulkarni > wrote: > > > > On Mon, 31 Oct 2022 at 15:27, Richard Sandiford > > wrote: > > > > > > Prathamesh Kulkarni writes: > > > > 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. > > > > > > 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