From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 116328 invoked by alias); 21 May 2019 13:45:01 -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 116311 invoked by uid 89); 21 May 2019 13:45:01 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-18.2 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=splitpaths, split-paths, sk:CONVERT X-HELO: mx0a-001b2d01.pphosted.com Received: from mx0b-001b2d01.pphosted.com (HELO mx0a-001b2d01.pphosted.com) (148.163.158.5) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 21 May 2019 13:44:59 +0000 Received: from pps.filterd (m0098414.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x4LDaw2h047839 for ; Tue, 21 May 2019 09:44:55 -0400 Received: from e06smtp03.uk.ibm.com (e06smtp03.uk.ibm.com [195.75.94.99]) by mx0b-001b2d01.pphosted.com with ESMTP id 2smgepe2ms-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Tue, 21 May 2019 09:44:55 -0400 Received: from localhost by e06smtp03.uk.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 21 May 2019 14:44:53 +0100 Received: from b06cxnps3075.portsmouth.uk.ibm.com (9.149.109.195) by e06smtp03.uk.ibm.com (192.168.101.133) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256/256) Tue, 21 May 2019 14:44:51 +0100 Received: from b06wcsmtp001.portsmouth.uk.ibm.com (b06wcsmtp001.portsmouth.uk.ibm.com [9.149.105.160]) by b06cxnps3075.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x4LDiotd62914778 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 21 May 2019 13:44:51 GMT Received: from b06wcsmtp001.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id B6499A405B; Tue, 21 May 2019 13:44:50 +0000 (GMT) Received: from b06wcsmtp001.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id B51C3A4060; Tue, 21 May 2019 13:44:49 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by b06wcsmtp001.portsmouth.uk.ibm.com (Postfix) with ESMTP; Tue, 21 May 2019 13:44:49 +0000 (GMT) From: Jiufu Guo To: gcc-patches@gcc.gnu.org Cc: jakub@redhat.com, rguenther@suse.de, dberlin@dberlin.org, segher@kernel.crashing.org, wschmidt@linux.ibm.com Subject: [PATCH] A jump threading opportunity for condition branch Date: Tue, 21 May 2019 13:45:00 -0000 x-cbid: 19052113-0012-0000-0000-0000031DF7C4 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 19052113-0013-0000-0000-00002156A8DF Message-Id: <1558446288-52444-1-git-send-email-guojiufu@linux.ibm.com> X-IsSubscribed: yes X-SW-Source: 2019-05/txt/msg01390.txt.bz2 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; + + 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; + } + + 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; + + if (!single_succ_p (def->bb)) + return false; + + 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) +{ + 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; + + if (gimple_code (SSA_NAME_DEF_STMT (cond)) != GIMPLE_PHI) + return false; + + gphi *phi = as_a (SSA_NAME_DEF_STMT (cond)); + + for (unsigned int i = 0; i < phi->nargs; i++) + if (!cmp_from_unconditional_block (phi, i)) + 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 +1401,11 @@ 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 || is_trivial_join_block (e->dest)) { - 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 -- 2.7.4