From patchwork Tue May 24 13:54:45 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 54343 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 54F92381BBFF for ; Tue, 24 May 2022 13:55:05 +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 DD97B3857340 for ; Tue, 24 May 2022 13:54:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DD97B3857340 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: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=qH5WGEXBX0B3LOjonfkC8OAFBX6FeIvRJ1uEwjzCHQk=; b=R9yGWBNQcqZAF9Hht/U+OZfSm4 kVOqwj0oGuIzThkyNrGjgd4Dy/LXEsCFr+BGMKAwTbruABPdkbRInk+0tXmmupzD9n9oMQX45/Hcs WY7VZzJbxR4q0i8wpboVzPPqpX1ptbVbRHX2AceGnPl5Dg9sjPad1gPeYjm+TF4CeJu9MhrVl5aU1 uVp7pgtPPjPmsD9KAsw7KdyOJ8ORlpVqQiaqtL2gX11jwqX6vVo/FEqOpkJFP37h6LZiGJtDxMudN mqubTxBg9x+B/NXsQW9nMCe6assWfQrt4zI+sUiC23l2e11b8It4BR/0j5kdRuUpvSr4MnJ0Ouu+8 HaOHC7Dg==; Received: from [185.62.158.67] (port=54763 helo=Dell) by server.nextmovesoftware.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1ntUzm-0006UM-3b for gcc-patches@gcc.gnu.org; Tue, 24 May 2022 09:54:46 -0400 From: "Roger Sayle" To: "'GCC Patches'" Subject: [PATCH] Canonicalize X&-Y as X*Y in match.pd when Y is [0,1]. Date: Tue, 24 May 2022 14:54:45 +0100 Message-ID: <024f01d86f75$d40ae450$7c20acf0$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AdhvdK0i/jiu0SWXTJSd/Ceu94ZS2Q== 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.4 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, 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+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" "For every pessimization, there's an equal and opposite optimization". In the review of my original patch for PR middle-end/98865, Richard Biener pointed out that match.pd shouldn't be transforming X*Y into X&-Y as the former is considered cheaper by tree-ssa's cost model (operator count). A corollary of this is that we should instead be transforming X&-Y into the cheaper X*Y as a preferred canonical form (especially as RTL expansion now intelligently selects the appropriate implementation based on the target's costs). With this patch we now generate identical code for: int foo(int x, int y) { return -(x&1) & y; } int bar(int x, int y) { return (x&1) * y; } specifically on x86_64-pc-linux-gnu both use and/neg/and when optimizing for speed, but both use and/mul when optimizing for size. One minor wrinkle/improvement is that this patch includes three additional optimizations (that account for the change in canonical form) to continue to optimize PR92834 and PR94786. 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? 2022-05-24 Roger Sayle gcc/ChangeLog * match.pd (match_zero_one_valued_p): New predicate. (mult @0 @1): Use zero_one_valued_p for optimization to the expression "bit_and @0 @1". (bit_and (negate zero_one_valued_p@0) @1): Optimize to MULT_EXPR. (plus @0 (mult (minus @1 @0) zero_one_valued_p@2): New transform. (minus @0 (mult (minus @0 @1) zero_one_valued_p@2): Likewise. (bit_xor @0 (mult (bit_xor @0 @1) zero_one_valued_p@2): Likewise. gcc/testsuite/ChangeLog * gcc.dg/pr98865.c: New test case. Thanks in advance, Roger diff --git a/gcc/match.pd b/gcc/match.pd index c2fed9b..ce97d85 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -285,14 +285,6 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) || !COMPLEX_FLOAT_TYPE_P (type))) (negate @0))) -/* Transform { 0 or 1 } * { 0 or 1 } into { 0 or 1 } & { 0 or 1 } */ -(simplify - (mult SSA_NAME@1 SSA_NAME@2) - (if (INTEGRAL_TYPE_P (type) - && get_nonzero_bits (@1) == 1 - && get_nonzero_bits (@2) == 1) - (bit_and @1 @2))) - /* Transform x * { 0 or 1, 0 or 1, ... } into x & { 0 or -1, 0 or -1, ...}, unless the target has native support for the former but not the latter. */ (simplify @@ -1787,6 +1779,24 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (bit_not (bit_not @0)) @0) +(match zero_one_valued_p + @0 + (if (INTEGRAL_TYPE_P (type) && tree_nonzero_bits (@0) == 1))) +(match zero_one_valued_p + truth_valued_p@0) + +/* Transform { 0 or 1 } * { 0 or 1 } into { 0 or 1 } & { 0 or 1 }. */ +(simplify + (mult zero_one_valued_p@0 zero_one_valued_p@1) + (if (INTEGRAL_TYPE_P (type)) + (bit_and @0 @1))) + +/* Transform X & -Y into X * Y when Y is { 0 or 1 }. */ +(simplify + (bit_and:c (negate zero_one_valued_p@0) @1) + (if (INTEGRAL_TYPE_P (type)) + (mult @0 @1))) + /* Convert ~ (-A) to A - 1. */ (simplify (bit_not (convert? (negate @0))) @@ -3320,6 +3330,25 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) && (GIMPLE || !TREE_SIDE_EFFECTS (@1))) (cond (cmp @2 @3) @1 @0)))) +/* Likewise using multiplication, A + (B-A)*cmp into cmp ? B : A. */ +(simplify + (plus:c @0 (mult:c (minus @1 @0) zero_one_valued_p@2)) + (if (INTEGRAL_TYPE_P (type) + && (GIMPLE || !TREE_SIDE_EFFECTS (@1))) + (cond @2 @1 @0))) +/* Likewise using multiplication, A - (A-B)*cmp into cmp ? B : A. */ +(simplify + (minus @0 (mult:c (minus @0 @1) zero_one_valued_p@2)) + (if (INTEGRAL_TYPE_P (type) + && (GIMPLE || !TREE_SIDE_EFFECTS (@1))) + (cond @2 @1 @0))) +/* Likewise using multiplication, A ^ (A^B)*cmp into cmp ? B : A. */ +(simplify + (bit_xor:c @0 (mult:c (bit_xor:c @0 @1) zero_one_valued_p@2)) + (if (INTEGRAL_TYPE_P (type) + && (GIMPLE || !TREE_SIDE_EFFECTS (@1))) + (cond @2 @1 @0))) + /* Simplifications of shift and rotates. */ (for rotate (lrotate rrotate) diff --git a/gcc/testsuite/gcc.dg/pr98865.c b/gcc/testsuite/gcc.dg/pr98865.c new file mode 100644 index 0000000..95f7270 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr98865.c @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo(int x, int y) +{ + return -(x&1) & y; +} + +int bar(int x, int y) +{ + return (x&1) * y; +} + +/* { dg-final { scan-tree-dump-times " \\* " 2 "optimized" } } */