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?

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

Reply via email to