From: Kyrylo Tkachov <[email protected]>
A chain of if-convertible diamonds controlled by repeated conditions can
be tail-duplicated by the backward jump threader. The resulting
decision tree prevents later if-conversion from retaining the values as
compact conditional selects.
Add pass_merge_diamonds immediately before pass_thread_jumps_full. The
existing tree ifcombine instance runs after this threader, which is too
late to preserve the original diamonds.
For a later if-convertible diamond, search its immediate dominators for
the nearest same condition with a matching recorded loop father. When
that occurrence is also an if-convertible diamond and each nonvirtual
PHI argument is available there, move the later join PHIs to the earlier
join while preserving their result SSA names. The later branch then has
no effect and can be removed.
Reject abnormal condition and diamond edges. Also reject condition
operands, PHI results and PHI arguments that participate in abnormal
PHIs. Keep potentially trapping conditions so the later evaluation is
not removed. Stop at the nearest repeated condition or when the
recorded loop father changes, so definitions are not relocated across
unrelated control-flow regions.
Collect candidates in dominator preorder before changing the CFG.
Moving a PHI definition can only enable a dominated candidate, which is
visited later. Because its recognized arms contain no executable
statements, a diamond without nonvirtual PHIs is itself redundant and
can be folded when first visited. Adding PHIs therefore cannot make an
earlier candidate newly eligible. One dominator-preorder sweep reaches
a fixed point without retries or whole-CFG rescans.
Gate the pass on flag_thread_jumps and flag_expensive_optimizations,
matching the following backward threader.
Add structural coverage for interleaved repeated conditions and for a
merge that makes a later condition pair eligible in the same preorder
sweep. Add an execution test with debug information that verifies both
expected merges. Add a negative test for a potentially trapping
floating-point condition and make the positive floating-point case
explicitly nontrapping.
Together with the preceding phiopt patch, this makes 731.astcenc_r about
20% faster on AArch64 at -Ofast -flto=auto. Its hot quantization
function has about 45% fewer static instructions and about 78% fewer
conditional branches, with twice as many conditional selects.
Bootstrapped and tested on aarch64-none-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): New function.
(value_available_at): New function.
(abnormal_ssa_p): New function.
(merge_cond_diamond_up): New function.
(pass_data_merge_diamonds): New variable.
(pass_merge_diamonds): New class.
(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.
* gcc.dg/tree-ssa/pr125672-5.c: New test.
* gcc.dg/tree-ssa/pr125672-6.c: New test.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/passes.def | 1 +
gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c | 33 +++
gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c | 36 +++
gcc/testsuite/gcc.dg/tree-ssa/pr125672-5.c | 36 +++
gcc/testsuite/gcc.dg/tree-ssa/pr125672-6.c | 18 ++
gcc/tree-pass.h | 1 +
gcc/tree-ssa-ifcombine.cc | 273 +++++++++++++++++++++
7 files changed, 398 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
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr125672-5.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr125672-6.c
diff --git a/gcc/passes.def b/gcc/passes.def
index 9095c134f49..6e7bf23c49b 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..28b4d852aa0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c
@@ -0,0 +1,33 @@
+/* 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 -fno-trapping-math -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..9f712b873ba
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c
@@ -0,0 +1,36 @@
+/* Execution test: merging same-condition if-convertible diamonds must
+ preserve semantics. */
+/* { dg-do run } */
+/* { dg-options "-O2 -g -fdump-tree-mergediam-details" } */
+
+__attribute__ ((noipa)) static void
+kern (int n, const int *a, const int *b, int *o)
+{
+ for (int i = 0; i < n; ++i)
+ {
+ int ai = a[i];
+ int bi = b[i];
+ int m0 = ai > bi ? -1 : 0;
+ int m1 = ai < bi ? -1 : 0;
+ o[4 * i] = m0 == -1 ? ai : bi;
+ o[4 * i + 1] = m1 == -1 ? ai : bi;
+ o[4 * i + 2] = m0 == -1 ? bi : ai;
+ o[4 * i + 3] = m1 == -1 ? bi : ai;
+ }
+}
+
+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;
+}
+
+/* { dg-final { scan-tree-dump-times "merging if-convertible diamond" 2
"mergediam" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr125672-5.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-5.c
new file mode 100644
index 00000000000..e51f9bca630
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-5.c
@@ -0,0 +1,36 @@
+/* A merge that moves R before the first D condition makes the later D
+ diamond eligible in the same dominator-preorder sweep. */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-mergediam-details" } */
+
+int
+f (int c, int d, int a, int b, int x, int y, int p, int q, int u)
+{
+ int c0, d0, r, s;
+ if (c > 0)
+ c0 = a;
+ else
+ c0 = b;
+ if (d > 0)
+ d0 = x;
+ else
+ d0 = y;
+ goto C1;
+
+D1:
+ if (d > 0)
+ s = r;
+ else
+ s = u;
+ return c0 + d0 + s;
+
+C1:
+ if (c > 0)
+ r = p;
+ else
+ r = q;
+ goto D1;
+}
+
+/* Both pairs of same-condition diamonds are merged. */
+/* { dg-final { scan-tree-dump-times "merging if-convertible diamond" 2
"mergediam" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr125672-6.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-6.c
new file mode 100644
index 00000000000..c645c92b401
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-6.c
@@ -0,0 +1,18 @@
+/* A potentially trapping comparison must not be removed across a call that
+ can change the floating-point environment. */
+/* { dg-do compile } */
+/* { dg-options "-O2 -frounding-math -ftrapping-math
-fdump-tree-mergediam-details" } */
+
+extern void clear_exceptions (void);
+
+int
+f (float x, float y)
+{
+ int a = x < y ? 1 : 2;
+ clear_exceptions ();
+ int b = x < y ? 3 : 4;
+ return a + b;
+}
+
+/* { dg-final { scan-tree-dump-not "merging if-convertible diamond"
"mergediam" } } */
+
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index a3b35e009e0..fdbd6dbf53d 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -463,6 +463,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..072458de862 100644
--- a/gcc/tree-ssa-ifcombine.cc
+++ b/gcc/tree-ssa-ifcombine.cc
@@ -1450,3 +1450,276 @@ make_pass_tree_ifcombine (gcc::context *ctxt)
{
return new pass_tree_ifcombine (ctxt);
}
+
+/* Merge a later if-convertible diamond into an earlier one controlled by the
+ same condition before backward jump 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 arguments of each nonvirtual PHI at the later join must be available
+ before the first condition, so the PHI can be evaluated at the first join.
+ The second branch then has no effect and is removed. A join without
+ nonvirtual PHIs is handled in the same way. */
+
+/* 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);
+ if ((te->flags | fe->flags) & EDGE_ABNORMAL)
+ return NULL;
+
+ 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 (((*e_true)->flags | (*e_false)->flags) & EDGE_ABNORMAL)
+ return NULL;
+ if (EDGE_COUNT (join->preds) != 2
+ || (*e_true)->src == (*e_false)->src)
+ 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
+ successful. */
+
+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));
+ /* Removing B2's branch also removes its condition evaluation. */
+ if (!c2 || gimple_could_trap_p (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))
+ {
+ if (b1->loop_father != b2->loop_father)
+ break;
+ 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)
+ return false;
+
+ /* 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;
+ 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;
+ 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)
+ return false;
+
+ 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 flag_thread_jumps && flag_expensive_optimizations;
+ }
+
+ unsigned int execute (function *fun) final override
+ {
+ calculate_dominance_info (CDI_DOMINATORS);
+ bool changed = false;
+ /* Collect candidates in dominator preorder before mutating the CFG.
+ A merge can move PHI definitions before dominated candidates, so
+ processing their producers first makes one sweep sufficient. A source
+ without nonvirtual PHIs can also be folded, so gaining PHIs cannot make
+ an earlier candidate newly eligible. Store block indices because a
+ merge can delete blocks. */
+ auto_vec<basic_block> bbs = get_all_dominated_blocks
+ (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (fun));
+ auto_vec<int> candidates;
+ unsigned i;
+ basic_block bb;
+ FOR_EACH_VEC_ELT (bbs, i, bb)
+ if (bb->index >= NUM_FIXED_BLOCKS
+ && safe_is_a <gcond *> (*gsi_last_bb (bb)))
+ candidates.safe_push (bb->index);
+
+ 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 = 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)
