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 83A7C385829E for ; Mon, 8 Aug 2022 11:42:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 83A7C385829E Received: by mail-ej1-x62f.google.com with SMTP id j8so16032977ejx.9 for ; Mon, 08 Aug 2022 04:42:15 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=iALtSixm0UxNiyapUscmYVaLb8c7W4fLcy+wLoXfVEc=; b=B/GPTRHFJVE7iGKhNBpMOMas2GsNKA7r+00AQWlo75qMXPJP1+6dm9x9cmqdsDWRFT e4K/HBWfZRDgwhyiFjCdGxHHVOWxV3vNJPsaoiFgWJK41rLvL6DqatCVcLVJM1zqGKn8 qQNrwJ+SOJeR5AffobCxxLumVMozoIafoSuoBb+nvBbNllW4Py0uu6jxHpcwkxPHbXoN msa/1PiS7H/k/BNw8euCQoYs8PSZ+dvxOSOVN9FaVe84A5rvX95vfHP3wxE3NUb3jac9 q379N+FgwHUd+v627BEasxNsc112WI2GblF0TNgwy7CzkJQjqvQAHSoM+t/yHjiZiD// NYRg== X-Gm-Message-State: ACgBeo0Yt1z35kUK050253ktdeU1KRxT1ZqEtjfhgrL/TDOlIV2qnGRB dDvAXt0fB8Fyhm/mxVEVscnmzNtTMYk4aNzPv9GbbOs6psw= X-Google-Smtp-Source: AA6agR6M5D2KXmwkFBh2A7TY1jtYD4LWFKDpCQ1ulnIoUFP62IfmcyGsbrjSyjtCmvYP4o3lsv2MFn6uy/pOhNlQLQs= X-Received: by 2002:a17:907:948f:b0:731:3f2e:8916 with SMTP id dm15-20020a170907948f00b007313f2e8916mr5834716ejc.442.1659958934077; Mon, 08 Aug 2022 04:42:14 -0700 (PDT) MIME-Version: 1.0 References: <00a501d8aafd$e10b6da0$a32248e0$@nextmovesoftware.com> In-Reply-To: <00a501d8aafd$e10b6da0$a32248e0$@nextmovesoftware.com> From: Richard Biener Date: Mon, 8 Aug 2022 13:42:02 +0200 Message-ID: Subject: Re: [PATCH] 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, 08 Aug 2022 11:42:17 -0000 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 > -- >