From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x132.google.com (mail-lf1-x132.google.com [IPv6:2a00:1450:4864:20::132]) by sourceware.org (Postfix) with ESMTPS id 95D69385515F for ; Tue, 29 Nov 2022 10:12:29 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 95D69385515F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=vrull.eu Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=vrull.eu Received: by mail-lf1-x132.google.com with SMTP id b3so21728212lfv.2 for ; Tue, 29 Nov 2022 02:12:29 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=vrull.eu; s=google; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=RBldGlx0kXbTBD6wh4w8fr2N+uP5++er9YoPJIHTumc=; b=VEmHYKNgArDbvgNbn9+6PKWmSOlT3TbGGl3l6UO+i+CwWn5IN3bGJvvuyKhe6mFvG5 Vy5NcACPQtcLsU22bX1cKCH3uFglvLj1JAMr5zuTEyq5PqjI21khORYNKS11Him78Ywv /D2k5Vby2jPiFuAeYrMWgx+fL9mF7+1ERqUU6NN6udAj+TOvZc0arXcsT4/ccd7/gpre nHbY1HPPkEuWQrS4A1Dz9OkB624HEz5YyENqJb4KxlVQYjB3rz+aUh8ZO+nMSukBTKUb jsOpTNC2xyJHJjbjKpmnY0jsZL6vU+RNf7HmxV1O1e4kgmm6hOYnvQVERc1sOiNxwah1 qfkA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:cc: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=RBldGlx0kXbTBD6wh4w8fr2N+uP5++er9YoPJIHTumc=; b=0W8Xfs0bK3R+rTzCZxATnmUP7uQipSghn1yxOX3ycsI6PjQbKSaoVoavgzTg8jeo83 3IENQBU06quPaPvDVjoHULIMnLmrBbVmZJtofJKd5ishVHnLijGECnrOJQAE2Y4wAiW/ ww6JE4FIboFNfWdiVnmflP2Eg3HpkeaOybfEjWWkjgV7T04CrowzEZ8W3rRNBakCrBzB BZ7rcxFmqG5zlqQrDF9bZPwZiDm8AtjvyJX6o1KG2We3VL1DtzzyzeZOmmhv/cYO6zMU Is/G1BuyEJHl4dLRU8TjeBi3uaxTv2PtbZNRQw3Uw7AcEa2Si3pTD6stDne84waCFNpo fA8w== X-Gm-Message-State: ANoB5pmzzTzUxeNX9PxfDD7A/9GkYPYh5jCFeDj4PEEFLCWvDN27lEbU NJZcvZpJqKH4lv5XsHTj4eTUgEiXvYmNHAK9foTohw== X-Google-Smtp-Source: AA0mqf7VdeVPEBQT9yTaB4kVN0sZjhHLPaqWzh93rHnO8CjBsLp19B2QdUDMHurFLBHZhrNoGjkVTdTXIbGQmAaJ3Aw= X-Received: by 2002:a05:6512:238d:b0:4ad:5f5c:2b31 with SMTP id c13-20020a056512238d00b004ad5f5c2b31mr17827847lfv.422.1669716748054; Tue, 29 Nov 2022 02:12:28 -0800 (PST) MIME-Version: 1.0 References: <20220813095843.1452308-1-manolis.tsamis@vrull.eu> In-Reply-To: From: Manolis Tsamis Date: Tue, 29 Nov 2022 12:11:51 +0200 Message-ID: Subject: Re: [PATCH] Add pattern to convert vector shift + bitwise and + multiply to vector compare in some cases. To: Tamar Christina Cc: Philipp Tomsich , Richard Biener , GCC Patches , "jiangning.liu@amperecomputing.com" Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-8.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,JMQ_SPF_NEUTRAL,KAM_SHORT,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: Hi all, based on everyone's comments I have sent a v2 of this patch that can be found here https://gcc.gnu.org/pipermail/gcc-patches/2022-November/607472.html As per Richard's comments the pattern now uses vec_cond_expr instead and includes other fixes as requested. Also based on Tamar's suggestion I have made it work with poly_int instead = of aborting for VLA vectors. I would appreciate any further feedback for the new version. Manolis On Tue, Nov 22, 2022 at 12:57 PM Tamar Christina wrote: > > Hi, > > > -----Original Message----- > > From: Philipp Tomsich > > Sent: Tuesday, November 22, 2022 10:35 AM > > To: Tamar Christina > > Cc: Richard Biener ; mtsamis > > ; GCC Patches ; > > jiangning.liu@amperecomputing.com > > Subject: Re: [PATCH] Add pattern to convert vector shift + bitwise and = + > > multiply to vector compare in some cases. > > > > Richard & Tamar, > > > > On Fri, 26 Aug 2022 at 15:29, Tamar Christina > > wrote: > > > > > > > -----Original Message----- > > > > From: Gcc-patches > > > bounces+tamar.christina=3Darm.com@gcc.gnu.org> On Behalf Of Richard > > > > Biener via Gcc-patches > > > > Sent: Friday, August 26, 2022 10:08 AM > > > > To: mtsamis > > > > Cc: GCC Patches ; > > > > jiangning.liu@amperecomputing.com; Philipp Tomsich > > > > > > > > Subject: Re: [PATCH] Add pattern to convert vector shift + bitwise > > > > and + multiply to vector compare in some cases. > > > > > > > > On Sat, Aug 13, 2022 at 11:59 AM mtsamis > > wrote: > > > > > > > > > > When using SWAR (SIMD in a register) techniques a comparison > > > > > operation within such a register can be made by using a > > > > > combination of shifts, bitwise and and multiplication. If code > > > > > using this scheme is vectorized then there is potential to replac= e > > > > > all these operations with a single vector comparison, by > > > > > reinterpreting the vector types to > > > > match the width of the SWAR register. > > > > > > > > > > For example, for the test function packed_cmp_16_32, the original > > > > generated code is: > > > > > > > > > > ldr q0, [x0] > > > > > add w1, w1, 1 > > > > > ushr v0.4s, v0.4s, 15 > > > > > and v0.16b, v0.16b, v2.16b > > > > > shl v1.4s, v0.4s, 16 > > > > > sub v0.4s, v1.4s, v0.4s > > > > > str q0, [x0], 16 > > > > > cmp w2, w1 > > > > > bhi .L20 > > > > > > > > > > with this pattern the above can be optimized to: > > > > > > > > > > ldr q0, [x0] > > > > > add w1, w1, 1 > > > > > cmlt v0.8h, v0.8h, #0 > > > > > str q0, [x0], 16 > > > > > cmp w2, w1 > > > > > bhi .L20 > > > > > > > > > > The effect is similar for x86-64. > > > > > > > > > > gcc/ChangeLog: > > > > > > > > > > * match.pd: Simplify vector shift + bit_and + multiply in= some cases. > > > > > > > > > > gcc/testsuite/ChangeLog: > > > > > > > > > > * gcc.target/aarch64/swar_to_vec_cmp.c: New test. > > > > > > > > > > Signed-off-by: mtsamis > > > > > --- > > > > > gcc/match.pd | 57 +++++++++++++= ++ > > > > > .../gcc.target/aarch64/swar_to_vec_cmp.c | 72 > > > > +++++++++++++++++++ > > > > > 2 files changed, 129 insertions(+) create mode 100644 > > > > > gcc/testsuite/gcc.target/aarch64/swar_to_vec_cmp.c > > > > > > > > > > diff --git a/gcc/match.pd b/gcc/match.pd index > > > > > 8bbc0dbd5cd..5c768a94846 100644 > > > > > --- a/gcc/match.pd > > > > > +++ b/gcc/match.pd > > > > > @@ -301,6 +301,63 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > > > > > (view_convert (bit_and:itype (view_convert @0) > > > > > (ne @1 { build_zero_cst (type); > > > > > }))))))) > > > > > > > > > > +/* In SWAR (SIMD in a register) code a comparison of packed data= can > > > > > + be consturcted with a particular combination of shift, bitwis= e and, > > > > > + and multiplication by constants. If that code is vectorized = we can > > > > > + convert this pattern into a more efficient vector comparison. > > > > > +*/ (simplify (mult (bit_and (rshift @0 @1) @2) @3) > > > > > > > > You should restrict the pattern a bit more, below you use > > > > uniform_integer_cst_p and also require a vector type thus > > > > > > > > (simplify > > > > (mult (bit_and (rshift @0 VECTOR_CST@1) VECTOR_CST@2) > > > > VECTOR_CST@3) > > > > > > > > > > > > > + (with { > > > > > + tree op_type =3D TREE_TYPE (@0); > > > > > > > > that's the same as 'type' which is already available. > > > > > > > > > + tree rshift_cst =3D NULL_TREE; > > > > > + tree bit_and_cst =3D NULL_TREE; > > > > > + tree mult_cst =3D NULL_TREE; > > > > > + } > > > > > + /* Make sure we're working with vectors and uniform vector > > > > > + constants. */ (if (VECTOR_TYPE_P (op_type) > > > > > + && (rshift_cst =3D uniform_integer_cst_p (@1)) > > > > > + && (bit_and_cst =3D uniform_integer_cst_p (@2)) > > > > > + && (mult_cst =3D uniform_integer_cst_p (@3))) > > > > > + /* Compute what constants would be needed for this to > > > > > + represent a > > > > packed > > > > > + comparison based on the shift amount denoted by RSHIFT_CST= . */ > > > > > + (with { > > > > > + HOST_WIDE_INT vec_elem_bits =3D vector_element_bits (op_typ= e); > > > > > + HOST_WIDE_INT vec_nelts =3D TYPE_VECTOR_SUBPARTS > > > > > + (op_type).to_constant (); > > > > > > > > you need to check that this isn't a VLA vector operation. > > > > > > Seems like this pattern should be applicable to VLA as well no? > > > So could we not keep vec_nelts as a poly and just use exact_div Below > > > in the division? The pattern is only valid if cmp_bits_i is a multipl= e > > > of vec_elem_bits anyway. The build_vector_* should then do the right > > > thing. > > > > Seems like we never agreed on what should go into the next version. > > Am I right in assuming that applicability to VLA is ok and that we shou= ld > > primarily focus on addressing the below comments for v2? > > I don't think there was a disagreement here per say. Richard's point was= that in the > current form the patch is unsafe for VLA, as to_constant () would fail. = That is > if the idea was not to support VLA then this needs a check, or use the ch= ecking > version of to_constant. > > I was saying that we don=E2=80=99t need to make this ignore VLA, that the= pattern should > be applicable for VLA as well. That is to say, properly handling VLA wou= ld address > Richard's concerns as well. > > Cheers, > Tamar > > > > > Cheers, > > Philipp. > > > > > > > > > > > + HOST_WIDE_INT vec_bits =3D vec_elem_bits * vec_nelts; > > > > > + > > > > > + unsigned HOST_WIDE_INT cmp_bits_i, bit_and_i, mult_i; > > > > > + unsigned HOST_WIDE_INT target_mult_i, target_bit_and_i; > > > > > + cmp_bits_i =3D tree_to_uhwi (rshift_cst) + 1; > > > > > > > > and that the rshift_cst and others actually fit an uhwi. > > > > > > > > > + target_mult_i =3D (HOST_WIDE_INT_1U << cmp_bits_i) - 1; > > > > > + > > > > > + mult_i =3D tree_to_uhwi (mult_cst); > > > > > + bit_and_i =3D tree_to_uhwi (bit_and_cst); > > > > > + target_bit_and_i =3D 0; > > > > > + > > > > > + for (unsigned i =3D 0; i < vec_elem_bits / cmp_bits_i; i++) > > > > > + target_bit_and_i =3D (target_bit_and_i << cmp_bits_i) | 1= U; > > > > > > > > it would be nice to have a comment on what this actually does ... > > > > > > > > > + } > > > > > + (if ((exact_log2 (cmp_bits_i)) >=3D 0 > > > > > + && cmp_bits_i < HOST_BITS_PER_WIDE_INT > > > > > + && vec_elem_bits <=3D HOST_BITS_PER_WIDE_INT > > > > > + && tree_fits_uhwi_p (rshift_cst) > > > > > + && tree_fits_uhwi_p (mult_cst) > > > > > + && tree_fits_uhwi_p (bit_and_cst) > > > > > + && target_mult_i =3D=3D mult_i > > > > > + && target_bit_and_i =3D=3D bit_and_i) > > > > > + /* Compute the vector shape for the comparison and check if > > > > > + the > > > > target is > > > > > + able to expand the comparison with that type. */ > > > > > + (with { > > > > > + tree bool_type =3D build_nonstandard_boolean_type (cmp_bi= ts_i); > > > > > + int vector_type_nelts =3D vec_bits / cmp_bits_i; > > > > > + tree vector_type =3D build_vector_type (bool_type, > > > > > + vector_type_nelts); > > > > > > > > why do you build a bool vector type here and then ... > > > > > > > > > + tree zeros =3D build_zero_cst (vector_type); > > > > > + tree mask_type =3D truth_type_for (vector_type); > > > > > > > > ... its truth type? Note both might not be actually supported by > > > > the target and thus receive BLKmode or an integer mode. The latter > > > > is a problem for expand_vec_cmp_expr_p as that might pick up a patt= ern > > not suitable > > > > here. Also note that truth_type_for can result in a mask mode, ak= a > > > > QImode with AVX512 or some VnBImode on other archs - those are not > > > > OK to be simply view_converted back to op_type. In general a vecto= r > > > > compare operation yields a mask and you can convert that to a -1/0 > > > > value using a vec_cond_expr. I think we have a pattern that can > > > > then properly simplify the case where this can be expressed as a > > > > view_convert, but of course you then also need to check for > > vec_cond_expr support. > > > > > > > > I would suggest you make 'vector_type' an integer element type (tha= t > > > > also properly specifies the sign of the comparison!) and check you > > > > end up with a vector mode and the mode of the mask_type agrees with > > > > that if you don't want to go the vec_cond_expr route. > > > > > > > > > > > > > + } > > > > > + (if (expand_vec_cmp_expr_p (vector_type, mask_type, LT_EXP= R)) > > > > > + (view_convert:op_type (lt:mask_type > > > > > + (view_convert:vector_type > > > > @0) > > > > > + { zeros; }))))))))) > > > > > + > > > > > (for cmp (gt ge lt le) > > > > > outp (convert convert negate negate) > > > > > outn (negate negate convert convert) diff --git > > > > > a/gcc/testsuite/gcc.target/aarch64/swar_to_vec_cmp.c > > > > > b/gcc/testsuite/gcc.target/aarch64/swar_to_vec_cmp.c > > > > > new file mode 100644 > > > > > index 00000000000..26f9ad9ef28 > > > > > --- /dev/null > > > > > +++ b/gcc/testsuite/gcc.target/aarch64/swar_to_vec_cmp.c > > > > > @@ -0,0 +1,72 @@ > > > > > +/* { dg-do compile } */ > > > > > +/* { dg-options "-O2 -ftree-vectorize" } */ > > > > > + > > > > > +typedef unsigned char uint8_t; > > > > > +typedef unsigned short uint16_t; > > > > > +typedef unsigned int uint32_t; > > > > > + > > > > > +/* 8-bit SWAR tests. */ > > > > > + > > > > > +static uint8_t packed_cmp_8_8(uint8_t a) { > > > > > + return ((a >> 7) & 0x1U) * 0xffU; } > > > > > + > > > > > +/* 16-bit SWAR tests. */ > > > > > + > > > > > +static uint16_t packed_cmp_8_16(uint16_t a) { > > > > > + return ((a >> 7) & 0x101U) * 0xffU; } > > > > > + > > > > > +static uint16_t packed_cmp_16_16(uint16_t a) { > > > > > + return ((a >> 15) & 0x1U) * 0xffffU; } > > > > > + > > > > > +/* 32-bit SWAR tests. */ > > > > > + > > > > > +static uint32_t packed_cmp_8_32(uint32_t a) { > > > > > + return ((a >> 7) & 0x1010101U) * 0xffU; } > > > > > + > > > > > +static uint32_t packed_cmp_16_32(uint32_t a) { > > > > > + return ((a >> 15) & 0x10001U) * 0xffffU; } > > > > > + > > > > > +static uint32_t packed_cmp_32_32(uint32_t a) { > > > > > + return ((a >> 31) & 0x1U) * 0xffffffffU; } > > > > > + > > > > > +/* Driver function to test the vectorized code generated for the > > different > > > > > + packed_cmp variants. */ > > > > > + > > > > > +#define VECTORIZED_PACKED_CMP(T, FUNC) \ > > > > > + void vectorized_cmp_##FUNC(T* a, int n) \ > > > > > + { \ > > > > > + n =3D (n / 32) * 32; \ > > > > > + for(int i =3D 0; i < n; i +=3D 4) \ > > > > > + { \ > > > > > + a[i + 0] =3D FUNC(a[i + 0]); \ > > > > > + a[i + 1] =3D FUNC(a[i + 1]); \ > > > > > + a[i + 2] =3D FUNC(a[i + 2]); \ > > > > > + a[i + 3] =3D FUNC(a[i + 3]); \ > > > > > + } \ > > > > > + } > > > > > + > > > > > +VECTORIZED_PACKED_CMP(uint8_t, packed_cmp_8_8); > > > > > + > > > > > +VECTORIZED_PACKED_CMP(uint16_t, packed_cmp_8_16); > > > > > +VECTORIZED_PACKED_CMP(uint16_t, packed_cmp_16_16); > > > > > + > > > > > +VECTORIZED_PACKED_CMP(uint32_t, packed_cmp_8_32); > > > > > +VECTORIZED_PACKED_CMP(uint32_t, packed_cmp_16_32); > > > > > +VECTORIZED_PACKED_CMP(uint32_t, packed_cmp_32_32); > > > > > + > > > > > +/* { dg-final { scan-assembler {\tcmlt\t} } } */ > > > > > +/* { dg-final { scan-assembler-not {\tushr\t} } } */ > > > > > +/* { dg-final { scan-assembler-not {\tshl\t} } } */ > > > > > +/* { dg-final { scan-assembler-not {\tmul\t} } } */ > > > > > -- > > > > > 2.34.1 > > > > >