From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 35073 invoked by alias); 14 Jun 2019 12:51:18 -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 35064 invoked by uid 89); 14 Jun 2019 12:51:18 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-23.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 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; Fri, 14 Jun 2019 12:51:15 +0000 Received: from pps.filterd (m0098393.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x5ECma5p066238 for ; Fri, 14 Jun 2019 08:51:13 -0400 Received: from e32.co.us.ibm.com (e32.co.us.ibm.com [32.97.110.150]) by mx0a-001b2d01.pphosted.com with ESMTP id 2t4a30517d-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Fri, 14 Jun 2019 08:51:13 -0400 Received: from localhost by e32.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Fri, 14 Jun 2019 13:51:12 +0100 Received: from b03cxnp08027.gho.boulder.ibm.com (9.17.130.19) by e32.co.us.ibm.com (192.168.1.132) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256/256) Fri, 14 Jun 2019 13:51: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 x5ECp8xH22151486 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 14 Jun 2019 12:51:08 GMT Received: from b03ledav001.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 813F36E04E; Fri, 14 Jun 2019 12:51:08 +0000 (GMT) Received: from b03ledav001.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 059D96E052; Fri, 14 Jun 2019 12:51:07 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by b03ledav001.gho.boulder.ibm.com (Postfix) with ESMTPS; Fri, 14 Jun 2019 12:51: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 V4] A jump threading opportunity for condition branch References: <1558446288-52444-1-git-send-email-guojiufu@linux.ibm.com> <3366d732-a85b-b7e2-71de-1b3ff3037b55@redhat.com> <591820c3-6952-5276-970c-fd9dcd7263ca@redhat.com> Date: Fri, 14 Jun 2019 12:51:00 -0000 In-Reply-To: <591820c3-6952-5276-970c-fd9dcd7263ca@redhat.com> (Jeff Law's message of "Thu, 13 Jun 2019 12:55:59 -0600") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain x-cbid: 19061412-0004-0000-0000-0000151C20F1 X-IBM-SpamModules-Scores: X-IBM-SpamModules-Versions: BY=3.00011260; HX=3.00000242; KW=3.00000007; PH=3.00000004; SC=3.00000286; SDB=6.01217843; UDB=6.00640448; IPR=6.00998965; MB=3.00027308; MTD=3.00000008; XFM=3.00000015; UTC=2019-06-14 12:51:11 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 19061412-0005-0000-0000-00008C15BF6C Message-Id: X-IsSubscribed: yes X-SW-Source: 2019-06/txt/msg00831.txt.bz2 Jeff Law writes: > On 6/3/19 11:28 PM, 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 on >> previous versions, and refined to incorporate comments, such as accept >> the path with single_succ_p (e->src). >> Thanks for the reviews! >> >> Bootstrapped and tested on powerpc64le, powerpc64 and sh (with help >> from Jeff) with no regressions (two cases are improved and updated >> to keep original test coverage) 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) p0 if there is. >> >> Thanks! >> Jiufu Guo >> >> [gcc] >> 2019-06-04 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-06-04 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.target/sh/pr51244-20.c: Update testcase. > Yes, this is OK for the trunk. I'll commit it momentarily. Thanks Jeff! I got svn access, I could commit next time. > > Jeff > > > > >> >> >> --- >> 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/testsuite/gcc.target/sh/pr51244-20.c | 2 +- >> gcc/tree-ssa-threadedge.c | 70 +++++++++++++++++++++++- >> 7 files changed, 187 insertions(+), 5 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..fb171cd 100644 >> --- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c >> @@ -1,5 +1,5 @@ >> /* { dg-do compile } */ >> -/* { dg-options "-O2 -fsplit-paths -fno-tree-cselim -fdump-tree-split-paths-details -w" } */ >> +/* { dg-options "-O2 -fsplit-paths -fno-tree-cselim -fdump-tree-split-paths-details -fno-tree-dominator-opts -fno-tree-vrp -w" } */ >> >> struct __sFILE >> { >> diff --git a/gcc/testsuite/gcc.target/sh/pr51244-20.c b/gcc/testsuite/gcc.target/sh/pr51244-20.c >> index c342163..be265cd 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 } } */ >> diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c >> index c3ea2d6..785227d 100644 >> --- a/gcc/tree-ssa-threadedge.c >> +++ b/gcc/tree-ssa-threadedge.c >> @@ -1157,6 +1157,68 @@ 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) >> +{ >> + /* 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; >> + >> + return true; >> +} >> + >> /* We are exiting E->src, see if E->dest ends with a conditional >> jump which has a known value when reached via E. >> >> @@ -1317,10 +1379,12 @@ thread_across_edge (gcond *dummy_cond, >> >> /* If we were able to thread through a successor of E->dest, then >> record the jump threading opportunity. */ >> - if (found) >> + if (found >> + || edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (e)) >> { >> - propagate_threaded_block_debug_into (path->last ()->e->dest, >> - taken_edge->dest); >> + if (taken_edge->dest != path->last ()->e->dest) >> + propagate_threaded_block_debug_into (path->last ()->e->dest, >> + taken_edge->dest); >> register_jump_thread (path); >> } >> else >>