From patchwork Fri Jun 12 05:18:43 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 1307982 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=h3L7JWik; 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 49jpt56FLlz9s1x for ; Fri, 12 Jun 2020 15:18:52 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id BA9103952501; Fri, 12 Jun 2020 05:18:49 +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 4AB7F3851C17 for ; Fri, 12 Jun 2020 05:18:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 4AB7F3851C17 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=ZGpNo9vu91poxd9ruM99d4FbxPuud/BQaaD7fWdhcy0=; b=h3L7JWikr5YY7E1hz+LpO2pGVK MZLhHb7XK0Mm/VFZBCip/+Nwl8p2acto6cfcFzyqBeGCx9CLgrhiSCiJUzAB4Ik4lKRnu4XG2UN0F YCnGH8EEupMUO006fG3ULBWEFhECl9Us2mVizSZsFcg43CC+LG428cyF1tlVpIZL1SlqjRr2nWwQ0 3H7WrbSS3RNtUaMpqHlSW8a8e1IC5TJxX5gUwKzLAze1EWDmZZGjdCL7HIiSqbCM0PeIK0P4EnKIk MgTOO9lMLLT7scArQjnOLMmR4aa6xZDJJEHKYsLWsxZtD0GBlShNd9jQoaYccI2Vw5LSopjkrOmMO rb7w7+lg==; Received: from host86-137-89-56.range86-137.btcentralplus.com ([86.137.89.56]:50610 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 1jjc5V-0004ei-KB for gcc-patches@gcc.gnu.org; Fri, 12 Jun 2020 01:18:45 -0400 From: "Roger Sayle" To: Subject: [PATCH] middle-end: Parity folding optimizations. Date: Fri, 12 Jun 2020 06:18:43 +0100 Message-ID: <005501d64078$f1931610$d4b94230$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AdZAeCYpJkJzIx6tSt+9I6DIyyXKXQ== 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=-11.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, HTML_MESSAGE, 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-Content-Filtered-By: Mailman/MimeDel 2.1.29 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 patch implements several constant folding optimizations for __builtin_parity and friends. We canonicalize popcount(x)&1 as parity(x) in gimple, and potentially convert back again when we expand to RTL. parity(~x) is simplified to parity(x), which is true for all integer modes with an even number of bits. But probably most usefully, parity(x)^parity(y) can be simplified to a parity(x^y), requiring only a single libcall or popcount. This idiom is seen in PR target/44481 and elsewhere in the Linux kernel. This patch has been tested with "make bootstrap" and "make -k check" on x86_64-pc-linux-gnu with no regressions. If approved, I'd very much appreciate it if someone could commit this change for me. 2020-06-12 Roger Sayle * match.pd (popcount(x)&1 -> parity(x)): New simplification. (parity(~x) -> parity(x)): New simplification. (parity(x&1) -> x&1): New simplification. (parity(x)^parity(y) -> parity(x^y)): New simplification. 2020-06-12 Roger Sayle * gcc.dg/fold-parity-1.c: New test. * gcc.dg/fold-parity-2.c: Likewise. * gcc.dg/fold-parity-3.c: Likewise. * gcc.dg/fold-parity-4.c: Likewise. Thanks in advance, Roger --- Roger Sayle NextMove Software Cambridge, UK /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-original" } */ int foo(unsigned int x) { return __builtin_popcount(x) & 1; } int fool(unsigned long x) { return __builtin_popcountl(x) & 1; } int fooll(unsigned long long x) { return __builtin_popcountll(x) & 1; } /* { dg-final { scan-tree-dump-times "__builtin_popcount" 0 "original" } } */ /* { dg-final { scan-tree-dump-times "__builtin_parity" 3 "original" } } */ /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ int foo(unsigned int x) { return __builtin_parity(~x); } int fool(unsigned long x) { return __builtin_parityl(~x); } int fooll(unsigned long long x) { return __builtin_parityll(~x); } /* { dg-final { scan-tree-dump-times "~" 0 "optimized" } } */ /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ int foo(unsigned int x) { return __builtin_parity(x&1); } int fool(unsigned long x) { return __builtin_parityl(x&1); } int fooll(unsigned long long x) { return __builtin_parityll(x&1); } /* { dg-final { scan-tree-dump-times "__builtin_parity" 0 "optimized" } } */ /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ int foo(unsigned int x, unsigned int y) { return __builtin_parity(x) ^ __builtin_parity(y); } int fool(unsigned long x, unsigned long y) { return __builtin_parityl(x) ^ __builtin_parityl(y); } int fooll(unsigned long long x, unsigned long long y) { return __builtin_parityll(x) ^ __builtin_parityll(y); } /* { dg-final { scan-tree-dump-times "__builtin_parity" 3 "optimized" } } */ diff --git a/gcc/match.pd b/gcc/match.pd index 2b8c37e..ddb0650 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -5949,6 +5949,32 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (cmp (popcount @0) integer_zerop) (rep @0 { build_zero_cst (TREE_TYPE (@0)); })))) +/* Canonicalize POPCOUNT(x)&1 as PARITY(X). */ +(for popcount (BUILT_IN_POPCOUNT BUILT_IN_POPCOUNTL BUILT_IN_POPCOUNTLL + BUILT_IN_POPCOUNTIMAX) + parity (BUILT_IN_PARITY BUILT_IN_PARITYL BUILT_IN_PARITYLL + BUILT_IN_PARITYIMAX) + (simplify + (bit_and (popcount @0) integer_onep) + (parity @0))) + +/* PARITY simplifications. */ +(for parity (BUILT_IN_PARITY BUILT_IN_PARITYL BUILT_IN_PARITYLL + BUILT_IN_PARITYIMAX) + /* parity(~X) is parity(X). */ + (simplify + (parity (bit_not @0)) + (parity @0)) + /* parity(X&1) is nop_expr(X&1). */ + (simplify + (parity @0) + (if (tree_nonzero_bits (@0) == 1) + (convert @0))) + /* parity(X)^parity(Y) is parity(X^Y). */ + (simplify + (bit_xor (parity:s @0) (parity:s @1)) + (parity (bit_xor @0 @1)))) + #if GIMPLE /* 64- and 32-bits branchless implementations of popcount are detected: