Message ID  00ce01d8ab06$19113060$4b339120$@nextmovesoftware.com 

State  New 
Headers 
ReturnPath: <gccpatchesbounces+patchwork=sourceware.org@gcc.gnu.org> XOriginalTo: patchwork@sourceware.org DeliveredTo: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 410FF385702A for <patchwork@sourceware.org>; Mon, 8 Aug 2022 09:06:26 +0000 (GMT) XOriginalTo: gccpatches@gcc.gnu.org DeliveredTo: gccpatches@gcc.gnu.org Received: from server.nextmovesoftware.com (server.nextmovesoftware.com [162.254.253.69]) by sourceware.org (Postfix) with ESMTPS id 6BD0038582B3 for <gccpatches@gcc.gnu.org>; Mon, 8 Aug 2022 09:06:10 +0000 (GMT) DMARCFilter: OpenDMARC Filter v1.4.1 sourceware.org 6BD0038582B3 AuthenticationResults: sourceware.org; dmarc=none (p=none dis=none) header.from=nextmovesoftware.com AuthenticationResults: sourceware.org; spf=pass smtp.mailfrom=nextmovesoftware.com DKIMSignature: v=1; a=rsasha256; q=dns/txt; c=relaxed/relaxed; d=nextmovesoftware.com; s=default; h=ContentType:MIMEVersion:MessageID: Date:Subject:Cc:To:From:Sender:ReplyTo:ContentTransferEncoding:ContentID: ContentDescription:ResentDate:ResentFrom:ResentSender:ResentTo:ResentCc :ResentMessageID:InReplyTo:References:ListId:ListHelp:ListUnsubscribe: ListSubscribe:ListPost:ListOwner:ListArchive; bh=34VzJP3ilk3PBPE+Dk+RC2r8zCOX18RBvm44XvPQpHQ=; b=aEUIEwpgmxjK53QxqKeKJwdui6 1YxjxQiDNayF1a08201bCgXpFeaWkw4yZFueg6fHlXPP5mVFzup08pk2YmnP8qn4DWsgaPEYk+ATz 2A9Y/SB7ox+RV49E5MRdGsSkP+rwEhInD4QzPqp/s4DuJK8xHSqYGIi98axQWupCmnvldD1ejI97X FiVWpjaJ8CH+AgVJlKgR7a/anW55FbjfBD6YCjRCa/olSpYRTyg6dMR2fd6pTC9PprP19Zfe3Q9fU K5O+DLp0bIwI+xS7qw2SnXnXpwhO3JPAjKq+k0bV2v1pf05ZNXypyG/vwU9ro3z0z5HCp4u3Pb1Hk j/144M1w==; Received: from host8616941119.range86169.btcentralplus.com ([86.169.41.119]:57070 helo=Dell) by server.nextmovesoftware.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelopefrom <roger@nextmovesoftware.com>) id 1oKyi900085TML; Mon, 08 Aug 2022 05:06:09 0400 From: "Roger Sayle" <roger@nextmovesoftware.com> To: <gccpatches@gcc.gnu.org> Subject: [PATCH] PR treeoptimization/64992: (B << 2) != 0 is B when B is Boolean. Date: Mon, 8 Aug 2022 10:06:05 +0100 MessageID: <00ce01d8ab06$19113060$4b339120$@nextmovesoftware.com> MIMEVersion: 1.0 ContentType: multipart/mixed; boundary="=_NextPart_000_00CF_01D8AB0E.7AD59860" XMailer: Microsoft Outlook 16.0 ThreadIndex: AdirBaEKwGUos4itTrmBOpbgNtqTfw== ContentLanguage: engb XAntiAbuse: This header was added to track abuse, please include it with any abuse report XAntiAbuse: Primary Hostname  server.nextmovesoftware.com XAntiAbuse: Original Domain  gcc.gnu.org XAntiAbuse: Originator/Caller UID/GID  [47 12] / [47 12] XAntiAbuse: Sender Address Domain  nextmovesoftware.com XGetMessageSenderVia: server.nextmovesoftware.com: authenticated_id: roger@nextmovesoftware.com XAuthenticatedSender: server.nextmovesoftware.com: roger@nextmovesoftware.com XSource: XSourceArgs: XSourceDir: XSpamStatus: No, score=10.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_BARRACUDACENTRAL, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 XSpamCheckerVersion: SpamAssassin 3.4.6 (20210409) on server2.sourceware.org XBeenThere: gccpatches@gcc.gnu.org XMailmanVersion: 2.1.29 Precedence: list ListId: Gccpatches mailing list <gccpatches.gcc.gnu.org> ListUnsubscribe: <https://gcc.gnu.org/mailman/options/gccpatches>, <mailto:gccpatchesrequest@gcc.gnu.org?subject=unsubscribe> ListArchive: <https://gcc.gnu.org/pipermail/gccpatches/> ListPost: <mailto:gccpatches@gcc.gnu.org> ListHelp: <mailto:gccpatchesrequest@gcc.gnu.org?subject=help> ListSubscribe: <https://gcc.gnu.org/mailman/listinfo/gccpatches>, <mailto:gccpatchesrequest@gcc.gnu.org?subject=subscribe> Cc: 'Andrew Pinski' <apinski@marvell.com> ErrorsTo: gccpatchesbounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gccpatches" <gccpatchesbounces+patchwork=sourceware.org@gcc.gnu.org> 
Series 
PR treeoptimization/64992: (B << 2) != 0 is B when B is Boolean.


Commit Message
Roger Sayle
Aug. 8, 2022, 9:06 a.m. UTC
This patch resolves both PR treeoptimization/64992 and PR treeoptimization/98956 which are missed optimization enhancement request, for which Andrew Pinski already has a proposed solution (related to a fix for PR treeoptimization/98954). Yesterday, I proposed an alternate improved patch for PR98954, which although superior in most respects, alas didn't address this case [which doesn't include a BIT_AND_EXPR], hence this followup fix. For many functions, F(B), of a (zeroone) Boolean value B, the expression F(B) != 0 can often be simplified to just B. Hence "(B * 5) != 0" is B, "B != 0" is B, "bswap(B) != 0" is B, "(B >>r 3) != 0" is B. These are all currently optimized by GCC, with the strange exception of left shifts by a constant (possibly due to the undefined/implementation defined behaviour when the shift constant is larger than the first operand's precision). This patch adds support for this particular case, when the shift constant is valid. This patch has been tested on x86_64pclinuxgnu with make bootstrap and make k check, both with and without target_board=unix{m32}, with no new failures. Ok for mainline? 20220808 Roger Sayle <roger@nextmovesoftware.com> gcc/ChangeLog PR treeoptimization/64992 PR treeoptimization/98956 * match.pd (ne (lshift @0 @1) 0): Simplify (X << C) != 0 to X when X is zero_one_valued_p and the shift constant C is valid. (eq (lshift @0 @1) 0): Likewise, simplify (X << C) == 0 to !X when X is zero_one_valued_p and the shift constant C is valid. gcc/testsuite/ChangeLog PR treeoptimization/64992 * gcc.dg/pr64992.c: New test case. Thanks in advance, Roger 
Comments
On Mon, Aug 8, 2022 at 11:06 AM Roger Sayle <roger@nextmovesoftware.com> wrote: > > > This patch resolves both PR treeoptimization/64992 and PR > treeoptimization/98956 which are missed optimization enhancement > request, for which Andrew Pinski already has a proposed solution > (related to a fix for PR treeoptimization/98954). Yesterday, > I proposed an alternate improved patch for PR98954, which although > superior in most respects, alas didn't address this case [which > doesn't include a BIT_AND_EXPR], hence this followup fix. > > For many functions, F(B), of a (zeroone) Boolean value B, the > expression F(B) != 0 can often be simplified to just B. Hence > "(B * 5) != 0" is B, "B != 0" is B, "bswap(B) != 0" is B, > "(B >>r 3) != 0" is B. These are all currently optimized by GCC, > with the strange exception of left shifts by a constant (possibly > due to the undefined/implementation defined behaviour when the > shift constant is larger than the first operand's precision). > This patch adds support for this particular case, when the shift > constant is valid. > > This patch has been tested on x86_64pclinuxgnu with make bootstrap > and make k check, both with and without target_board=unix{m32}, > with no new failures. Ok for mainline? +/* (X << C) != 0 can be simplified to X, when X is zero_one_valued_p. */ +(simplify + (ne (lshift zero_one_valued_p@0 INTEGER_CST@1) integer_zerop@2) + (if (tree_fits_shwi_p (@1) + && tree_to_shwi (@1) > 0 + && tree_to_shwi (@1) < TYPE_PRECISION (TREE_TYPE (@0))) + (convert @0))) while we deliberately do not fold int << 34 since the result is undefined there is IMHO no reason to not fold the above for any (even nonconstant) shift value. We have guards with TYPE_OVERFLOW_SANITIZED in some cases but I think that's not appropriate here, there's one flag_sanitize check, maybe there's a special bit for SHIFT overflow we can use. Why is (X << 0) != 0 excempt in the condition? > > 20220808 Roger Sayle <roger@nextmovesoftware.com> > > gcc/ChangeLog > PR treeoptimization/64992 > PR treeoptimization/98956 > * match.pd (ne (lshift @0 @1) 0): Simplify (X << C) != 0 to X > when X is zero_one_valued_p and the shift constant C is valid. > (eq (lshift @0 @1) 0): Likewise, simplify (X << C) == 0 to !X > when X is zero_one_valued_p and the shift constant C is valid. > > gcc/testsuite/ChangeLog > PR treeoptimization/64992 > * gcc.dg/pr64992.c: New test case. > > > Thanks in advance, > Roger >  >
Hi Richard, > Original Message > From: Richard Biener <richard.guenther@gmail.com> > Sent: 08 August 2022 12:49 > Subject: Re: [PATCH] PR treeoptimization/64992: (B << 2) != 0 is B when B is > Boolean. > > On Mon, Aug 8, 2022 at 11:06 AM Roger Sayle > <roger@nextmovesoftware.com> wrote: > > > > This patch resolves both PR treeoptimization/64992 and PR > > treeoptimization/98956 which are missed optimization enhancement > > request, for which Andrew Pinski already has a proposed solution > > (related to a fix for PR treeoptimization/98954). Yesterday, I > > proposed an alternate improved patch for PR98954, which although > > superior in most respects, alas didn't address this case [which > > doesn't include a BIT_AND_EXPR], hence this followup fix. > > > > For many functions, F(B), of a (zeroone) Boolean value B, the > > expression F(B) != 0 can often be simplified to just B. Hence "(B * > > 5) != 0" is B, "B != 0" is B, "bswap(B) != 0" is B, "(B >>r 3) != 0" > > is B. These are all currently optimized by GCC, with the strange > > exception of left shifts by a constant (possibly due to the > > undefined/implementation defined behaviour when the shift constant is > > larger than the first operand's precision). > > This patch adds support for this particular case, when the shift > > constant is valid. > > > > This patch has been tested on x86_64pclinuxgnu with make bootstrap > > and make k check, both with and without target_board=unix{m32}, > > with no new failures. Ok for mainline? > > +/* (X << C) != 0 can be simplified to X, when X is zero_one_valued_p. > +*/ (simplify > + (ne (lshift zero_one_valued_p@0 INTEGER_CST@1) integer_zerop@2) > + (if (tree_fits_shwi_p (@1) > + && tree_to_shwi (@1) > 0 > + && tree_to_shwi (@1) < TYPE_PRECISION (TREE_TYPE (@0))) > + (convert @0))) > > while we deliberately do not fold int << 34 since the result is undefined there is > IMHO no reason to not fold the above for any (even nonconstant) shift value. > We have guards with TYPE_OVERFLOW_SANITIZED in some cases but I think > that's not appropriate here, there's one flag_sanitize check, maybe there's a > special bit for SHIFT overflow we can use. Why is (X << 0) != 0 excempt in the > condition? In this case, I think it makes more sense to err on the side of caution, and avoid changing the observable behaviour of programs, even in cases were the behaviour is officially undefined. For many targets, (1<<x) != 0 is indeed always true for any value of x, but a counter example are x86's SSE shifts, where shifts beyond the size of the vector result in zero. With STV, this means that (1<<258) != 0 has a different value if performed as scalar vs. performed as vector. Worse, one may end up with examples, where based upon optimization level, we see different results as shift operands become propagated constants in some paths, but was variable shifts others. Hence my personal preference is "first, do no harm" and limit this transformation to the safe 0 <= X < MODE_PRECISION (mode). Then given we'd like to avoid negative shifts, and therefore need to test against zero, my second preference is "0 < X" over "0 <= X". If the RTL contains a shift by zero, something strange is already going on (these should be caught optimized elsewhere), and it's better to leave these issues visible in the RTL, than paper over any "latent" mistakes. I fully I agree that this optimization could be more aggressive, but that isn't required to resolve this PR, and resolving PR64992 only to open the door for followup "unexpected behavior" PRs isn't great progress. Thoughts? Ok for mainline? > > 20220808 Roger Sayle <roger@nextmovesoftware.com> > > > > gcc/ChangeLog > > PR treeoptimization/64992 > > PR treeoptimization/98956 > > * match.pd (ne (lshift @0 @1) 0): Simplify (X << C) != 0 to X > > when X is zero_one_valued_p and the shift constant C is valid. > > (eq (lshift @0 @1) 0): Likewise, simplify (X << C) == 0 to !X > > when X is zero_one_valued_p and the shift constant C is valid. > > > > gcc/testsuite/ChangeLog > > PR treeoptimization/64992 > > * gcc.dg/pr64992.c: New test case. > > Thanks, Roger 
On Sat, Aug 13, 2022 at 12:35 AM Roger Sayle <roger@nextmovesoftware.com> wrote: > > Hi Richard, > > > Original Message > > From: Richard Biener <richard.guenther@gmail.com> > > Sent: 08 August 2022 12:49 > > Subject: Re: [PATCH] PR treeoptimization/64992: (B << 2) != 0 is B when B is > > Boolean. > > > > On Mon, Aug 8, 2022 at 11:06 AM Roger Sayle > > <roger@nextmovesoftware.com> wrote: > > > > > > This patch resolves both PR treeoptimization/64992 and PR > > > treeoptimization/98956 which are missed optimization enhancement > > > request, for which Andrew Pinski already has a proposed solution > > > (related to a fix for PR treeoptimization/98954). Yesterday, I > > > proposed an alternate improved patch for PR98954, which although > > > superior in most respects, alas didn't address this case [which > > > doesn't include a BIT_AND_EXPR], hence this followup fix. > > > > > > For many functions, F(B), of a (zeroone) Boolean value B, the > > > expression F(B) != 0 can often be simplified to just B. Hence "(B * > > > 5) != 0" is B, "B != 0" is B, "bswap(B) != 0" is B, "(B >>r 3) != 0" > > > is B. These are all currently optimized by GCC, with the strange > > > exception of left shifts by a constant (possibly due to the > > > undefined/implementation defined behaviour when the shift constant is > > > larger than the first operand's precision). > > > This patch adds support for this particular case, when the shift > > > constant is valid. > > > > > > This patch has been tested on x86_64pclinuxgnu with make bootstrap > > > and make k check, both with and without target_board=unix{m32}, > > > with no new failures. Ok for mainline? > > > > +/* (X << C) != 0 can be simplified to X, when X is zero_one_valued_p. > > +*/ (simplify > > + (ne (lshift zero_one_valued_p@0 INTEGER_CST@1) integer_zerop@2) > > + (if (tree_fits_shwi_p (@1) > > + && tree_to_shwi (@1) > 0 > > + && tree_to_shwi (@1) < TYPE_PRECISION (TREE_TYPE (@0))) > > + (convert @0))) > > > > while we deliberately do not fold int << 34 since the result is undefined there is > > IMHO no reason to not fold the above for any (even nonconstant) shift value. > > We have guards with TYPE_OVERFLOW_SANITIZED in some cases but I think > > that's not appropriate here, there's one flag_sanitize check, maybe there's a > > special bit for SHIFT overflow we can use. Why is (X << 0) != 0 excempt in the > > condition? > > In this case, I think it makes more sense to err on the side of caution, and > avoid changing the observable behaviour of programs, even in cases were > the behaviour is officially undefined. For many targets, (1<<x) != 0 is indeed > always true for any value of x, but a counter example are x86's SSE shifts, > where shifts beyond the size of the vector result in zero. With STV, this > means that (1<<258) != 0 has a different value if performed as scalar vs. > performed as vector. Worse, one may end up with examples, where based > upon optimization level, we see different results as shift operands become > propagated constants in some paths, but was variable shifts others. > > Hence my personal preference is "first, do no harm" and limit this > transformation to the safe 0 <= X < MODE_PRECISION (mode). > Then given we'd like to avoid negative shifts, and therefore need to > test against zero, my second preference is "0 < X" over "0 <= X". > If the RTL contains a shift by zero, something strange is already going on > (these should be caught optimized elsewhere), and it's better to leave > these issues visible in the RTL, than paper over any "latent" mistakes. > > I fully I agree that this optimization could be more aggressive, but that > isn't required to resolve this PR, and resolving PR64992 only to open > the door for followup "unexpected behavior" PRs isn't great progress. > > Thoughts? Ok for mainline? OK  can you add a comment reflecting the above? An improvement might be to allow nonconstant operands but test sth like expr_in_range (@1, 1, TYPE_PRECISION (...)) we already have expr_not_equal_to, expr_in_range could be done with value_range vr; if (get_global_range_query ()>range_of_expr (vr, @0) && vr.kind () == VR_RANGE) { wide_int wmin0 = vr.lower_bound (); wide_int wmax0 = vr.upper_bound (); ... there's a bunch of range_of_expr uses, I didn't check closely but some might fit a new expr_in_range utility. That can be done as followup (if you like). Btw, I wonder if bitCCP would have not simplified the shiftbyconstant compared to zero as well? If so, does that behave the same with respect to 0 or out of bound shifts? Richard. > > > > 20220808 Roger Sayle <roger@nextmovesoftware.com> > > > > > > gcc/ChangeLog > > > PR treeoptimization/64992 > > > PR treeoptimization/98956 > > > * match.pd (ne (lshift @0 @1) 0): Simplify (X << C) != 0 to X > > > when X is zero_one_valued_p and the shift constant C is valid. > > > (eq (lshift @0 @1) 0): Likewise, simplify (X << C) == 0 to !X > > > when X is zero_one_valued_p and the shift constant C is valid. > > > > > > gcc/testsuite/ChangeLog > > > PR treeoptimization/64992 > > > * gcc.dg/pr64992.c: New test case. > > > > > Thanks, > Roger >  > >
diff git a/gcc/match.pd b/gcc/match.pd index f82f94a..ef6d8e2 100644  a/gcc/match.pd +++ b/gcc/match.pd @@ 1900,6 +1900,22 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) && TYPE_PRECISION (type) <= TYPE_PRECISION (TREE_TYPE (@0))) (mult (convert @1) (convert @2)))) +/* (X << C) != 0 can be simplified to X, when X is zero_one_valued_p. */ +(simplify + (ne (lshift zero_one_valued_p@0 INTEGER_CST@1) integer_zerop@2) + (if (tree_fits_shwi_p (@1) + && tree_to_shwi (@1) > 0 + && tree_to_shwi (@1) < TYPE_PRECISION (TREE_TYPE (@0))) + (convert @0))) + +/* (X << C) == 0 can be simplified to X == 0, when X is zero_one_valued_p. */ +(simplify + (eq (lshift zero_one_valued_p@0 INTEGER_CST@1) integer_zerop@2) + (if (tree_fits_shwi_p (@1) + && tree_to_shwi (@1) > 0 + && tree_to_shwi (@1) < TYPE_PRECISION (TREE_TYPE (@0))) + (eq @0 @2))) + /* Convert ~ (A) to A  1. */ (simplify (bit_not (convert? (negate @0))) diff git a/gcc/testsuite/gcc.dg/pr64992.c b/gcc/testsuite/gcc.dg/pr64992.c new file mode 100644 index 0000000..43fbcf7  /dev/null +++ b/gcc/testsuite/gcc.dg/pr64992.c @@ 0,0 +1,7 @@ +/* { dgdo compile } */ +/* { dgoptions "O2 fdumptreeoptimized" } */ + +_Bool foo(_Bool x) { return (x << 2) != 0; } +_Bool bar(_Bool x) { return (x << 2) == 0; } + +/* { dgfinal { scantreedumpnot " << " "optimized" } } */