From patchwork Sun Aug 8 10:42:44 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 1514785 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=8.43.85.97; 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=nHpnjOBo; dkim-atps=neutral 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 (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GjG5d4PJ3z9sWl for ; Sun, 8 Aug 2021 20:43:15 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E99AD389103E for ; Sun, 8 Aug 2021 10:43:11 +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 DB7A23858018 for ; Sun, 8 Aug 2021 10:42:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DB7A23858018 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=Ur65FlD/uJ/44npZlx3LlIKu4HuNBH8aVPHhmcaullM=; b=nHpnjOBokT4fonzEV3MwsumWoQ RD1Qdjb1NJOlwWMlQpw+e+vfWHrgA4JvinYjg3iMBOPXJtf+zaeqtf33GwIOmOQTdx4//bd3d9M18 gmOqPaDhaNGRm3uc+2UGrhIeBjVDk/w7uAQDUmOyi6LWSMiydOFiGUZu2TNEIqUemYu7hcc8rStak 77dT5kMJBwvL+sympvGug5dgWJ1nMFayDV9tQeZkJyTGPyjNkEVsO3U+0+rTWSJps7e6DLP23MrKZ OTULkLIJUfMqeWzfof3JwwusgIYF/tv32mpHdWYUkKuNfVEBqDlKtG87VWhgFaroxjISMcb64kH/A vFOZvwNA==; Received: from host109-154-46-127.range109-154.btcentralplus.com ([109.154.46.127]:50812 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 1mCgGV-0007wf-1Y for gcc-patches@gcc.gnu.org; Sun, 08 Aug 2021 06:42:47 -0400 From: "Roger Sayle" To: "'GCC Patches'" Subject: [PATCH] Improve handling of unknown sign bit in CCP. Date: Sun, 8 Aug 2021 11:42:44 +0100 Message-ID: <001001d78c42$20088b40$6019a1c0$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AdeMQUe97qTpErqgRsWhFllbasb1XA== 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 middle-end patch implements several related improvements to tree-ssa's conditional (bit) constant propagation pass. The current code handling ordered comparisons contains the comment "If the most significant bits are not known we know nothing" which is not entirely true [this test even prevents this pass understanding these comparisons always have a zero or one result]. This patch introduces a new value_mask_to_min_max helper function, that understands the different semantics of the most significant bit on signed vs. unsigned values. This allows us to generalize ordered comparisons, GE_EXPR, GT_EXPR, LE_EXPR and LT_EXPR, where the code is tweaked to correctly handle the potential equal cases. Then finally support is added for the related tree codes MIN_EXPR, MAX_EXPR, ABS_EXPR and ABSU_EXPR. Regression testing revealed three test cases in the testsuite that were checking for specific optimizations that are now being performed earlier than expected. These tests can continue to check their original transformations by explicitly adding -fno-tree-ccp to their dg-options (some already specify -fno-ipa-vrp or -fno-tree-forwprop for the same reason). 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? 2021-08-08 Roger Sayle gcc/ChangeLog * tree-ssa-ccp.c (value_mask_to_min_max): Helper function to determine the upper and lower bounds from a mask-value pair. (bit_value_unop) [ABS_EXPR, ABSU_EXPR]: Add support for absolute value and unsigned absolute value expressions. (bit_value_binop): Initialize *VAL's precision. [LT_EXPR, LE_EXPR]: Use value_mask_to_min_max to determine upper and lower bounds of operands. Add LE_EXPR/GE_EXPR support when the operands are unknown but potentially equal. [MIN_EXPR, MAX_EXPR]: Support minimum/maximum expressions. gcc/testsuite/ChangeLog * gcc.dg/pr68217.c: Add -fno-tree-ccp option. * gcc.dg/tree-ssa/vrp24.c: Add -fno-tree-ccp option. * g++.dg/ipa/pure-const-3.C: Add -fno-tree-ccp option. Roger --- Roger Sayle NextMove Software Cambridge, UK diff --git a/gcc/testsuite/g++.dg/ipa/pure-const-3.C b/gcc/testsuite/g++.dg/ipa/pure-const-3.C index 4cf9a6a..172a36b 100644 --- a/gcc/testsuite/g++.dg/ipa/pure-const-3.C +++ b/gcc/testsuite/g++.dg/ipa/pure-const-3.C @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-ipa-vrp -fdump-tree-optimized" } */ +/* { dg-options "-O2 -fno-ipa-vrp -fdump-tree-optimized -fno-tree-ccp" } */ int *ptr; static int barvar; static int b(int a); diff --git a/gcc/testsuite/gcc.dg/pr68217.c b/gcc/testsuite/gcc.dg/pr68217.c index c5b0d1f..eb4f15e 100644 --- a/gcc/testsuite/gcc.dg/pr68217.c +++ b/gcc/testsuite/gcc.dg/pr68217.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1 -fno-tree-ccp" } */ int foo (void) { diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c index dfe44b3..91015da 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-tree-forwprop -fdump-tree-evrp-details -fdump-tree-optimized" } */ +/* { dg-options "-O2 -fno-tree-forwprop -fdump-tree-evrp-details -fdump-tree-optimized -fno-tree-ccp" } */ struct rtx_def; diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c index 9ce6214..003c9c2 100644 --- a/gcc/tree-ssa-ccp.c +++ b/gcc/tree-ssa-ccp.c @@ -1293,6 +1293,28 @@ ccp_fold (gimple *stmt) } } +/* Determine the minimum and maximum values, *MIN and *MAX respectively, + represented by the mask pair VAL and MASK with signedness SGN and + precision PRECISION. */ + +void +value_mask_to_min_max (widest_int *min, widest_int *max, + const widest_int &val, const widest_int &mask, + signop sgn, int precision) +{ + *min = wi::bit_and_not (val, mask); + *max = val | mask; + if (sgn == SIGNED && wi::neg_p (mask)) + { + widest_int sign_bit = wi::lshift (1, precision - 1); + *min ^= sign_bit; + *max ^= sign_bit; + /* MAX is zero extended, and MIN is sign extended. */ + *min = wi::ext (*min, precision, sgn); + *max = wi::ext (*max, precision, sgn); + } +} + /* Apply the operation CODE in type TYPE to the value, mask pair RVAL and RMASK representing a value of type RTYPE and set the value, mask pair *VAL and *MASK to the result. */ @@ -1334,6 +1356,33 @@ bit_value_unop (enum tree_code code, signop type_sgn, int type_precision, break; } + case ABS_EXPR: + case ABSU_EXPR: + if (wi::sext (rmask, rtype_precision) == -1) + *mask = -1; + else if (wi::neg_p (rmask)) + { + /* Result is either rval or -rval. */ + widest_int temv, temm; + bit_value_unop (NEGATE_EXPR, rtype_sgn, rtype_precision, &temv, + &temm, type_sgn, type_precision, rval, rmask); + temm |= (rmask | (rval ^ temv)); + /* Extend the result. */ + *mask = wi::ext (temm, type_precision, type_sgn); + *val = wi::ext (temv, type_precision, type_sgn); + } + else if (wi::neg_p (rval)) + { + bit_value_unop (NEGATE_EXPR, type_sgn, type_precision, val, mask, + type_sgn, type_precision, rval, rmask); + } + else + { + *mask = rmask; + *val = rval; + } + break; + default: *mask = -1; break; @@ -1357,6 +1406,8 @@ bit_value_binop (enum tree_code code, signop sgn, int width, /* Assume we'll get a constant result. Use an initial non varying value, we fall back to varying in the end if necessary. */ *mask = -1; + /* Ensure that VAL is initialized (to any value). */ + *val = 0; switch (code) { @@ -1527,6 +1578,7 @@ bit_value_binop (enum tree_code code, signop sgn, int width, case LT_EXPR: case LE_EXPR: { + widest_int min1, max1, min2, max2; int minmax, maxmin; const widest_int &o1val = swap_p ? r2val : r1val; @@ -1534,26 +1586,21 @@ bit_value_binop (enum tree_code code, signop sgn, int width, const widest_int &o2val = swap_p ? r1val : r2val; const widest_int &o2mask = swap_p ? r1mask : r2mask; - /* If the most significant bits are not known we know nothing. */ - if (wi::neg_p (o1mask) || wi::neg_p (o2mask)) - break; + value_mask_to_min_max (&min1, &max1, o1val, o1mask, + r1type_sgn, r1type_precision); + value_mask_to_min_max (&min2, &max2, o2val, o2mask, + r1type_sgn, r1type_precision); /* For comparisons the signedness is in the comparison operands. */ - sgn = r1type_sgn; - - /* If we know the most significant bits we know the values - value ranges by means of treating varying bits as zero - or one. Do a cross comparison of the max/min pairs. */ - maxmin = wi::cmp (o1val | o1mask, - wi::bit_and_not (o2val, o2mask), sgn); - minmax = wi::cmp (wi::bit_and_not (o1val, o1mask), - o2val | o2mask, sgn); - if (maxmin < 0) /* o1 is less than o2. */ + /* Do a cross comparison of the max/min pairs. */ + maxmin = wi::cmp (max1, min2, r1type_sgn); + minmax = wi::cmp (min1, max2, r1type_sgn); + if (maxmin < (code == LE_EXPR ? 1: 0)) /* o1 < or <= o2. */ { *mask = 0; *val = 1; } - else if (minmax > 0) /* o1 is not less or equal to o2. */ + else if (minmax > (code == LT_EXPR ? -1 : 0)) /* o1 >= or > o2. */ { *mask = 0; *val = 0; @@ -1574,6 +1621,49 @@ bit_value_binop (enum tree_code code, signop sgn, int width, break; } + case MIN_EXPR: + case MAX_EXPR: + { + widest_int min1, max1, min2, max2; + + value_mask_to_min_max (&min1, &max1, r1val, r1mask, sgn, width); + value_mask_to_min_max (&min2, &max2, r2val, r2mask, sgn, width); + + if (wi::cmp (max1, min2, sgn) <= 0) /* r1 is less than r2. */ + { + if (code == MIN_EXPR) + { + *mask = r1mask; + *val = r1val; + } + else + { + *mask = r2mask; + *val = r2val; + } + } + else if (wi::cmp (min1, max2, sgn) >= 0) /* r2 is less than r1. */ + { + if (code == MIN_EXPR) + { + *mask = r2mask; + *val = r2val; + } + else + { + *mask = r1mask; + *val = r1val; + } + } + else + { + /* The result is either r1 or r2. */ + *mask = r1mask | r2mask | (r1val ^ r2val); + *val = r1val; + } + break; + } + default:; } }