From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pg1-x52d.google.com (mail-pg1-x52d.google.com [IPv6:2607:f8b0:4864:20::52d]) by sourceware.org (Postfix) with ESMTPS id BFB873858D37 for ; Thu, 18 Aug 2022 02:08:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org BFB873858D37 Received: by mail-pg1-x52d.google.com with SMTP id q16so190422pgq.6 for ; Wed, 17 Aug 2022 19:08:51 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc; bh=0Gs3Mezkxo23VUCT1gL6SbImYJRGZ4cn2+qGypsPKMo=; b=7OQWJb7esjq4BhRiMCjYWPvpmenenhvlJS5wFBss40ImHlgBvKP7S1petJUW/r/wav 6m+nPD/QqsVZToVfnhhYubNwrQ64PhUd6Y6yOclP7INCTiutgzS117uTS5NW/L8OZJSn cNk3XIpmeN44Rv2XghuqMPw9B3Alk64a2QAPcpniWeHfa9emGg+5kY7Huoq/cEtCjf8c 9+CGGlfW5mS9o8mt4KV3XLcGRzM/fVqM2ok+9nguNG1q/jltMskqcoUJPRh4tUAPy6u9 ugCpBXiNQVXXADKAM2p9IjxTL/yZNkfDeX3LYCTMIHyc8JI2FUPkaBzBdd+okbq449GD b07Q== X-Gm-Message-State: ACgBeo1vJeOxZXdz87MARutmBpU3Dr2CZcunOY8OAFbXlg2dEiDvkAJb L9D7kNhU1+NIgWG537YpdsHXJ7724WX4VX4yAdU= X-Google-Smtp-Source: AA6agR5XWac4plxZW3Vsk8P7l0ZpXaK2krCc6jNoKbaj7oMhzPnDkKqVM4tpFH0R+cUDTkT1mpGAHntTzc0oM9/8ypo= X-Received: by 2002:a05:6a00:80b:b0:52e:c38f:f2c9 with SMTP id m11-20020a056a00080b00b0052ec38ff2c9mr914628pfk.66.1660788530506; Wed, 17 Aug 2022 19:08:50 -0700 (PDT) MIME-Version: 1.0 References: <20220813095843.1452308-1-manolis.tsamis@vrull.eu> In-Reply-To: <20220813095843.1452308-1-manolis.tsamis@vrull.eu> From: Andrew Pinski Date: Wed, 17 Aug 2022 19:08:38 -0700 Message-ID: Subject: Re: [PATCH] Add pattern to convert vector shift + bitwise and + multiply to vector compare in some cases. To: mtsamis Cc: gcc-patches@gcc.gnu.org, philipp.tomsich@vrull.eu, jiangning.liu@amperecomputing.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-7.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 18 Aug 2022 02:08:53 -0000 On Sat, Aug 13, 2022 at 2: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 replace 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, bitwise 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) > + (with { > + tree op_type = TREE_TYPE (@0); > + tree rshift_cst = NULL_TREE; > + tree bit_and_cst = NULL_TREE; > + tree mult_cst = NULL_TREE; > + } > + /* Make sure we're working with vectors and uniform vector constants. */ > + (if (VECTOR_TYPE_P (op_type) I think you can use type here and don't need op_type. Maybe change this to: (simplify (mult (bit_and (rshift @0 uniform_integer_cst_p@1) uniform_integer_cst_p@2) uniform_integer_cst_p@3) (if (VECTOR_TYPE_P (type)) (with { tree rshift_cst = uniform_integer_cst_p (@1); tree bit_and_cst = uniform_integer_cst_p (@2); tree mult_cst = uniform_integer_cst_p (@3); } ... Similar to the patterns under "Simplifications of comparisons". Thanks, Andrew Pinski > + && (rshift_cst = uniform_integer_cst_p (@1)) > + && (bit_and_cst = uniform_integer_cst_p (@2)) > + && (mult_cst = 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 = vector_element_bits (op_type); > + HOST_WIDE_INT vec_nelts = TYPE_VECTOR_SUBPARTS (op_type).to_constant (); > + HOST_WIDE_INT vec_bits = 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 = tree_to_uhwi (rshift_cst) + 1; > + target_mult_i = (HOST_WIDE_INT_1U << cmp_bits_i) - 1; > + > + mult_i = tree_to_uhwi (mult_cst); > + bit_and_i = tree_to_uhwi (bit_and_cst); > + target_bit_and_i = 0; > + > + for (unsigned i = 0; i < vec_elem_bits / cmp_bits_i; i++) > + target_bit_and_i = (target_bit_and_i << cmp_bits_i) | 1U; > + } > + (if ((exact_log2 (cmp_bits_i)) >= 0 > + && cmp_bits_i < HOST_BITS_PER_WIDE_INT > + && vec_elem_bits <= 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 == mult_i > + && target_bit_and_i == 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 = build_nonstandard_boolean_type (cmp_bits_i); > + int vector_type_nelts = vec_bits / cmp_bits_i; > + tree vector_type = build_vector_type (bool_type, vector_type_nelts); > + tree zeros = build_zero_cst (vector_type); > + tree mask_type = truth_type_for (vector_type); > + } > + (if (expand_vec_cmp_expr_p (vector_type, mask_type, LT_EXPR)) > + (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 = (n / 32) * 32; \ > + for(int i = 0; i < n; i += 4) \ > + { \ > + a[i + 0] = FUNC(a[i + 0]); \ > + a[i + 1] = FUNC(a[i + 1]); \ > + a[i + 2] = FUNC(a[i + 2]); \ > + a[i + 3] = 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 >