From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 87497 invoked by alias); 22 May 2019 12:38:58 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 87489 invoked by uid 89); 22 May 2019 12:38:58 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-18.4 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_PASS autolearn=ham version=3.3.1 spammy=taste, guo, vertical, Guo X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 22 May 2019 12:38:56 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 35B94ADC1; Wed, 22 May 2019 12:38:54 +0000 (UTC) Date: Wed, 22 May 2019 12:38:00 -0000 From: Richard Biener To: Jiufu Guo cc: gcc-patches@gcc.gnu.org, Jakub Jelinek , Daniel Berlin , segher@kernel.crashing.org, wschmidt@linux.ibm.com, law@redhat.com Subject: Re: [PATCH] A jump threading opportunity for condition branch In-Reply-To: <1558446288-52444-1-git-send-email-guojiufu@linux.ibm.com> Message-ID: References: <1558446288-52444-1-git-send-email-guojiufu@linux.ibm.com> User-Agent: Alpine 2.20 (LSU 67 2015-01-07) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-SW-Source: 2019-05/txt/msg01499.txt.bz2 On Tue, 21 May 2019, Jiufu Guo wrote: > Hi, > > This patch implements a new opportunity of jump threading for PR77820. > In this optimization, conditional jumps are merged with unconditional jump. > And then moving CMP result to GPR is eliminated. > > It looks like below: > > > p0 = a CMP b > goto ; > > > p1 = c CMP d > goto ; > > > # phi = PHI > if (phi != 0) goto ; else goto ; > > Could be transformed to: > > > p0 = a CMP b > if (p0 != 0) goto ; else goto ; > > > p1 = c CMP d > if (p1 != 0) goto ; else goto ; > > > This optimization eliminates: > 1. saving CMP result: p0 = a CMP b. > 2. additional CMP on branch: if (phi != 0). > 3. converting CMP result if there is phi = (INT_CONV) p0 if there is. > > Bootstrapped and tested on powerpc64le with no regressions(one case is improved) > and new testcases are added. Is this ok for trunk? > > Thanks! > Jiufu Guo > > > [gcc] > 2019-05-21 Jiufu Guo > Lijia He > > PR tree-optimization/77820 > * tree-ssa-threadedge.c (cmp_from_unconditional_block): New function. > * tree-ssa-threadedge.c (is_trivial_join_block): New function. > * tree-ssa-threadedge.c (thread_across_edge): Call is_trivial_join_block. > > [gcc/testsuite] > 2019-05-21 Jiufu Guo > Lijia He > > PR tree-optimization/77820 > * gcc.dg/tree-ssa/phi_on_compare-1.c: New testcase. > * gcc.dg/tree-ssa/phi_on_compare-2.c: New testcase. > * gcc.dg/tree-ssa/phi_on_compare-3.c: New testcase. > * gcc.dg/tree-ssa/phi_on_compare-4.c: New testcase. > * gcc.dg/tree-ssa/split-path-6.c: Update testcase. > > --- > gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c | 32 +++++++++ > gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c | 27 +++++++ > gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c | 31 ++++++++ > gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-4.c | 40 +++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c | 2 +- > gcc/tree-ssa-threadedge.c | 91 +++++++++++++++++++++++- > 6 files changed, 219 insertions(+), 4 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-4.c > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c > new file mode 100644 > index 0000000..ad4890a > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c > @@ -0,0 +1,32 @@ > +/* { dg-do compile } */ > +/* { dg-options "-Ofast -fdump-tree-vrp1" } */ > + > +void g (int); > +void g1 (int); > + > +void > +f (long a, long b, long c, long d, long x) > +{ > + _Bool t; > + if (x) > + { > + g (a + 1); > + t = a < b; > + c = d + x; > + } > + else > + { > + g (b + 1); > + a = c + d; > + t = c > d; > + } > + > + if (t) > + { > + g1 (c); > + } > + > + g (a); > +} > + > +/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "vrp1" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c > new file mode 100644 > index 0000000..ca67d65 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c > @@ -0,0 +1,27 @@ > +/* { dg-do compile } */ > +/* { dg-options "-Ofast -fdump-tree-vrp1" } */ > + > +void g (void); > +void g1 (void); > + > +void > +f (long a, long b, long c, long d, int x) > +{ > + _Bool t; > + if (x) > + { > + t = c < d; > + } > + else > + { > + t = a < b; > + } > + > + if (t) > + { > + g1 (); > + g (); > + } > +} > + > +/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "vrp1" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c > new file mode 100644 > index 0000000..a126e97 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c > @@ -0,0 +1,31 @@ > +/* { dg-do compile } */ > +/* { dg-options "-Ofast -fdump-tree-vrp1" } */ > + > +void g (void); > +void g1 (void); > + > +void > +f (long a, long b, long c, long d, int x) > +{ > + int t; > + if (x) > + { > + t = a < b; > + } > + else if (d == x) > + { > + t = c < b; > + } > + else > + { > + t = d > c; > + } > + > + if (t) > + { > + g1 (); > + g (); > + } > +} > + > +/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "vrp1" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-4.c b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-4.c > new file mode 100644 > index 0000000..5a50c2d > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-4.c > @@ -0,0 +1,40 @@ > +/* { dg-do compile } */ > +/* { dg-options "-Ofast -fdump-tree-vrp1" } */ > + > +void g (int); > +void g1 (int); > + > +void > +f (long a, long b, long c, long d, int x) > +{ > + int t; > + _Bool l1 = 0, l2 = 0; > + if (x) > + { > + g (a); > + c = a + b; > + t = a < b; > + l1 = 1; > + } > + else > + { > + g1 (b); > + t = c > d; > + d = c + b; > + l2 = 1; > + } > + > + if (t) > + { > + if (l1 | l2) > + g1 (c); > + } > + else > + { > + g (d); > + g1 (a + b); > + } > + g (c + d); > +} > + > +/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "vrp1" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c > index e9b4f26..1d7b587 100644 > --- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c > +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c > @@ -69,4 +69,4 @@ lookharder (string) > } > } > > -/* { dg-final { scan-tree-dump-times "Duplicating join block" 3 "split-paths" } } */ > +/* { dg-final { scan-tree-dump-times "Duplicating join block" 2 "split-paths" } } */ > diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c > index c3ea2d6..23000f6 100644 > --- a/gcc/tree-ssa-threadedge.c > +++ b/gcc/tree-ssa-threadedge.c > @@ -1157,6 +1157,90 @@ thread_through_normal_block (edge e, > return 0; > } > > +/* Return true if PHI's INDEX-th incoming value is a CMP, and the CMP is > + defined in the incoming basic block. Otherwise return false. */ > +static bool > +cmp_from_unconditional_block (gphi *phi, int index) > +{ > + tree value = gimple_phi_arg_def (phi, index); > + if (!(TREE_CODE (value) == SSA_NAME && has_single_use (value))) > + return false; Not sure why we should reject a constant here but I guess we expect it to find a simplified condition anyways ;) > + > + gimple *def = SSA_NAME_DEF_STMT (value); > + > + if (!is_gimple_assign (def)) > + return false; > + > + if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))) > + { > + value = gimple_assign_rhs1 (def); > + if (!(TREE_CODE (value) == SSA_NAME && has_single_use (value))) > + return false; > + > + def = SSA_NAME_DEF_STMT (value); > + > + if (!is_gimple_assign (def)) > + return false; too much vertial space. > + } > + > + if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison) > + return false; > + > + /* Check if phi's incoming value is defined in the incoming basic_block. */ > + edge e = gimple_phi_arg_edge (phi, index); > + if (def->bb != e->src) > + return false; why does this matter? > + > + if (!single_succ_p (def->bb)) > + return false; Or this? The actual threading will ensure this will hold true. > + return true; > +} > + > +/* There are basic blocks look like: > + > + p0 = a CMP b ; or p0 = (INT)( a CMP b) > + goto ; > + > + > + p1 = c CMP d > + goto ; > + > + > + # phi = PHI > + if (phi != 0) goto ; else goto ; > + > + Then, : a trivial join block. > + > + Check if BB is in like above. */ > + > +bool > +is_trivial_join_block (basic_block bb) I'd make this work on a specific edge. edge_forwards_conditional_to_conditional_jump_through_empty_bb_p (edge e) { basic_block b = e->dest; maybe too elaborate name ;) > +{ > + gimple *gs = last_and_only_stmt (bb); > + if (gs == NULL) > + return false; > + > + if (gimple_code (gs) != GIMPLE_COND) > + return false; > + > + tree cond = gimple_cond_lhs (gs); > + > + if(TREE_CODE (cond) != SSA_NAME) > + return false; space after if( too much vertical space in this function for my taste btw. For the forwarding to work we want a NE_EXPR or EQ_EXPR as gimple_cond_code and integer_one_p or integer_zero_p gimple_cond_rhs. > + > + if (gimple_code (SSA_NAME_DEF_STMT (cond)) != GIMPLE_PHI) > + return false; > + > + gphi *phi = as_a (SSA_NAME_DEF_STMT (cond)); I think to match your pattern you want to check that gimple_bb (phi) == bb as well here. > + for (unsigned int i = 0; i < phi->nargs; i++) > + if (!cmp_from_unconditional_block (phi, i)) Just process the incoming edge argument and inline the helper. You can use PHI_ARG_DEF_FROM_EDGE here. Thanks for integrating this into jump-threading - it does look like a good fit. How often does this trigger during bootstrap? Thanks, Richard.