[2/2] tree-optimization/125672 - merge same-condition if-convertible diamonds

diff --git a/gcc/passes.def b/gcc/passes.def
index 1fc867fae51..3c4f0629e78 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -233,6 +233,7 @@  along with GCC; see the file COPYING3.  If not see
       NEXT_PASS (pass_return_slot);
       NEXT_PASS (pass_fre, true /* may_iterate */);
       NEXT_PASS (pass_merge_phi);
+      NEXT_PASS (pass_merge_diamonds);
       NEXT_PASS (pass_thread_jumps_full, /*first=*/true);
       NEXT_PASS (pass_vrp, false /* final_p*/);
       NEXT_PASS (pass_array_bounds);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c
new file mode 100644
index 00000000000..e66eeb0eac1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c
@@ -0,0 +1,17 @@ 
+/* Same-condition if-convertible diamonds separated by intervening diamonds are
+   merged before jump threading so the threader cannot tail-duplicate them.  */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-mergediam-details" } */
+
+void f (float *o, float a1, float a2, float b0, float b1,
+	float c0, float c1, float d0, float d1)
+{
+  float t0, t1, t2, t3;
+  if (a1 > 0) t0 = b0; else t0 = c0;
+  if (a2 > 0) t1 = b1; else t1 = c1;
+  if (a1 > 0) t2 = d0; else t2 = d1;
+  if (a2 > 0) t3 = b0; else t3 = c1;
+  o[0] = t0; o[1] = t1; o[2] = t2; o[3] = t3;
+}
+
+/* { dg-final { scan-tree-dump-times "merging if-convertible diamond" 2 "mergediam" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c
new file mode 100644
index 00000000000..24a4f7ce674
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c
@@ -0,0 +1,32 @@ 
+/* Execution test: merging same-condition if-convertible diamonds must
+   preserve semantics.  */
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+__attribute__((noipa)) static void
+kern (int n, const int *a, const int *b, int *o)
+{
+  for (int i = 0; i < n; i++)
+    {
+      int m0 = (a[i] > b[i]) ? -1 : 0;        /* a comparison mask */
+      int m1 = (a[i] < b[i]) ? -1 : 0;        /* a second mask */
+      o[4*i + 0] = (m0 == -1) ? a[i] : b[i];  /* select under mask 0 */
+      o[4*i + 1] = (m1 == -1) ? a[i] : b[i];  /* select under mask 1 */
+      o[4*i + 2] = (m0 == -1) ? b[i] : a[i];  /* mask 0 again */
+      o[4*i + 3] = (m1 == -1) ? b[i] : a[i];  /* mask 1 again */
+    }
+}
+
+int
+main (void)
+{
+  int a[3] = { 5, 2, 9 };
+  int b[3] = { 3, 7, 9 };
+  int o[12];
+  int exp[12] = { 5, 3, 3, 5,   7, 2, 2, 7,   9, 9, 9, 9 };
+  kern (3, a, b, o);
+  for (int i = 0; i < 12; i++)
+    if (o[i] != exp[i])
+      __builtin_abort ();
+  return 0;
+}
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index b3c97658a8f..1625c1766e0 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -464,6 +464,7 @@  extern gimple_opt_pass *make_pass_phiopt (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_forwprop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_phiprop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_tree_ifcombine (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_merge_diamonds (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);
diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc
index 0c3e78ef331..fc66ccac81e 100644
--- a/gcc/tree-ssa-ifcombine.cc
+++ b/gcc/tree-ssa-ifcombine.cc
@@ -1450,3 +1450,287 @@  make_pass_tree_ifcombine (gcc::context *ctxt)
 {
   return new pass_tree_ifcombine (ctxt);
 }
+
+/* Merge if-convertible diamonds that share a controlling condition.  The
+   backward jump threader tail-duplicates such a chain into a 2^N decision
+   tree, so the per-lane selects come out as branches instead of conditional
+   moves.  This pass merges a later diamond into an earlier same-condition
+   one before threading runs:
+
+	  if (c)                            if (c)
+	 /      \                          /      \
+	.        .  (empty arms)          .        .
+	 \      /                          \      /
+      x = PHI <a, b>                    x = PHI <a, b>
+	   |                            y = PHI <p, q>
+	  ...               ==>              |
+	   |                                ...
+	  if (c)                             |
+	 /      \                           ...
+	.        .
+	 \      /
+      y = PHI <p, q>
+	   |
+	  ...
+
+   Both p and q are defined above the first join, so the later join's PHI
+   can be evaluated there, keyed by the shared condition (p on the true
+   side, q on the false side); the second branch then decides nothing and
+   is removed.  The threader sees one diamond per condition and finds
+   nothing to tail-duplicate.  This relies on early phiopt having
+   de-indirected constant-pair masks (cmp ? -1 : 0 -> -(int)cmp) so the
+   repeated mask tests share an identical GIMPLE_COND.  Gated on
+   flag_thread_jumps.  */
+
+/* If COND_BB heads an if-then-else with empty (side-effect-free) arms that
+   reconverge at a single join, return the join and set *E_TRUE / *E_FALSE to
+   the edges entering it on the true / false side (possibly via one empty
+   forwarder).  Otherwise NULL.  */
+
+static basic_block
+ifcvt_diamond_join (basic_block cond_bb, edge *e_true, edge *e_false)
+{
+  basic_block tb = NULL, fb = NULL;
+  if (!recognize_if_then_else (cond_bb, &tb, &fb))
+    return NULL;
+  edge te = find_edge (cond_bb, tb);
+  edge fe = find_edge (cond_bb, fb);
+
+  edge tj_e = te, fj_e = fe;
+  basic_block tj = tb, fj = fb;
+  if (single_pred_p (tb) && single_succ_p (tb) && empty_block_p (tb))
+    {
+      tj = single_succ (tb);
+      tj_e = single_succ_edge (tb);
+    }
+  if (single_pred_p (fb) && single_succ_p (fb) && empty_block_p (fb))
+    {
+      fj = single_succ (fb);
+      fj_e = single_succ_edge (fb);
+    }
+
+  basic_block join;
+  if (tb == fj && tb != cond_bb)
+    {
+      join = tb;
+      *e_true = te;
+      *e_false = fj_e;
+    }
+  else if (fb == tj && fb != cond_bb)
+    {
+      join = fb;
+      *e_true = tj_e;
+      *e_false = fe;
+    }
+  else if (tj == fj && tj != cond_bb && tb != fb)
+    {
+      join = tj;
+      *e_true = tj_e;
+      *e_false = fj_e;
+    }
+  else
+    return NULL;
+
+  if (EDGE_COUNT (join->preds) != 2
+      || (*e_true)->src == (*e_false)->src)
+    return NULL;
+  if (tb != join && !bb_no_side_effects_p (tb))
+    return NULL;
+  if (fb != join && !bb_no_side_effects_p (fb))
+    return NULL;
+  return join;
+}
+
+/* True if VAL (a constant, default def, or SSA name whose definition dominates
+   BB) is available at BB.  */
+
+static bool
+value_available_at (tree val, basic_block bb)
+{
+  if (TREE_CODE (val) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (val))
+    return true;
+  basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
+  return def_bb && dominated_by_p (CDI_DOMINATORS, bb, def_bb);
+}
+
+/* True if T is an SSA name that occurs in an abnormal PHI (must not be moved
+   or have its definition relocated).  */
+
+static inline bool
+abnormal_ssa_p (tree t)
+{
+  return TREE_CODE (t) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (t);
+}
+
+/* Try to merge the same-condition if-convertible diamond headed by B2 into an
+   earlier dominating one by moving B2's join PHIs up.  Return true if done.  */
+
+static bool
+merge_cond_diamond_up (basic_block b2)
+{
+  edge t2, f2;
+  basic_block join2 = ifcvt_diamond_join (b2, &t2, &f2);
+  if (!join2)
+    return false;
+  gcond *c2 = safe_dyn_cast <gcond *> (*gsi_last_bb (b2));
+  if (!c2)
+    return false;
+  tree cl = gimple_cond_lhs (c2), cr = gimple_cond_rhs (c2);
+  if (abnormal_ssa_p (cl) || abnormal_ssa_p (cr))
+    return false;
+
+  for (basic_block b1 = get_immediate_dominator (CDI_DOMINATORS, b2);
+       b1; b1 = get_immediate_dominator (CDI_DOMINATORS, b1))
+    {
+      gcond *c1 = safe_dyn_cast <gcond *> (*gsi_last_bb (b1));
+      if (!c1
+	  || gimple_cond_code (c1) != gimple_cond_code (c2)
+	  || !operand_equal_p (gimple_cond_lhs (c1), cl, 0)
+	  || !operand_equal_p (gimple_cond_rhs (c1), cr, 0))
+	continue;
+
+      edge t1, f1;
+      basic_block join1 = ifcvt_diamond_join (b1, &t1, &f1);
+      if (!join1 || join1 == join2 || join1 == b2 || join1 == b1)
+	continue;
+
+      /* Each non-virtual JOIN2 PHI must have both args available at B1 and be
+	 free of abnormal coalescing, so it can be moved up to JOIN1.  */
+      bool ok = true, any = false;
+      for (gphi_iterator gpi = gsi_start_phis (join2);
+	   !gsi_end_p (gpi); gsi_next (&gpi))
+	{
+	  gphi *phi = gpi.phi ();
+	  tree res = gimple_phi_result (phi);
+	  if (virtual_operand_p (res))
+	    continue;
+	  any = true;
+	  tree tv = PHI_ARG_DEF_FROM_EDGE (phi, t2);
+	  tree fv = PHI_ARG_DEF_FROM_EDGE (phi, f2);
+	  if (abnormal_ssa_p (res) || abnormal_ssa_p (tv) || abnormal_ssa_p (fv)
+	      || !value_available_at (tv, b1) || !value_available_at (fv, b1))
+	    {
+	      ok = false;
+	      break;
+	    }
+	}
+      if (!ok || !any)
+	continue;
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "merging if-convertible diamond bb%d up into same-condition "
+		 "diamond bb%d\n", b2->index, b1->index);
+
+      /* Move each non-virtual JOIN2 PHI to JOIN1, keeping its result SSA name.
+	 JOIN1 dominates all of the result's uses, so no use or debug bind
+	 changes.  The virtual PHI is left to degenerate after cfg cleanup.  */
+      for (gphi_iterator gpi = gsi_start_phis (join2); !gsi_end_p (gpi);)
+	{
+	  gphi *phi = gpi.phi ();
+	  tree res = gimple_phi_result (phi);
+	  if (virtual_operand_p (res))
+	    {
+	      gsi_next (&gpi);
+	      continue;
+	    }
+	  tree tv = PHI_ARG_DEF_FROM_EDGE (phi, t2);
+	  tree fv = PHI_ARG_DEF_FROM_EDGE (phi, f2);
+	  location_t tl = gimple_phi_arg_location_from_edge (phi, t2);
+	  location_t fl = gimple_phi_arg_location_from_edge (phi, f2);
+	  remove_phi_node (&gpi, false);
+	  gphi *nphi = create_phi_node (res, join1);
+	  add_phi_arg (nphi, tv, t1, tl);
+	  add_phi_arg (nphi, fv, f1, fl);
+	}
+
+      /* B2's branch is now redundant; keep its true edge as a fallthrough and
+	 drop the false edge with any unreachable blocks.  */
+      edge b2t, b2f;
+      extract_true_false_edges_from_block (b2, &b2t, &b2f);
+      gimple_stmt_iterator gsic2 = gsi_last_bb (b2);
+      gsi_remove (&gsic2, true);
+      remove_edge_and_dominated_blocks (b2f);
+      b2t->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+      b2t->flags |= EDGE_FALLTHRU;
+      b2t->probability = profile_probability::always ();
+      loops_state_set (LOOPS_NEED_FIXUP);
+      return true;
+    }
+  return false;
+}
+
+namespace {
+
+const pass_data pass_data_merge_diamonds =
+{
+  GIMPLE_PASS, /* type */
+  "mergediam", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_TREE_IFCOMBINE, /* tv_id */
+  PROP_cfg | PROP_ssa, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_merge_diamonds : public gimple_opt_pass
+{
+public:
+  pass_merge_diamonds (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_merge_diamonds, ctxt)
+  {}
+
+  bool gate (function *) final override
+  {
+    return optimize > 0 && flag_thread_jumps && !optimize_debug;
+  }
+
+  unsigned int execute (function *fun) final override
+  {
+    calculate_dominance_info (CDI_DOMINATORS);
+    bool changed = false;
+    /* Collect candidates first and look them up again by index: a merge
+       deletes basic blocks (the redundant branch, and blocks that become
+       unreachable), so the block list must not be iterated while
+       mutating.  remove_edge_and_dominated_blocks keeps the dominator
+       information valid throughout, so all merges can be done in one
+       sweep; in particular a chain of same-condition diamonds merges
+       bottom-up in a single pass, each merge carrying its join PHIs to
+       the next.  A merge can also change a join's predecessor count and
+       thereby enable a merge that failed earlier in the sweep, so rescan
+       until a sweep performs no merge; almost always the second sweep
+       finds nothing.  */
+    auto_vec<int> candidates;
+    bool again = true;
+    while (again)
+      {
+	again = false;
+	candidates.truncate (0);
+	basic_block bb;
+	FOR_EACH_BB_FN (bb, fun)
+	  if (safe_is_a <gcond *> (*gsi_last_bb (bb)))
+	    candidates.safe_push (bb->index);
+	unsigned i;
+	int idx;
+	FOR_EACH_VEC_ELT (candidates, i, idx)
+	  {
+	    basic_block b2 = BASIC_BLOCK_FOR_FN (fun, idx);
+	    if (!b2 || !safe_is_a <gcond *> (*gsi_last_bb (b2)))
+	      continue;
+	    if (merge_cond_diamond_up (b2))
+	      changed = again = true;
+	  }
+      }
+    return changed ? TODO_cleanup_cfg : 0;
+  }
+}; // class pass_merge_diamonds
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_merge_diamonds (gcc::context *ctxt)
+{
+  return new pass_merge_diamonds (ctxt);
+}