Hi Andrea, Thanks for taking a look.
> On 16 Jun 2026, at 03:12, Andrew Pinski <[email protected]> > wrote: > > On Mon, Jun 15, 2026 at 8:55 AM <[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. >> >> 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 >> branch is folded to a constant. Folding the condition (rather than >> editing edges) leaves the CFG topology and dominator info valid for the >> rest of the pass; the requested cfg cleanup removes the dead arm. >> >> 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 (e.g. predictable chess-eval >> selects) is unaffected. >> >> Bootstrapped and regtested on aarch64-unknown-linux-gnu. >> >> Richard, is this the direction you had in mind for this PR? >> >> Thanks, >> Kyrill >> >> 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/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.c | 26 ++ >> gcc/tree-pass.h | 1 + >> gcc/tree-ssa-ifcombine.cc | 381 +++++++++++++++++++++ >> 6 files changed, 456 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.c >> >> diff --git a/gcc/passes.def b/gcc/passes.def >> index 1fc867fae51..3c4f0629e78 100644 >> --- a/gcc/passes.def >> +++ b/gcc/passes.def >> @@ -233,6 +233,7 @@ along with GCC; see the file COPYING3. If not see >> NEXT_PASS (pass_return_slot); >> NEXT_PASS (pass_fre, true /* may_iterate */); >> NEXT_PASS (pass_merge_phi); >> + NEXT_PASS (pass_merge_diamonds); >> NEXT_PASS (pass_thread_jumps_full, /*first=*/true); >> NEXT_PASS (pass_vrp, false /* final_p*/); >> NEXT_PASS (pass_array_bounds); >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c >> b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c >> new file mode 100644 >> index 00000000000..59c7762a3b3 >> --- /dev/null >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-2.c >> @@ -0,0 +1,32 @@ >> +/* Execution test: merging same-condition if-convertible diamonds must >> + preserve semantics. PR tree-optimization/125672. */ >> +/* { dg-do run } */ >> +/* { dg-options "-O2" } */ >> + >> +__attribute__((noipa)) static void >> +kern (int n, const int *a, const int *b, int *o) >> +{ >> + for (int i = 0; i < n; i++) >> + { >> + int m0 = (a[i] > b[i]) ? -1 : 0; /* a comparison mask */ >> + int m1 = (a[i] < b[i]) ? -1 : 0; /* a second mask */ >> + o[4*i + 0] = (m0 == -1) ? a[i] : b[i]; /* select under mask 0 */ >> + o[4*i + 1] = (m1 == -1) ? a[i] : b[i]; /* select under mask 1 */ >> + o[4*i + 2] = (m0 == -1) ? b[i] : a[i]; /* mask 0 again */ >> + o[4*i + 3] = (m1 == -1) ? b[i] : a[i]; /* mask 1 again */ >> + } >> +} >> + >> +int >> +main (void) >> +{ >> + int a[3] = { 5, 2, 9 }; >> + int b[3] = { 3, 7, 9 }; >> + int o[12]; >> + int exp[12] = { 5, 3, 3, 5, 7, 2, 2, 7, 9, 9, 9, 9 }; >> + kern (3, a, b, o); >> + for (int i = 0; i < 12; i++) >> + if (o[i] != exp[i]) >> + __builtin_abort (); >> + return 0; >> +} >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c >> b/gcc/testsuite/gcc.dg/tree-ssa/pr125672-3.c >> new file mode 100644 >> index 00000000000..811b6490357 >> --- /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.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..96414131c36 100644 >> --- a/gcc/tree-ssa-ifcombine.cc >> +++ b/gcc/tree-ssa-ifcombine.cc >> @@ -1358,6 +1358,387 @@ 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. Requires valid dominator info; makes no CFG >> + change. */ >> + >> +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; >> + >> + tree m = gimple_cond_lhs (gc); >> + tree c = gimple_cond_rhs (gc); >> + if (TREE_CODE (m) != SSA_NAME && TREE_CODE (c) == SSA_NAME) >> + std::swap (m, c); >> + if (TREE_CODE (m) != SSA_NAME || TREE_CODE (c) != INTEGER_CST) >> + return false; > > SSA_NAME should always be first and INTEGER_CST will always be last > based on canonicalization. (See tree_swap_operands_p, it has been this > way since before tree-ssa) So the swapping part is NOT needed. Ok, removed. > > >> + >> + 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 = operand_equal_p (vt, c, 0); >> + bool c_eq_vf = operand_equal_p (vf, c, 0); > > Since they are both INTEGER_CST, use tree_int_cst_equal. Done. > >> + /* Whether "m == c" is true when cm's branch is taken. */ >> + bool when_true; >> + if (c_eq_vt && !c_eq_vf) >> + when_true = true; >> + else if (c_eq_vf && !c_eq_vt) >> + when_true = false; >> + else >> + return false; > > if (c_eq_vt == c_eq_vf) > return false; > when_true = c_eq_vt; Ok, done. > >> + if (cc == NE_EXPR) >> + when_true = !when_true; >> + >> + gcond *ctrl = as_a <gcond *> (*gsi_last_bb (cm)); >> + enum tree_code ctrl_code = gimple_cond_code (ctrl); >> + tree ctrl_lhs = gimple_cond_lhs (ctrl); >> + tree ctrl_rhs = gimple_cond_rhs (ctrl); >> + if (!when_true) >> + { >> + ctrl_code = invert_tree_comparison (ctrl_code, HONOR_NANS (ctrl_lhs)); > Why not switch around true/false edges instead of using > invert_tree_comparison and failing? Yeah, done that now. > >> + if (ctrl_code == ERROR_MARK) >> + return false; >> + } >> + >> + gimple_cond_set_code (gc, ctrl_code); >> + gimple_cond_set_lhs (gc, ctrl_lhs); >> + gimple_cond_set_rhs (gc, ctrl_rhs); >> + update_stmt (gc); >> + >> + 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 (gphi *phi = dyn_cast <gphi *> (use_stmt)) >> + ub = gimple_phi_arg_edge (phi, PHI_ARG_INDEX_FROM_USE (use_p))->src; > phi_arg_index_from_use instead of all caps version. > But really just: > ub = phi_arg_edge_from_use (use_p)->src; Done. >> + 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; >> + >> + /* Every live non-virtual PHI of JOIN1 must be recomputable at JOIN2; >> + JOIN1 must carry no virtual PHI. */ > > I am not a fan of this wording. Why not all non-virtual, why are > unused one (non-live) special? Why are vPHI special? Reworded, and the vPHI restriction is dropped. In non-live (zero-use) PHIs there is simply to recompute, so the move loop drops them instead of bailing. Only the live PHIs need a home at JOIN2, hence only they are required to be recomputable there (all_uses_dominated_by). > >> + 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)) >> + { >> + ok = false; >> + break; >> + } >> + 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 (!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); >> + } >> + >> + /* Fold away B1's now-redundant branch. Both arms reach JOIN1, which >> no >> + longer holds a PHI distinguishing them, so the branch is dead. >> Making >> + the condition constant (rather than editing edges) forces it to the >> + true edge, which reaches JOIN1 directly or via the empty arm, and >> keeps >> + the CFG and dominator info valid for the rest of the pass; cfg >> cleanup >> + then removes the dead edge and empty block. */ >> + gimple_cond_make_true (c1); > > I think you can remove the edge. If you use the correct order of how > you run over the bbs, then deleting that bb can be handled too. Yes, done. > >> + update_stmt (c1); >> + >> + 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; } > > I think we need `!optimize_debug` Done. > >> + 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); >> + >> + /* Phase 1: de-indirect mask comparisons (no CFG change). */ > That is not true; there is CFG change happening, as you change the > conditional and in some cases swap around the if (see above on reasons > why). Right, fixed. > >> + bool di = true; >> + while (di) >> + { >> + di = false; >> + basic_block bb; >> + FOR_EACH_BB_FN (bb, fun) >> + if (deindirect_mask_cond (bb)) >> + di = any = true; > Looping here seems wrong. Maybe a better order of BB is needed. Maybe > single_pred_before_succ_order. Or maybe reverse_dom order that is > inner first. Ok, done. Phase 1 is now a single forward pass over single_pred_before_succ_order () with no while loop. In that order an outer mask test is de-indirected before the inner test that depends on it, so one pass suffices. > >> + } >> + >> + /* Phase 2: merge diamonds controlled by identical conditions. Neither >> the >> + PHI motion nor folding a branch to a constant changes the CFG >> topology, so >> + dominator info stays valid throughout: a single walk suffices, and the >> + inner loop drains a whole chain of same-condition diamonds into BB. A >> + folded branch becomes constant, so merge_cond_diamond never re-matches >> it, >> + and the walk need not be in dominator order. A chain collapses into its >> + deepest member whichever way it is visited. */ >> + basic_block bb; >> + FOR_EACH_BB_FN (bb, fun) > > I suspect you want a different order since the above is just some > random order of bbs. Maybe single_pred_before_succ_order. Like what is > used in phiopt and ifcombine. Indeed, done. > > >> + while (merge_cond_diamond (bb)) >> + any = true; > > Also 2 BB walks seems wrong. And looping seems wrong too. Is there any > how to combine the two or add a working list to do the second only on > that list in a specific order so you don't need 2 while done_something > loop. Also The done_something looping is gone (the ordering fix removed the need for it), and I took the worklist suggestion. Phase 1 now collects the if-convertible diamond heads it visits into a worklist, and phase 2 walks only that list. I also tried folding the two into a single interleaved walk (de-indirect then merge per block) but it regresses, which is why the two phases stay separate. merge_cond_diamond only fuses two diamonds when their GIMPLE_CONDs are already identical, and for this idiom that holds only after both have been de-indirected; in an interleaved walk a diamond is reached for merging before a later same-condition diamond has been de-indirected. This reduces the if-conversion we get on the astcenc motivating benchmark. I’ve tried to express that in a new test gcc.dg/tree-ssa/pr125672-6.c. I’ll send an updated version shortly. Thanks again, Kyrill > >> + 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)
