From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from server.nextmovesoftware.com (server.nextmovesoftware.com [162.254.253.69]) by sourceware.org (Postfix) with ESMTPS id DD4653858413 for ; Wed, 18 May 2022 16:55:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DD4653858413 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=0TlX0QBQOw4LjadGvl3Eqz+GyR2dzqInQHWyiDGVVu0=; b=I45lYkg4etdeNeYVww6ONsvoU7 +7GdSB9goIwS+D9+bq6VJ2XQ7iQLD2NfZvNy+yxqNf9etxyqKkGgZIyhXr8LxCT11XauEU1A4I0ig ttPYUTKkHg44B4ogyKPtE0vGkKeLIcZQXiGbF/QJ4Rx9t5AsBf90wHLdmpKALCeUCGdgDydhGWdep yzZuI9vi1U4YIfiM7muJpXw+kUEbPJeeNDHBtL+7CTt+Aba1eHfvm5CUGoYub/2+AiskgB4saU4Do uQcRxZXAI1TgGJPdSu8WVLLFE9yna44xcZAlbCV9na4+bPj34Tzaoe3/tWL2+hcpGgCf+iGn/9879 w0Grjbbw==; Received: from [185.62.158.67] (port=52922 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 1nrMxM-00005T-8C; Wed, 18 May 2022 12:55:28 -0400 From: "Roger Sayle" To: Subject: [PATCH take #2] PR middle-end/98865: Expand X*Y as X&-Y when Y is [0.1]. Date: Wed, 18 May 2022 17:55:26 +0100 Message-ID: <061801d86ad8$13976a00$3ac63e00$@nextmovesoftware.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_NextPart_000_0619_01D86AE0.755BD200" X-Mailer: Microsoft Outlook 16.0 Thread-Index: Adhq1o9HGa/6CnivRjuazZvL2ZY37Q== 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, 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: , X-List-Received-Date: Wed, 18 May 2022 16:55:30 -0000 This is a multipart message in MIME format. ------=_NextPart_000_0619_01D86AE0.755BD200 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit The patch is a revised solution for PR middle-end/98865 incorporating the feedback/suggestions from Richard Biener's review here: https://gcc.gnu.org/pipermail/gcc-patches/2022-May/593928.html Most significantly, this patch now performs the transformation/optimization during RTL expansion, where the target's rtx_costs can be used to determine whether the original multiplication (that may be possibly be implemented by a shift or lea) is cheaper than a negation and a bit-wise and. Previously the expression (x>>63)*y would be compiled with -O2 as shrq $63, %rdi movq %rdi, %rax imulq %rsi, %rax but with this patch now produces: sarq $63, %rdi movq %rdi, %rax andq %rsi, %rax Likewise the expression (x>>63)*135 [that appears in a hot-spot of the Botan AES-128 benchmark] was previously: shrq $63, %rdi leaq (%rdi,%rdi,8), %rdx movq %rdx, %rax salq $4, %rax subq %rdx, %rax now becomes: movq %rdi, %rax sarq $63, %rax andl $135, %eax 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. Many thanks to Uros for the speedy review and approval of my x86_rtx_costs patch that enables this transformation on -m32 using the correct cost of DImode multiplication. Ok for mainline? 2022-05-18 Roger Sayle gcc/ChangeLog PR middle-end/98865 * expr.cc (expand_expr_real_2) [MULT_EXPR]: Expand X*Y as X&Y when both X and Y are [0, 1], X*Y as X&-Y when Y is [0,1] and likewise X*Y as -X&Y when X is [0,1] using tree_nonzero_bits. gcc/testsuite/ChangeLog PR middle-end/98865 * gcc.target/i386/pr98865.c: New test case. Thanks in advance, Roger -- ------=_NextPart_000_0619_01D86AE0.755BD200 Content-Type: text/plain; name="patchbmb.txt" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="patchbmb.txt" diff --git a/gcc/expr.cc b/gcc/expr.cc=0A= index 1806091..7197996 100644=0A= --- a/gcc/expr.cc=0A= +++ b/gcc/expr.cc=0A= @@ -9541,6 +9541,38 @@ expand_expr_real_2 (sepops ops, rtx target, = machine_mode tmode,=0A= }=0A= =0A= expand_operands (treeop0, treeop1, subtarget, &op0, &op1, = EXPAND_NORMAL);=0A= +=0A= + /* Expand X*Y as X&-Y when Y must be zero or one. */=0A= + if (SCALAR_INT_MODE_P (mode))=0A= + {=0A= + bool bit0_p =3D tree_nonzero_bits (treeop0) =3D=3D 1;=0A= + bool bit1_p =3D tree_nonzero_bits (treeop1) =3D=3D 1;=0A= +=0A= + /* Expand X*Y as X&Y when both X and Y must be zero or one. */=0A= + if (bit0_p && bit1_p)=0A= + return REDUCE_BIT_FIELD (expand_and (mode, op0, op1, target));=0A= +=0A= + if (bit0_p || bit1_p)=0A= + {=0A= + bool speed =3D optimize_insn_for_speed_p ();=0A= + int cost =3D add_cost (speed, mode) + neg_cost (speed, mode);=0A= + struct algorithm algorithm;=0A= + enum mult_variant variant;=0A= + if (CONST_INT_P (op1)=0A= + ? !choose_mult_variant (mode, INTVAL (op1),=0A= + &algorithm, &variant, cost)=0A= + : cost < mul_cost (speed, mode))=0A= + {=0A= + target =3D bit0_p ? expand_and (mode, negate_rtx (mode, op0),=0A= + op1, target)=0A= + : expand_and (mode, op0,=0A= + negate_rtx (mode, op1),=0A= + target);=0A= + return REDUCE_BIT_FIELD (target);=0A= + }=0A= + }=0A= + }=0A= +=0A= return REDUCE_BIT_FIELD (expand_mult (mode, op0, op1, target, = unsignedp));=0A= =0A= case TRUNC_MOD_EXPR:=0A= diff --git a/gcc/testsuite/gcc.target/i386/pr98865.c = b/gcc/testsuite/gcc.target/i386/pr98865.c=0A= new file mode 100644=0A= index 0000000..d047c4b=0A= --- /dev/null=0A= +++ b/gcc/testsuite/gcc.target/i386/pr98865.c=0A= @@ -0,0 +1,54 @@=0A= +/* { dg-do compile } */=0A= +/* { dg-options "-O2 -fdump-tree-optimized" } */=0A= +=0A= +#if __SIZEOF_INT__ =3D=3D 4=0A= +unsigned int foo(unsigned int a, unsigned int b)=0A= +{=0A= + return (a >> 31) * b;=0A= +}=0A= +=0A= +int bar(int a, int b)=0A= +{=0A= + return -(a >> 31) * b;=0A= +}=0A= +=0A= +int baz(int a, int b)=0A= +{=0A= + int c =3D a >> 31;=0A= + int d =3D -c;=0A= + return d * b;=0A= +}=0A= +=0A= +unsigned int pin(int a, unsigned int b)=0A= +{=0A= + unsigned int t =3D a & 1;=0A= + return t * b;=0A= +}=0A= +#endif=0A= +=0A= +#if __SIZEOF_LONG_LONG__ =3D=3D 8=0A= +unsigned long long fool(unsigned long long a, unsigned long long b)=0A= +{=0A= + return (a >> 63) * b;=0A= +}=0A= +=0A= +long long barl (long long a, long long b)=0A= +{=0A= + return -(a >> 63) * b;=0A= +}=0A= +=0A= +long long bazl (long long a, long long b)=0A= +{=0A= + long long c =3D a >> 63;=0A= + long long d =3D -c;=0A= + return d * b;=0A= +}=0A= +=0A= +unsigned long long pinl(long long a, unsigned long long b)=0A= +{=0A= + unsigned long long t =3D a & 1;=0A= + return t * b;=0A= +}=0A= +#endif=0A= +=0A= +/* { dg-final { scan-assembler-not "imul" } } */=0A= ------=_NextPart_000_0619_01D86AE0.755BD200--