From patchwork Fri Jun 24 15:09:36 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 1648044 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=nextmovesoftware.com header.i=@nextmovesoftware.com header.a=rsa-sha256 header.s=default header.b=PJYuoHDW; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4LV0sc0C5Mz9s1l for ; Sat, 25 Jun 2022 01:09:55 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4D07538418BC for ; Fri, 24 Jun 2022 15:09:51 +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 B1394386F0CB for ; Fri, 24 Jun 2022 15:09:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org B1394386F0CB 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:To:From:Sender:Reply-To:Cc:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=G/TNxniyweurXR++0fQ3fzvkkbUmL4jKLs/AWINlTY8=; b=PJYuoHDWkEKd01IrbpHLwJIiSl aYpWgvPlt0IaC9AwTz9t2ZjxuIwUYI0oaqqY3VqeXO1aZIp6DVyjUvLHQKVInbPi9ELKlGkWgwaFb +I/L+9itp83ciilzBl628oKXLB4Quq1M8Fd97zAufyS/gJ7TNtejleLidkwRc6WHDnwDb1XzL1hAa nAu74Wgf5PtuMbDVbSb5EYtbRrOS2UkVZTMKeFVkxne0ASaNqTWDg+igOzKlcjChFIWCpr6ZAcFwI yk3BiOI67hiQXlqPr6xDaVTf/qqVFRejOU9Yh5iM4qzywSIjDX1NKmTjqlneefaKNULTYUIqR7pZt DOl9Qs/g==; Received: from [185.62.158.67] (port=56235 helo=Dell) by server.nextmovesoftware.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1o4kwC-0006L6-TV for gcc-patches@gcc.gnu.org; Fri, 24 Jun 2022 11:09:37 -0400 From: "Roger Sayle" To: Subject: [PATCH] PR tree-optimization/94026: Simplify (X>>8)&6 != 0 as X&1536 != 0. Date: Fri, 24 Jun 2022 16:09:36 +0100 Message-ID: <009201d887dc$6b83e330$428ba990$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AdiH21ECd3yGI1TXTk6eH2qRIqZSFg== 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+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch implements the missed optimization described in PR 94026, where a the shift can be eliminated from the sequence of a shift, followed by a bit-wise AND followed by an equality/inequality test. Specifically, ((X << C1) & C2) cmp C3 into (X & (C2 >> C1)) cmp (C3 >> C1) and likewise ((X >> C1) & C2) cmp C3 into (X & (C2 << C1)) cmp (C3 << C1) where cmp is == or !=, and C1, C2 and C3 are integer constants. The example in the subject line is taken from the hot function self_atari from the Go program Leela (in SPEC CPU 2017). 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? 2022-06-24 Roger Sayle gcc/ChangeLog PR tree-optimization/94026 * match.pd (((X << C1) & C2) eq/ne C3): New simplification. (((X >> C1) & C2) eq/ne C3): Likewise. gcc/testsuite/ChangeLog PR tree-optimization/94026 * gcc.dg/pr94026.c: New test case. Thanks in advance, Roger diff --git a/gcc/match.pd b/gcc/match.pd index a63b649..5089b07 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -3559,6 +3559,29 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) && wi::lshift (wi::to_wide (@0), cand) == wi::to_wide (@2)) (cmp @1 { build_int_cst (TREE_TYPE (@1), cand); })))))) +/* Fold ((X << C1) & C2) cmp C3 into (X & (C2 >> C1)) cmp (C3 >> C1) + ((X >> C1) & C2) cmp C3 into (X & (C2 << C1)) cmp (C3 << C1). */ +(for cmp (ne eq) + (simplify + (cmp (bit_and:s (lshift:s @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3) + (if (tree_fits_shwi_p (@1) + && tree_to_shwi (@1) > 0 + && tree_to_shwi (@1) < TYPE_PRECISION (TREE_TYPE (@0)) + && tree_to_shwi (@1) <= wi::ctz (wi::to_wide (@3))) + (with { wide_int c1 = wi::to_wide (@1); + wide_int c2 = wi::lrshift (wi::to_wide (@2), c1); + wide_int c3 = wi::lrshift (wi::to_wide (@3), c1); } + (cmp (bit_and @0 { wide_int_to_tree (TREE_TYPE (@0), c2); }) + { wide_int_to_tree (TREE_TYPE (@0), c3); })))) + (simplify + (cmp (bit_and:s (rshift:s @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3) + (if (tree_fits_shwi_p (@1) + && tree_to_shwi (@1) > 0 + && tree_to_shwi (@1) < TYPE_PRECISION (TREE_TYPE (@0)) + && tree_to_shwi (@1) <= wi::clz (wi::to_wide (@2)) + && tree_to_shwi (@1) <= wi::clz (wi::to_wide (@3))) + (cmp (bit_and @0 (lshift @2 @1)) (lshift @3 @1))))) + /* Fold (X << C1) & C2 into (X << C1) & (C2 | ((1 << C1) - 1)) (X >> C1) & C2 into (X >> C1) & (C2 | ~((type) -1 >> C1)) if the new mask might be further optimized. */ diff --git a/gcc/testsuite/gcc.dg/pr94026.c b/gcc/testsuite/gcc.dg/pr94026.c new file mode 100644 index 0000000..489b978 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr94026.c @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int f1(int x) { return ((x >> 8) & 6) != 0; } +int f2(int x) { return ((x << 2) & 24) != 0; } +int f3(unsigned x) { return ((x << 2) & 15) != 0; } +int f4(unsigned x) { return ((x >> 2) & 14) != 0; } + +int fifth (int c) +{ + int a = (c >> 8) & 7; + + if (a >= 2) { + return 1; + } else { + return 0; + } +} +/* { dg-final { scan-tree-dump-not " << " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " >> " "optimized" } } */ +