From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x12d.google.com (mail-lf1-x12d.google.com [IPv6:2a00:1450:4864:20::12d]) by sourceware.org (Postfix) with ESMTPS id 32C133858D1E for ; Tue, 29 Nov 2022 10:05:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 32C133858D1E 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-x12d.google.com with SMTP id u27so10669468lfc.9 for ; Tue, 29 Nov 2022 02:05:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=vrull.eu; s=google; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=+0UXXzEKT7dDqVeNJ1MZiIf66Z9BKaRCcPTFoYbTrfo=; b=bYwIepM+f78q91SajRw8EuQMFXG0gmIurtWDvMz6jhmHwkICR/J6pybu/sqgbMSKXx kEUI2ZnP3zcbtUABBd9a9JD7YMefxdtX42/rcIGyUgC2wkGewObbglVVUTi56oHMgQHb oSiUtlYT2sUTbmbhvx7r+6KIhChzAckEXBOQ0pctmwo+AvSicUbnBVSCJyYirBq0InSN sd9dZFDzgwKDsRPkx845uNu7OV2ViuhoeZvF8YGt3xz+aXGr6yJ1u8Pmk2iBDdhE7Jpq amHGDDHVQVcuoro8NXfyCCuII//Lx1IIGqUZp/AuO1d7ULeKZNl+Y01ABucDFUB/GugA JWMA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=+0UXXzEKT7dDqVeNJ1MZiIf66Z9BKaRCcPTFoYbTrfo=; b=mPDW0hv4eqDC6EueZMPS3yEZy+6zFOe2AogJ9ezTudO9NqLq/BPfc7YVF0M11xotZd lxeWr5sexiZRP0G/RR37gNTbgvlX70t3boNy06a3JIE9MPY9D1CbPeMVRzfdGnDZk6eV V1R9lduiWHbCs4m0xyH1noI0MHZakEkgEYPA93ZjccYWOIhQsM4YqQEnxIqr71W8ucej W8+5liYr34l/q2/JxJwOye9VPZ8THsX1/tChafJUaxQAlYxh/N7kXNJf1/u7n4GlpiGG MGa6ueDe1Bye9mewEQ1UymIlyZ3+uja+jfni9FTCN8mZZxMGilfeVFjL0sZPzqa26q9n 26Ag== X-Gm-Message-State: ANoB5pkaAvpAv7MTBfqXvk3k7jYpknD2mLVtUv8XAsZ3wwNJ9I7BqCSh 6jg6tgMIZLM5Gs6gpPVAKayduovL5vAuRDXc X-Google-Smtp-Source: AA0mqf7+4pk97TdYm6Q7Vh1j/wAkKSPKHBLx6n7f1ExNQaVruJLe+zbsFZ2mDTMWyp66DgXTEL/yyA== X-Received: by 2002:a19:8c50:0:b0:4b1:cbeb:c578 with SMTP id i16-20020a198c50000000b004b1cbebc578mr19333920lfj.86.1669716342753; Tue, 29 Nov 2022 02:05:42 -0800 (PST) Received: from helsinki-03.engr ([2a01:4f9:6b:2a47::2]) by smtp.gmail.com with ESMTPSA id m1-20020a056512114100b004972b0bb426sm2162829lfg.257.2022.11.29.02.05.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 29 Nov 2022 02:05:41 -0800 (PST) From: Manolis Tsamis To: gcc-patches@gcc.gnu.org Cc: Philipp Tomsich , Tamar Christina , Richard Biener , jiangning.liu@amperecomputing.com, Christoph Muellner , Manolis Tsamis Subject: [PATCH v2] Add pattern to convert vector shift + bitwise and + multiply to vector compare in some cases. Date: Tue, 29 Nov 2022 11:04:46 +0100 Message-Id: <20221129100446.3875697-1-manolis.tsamis@vrull.eu> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-11.4 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: 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. Signed-off-by: Manolis Tsamis 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. --- Changes in v2: - Changed pattern to use vec_cond_expr. - Changed pattern to work with VLA vector. - Added more checks and comments. gcc/match.pd | 60 ++++++++++++++++ .../gcc.target/aarch64/swar_to_vec_cmp.c | 72 +++++++++++++++++++ 2 files changed, 132 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 67a0a682f31..05e7fc79ba8 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -301,6 +301,66 @@ 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 signed comparison of packed data can + be constructed 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 uniform_integer_cst_p@1) + uniform_integer_cst_p@2) + uniform_integer_cst_p@3) + (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); + } + /* Make sure we're working with vectors and uniform vector constants. */ + (if (VECTOR_TYPE_P (type) + && tree_fits_uhwi_p (rshift_cst) + && tree_fits_uhwi_p (mult_cst) + && tree_fits_uhwi_p (bit_and_cst)) + /* 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 (type); + poly_int64 vec_nelts = TYPE_VECTOR_SUBPARTS (type); + poly_int64 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; + + /* The bit pattern in BIT_AND_I should be a mask for the least + significant bit of each packed element that is CMP_BITS wide. */ + 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 + && multiple_p (vec_bits, cmp_bits_i) + && vec_elem_bits <= HOST_BITS_PER_WIDE_INT + && 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 { + /* We're doing a signed comparison. */ + tree cmp_type = build_nonstandard_integer_type (cmp_bits_i, 0); + poly_int64 vector_type_nelts = exact_div (vec_bits, cmp_bits_i); + tree vector_cmp_type = build_vector_type (cmp_type, vector_type_nelts); + tree zeros = build_zero_cst (vector_cmp_type); + tree ones = build_all_ones_cst (vector_cmp_type); + } + (if (expand_vec_cmp_expr_p (vector_cmp_type, vector_cmp_type, LT_EXPR)) + (view_convert:type (vec_cond (lt (view_convert:vector_cmp_type @0) + { zeros; }) + { ones; } { 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