From patchwork Fri Aug 21 16:52:31 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 1349418 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=nextmovesoftware.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=nextmovesoftware.com header.i=@nextmovesoftware.com header.a=rsa-sha256 header.s=default header.b=ocbJJb1z; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4BY6yH0jbjz9sR4 for ; Sat, 22 Aug 2020 02:52:38 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id CC6C33857C76; Fri, 21 Aug 2020 16:52:35 +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 394993857C47 for ; Fri, 21 Aug 2020 16:52:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 394993857C47 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=nextmovesoftware.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=roger@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:To:From:Sender:Reply-To:Cc: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=7AtynQrsN0e0w1MNm1kyTJ1JoLaYEckXTnrIfR7Rco4=; b=ocbJJb1z058wlvC0xwu6uA+QLq 5vWnw9D3f8YK/tXVN9LC8qkTgu75plgO4MGWXsjID5+TEZPCcVHiAVQmBesNqqCoFGngHq0yHUzb0 j/nocNouE/TlOgGqiMqT7cwQGcqjJGpH78fMy4aDd5BfCglYps2y34VZGS+l3JA4XBsC4Vn1B2q1f RY2y2d3Jn/0l/s5bcN/ArF5O1Hbwbo5ZnV8tdfu+nbckyCRs7MPR/sZa0l2GosbyMWTySLWqXBNeD LFhv9qo+6+dctj5A4ZxqCuHeDZq+hAI7ocIfzGt3CV2stuR8FufMwhy1SNUNot2YWL38qzlw6gvXC WT2juWZw==; Received: from [185.62.158.67] (port=60670 helo=Dell) by server.nextmovesoftware.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.93) (envelope-from ) id 1k9AHI-00025G-LA for gcc-patches@gcc.gnu.org; Fri, 21 Aug 2020 12:52:32 -0400 From: "Roger Sayle" To: "'GCC Patches'" Subject: [PATCH] middle-end: Simplify popcount/parity of bswap/rotate. Date: Fri, 21 Aug 2020 17:52:31 +0100 Message-ID: <000801d677db$76682c10$63388430$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AdZ32vr+DqMPtX0gRaW3Gxe3o9pgEw== 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=-10.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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@gcc.gnu.org Sender: "Gcc-patches" This simple patch to match.pd optimizes away bit permutation operations, specifically bswap and rotate, in calls to popcount and parity. Although this patch has been developed and tested on LP64, it relies on there being no truncations or extensions to "marry up" the appropriate PARITY, PARITYL and PARITYLL forms with either BSWAP32 or BSWAP64, assuming this transformation won't fire if the integral types have different sizes. The following patch has been tested on x86_64-pc-linux-gnu with "make bootstrap" and "make -k check" with no new failures. Ok for mainline? 2020-08-21 Roger Sayle gcc/ChangeLog * gcc/match.pd (popcount(bswapN(x)) -> popcount(x), popcount(rotate(x)) -> popcount(x), parity(bswapN(x)) -> parity(x), parity(rotate(x)) -> parity(x)): New simplifications. gcc/testsuite/ChangeLog * gcc.dg/fold-popcount-6.c: New test. * gcc.dg/fold-popcount-7.c: New test. * gcc.dg/fold-parity-6.c: New test. * gcc.dg/fold-parity-7.c: New test. Thanks in advance, Roger --- Roger Sayle NextMove Software Cambridge, UK 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..37b55a1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-popcount-6.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +unsigned int foo(unsigned int x) +{ + if (sizeof(unsigned int) == 4) + return __builtin_popcount (__builtin_bswap32(x)); + return x; +} + +unsigned int bar(unsigned long x) +{ + if (sizeof(unsigned long) == 8) + return __builtin_popcountl (__builtin_bswap64(x)); + if (sizeof(unsigned long) == 4) + return __builtin_popcountl (__builtin_bswap32(x)); + return x; +} + +/* { 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..fdcefe1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-popcount-7.c @@ -0,0 +1,24 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +unsigned int foo(unsigned int x) +{ + if (sizeof(unsigned int) == 4) { + unsigned int y = (x>>4) | (x<<28); + return __builtin_popcount(y); + } else return x; +} + +unsigned int bar(unsigned long x) +{ + if (sizeof(unsigned long) == 8) { + unsigned long y = (x>>4) | (x<<60); + return __builtin_popcountl (y); + } else if(sizeof(unsigned long) == 4) { + unsigned long y = (x>>4) | (x<<28); + return __builtin_popcountl (y); + } else return (unsigned int)x; +} + +/* { dg-final { scan-tree-dump-times " r>> " 0 "optimized" } } */ + 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..ece0048 --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-parity-6.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +unsigned int foo(unsigned int x) +{ + if (sizeof(unsigned int) == 4) + return __builtin_parity (__builtin_bswap32(x)); + return x; +} + +unsigned int bar(unsigned long x) +{ + if (sizeof(unsigned long) == 8) + return __builtin_parityl (__builtin_bswap64(x)); + if (sizeof(unsigned long) == 4) + return __builtin_parityl (__builtin_bswap32(x)); + return (unsigned int)x; +} + +/* { 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..9b5085b --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-parity-7.c @@ -0,0 +1,24 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +unsigned int foo(unsigned int x) +{ + if (sizeof(unsigned int) == 4) { + unsigned int y = (x>>4) | (x<<28); + return __builtin_parity (y); + } else return x; +} + +unsigned int bar(unsigned long x) +{ + if (sizeof(unsigned long) == 8) { + unsigned long y = (x>>4) | (x<<60); + return __builtin_parityl (y); + } else if (sizeof(unsigned long) == 4) { + unsigned long y = (x>>4) | (x<<28); + return __builtin_parityl (y); + } else return (unsigned int)x; +} + +/* { dg-final { scan-tree-dump-times " r>> " 0 "optimized" } } */ + diff --git a/gcc/match.pd b/gcc/match.pd index c3b8816..7e8a893 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -6060,12 +6060,40 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (bit_and (POPCOUNT @0) integer_onep) (PARITY @0)) +/* Rely on no conversion to marry POPCOUNT, POPCOUNTL and POPCOUNTLL. */ +(simplify + (POPCOUNT (BUILT_IN_BSWAP32 @0)) + (POPCOUNT @0)) +(simplify + (POPCOUNT (BUILT_IN_BSWAP64 @0)) + (POPCOUNT @0)) + +(for popcount (POPCOUNT) + (for rot (lrotate rrotate) + (simplify + (popcount (rot @0 @1)) + (popcount @0)))) + /* PARITY simplifications. */ /* parity(~X) is parity(X). */ (simplify (PARITY (bit_not @0)) (PARITY @0)) +/* Rely on no conversion to marry PARITY, PARITYL and PARITYLL. */ +(simplify + (PARITY (BUILT_IN_BSWAP32 @0)) + (PARITY @0)) +(simplify + (PARITY (BUILT_IN_BSWAP64 @0)) + (PARITY @0)) + +(for parity (PARITY) + (for rot (lrotate rrotate) + (simplify + (parity (rot @0 @1)) + (parity @0)))) + /* parity(X)^parity(Y) is parity(X^Y). */ (simplify (bit_xor (PARITY:s @0) (PARITY:s @1))