On Tue, 7 May 2019, Andrew Pinski wrote:
> 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.
The awkward part is that it changes the CFG so it doesn't fit forwprop
well. I thought of ifcombine which kind-of does a reverse transform
but in the end it is really duplicating <X> to get rid of the PHI and
then applying forwprop.
Richard.
> 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
> >
>
--
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)
