[PATCH 0/6] Improve PHIOPT match and simplify for diamond shaped bbs

[PATCH 0/6] Improve PHIOPT match and simplify for diamond shaped bbs

[Andrew Pinski]

This set of patches implement match and simplify for diamond shaped bbs.
Right now there are no match-and-simplify patterns which take advantages
of this directly. Though predicates can cause a diamond shaped bb to
show up in phiopt1 even though the BB is empty. This allows
for that and fixes phi-opt-23.c/phi-opt-24.c testcases.


Andrew Pinski (6):
  PHIOPT: Move check on diamond bb to tree_ssa_phiopt_worker from
    minmax_replacement
  PHIOPT: Cleanup tree_ssa_phiopt_worker code
  PHIOPT: Allow other diamond uses when do_hoist_loads is true
  PHIOPT: Factor out some code from match_simplify_replacement
  PHIOPT: Ignore predicates for match-and-simplify phi-opt
  PHIOPT: Add support for diamond shaped bb to
    match_simplify_replacement

 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c    |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c    |   4 +-
 .../gcc.dg/tree-ssa/ssa-ifcombine-13.c        |   4 +-
 gcc/tree-ssa-phiopt.cc                        | 360 ++++++++++--------
 4 files changed, 218 insertions(+), 154 deletions(-)

-- 
2.39.1

[PATCH 1/6] PHIOPT: Move check on diamond bb to tree_ssa_phiopt_worker from minmax_replacement

[Andrew Pinski]

This moves the check to make sure on the diamond shaped form bbs that
the the two middle bbs are only for that diamond shaped form earlier
in the shared code.
Also remove the redundant check for single_succ_p since that was already
done before hand.
The next patch will simplify the code even further and remove redundant
checks.

gcc/ChangeLog:

	* tree-ssa-phiopt.cc (tree_ssa_phiopt_worker): Move the
	diamond form check from ...
	(minmax_replacement): Here.
---
 gcc/tree-ssa-phiopt.cc | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index d886c88215b..296ba646e62 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -220,6 +220,14 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
 	  continue;
 	}
 
+      if (diamond_p)
+	{
+	  if (!single_pred_p (bb1)
+	      || !single_pred_p (bb2)
+	      || !single_succ_p (bb2))
+	    continue;
+	}
+
       if (do_store_elim && !diamond_p)
 	{
 	  /* Also make sure that bb1 only have one predecessor and that it
@@ -2032,12 +2040,6 @@ minmax_replacement (basic_block cond_bb, basic_block middle_bb, basic_block alt_
       tree alt_lhs, alt_op0, alt_op1;
       bool invert = false;
 
-      if (!single_pred_p (middle_bb)
-	  || !single_pred_p (alt_middle_bb)
-	  || !single_succ_p (middle_bb)
-	  || !single_succ_p (alt_middle_bb))
-	return false;
-
       /* When THREEWAY_P then e1 will point to the edge of the final transition
 	 from middle-bb to end.  */
       if (true_edge == e0)
-- 
2.39.1

[PATCH 2/6] PHIOPT: Cleanup tree_ssa_phiopt_worker code

[Andrew Pinski]

This patch cleans up tree_ssa_phiopt_worker by merging
common code. Making do_store_elim handled earlier.
Note this does not change any overall logic of the code,
just moves code around enough to be able to do this.
This will make it easier to move code around even more
and a few other fixes I have.
Plus I think all of the do_store_elim code really
should move to its own function as how much code is shared
is now obvious not much.

OK? Bootstrapped and tested on x86_64-linux-gnu.

gcc/ChangeLog:

	* tree-ssa-phiopt.cc (tree_ssa_phiopt_worker): Rearrange
	code for better code readability.
---
 gcc/tree-ssa-phiopt.cc | 212 +++++++++++++++++++++--------------------
 1 file changed, 107 insertions(+), 105 deletions(-)

diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index 296ba646e62..05f19825ce9 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -175,10 +175,14 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
 	  std::swap (bb1, bb2);
 	  std::swap (e1, e2);
 	}
-      else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
+      else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
+	       && single_succ_p (bb2))
 	{
 	  diamond_p = true;
 	  e2 = EDGE_SUCC (bb2, 0);
+	  /* Make sure bb2 is just a fall through. */
+	  if ((e2->flags & EDGE_FALLTHRU) == 0)
+	    continue;
 	}
       else
 	continue;
@@ -190,46 +194,23 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
 	  || (e1->flags & EDGE_FALLTHRU) == 0)
 	continue;
 
-      if (do_store_elim && diamond_p)
+      if (do_store_elim)
 	{
-	  basic_block bb3 = e1->dest;
-
-	  if (!single_succ_p (bb2)
-	      || (e2->flags & EDGE_FALLTHRU) == 0
-	      || EDGE_COUNT (bb3->preds) != 2)
-	    continue;
-	  if (cond_if_else_store_replacement (bb1, bb2, bb3))
-	    cfgchanged = true;
-	  continue;
-	}
-      else if (do_hoist_loads && diamond_p)
-	{
-	  basic_block bb3 = e1->dest;
-
-	  if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
-	      && single_succ_p (bb2)
-	      && single_pred_p (bb1)
-	      && single_pred_p (bb2)
-	      && EDGE_COUNT (bb->succs) == 2
-	      && EDGE_COUNT (bb3->preds) == 2
-	      /* If one edge or the other is dominant, a conditional move
-		 is likely to perform worse than the well-predicted branch.  */
-	      && !predictable_edge_p (EDGE_SUCC (bb, 0))
-	      && !predictable_edge_p (EDGE_SUCC (bb, 1)))
-	    hoist_adjacent_loads (bb, bb1, bb2, bb3);
-	  continue;
-	}
-
-      if (diamond_p)
-	{
-	  if (!single_pred_p (bb1)
-	      || !single_pred_p (bb2)
-	      || !single_succ_p (bb2))
-	    continue;
-	}
+	  if (diamond_p)
+	    {
+	      basic_block bb3 = e1->dest;
+
+	      /* Only handle sinking of store from 2 bbs only,
+		 The middle bbs don't need to come from the
+		 if always since we are sinking rather than
+		 hoisting. */
+	      if (EDGE_COUNT (bb3->preds) != 2)
+		continue;
+	      if (cond_if_else_store_replacement (bb1, bb2, bb3))
+		cfgchanged = true;
+	      continue;
+	    }
 
-      if (do_store_elim && !diamond_p)
-	{
 	  /* Also make sure that bb1 only have one predecessor and that it
 	     is bb.  */
 	  if (!single_pred_p (bb1)
@@ -243,85 +224,106 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
 	    continue;
 	  if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
 	    cfgchanged = true;
+	  continue;
 	}
-      else
+
+      if (diamond_p)
 	{
-	  gimple_stmt_iterator gsi;
-	  bool candorest = true;
+	  basic_block bb3 = e1->dest;
+
+	  if (!single_pred_p (bb1)
+	      || !single_pred_p (bb2))
+	    continue;
 
-	  /* Check that we're looking for nested phis.  */
-	  basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
-	  gimple_seq phis = phi_nodes (merge);
+	  if (do_hoist_loads
+	      && !FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
+	      && EDGE_COUNT (bb->succs) == 2
+	      && EDGE_COUNT (bb3->preds) == 2
+	      /* If one edge or the other is dominant, a conditional move
+		 is likely to perform worse than the well-predicted branch.  */
+	      && !predictable_edge_p (EDGE_SUCC (bb, 0))
+	      && !predictable_edge_p (EDGE_SUCC (bb, 1)))
+	    {
+	      hoist_adjacent_loads (bb, bb1, bb2, bb3);
+	      continue;
+	    }
+	}
 
-	  /* Value replacement can work with more than one PHI
-	     so try that first. */
-	  if (!early_p && !diamond_p)
-	    for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
+      gimple_stmt_iterator gsi;
+      bool candorest = true;
+
+      /* Check that we're looking for nested phis.  */
+      basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
+      gimple_seq phis = phi_nodes (merge);
+
+      /* Value replacement can work with more than one PHI
+	 so try that first. */
+      if (!early_p && !diamond_p)
+	for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
+	  {
+	    phi = as_a <gphi *> (gsi_stmt (gsi));
+	    arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
+	    arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
+	    if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
 	      {
-		phi = as_a <gphi *> (gsi_stmt (gsi));
-		arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
-		arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
-		if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
-		  {
-		    candorest = false;
-		    cfgchanged = true;
-		    break;
-		  }
+		candorest = false;
+		cfgchanged = true;
+		break;
 	      }
+	  }
 
-	  if (!candorest)
-	    continue;
+      if (!candorest)
+	continue;
 
-	  phi = single_non_singleton_phi_for_edges (phis, e1, e2);
-	  if (!phi)
-	    continue;
+      phi = single_non_singleton_phi_for_edges (phis, e1, e2);
+      if (!phi)
+	continue;
+
+      arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
+      arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
 
+      /* Something is wrong if we cannot find the arguments in the PHI
+	  node.  */
+      gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
+
+      gphi *newphi;
+      if (single_pred_p (bb1)
+	  && !diamond_p
+	  && (newphi = factor_out_conditional_conversion (e1, e2, phi,
+							  arg0, arg1,
+							  cond_stmt)))
+	{
+	  phi = newphi;
+	  /* factor_out_conditional_conversion may create a new PHI in
+	     BB2 and eliminate an existing PHI in BB2.  Recompute values
+	     that may be affected by that change.  */
 	  arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
 	  arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
-
-	  /* Something is wrong if we cannot find the arguments in the PHI
-	     node.  */
 	  gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
-
-	  gphi *newphi;
-	  if (single_pred_p (bb1)
-	      && !diamond_p
-	      && (newphi = factor_out_conditional_conversion (e1, e2, phi,
-							      arg0, arg1,
-							      cond_stmt)))
-	    {
-	      phi = newphi;
-	      /* factor_out_conditional_conversion may create a new PHI in
-		 BB2 and eliminate an existing PHI in BB2.  Recompute values
-		 that may be affected by that change.  */
-	      arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
-	      arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
-	      gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
-	    }
-
-	  /* Do the replacement of conditional if it can be done.  */
-	  if (!early_p
-	      && !diamond_p
-	      && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
-	    cfgchanged = true;
-	  else if (!diamond_p
-		   && match_simplify_replacement (bb, bb1, e1, e2, phi,
-						  arg0, arg1, early_p))
-	    cfgchanged = true;
-	  else if (!early_p
-		   && !diamond_p
-		   && single_pred_p (bb1)
-		   && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
-							    phi, arg0, arg1))
-	    cfgchanged = true;
-	  else if (minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1,
-				       diamond_p))
-	    cfgchanged = true;
-	  else if (single_pred_p (bb1)
-		   && !diamond_p
-		   && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
-	    cfgchanged = true;
 	}
+
+      /* Do the replacement of conditional if it can be done.  */
+      if (!early_p
+	  && !diamond_p
+	  && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
+	cfgchanged = true;
+      else if (!diamond_p
+	       && match_simplify_replacement (bb, bb1, e1, e2, phi,
+					      arg0, arg1, early_p))
+	cfgchanged = true;
+      else if (!early_p
+	       && !diamond_p
+	       && single_pred_p (bb1)
+	       && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
+							phi, arg0, arg1))
+	cfgchanged = true;
+      else if (minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1,
+				   diamond_p))
+	cfgchanged = true;
+      else if (single_pred_p (bb1)
+	       && !diamond_p
+	       && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
+	cfgchanged = true;
     }
 
   free (bb_order);
-- 
2.39.1

[PATCH 3/6] PHIOPT: Allow other diamond uses when do_hoist_loads is true

[Andrew Pinski]

While working on adding diamond shaped form to match-and-simplify
phiopt, I Noticed that we would not reach there if do_hoist_loads
was true. In the original code before the cleanups it was not
obvious why but after I finished the cleanups, it was just a matter
of removing a continue and that is what this patch does.

This just happens also to fix a bug report that I noticed too.

OK? Bootstrapped and tested on x86_64-linux-gnu.

gcc/ChangeLog:

	PR tree-optimize/68894
	* tree-ssa-phiopt.cc (tree_ssa_phiopt_worker): Remove the
	continue for the do_hoist_loads diamond case.
---
 gcc/tree-ssa-phiopt.cc | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index 05f19825ce9..e4062f33efa 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -243,10 +243,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
 		 is likely to perform worse than the well-predicted branch.  */
 	      && !predictable_edge_p (EDGE_SUCC (bb, 0))
 	      && !predictable_edge_p (EDGE_SUCC (bb, 1)))
-	    {
-	      hoist_adjacent_loads (bb, bb1, bb2, bb3);
-	      continue;
-	    }
+	    hoist_adjacent_loads (bb, bb1, bb2, bb3);
 	}
 
       gimple_stmt_iterator gsi;
-- 
2.39.1

[PATCH 4/6] PHIOPT: Factor out some code from match_simplify_replacement

[Andrew Pinski]

This factors out the code checking if we have an empty bb
or one statement that feeds into the phi so it can be used
when adding diamond shaped bb form to match_simplify_replacement
in the next patch. Also allows for some improvements
in the next patches too.

OK? Bootstrapped and tested on x86_64-linux-gnu.

gcc/ChangeLog:

	* tree-ssa-phiopt.cc (empty_bb_or_one_feeding_into_p):
	New function.
	(match_simplify_replacement): Call
	empty_bb_or_one_feeding_into_p instead of doing it inline.
---
 gcc/tree-ssa-phiopt.cc | 106 ++++++++++++++++++++++++-----------------
 1 file changed, 62 insertions(+), 44 deletions(-)

diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index e4062f33efa..cb4d8788b56 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -940,6 +940,66 @@ gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
   return NULL;
 }
 
+/* empty_bb_or_one_feeding_into_p returns true if bb was empty basic block
+   or it has one cheap preparation statement that feeds into the PHI
+   statement and it sets STMT to that statement. */
+static bool
+empty_bb_or_one_feeding_into_p (basic_block bb,
+				gimple *phi,
+				gimple *&stmt)
+{
+  stmt = nullptr;
+  gimple *stmt_to_move = nullptr;
+
+  if (empty_block_p (bb))
+    return true;
+
+  if (!single_pred_p (bb))
+    return false;
+
+  /* The middle bb cannot have phi nodes as we don't
+     move those assignments yet. */
+  if (!gimple_seq_empty_p (phi_nodes (bb)))
+    return false;
+
+  stmt_to_move = last_and_only_stmt (bb);
+  if (!stmt_to_move)
+    return false;
+
+  if (gimple_vuse (stmt_to_move))
+    return false;
+
+  if (gimple_could_trap_p (stmt_to_move)
+      || gimple_has_side_effects (stmt_to_move))
+    return false;
+
+  if (gimple_uses_undefined_value_p (stmt_to_move))
+    return false;
+
+  /* Allow assignments and not no calls.
+     As const calls don't match any of the above, yet they could
+     still have some side-effects - they could contain
+     gimple_could_trap_p statements, like floating point
+     exceptions or integer division by zero.  See PR70586.
+     FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
+     should handle this.  */
+  if (!is_gimple_assign (stmt_to_move))
+    return false;
+
+  tree lhs = gimple_assign_lhs (stmt_to_move);
+  gimple *use_stmt;
+  use_operand_p use_p;
+
+  /* Allow only a statement which feeds into the other stmt.  */
+  if (!lhs || TREE_CODE (lhs) != SSA_NAME
+      || !single_imm_use (lhs, &use_p, &use_stmt)
+      || use_stmt != phi)
+    return false;
+
+  stmt = stmt_to_move;
+  return true;
+}
+
 /*  The function match_simplify_replacement does the main work of doing the
     replacement using match and simplify.  Return true if the replacement is done.
     Otherwise return false.
@@ -965,50 +1025,8 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
 
   /* If the basic block only has a cheap preparation statement,
      allow it and move it once the transformation is done. */
-  if (!empty_block_p (middle_bb))
-    {
-      if (!single_pred_p (middle_bb))
-	return false;
-
-      /* The middle bb cannot have phi nodes as we don't
-	 move those assignments yet. */
-      if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
-	return false;
-
-      stmt_to_move = last_and_only_stmt (middle_bb);
-      if (!stmt_to_move)
-	return false;
-
-      if (gimple_vuse (stmt_to_move))
-	return false;
-
-      if (gimple_could_trap_p (stmt_to_move)
-	  || gimple_has_side_effects (stmt_to_move))
-	return false;
-
-      if (gimple_uses_undefined_value_p (stmt_to_move))
-	return false;
-
-      /* Allow assignments and not no calls.
-	 As const calls don't match any of the above, yet they could
-	 still have some side-effects - they could contain
-	 gimple_could_trap_p statements, like floating point
-	 exceptions or integer division by zero.  See PR70586.
-	 FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
-	 should handle this.  */
-      if (!is_gimple_assign (stmt_to_move))
-	return false;
-
-      tree lhs = gimple_assign_lhs (stmt_to_move);
-      gimple *use_stmt;
-      use_operand_p use_p;
-
-      /* Allow only a statement which feeds into the phi.  */
-      if (!lhs || TREE_CODE (lhs) != SSA_NAME
-	  || !single_imm_use (lhs, &use_p, &use_stmt)
-	  || use_stmt != phi)
-	return false;
-    }
+  if (!empty_bb_or_one_feeding_into_p (middle_bb, phi, stmt_to_move))
+    return false;
 
     /* At this point we know we have a GIMPLE_COND with two successors.
      One successor is BB, the other successor is an empty block which
-- 
2.39.1

[PATCH 5/6] PHIOPT: Ignore predicates for match-and-simplify phi-opt

[Andrew Pinski]

This fixes a missed optimization where early phi-opt would
not work when there was predicates. The easiest fix is
to change empty_bb_or_one_feeding_into_p to ignore those
statements while checking for only feeding statement.

Note phi-opt-23.c and phi-opt-24.c still fail as we don't handle
diamond form in match_and_simplify phiopt yet.

OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

gcc/ChangeLog:

	* tree-ssa-phiopt.cc (empty_bb_or_one_feeding_into_p):
	Instead of calling last_and_only_stmt, look for the last statement
	manually.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/ssa-ifcombine-13.c: Add -fno-ssa-phiopt.
---
 .../gcc.dg/tree-ssa/ssa-ifcombine-13.c        |  4 +++-
 gcc/tree-ssa-phiopt.cc                        | 22 +++++++++++++++++--
 2 files changed, 23 insertions(+), 3 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c
index 425eb3d6481..7976544c79b 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c
@@ -1,5 +1,7 @@
 /* { dg-do compile } */
-/* { dg-options "-O1 -fdump-tree-optimized-details-blocks --param logical-op-non-short-circuit=1" } */
+/* Disable phi-opt as it is no longer confused by predicate which had allowed ifcombine to work in the past.
+   Note this testcase is about ifcombine rather than phi-opt. */
+/* { dg-options "-O1 -fdump-tree-optimized-details-blocks --param logical-op-non-short-circuit=1 -fno-ssa-phiopt" } */
 
 _Bool f1(_Bool a, _Bool b)
 {
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index cb4d8788b56..ffd6a4e6f35 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -962,9 +962,27 @@ empty_bb_or_one_feeding_into_p (basic_block bb,
   if (!gimple_seq_empty_p (phi_nodes (bb)))
     return false;
 
-  stmt_to_move = last_and_only_stmt (bb);
+  gimple_stmt_iterator gsi;
+
+  gsi = gsi_start_nondebug_after_labels_bb (bb);
+  while (!gsi_end_p (gsi))
+    {
+      gimple *s = gsi_stmt (gsi);
+      gsi_next_nondebug (&gsi);
+      /* Skip over Predict and nop statements. */
+      if (gimple_code (s) == GIMPLE_PREDICT
+	  || gimple_code (s) == GIMPLE_NOP)
+	continue;
+      /* If there is more one statement return false. */
+      if (stmt_to_move)
+	return false;
+      stmt_to_move = s;
+    }
+
+  /* The only statement here was a Predict or a nop statement
+     so return true. */
   if (!stmt_to_move)
-    return false;
+    return true;
 
   if (gimple_vuse (stmt_to_move))
     return false;
-- 
2.39.1

[PATCH 6/6] PHIOPT: Add support for diamond shaped bb to match_simplify_replacement

[Andrew Pinski]

This adds diamond shaped form of basic blocks to match_simplify_replacement.
This is the patch is the start of removing/moving all
of what minmax_replacement does to match.pd to reduce the code duplication.

OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

Note phi-opt-{23,24}.c testcase had an incorrect xfail as there should
have been 2 if still because f4/f5 would not be transformed as -ABS is
not allowable during early phi-opt.

gcc/ChangeLog:

	* tree-ssa-phiopt.cc (match_simplify_replacement): Add new arguments
	and support diamond shaped basic block form.
	(tree_ssa_phiopt_worker): Update call to match_simplify_replacement

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/phi-opt-23.c: Update testcase.
	* gcc.dg/tree-ssa/phi-opt-24.c: Likewise.
---
 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c |  4 +--
 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c |  4 +--
 gcc/tree-ssa-phiopt.cc                     | 37 ++++++++++++++++++----
 3 files changed, 35 insertions(+), 10 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c
index ff658cd16a7..86aab955d5e 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c
@@ -38,7 +38,7 @@ int f5(int A)
   return -A;
 }
 
-/* These should be optimized in phiopt1 but is confused by predicts. */
-/* { dg-final { scan-tree-dump-not "if" "phiopt1" { xfail *-*-* } } } */
+/* f4 and f5 are not allowed to be optimized in early phi-opt. */
+/* { dg-final { scan-tree-dump-times "if" 2 "phiopt1" } } */
 /* { dg-final { scan-tree-dump-not "if" "phiopt2" } } */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c
index eb89decb4bf..bd8308efa0e 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c
@@ -38,7 +38,7 @@ float f5(float A)
   return -A;
 }
 
-/* These should be optimized in phiopt1 but is confused by predicts. */
-/* { dg-final { scan-tree-dump-not "if" "phiopt1" { xfail *-*-* } } } */
+/* f4 and f5 are not allowed to be optimized in early phi-opt. */
+/* { dg-final { scan-tree-dump-times "if" 2 "phiopt1" } } */
 /* { dg-final { scan-tree-dump-not "if" "phiopt2" } } */
 
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index ffd6a4e6f35..757e44692ed 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -57,8 +57,8 @@ along with GCC; see the file COPYING3.  If not see
 
 static bool two_value_replacement (basic_block, basic_block, edge, gphi *,
 				   tree, tree);
-static bool match_simplify_replacement (basic_block, basic_block,
-					edge, edge, gphi *, tree, tree, bool);
+static bool match_simplify_replacement (basic_block, basic_block, basic_block,
+					edge, edge, gphi *, tree, tree, bool, bool);
 static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree,
 						gimple *);
 static int value_replacement (basic_block, basic_block,
@@ -304,9 +304,8 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
 	  && !diamond_p
 	  && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
 	cfgchanged = true;
-      else if (!diamond_p
-	       && match_simplify_replacement (bb, bb1, e1, e2, phi,
-					      arg0, arg1, early_p))
+      else if (match_simplify_replacement (bb, bb1, bb2, e1, e2, phi,
+					   arg0, arg1, early_p, diamond_p))
 	cfgchanged = true;
       else if (!early_p
 	       && !diamond_p
@@ -1026,8 +1025,10 @@ empty_bb_or_one_feeding_into_p (basic_block bb,
 
 static bool
 match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
+			    basic_block middle_bb_alt,
 			    edge e0, edge e1, gphi *phi,
-			    tree arg0, tree arg1, bool early_p)
+			    tree arg0, tree arg1, bool early_p,
+			    bool threeway_p)
 {
   gimple *stmt;
   gimple_stmt_iterator gsi;
@@ -1035,6 +1036,7 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
   gimple_seq seq = NULL;
   tree result;
   gimple *stmt_to_move = NULL;
+  gimple *stmt_to_move_alt = NULL;
   auto_bitmap inserted_exprs;
 
   /* Special case A ? B : B as this will always simplify to B. */
@@ -1046,6 +1048,12 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
   if (!empty_bb_or_one_feeding_into_p (middle_bb, phi, stmt_to_move))
     return false;
 
+  if (threeway_p
+      && middle_bb != middle_bb_alt
+      && !empty_bb_or_one_feeding_into_p (middle_bb_alt, phi,
+					  stmt_to_move_alt))
+    return false;
+
     /* At this point we know we have a GIMPLE_COND with two successors.
      One successor is BB, the other successor is an empty block which
      falls through into BB.
@@ -1110,6 +1118,23 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
       reset_flow_sensitive_info (name);
     }
 
+  if (stmt_to_move_alt)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "statement un-sinked:\n");
+	  print_gimple_stmt (dump_file, stmt_to_move_alt, 0,
+			   TDF_VOPS|TDF_MEMSYMS);
+	}
+
+      tree name = gimple_get_lhs (stmt_to_move_alt);
+      // Mark the name to be renamed if there is one.
+      bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
+      gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt_to_move_alt);
+      gsi_move_before (&gsi1, &gsi);
+      reset_flow_sensitive_info (name);
+    }
+
   replace_phi_edge_with_variable (cond_bb, e1, phi, result, inserted_exprs);
 
   /* Add Statistic here even though replace_phi_edge_with_variable already
-- 
2.39.1

Re: [PATCH 1/6] PHIOPT: Move check on diamond bb to tree_ssa_phiopt_worker from minmax_replacement

[Richard Biener]

On Sun, Apr 23, 2023 at 12:11 AM Andrew Pinski via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This moves the check to make sure on the diamond shaped form bbs that
> the the two middle bbs are only for that diamond shaped form earlier
> in the shared code.
> Also remove the redundant check for single_succ_p since that was already
> done before hand.
> The next patch will simplify the code even further and remove redundant
> checks.

OK.

> gcc/ChangeLog:
>
>         * tree-ssa-phiopt.cc (tree_ssa_phiopt_worker): Move the
>         diamond form check from ...
>         (minmax_replacement): Here.
> ---
>  gcc/tree-ssa-phiopt.cc | 14 ++++++++------
>  1 file changed, 8 insertions(+), 6 deletions(-)
>
> diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
> index d886c88215b..296ba646e62 100644
> --- a/gcc/tree-ssa-phiopt.cc
> +++ b/gcc/tree-ssa-phiopt.cc
> @@ -220,6 +220,14 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
>           continue;
>         }
>
> +      if (diamond_p)
> +       {
> +         if (!single_pred_p (bb1)
> +             || !single_pred_p (bb2)
> +             || !single_succ_p (bb2))
> +           continue;
> +       }
> +
>        if (do_store_elim && !diamond_p)
>         {
>           /* Also make sure that bb1 only have one predecessor and that it
> @@ -2032,12 +2040,6 @@ minmax_replacement (basic_block cond_bb, basic_block middle_bb, basic_block alt_
>        tree alt_lhs, alt_op0, alt_op1;
>        bool invert = false;
>
> -      if (!single_pred_p (middle_bb)
> -         || !single_pred_p (alt_middle_bb)
> -         || !single_succ_p (middle_bb)
> -         || !single_succ_p (alt_middle_bb))
> -       return false;
> -
>        /* When THREEWAY_P then e1 will point to the edge of the final transition
>          from middle-bb to end.  */
>        if (true_edge == e0)
> --
> 2.39.1
>

Re: [PATCH 4/6] PHIOPT: Factor out some code from match_simplify_replacement

[Richard Biener]

On Sun, Apr 23, 2023 at 12:11 AM Andrew Pinski via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This factors out the code checking if we have an empty bb
> or one statement that feeds into the phi so it can be used
> when adding diamond shaped bb form to match_simplify_replacement
> in the next patch. Also allows for some improvements
> in the next patches too.
>
> OK? Bootstrapped and tested on x86_64-linux-gnu.

OK.

> gcc/ChangeLog:
>
>         * tree-ssa-phiopt.cc (empty_bb_or_one_feeding_into_p):
>         New function.
>         (match_simplify_replacement): Call
>         empty_bb_or_one_feeding_into_p instead of doing it inline.
> ---
>  gcc/tree-ssa-phiopt.cc | 106 ++++++++++++++++++++++++-----------------
>  1 file changed, 62 insertions(+), 44 deletions(-)
>
> diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
> index e4062f33efa..cb4d8788b56 100644
> --- a/gcc/tree-ssa-phiopt.cc
> +++ b/gcc/tree-ssa-phiopt.cc
> @@ -940,6 +940,66 @@ gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
>    return NULL;
>  }
>
> +/* empty_bb_or_one_feeding_into_p returns true if bb was empty basic block
> +   or it has one cheap preparation statement that feeds into the PHI
> +   statement and it sets STMT to that statement. */
> +static bool
> +empty_bb_or_one_feeding_into_p (basic_block bb,
> +                               gimple *phi,
> +                               gimple *&stmt)
> +{
> +  stmt = nullptr;
> +  gimple *stmt_to_move = nullptr;
> +
> +  if (empty_block_p (bb))
> +    return true;
> +
> +  if (!single_pred_p (bb))
> +    return false;
> +
> +  /* The middle bb cannot have phi nodes as we don't
> +     move those assignments yet. */
> +  if (!gimple_seq_empty_p (phi_nodes (bb)))
> +    return false;
> +
> +  stmt_to_move = last_and_only_stmt (bb);
> +  if (!stmt_to_move)
> +    return false;
> +
> +  if (gimple_vuse (stmt_to_move))
> +    return false;
> +
> +  if (gimple_could_trap_p (stmt_to_move)
> +      || gimple_has_side_effects (stmt_to_move))
> +    return false;
> +
> +  if (gimple_uses_undefined_value_p (stmt_to_move))
> +    return false;
> +
> +  /* Allow assignments and not no calls.
> +     As const calls don't match any of the above, yet they could
> +     still have some side-effects - they could contain
> +     gimple_could_trap_p statements, like floating point
> +     exceptions or integer division by zero.  See PR70586.
> +     FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
> +     should handle this.  */
> +  if (!is_gimple_assign (stmt_to_move))
> +    return false;
> +
> +  tree lhs = gimple_assign_lhs (stmt_to_move);
> +  gimple *use_stmt;
> +  use_operand_p use_p;
> +
> +  /* Allow only a statement which feeds into the other stmt.  */
> +  if (!lhs || TREE_CODE (lhs) != SSA_NAME
> +      || !single_imm_use (lhs, &use_p, &use_stmt)
> +      || use_stmt != phi)
> +    return false;
> +
> +  stmt = stmt_to_move;
> +  return true;
> +}
> +
>  /*  The function match_simplify_replacement does the main work of doing the
>      replacement using match and simplify.  Return true if the replacement is done.
>      Otherwise return false.
> @@ -965,50 +1025,8 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
>
>    /* If the basic block only has a cheap preparation statement,
>       allow it and move it once the transformation is done. */
> -  if (!empty_block_p (middle_bb))
> -    {
> -      if (!single_pred_p (middle_bb))
> -       return false;
> -
> -      /* The middle bb cannot have phi nodes as we don't
> -        move those assignments yet. */
> -      if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
> -       return false;
> -
> -      stmt_to_move = last_and_only_stmt (middle_bb);
> -      if (!stmt_to_move)
> -       return false;
> -
> -      if (gimple_vuse (stmt_to_move))
> -       return false;
> -
> -      if (gimple_could_trap_p (stmt_to_move)
> -         || gimple_has_side_effects (stmt_to_move))
> -       return false;
> -
> -      if (gimple_uses_undefined_value_p (stmt_to_move))
> -       return false;
> -
> -      /* Allow assignments and not no calls.
> -        As const calls don't match any of the above, yet they could
> -        still have some side-effects - they could contain
> -        gimple_could_trap_p statements, like floating point
> -        exceptions or integer division by zero.  See PR70586.
> -        FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
> -        should handle this.  */
> -      if (!is_gimple_assign (stmt_to_move))
> -       return false;
> -
> -      tree lhs = gimple_assign_lhs (stmt_to_move);
> -      gimple *use_stmt;
> -      use_operand_p use_p;
> -
> -      /* Allow only a statement which feeds into the phi.  */
> -      if (!lhs || TREE_CODE (lhs) != SSA_NAME
> -         || !single_imm_use (lhs, &use_p, &use_stmt)
> -         || use_stmt != phi)
> -       return false;
> -    }
> +  if (!empty_bb_or_one_feeding_into_p (middle_bb, phi, stmt_to_move))
> +    return false;
>
>      /* At this point we know we have a GIMPLE_COND with two successors.
>       One successor is BB, the other successor is an empty block which
> --
> 2.39.1
>

Re: [PATCH 5/6] PHIOPT: Ignore predicates for match-and-simplify phi-opt

[Richard Biener]

On Sun, Apr 23, 2023 at 12:11 AM Andrew Pinski via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This fixes a missed optimization where early phi-opt would
> not work when there was predicates. The easiest fix is
> to change empty_bb_or_one_feeding_into_p to ignore those
> statements while checking for only feeding statement.
>
> Note phi-opt-23.c and phi-opt-24.c still fail as we don't handle
> diamond form in match_and_simplify phiopt yet.
>
> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

OK.

> gcc/ChangeLog:
>
>         * tree-ssa-phiopt.cc (empty_bb_or_one_feeding_into_p):
>         Instead of calling last_and_only_stmt, look for the last statement
>         manually.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/ssa-ifcombine-13.c: Add -fno-ssa-phiopt.
> ---
>  .../gcc.dg/tree-ssa/ssa-ifcombine-13.c        |  4 +++-
>  gcc/tree-ssa-phiopt.cc                        | 22 +++++++++++++++++--
>  2 files changed, 23 insertions(+), 3 deletions(-)
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c
> index 425eb3d6481..7976544c79b 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c
> @@ -1,5 +1,7 @@
>  /* { dg-do compile } */
> -/* { dg-options "-O1 -fdump-tree-optimized-details-blocks --param logical-op-non-short-circuit=1" } */
> +/* Disable phi-opt as it is no longer confused by predicate which had allowed ifcombine to work in the past.
> +   Note this testcase is about ifcombine rather than phi-opt. */
> +/* { dg-options "-O1 -fdump-tree-optimized-details-blocks --param logical-op-non-short-circuit=1 -fno-ssa-phiopt" } */
>
>  _Bool f1(_Bool a, _Bool b)
>  {
> diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
> index cb4d8788b56..ffd6a4e6f35 100644
> --- a/gcc/tree-ssa-phiopt.cc
> +++ b/gcc/tree-ssa-phiopt.cc
> @@ -962,9 +962,27 @@ empty_bb_or_one_feeding_into_p (basic_block bb,
>    if (!gimple_seq_empty_p (phi_nodes (bb)))
>      return false;
>
> -  stmt_to_move = last_and_only_stmt (bb);
> +  gimple_stmt_iterator gsi;
> +
> +  gsi = gsi_start_nondebug_after_labels_bb (bb);
> +  while (!gsi_end_p (gsi))
> +    {
> +      gimple *s = gsi_stmt (gsi);
> +      gsi_next_nondebug (&gsi);
> +      /* Skip over Predict and nop statements. */
> +      if (gimple_code (s) == GIMPLE_PREDICT
> +         || gimple_code (s) == GIMPLE_NOP)
> +       continue;
> +      /* If there is more one statement return false. */
> +      if (stmt_to_move)
> +       return false;
> +      stmt_to_move = s;
> +    }
> +
> +  /* The only statement here was a Predict or a nop statement
> +     so return true. */
>    if (!stmt_to_move)
> -    return false;
> +    return true;
>
>    if (gimple_vuse (stmt_to_move))
>      return false;
> --
> 2.39.1
>

Re: [PATCH 2/6] PHIOPT: Cleanup tree_ssa_phiopt_worker code

[Richard Biener]

On Sun, Apr 23, 2023 at 12:13 AM Andrew Pinski via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This patch cleans up tree_ssa_phiopt_worker by merging
> common code. Making do_store_elim handled earlier.
> Note this does not change any overall logic of the code,
> just moves code around enough to be able to do this.
> This will make it easier to move code around even more
> and a few other fixes I have.
> Plus I think all of the do_store_elim code really
> should move to its own function as how much code is shared
> is now obvious not much.

Agreed.

> OK? Bootstrapped and tested on x86_64-linux-gnu.

OK.

Thanks,
Richard.

> gcc/ChangeLog:
>
>         * tree-ssa-phiopt.cc (tree_ssa_phiopt_worker): Rearrange
>         code for better code readability.
> ---
>  gcc/tree-ssa-phiopt.cc | 212 +++++++++++++++++++++--------------------
>  1 file changed, 107 insertions(+), 105 deletions(-)
>
> diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
> index 296ba646e62..05f19825ce9 100644
> --- a/gcc/tree-ssa-phiopt.cc
> +++ b/gcc/tree-ssa-phiopt.cc
> @@ -175,10 +175,14 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
>           std::swap (bb1, bb2);
>           std::swap (e1, e2);
>         }
> -      else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
> +      else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
> +              && single_succ_p (bb2))
>         {
>           diamond_p = true;
>           e2 = EDGE_SUCC (bb2, 0);
> +         /* Make sure bb2 is just a fall through. */
> +         if ((e2->flags & EDGE_FALLTHRU) == 0)
> +           continue;
>         }
>        else
>         continue;
> @@ -190,46 +194,23 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
>           || (e1->flags & EDGE_FALLTHRU) == 0)
>         continue;
>
> -      if (do_store_elim && diamond_p)
> +      if (do_store_elim)
>         {
> -         basic_block bb3 = e1->dest;
> -
> -         if (!single_succ_p (bb2)
> -             || (e2->flags & EDGE_FALLTHRU) == 0
> -             || EDGE_COUNT (bb3->preds) != 2)
> -           continue;
> -         if (cond_if_else_store_replacement (bb1, bb2, bb3))
> -           cfgchanged = true;
> -         continue;
> -       }
> -      else if (do_hoist_loads && diamond_p)
> -       {
> -         basic_block bb3 = e1->dest;
> -
> -         if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
> -             && single_succ_p (bb2)
> -             && single_pred_p (bb1)
> -             && single_pred_p (bb2)
> -             && EDGE_COUNT (bb->succs) == 2
> -             && EDGE_COUNT (bb3->preds) == 2
> -             /* If one edge or the other is dominant, a conditional move
> -                is likely to perform worse than the well-predicted branch.  */
> -             && !predictable_edge_p (EDGE_SUCC (bb, 0))
> -             && !predictable_edge_p (EDGE_SUCC (bb, 1)))
> -           hoist_adjacent_loads (bb, bb1, bb2, bb3);
> -         continue;
> -       }
> -
> -      if (diamond_p)
> -       {
> -         if (!single_pred_p (bb1)
> -             || !single_pred_p (bb2)
> -             || !single_succ_p (bb2))
> -           continue;
> -       }
> +         if (diamond_p)
> +           {
> +             basic_block bb3 = e1->dest;
> +
> +             /* Only handle sinking of store from 2 bbs only,
> +                The middle bbs don't need to come from the
> +                if always since we are sinking rather than
> +                hoisting. */
> +             if (EDGE_COUNT (bb3->preds) != 2)
> +               continue;
> +             if (cond_if_else_store_replacement (bb1, bb2, bb3))
> +               cfgchanged = true;
> +             continue;
> +           }
>
> -      if (do_store_elim && !diamond_p)
> -       {
>           /* Also make sure that bb1 only have one predecessor and that it
>              is bb.  */
>           if (!single_pred_p (bb1)
> @@ -243,85 +224,106 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
>             continue;
>           if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
>             cfgchanged = true;
> +         continue;
>         }
> -      else
> +
> +      if (diamond_p)
>         {
> -         gimple_stmt_iterator gsi;
> -         bool candorest = true;
> +         basic_block bb3 = e1->dest;
> +
> +         if (!single_pred_p (bb1)
> +             || !single_pred_p (bb2))
> +           continue;
>
> -         /* Check that we're looking for nested phis.  */
> -         basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
> -         gimple_seq phis = phi_nodes (merge);
> +         if (do_hoist_loads
> +             && !FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
> +             && EDGE_COUNT (bb->succs) == 2
> +             && EDGE_COUNT (bb3->preds) == 2
> +             /* If one edge or the other is dominant, a conditional move
> +                is likely to perform worse than the well-predicted branch.  */
> +             && !predictable_edge_p (EDGE_SUCC (bb, 0))
> +             && !predictable_edge_p (EDGE_SUCC (bb, 1)))
> +           {
> +             hoist_adjacent_loads (bb, bb1, bb2, bb3);
> +             continue;
> +           }
> +       }
>
> -         /* Value replacement can work with more than one PHI
> -            so try that first. */
> -         if (!early_p && !diamond_p)
> -           for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
> +      gimple_stmt_iterator gsi;
> +      bool candorest = true;
> +
> +      /* Check that we're looking for nested phis.  */
> +      basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
> +      gimple_seq phis = phi_nodes (merge);
> +
> +      /* Value replacement can work with more than one PHI
> +        so try that first. */
> +      if (!early_p && !diamond_p)
> +       for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
> +         {
> +           phi = as_a <gphi *> (gsi_stmt (gsi));
> +           arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
> +           arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
> +           if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
>               {
> -               phi = as_a <gphi *> (gsi_stmt (gsi));
> -               arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
> -               arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
> -               if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
> -                 {
> -                   candorest = false;
> -                   cfgchanged = true;
> -                   break;
> -                 }
> +               candorest = false;
> +               cfgchanged = true;
> +               break;
>               }
> +         }
>
> -         if (!candorest)
> -           continue;
> +      if (!candorest)
> +       continue;
>
> -         phi = single_non_singleton_phi_for_edges (phis, e1, e2);
> -         if (!phi)
> -           continue;
> +      phi = single_non_singleton_phi_for_edges (phis, e1, e2);
> +      if (!phi)
> +       continue;
> +
> +      arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
> +      arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
>
> +      /* Something is wrong if we cannot find the arguments in the PHI
> +         node.  */
> +      gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
> +
> +      gphi *newphi;
> +      if (single_pred_p (bb1)
> +         && !diamond_p
> +         && (newphi = factor_out_conditional_conversion (e1, e2, phi,
> +                                                         arg0, arg1,
> +                                                         cond_stmt)))
> +       {
> +         phi = newphi;
> +         /* factor_out_conditional_conversion may create a new PHI in
> +            BB2 and eliminate an existing PHI in BB2.  Recompute values
> +            that may be affected by that change.  */
>           arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
>           arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
> -
> -         /* Something is wrong if we cannot find the arguments in the PHI
> -            node.  */
>           gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
> -
> -         gphi *newphi;
> -         if (single_pred_p (bb1)
> -             && !diamond_p
> -             && (newphi = factor_out_conditional_conversion (e1, e2, phi,
> -                                                             arg0, arg1,
> -                                                             cond_stmt)))
> -           {
> -             phi = newphi;
> -             /* factor_out_conditional_conversion may create a new PHI in
> -                BB2 and eliminate an existing PHI in BB2.  Recompute values
> -                that may be affected by that change.  */
> -             arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
> -             arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
> -             gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
> -           }
> -
> -         /* Do the replacement of conditional if it can be done.  */
> -         if (!early_p
> -             && !diamond_p
> -             && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
> -           cfgchanged = true;
> -         else if (!diamond_p
> -                  && match_simplify_replacement (bb, bb1, e1, e2, phi,
> -                                                 arg0, arg1, early_p))
> -           cfgchanged = true;
> -         else if (!early_p
> -                  && !diamond_p
> -                  && single_pred_p (bb1)
> -                  && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
> -                                                           phi, arg0, arg1))
> -           cfgchanged = true;
> -         else if (minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1,
> -                                      diamond_p))
> -           cfgchanged = true;
> -         else if (single_pred_p (bb1)
> -                  && !diamond_p
> -                  && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
> -           cfgchanged = true;
>         }
> +
> +      /* Do the replacement of conditional if it can be done.  */
> +      if (!early_p
> +         && !diamond_p
> +         && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
> +       cfgchanged = true;
> +      else if (!diamond_p
> +              && match_simplify_replacement (bb, bb1, e1, e2, phi,
> +                                             arg0, arg1, early_p))
> +       cfgchanged = true;
> +      else if (!early_p
> +              && !diamond_p
> +              && single_pred_p (bb1)
> +              && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
> +                                                       phi, arg0, arg1))
> +       cfgchanged = true;
> +      else if (minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1,
> +                                  diamond_p))
> +       cfgchanged = true;
> +      else if (single_pred_p (bb1)
> +              && !diamond_p
> +              && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
> +       cfgchanged = true;
>      }
>
>    free (bb_order);
> --
> 2.39.1
>

Re: [PATCH 3/6] PHIOPT: Allow other diamond uses when do_hoist_loads is true

[Richard Biener]

On Sun, Apr 23, 2023 at 12:13 AM Andrew Pinski via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> While working on adding diamond shaped form to match-and-simplify
> phiopt, I Noticed that we would not reach there if do_hoist_loads
> was true. In the original code before the cleanups it was not
> obvious why but after I finished the cleanups, it was just a matter
> of removing a continue and that is what this patch does.
>
> This just happens also to fix a bug report that I noticed too.
>
> OK? Bootstrapped and tested on x86_64-linux-gnu.

OK.

> gcc/ChangeLog:
>
>         PR tree-optimize/68894
>         * tree-ssa-phiopt.cc (tree_ssa_phiopt_worker): Remove the
>         continue for the do_hoist_loads diamond case.
> ---
>  gcc/tree-ssa-phiopt.cc | 5 +----
>  1 file changed, 1 insertion(+), 4 deletions(-)
>
> diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
> index 05f19825ce9..e4062f33efa 100644
> --- a/gcc/tree-ssa-phiopt.cc
> +++ b/gcc/tree-ssa-phiopt.cc
> @@ -243,10 +243,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
>                  is likely to perform worse than the well-predicted branch.  */
>               && !predictable_edge_p (EDGE_SUCC (bb, 0))
>               && !predictable_edge_p (EDGE_SUCC (bb, 1)))
> -           {
> -             hoist_adjacent_loads (bb, bb1, bb2, bb3);
> -             continue;
> -           }
> +           hoist_adjacent_loads (bb, bb1, bb2, bb3);
>         }
>
>        gimple_stmt_iterator gsi;
> --
> 2.39.1
>

Re: [PATCH 6/6] PHIOPT: Add support for diamond shaped bb to match_simplify_replacement

[Richard Biener]

On Sun, Apr 23, 2023 at 12:13 AM Andrew Pinski via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This adds diamond shaped form of basic blocks to match_simplify_replacement.
> This is the patch is the start of removing/moving all
> of what minmax_replacement does to match.pd to reduce the code duplication.
>
> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

OK.

thanks,
Richard.

> Note phi-opt-{23,24}.c testcase had an incorrect xfail as there should
> have been 2 if still because f4/f5 would not be transformed as -ABS is
> not allowable during early phi-opt.
>
> gcc/ChangeLog:
>
>         * tree-ssa-phiopt.cc (match_simplify_replacement): Add new arguments
>         and support diamond shaped basic block form.
>         (tree_ssa_phiopt_worker): Update call to match_simplify_replacement
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/phi-opt-23.c: Update testcase.
>         * gcc.dg/tree-ssa/phi-opt-24.c: Likewise.
> ---
>  gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c |  4 +--
>  gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c |  4 +--
>  gcc/tree-ssa-phiopt.cc                     | 37 ++++++++++++++++++----
>  3 files changed, 35 insertions(+), 10 deletions(-)
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c
> index ff658cd16a7..86aab955d5e 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-23.c
> @@ -38,7 +38,7 @@ int f5(int A)
>    return -A;
>  }
>
> -/* These should be optimized in phiopt1 but is confused by predicts. */
> -/* { dg-final { scan-tree-dump-not "if" "phiopt1" { xfail *-*-* } } } */
> +/* f4 and f5 are not allowed to be optimized in early phi-opt. */
> +/* { dg-final { scan-tree-dump-times "if" 2 "phiopt1" } } */
>  /* { dg-final { scan-tree-dump-not "if" "phiopt2" } } */
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c
> index eb89decb4bf..bd8308efa0e 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-24.c
> @@ -38,7 +38,7 @@ float f5(float A)
>    return -A;
>  }
>
> -/* These should be optimized in phiopt1 but is confused by predicts. */
> -/* { dg-final { scan-tree-dump-not "if" "phiopt1" { xfail *-*-* } } } */
> +/* f4 and f5 are not allowed to be optimized in early phi-opt. */
> +/* { dg-final { scan-tree-dump-times "if" 2 "phiopt1" } } */
>  /* { dg-final { scan-tree-dump-not "if" "phiopt2" } } */
>
> diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
> index ffd6a4e6f35..757e44692ed 100644
> --- a/gcc/tree-ssa-phiopt.cc
> +++ b/gcc/tree-ssa-phiopt.cc
> @@ -57,8 +57,8 @@ along with GCC; see the file COPYING3.  If not see
>
>  static bool two_value_replacement (basic_block, basic_block, edge, gphi *,
>                                    tree, tree);
> -static bool match_simplify_replacement (basic_block, basic_block,
> -                                       edge, edge, gphi *, tree, tree, bool);
> +static bool match_simplify_replacement (basic_block, basic_block, basic_block,
> +                                       edge, edge, gphi *, tree, tree, bool, bool);
>  static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree,
>                                                 gimple *);
>  static int value_replacement (basic_block, basic_block,
> @@ -304,9 +304,8 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
>           && !diamond_p
>           && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
>         cfgchanged = true;
> -      else if (!diamond_p
> -              && match_simplify_replacement (bb, bb1, e1, e2, phi,
> -                                             arg0, arg1, early_p))
> +      else if (match_simplify_replacement (bb, bb1, bb2, e1, e2, phi,
> +                                          arg0, arg1, early_p, diamond_p))
>         cfgchanged = true;
>        else if (!early_p
>                && !diamond_p
> @@ -1026,8 +1025,10 @@ empty_bb_or_one_feeding_into_p (basic_block bb,
>
>  static bool
>  match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
> +                           basic_block middle_bb_alt,
>                             edge e0, edge e1, gphi *phi,
> -                           tree arg0, tree arg1, bool early_p)
> +                           tree arg0, tree arg1, bool early_p,
> +                           bool threeway_p)
>  {
>    gimple *stmt;
>    gimple_stmt_iterator gsi;
> @@ -1035,6 +1036,7 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
>    gimple_seq seq = NULL;
>    tree result;
>    gimple *stmt_to_move = NULL;
> +  gimple *stmt_to_move_alt = NULL;
>    auto_bitmap inserted_exprs;
>
>    /* Special case A ? B : B as this will always simplify to B. */
> @@ -1046,6 +1048,12 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
>    if (!empty_bb_or_one_feeding_into_p (middle_bb, phi, stmt_to_move))
>      return false;
>
> +  if (threeway_p
> +      && middle_bb != middle_bb_alt
> +      && !empty_bb_or_one_feeding_into_p (middle_bb_alt, phi,
> +                                         stmt_to_move_alt))
> +    return false;
> +
>      /* At this point we know we have a GIMPLE_COND with two successors.
>       One successor is BB, the other successor is an empty block which
>       falls through into BB.
> @@ -1110,6 +1118,23 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
>        reset_flow_sensitive_info (name);
>      }
>
> +  if (stmt_to_move_alt)
> +    {
> +      if (dump_file && (dump_flags & TDF_DETAILS))
> +       {
> +         fprintf (dump_file, "statement un-sinked:\n");
> +         print_gimple_stmt (dump_file, stmt_to_move_alt, 0,
> +                          TDF_VOPS|TDF_MEMSYMS);
> +       }
> +
> +      tree name = gimple_get_lhs (stmt_to_move_alt);
> +      // Mark the name to be renamed if there is one.
> +      bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
> +      gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt_to_move_alt);
> +      gsi_move_before (&gsi1, &gsi);
> +      reset_flow_sensitive_info (name);
> +    }
> +
>    replace_phi_edge_with_variable (cond_bb, e1, phi, result, inserted_exprs);
>
>    /* Add Statistic here even though replace_phi_edge_with_variable already
> --
> 2.39.1
>