From patchwork Tue Sep 13 17:54:58 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 57605 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 EC6183858D28 for ; Tue, 13 Sep 2022 17:55:20 +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 9F5C43858D28 for ; Tue, 13 Sep 2022 17:55:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9F5C43858D28 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:In-Reply-To:References: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:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=EccVkO1TQ1emsETA40yATHPg7IiXR1tbrZ3uAFrPhN4=; b=sj8ZHzU+kQwz8kFy3rNkSOD2AF SXIXA8WS6Vq5bINCUsFBLpCs0aOwTiQYUW3zeMjNaEjSdehd1pzv8RfVt+NIJmFrPCLDpawgZpvjN c4PeP/IqZ3BkL8//wBb4fK9lJOQetUXSgz3c0La27hrRZY6Gl6WN2LUBCMdQ2SY1jzWNDaDoHBdBc 3G6y1+Z5uEQT86cZqTpNQDsjdu6r/Y1s8Pm16D57/m4P5WE0l17kFJAsOtjfO0zz4WJb5iy92f4/R LyY/try7ttMa9DXJvn2GGhK8G7NtTIlZ9JK6jrSpWT6i/xmfXNILK4pm8ZbTg6et735klZCo1jwNZ C4oT1/MQ==; Received: from [185.62.158.67] (port=65476 helo=Dell) by server.nextmovesoftware.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.95) (envelope-from ) id 1oYA7g-0005yu-Hz; Tue, 13 Sep 2022 13:55:00 -0400 From: "Roger Sayle" To: "'GCC Patches'" References: <00a501d8aafd$e10b6da0$a32248e0$@nextmovesoftware.com> In-Reply-To: Subject: [PATCH] PR tree-optimization/71343: Value number X<<2 as X*4. Date: Tue, 13 Sep 2022 18:54:58 +0100 Message-ID: <000e01d8c799$f1d2fe10$d578fa30$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AdjHmK3mFL17HP/1T7OlS/Az8hD+5w== 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, 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" This patch is the second part of a fix for PR tree-optimization/71343, that implements Richard Biener's suggestion of using tree-ssa's value numbering instead of match.pd. The change is that when assigning a value number for the expression X< gcc/ChangeLog PR tree-optimization/71343 * tree-ssa-sccvn.cc (visit_nary_op) : Make the value number of the expression X << C the same as the value number for the multiplication X * (1< -----Original Message----- > From: Richard Biener > Sent: 08 August 2022 12:42 > To: Roger Sayle > Cc: GCC Patches > Subject: Re: [PATCH] PR tree-optimization/71343: Optimize (X< (X&Y)< > On Mon, Aug 8, 2022 at 10:07 AM Roger Sayle > wrote: > > > > This patch resolves PR tree-optimization/71343, a missed-optimization > > enhancement request where GCC fails to see that (a<<2)+(b<<2) == a*4+b*4. > > This requires two related (sets of) optimizations to be added to match.pd. > > > > The first is that (X< > for many binary operators, including AND, IOR, XOR, and (if overflow > > isn't an issue) PLUS and MINUS. Likewise, the right shifts (both > > logical and arithmetic) and bit-wise logical operators can be > > simplified in a similar fashion. These all reduce the number of > > GIMPLE binary operations from 3 to 2, by combining/eliminating a shift > operation. > > > > The second optimization reflects that the middle-end doesn't impose a > > canonical form on multiplications by powers of two, vs. left shifts, > > instead leaving these operations as specified by the programmer unless > > there's a good reason to change them. Hence, GIMPLE code may contain > > the expressions "X * 8" and "X << 3" even though these represent the > > same value/computation. The tweak to match.pd is that comparison > > operations whose operands are equivalent non-canonical expressions can > > be taught their equivalence. Hence "(X * 8) == (X << 3)" will always > > evaluate to true, and "(X<<2) > 4*X" will always evaluate to false. > > > > 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? > > +/* Shifts by constants distribute over several binary operations, > + hence (X << C) + (Y << C) can be simplified to (X + Y) << C. */ > +(for op (plus minus) > + (simplify > + (op (lshift:s @0 INTEGER_CST@1) (lshift:s @2 INTEGER_CST@1)) > + (if (INTEGRAL_TYPE_P (type) > + && TYPE_OVERFLOW_WRAPS (type) > + && !TYPE_SATURATING (type) > + && tree_fits_shwi_p (@1) > + && tree_to_shwi (@1) > 0 > + && tree_to_shwi (@1) < TYPE_PRECISION (type)) > > I do wonder why we need to restrict this to shifts by constants? > Any out-of-bound shift was already there, no? > > +/* Some tree expressions are intentionally non-canonical. > + We handle the comparison of the equivalent forms here. */ (for cmp > +(eq le ge) > + (simplify > + (cmp:c (lshift @0 INTEGER_CST@1) (mult @0 integer_pow2p@2)) > + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) > + && tree_fits_shwi_p (@1) > + && tree_to_shwi (@1) > 0 > + && tree_to_shwi (@1) < TYPE_PRECISION (TREE_TYPE (@0)) > + && wi::to_wide (@1) == wi::exact_log2 (wi::to_wide (@2))) > + { constant_boolean_node (true, type); }))) > + > +(for cmp (ne lt gt) > + (simplify > + (cmp:c (lshift @0 INTEGER_CST@1) (mult @0 integer_pow2p@2)) > + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) > + && tree_fits_shwi_p (@1) > + && tree_to_shwi (@1) > 0 > + && tree_to_shwi (@1) < TYPE_PRECISION (TREE_TYPE (@0)) > + && wi::to_wide (@1) == wi::exact_log2 (wi::to_wide (@2))) > + { constant_boolean_node (false, type); }))) > > hmm. I wonder if it makes more sense to handle this in value-numbering. > tree-ssa-sccvn.cc:visit_nary_op handles some cases that are not exactly > canonicalization issues but the shift vs mult could be handled there by just > performing the alternate lookup. That would also enable CSE and by means of > that of course the comparisons you do above. > > Thanks, > Richard. > > > > > 2022-08-08 Roger Sayle > > > > gcc/ChangeLog > > PR tree-optimization/71343 > > * match.pd (op (lshift @0 @1) (lshift @2 @1)): Optimize the > > expression (X< > (op (rshift @0 @1) (rshift @2 @1)): Likwise, simplify (X>>C)^(Y>>C) > > to (X^Y)>>C for binary logical operators, AND, IOR and XOR. > > (cmp:c (lshift @0) (mult @1)): Optimize comparisons between > > shifts by integer constants and multiplications by powers of 2. > > > > gcc/testsuite/ChangeLog > > PR tree-optimization/71343 > > * gcc.dg/pr71343-1.c: New test case. > > * gcc.dg/pr71343-2.c: Likewise. > > > > > > Thanks in advance, > > Roger > > -- diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc index 74b8d8d..2644446 100644 --- a/gcc/tree-ssa-sccvn.cc +++ b/gcc/tree-ssa-sccvn.cc @@ -5312,6 +5312,30 @@ visit_nary_op (tree lhs, gassign *stmt) } } break; + case LSHIFT_EXPR: + /* For X << C, use the value number of X * (1 << C). */ + if (INTEGRAL_TYPE_P (type)) + { + tree rhs2 = gimple_assign_rhs2 (stmt); + if (TREE_CODE (rhs2) == INTEGER_CST + && tree_fits_uhwi_p (rhs2) + && tree_to_uhwi (rhs2) < TYPE_PRECISION (type)) + { + wide_int w = wi::set_bit_in_zero (tree_to_uhwi (rhs2), + TYPE_PRECISION (type)); + gimple_match_op match_op (gimple_match_cond::UNCOND, + MULT_EXPR, type, rhs1, + wide_int_to_tree (type, w)); + result = vn_nary_build_or_lookup (&match_op); + if (result) + { + bool changed = set_ssa_val_to (lhs, result); + vn_nary_op_insert_stmt (stmt, result); + return changed; + } + } + } + break; default: break; } diff --git a/gcc/testsuite/gcc.dg/pr71343-2.c b/gcc/testsuite/gcc.dg/pr71343-2.c new file mode 100644 index 0000000..11800a9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr71343-2.c @@ -0,0 +1,34 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +unsigned int test1(unsigned int a , unsigned int b) +{ + return (a << 2) + (b << 2) == a * 4 + b * 4; +} + +unsigned int test2(unsigned int a , unsigned int b) +{ + return (a << 2) + (b << 2) == (a + b) << 2; +} + +unsigned int test3(unsigned int a , unsigned int b) +{ + return a * 4 + b * 4 == (a + b) * 4; +} + +unsigned int test4(unsigned int a , unsigned int b) +{ + return (a + b) << 2 == (a + b) * 4; +} + +unsigned int test5(unsigned int a , unsigned int b) +{ + return (a << 2) + (b << 2) == (a + b) * 4; +} + +unsigned int test6(unsigned int a , unsigned int b) +{ + return (a + b) << 2 == a * 4 + b * 4; +} + +/* { dg-final { scan-tree-dump-times "return 1" 6 "optimized" } } */