From patchwork Mon Jun 3 02:18:31 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jiufu Guo X-Patchwork-Id: 1109038 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-502165-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=linux.ibm.com Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 45HJdh54fDz9s1c for ; Mon, 3 Jun 2019 12:18:54 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:references:date:in-reply-to:mime-version :content-type:message-id; q=dns; s=default; b=ESdgz2nOdaSm+WCjPm /U52KNFtSQ900JgaAaKFWRbCZ94+XKzVV1J51/IzNtf8RR7R+TN7ex3pCOzNOw1D g6+WV0ID9BYArYLMWca5kFTXBbGwVP45Gqba7AfgppBBGvHiYleWAVEk7xdL04Y2 CzesFRC9sKbRPwePWyxVNirdw= 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:from :to:cc:subject:references:date:in-reply-to:mime-version :content-type:message-id; s=default; bh=ngZ1/cy+PkQduxb6vtrAx5Md DHE=; b=IJek/hIW9mPui834HKGLc3wvVHPLB9Juy88TC6f36FKU3x4bFTifjYxa l0k4fh34p1DFpDiDKXHCkm61OjocpH1P9LYoUZoqf3k7U3K+Uz2mGiEHUv3rPaFu uZ0NcTjxEs3qaXxWO43WT4qUEmeug4uKm6QI8IpU3LBXJSDz16c= Received: (qmail 15049 invoked by alias); 3 Jun 2019 02:18:43 -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 15037 invoked by uid 89); 3 Jun 2019 02:18:42 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.7 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; Mon, 03 Jun 2019 02:18:40 +0000 Received: from pps.filterd (m0098410.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x532HE87105630 for ; Sun, 2 Jun 2019 22:18:39 -0400 Received: from e33.co.us.ibm.com (e33.co.us.ibm.com [32.97.110.151]) by mx0a-001b2d01.pphosted.com with ESMTP id 2svs7yahr8-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Sun, 02 Jun 2019 22:18:38 -0400 Received: from localhost by e33.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Mon, 3 Jun 2019 03:18:38 +0100 Received: from b03cxnp08026.gho.boulder.ibm.com (9.17.130.18) by e33.co.us.ibm.com (192.168.1.133) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256/256) Mon, 3 Jun 2019 03:18:34 +0100 Received: from b03ledav002.gho.boulder.ibm.com (b03ledav002.gho.boulder.ibm.com [9.17.130.233]) by b03cxnp08026.gho.boulder.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x532IXfN19661294 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 3 Jun 2019 02:18:33 GMT Received: from b03ledav002.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 5314E136059; Mon, 3 Jun 2019 02:18:33 +0000 (GMT) Received: from b03ledav002.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id B012413604F; Mon, 3 Jun 2019 02:18:32 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by b03ledav002.gho.boulder.ibm.com (Postfix) with ESMTPS; Mon, 3 Jun 2019 02:18:32 +0000 (GMT) From: Jiufu Guo To: Jeff Law , Richard Biener Cc: gcc-patches@gcc.gnu.org, Jakub Jelinek , Daniel Berlin , segher@kernel.crashing.org, wschmidt@linux.ibm.com Subject: [PATCH V3] 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> Date: Sun, 02 Jun 2019 21:18:31 -0500 In-Reply-To: <3366d732-a85b-b7e2-71de-1b3ff3037b55@redhat.com> (Jeff Law's message of "Thu, 30 May 2019 09:25:54 -0600") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) MIME-Version: 1.0 x-cbid: 19060302-0036-0000-0000-00000AC60BF9 X-IBM-SpamModules-Scores: X-IBM-SpamModules-Versions: BY=3.00011206; HX=3.00000242; KW=3.00000007; PH=3.00000004; SC=3.00000286; SDB=6.01212428; UDB=6.00637156; IPR=6.00993486; MB=3.00027158; MTD=3.00000008; XFM=3.00000015; UTC=2019-06-03 02:18:36 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 19060302-0037-0000-0000-00004C0B438C Message-Id: X-IsSubscribed: yes 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. 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-05-31 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-31 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. --- 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 | 73 +++++++++++++++++++++++- 7 files changed, 190 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..d632ad0 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -1157,6 +1157,71 @@ 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; + + if (!single_succ_p (e->src)) + 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 +1382,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