From: Kyrylo Tkachov <[email protected]>
When a chain of if-convertible diamonds shares a controlling condition,
the backward jump threader tail-duplicates it into a 2^N decision tree
and the per-lane selects can no longer be if-converted.
Add pass_merge_diamonds, run before pass_thread_jumps_full and gated on
flag_thread_jumps. For each if-convertible diamond it walks the
immediate dominators for an earlier diamond with an identical
GIMPLE_COND and, when all non-virtual join PHIs of the later diamond
have their arguments available at the earlier join, moves the PHIs up
into it, keeping their result SSA names, and removes the now redundant
branch. The threader then finds no correlated conditions to duplicate
and RTL if-conversion lowers the selects to conditional moves; whether
each select becomes a move remains a cost-model decision.
The scan collects candidate blocks by index up front and processes them
in one sweep, looking each up again by index since a merge deletes
blocks. A chain of same-condition diamonds merges bottom-up within a
single sweep (remove_edge_and_dominated_blocks keeps the dominator
information valid throughout); a rescan happens only when a merge
changed the topology in a way that could enable a merge that failed
earlier, so the common case is one sweep plus one empty verification
sweep.
Improves 731.astcenc_r (SPEC CPU2026) by 20% on aarch64 at -Ofast
-flto; the hot select kernel goes from 36 conditional branches and 12
conditional moves to 8 and 24. Placing the pass after the first VRP
instance instead gives identical results, so the minimal placement is
kept.
Bootstrapped and regression tested on aarch64-unknown-linux-gnu.
gcc/ChangeLog:
PR tree-optimization/125672
* passes.def: Add pass_merge_diamonds before
pass_thread_jumps_full.
* tree-pass.h (make_pass_merge_diamonds): Declare.
* tree-ssa-ifcombine.cc (ifcvt_diamond_join, value_available_at)
(abnormal_ssa_p, merge_cond_diamond_up): New functions.
(class pass_merge_diamonds): New pass.
(make_pass_merge_diamonds): New function.
gcc/testsuite/ChangeLog:
PR tree-optimization/125672
* gcc.dg/tree-ssa/pr125672-2.c: New test.
* gcc.dg/tree-ssa/pr125672-3.c: New test.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/passes.def | 1 +
gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c | 17 ++
gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c | 32 +++
gcc/tree-pass.h | 1 +
gcc/tree-ssa-ifcombine.cc | 284 +++++++++++++++++++++
5 files changed, 335 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c
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);
+}
--
2.50.1 (Apple Git-155)
