From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x62f.google.com (mail-ej1-x62f.google.com [IPv6:2a00:1450:4864:20::62f]) by sourceware.org (Postfix) with ESMTPS id D14943858CDB for ; Mon, 15 Aug 2022 07:49:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D14943858CDB Received: by mail-ej1-x62f.google.com with SMTP id gk3so12219785ejb.8 for ; Mon, 15 Aug 2022 00:49:11 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc; bh=Tfvl7Mkfcx/jDBmCwfao1Oaxvla3FHcK64k1cm/mBpY=; b=zAudhZZSsSJgWahZhc5XGbJJQ1KM9RXLiVCbwgo9nPqZ4pNqfviHMq5aHlHDWBuToW jvSJRM1XJPnX5VlpBC0vPzhXKuviji8rBv8x8fNJ4aBYbffrAOIk1U8rJTZ3yH6b4qVD myRRdG5DRvoXDTFYiJUBjZ9Lol7RCLRTXEqFpoBoKctFng1Du1qIgv9IQy2SCDStwMfa TGsFVYbXxzei5NotGQrh4eVoMUoKKcMbx4lDrYaEydM/aXk8dqY2zwsxo2/3tI4I6joX Ik4ik/2jdUyWAuQrnq0Zh9AL+fqANEtAr5EFLpwPUnDYDimtYoqp3GImLh4i1flgiAkz 9ytQ== X-Gm-Message-State: ACgBeo12xEAVCxiXG6ixRIKWPXU4+TWEkOgWtAAhsyFlaO/meHZaWDxS GwMsPMu4lN+PiPLMGAk8MEhULwRWYbFnC6GtINDweP+k X-Google-Smtp-Source: AA6agR6RITeEWnurT1bHT23XZ0Fn0p6Ipua6TbexO/t3jPxhk9wooWE1XCVsxm29ym69ARFrSNxU4LjQgU+xHauAK4U= X-Received: by 2002:a17:907:97c1:b0:733:19ef:b2b with SMTP id js1-20020a17090797c100b0073319ef0b2bmr9494766ejc.511.1660549750614; Mon, 15 Aug 2022 00:49:10 -0700 (PDT) MIME-Version: 1.0 References: <00a501d8aafd$e10b6da0$a32248e0$@nextmovesoftware.com> <009a01d8ae94$c7d92800$578b7800$@nextmovesoftware.com> In-Reply-To: <009a01d8ae94$c7d92800$578b7800$@nextmovesoftware.com> From: Richard Biener Date: Mon, 15 Aug 2022 09:48:58 +0200 Message-ID: Subject: Re: [PATCH take #2] PR tree-optimization/71343: Optimize (X< Cc: GCC Patches Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, 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: Mon, 15 Aug 2022 07:49:14 -0000 On Fri, Aug 12, 2022 at 11:45 PM Roger Sayle wrote: > > > Hi Richard, > Many thanks for the review and useful suggestions. I (think I) agree that > handling non-canonical forms in value_numbering makes more sense, > so this revised patch is just the first (non-controversial) part of the original > submission, that incorporates your observation that it doesn't need to > be limited to (valid) constant shifts, and can be generalized to any > shift, without introducing undefined behaviour that didn't exist before. > > This revised 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? OK. Thanks, Richard. > > 2022-08-12 Roger Sayle > Richard Biener > > 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)): Likewise, simplify (X>>C)^(Y>>C) > to (X^Y)>>C for binary logical operators, AND, IOR and XOR. > > gcc/testsuite/ChangeLog > PR tree-optimization/71343 > * gcc.dg/pr71343-1.c: New test case. > > > Thanks, > Roger > -- > > > -----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 > > > -- > > >