On Thu, Jun 25, 2026 at 5:40 AM Richard Biener <[email protected]> wrote: > > 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)
The other simpler option is to allow `-(convert)(compare)` and `(convert)(compare)` in early phiopt. And that seems to fix the issue too (I hacked up phiopt_early_allow to accept NEGATE_EXPR even with a non-empty sequence to test it out). That might be the better option for this case. Since those 2 forms will prop into the next case and not worry about jump threading. Note phiopt does reject if there is a predicate though so it could use that for the threaded jump and it looks like that code needs to be changed slightly too to support disabling for -/convert case too. Thanks, Andrea > > > > 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) > >
