From patchwork Wed Oct 9 18:58:37 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 281974 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 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 2D6512C03AA for ; Thu, 10 Oct 2013 05:58:48 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:references :in-reply-to:content-type; q=dns; s=default; b=b7/SIfdAvEQIHwDYo sAU6flyssSYVcd3e24/VKnNN2Zuscg+FW7AafbxGYQacvBrw9wxy/hNjyhvf9EHq 5EFPH7n+ge2cAhhEZq85nKEV1GIA6nsxDAiZDYJUjLW7kalpUEhS6rnt0aqreCV1 dT2vNeZoMmg71uArX/uoz6ytPI= 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 :message-id:date:from:mime-version:to:subject:references :in-reply-to:content-type; s=default; bh=Xmiqr/ctr8n9U6p1CfdACTr df6g=; b=bGg+RYgDx7QyWbAI+U/VkDVYDjFSqgd+CeQG2IZmNA7nghPsXcVtFJK J8DlJdbnqnfQIZ7voduBmUmcrwgbMz/2cNE9OwHIC4Ac+oHz93Um9Vzo3nW7d+sq 6Ltuvz76upsdBFyGt7XqkBhSoyTs6fj74l/sdQnYAKGs2vWk9gPE= Received: (qmail 18382 invoked by alias); 9 Oct 2013 18:58:42 -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 18369 invoked by uid 89); 9 Oct 2013 18:58:42 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-4.5 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.2 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; Wed, 09 Oct 2013 18:58:41 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r99IwbDV012020 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Wed, 9 Oct 2013 14:58:37 -0400 Received: from stumpy.slc.redhat.com (ovpn-113-178.phx2.redhat.com [10.3.113.178]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r99IwbLU023587; Wed, 9 Oct 2013 14:58:37 -0400 Message-ID: <5255A75D.7080504@redhat.com> Date: Wed, 09 Oct 2013 12:58:37 -0600 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0 MIME-Version: 1.0 To: Zhenqiang Chen , gcc-patches@gcc.gnu.org Subject: Re: [PATCH] Enhance phiopt to handle BIT_AND_EXPR References: <000001cebdbf$a3155310$e93ff930$@arm.com> In-Reply-To: <000001cebdbf$a3155310$e93ff930$@arm.com> X-IsSubscribed: yes On 09/30/13 03:29, Zhenqiang Chen wrote: > Hi, > > The patch enhances phiopt to handle cases like: > > if (a == 0 && (...)) > return 0; > return a; > > Boot strap and no make check regression on X86-64 and ARM. > > Is it OK for trunk? > > Thanks! > -Zhenqiang > > ChangeLog: > 2013-09-30 Zhenqiang Chen > > * tree-ssa-phiopt.c (operand_equal_for_phi_arg_p_1): New. > (value_replacement): Move a check to operand_equal_for_phi_arg_p_1. > > testsuite/ChangeLog: > 2013-09-30 Zhenqiang Chen > > * gcc.dg/tree-ssa/phi-opt-11.c: New test case. So I made some minor changes. First, the duplicated code was factored out into its own function. Block comments were added to the two new functions and comments within the functions were improved. Finally, I added to additional cases to the testcase to show other cases it handles. I also fixed some trailing whitespace in tree-ssa-phiopt.c unrelated to your changes. Bootstrapped & regression tested on x86_64-unknown-linux-gnu. Installed on the trunk. Final patch attached for reference. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b427946..b1028bf 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2013-10-09 Zhenqiang Chen + + * tree-ssa-phiopts.c (rhs_is_fed_for_value_replacement): New function. + (operand_equal_for_value_replacement): New function, extracted from + value_replacement and enhanced to catch more cases. + (value_replacement): Use operand_equal_for_value_replacement. + 2013-10-09 Andrew MacLeod * loop-doloop.c (doloop_modify, doloop_optimize): Use diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 66b3c38..76cce59 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2013-10-09 Zhenqiang Chen + + * gcc.dg/tree-ssa/phi-opt-11.c: New test. + 2013-10-09 Marek Polacek PR c++/58635 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-11.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-11.c new file mode 100644 index 0000000..7c83007 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-11.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-optimized" } */ + +int f(int a, int b, int c) +{ + if (a == 0 && b > c) + return 0; + return a; +} + +int g(int a, int b, int c) +{ + if (a == 42 && b > c) + return 42; + return a; +} + +int h(int a, int b, int c, int d) +{ + if (a == d && b > c) + return d; + return a; +} +/* { dg-final { scan-tree-dump-times "if" 0 "optimized"} } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c index 8e1ddab..adf8a28 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -110,6 +110,26 @@ static bool gate_hoist_loads (void); This opportunity can sometimes occur as a result of other optimizations. + + Another case caught by value replacement looks like this: + + bb0: + t1 = a == CONST; + t2 = b > c; + t3 = t1 & t2; + if (t3 != 0) goto bb1; else goto bb2; + bb1: + bb2: + x = PHI (CONST, a) + + Gets replaced with: + bb0: + bb2: + t1 = a == CONST; + t2 = b > c; + t3 = t1 & t2; + x = a; + ABS Replacement --------------- @@ -155,7 +175,7 @@ static bool gate_hoist_loads (void); Adjacent Load Hoisting ---------------------- - + This transformation replaces bb0: @@ -286,7 +306,7 @@ single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1) phi optimizations. Both share much of the infrastructure in how to match applicable basic block patterns. DO_STORE_ELIM is true when we want to do conditional store replacement, false otherwise. - DO_HOIST_LOADS is true when we want to hoist adjacent loads out + DO_HOIST_LOADS is true when we want to hoist adjacent loads out of diamond control flow patterns, false otherwise. */ static unsigned int tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads) @@ -389,7 +409,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads) continue; } else - continue; + continue; e1 = EDGE_SUCC (bb1, 0); @@ -437,7 +457,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads) if (!candorest) continue; - + phi = single_non_singleton_phi_for_edges (phis, e1, e2); if (!phi) continue; @@ -672,6 +692,93 @@ jump_function_from_stmt (tree *arg, gimple stmt) return false; } +/* RHS is a source argument in a BIT_AND_EXPR which feeds a conditional + of the form SSA_NAME NE 0. + + If RHS is fed by a simple EQ_EXPR comparison of two values, see if + the two input values of the EQ_EXPR match arg0 and arg1. + + If so update *code and return TRUE. Otherwise return FALSE. */ + +static bool +rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1, + enum tree_code *code, const_tree rhs) +{ + /* Obviously if RHS is not an SSA_NAME, we can't look at the defining + statement. */ + if (TREE_CODE (rhs) == SSA_NAME) + { + gimple def1 = SSA_NAME_DEF_STMT (rhs); + + /* Verify the defining statement has an EQ_EXPR on the RHS. */ + if (is_gimple_assign (def1) && gimple_assign_rhs_code (def1) == EQ_EXPR) + { + /* Finally verify the source operands of the EQ_EXPR are equal + to arg0 and arg1. */ + tree op0 = gimple_assign_rhs1 (def1); + tree op1 = gimple_assign_rhs2 (def1); + if ((operand_equal_for_phi_arg_p (arg0, op0) + && operand_equal_for_phi_arg_p (arg1, op1)) + || (operand_equal_for_phi_arg_p (arg0, op1) + && operand_equal_for_phi_arg_p (arg1, op0))) + { + /* We will perform the optimization. */ + *code = gimple_assign_rhs_code (def1); + return true; + } + } + } + return false; +} + +/* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND. + + Also return TRUE if arg0/arg1 are equal to the source arguments of a + an EQ comparison feeding a BIT_AND_EXPR which feeds COND. + + Return FALSE otherwise. */ + +static bool +operand_equal_for_value_replacement (const_tree arg0, const_tree arg1, + enum tree_code *code, gimple cond) +{ + gimple def; + tree lhs = gimple_cond_lhs (cond); + tree rhs = gimple_cond_rhs (cond); + + if ((operand_equal_for_phi_arg_p (arg0, lhs) + && operand_equal_for_phi_arg_p (arg1, rhs)) + || (operand_equal_for_phi_arg_p (arg1, lhs) + && operand_equal_for_phi_arg_p (arg0, rhs))) + return true; + + /* Now handle more complex case where we have an EQ comparison + which feeds a BIT_AND_EXPR which feeds COND. + + First verify that COND is of the form SSA_NAME NE 0. */ + if (*code != NE_EXPR || !integer_zerop (rhs) + || TREE_CODE (lhs) != SSA_NAME) + return false; + + /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR. */ + def = SSA_NAME_DEF_STMT (lhs); + if (!is_gimple_assign (def) || gimple_assign_rhs_code (def) != BIT_AND_EXPR) + return false; + + /* Now verify arg0/arg1 correspond to the source arguments of an + EQ comparison feeding the BIT_AND_EXPR. */ + + tree tmp = gimple_assign_rhs1 (def); + if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp)) + return true; + + tmp = gimple_assign_rhs2 (def); + if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp)) + return true; + + return false; +} + /* The function value_replacement does the main work of doing the value replacement. Return non-zero if the replacement is done. Otherwise return 0. If we remove the middle basic block, return 2. @@ -741,10 +848,7 @@ value_replacement (basic_block cond_bb, basic_block middle_bb, We now need to verify that the two arguments in the PHI node match the two arguments to the equality comparison. */ - if ((operand_equal_for_phi_arg_p (arg0, gimple_cond_lhs (cond)) - && operand_equal_for_phi_arg_p (arg1, gimple_cond_rhs (cond))) - || (operand_equal_for_phi_arg_p (arg1, gimple_cond_lhs (cond)) - && operand_equal_for_phi_arg_p (arg0, gimple_cond_rhs (cond)))) + if (operand_equal_for_value_replacement (arg0, arg1, &code, cond)) { edge e; tree arg; @@ -1746,7 +1850,7 @@ local_mem_dependence (gimple stmt, basic_block bb) /* Given a "diamond" control-flow pattern where BB0 tests a condition, BB1 and BB2 are "then" and "else" blocks dependent on this test, - and BB3 rejoins control flow following BB1 and BB2, look for + and BB3 rejoins control flow following BB1 and BB2, look for opportunities to hoist loads as follows. If BB3 contains a PHI of two loads, one each occurring in BB1 and BB2, and the loads are provably of adjacent fields in the same structure, then move both @@ -1796,7 +1900,7 @@ hoist_adjacent_loads (basic_block bb0, basic_block bb1, arg1 = gimple_phi_arg_def (phi_stmt, 0); arg2 = gimple_phi_arg_def (phi_stmt, 1); - + if (TREE_CODE (arg1) != SSA_NAME || TREE_CODE (arg2) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (arg1)