From patchwork Mon May 6 14:24:04 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jiufu Guo X-Patchwork-Id: 1095858 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-500175-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="uoIDN2dM"; 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 44yQ3w1tMKz9s7T for ; Tue, 7 May 2019 00:24:40 +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=YPeYMxZaJSSN qn53c+AYHQL6xuMuuRGqBITz9QFOp9BXRlG4OJD6jzxeWCssvobX9n5mWt1C9l7E Kau2yqUDF4oM3Fe9UG6x9kbOzgGz3/M8TnunenRusUaeJLkIen7ZkzMUe6F5YgSn rCXvE+QDYaXjcba6Ig12iFFvsGdgSwY= 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=nSflDLArEr3l308ljE EF2X+RcGw=; b=uoIDN2dM/BvfrxXsoOKa8Bnkm6tqkjiUyNF9wslEWneOPXuUxL 0tVGcrqu8feUBi0CWfevqXKdgq45IS9UCFAMBRKCzr0P1SHPEHWEMhI87QfQKA9k QpTKjTeX1JNEOFKohgLD7dLItNIG/6WG8TAC+PbMbVA5bV//uw8KCd2qE= Received: (qmail 2107 invoked by alias); 6 May 2019 14:24:32 -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 1994 invoked by uid 89); 6 May 2019 14:24:24 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-27.6 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.1 spammy= 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; Mon, 06 May 2019 14:24:14 +0000 Received: from pps.filterd (m0098420.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x46EItM0077041 for ; Mon, 6 May 2019 10:24:12 -0400 Received: from e06smtp01.uk.ibm.com (e06smtp01.uk.ibm.com [195.75.94.97]) by mx0b-001b2d01.pphosted.com with ESMTP id 2sanf0ukuq-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Mon, 06 May 2019 10:24:12 -0400 Received: from localhost by e06smtp01.uk.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Mon, 6 May 2019 15:24:10 +0100 Received: from b06cxnps4076.portsmouth.uk.ibm.com (9.149.109.198) by e06smtp01.uk.ibm.com (192.168.101.131) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256/256) Mon, 6 May 2019 15:24:07 +0100 Received: from d06av25.portsmouth.uk.ibm.com (d06av25.portsmouth.uk.ibm.com [9.149.105.61]) by b06cxnps4076.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x46EO6cO52166724 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 6 May 2019 14:24:06 GMT Received: from d06av25.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id DAD8D11C04C; Mon, 6 May 2019 14:24:05 +0000 (GMT) Received: from d06av25.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id D6A4D11C04A; Mon, 6 May 2019 14:24:04 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by d06av25.portsmouth.uk.ibm.com (Postfix) with ESMTP; Mon, 6 May 2019 14:24:04 +0000 (GMT) From: Jiufu Guo To: gcc-patches@gcc.gnu.org Cc: jakub@redhat.com, rguenther@suse.de, dberlin@dberlin.org, segher@linux.ibm.com, wschmidt@linux.ibm.com Subject: [PATCH] Eliminates phi on branch for CMP result Date: Mon, 6 May 2019 09:24:04 -0500 x-cbid: 19050614-4275-0000-0000-00000331ED39 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 19050614-4276-0000-0000-0000384154D2 Message-Id: <1557152644-3063-1-git-send-email-guojiufu@linux.ibm.com> X-IsSubscribed: yes Hi, This patch implements the optimization in PR77820. The optimization eliminates phi and phi's basic block, if the phi is used only by condition branch, and the phi's incoming value in the result of a CMP result. 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. p0 = a CMP b goto ; p1 = c CMP d goto ; # phi = PHI if (phi != 0) goto ; else goto ; Transform to: p0 = a CMP b if (p0 != 0) goto ; else goto ; p1 = c CMP d if (p1 != 0) goto ; else goto ; Bootstrapped and tested on powerpc64le with no regressions, and testcases were saved. Is this ok for trunk? Thanks! [gcc] 2019-05-06 Jiufu Guo Lijia He PR tree-optimization/77820 * tree-ssa-mergephicmp.c: New file. * Makefile.in (OBJS): Add tree-ssa-mergephicmp.o. * common.opt (ftree-mergephicmp): New flag. * passes.def (pass_mergephicmp): New pass. * timevar.def (TV_TREE_MERGEPHICMP): New timevar. * tree-pass.h: New file. [gcc/testsuite] 2019-05-06 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/Makefile.in | 1 + gcc/common.opt | 4 + gcc/passes.def | 1 + gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c | 31 +++ gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c | 31 +++ gcc/timevar.def | 1 + gcc/tree-pass.h | 1 + gcc/tree-ssa-mergephicmp.c | 260 +++++++++++++++++++++++ 8 files changed, 330 insertions(+) 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/tree-ssa-mergephicmp.c diff --git a/gcc/Makefile.in b/gcc/Makefile.in index d186d71..9729501 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1567,6 +1567,7 @@ OBJS = \ tree-ssa-reassoc.o \ tree-ssa-sccvn.o \ tree-ssa-scopedtables.o \ + tree-ssa-mergephicmp.o \ tree-ssa-sink.o \ tree-ssa-strlen.o \ tree-ssa-structalias.o \ diff --git a/gcc/common.opt b/gcc/common.opt index d342c4f..5ea5ed2 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -2702,6 +2702,10 @@ ftree-salias Common Ignore Does nothing. Preserved for backward compatibility. +ftree-mergephicmp +Common Report Var(flag_mergephicmp) Init(1) Optimization +Enable optimization on branch phi compare on trees. + ftree-sink Common Report Var(flag_tree_sink) Optimization Enable SSA code sinking on trees. diff --git a/gcc/passes.def b/gcc/passes.def index 446a7c4..e3a3913 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -249,6 +249,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_lim); NEXT_PASS (pass_walloca, false); NEXT_PASS (pass_pre); + NEXT_PASS (pass_mergephicmp); NEXT_PASS (pass_sink_code); NEXT_PASS (pass_sancov); NEXT_PASS (pass_asan); 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..2e3f4f6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c @@ -0,0 +1,31 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-mergephicmp" } */ + +void g (void); +void g1 (void); + +void +f (long a, long b, long c, long d, int x) +{ + _Bool t; + if (x) + { + t = a < b; + } + else if (d == a + b) + { + t = c < d; + } + else + { + t = a == c; + } + + if (t) + { + g1 (); + g (); + } +} + +/* { dg-final { scan-tree-dump-not "PHI" "mergephicmp" } } */ 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..7c35417 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c @@ -0,0 +1,31 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-mergephicmp" } */ + +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 == a + b) + { + t = c < d; + } + else + { + t = a == c; + } + + if (t) + { + g1 (); + g (); + } +} + +/* { dg-final { scan-tree-dump-times "PHI" 0 "mergephicmp" } } */ diff --git a/gcc/timevar.def b/gcc/timevar.def index 5415446..91f92d7 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -170,6 +170,7 @@ DEFTIMEVAR (TV_TREE_SPLIT_EDGES , "tree split crit edges") DEFTIMEVAR (TV_TREE_REASSOC , "tree reassociation") DEFTIMEVAR (TV_TREE_PRE , "tree PRE") DEFTIMEVAR (TV_TREE_FRE , "tree FRE") +DEFTIMEVAR (TV_TREE_MERGEPHICMP , "tree branch on PHI compare") DEFTIMEVAR (TV_TREE_SINK , "tree code sinking") DEFTIMEVAR (TV_TREE_PHIOPT , "tree linearize phis") DEFTIMEVAR (TV_TREE_BACKPROP , "tree backward propagate") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 47be59b..e21e820 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -441,6 +441,7 @@ extern gimple_opt_pass *make_pass_tree_ifcombine (gcc::context *ctxt); extern gimple_opt_pass *make_pass_dse (gcc::context *ctxt); extern gimple_opt_pass *make_pass_nrv (gcc::context *ctxt); extern gimple_opt_pass *make_pass_rename_ssa_copies (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_mergephicmp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_sink_code (gcc::context *ctxt); extern gimple_opt_pass *make_pass_fre (gcc::context *ctxt); extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt); diff --git a/gcc/tree-ssa-mergephicmp.c b/gcc/tree-ssa-mergephicmp.c new file mode 100644 index 0000000..7bb82d5 --- /dev/null +++ b/gcc/tree-ssa-mergephicmp.c @@ -0,0 +1,260 @@ +/* Elimiate PHI nodes which come from comparasion and used by branch. + Copyright (C) 2004-2019 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 3, or (at your option) any +later version. + +GCC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "cfghooks.h" +#include "tree-pass.h" +#include "ssa.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" + +/* Return true if it is ok to merge phi's incoming value: + - phi's incoming value is + phi_arg = a CMP b + or + cmp = a CMP b + phi_arg = (INT_CONV) cmp + - phi's incoming value is defined in incoming basic block. + + * Parameter PHI: the phi to be checked. + * Parameter INDEX: index'th incoming argument of phi to be checked. */ +static bool +could_incoming_merge (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 (!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; +} + +/* Return true if the basic_block is ok to optimize: + + res = PHI + if (res != 0) goto l_true; goto l_false; + + The phi stmt is saved to argument PHI. + The gcond stmt is saved to argument GC. */ +static bool +could_optimize_phi_bb (basic_block bb, gphi **phi, gcond **gc) +{ + /* There should be only one phi. */ + gphi_iterator pi = gsi_start_phis (bb); + if (gsi_end_p (pi)) + return false; + + *phi = pi.phi (); + if (!has_single_use ((*phi)->result)) + return false; + + gsi_next (&pi); + if (!gsi_end_p (pi)) + return false; + + /* There should be only one stmt which is gcond. */ + gimple *gs = last_and_only_stmt (bb); + if (gs == NULL) + return false; + + if (!is_a (gs)) + return false; + + *gc = as_a (gs); + if (gimple_cond_lhs (*gc) != (*phi)->result) + return false; + + /* Check if all incoming basic blocks can merge. */ + for (unsigned int i = 0; i < (*phi)->nargs; i++) + if (!could_incoming_merge (*phi, i)) + return false; + + /* Check if there is no phi in any successors. */ + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, (*phi)->bb->succs) + { + if (!gsi_end_p (gsi_start_phis (e->dest))) + return false; + } + + return true; +} + +/* Merge the phi and the gcond into the index'th incoming block. */ +static void +merge_incoming_bb (gcond *gc, gphi *phi, int index) +{ + tree value = gimple_phi_arg_def (phi, index); + + gcond *new_gc = gimple_build_cond (gimple_cond_code (gc), value, + gimple_cond_rhs (gc), NULL, NULL); + + gimple *def = SSA_NAME_DEF_STMT (value); + gimple_stmt_iterator last = gsi_last_bb (def->bb); + gsi_insert_after (&last, new_gc, GSI_NEW_STMT); + + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, phi->bb->succs) + { + edge new_e = make_edge (def->bb, e->dest, e->flags); + new_e->probability = e->probability; + } +} + +/* If there are basic blocks look like: + + p0 = a CMP b + goto ; + + + p1 = c CMP d + goto ; + + + # phi = PHI + if (phi != 0) goto ; else goto ; + +Transform it to: + + + p0 = a CMP b + if (p0 != 0) goto ; else goto ; + + + p1 = c CMP d + if (p1 != 0) goto ; else goto ; */ + +static bool +mergephicmp_once (function *fun) +{ + bool change = false; + basic_block bb; + basic_block prev_need_delete = NULL; + + FOR_EACH_BB_FN (bb, fun) + { + gphi *phi; + gcond *gc; + + /* Prev bb can be deleted only after iterator move to next bb. */ + if (prev_need_delete) + delete_basic_block (prev_need_delete); + prev_need_delete = NULL; + + if (could_optimize_phi_bb (bb, &phi, &gc)) + { + for (unsigned int i = 0; i < phi->nargs; i++) + merge_incoming_bb (gc, phi, i); + + change = true; + prev_need_delete = bb; + } + } + + return change; +} + +namespace { + +const pass_data pass_data_mergephicmp = { + GIMPLE_PASS, /* type */ + "mergephicmp", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_TREE_MERGEPHICMP, /* tv_id */ + /* PROP_no_crit_edges is ensured by running split_critical_edges in + pass_data_sink_code::execute (). */ + (PROP_cfg | PROP_ssa), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ +}; + +class pass_mergephicmp : public gimple_opt_pass +{ +public: + pass_mergephicmp (gcc::context *ctxt) + : gimple_opt_pass (pass_data_mergephicmp, ctxt) + { + } + + /* opt_pass methods: */ + virtual bool gate (function *) { return flag_mergephicmp != 0; } + + virtual unsigned int execute (function *); + +}; // class pass_sink_code + +unsigned int +pass_mergephicmp::execute (function *fun) +{ + bool changed; + + if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1) + return 0; + + changed = mergephicmp_once (fun); + + if (changed) + free_dominance_info (CDI_DOMINATORS); + + return changed ? TODO_cleanup_cfg : 0; +} + +} // anon namespace + +gimple_opt_pass * +make_pass_mergephicmp (gcc::context *ctxt) +{ + return new pass_mergephicmp (ctxt); +}