From patchwork Sun Jul 18 10:16:51 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 1506576 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: 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=QaHiu9Ys; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GSLWS2j5kz9sW8 for ; Sun, 18 Jul 2021 20:17:22 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 001BB388A839 for ; Sun, 18 Jul 2021 10:17:18 +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 A30A33838024 for ; Sun, 18 Jul 2021 10:16:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A30A33838024 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=OQqv1bUGYHv6NLxdxLE205cIgDuNykZuQCRHFdoMqXk=; b=QaHiu9YsRZrsvBY1aWEAy+l43E s6HekGUXoI2an/EHUKlU7TIUlhDL5eQcvH1Rag7/DJIgNITD9Onh8JxInTwnz7AdWRjfZWvfaqj6z 36YKz6VLphFRt47VoRDCncnMT3xc08xxOQGfBcpuSF5Wb869x4J4f1FUO6w18Dc6fDQRgT1UWoQiG 6FppuRictwyolld2YEf4TSFXeSTpgUMbMPLlULdDf+NjdfasCjQTVszaUR1YPxAUfTBEU/nL8JyoN KR2VxCC0dkUsZkE2TPrHsGyj2Upfgopih9hoET4fEGslrUFtsfEdsQ7YQx5O9g7XE2MlasArnnsvP 1Uu1dgzg==; Received: from host86-169-60-32.range86-169.btcentralplus.com ([86.169.60.32]:49838 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 1m53qv-0002EZ-Rw for gcc-patches@gcc.gnu.org; Sun, 18 Jul 2021 06:16:54 -0400 From: "Roger Sayle" To: "'GCC Patches'" Subject: [PATCH] Fold bswap32(x) != 0 to x != 0 (and related transforms) Date: Sun, 18 Jul 2021 11:16:51 +0100 Message-ID: <013801d77bbe$077aa5c0$166ff140$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: Add7vPNNY6s9UOgkSQ+L7JRuDNE69A== 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.6 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 autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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 to match.pd implements several closely related folding simplifications at the tree-level, that make use of the property that bit permutation functions, rotate and bswap have inverses. [1] bswap(X) eq/ne C, for constant C, simplifies to X eq/ne C' where C'=bswap(C), generalizing the transform in the subject. [2] bswap(X) eq/ne bswap(Y) simplifies to X eq/ne Y. [3] lrotate(X,C1) eq/ne C2 simplifies to X eq/ne C3, where C3 = rrotate(C2,C1), i.e. apply the inverse rotation to C2. [4] Likewise, rrotate(X,C1) eq/ne C2 simplifies to X eq/ne C3, where C3 = lrotate(C2,C1). [5] rotate(X,Z) eq/ne rotate(Y,Z) simplifies to X eq/ne Y, when the bit-count Z (the same on both sides) has no side-effects. [6] rotate(X,Y) eq/ne 0 simplifies to X eq/ne 0 if Y has no side-effects. [7] Likewise, rotate(X,Y) eq/ne -1 simplifies to X eq/ne -1, if Y has no side-effects. This patch has been tested on x86_64-pc-linux-gnu with a "make bootstrap" and "make -k check" with no new failures. Ok for mainline? 2010-07-18 Roger Sayle gcc/ChangeLog * match.pd (rotate): Simplify equality/inequality of rotations. (bswap): Simplify equality/inequality tests of byte swapping. gcc/testsuite/ChangeLog * gcc.dg/fold-eqrotate-1.c: New test case. * gcc.dg/fold-eqbswap-1.c: New test case. Roger --- Roger Sayle NextMove Software Cambridge, UK /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ int test1(int x, int y) { #if __SIZEOF_INT__ == 4 return __builtin_bswap32(x) == __builtin_bswap32(y); #else return x == y; #endif } int test2(int x, int y) { #if __SIZEOF_INT__ == 4 return __builtin_bswap32(x) != __builtin_bswap32(y); #else return x != y; #endif } int test3(int x) { #if __SIZEOF_INT__ == 4 return __builtin_bswap32(x) == 12345; #else return x; #endif } int test4(int x) { #if __SIZEOF_INT__ == 4 return __builtin_bswap32(x) != 12345; #else return x; #endif } int test1ll(long long x, long long y) { #if __SIZEOF_LONG_LONG__ == 8 return __builtin_bswap64(x) == __builtin_bswap64(y); #else return x == y; #endif } int test2ll(long long x, long long y) { #if __SIZEOF_LONG_LONG__ == 8 return __builtin_bswap64(x) != __builtin_bswap64(y); #else return x != y; #endif } int test3ll(long long x) { #if __SIZEOF_LONG_LONG__ == 8 return __builtin_bswap64(x) == 12345; #else return (int)x; #endif } int test4ll(long long x) { #if __SIZEOF_LONG_LONG__ == 8 return __builtin_bswap64(x) != 12345; #else return (int)x; #endif } int test1s(short x, short y) { #if __SIZEOF_SHORT__ == 2 return __builtin_bswap16(x) == __builtin_bswap16(y); #else return x == y; #endif } int test2s(short x, short y) { #if __SIZEOF_SHORT__ == 2 return __builtin_bswap16(x) != __builtin_bswap16(y); #else return x != y; #endif } int test3s(short x) { #if __SIZEOF_SHORT__ == 2 return __builtin_bswap16(x) == 12345; #else return (int)x; #endif } int test4s(short x) { #if __SIZEOF_SHORT__ == 2 return __builtin_bswap16(x) != 12345; #else return (int)x; #endif } /* { dg-final { scan-tree-dump-times "__builtin_bswap" 0 "optimized" } } */ /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ int test1(unsigned int x, unsigned int y) { #if __SIZEOF_INT__ == 4 unsigned int r1 = (x << 16) | (x >> 16); unsigned int r2 = (y << 16) | (y >> 16); return r1 == r2; #else return x == y; #endif } int test2(unsigned int x) { #if __SIZEOF_INT__ == 4 unsigned int r1 = (x << 16) | (x >> 16); return r1 == 12345; #else return x == 12345; #endif } int test3(unsigned int x) { #if __SIZEOF_INT__ == 4 unsigned int r1 = (x << 16) | (x >> 16); return r1 == 0; #else return x == 0; #endif } int test4(unsigned int x) { #if __SIZEOF_INT__ == 4 unsigned int r1 = (x << 16) | (x >> 16); return r1 == ~0; #else return x == ~0; #endif } /* { dg-final { scan-tree-dump-times "r>>" 0 "optimized" } } */ diff --git a/gcc/match.pd b/gcc/match.pd index beb8d27..aa850bb 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -3312,6 +3312,25 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) { tree rotate_type = TREE_TYPE (@0); } (convert (rotate (convert:rotate_type @1) @2)))))) +(for cmp (eq ne) + (for rotate (lrotate rrotate) + invrot (rrotate lrotate) + /* (X >>r Y) cmp (Z >>r Y) may simplify to X cmp Y. */ + (simplify + (cmp (rotate @1 @0) (rotate @2 @0)) + (if (GIMPLE || !TREE_SIDE_EFFECTS (@0)) + (cmp @1 @2))) + /* (X >>r C1) cmp C2 may simplify to X cmp C3. */ + (simplify + (cmp (rotate @0 INTEGER_CST@1) INTEGER_CST@2) + (cmp @0 { const_binop (invrot, TREE_TYPE (@0), @2, @1); })) + /* (X >>r Y) cmp C where C is 0 or ~0, may simplify to X cmp C. */ + (simplify + (cmp (rotate @0 @1) INTEGER_CST@2) + (if ((GIMPLE || !TREE_SIDE_EFFECTS (@1)) + && (integer_zerop (@2) || integer_all_onesp (@2))) + (cmp @0 @2))))) + /* Simplifications of conversions. */ /* Basic strip-useless-type-conversions / strip_nops. */ @@ -3622,6 +3641,13 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (simplify (bswap (bitop:c (bswap @0) @1)) (bitop @0 (bswap @1)))) + (for cmp (eq ne) + (simplify + (cmp (bswap @0) (bswap @1)) + (cmp @0 @1)) + (simplify + (cmp (bswap @0) INTEGER_CST@1) + (cmp @0 (bswap @1)))) /* (bswap(x) >> C1) & C2 can sometimes be simplified to (x >> C3) & C2. */ (simplify (bit_and (convert1? (rshift@0 (convert2? (bswap@4 @1)) INTEGER_CST@2))