On Fri, Jun 26, 2026 at 10:52 PM Andrea Pinski <[email protected]> wrote: > > 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.
So that leaves part 2 as still being needed after the change to phiopt. I am thinking if there is a decent way of solving this. I think your code is not the best; especially when it comes to debug info. look for say: if (a) goto empty; else goto join; empty: goto join; r = PHI<b,c> r1 = PHI<b1,c1> join here is join0. and then look into the immediate dominators for a similar pattern with the same condition. But only look for one. For each phi in join0, see if we can move it to join1 and move it. That is, all args of the phi can be reached at join1. And then just set cfgcleanup if we moved any phi. It is similar to yours but in the opposite direction which solves the debug info and the use problem. There is only one issue which I think both don't take into account is lengthening the live range of the phi/args. In your case you length the args live range maybe across calls. While with my idea you only length the result of the phi and maybe shorten the live range of the args. So maybe this should be even more localized. Thanks, Andrea > > > > > > 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) > > >
