From patchwork Tue May 21 13:44:48 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jiufu Guo X-Patchwork-Id: 1102785 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-501337-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="U+PG8iul"; 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 457cTP3st2z9sBV for ; Tue, 21 May 2019 23:45:09 +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:date:message-id; q=dns; s=default; b=f5Sc1NIgPuET 9vr/MeZ0Kc20Aw0mrliQt0AM8HBki5CxcTKUO15gM8Zkv2h9DoTLgPt5DINACeSC CDA5497D3S0AfYuK4Sv0dkTRut6+a84Yjwdr7SvOSwyb49gx4v7cTiPCfn48fx1Q RZhkpmUymAwfHbUG2GMWFRug0ohwli4= 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:date:message-id; s=default; bh=oYbsKN5GYoA3gkQCEA zlAph3J+Q=; b=U+PG8iulS3REKFdgTxxb1QaZGn1FInT5AQyKgGcVzvcRkl+3Ar JPcclRweaQvaloRpOexs3ifBGk/jA8p1gZ2k8OeNGYjyee41F662yUdSLFwoy5Eu C2tkmNypFl6LNeogQQoHpgyVLKrdH2TPuPUfND2DOMu1WtTeHNp0VG9kQ= 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-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 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 08:44:48 -0500 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 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