From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 125413 invoked by alias); 4 Jun 2019 03:03:17 -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 125403 invoked by uid 89); 4 Jun 2019 03:03:17 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.1 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_LOW,SPF_PASS,UNSUBSCRIBE_BODY autolearn=ham version=3.3.1 spammy= X-HELO: mx0a-001b2d01.pphosted.com Received: from mx0a-001b2d01.pphosted.com (HELO mx0a-001b2d01.pphosted.com) (148.163.156.1) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 04 Jun 2019 03:03:14 +0000 Received: from pps.filterd (m0098399.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x542vtCq118611 for ; Mon, 3 Jun 2019 23:03:13 -0400 Received: from e35.co.us.ibm.com (e35.co.us.ibm.com [32.97.110.153]) by mx0a-001b2d01.pphosted.com with ESMTP id 2swdumdhcu-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Mon, 03 Jun 2019 23:03:12 -0400 Received: from localhost by e35.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 4 Jun 2019 04:03:12 +0100 Received: from b03cxnp08027.gho.boulder.ibm.com (9.17.130.19) by e35.co.us.ibm.com (192.168.1.135) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256/256) Tue, 4 Jun 2019 04:03:09 +0100 Received: from b03ledav001.gho.boulder.ibm.com (b03ledav001.gho.boulder.ibm.com [9.17.130.232]) by b03cxnp08027.gho.boulder.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x54338YQ26607966 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 4 Jun 2019 03:03:08 GMT Received: from b03ledav001.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 0C34C6E04C; Tue, 4 Jun 2019 03:03:08 +0000 (GMT) Received: from b03ledav001.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 7EFBE6E04E; Tue, 4 Jun 2019 03:03:07 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by b03ledav001.gho.boulder.ibm.com (Postfix) with ESMTPS; Tue, 4 Jun 2019 03:03:07 +0000 (GMT) From: Jiufu Guo To: Jeff Law Cc: Richard Biener , gcc-patches@gcc.gnu.org, Jakub Jelinek , Daniel Berlin , segher@kernel.crashing.org, wschmidt@linux.ibm.com Subject: Re: [PATCH V2] A jump threading opportunity for condition branch References: <1558446288-52444-1-git-send-email-guojiufu@linux.ibm.com> <08cc117a-52c7-adb7-2bef-1aef6379e5c6@redhat.com> Date: Tue, 04 Jun 2019 03:03:00 -0000 In-Reply-To: (Jeff Law's message of "Thu, 30 May 2019 17:35:43 -0600") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain x-cbid: 19060403-0012-0000-0000-0000173FF72A X-IBM-SpamModules-Scores: X-IBM-SpamModules-Versions: BY=3.00011211; HX=3.00000242; KW=3.00000007; PH=3.00000004; SC=3.00000286; SDB=6.01212916; UDB=6.00637453; IPR=6.00993981; MB=3.00027172; MTD=3.00000008; XFM=3.00000015; UTC=2019-06-04 03:03:11 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 19060403-0013-0000-0000-000057872804 Message-Id: X-IsSubscribed: yes X-SW-Source: 2019-06/txt/msg00134.txt.bz2 Jeff Law writes: > On 5/30/19 9:03 AM, Jiufu Guo wrote: >> Jeff Law writes: >> >>> On 5/29/19 6:36 AM, Richard Biener wrote: >>>> On Tue, 28 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. >>>>> >>>>> This version is based on the proposal of Richard, Jeff and Andrew, and >>>>> refined to incorporate comments. Thanks for the reviews! >>>>> >>>>> Bootstrapped and tested on powerpc64le and powerpc64be with no >>>>> regressions (one case is improved) and new testcases are added. Is this >>>>> ok for trunk? >>>>> >>>>> Example of this opportunity 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. >>>>> >>>>> Thanks! >>>>> Jiufu Guo >>>>> >>>>> >>>>> [gcc] >>>>> 2019-05-28 Jiufu Guo >>>>> Lijia He >>>>> >>>>> PR tree-optimization/77820 >>>>> * tree-ssa-threadedge.c >>>>> (edge_forwards_cmp_to_conditional_jump_through_empty_bb_p): New >>>>> function. >>>>> (thread_across_edge): Add call to >>>>> edge_forwards_cmp_to_conditional_jump_through_empty_bb_p. >>>>> >>>>> [gcc/testsuite] >>>>> 2019-05-28 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 | 30 ++++++++++ >>>>> gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c | 23 +++++++ >>>>> gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c | 25 ++++++++ >>>>> 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 | 76 +++++++++++++++++++++++- >>>>> 6 files changed, 192 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..5227c87 >>>>> --- /dev/null >>>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c >>>>> @@ -0,0 +1,30 @@ >>>>> +/* { 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..eaf89bb >>>>> --- /dev/null >>>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c >>>>> @@ -0,0 +1,23 @@ >>>>> +/* { 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..d5a1e0b >>>>> --- /dev/null >>>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c >>>>> @@ -0,0 +1,25 @@ >>>>> +/* { 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..53acabc >>>>> --- /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..36c413a 100644 >>>>> --- a/gcc/tree-ssa-threadedge.c >>>>> +++ b/gcc/tree-ssa-threadedge.c >>>>> @@ -1157,6 +1157,74 @@ thread_through_normal_block (edge e, >>>>> return 0; >>>>> } >>>>> >>>>> +/* 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, edge (P0,X) or (P1,X) could be marked as EDGE_START_JUMP_THREAD >>>>> + And edge (X,Y), (X,Z) is EDGE_COPY_SRC_JOINER_BLOCK >>>>> + >>>>> + Return true if E is (P0,X) or (P1,X) */ >>>>> + >>>>> +bool >>>>> +edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e) >>>>> +{ >>>>> + basic_block bb = e->dest; >>>>> + >>>>> + /* See if there is only one stmt which is gcond. */ >>>>> + gimple *gs = last_and_only_stmt (bb); >>>>> + if (gs == NULL || gimple_code (gs) != GIMPLE_COND) >>>>> + return false; >>>> gcond *gs; >>>> if (!(gs = safe_dyn_cast (last_and_only_stmt (bb)))) >>>> return false; >>>> >>>> makes the following gimple_cond_ accesses more efficient when >>>> checking is enabled. >>>> >>>>> + >>>>> + /* See if gcond's cond is "(phi !=/== 0/1)" in the basic block. */ >>>>> + tree cond = gimple_cond_lhs (gs); >>>>> + enum tree_code code = gimple_cond_code (gs); >>>>> + tree rhs = gimple_cond_rhs (gs); >>>>> + if (TREE_CODE (cond) != SSA_NAME >>>>> + || (code != NE_EXPR && code != EQ_EXPR) >>>>> + || (!integer_onep (rhs) && !integer_zerop (rhs))) >>>>> + return false; >>>>> + gphi *phi = dyn_cast (SSA_NAME_DEF_STMT (cond)); >>>>> + if (phi == NULL || gimple_bb (phi) != bb) >>>>> + return false; >>>>> + >>>>> + /* Check if phi's incoming value is CMP. */ >>>>> + gimple *def; >>>>> + tree value = PHI_ARG_DEF_FROM_EDGE (phi, e); >>>>> + if (TREE_CODE (value) == SSA_NAME >>>>> + && has_single_use (value) >>>>> + && is_gimple_assign (SSA_NAME_DEF_STMT (value))) >>>>> + def = SSA_NAME_DEF_STMT (value); >>>> Same is true here and below if you rewrite to >>>> >>>> gassign *def; >>>> tree value = PHI_ARG_DEF_FROM_EDGE (phi, e); >>>> if (TREE_CODE (value) != SSA_NAME >>>> || !has_single_use (value) >>>> || !(def = dyn_cast (SSA_NAME_DEF_STMT (value)))) >>>> return false; >>>> >>>> Otherwise it looks good. I'd like to have Jeffs opinion and >>>> final ACK here because we touch jump-threading and he's most >>>> familiar with that detail and the place you hook into. >>> I've got the full thread to look over. At a high level I wouldn't have >>> guessed it'd be this easy to get the threader handle this, but >>> occasionally we are surprised in a good way. Anyway, I'll be looking >>> through the full discussion. >>> >>> Jeff >> >> Hi Jeff, Richard and all, >> >> Thanks a lot for your great comments in all threads. Based on those >> comments, I refined the code as below: >> >> bool >> edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e) >> { >> /* See if there is only one stmt which is gcond. */ >> gcond *gs; >> if (!(gs = safe_dyn_cast (last_and_only_stmt (e->dest)))) >> return false; >> >> /* See if gcond's cond is "(phi !=/== 0/1)" in the basic block. */ >> tree cond = gimple_cond_lhs (gs); >> enum tree_code code = gimple_cond_code (gs); >> tree rhs = gimple_cond_rhs (gs); >> if (TREE_CODE (cond) != SSA_NAME >> || (code != NE_EXPR && code != EQ_EXPR) >> || (!integer_onep (rhs) && !integer_zerop (rhs))) >> return false; >> gphi *phi = dyn_cast (SSA_NAME_DEF_STMT (cond)); >> if (phi == NULL || gimple_bb (phi) != e->dest) >> return false; >> >> /* Check if phi's incoming value is CMP. */ >> gassign *def; >> tree value = PHI_ARG_DEF_FROM_EDGE (phi, e); >> if (TREE_CODE (value) != SSA_NAME >> || !has_single_use (value) >> || !(def = dyn_cast (SSA_NAME_DEF_STMT (value)))) >> return false; >> >> /* Or if it is (INT) (a CMP b). */ >> 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) >> || !(def = dyn_cast (SSA_NAME_DEF_STMT (value)))) >> return false; >> } >> >> if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison) >> return false; >> >> if (!single_succ_p (e->src)) >> return false; >> >> return true; >> } >> >> >> In this code, I put "if (!single_succ_p (e->src))" there, which may be >> helpful for reducing the copy block. > Sounds good. My testing did show a regression on the sh port. > > For pr51244-20 on the SH port your changes make the ultimate resulting > code better, but compromise the test. We can restore the shape of the > CFG and get the testing coverage for sh_treg_combine by disabling VRP > and DOM. > > Can you please include the attached patch in your next update? Thanks, I sent out a new version patch to include this update. Jiufu Guo > > Jeff > diff --git a/gcc/testsuite/gcc.target/sh/pr51244-20.c b/gcc/testsuite/gcc.target/sh/pr51244-20.c > index c342163160b..be265cd16af 100644 > --- a/gcc/testsuite/gcc.target/sh/pr51244-20.c > +++ b/gcc/testsuite/gcc.target/sh/pr51244-20.c > @@ -1,7 +1,7 @@ > /* Check that the SH specific sh_treg_combine RTL optimization pass works as > expected. */ > /* { dg-do compile } */ > -/* { dg-options "-O2" } */ > +/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-vrp" } */ > > /* { dg-final { scan-assembler-not "not\t" } } */ > /* { dg-final { scan-assembler-times "cmp/eq" 2 } } */