On Tue, Jun 16, 2026 at 5:22 PM <[email protected]> wrote: > > 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.
So this is (cmp ? CST1 : CST2) ==/!= CST, we should attempt to simplify that with a match pattern like (simplify (ne (cond^ @0 INTEGER_CST@1 INTEGER_CST@2) INTEGER_CST@3) (if (@1 != @3 && @2 == @3) @0))) ? (fix that to actually be correct, of course) > 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); I wonder whether we want to do this after VRP to give us a chance to eliminate redundant compares after inlining first? There's also likely a bit of DCE/DSE left on the plate at this point which might inhibit this transform? I realize this might require pushing back thread-jumps-full, but maybe that's not too bad? > 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) >
