From patchwork Fri Jan 15 22:32:33 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 568502 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 8E3AA140BAB for ; Sat, 16 Jan 2016 09:32:47 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=CosPBjMB; 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 :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=OjOsvNwVvM3h+fsJu SEjbYiY3YV2xfvIAXnEpwUeEIXtaKCSlc+dz1lXS7IRmgDF5RLViSts5FIbc35nY qoVY8FEFWhHMqqRDE8E0jrJ7gKddQRUDy0fegdmOQioyvCaZamR54TagIW+ABKNG Jl3vSCIV4UxQT4VuUnwmk5ikKM= 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 :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=aNbGmW1cBVHO21HbZO4KIM8 BGSk=; b=CosPBjMBCKUNaMVSWmRvmwG/M1NdEkIgoHyCNmiht+f9GtQqWrYD9Y9 ARIvxbrRpa3negStEFYEH1pa9Pp3Tsx1DOvCPURe8D7OtDgCU2ZvTcCIPcq9L1pI Kpp833rgc6ZDHX9EYR4TEo8hXxh0TJ7jTwfvrd3TK60QBdS5ToZE= Received: (qmail 83349 invoked by alias); 15 Jan 2016 22:32:39 -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 83298 invoked by uid 89); 15 Jan 2016 22:32:37 -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=boo, 75, 6, partitioning, 9426 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 (AES256-GCM-SHA384 encrypted) ESMTPS; Fri, 15 Jan 2016 22:32:35 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (Postfix) with ESMTPS id 3ABD7A2C0A for ; Fri, 15 Jan 2016 22:32:34 +0000 (UTC) Received: from slagheap.utah.redhat.com (ovpn-113-225.phx2.redhat.com [10.3.113.225]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u0FMWXIt005551; Fri, 15 Jan 2016 17:32:33 -0500 Subject: Re: [PATCH][PR tree-optimization/69270] Exploit VRP information in DOM To: Jakub Jelinek References: <5697508C.6050006@redhat.com> <20160114074643.GX3017@tucnak.redhat.com> <20160114074919.GL22971@tucnak.redhat.com> <5697E5A2.4050105@redhat.com> Cc: gcc-patches@gcc.gnu.org From: Jeff Law Message-ID: <56997381.7010101@redhat.com> Date: Fri, 15 Jan 2016 15:32:33 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.0 MIME-Version: 1.0 In-Reply-To: <5697E5A2.4050105@redhat.com> X-IsSubscribed: yes On 01/14/2016 11:14 AM, Jeff Law wrote: > On 01/14/2016 12:49 AM, Jakub Jelinek wrote: >> On Thu, Jan 14, 2016 at 08:46:43AM +0100, Jakub Jelinek wrote: >>> On Thu, Jan 14, 2016 at 12:38:52AM -0700, Jeff Law wrote: >>>> + /* An integral type with more precision, but the object >>>> + only takes on values [0..1] as determined by VRP >>>> + analysis. */ >>>> + wide_int min, max; >>>> + if (INTEGRAL_TYPE_P (TREE_TYPE (op)) >>>> + && get_range_info (op, &min, &max) == VR_RANGE >>>> + && wi::eq_p (min, 0) >>>> + && wi::eq_p (max, 1)) >>>> + return true; >>> >>> You could use and/or: >>> if (INTEGRAL_TYPE_P (TREE_TYPE (op)) && wi::eq_p (get_nonzero_bits >>> (op), 1)) >>> set_range_info for VR_RANGE should usually update also the non-zero >>> bits, but >>> set_nonzero_bits does not update the recorded range. >> >> Though, that would need to be limited to TYPE_PRECISION (TREE_TYPE >> (op)) > 1 >> or TYPE_UNSIGNED. > Quite surprisingly, this does seem to do better fairly often. Usually > it's just getting more constants into the PHI nodes without further > improvements. However occasionally I see a PHI that turns into a > constant, which is then propagated to a use where we're able to simplify > some arithmetic/logical. > > Unfortunately it doesn't make a bit of difference in the final output, > so something post DOM was picking up these anyway (most likely VRP2). > But I'm a fan of getting stuff optimized earlier in the pipeline when > it's reasonable to do so, and this seems reasonable. > > Limiting to TYPE_PRECISION > 1 or TYPE_UNSIGNED ought to be trivial. So further testing did show some code regressions from this improvement. Specifically we were clearly better at propagating boolean values derived from test conditions into PHIs (and ultimately into real statements as well). That was the purpose of the patch. Where we took a small step backwards was the out-of-ssa translation and RTL expansion. A constant argument in a PHI generates a constant load at RTL time. We have uncprop to detect cases where there are already objects holding the value we want and just before out-of-ssa we un-propagate the constant. When the object holding the value we want coalesces with the LHS of the PHI (which is most of the time) we win. uncprop wasn't catching these new cases where we'd propagated constants more aggressively into PHI nodes. This patch fixes that problem. In all, this is a very small improvement in the generated code. It may ultimately prove more useful in the future to drive path partitioning. There's two small tests. One verifies we're able to propagate more constants per the original intent of the patch. The other verifies we un-propagate as well. Bootstrapped and regression tested on x86_64. Installed on the trunk. jeff commit 1384b36abcd52a7ac72ca6538afa2aed2e04f8e0 Author: Jeff Law Date: Fri Jan 15 17:15:24 2016 -0500 PR tree-optimization/69270 * tree-ssanames.c (ssa_name_has_boolean_range): Moved here from tree-ssa-dom.c. Improve test for [0..1] ranve from VRP. * tree-ssa-dom.c (ssa_name_has_boolean_range): Remove. * tree-ssanames.h (ssa_name_has_boolean_range): Prototype. * tree-ssa-uncprop.c (associate_equivalences_with_edges): Use ssa_name_has_boolean_range and constant_boolean_node. PR tree-optimization/69270 * gcc.dg/tree-ssa/pr69270-2.c: New test. * gcc.dg/tree-ssa/pr69270-3.c: New test. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index e3dc328..409e981 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,13 @@ +2016-01-15 Jeff Law + + PR tree-optimization/69270 + * tree-ssanames.c (ssa_name_has_boolean_range): Moved here from + tree-ssa-dom.c. Improve test for [0..1] ranve from VRP. + * tree-ssa-dom.c (ssa_name_has_boolean_range): Remove. + * tree-ssanames.h (ssa_name_has_boolean_range): Prototype. + * tree-ssa-uncprop.c (associate_equivalences_with_edges): Use + ssa_name_has_boolean_range and constant_boolean_node. + 2016-01-15 Vladimir Makarov PR rtl-optimization/69030 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 29291a2..d9a9246 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2016-01-15 Jeff Law + + PR tree-optimization/69270 + * gcc.dg/tree-ssa/pr69270-2.c: New test. + * gcc.dg/tree-ssa/pr69270-3.c: New test. + 2016-01-15 Paul Thomas PR fortran/49630 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr69270-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr69270-2.c new file mode 100644 index 0000000..15c7bdd --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr69270-2.c @@ -0,0 +1,52 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dom3-details -w" } */ + +/* There should be a reference to usecount that turn into + constants. */ +/* { dg-final { scan-tree-dump-times "Replaced .usecount_\[0-9\]+. with constant .1." 1 "dom3"} } */ + +/* And an assignment using usecount ought to fold down to constants. */ +/* { dg-final { scan-tree-dump-times "Folded to: usecount_\[0-9\]+ = 2;" 1 "dom3"} } */ + +/* The arithmetic using usecount should be gone, except for the one in the + details debugging. */ +/* { dg-final { scan-tree-dump-times "usecount_\[0-9\]+ = usecount_\[0-9\]+ . 1;" 1 "dom3"} } */ + +typedef union tree_node *tree; +typedef union gimple_statement_d *gimple; +extern const int tree_code_type[]; +union tree_node +{ + int code:16; +}; +typedef struct immediate_use_iterator_d +{ +} +imm_use_iterator; +void +insert_debug_temp_for_var_def (gimple stmt) +{ + gimple def_stmt = ((void *) 0); + int usecount = 0; + tree value = ((void *) 0); + for (; arf ();) + { + if (!gimple_debug_bind_p (stmt)) + continue; + if (usecount++) + break; + unsigned char no_value = 0; + if (!gimple_bb (def_stmt)) + no_value = 1; + if (!no_value) + value = gimple_assign_rhs_to_tree (); + } + if (value) + { + if ((tree_code_type[(int) (((value)->code))] == 42) + || (usecount == 1 && (is_gimple_min_invariant (value)))) + value = unshare_expr (value); + } +} + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr69270-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr69270-3.c new file mode 100644 index 0000000..89735f6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr69270-3.c @@ -0,0 +1,26 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-uncprop-details -w" } */ + +/* We're looking for a constant argument a PHI node. There + should only be one if we unpropagate correctly. */ +/* { dg-final { scan-tree-dump-times ", 1" 1 "uncprop1"} } */ + +typedef long unsigned int size_t; +typedef union gimple_statement_d *gimple; +unsigned char +propagate_with_phi () +{ + gimple use_stmt; + unsigned char phi_inserted; + phi_inserted = 0; + for (; !end_imm_use_stmt_p (); next_imm_use_stmt ()) + { + if (!(arf () == 10 && boo () == 20)) + continue; + if (!phi_inserted) + phi_inserted = 1; + else + update_stmt (); + } +} + diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index f2257b3..8298637 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -316,39 +316,6 @@ record_conditions (struct edge_info *edge_info, tree cond, tree inverted) edge_info->cond_equivalences.safe_push (c); } -/* Return TRUE is OP, an SSA_NAME has a range of values [0..1], false - otherwise. - - This can be because it is a boolean type, any unsigned integral - type with a single bit of precision, or has known range of [0..1] - via VRP analysis. */ - -static bool -ssa_name_has_boolean_range (tree op) -{ - /* Boolean types always have a range [0..1]. */ - if (TREE_CODE (TREE_TYPE (op)) == BOOLEAN_TYPE) - return true; - - /* An integral type with a single bit of precision. */ - if (INTEGRAL_TYPE_P (TREE_TYPE (op)) - && TYPE_UNSIGNED (TREE_TYPE (op)) - && TYPE_PRECISION (TREE_TYPE (op)) == 1) - return true; - - /* An integral type with more precision, but the object - only takes on values [0..1] as determined by VRP - analysis. */ - wide_int min, max; - if (INTEGRAL_TYPE_P (TREE_TYPE (op)) - && get_range_info (op, &min, &max) == VR_RANGE - && wi::eq_p (min, 0) - && wi::eq_p (max, 1)) - return true; - - return false; -} - /* We have finished optimizing BB, record any information implied by taking a specific outgoing edge from BB. */ diff --git a/gcc/tree-ssa-uncprop.c b/gcc/tree-ssa-uncprop.c index 4b57578..307bb1f 100644 --- a/gcc/tree-ssa-uncprop.c +++ b/gcc/tree-ssa-uncprop.c @@ -94,23 +94,26 @@ associate_equivalences_with_edges (void) can record an equivalence for OP0 rather than COND. */ if (TREE_CODE (op0) == SSA_NAME && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) - && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE + && ssa_name_has_boolean_range (op0) && is_gimple_min_invariant (op1)) { + tree true_val = constant_boolean_node (true, TREE_TYPE (op0)); + tree false_val = constant_boolean_node (false, + TREE_TYPE (op0)); if (code == EQ_EXPR) { equivalency = XNEW (struct edge_equivalency); equivalency->lhs = op0; equivalency->rhs = (integer_zerop (op1) - ? boolean_false_node - : boolean_true_node); + ? false_val + : true_val); true_edge->aux = equivalency; equivalency = XNEW (struct edge_equivalency); equivalency->lhs = op0; equivalency->rhs = (integer_zerop (op1) - ? boolean_true_node - : boolean_false_node); + ? true_val + : false_val); false_edge->aux = equivalency; } else @@ -118,15 +121,15 @@ associate_equivalences_with_edges (void) equivalency = XNEW (struct edge_equivalency); equivalency->lhs = op0; equivalency->rhs = (integer_zerop (op1) - ? boolean_true_node - : boolean_false_node); + ? true_val + : false_val); true_edge->aux = equivalency; equivalency = XNEW (struct edge_equivalency); equivalency->lhs = op0; equivalency->rhs = (integer_zerop (op1) - ? boolean_false_node - : boolean_true_node); + ? false_val + : true_val); false_edge->aux = equivalency; } } diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 82866b2..b6f72e2 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -411,6 +411,40 @@ get_nonzero_bits (const_tree name) return ri->get_nonzero_bits (); } +/* Return TRUE is OP, an SSA_NAME has a range of values [0..1], false + otherwise. + + This can be because it is a boolean type, any unsigned integral + type with a single bit of precision, or has known range of [0..1] + via VRP analysis. */ + +bool +ssa_name_has_boolean_range (tree op) +{ + gcc_assert (TREE_CODE (op) == SSA_NAME); + + /* Boolean types always have a range [0..1]. */ + if (TREE_CODE (TREE_TYPE (op)) == BOOLEAN_TYPE) + return true; + + /* An integral type with a single bit of precision. */ + if (INTEGRAL_TYPE_P (TREE_TYPE (op)) + && TYPE_UNSIGNED (TREE_TYPE (op)) + && TYPE_PRECISION (TREE_TYPE (op)) == 1) + return true; + + /* An integral type with more precision, but the object + only takes on values [0..1] as determined by VRP + analysis. */ + if (INTEGRAL_TYPE_P (TREE_TYPE (op)) + && (TYPE_PRECISION (TREE_TYPE (op)) > 1 + || TYPE_UNSIGNED (TREE_TYPE (op))) + && wi::eq_p (get_nonzero_bits (op), 1)) + return true; + + return false; +} + /* We no longer need the SSA_NAME expression VAR, release it so that it may be reused. diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h index d8ce684..c81b1a1 100644 --- a/gcc/tree-ssanames.h +++ b/gcc/tree-ssanames.h @@ -75,6 +75,7 @@ extern enum value_range_type get_range_info (const_tree, wide_int *, wide_int *); extern void set_nonzero_bits (tree, const wide_int_ref &); extern wide_int get_nonzero_bits (const_tree); +extern bool ssa_name_has_boolean_range (tree); extern void init_ssanames (struct function *, int); extern void fini_ssanames (struct function *); extern void ssanames_print_statistics (void);