From: Kyrylo Tkachov <[email protected]>
The backward jump threader tail-duplicates an if-convertible "diamond" chain
when the same predicate controls several diamonds. The astcenc "none" backend
lowers a per-lane "r = mask ? hi : lo" select, where one comparison mask drives
two selects, to such a chain:
m = (a > b) ? -1 : 0; // a comparison mask, kept as PHI<0, -1>
...
if (m == -1) ... // select 1 under the mask
...
if (m == -1) ... // select 2 under the same mask
The threader sees the later tests are redundant on the path through the first
(m, hence m == -1, is known) and tail-duplicates the intervening diamonds to
fold the branch away, turning an N-diamond chain into a 2^N decision tree that
reconverges at a single multi-predecessor merge. phiopt and RTL if-conversion
can no longer recognise the per-select conditional moves, so they come out as
compare+branch. On 731.astcenc_r (SPEC CPU2026, aarch64) this is the dominant
gap in compute_quantized_weights_for_decimation, where -O3 emits the hot select
kernel with ~34 branches / 12 fcsel instead of ~5 / 24. This pass gives ~19%
improvement on that benchmark overall.
Rather than restrict the threader (which is doing a legitimate transform), this
removes the underlying redundancy with two value/control simplifications that
improve the GIMPLE in their own right; a beneficial side effect is that the
threader no longer finds correlated conditions to tail-duplicate. They run in a
small pass, pass_merge_diamonds, placed before pass_thread_jumps_full and gated
on flag_thread_jumps, so it runs exactly when the backward threader does (under
-fno-thread-jumps the diamonds stay clean and if-conversion handles them):
1. De-indirection: a test "m == C" / "m != C" whose operand m is a PHI of two
integer constants (a mask "cmp ? cst : cst" from a clean diamond) is
rewritten to test the mask's own controlling condition cmp. We already
perform this for a single-use mask; here it is exposed across a multi-use
mask PHI. The mask PHI then becomes dead.
2. Merge: two if-convertible diamonds controlled by an identical condition,
the first dominating the second, are merged. The live PHIs of the first
are recomputed in the second under its (identical) branch, and the first
diamond's now-dead edge is removed with remove_edge_and_dominated_blocks,
which keeps the dominator information valid for the rest of the pass.
De-indirection runs as a phase that completes before any merge, so that all
same-condition diamonds are recognised before one of them is folded away; the
merge phase then drains each chain of same-condition diamonds, visiting the
if-convertible diamond heads collected during de-indirection.
The result is a chain of distinct-condition, two-PHI diamonds that the threader
leaves alone and RTL if-conversion lowers to conditional moves. Whether each
select becomes a conditional move stays an RTL if-conversion cost-model
decision, so code that benefits from branches is unaffected.
Bootstrapped and regtested on aarch64-unknown-linux-gnu.
Signed-off-by: Kyrylo Tkachov <[email protected]>
gcc/ChangeLog:
PR tree-optimization/125672
* tree-ssa-ifcombine.cc (ifcvt_diamond_join): New function.
(deindirect_mask_cond): New function.
(all_uses_dominated_by): New function.
(merge_cond_diamond): New function.
(class pass_merge_diamonds): New pass.
(make_pass_merge_diamonds): New function.
* tree-pass.h (make_pass_merge_diamonds): Declare.
* passes.def: Run pass_merge_diamonds before pass_thread_jumps_full.
gcc/testsuite/ChangeLog:
PR tree-optimization/125672
* gcc.dg/tree-ssa/pr125672.c: New test.
* gcc.dg/tree-ssa/pr125672-2.c: New test.
* gcc.dg/tree-ssa/pr125672-3.c: New test.
* gcc.dg/tree-ssa/pr125672-4.c: New test.
* gcc.dg/tree-ssa/pr125672-5.c: New test.
* gcc.dg/tree-ssa/pr125672-6.c: New test.
---
gcc/passes.def | 1 +
gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c | 32 ++
gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c | 15 +
gcc/testsuite/gcc.dg/tree-ssa/pr125672-4.c | 22 ++
gcc/testsuite/gcc.dg/tree-ssa/pr125672-5.c | 37 ++
gcc/testsuite/gcc.dg/tree-ssa/pr125672-6.c | 26 ++
gcc/testsuite/gcc.dg/tree-ssa/pr125672.c | 26 ++
gcc/tree-pass.h | 1 +
gcc/tree-ssa-ifcombine.cc | 400 +++++++++++++++++++++
9 files changed, 560 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-4.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
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr125672.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..59c7762a3b3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c
@@ -0,0 +1,32 @@
+/* Execution test: merging same-condition if-convertible diamonds must
+ preserve semantics. PR tree-optimization/125672. */
+/* { 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/testsuite/gcc.dg/tree-ssa/pr125672-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c
new file mode 100644
index 00000000000..958d0d2aaec
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c
@@ -0,0 +1,15 @@
+/* A single comparison mask feeding selects is already simplified by phiopt,
+ so pass_merge_diamonds is not needed and must not fire here; it only acts
+ when interleaved masks defeat phiopt. PR tree-optimization/125672. */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-mergediam-details" } */
+
+void
+f (float a, float b, int x, int y, int u, int v, int *o)
+{
+ int m = (a > b) ? -1 : 0;
+ o[0] = (m == -1) ? x : y;
+ o[1] = (m == -1) ? u : v;
+}
+
+/* { dg-final { scan-tree-dump-not "de-indirecting mask test" "mergediam" } }
*/
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr125672-4.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-4.c
new file mode 100644
index 00000000000..3c02943ccc8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-4.c
@@ -0,0 +1,22 @@
+/* PR tree-optimization/125672: two comparison masks are interleaved (which
+ defeats phiopt), and each drives two selects. pass_merge_diamonds
+ de-indirects the four mask tests and merges each pair of same-condition
+ diamonds, so both pairs are merged. */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-mergediam-details" } */
+
+void
+f (float a, float b, float c, float d,
+ int x0, int y0, int u0, int v0, int x1, int y1, int u1, int v1, int *o)
+{
+ int m0 = (a > b) ? -1 : 0;
+ int m1 = (c > d) ? -1 : 0;
+ o[0] = (m0 == -1) ? x0 : y0; /* mask 0 */
+ o[1] = (m1 == -1) ? x1 : y1; /* mask 1, interleaved */
+ o[2] = (m0 == -1) ? u0 : v0; /* mask 0 again */
+ o[3] = (m1 == -1) ? u1 : v1; /* mask 1 again */
+}
+
+/* Both same-condition pairs are merged. */
+/* { 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..15100f54cff
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-5.c
@@ -0,0 +1,37 @@
+/* PR tree-optimization/125672: a chain of same-condition diamonds collapses
via
+ successive merges in a single pass. One mask drives three selects (a second
+ mask is interleaved so phiopt cannot pre-simplify); after de-indirection the
+ three mask-0 diamonds form a dominator chain that is drained by repeated
+ merges. Each merge removes the dominating diamond's now-dead edge with
+ remove_edge_and_dominated_blocks, which keeps the dominator tree valid so
the
+ next merge in the chain still sees correct dominator information. This is
also an execution test: a wrong dominator
+ update would miscompile the recomputed selects. */
+
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-mergediam-details" } */
+
+__attribute__((noipa)) static void
+kern (float a, float b, float c, float d,
+ int x0, int y0, int u0, int v0, int p0, int q0, int x1, int y1, int *o)
+{
+ int m0 = (a > b) ? -1 : 0;
+ int m1 = (c > d) ? -1 : 0;
+ o[0] = (m0 == -1) ? x0 : y0; /* mask 0 */
+ o[1] = (m1 == -1) ? x1 : y1; /* mask 1, interleaved (defeats phiopt) */
+ o[2] = (m0 == -1) ? u0 : v0; /* mask 0 */
+ o[3] = (m0 == -1) ? p0 : q0; /* mask 0 (three deep) */
+}
+
+int
+main (void)
+{
+ int o[4];
+ kern (2, 1, 1, 2, 10, 11, 12, 13, 14, 15, 20, 21, o);
+ /* a>b true -> m0; c>d false -> !m1. */
+ if (o[0] != 10 || o[1] != 21 || o[2] != 12 || o[3] != 14)
+ __builtin_abort ();
+ return 0;
+}
+
+/* The three mask-0 diamonds collapse into one via two successive merges. */
+/* { 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..4be14d16b7d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-6.c
@@ -0,0 +1,26 @@
+/* PR tree-optimization/125672: pass_merge_diamonds de-indirects every mask
test
+ before it merges any diamond, so that all same-condition diamonds are
+ recognised before one of them is folded away. Two masks drive the selects
+ (m1 is interleaved to defeat phiopt), and the result R of the first m0
select
+ is consumed only at the end (o[3] = R), placing its use below the later m0
+ select. With the phases kept separate the pass performs three merges; a
+ single walk that merges as it de-indirects commits to a merge before the
+ remaining mask tests are de-indirected and performs only two. */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-mergediam-details" } */
+
+void
+f (float a, float b, float c, float d,
+ int p, int q, int x0, int y0, int x1, int y1, int u1, int v1, int *o)
+{
+ int m0 = (a > b) ? -1 : 0;
+ int m1 = (c > d) ? -1 : 0;
+ int r = (m0 == -1) ? p : q; /* m0 select; result reused at o[3] */
+ o[0] = (m1 == -1) ? x1 : y1; /* m1 select, interleaved (defeats phiopt) */
+ o[1] = (m0 == -1) ? x0 : y0; /* m0 select */
+ o[2] = (m1 == -1) ? u1 : v1; /* m1 select */
+ o[3] = r; /* late use of the first m0 select */
+}
+
+/* { dg-final { scan-tree-dump-times "merging if-convertible diamond" 3
"mergediam" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr125672.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr125672.c
new file mode 100644
index 00000000000..87acf94a559
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672.c
@@ -0,0 +1,26 @@
+/* PR tree-optimization/125672: when one comparison mask drives several
+ per-lane selects, the backward jump threader tail-duplicates the
+ if-convertible diamond chain. pass_merge_diamonds removes the redundancy
+ before threading: it de-indirects the mask comparisons and merges the
+ diamonds controlled by an identical condition. */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-mergediam-details" } */
+
+void
+f (float a, float b, float c, float d,
+ int x0, int y0, int x1, int y1,
+ int u0, int v0, int u1, int v1, int *o)
+{
+ int m0 = (a > b) ? -1 : 0;
+ int m1 = (c > d) ? -1 : 0;
+ o[0] = (m0 == -1) ? x0 : y0;
+ o[1] = (m1 == -1) ? x1 : y1;
+ o[2] = (m0 == -1) ? u0 : v0;
+ o[3] = (m1 == -1) ? u1 : v1;
+}
+
+/* The mask comparisons are de-indirected to test the comparison directly...
*/
+/* { dg-final { scan-tree-dump "de-indirecting mask test" "mergediam" } } */
+/* ... and the two diamonds per mask are merged into one. */
+/* { dg-final { scan-tree-dump "merging if-convertible diamond" "mergediam" }
} */
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 6489abf3a06..7b33862a06a 100644
--- a/gcc/tree-ssa-ifcombine.cc
+++ b/gcc/tree-ssa-ifcombine.cc
@@ -1358,6 +1358,406 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
/* Main entry for the tree if-conversion pass. */
+/* Merge if-convertible "diamonds" controlled by an identical condition, and
+ de-indirect mask comparisons that feed them, before the backward jump
+ threaders run.
+
+ When a comparison mask drives several selects, as in
+
+ m = (a > b) ? -1 : 0; // comparison mask, kept as a PHI of 0 and -1
+ if (m == -1) ... // a select under the mask
+ if (m == -1) ... // another select under the same mask
+
+ the per-lane selects lower to a chain of if-convertible diamonds in which
+ the same predicate controls several diamonds. The backward jump threader
+ then notices the later tests are redundant on the path through the earlier
+ one (m, and hence "m == -1", is known there) and tail-duplicates the
+ intervening diamonds to fold the branch away, turning an N-diamond chain
+ into a 2^N decision tree that reconverges at a single multi-predecessor
+ merge. RTL if-conversion can no longer recover the per-select conditional
+ moves and emits compare+branch instead.
+
+ This pass removes the redundancy at its two sources, so there is nothing for
+ threading to duplicate.
+
+ De-indirection: a test "m == C" / "m != C" whose operand m is a PHI of two
+ integer constants (a mask "cmp ? cst : cst") is rewritten to test the mask's
+ own controlling condition cmp; the mask PHI then becomes dead.
+
+ Merge: two if-convertible diamonds controlled by an identical condition,
+ where the first dominates the second, are merged: the PHIs of the first are
+ recomputed in the second under its identical branch and the first branch is
+ folded away, so both selects live under one branch.
+
+ The result is a chain of distinct-condition diamonds that the threader
+ leaves alone and RTL if-conversion lowers to conditional moves; whether each
+ select actually becomes a conditional move stays an RTL if-conversion
+ cost-model decision. */
+
+/* If COND_BB heads an if-then-else whose two arms are empty (no side effects)
+ and reconverge at a single join block, return that join block and set
+ *E_TRUE and *E_FALSE to the edges entering the join on the condition's true
+ and false side (possibly through 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);
+ }
+
+ /* One arm may reach the join directly (a triangle), with the other through
+ an empty forwarder, or both arms may forward to the join. */
+ 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;
+}
+
+/* Rewrite the GIMPLE_COND ending COND_BB if it tests "m == C" / "m != C"
+ where m is a PHI of two integer constants controlled by a clean diamond:
+ replace the test with that diamond's controlling condition. This removes
+ the mask indirection so the predicate is exposed directly. Returns true if
+ the condition was rewritten, which may swap COND_BB's outgoing true/false
+ edges. Requires valid dominator info. */
+
+static bool
+deindirect_mask_cond (basic_block cond_bb)
+{
+ gcond *gc = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
+ if (!gc)
+ return false;
+ enum tree_code cc = gimple_cond_code (gc);
+ if (cc != EQ_EXPR && cc != NE_EXPR)
+ return false;
+
+ /* By canonicalization the SSA_NAME is the LHS and the INTEGER_CST the RHS
+ (tree_swap_operands_p), so no operand swap is needed. */
+ tree m = gimple_cond_lhs (gc);
+ tree c = gimple_cond_rhs (gc);
+ if (TREE_CODE (m) != SSA_NAME || TREE_CODE (c) != INTEGER_CST)
+ return false;
+
+ gphi *mphi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (m));
+ if (!mphi || gimple_phi_num_args (mphi) != 2)
+ return false;
+ basic_block jm = gimple_bb (mphi);
+
+ basic_block cm = get_immediate_dominator (CDI_DOMINATORS, jm);
+ if (!cm)
+ return false;
+ edge et, ef;
+ if (ifcvt_diamond_join (cm, &et, &ef) != jm)
+ return false;
+
+ tree vt = PHI_ARG_DEF_FROM_EDGE (mphi, et);
+ tree vf = PHI_ARG_DEF_FROM_EDGE (mphi, ef);
+ if (TREE_CODE (vt) != INTEGER_CST || TREE_CODE (vf) != INTEGER_CST)
+ return false;
+
+ bool c_eq_vt = tree_int_cst_equal (vt, c);
+ bool c_eq_vf = tree_int_cst_equal (vf, c);
+ /* C must equal exactly one of the two mask values, otherwise the test does
+ not reduce to the mask's controlling condition. */
+ if (c_eq_vt == c_eq_vf)
+ return false;
+ /* Whether "m == c" holds when cm's true edge (ET) is taken. */
+ bool when_true = c_eq_vt;
+ if (cc == NE_EXPR)
+ when_true = !when_true;
+
+ /* Copy the mask's controlling condition into GC verbatim. If "m == c"
+ instead holds on cm's false edge, swap GC's outgoing true/false edges
+ rather than inverting the comparison (inversion would fail for an
+ unordered FP comparison). */
+ gcond *ctrl = as_a <gcond *> (*gsi_last_bb (cm));
+ gimple_cond_set_code (gc, gimple_cond_code (ctrl));
+ gimple_cond_set_lhs (gc, gimple_cond_lhs (ctrl));
+ gimple_cond_set_rhs (gc, gimple_cond_rhs (ctrl));
+ update_stmt (gc);
+ if (!when_true)
+ {
+ EDGE_SUCC (cond_bb, 0)->flags ^= (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+ EDGE_SUCC (cond_bb, 1)->flags ^= (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "de-indirecting mask test in bb%d via diamond bb%d\n",
+ cond_bb->index, cm->index);
+ return true;
+}
+
+/* Return true if every use of NAME is dominated by block BY (treating a use
+ in a PHI as occurring on the corresponding predecessor edge). */
+
+static bool
+all_uses_dominated_by (tree name, basic_block by)
+{
+ imm_use_iterator it;
+ use_operand_p use_p;
+ gimple *use_stmt;
+ FOR_EACH_IMM_USE_FAST (use_p, it, name)
+ {
+ use_stmt = USE_STMT (use_p);
+ if (is_gimple_debug (use_stmt))
+ continue;
+ basic_block ub;
+ if (is_a <gphi *> (use_stmt))
+ ub = phi_arg_edge_from_use (use_p)->src;
+ else
+ ub = gimple_bb (use_stmt);
+ if (!dominated_by_p (CDI_DOMINATORS, ub, by))
+ return false;
+ }
+ return true;
+}
+
+/* Try to merge the same-condition diamond headed by B2 into a dominating
+ diamond. Return true if a merge was performed. */
+
+static bool
+merge_cond_diamond (basic_block b2)
+{
+ edge t2, f2;
+ basic_block join2 = ifcvt_diamond_join (b2, &t2, &f2);
+ if (!join2)
+ return false;
+ gcond *c2 = as_a <gcond *> (*gsi_last_bb (b2));
+
+ 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)
+ continue;
+ if (gimple_cond_code (c1) != gimple_cond_code (c2)
+ || !operand_equal_p (gimple_cond_lhs (c1), gimple_cond_lhs (c2), 0)
+ || !operand_equal_p (gimple_cond_rhs (c1), gimple_cond_rhs (c2), 0))
+ continue;
+
+ edge t1, f1;
+ basic_block join1 = ifcvt_diamond_join (b1, &t1, &f1);
+ if (!join1 || join1 == join2 || join1 == b2)
+ continue;
+
+ /* Each live data PHI of JOIN1 must be recomputable at JOIN2. A virtual
+ PHI is left in place: the diamond arms are side-effect free (checked by
+ ifcvt_diamond_join), so its two arguments are equal and it degenerates
+ once B1's branch is folded and cfg cleanup merges the edge. */
+ bool ok = true, any_phi = false;
+ for (gphi_iterator gpi = gsi_start_phis (join1);
+ !gsi_end_p (gpi); gsi_next (&gpi))
+ {
+ gphi *phi = gpi.phi ();
+ tree res = gimple_phi_result (phi);
+ if (virtual_operand_p (res))
+ continue;
+ any_phi = true;
+ if (!has_zero_uses (res) && !all_uses_dominated_by (res, join2))
+ {
+ ok = false;
+ break;
+ }
+ }
+ if (!ok || !any_phi)
+ continue;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "merging if-convertible diamond bb%d into same-condition "
+ "diamond bb%d\n", b1->index, b2->index);
+
+ /* Move each live PHI of JOIN1 to JOIN2 under B2's branch; drop dead
+ ones. */
+ for (gphi_iterator gpi = gsi_start_phis (join1); !gsi_end_p (gpi);)
+ {
+ gphi *phi = gpi.phi ();
+ tree res = gimple_phi_result (phi);
+ if (virtual_operand_p (res))
+ {
+ gsi_next (&gpi);
+ continue;
+ }
+ if (!has_zero_uses (res))
+ {
+ tree tv = PHI_ARG_DEF_FROM_EDGE (phi, t1);
+ tree fv = PHI_ARG_DEF_FROM_EDGE (phi, f1);
+ location_t tl = gimple_phi_arg_location_from_edge (phi, t1);
+ location_t fl = gimple_phi_arg_location_from_edge (phi, f1);
+ tree nres = copy_ssa_name (res);
+ gphi *nphi = create_phi_node (nres, join2);
+ add_phi_arg (nphi, tv, t2, tl);
+ add_phi_arg (nphi, fv, f2, fl);
+
+ imm_use_iterator it;
+ use_operand_p use_p;
+ gimple *use_stmt;
+ FOR_EACH_IMM_USE_STMT (use_stmt, it, res)
+ {
+ /* Non-debug uses are all dominated by JOIN2 (checked above).
+ A debug use may sit in a block JOIN2 does not dominate; the
+ recomputed value is not available there, so reset it rather
+ than create invalid SSA. */
+ if (is_gimple_debug (use_stmt)
+ && !dominated_by_p (CDI_DOMINATORS,
+ gimple_bb (use_stmt), join2))
+ {
+ gimple_debug_bind_reset_value (use_stmt);
+ update_stmt (use_stmt);
+ continue;
+ }
+ FOR_EACH_IMM_USE_ON_STMT (use_p, it)
+ SET_USE (use_p, nres);
+ update_stmt (use_stmt);
+ }
+ }
+ remove_phi_node (&gpi, true);
+ }
+
+ /* Remove B1's now-redundant branch. Both arms reach JOIN1, which no
+ longer holds a PHI distinguishing them, so the branch is dead. Keep
B1's
+ true edge as a fallthrough and delete the false edge with any blocks
that
+ become unreachable; remove_edge_and_dominated_blocks keeps the
dominator
+ info valid for the rest of the walk. cfg cleanup merges the empty
arm. */
+ edge b1t = EDGE_SUCC (b1, 0);
+ edge b1f = EDGE_SUCC (b1, 1);
+ if (b1f->flags & EDGE_TRUE_VALUE)
+ std::swap (b1t, b1f);
+ gimple_stmt_iterator gsic1 = gsi_last_bb (b1);
+ gsi_remove (&gsic1, true);
+ remove_edge_and_dominated_blocks (b1f);
+ b1t->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+ b1t->flags |= EDGE_FALLTHRU;
+ b1t->probability = profile_probability::always ();
+
+ 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)
+ {}
+
+ /* opt_pass methods: */
+ /* This pass only removes redundancy that the backward jump threader would
+ otherwise tail-duplicate, so it is only useful when that threader runs.
*/
+ bool gate (function *) final override
+ { return flag_thread_jumps && !optimize_debug; }
+ unsigned int execute (function *) final override;
+
+}; // class pass_merge_diamonds
+
+unsigned int
+pass_merge_diamonds::execute (function *fun)
+{
+ bool any = false;
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ /* Visit blocks so a block's single predecessor comes first (as in phiopt
+ and ifcombine). This is ~dominator order, so the two phases below need no
+ iteration: in phase 1 an outer mask test is de-indirected before an inner
+ test that depends on it, and in phase 2 merge_cond_diamond sees a
+ dominating diamond's controlling condition already de-indirected. The
+ phases are kept separate: all conditions must be de-indirected before
+ any merge so that same-condition diamonds are recognised as such. */
+ basic_block *order = single_pred_before_succ_order ();
+ int n = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS;
+
+ /* Phase 1: de-indirect mask comparisons, collecting the if-convertible
+ diamond heads to revisit for merging (a worklist for phase 2, so phase 2
+ does not re-walk every block). */
+ auto_vec<basic_block> heads;
+ for (int i = 0; i < n; i++)
+ {
+ if (deindirect_mask_cond (order[i]))
+ any = true;
+ edge et, ef;
+ if (ifcvt_diamond_join (order[i], &et, &ef))
+ heads.safe_push (order[i]);
+ }
+
+ /* Phase 2: merge diamonds controlled by identical conditions, visiting only
+ the collected heads; the inner loop drains a whole chain of
+ same-condition diamonds into B2. Kept separate from phase 1: every
+ condition must be de-indirected before any merge folds a diamond away. */
+ for (basic_block b2 : heads)
+ while (merge_cond_diamond (b2))
+ any = true;
+
+ free (order);
+ return any ? TODO_cleanup_cfg : 0;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_merge_diamonds (gcc::context *ctxt)
+{
+ return new pass_merge_diamonds (ctxt);
+}
+
+
namespace {
const pass_data pass_data_tree_ifcombine =
--
2.50.1 (Apple Git-155)
