On Mon, May 6, 2019 at 7:24 AM Jiufu Guo <guoji...@linux.ibm.com> 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?
forwprop was created orginally to something similar but this case is a
specific case of backwards prop (almost).
I wonder if it could be combined with that or as Richard mentioned,
jump threading.
Thanks,
Andrew Pinski
>
> 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);
> +}
> --
> 2.7.4
>
