From patchwork Sat Feb 4 14:52:44 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 724097 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3vFxYd4ypfz9s70 for ; Sun, 5 Feb 2017 01:53:09 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="ICnmpou0"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=eWtqM9TJdoNKk/5SDMF/M5JoyknWePNdb9XbgphWEsPhslUHc5 1MP9sXylMxjYEw3+WTiFpEL2WWx3q8e3sZSw2zULI7xgv0aODj4ITMsfWEGLI07D FlchvOuI+IDN7erLR7m3dGGbmppw7ti16Uv0Z0b+qgUOfe7EOC6xdsTBs= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=Ct/kjwJNecuEBi9gDHW7cxaVyvg=; b=ICnmpou0ULJZluLq/Szt sXvKOFyo9bTCJ3BbgnGa/o+J/XpNbQnxUBF1mbxphAf61z6UNbN8yNxAFAtWlrlJ jeKzs8e+K1We7zkLN2Sp4MIt4AC2CZcmzzT9rtZmPKomCGInnHANc0vniPiF0U6F NT4J6i+/blk28GNKMfO55BM= Received: (qmail 66593 invoked by alias); 4 Feb 2017 14:52:51 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 66446 invoked by uid 89); 4 Feb 2017 14:52:50 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=H*M:a6d3 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sat, 04 Feb 2017 14:52:47 +0000 Received: from int-mx13.intmail.prod.int.phx2.redhat.com (int-mx13.intmail.prod.int.phx2.redhat.com [10.5.11.26]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 648D87F081 for ; Sat, 4 Feb 2017 14:52:47 +0000 (UTC) Received: from localhost.localdomain (ovpn-120-20.rdu2.redhat.com [10.10.120.20] (may be forged)) by int-mx13.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id v14EqkN9002113 for ; Sat, 4 Feb 2017 09:52:46 -0500 To: gcc-patches From: Jeff Law Subject: [RFA] [PR tree-optimization/79095][PATCH 3/4] Improve ASSERT_EXPRs and simplification of overflow tests Message-ID: Date: Sat, 4 Feb 2017 07:52:44 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.5.1 MIME-Version: 1.0 X-IsSubscribed: yes This is the actual optimization piece of the patchseries and uses the overflow test detection function in patch #2. First, when we detect an overflow test, we register additional ASSERT_EXPRs for the given name. So instead of an ASSERT_EXPR for an expression like A < B, we get an assert like A > 0xfffffffe or A <= 0. Additionally, during propagation and folding, if we are presented with an overflow test which collapses into an equality test, we will simplify the test into an equality check (without changing the IL). So A + 1 < A would turn into A == -1 or A + 1 > A turns into A != -1. There's a corresponding equivalent for A - 1 < A and A - 1 > A. The net result is the new ASSERT_EXPRs and simplified tests allow VRP to eliminate more paths through the CFG and improve its constant propagation capabilities. Examples can be found in the next patch which has the tests. Bootstrapped and regression tested with the other patches in this series. OK for the trunk? * tree-vrp.c (register_edge_assert_for_2): Register additional asserts fif NAME is used in an overflow test. (vrp_evaluate_conditional_warnv_with_ops): If the ops represent an overflow check that can be expressed as an equality test, then adjust ops to be that equality test. diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 6459c71..8d78646 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -5299,7 +5298,19 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi, /* Only register an ASSERT_EXPR if NAME was found in the sub-graph reachable from E. */ if (live_on_edge (e, name)) - register_new_assert_for (name, name, comp_code, val, NULL, e, bsi); + { + tree x; + if (overflow_comparison_p (comp_code, name, val, false, false, &x) + || overflow_comparison_p (swap_tree_comparison (comp_code), val, name, + false, true, &x)) + { + enum tree_code new_code + = ((comp_code == GT_EXPR || comp_code == GE_EXPR) + ? GT_EXPR : LE_EXPR); + register_new_assert_for (name, name, new_code, x, NULL, e, bsi); + } + register_new_assert_for (name, name, comp_code, val, NULL, e, bsi); + } /* In the case of NAME <= CST and NAME being defined as NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2 @@ -7658,6 +7669,60 @@ vrp_evaluate_conditional_warnv_with_ops (enum tree_code code, tree op0, && !POINTER_TYPE_P (TREE_TYPE (op0))) return NULL_TREE; + /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed + as a simple equality test, then prefer that over its current form + for evaluation. + + An overflow test which collapses to an equality test can always be + expressed as a comparison of one argument against zero. Overflow + occurs when the chosen argument is zero and does not occur if the + chosen argument is not zero. */ + tree x; + if (overflow_comparison_p (code, op0, op1, use_equiv_p, false, &x)) + { + wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED); + /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0) + B = A - 1; if (A > B) -> B = A - 1; if (A != 0) */ + if (integer_zerop (x)) + { + op1 = x; + code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR; + } + /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0) + B = A + 1; if (A < B) -> B = A + 1; if (B != 0) */ + else if (wi::eq_p (x, max - 1)) + { + op0 = op1; + op1 = wide_int_to_tree (TREE_TYPE (op0), 0); + code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR; + } + } + else if (overflow_comparison_p (swap_tree_comparison (code), + op1, op0, use_equiv_p, true, &x)) + { + /* X holds the value if we wanted to generate an overflow check + for the comparison using OP1. But we're actually going to + test against OP0 and we're always going to use an equality + test, so the constants for detection below are different + than the constant we pass into vrp_evaluate_... */ + wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED); + /* B = A - 1; if (B > A) -> B = A - 1; if (A == 0) + B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */ + if (wi::eq_p (x, max - 1)) + { + op0 = op1; + op1 = wide_int_to_tree (TREE_TYPE (op0), 0); + code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR; + } + /* B = A + 1; if (B < A) -> B = A + 1; if (B == 0) + B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */ + else if (integer_zerop (x)) + { + op1 = x; + code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR; + } + } + if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges (code, op0, op1, strict_overflow_p))) return ret;