From patchwork Wed May 10 14:46:10 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 92163 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp3679130vqo; Wed, 10 May 2023 07:46:46 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ5oncYvsqdS/mSehFYhUj6qq2EhDCA14BmlIdmtK/qCUVPithvkXvifcwLbrkHpdWiMEhDn X-Received: by 2002:a17:907:869e:b0:93d:ae74:fa9e with SMTP id qa30-20020a170907869e00b0093dae74fa9emr17199758ejc.7.1683730006308; Wed, 10 May 2023 07:46:46 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1683730006; cv=none; d=google.com; s=arc-20160816; b=WyF4F/mNNleWXWWVltl/VHiScmzduQ44m99Kp2NkLbxzS8XAyw/4Vl92WGywAftlnS +ec8/u+sUKTfF8QEysiLHzaKpS0jRU3uOgUn7TnXNiRh6+vgGnul06l0N4griGCIhaH0 XEdMDLnDu4+eHLwp6GoFWZC2Be5K9jYMZmAXFZEhCj1yebi0VuX6hkUBdUWxjLrMeVgM 6g4Tm56+gOAS4Kg8+/13kaFIHRSSTF3seQDAbXduoMMPoXoap0+kUxEwK/sLGa4siziy zf0EviePVczBND12TSb2jVo32lqOI5ueZ5S1L09zfspPvWIHz1fnsHNMgnNRRxzL9Cqy VSqw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-language:thread-index :mime-version:message-id:date:subject:cc:to:from:dkim-signature :dmarc-filter:delivered-to; bh=POdljCSOJREtfVKulE2atBXxRGN5mEvtFs6ci8PohG8=; b=l/vuA3xbw1/5ZCDXPzSa4PN5Urb3IUUsGgNlJMhpxMfxsoODeY3OXvJ34SrpWGjMAG rVohFEgJNaUigQhZYdA4e3ju1xP3BjY3y/1lwaGPVQSwCV0eLHQSYYIoQyU+XR49cgHa ZylR2/EWhj/qlAMHvaqIDDPGHsNt9hfdOuDUBO5BgsqoXXJK8nFuwFunhcQswVldRXqA aEYAdpdjuciIYqWjCVMfDpOh8hhvl38kBFZwneIamRmoehQWhwL0oJQvOVz/sTNCLd8X mGG0KY5irHfMmQNnJ2QAw4pphlzsDJ++LDpbJfkav/uRINmwnReQXqtoU0x4z3qNr3wQ l0bA== ARC-Authentication-Results: i=1; mx.google.com; dkim=fail header.i=@nextmovesoftware.com header.s=default header.b=ZhlDDMV4; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org" Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id kv8-20020a17090778c800b0094f6cfceb2fsi4255168ejc.236.2023.05.10.07.46.46 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 10 May 2023 07:46:46 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=fail header.i=@nextmovesoftware.com header.s=default header.b=ZhlDDMV4; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org" Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2E2893853559 for ; Wed, 10 May 2023 14:46:39 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from server.nextmovesoftware.com (server.nextmovesoftware.com [162.254.253.69]) by sourceware.org (Postfix) with ESMTPS id 2A4A8385702F for ; Wed, 10 May 2023 14:46:13 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2A4A8385702F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=nextmovesoftware.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=nextmovesoftware.com DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=nextmovesoftware.com; s=default; h=Content-Type:MIME-Version:Message-ID: Date:Subject:Cc:To:From:Sender:Reply-To:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=POdljCSOJREtfVKulE2atBXxRGN5mEvtFs6ci8PohG8=; b=ZhlDDMV4dHy0aLKNKeAebhBmSR /CVzzYkObkyQzncfh8P6DtZ1bPaNtzIaAL+yAhi+tLv5IT4OHsq2NtQb9hDxM7vy5StSM5tmG901u 6Uk11wY3EUDnVksL4oa51cpO6MvQrwKtNPgTNhkYxjgHonNMpk8gNL5N6/0uOu1NboKyL9soqlaQv P6FPfxYS9uP+Ey8DUEL0aaARqN80fbq9sVTYfQ/HhAr9GqQhRkqQf/8Zun7KIs7AuUaL6SjgPYijg rnc6iQMphe69L6XQjFETWd7eNeHR3Pd+IovEFiBdGUSFENY1MJzExu6yyL9jp057idOnY0zp6wSB2 ornF+rnA==; Received: from [185.62.158.67] (port=63222 helo=Dell) by server.nextmovesoftware.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1pwl52-0005R0-0R; Wed, 10 May 2023 10:46:12 -0400 From: "Roger Sayle" To: "'GCC Patches'" Cc: "'Marc Glisse'" Subject: [PATCH take #3] match.pd: Simplify popcount/parity of bswap/rotate. Date: Wed, 10 May 2023 15:46:10 +0100 Message-ID: <000a01d9834e$2a7811e0$7f6835a0$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AdmDTbVO6q43nVXgRhegqNEYOm/+lg== Content-Language: en-gb X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - server.nextmovesoftware.com X-AntiAbuse: Original Domain - gcc.gnu.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - nextmovesoftware.com X-Get-Message-Sender-Via: server.nextmovesoftware.com: authenticated_id: roger@nextmovesoftware.com X-Authenticated-Sender: server.nextmovesoftware.com: roger@nextmovesoftware.com X-Source: X-Source-Args: X-Source-Dir: X-Spam-Status: No, score=-12.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, 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: , Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765518874895682179?= X-GMAIL-MSGID: =?utf-8?q?1765518874895682179?= This is the latest iteration of my patch from August 2020 https://gcc.gnu.org/pipermail/gcc-patches/2020-August/552391.html incorporating feedback and suggestions from reviewers. This patch to match.pd optimizes away bit permutation operations, specifically bswap and rotate, in calls to popcount and parity. This patch has been tested on x86_64-pc-linux-gnu with make bootstrap and make -k check, both with and without --target_board=unix{-m32} with no new failures. Ok for mainline? 2023-05-10 Roger Sayle gcc/ChangeLog * match.pd : Simplify popcount(bswap(x)) as popcount(x). Simplify popcount(rotate(x,y)) as popcount(x). : Simplify parity(bswap(x)) as parity(x). Simplify parity(rotate(x,y)) as parity(x). gcc/testsuite/ChangeLog * gcc.dg/fold-parity-6.c: New test. * gcc.dg/fold-parity-7.c: New test. * gcc.dg/fold-popcount-6.c: New test. * gcc.dg/fold-popcount-7.c: New test. Thanks again, Roger diff --git a/gcc/match.pd b/gcc/match.pd index ceae1c3..bc083be 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -7766,6 +7766,32 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (cmp (popcount @0) integer_zerop) (rep @0 { build_zero_cst (TREE_TYPE (@0)); })))) +/* popcount(bswap(x)) is popcount(x). */ +(for popcount (POPCOUNT) + (for bswap (BUILT_IN_BSWAP16 BUILT_IN_BSWAP32 + BUILT_IN_BSWAP64 BUILT_IN_BSWAP128) + (simplify + (popcount (convert?@0 (bswap:s@1 @2))) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) + && INTEGRAL_TYPE_P (TREE_TYPE (@1))) + (with { unsigned int prec0 = TYPE_PRECISION (TREE_TYPE (@0)); + unsigned int prec1 = TYPE_PRECISION (TREE_TYPE (@1)); } + (if (prec0 == prec1 || (prec0 > prec1 && TYPE_UNSIGNED (@1))) + (popcount @2))))))) + +/* popcount(rotate(X Y)) is popcount(X). */ +(for popcount (POPCOUNT) + (for rot (lrotate rrotate) + (simplify + (popcount (convert?@0 (rot:s@1 @2 @3))) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) + && INTEGRAL_TYPE_P (TREE_TYPE (@1)) + && (GIMPLE || !TREE_SIDE_EFFECTS (@3))) + (with { unsigned int prec0 = TYPE_PRECISION (TREE_TYPE (@0)); + unsigned int prec1 = TYPE_PRECISION (TREE_TYPE (@1)); } + (if (prec0 == prec1 || (prec0 > prec1 && TYPE_UNSIGNED (@1))) + (popcount @2))))))) + /* Canonicalize POPCOUNT(x)&1 as PARITY(X). */ (simplify (bit_and (POPCOUNT @0) integer_onep) @@ -7777,6 +7803,30 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (PARITY (bit_not @0)) (PARITY @0)) +/* parity(bswap(x)) is parity(x). */ +(for parity (PARITY) + (for bswap (BUILT_IN_BSWAP16 BUILT_IN_BSWAP32 + BUILT_IN_BSWAP64 BUILT_IN_BSWAP128) + (simplify + (parity (convert?@0 (bswap:s@1 @2))) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) + && INTEGRAL_TYPE_P (TREE_TYPE (@1)) + && TYPE_PRECISION (TREE_TYPE (@0)) + >= TYPE_PRECISION (TREE_TYPE (@1))) + (parity @2))))) + +/* parity(rotate(X Y)) is parity(X). */ +(for parity (PARITY) + (for rot (lrotate rrotate) + (simplify + (parity (convert?@0 (rot:s@1 @2 @3))) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) + && INTEGRAL_TYPE_P (TREE_TYPE (@1)) + && (GIMPLE || !TREE_SIDE_EFFECTS (@3)) + && TYPE_PRECISION (TREE_TYPE (@0)) + >= TYPE_PRECISION (TREE_TYPE (@1))) + (parity @2))))) + /* parity(X)^parity(Y) is parity(X^Y). */ (simplify (bit_xor (PARITY:s @0) (PARITY:s @1)) diff --git a/gcc/testsuite/gcc.dg/fold-parity-6.c b/gcc/testsuite/gcc.dg/fold-parity-6.c new file mode 100644 index 0000000..623afb9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-parity-6.c @@ -0,0 +1,37 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo(unsigned int x) +{ +#if __SIZEOF_INT__ == 4 + return __builtin_parity (__builtin_bswap32(x)); +#elif __SIZEOF_INT__ == 2 + return __builtin_parity (__builtin_bswap16(x)); +#else + return x; +#endif +} + +int bar(unsigned long x) +{ +#if __SIZEOF_LONG__ == 8 + return __builtin_parityl (__builtin_bswap64(x)); +#elif __SIZEOF_LONG__ == 4 + return __builtin_parityl (__builtin_bswap32(x)); +#else + return x; +#endif +} + +int baz(unsigned long long x) +{ +#if __SIZEOF_LONG_LONG__ == 8 + return __builtin_parityll (__builtin_bswap64(x)); +#elif __SIZEOF_LONG_LONG__ == 4 + return __builtin_parityll (__builtin_bswap32(x)); +#else + return x; +#endif +} + +/* { dg-final { scan-tree-dump-times "bswap" 0 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/fold-parity-7.c b/gcc/testsuite/gcc.dg/fold-parity-7.c new file mode 100644 index 0000000..c08cdee --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-parity-7.c @@ -0,0 +1,43 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo(unsigned int x) +{ +#if __SIZEOF_INT__ == 4 + unsigned int y = (x>>4) | (x<<28); + return __builtin_parity(y); +#elif __SIZEOF_INT__ == 2 + unsigned int y = (x>>4) | (x<<12); + return __builtin_parity(y); +#else + return x; +#endif +} + +int bar(unsigned long x) +{ +#if __SIZEOF_LONG__ == 8 + unsigned long y = (x>>4) | (x<<60); + return __builtin_parityl (y); +#elif __SIZEOF_LONG__ == 4 + unsigned long y = (x>>4) | (x<<28); + return __builtin_parityl (y); +#else + return x; +#endif +} + +int baz(unsigned long long x) +{ +#if __SIZEOF_LONG_LONG__ == 8 + unsigned long long y = (x>>4) | (x<<60); + return __builtin_parityll (y); +#elif __SIZEOF_LONG_LONG__ == 4 + unsigned long long y = (x>>4) | (x<<28); + return __builtin_parityll (y); +#else + return x; +#endif +} + +/* { dg-final { scan-tree-dump-times " r>> " 0 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/fold-popcount-6.c b/gcc/testsuite/gcc.dg/fold-popcount-6.c new file mode 100644 index 0000000..e7f38d0 --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-popcount-6.c @@ -0,0 +1,37 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo(unsigned int x) +{ +#if __SIZEOF_INT__ == 4 + return __builtin_popcount (__builtin_bswap32(x)); +#elif __SIZEOF_INT__ == 2 + return __builtin_popcount (__builtin_bswap16(x)); +#else + return x; +#endif +} + +int bar(unsigned long x) +{ +#if __SIZEOF_LONG__ == 8 + return __builtin_popcountl (__builtin_bswap64(x)); +#elif __SIZEOF_LONG__ == 4 + return __builtin_popcountl (__builtin_bswap32(x)); +#else + return x; +#endif +} + +int baz(unsigned long long x) +{ +#if __SIZEOF_LONG_LONG__ == 8 + return __builtin_popcountll (__builtin_bswap64(x)); +#elif __SIZEOF_LONG_LONG__ == 4 + return __builtin_popcountll (__builtin_bswap32(x)); +#else + return x; +#endif +} + +/* { dg-final { scan-tree-dump-times "bswap" 0 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/fold-popcount-7.c b/gcc/testsuite/gcc.dg/fold-popcount-7.c new file mode 100644 index 0000000..dcfdf5f --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-popcount-7.c @@ -0,0 +1,43 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo(unsigned int x) +{ +#if __SIZEOF_INT__ == 4 + unsigned int y = (x>>4) | (x<<28); + return __builtin_popcount(y); +#elif __SIZEOF_INT__ == 2 + unsigned int y = (x>>4) | (x<<12); + return __builtin_popcount(y); +#else + return x; +#endif +} + +int bar(unsigned long x) +{ +#if __SIZEOF_LONG__ == 8 + unsigned long y = (x>>4) | (x<<60); + return __builtin_popcountl (y); +#elif __SIZEOF_LONG__ == 4 + unsigned long y = (x>>4) | (x<<28); + return __builtin_popcountl (y); +#else + return x; +#endif +} + +int baz(unsigned long long x) +{ +#if __SIZEOF_LONG_LONG__ == 8 + unsigned long long y = (x>>4) | (x<<60); + return __builtin_popcountll (y); +#elif __SIZEOF_LONG_LONG__ == 4 + unsigned long long y = (x>>4) | (x<<28); + return __builtin_popcountll (y); +#else + return x; +#endif +} + +/* { dg-final { scan-tree-dump-times " r>> " 0 "optimized" } } */