From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 477243858D32 for ; Thu, 7 Jul 2022 13:59:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 477243858D32 Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-548-PEyNQ1uWNwWZA00KHHcgAw-1; Thu, 07 Jul 2022 09:59:45 -0400 X-MC-Unique: PEyNQ1uWNwWZA00KHHcgAw-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.rdu2.redhat.com [10.11.54.7]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id D46DB1019C8A for ; Thu, 7 Jul 2022 13:59:44 +0000 (UTC) Received: from sfeifer.remote.csb (unknown [10.22.18.61]) by smtp.corp.redhat.com (Postfix) with ESMTP id B66791415117 for ; Thu, 7 Jul 2022 13:59:44 +0000 (UTC) From: Sam Feifer To: gcc-patches@gcc.gnu.org Subject: [PATCH] match.pd: Add new bitwise arithmetic pattern [PR98304] Date: Thu, 7 Jul 2022 09:59:35 -0400 Message-Id: <20220707135935.2249978-1-sfeifer@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.85 on 10.11.54.7 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-13.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, 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: Thu, 07 Jul 2022 13:59:48 -0000 Hi! This patch is meant to solve a missed optimization in match.pd. It optimizes the following expression: n - (((n > 63) ? n : 63) & -64) where the constant being negated (in this case -64) is a power of 2 and the sum of the two constants is -1. For the signed case, this gets optimized to (n <= 63) ? n : (n & 63). For the unsigned case, it gets optimized to (n & 63). In both scenarios, the number of instructions produced decreases. There are also tests for this optimization making sure the optimization happens when it is supposed to, and does not happen when it isn't. Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk? PR tree-optimization/98304 gcc/ChangeLog: * match.pd (n - (((n > C1) ? n : C1) & -C2)): New simplification. gcc/testsuite/ChangeLog: * gcc.c-torture/execute/pr98304-2.c: New test. * gcc.dg/pr98304-1.c: New test. --- gcc/match.pd | 12 ++++ .../gcc.c-torture/execute/pr98304-2.c | 37 ++++++++++++ gcc/testsuite/gcc.dg/pr98304-1.c | 57 +++++++++++++++++++ 3 files changed, 106 insertions(+) create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr98304-2.c create mode 100644 gcc/testsuite/gcc.dg/pr98304-1.c diff --git a/gcc/match.pd b/gcc/match.pd index 88c6c414881..45aefd96688 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -7836,3 +7836,15 @@ and, (match (bitwise_induction_p @0 @2 @3) (bit_not (nop_convert1? (bit_xor@0 (convert2? (lshift integer_onep@1 @2)) @3)))) + +/* n - (((n > C1) ? n : C1) & -C2) -> n & C1 for unsigned case. + n - (((n > C1) ? n : C1) & -C2) -> (n <= C1) ? n : (n & C1) for signed case. */ +(simplify + (minus @0 (bit_and (max @0 INTEGER_CST@1) INTEGER_CST@2)) + (with { auto i = wi::neg (wi::to_wide (@2)); } + /* Check if -C2 is a power of 2 and C1 = -C2 - 1. */ + (if (wi::popcount (i) == 1 + && (wi::to_wide (@1)) == (i - 1)) + (if (TYPE_UNSIGNED (TREE_TYPE (@0))) + (bit_and @0 @1) + (cond (le @0 @1) @0 (bit_and @0 @1)))))) diff --git a/gcc/testsuite/gcc.c-torture/execute/pr98304-2.c b/gcc/testsuite/gcc.c-torture/execute/pr98304-2.c new file mode 100644 index 00000000000..114c612db3b --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr98304-2.c @@ -0,0 +1,37 @@ +/* PR tree-optimization/98304 */ + +#include "../../gcc.dg/pr98304-1.c" + +/* Runtime tests. */ +int main() { + + /* Signed tests. */ + if (foo(-42) != -42 + || foo(0) != 0 + || foo(63) != 63 + || foo(64) != 0 + || foo(65) != 1 + || foo(99) != 35) { + __builtin_abort(); + } + + /* Unsigned tests. */ + if (bar(42) != 42 + || bar(0) != 0 + || bar(63) != 63 + || bar(64) != 0 + || bar(65) != 1 + || bar(99) != 35) { + __builtin_abort(); + } + + /* Should not simplify. */ + if (corge(13) != 13 + || thud(13) != 13 + || qux(13) != 13 + || quux(13) != 13) { + __builtin_abort(); + } + + return 0; +} diff --git a/gcc/testsuite/gcc.dg/pr98304-1.c b/gcc/testsuite/gcc.dg/pr98304-1.c new file mode 100644 index 00000000000..dce54ddffe8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr98304-1.c @@ -0,0 +1,57 @@ +/* PR tree-optimization/98304 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* Signed test function. */ +__attribute__((noipa)) int foo(int n) { + return n - (((n > 63) ? n : 63) & -64); +} + +/* Unsigned test function. */ +__attribute__((noipa)) unsigned int bar(unsigned int n) { + return n - (((n > 63) ? n : 63) & -64); +} + +/* Different power of 2. */ +__attribute__((noipa)) int goo(int n) { + return n - (((n > 31) ? n : 31) & -32); +} + +/* Commutative property (should be identical to foo) */ +__attribute__((noipa)) int baz(int n) { + return n - (((64 > n) ? 63 : n) & -64); +} + +/* < instead of >. */ +__attribute__((noipa)) int fred(int n) { + return n - (((63 < n) ? n : 63) & -64); +} + +/* Constant is not a power of 2 so should not simplify. */ +__attribute__((noipa)) int qux(int n) { + return n - (((n > 62) ? n : 62) & -63); +} + +/* Constant is not a power of 2 so should not simplify. */ +__attribute__((noipa)) unsigned int quux(unsigned int n) { + return n - (((n > 62) ? n : 62) & -63); +} + +/* Constant is a variable so should not simplify. */ +__attribute__((noipa)) int waldo(int n, int x) { + return n - (((n > 63) ? n : 63) & x); +} + +/* Difference between constants is not -1. */ +__attribute__((noipa)) int corge(int n) { + return n - (((n > 1) ? n : 1) & -64); +} + +/* Difference between constants is not -1. */ +__attribute__((noipa)) unsigned int thud(unsigned int n) +{ + return n - (((n > 1) ? n : 1) & -64); +} + +/* { dg-final { scan-tree-dump-times " - " 5 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " <= " 4 "optimized" } } */ base-commit: a8b5d63503b8cf49de32d241218057409f8731ac -- 2.31.1