From patchwork Tue Jun 4 05:28:55 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jiufu Guo X-Patchwork-Id: 1109619 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-502269-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=linux.ibm.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="BlEnhyo0"; dkim-atps=neutral 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 45J0rT6WCzz9s3Z for ; Tue, 4 Jun 2019 15:30:48 +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=xRhD4fT0xiYshiUCoY 7jfM14URxsx+DlF8CPjQ+XLsIEBQHOZjUowj/AV+EjfYeLesIC7ffwMgO9ESpAZn EE6Ike/mcXeBvLw8k++G8gqOkpjlW6TCMyFtCQ8nOGyC01YvOkvN7WyufkkjI5pL emQGRza2mfyJLxhLRLyWsyO50= 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=ZlvP9a5Fo0ujfnYB9ni5EC5w JT4=; b=BlEnhyo0VBLQOXFaOsy/zsbw/oxkxfbvOEugbpWtQ9dxJoRhe6biJZc+ WRZMQpA+FtNGcQRR04oVckCfcZxFMsH57qnd6OEq9qm6iGMw7e2QN+wddBgwF2W3 8RMMmEcShcAfe1rqT97sbaQsaqqaoEo71d+JaV5RvifckGIehrw= Received: (qmail 74130 invoked by alias); 4 Jun 2019 05:30:40 -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 74027 invoked by uid 89); 4 Jun 2019 05:30:27 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.8 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; Tue, 04 Jun 2019 05:30:25 +0000 Received: from pps.filterd (m0098404.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x545U4gE097577 for ; Tue, 4 Jun 2019 01:30:17 -0400 Received: from e11.ny.us.ibm.com (e11.ny.us.ibm.com [129.33.205.201]) by mx0a-001b2d01.pphosted.com with ESMTP id 2swhw1scwe-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Tue, 04 Jun 2019 01:30:17 -0400 Received: from localhost by e11.ny.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 4 Jun 2019 06:30:15 +0100 Received: from b01cxnp22036.gho.pok.ibm.com (9.57.198.26) by e11.ny.us.ibm.com (146.89.104.198) 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 06:30:12 +0100 Received: from b01ledav001.gho.pok.ibm.com (b01ledav001.gho.pok.ibm.com [9.57.199.106]) by b01cxnp22036.gho.pok.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x545SuqY27918750 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 4 Jun 2019 05:28:56 GMT Received: from b01ledav001.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 7D6FE28059; Tue, 4 Jun 2019 05:28:56 +0000 (GMT) Received: from b01ledav001.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id C162C28058; Tue, 4 Jun 2019 05:28:55 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by b01ledav001.gho.pok.ibm.com (Postfix) with ESMTPS; Tue, 4 Jun 2019 05:28:55 +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: [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> Date: Tue, 04 Jun 2019 00:28:55 -0500 In-Reply-To: (Jiufu Guo's message of "Sun, 02 Jun 2019 21:18:31 -0500") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) MIME-Version: 1.0 x-cbid: 19060405-2213-0000-0000-00000399C679 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.01212962; UDB=6.00637483; IPR=6.00994029; MB=3.00027175; MTD=3.00000008; XFM=3.00000015; UTC=2019-06-04 05:30:14 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 19060405-2214-0000-0000-00005EB263B8 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, 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. --- 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