From patchwork Thu Aug 12 09:52:08 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 1516237 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=OyHVyymK; 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 4GlhnN4Rtdz9sX1 for ; Thu, 12 Aug 2021 19:52:39 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 81C8D3886C77 for ; Thu, 12 Aug 2021 09:52:33 +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 6604C3836401 for ; Thu, 12 Aug 2021 09:52:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6604C3836401 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=se4Iuqr2RRJbgse9SA9QIL8CbtCH2uKpnkuVzZVW438=; b=OyHVyymK3D79Nb6tO/J7+xwPdv z494V3krnVlfdjC8Q6Vtk/rpGGbKNJ3H7Q+dvmeZKBN8cgCL5ZUk6s+GTmhX58ZmfA191x1heSamT nmyjToIzhSxs0qQLjHetn7ISyi6MwAHFUv/bF1mf+vWiDmJ+BVeZLZhlLlm0QQ8wOJv4ZSAT9htQf 40E8VB+gUbxzaiN5t+iue/NwfxfLqhFCn6Qkusecm1bOef/JJlEnaBsXt1jwrb2M5QwXoqU/H3e6s DBTXPbnEtUSlEEGwxbR1QUx3/YnJvr0r89q5k7IAs7z3szAmkIXS1HwtergPPWdC4iiN3Go2I2syB fJfMW9JA==; Received: from host109-154-46-127.range109-154.btcentralplus.com ([109.154.46.127]:53218 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 1mE7Ni-0002MV-Lz for gcc-patches@gcc.gnu.org; Thu, 12 Aug 2021 05:52:10 -0400 From: "Roger Sayle" To: "'GCC Patches'" Subject: [PATCH] Improved handling of MINUS_EXPR in bit CCP. Date: Thu, 12 Aug 2021 10:52:08 +0100 Message-ID: <050001d78f5f$b7d650e0$2782f2a0$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AdePXtzndYFvKdAsTLqcPpAFfaOdeg== 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.2 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 improves the bit bounds for MINUS_EXPR during tree-ssa's conditional constant propagation (CCP) pass (and as an added bonus adds support for POINTER_DIFF_EXPR). The pessimistic assumptions made by the current algorithm are demonstrated by considering 1 - (x&1). Intuitively this should have possible values 0 and 1, and therefore an unknown mask of 1. Alas by treating subtraction as a negation followed by addition, the second operand first becomes 0 or -1, with an unknown mask of all ones, which results in the addition containing no known bits. Improved bounds are achieved by using the same approach used for PLUS_EXPR, determining the result with the minimum number of borrows, the result from the maximum number of borrows, and examining the bits they have in common. One additional benefit of this approach is that it is applicable to POINTER_DIFF_EXPR, where previously the negation of a pointer didn't/doesn't make sense. A more convincing example, where a transformation missed by .032t.cpp isn't caught a few passes later by .038t.evrp, is the expression (7 - (x&5)) & 2, which (in the new test case) currently survives the tree-level optimizers but with this patch is now simplified to the constant value 2. This patch has been tested on x86_64-pc-linux-gnu with "make bootstrap" and "make -k check" with no new failures. Ok for mainline? 2021-08-12 Roger Sayle gcc/ChangeLog * tree-ssa-ccp.c (bit_value_binop) [MINUS_EXPR]: Use same algorithm as PLUS_EXPR to improve subtraction bit bounds. [POINTER_DIFF_EXPR]: Treat as synonymous with MINUS_EXPR. gcc/testsuite/ChangeLog * gcc.dg/tree-ssa/ssa-ccp-40.c: New test case. Roger --- Roger Sayle NextMove Software Cambridge, UK /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ int foo(int x) { int p = 7; int q = p - (x & 5); return q & 2; } /* { dg-final { scan-tree-dump "return 2;" "optimized" } } */ diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c index 003c9c2..1223370 100644 --- a/gcc/tree-ssa-ccp.c +++ b/gcc/tree-ssa-ccp.c @@ -1398,7 +1398,7 @@ bit_value_binop (enum tree_code code, signop sgn, int width, widest_int *val, widest_int *mask, signop r1type_sgn, int r1type_precision, const widest_int &r1val, const widest_int &r1mask, - signop r2type_sgn, int r2type_precision, + signop r2type_sgn, int r2type_precision ATTRIBUTE_UNUSED, const widest_int &r2val, const widest_int &r2mask) { bool swap_p = false; @@ -1445,7 +1445,7 @@ bit_value_binop (enum tree_code code, signop sgn, int width, } else { - if (wi::neg_p (shift)) + if (wi::neg_p (shift, r2type_sgn)) { shift = -shift; if (code == RROTATE_EXPR) @@ -1482,7 +1482,7 @@ bit_value_binop (enum tree_code code, signop sgn, int width, } else { - if (wi::neg_p (shift)) + if (wi::neg_p (shift, r2type_sgn)) break; if (code == RSHIFT_EXPR) { @@ -1522,13 +1522,16 @@ bit_value_binop (enum tree_code code, signop sgn, int width, } case MINUS_EXPR: + case POINTER_DIFF_EXPR: { - widest_int temv, temm; - bit_value_unop (NEGATE_EXPR, r2type_sgn, r2type_precision, &temv, &temm, - r2type_sgn, r2type_precision, r2val, r2mask); - bit_value_binop (PLUS_EXPR, sgn, width, val, mask, - r1type_sgn, r1type_precision, r1val, r1mask, - r2type_sgn, r2type_precision, temv, temm); + /* Subtraction is derived from the addition algorithm above. */ + widest_int lo = wi::bit_and_not (r1val, r1mask) - (r2val | r2mask); + lo = wi::ext (lo, width, sgn); + widest_int hi = (r1val | r1mask) - wi::bit_and_not (r2val, r2mask); + hi = wi::ext (hi, width, sgn); + *mask = r1mask | r2mask | (lo ^ hi); + *mask = wi::ext (*mask, width, sgn); + *val = lo; break; }