On Mon, 6 May 2019, Jiufu Guo wrote:
> 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>
> p0 = a CMP b
> goto <X>;
>
> <P1>
> p1 = c CMP d
> goto <X>;
>
> <X>
> # phi = PHI <p0 (P0), p1 (P1)>
> if (phi != 0) goto <Y>; else goto <Z>;
>
> Transform to:
>
> <P0>
> p0 = a CMP b
> if (p0 != 0) goto <Y>; else goto <Z>;
>
> <P1>
> p1 = c CMP d
> if (p1 != 0) goto <Y>; else goto <Z>;
>
> Bootstrapped and tested on powerpc64le with no regressions, and testcases were
> saved. Is this ok for trunk?
I'm not sure I like a new pass here ;) The transform is basically
tail-duplicating the PHI block because the exit conditional can
be "simplfied" - that's something jump threading generally does
though it relies on "simplified" being a little bit more simplified
than above.
I suspect this transform was implemented because of some benchmark?
I suspect the performance benefit is because of better branch
prediction by not mangling both conditional branches into one?
The transform is also somewhat similar to tail-duplication done
in path splitting or tracer.
The pass itself does quite strict pattern-matching but I wonder
if more cases should be handled this way.
Any specific reason for the pass placement between PRE and sinking?
tracer and path splitting run much later, jump threading runs
all over the place.
Thanks,
Richard.
> Thanks!
>
> [gcc]
> 2019-05-06 Jiufu Guo <guoji...@linux.ibm.com>
> Lijia He <heli...@linux.ibm.com>
>
> 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 <guoji...@linux.ibm.com>
> Lijia He <heli...@linux.ibm.com>
>
> 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
> +<http://www.gnu.org/licenses/>. */
> +
> +#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:
> + <X>
> + res = PHI <v0(b0), v1(b1)...>
> + 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<gcond *> (gs))
> + return false;
> +
> + *gc = as_a<gcond *> (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>
> + p0 = a CMP b
> + goto <X>;
> +
> + <P1>
> + p1 = c CMP d
> + goto <X>;
> +
> + <X>
> + # phi = PHI <p0 (P0), p1 (P1)>
> + if (phi != 0) goto <Y>; else goto <Z>;
> +
> +Transform it to:
> +
> + <P0>
> + p0 = a CMP b
> + if (p0 != 0) goto <Y>; else goto <Z>;
> +
> + <P1>
> + p1 = c CMP d
> + if (p1 != 0) goto <Y>; else goto <Z>; */
> +
> +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);
> +}
>
--
Richard Biener <rguent...@suse.de>
SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)
