On Wed, 10 Jun 2026, [email protected] wrote: > From: Kyrylo Tkachov <[email protected]> > > In the sink pass, if-convert a diamond that selects between two loads at > data-dependent addresses (PHI <*P, *Q>) into a single reg-offset load behind > branchless selects, reusing phi-opt's factoring helpers > (factor_out_conditional_load from the previous patch and > factor_out_conditional_operation, made non-static here) to common the load > and its address. Guarded so that outside any loop it always fires (nothing > to vectorise), > and in a loop only on non-vectorisable load-address recurrences, leaving > affine vectorisable loops alone. This was needed to avoid regressing the > marian > benchmark in SPEC2026 that otherwise ended up using expensive gathers to > vectorise. We can look to relax this condition in the future for cases where > we think it's beneficial.
Hmm, if it's bad for vectorization we should do it after vectorization. I always feel bad when I see lots of code anticipating whether we might eventually vectorize or not. Also ... > The load is commoned only when both arms are guaranteed to reduce to pure > speculatable scalar (scc_arms_speculatable_p), so the branchless finish always > succeeds and no commoned-but-still-branching diamond is ever left behind. The > recurrence walk is bounded by a new --param=sink-diamond-recurrence-limit > (default 256). > > With this patch the Snappy hot loop gets if-converted optimally and > performance > improves by 25% on my aarch64 machine, making it a bit better than what LLVM > gets today. > > The code goes from: > .L8: ; ---type==0 arm > lsr x3, x1, 2 ; tag >> 2 > add x1, x0, x3 > add x3, x3, 2 > add x0, x0, x3 ; ip += (tag>>2)+2 > ldrb w1, [x1, 1] ; LOAD #1: tag = ip[(tag>>2)+1] > cmp x2, x0 > bls .L2 > .L5: ; loop head / else arm > ands x3, x1, 3 ; type = tag & 3 > beq .L8 ; <-- DATA-DEPENDENT BRANCH (mispredicts) > ldrb w1, [x0, x3] ; LOAD #2: tag = ip[type] > add w3, w3, 1 > add x0, x0, x3 ; ip += type+1 > cmp x2, x0 > bhi .L5 > > to: > .L3: ; --- single loop body, no diamond branch > lsr x4, x1, 2 ; tag >> 2 > ands x3, x1, 3 ; type = tag & 3 (Z = type==0) > csinc x1, x3, x4, ne ; offset = (type!=0) ? type : (tag>>2)+1 > ldrb w1, [x0, x1] ; ONE reg-offset LOAD: tag = ip[offset] > add x4, x4, 2 > csinc x3, x4, x3, eq ; advance = (type==0) ? (tag>>2)+2 : type+1 > add x0, x0, x3 ; ip += advance > cmp x2, x0 > bhi .L3 > > crucially avoiding the badly-predicted branch. > > Bootstrapped and tested on aarch64-none-linux-gnu. > > Signed-off-by: Kyrylo Tkachov <[email protected]> > > gcc/ > PR tree-optimization/125557 > * params.opt (sink-diamond-recurrence-limit): New param. > * doc/params.texi (sink-diamond-recurrence-limit): Document it. > * tree-ssa-phiopt.h (factor_out_conditional_operation): Declare. > * tree-ssa-phiopt.cc (factor_out_conditional_operation): Remove static. > * tree-ssa-sink.cc (scc_recurrence_p, scc_arms_speculatable_p) > (scc_try_ifconvert, sink_common_computations_to_bb): New. > (pass_sink_code::execute): Call it at the early sink. > > gcc/testsuite/ > PR tree-optimization/125557 > * gcc.dg/tree-ssa/scc-diamond-1.c: New test. > * gcc.dg/tree-ssa/scc-diamond-3.c: New test. > * gcc.target/aarch64/scc-diamond-2.c: New test. > --- > gcc/doc/params.texi | 9 + > gcc/params.opt | 4 + > gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-1.c | 36 ++ > gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-3.c | 49 +++ > .../gcc.target/aarch64/scc-diamond-2.c | 30 ++ > gcc/tree-ssa-phiopt.cc | 2 +- > gcc/tree-ssa-phiopt.h | 5 + > gcc/tree-ssa-sink.cc | 374 ++++++++++++++++++ > 8 files changed, 508 insertions(+), 1 deletion(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-1.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-3.c > create mode 100644 gcc/testsuite/gcc.target/aarch64/scc-diamond-2.c > > diff --git a/gcc/doc/params.texi b/gcc/doc/params.texi > index 28cfe73d9d7..09912b85e95 100644 > --- a/gcc/doc/params.texi > +++ b/gcc/doc/params.texi > @@ -1371,6 +1371,15 @@ The maximum number of conditional store pairs that can > be sunk. Set to 0 > if either vectorization (@option{-ftree-vectorize}) or if-conversion > (@option{-ftree-loop-if-convert}) is disabled. > > +@paindex sink-diamond-recurrence-limit > +@item sink-diamond-recurrence-limit > +The maximum number of SSA definitions the sink pass follows when checking > +whether a conditional load forms a data-dependent address recurrence, the > guard > +for if-converting a diamond that selects between two loads at data-dependent > +addresses (@code{PHI <*P, *Q>}) into a single reg-offset load behind > branchless > +selects. Larger values allow longer recurrences to be if-converted, at the > cost > +of compile time. > + > @paindex case-values-threshold > @item case-values-threshold > The smallest number of different values for which it is best to use a > diff --git a/gcc/params.opt b/gcc/params.opt > index 90f9943c8cb..d9df43e5464 100644 > --- a/gcc/params.opt > +++ b/gcc/params.opt > @@ -1069,6 +1069,10 @@ Maximum number of times that an insn could be > scheduled. > Common Joined UInteger Var(param_simultaneous_prefetches) Init(3) Param > Optimization > The number of prefetches that can run at the same time. > > +-param=sink-diamond-recurrence-limit= > +Common Joined UInteger Var(param_sink_diamond_recurrence_limit) Init(256) > IntegerRange(1, 2147483647) Param Optimization > +Maximum number of SSA definitions the sink pass follows when checking > whether a conditional load forms a data-dependent address recurrence (the > guard for if-converting diamond loads). > + > -param=sink-frequency-threshold= > Common Joined UInteger Var(param_sink_frequency_threshold) Init(75) > IntegerRange(0, 100) Param Optimization > Target block's relative execution frequency (as a percentage) required to > sink a statement. > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-1.c > b/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-1.c > new file mode 100644 > index 00000000000..5d419aa83d2 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-1.c > @@ -0,0 +1,36 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-sink1-details" } */ > + > +/* PR tree-optimization/125557. The loop selects, from the just-read byte, > the > + offset of the next load and advances a pointer -- a data-dependent load > + address recurrence (the loaded value feeds its own next address). Such a > + loop cannot vectorise, so sink_common_computations_to_bb commons the two > + conditional loads into one reg-offset load and if-converts the diamond > into > + branchless selects. scc_recurrence_p detects the recurrence and allows > it. */ > + > +#include <stddef.h> > +#include <stdint.h> > + > +const uint8_t * > +advance (const uint8_t *ip, size_t tag, const uint8_t *end) > +{ > + while (ip < end) > + { > + size_t type = tag & 3; > + if (type == 0) > + { > + size_t nlt = (tag >> 2) + 1; > + tag = ip[nlt]; > + ip += nlt + 1; > + } > + else > + { > + tag = ip[type]; > + ip += type + 1; > + } > + } > + return ip; > +} > + > +/* The diamond is if-converted (branchless): one selected-offset load > remains. */ > +/* { dg-final { scan-tree-dump "If-converted diamond" "sink1" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-3.c > b/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-3.c > new file mode 100644 > index 00000000000..95877bb71f4 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-3.c > @@ -0,0 +1,49 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fstrict-aliasing -fdump-tree-sink1-details" } */ > + > +/* PR tree-optimization/125557. Alias-type merging in > factor_out_conditional_load. > + > + Same data-dependent load-address recurrence as scc-diamond-1.c, but the > two > + arms read the next tag through pointers with *different* TBAA alias > types: a > + plain "const unsigned char" load in one arm and a may_alias load in the > other. > + The two MEM_REFs have the same value type (unsigned char) but different > + operand-1 (alias-ptr) types. Rather than refusing to common loads with > + mismatched alias types, factor_out_conditional_load merges them the way > + get_alias_type_for_stmts does: since the types are incompatible the > combined > + load is given ptr_type_node (the alias-everything type) and the dependence > + clique/base are dropped, so it conservatively conflicts with any store > either > + original arm could. The two conditional loads are therefore commoned > into a > + single reg-offset load and the diamond is if-converted. */ > + > +#include <stddef.h> > +#include <stdint.h> > + > +typedef uint8_t alias_u8 __attribute__((may_alias)); > + > +const uint8_t * > +advance (const uint8_t *ip, size_t tag, const uint8_t *end) > +{ > + while (ip < end) > + { > + size_t type = tag & 3; > + if (type == 0) > + { > + size_t nlt = (tag >> 2) + 1; > + /* Plain alias type: operand-1 type is "const unsigned char *". */ > + tag = ip[nlt]; > + ip += nlt + 1; > + } > + else > + { > + /* may_alias: operand-1 type is the alias-everything pointer. Same > + value type (unsigned char), different operand-1 type. */ > + tag = *(const alias_u8 *) (ip + type); > + ip += type + 1; > + } > + } > + return ip; > +} > + > +/* The mismatched alias types are merged to the alias-everything type, so the > + loads are commoned and the diamond is if-converted. */ > +/* { dg-final { scan-tree-dump "If-converted diamond" "sink1" } } */ > diff --git a/gcc/testsuite/gcc.target/aarch64/scc-diamond-2.c > b/gcc/testsuite/gcc.target/aarch64/scc-diamond-2.c > new file mode 100644 > index 00000000000..8911f4e6a3f > --- /dev/null > +++ b/gcc/testsuite/gcc.target/aarch64/scc-diamond-2.c > @@ -0,0 +1,30 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -march=armv8.2-a+sve -fdump-tree-sink1-details > -fdump-tree-vect-details" } */ > + > +/* Counterpart to scc-diamond-1.c, showing why > sink_common_computations_to_bb is > + guarded by a recurrence check. The conditional loads a[i] / b[i] are > affine > + in the induction variable and do NOT depend on any loaded value -- there > is > + no recurrence, and the loop vectorises (masked/blended contiguous loads). > + If the diamond were if-converted into one selected-address load it would > + become a gather and lose the cheap contiguous vectorisation, so the guard > + must leave this loop alone. */ > + > +void > +f (int *__restrict r, const int *__restrict a, const int *__restrict b, > + const int *__restrict c, int n) > +{ > + for (int i = 0; i < n; i++) > + { > + int x; > + if (c[i]) > + x = a[i]; > + else > + x = b[i]; > + r[i] = x; > + } > +} > + > +/* The guard prevents if-conversion (no load-address recurrence) ... */ > +/* { dg-final { scan-tree-dump-not "If-converted diamond" "sink1" } } */ > +/* ... so the loop still vectorises with cheap contiguous loads. */ > +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */ > diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc > index b018590c378..c2cdc54f977 100644 > --- a/gcc/tree-ssa-phiopt.cc > +++ b/gcc/tree-ssa-phiopt.cc > @@ -554,7 +554,7 @@ factor_out_conditional_load (edge e0, edge e1, > basic_block merge, gphi *phi) > to the result of PHI stmt. COND_STMT is the controlling predicate. > Return true if the operation was factored out; false otherwise. */ > > -static bool > +bool > factor_out_conditional_operation (edge e0, edge e1, basic_block merge, > gphi *phi, gimple *cond_stmt, > bool early_p) > diff --git a/gcc/tree-ssa-phiopt.h b/gcc/tree-ssa-phiopt.h > index 3bebcee6fb4..7383095f5a5 100644 > --- a/gcc/tree-ssa-phiopt.h > +++ b/gcc/tree-ssa-phiopt.h > @@ -30,4 +30,9 @@ extern bool conditional_load_factorable_p (edge e0, edge > e1, basic_block merge, > result = *P'. */ > extern bool factor_out_conditional_load (edge e0, edge e1, basic_block merge, > gphi *phi); > +/* Factor a common operation (unary, conversion, or N-ary with one differing > + operand) out of a 2-argument PHI. */ > +extern bool factor_out_conditional_operation (edge e0, edge e1, > + basic_block merge, gphi *phi, > + gimple *cond_stmt, bool early_p); > #endif > diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc > index 2c6cad2687c..bc739ce6ea1 100644 > --- a/gcc/tree-ssa-sink.cc > +++ b/gcc/tree-ssa-sink.cc > @@ -37,6 +37,11 @@ along with GCC; see the file COPYING3. If not see > #include "tree-eh.h" > #include "tree-ssa-live.h" > #include "tree-dfa.h" > +#include "hash-map.h" > +#include "gimple-match.h" > +#include "tree-ssa-phiopt.h" > +#include "tree-ssa-dce.h" > +#include "gimple-fold.h" > > /* TODO: > 1. Sinking store only using scalar promotion (IE without moving the RHS): > @@ -513,6 +518,368 @@ statement_sink_location (gimple *stmt, basic_block > frombb, > return true; > } > > +/* If-convert a data-dependent load diamond into a single reg-offset load. > + At a diamond merge the conditional load (and the operations feeding its > + address) are commoned by reusing phi-opt's factoring helpers: > + factor_out_conditional_load turns PHI <*P, *Q> into a selected-pointer > load, > + then factor_out_conditional_operation pulls the common operations out, > + leaving one PHI selecting the differing offset. > + scc_try_ifconvert then removes the branch (branchless selects + a single > + reg-offset load). scc_recurrence_p guards it so it only fires on > + non-vectorisable load-address recurrences (e.g. a tag-byte pointer > + chase) and leaves affine, vectorisable loops alone. Run at the early > sink, > + after phi-prop so phi-prop cannot undo it. > + > + Having commoned a load in the clean if/else diamond HEAD -> {ARM0,ARM1} -> > + JOIN (E0/E1 the arm->join edges), finish branchlessly: DCE the now-dead > arm > + loads, hoist the remaining pure arm arithmetic into HEAD, and turn every > + JOIN PHI into a COND_EXPR select -- removing the data-dependent branch > (the > + actual win; merely commoning the load while keeping the branch regresses). > + Only reached for load-commoned diamonds, cfg-cleanup later folds the > emptied > + diamond. */ > +static bool > +scc_try_ifconvert (basic_block head, basic_block arm0, basic_block arm1, > + basic_block join, edge e0, edge e1) > +{ > + gimple_stmt_iterator gl = gsi_last_nondebug_bb (head); > + if (gsi_end_p (gl)) > + return false; > + gcond *cond = dyn_cast<gcond *> (gsi_stmt (gl)); > + if (!cond || gimple_has_volatile_ops (cond)) > + return false; > + > + /* The COND_EXPR select rewrite below cannot represent a virtual PHI. Bail > + out now -- before any DCE, hoisting or insertion -- if the merge carries > + one, rather than partway through the rewrite, which would leave the > + diamond half if-converted. */ > + for (gphi_iterator gpi = gsi_start_phis (join); !gsi_end_p (gpi); > + gsi_next (&gpi)) > + if (virtual_operand_p (gimple_phi_result (gpi.phi ()))) > + return false; > + > + /* DCE the arms to drop the loads/addresses we just commoned away: seed > every > + arm assignment and let simple_dce_from_worklist remove the dead ones, > and > + their now-dead operands, transitively. */ > + basic_block arms[2] = {arm0, arm1}; > + auto_bitmap dce_worklist; > + for (int i = 0; i < 2; i++) > + for (gimple_stmt_iterator gi = gsi_start_bb (arms[i]); !gsi_end_p (gi); > + gsi_next (&gi)) > + { > + gimple *s = gsi_stmt (gi); > + if (is_gimple_assign (s) > + && TREE_CODE (gimple_assign_lhs (s)) == SSA_NAME) > + bitmap_set_bit (dce_worklist, > + SSA_NAME_VERSION (gimple_assign_lhs (s))); > + } > + simple_dce_from_worklist (dce_worklist); > + > + /* Both arms must now be pure scalar computation we can speculate. */ > + for (int i = 0; i < 2; i++) > + { > + if (!gimple_seq_empty_p (phi_nodes (arms[i]))) > + return false; > + for (gimple_stmt_iterator gi = gsi_start_bb (arms[i]); !gsi_end_p (gi); > + gsi_next (&gi)) > + { > + gimple *s = gsi_stmt (gi); > + if (is_gimple_debug (s)) > + continue; > + if (!is_gimple_assign (s) || gimple_vuse (s) || gimple_vdef (s) > + || gimple_has_side_effects (s) || gimple_could_trap_p (s) > + || TREE_CODE (gimple_assign_lhs (s)) != SSA_NAME) > + return false; > + } > + } > + > + edge te, fe; > + extract_true_false_edges_from_block (head, &te, &fe); > + edge e_then = (e0->src == te->dest) ? e0 : e1; > + edge e_else = (e_then == e0) ? e1 : e0; > + > + /* Hoist the pure arm statements into HEAD ahead of the branch. */ > + gimple_stmt_iterator dst = gsi_for_stmt (cond); > + for (int i = 0; i < 2; i++) > + for (gimple_stmt_iterator gi = gsi_start_bb (arms[i]); !gsi_end_p (gi);) > + { > + gimple *s = gsi_stmt (gi); > + if (is_gimple_debug (s)) > + { > + gsi_next (&gi); > + continue; > + } > + gsi_move_before (&gi, &dst); > + reset_flow_sensitive_info (gimple_assign_lhs (s)); > + } > + > + /* Materialise the condition as a boolean, then a select per JOIN PHI, > built > + into one sequence with gimple_build and inserted before the branch. */ > + gimple_seq seq = NULL; > + tree ct = gimple_build (&seq, gimple_cond_code (cond), boolean_type_node, > + gimple_cond_lhs (cond), gimple_cond_rhs (cond)); > + auto_vec<gphi *, 8> phis; > + auto_vec<tree, 8> sels; > + for (gphi_iterator gpi = gsi_start_phis (join); !gsi_end_p (gpi); > + gsi_next (&gpi)) > + { > + gphi *phi = gpi.phi (); > + tree res = gimple_phi_result (phi); > + tree s = gimple_build (&seq, COND_EXPR, TREE_TYPE (res), ct, > + PHI_ARG_DEF_FROM_EDGE (phi, e_then), > + PHI_ARG_DEF_FROM_EDGE (phi, e_else)); > + phis.safe_push (phi); > + sels.safe_push (s); > + } > + dst = gsi_for_stmt (cond); > + gsi_insert_seq_before (&dst, seq, GSI_SAME_STMT); > + for (unsigned i = 0; i < phis.length (); i++) > + { > + replace_uses_by (gimple_phi_result (phis[i]), sels[i]); > + gphi_iterator gp = gsi_for_phi (phis[i]); > + remove_phi_node (&gp, false); > + } > + statistics_counter_event (cfun, "diamond load if-converted to selects", 1); > + if (dump_file && (dump_flags & TDF_DETAILS)) > + fprintf (dump_file, "If-converted diamond head bb%d (branchless)\n", > + head->index); > + return true; > +} > + > +/* Vectorisation guard. Walk the dependences of START backwards within LOOP, > + following SSA defs and (for loop-header PHIs) the value coming round the > + latch, and return true if we reach TARGET -- i.e. START depends on TARGET > + around the loop. Used with START = the diamond's loaded arm value and > + TARGET = the load-PHI result to detect a data-dependent load-address > + recurrence (in a pointer chase): such loops cannot vectorise, so > + if-converting them is free; affine loops lack the recurrence and > + are left alone so they still vectorise. */ > +static bool > +scc_recurrence_p (tree start, tree target, class loop *loop) > +{ > + auto_vec<tree, 32> wl; > + hash_set<tree> seen; > + wl.safe_push (start); > + /* SEEN already bounds the walk to the loop's distinct SSA names; this > + adjustable cap (--param=sink-diamond-recurrence-limit) additionally > bounds > + compile time on pathological functions. */ > + int budget = param_sink_diamond_recurrence_limit; > + while (!wl.is_empty () && budget-- > 0) > + { > + tree t = wl.pop (); > + if (t == target) > + return true; > + if (TREE_CODE (t) != SSA_NAME || seen.add (t)) > + continue; > + gimple *def = SSA_NAME_DEF_STMT (t); > + basic_block dbb = gimple_bb (def); > + if (!dbb || !flow_bb_inside_loop_p (loop, dbb)) > + continue; > + if (gphi *phi = dyn_cast<gphi *> (def)) > + { > + class loop *dl = dbb->loop_father; > + if (dbb == dl->header) > + { > + tree larg = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (dl)); > + if (larg) > + wl.safe_push (larg); > + } > + else > + for (unsigned i = 0; i < gimple_phi_num_args (phi); i++) > + wl.safe_push (gimple_phi_arg_def (phi, i)); > + } > + else if (is_gimple_assign (def)) > + { > + ssa_op_iter it; > + tree op; > + FOR_EACH_SSA_TREE_OPERAND (op, def, it, SSA_OP_USE) > + wl.safe_push (op); > + } > + } > + return false; > +} > + > +/* Return true if both ARM0/ARM1 reduce to pure, speculatable scalar once the > + conditional load(s) are commoned, so the branchless if-conversion is > + guaranteed to succeed. Every load must be single-use and feed a merge PHI > + that selects between two single-use loads (PHI <*P, *Q>) -- commoning then > + replaces it by one load of the selected pointer, which is safe -- and > every > + other statement must be pure non-trapping scalar that the if-conversion > can > + speculate. Gating on this avoids commoning a diamond we cannot then make > + branchless (commoning while leaving the branch in place is not > profitable). */ > +static bool > +scc_arms_speculatable_p (basic_block bb, basic_block arm0, basic_block arm1, > + edge e0, edge e1) > +{ > + basic_block arms[2] = { arm0, arm1 }; > + for (int k = 0; k < 2; k++) > + for (gimple_stmt_iterator gi = gsi_start_bb (arms[k]); !gsi_end_p (gi); > + gsi_next (&gi)) > + { > + gimple *s = gsi_stmt (gi); > + if (is_gimple_debug (s)) > + continue; > + if (gimple_code (s) == GIMPLE_PHI || !is_gimple_assign (s) > + || gimple_vdef (s)) > + return false; > + if (gimple_vuse (s)) > + { > + /* A load: only admissible if it feeds a merge PHI that > + factor_out_conditional_load will actually common away. Use that > + helper's own eligibility test -- a load it would not common (e.g. > + a non-zero-offset field access) must reject the diamond here, or > it > + survives to scc_try_ifconvert and aborts the if-conversion after > the > + irreversible commoning. */ > + tree lhs = gimple_assign_lhs (s); > + use_operand_p use_p; > + gimple *use_stmt; > + if (TREE_CODE (lhs) != SSA_NAME > + || !single_imm_use (lhs, &use_p, &use_stmt) > + || gimple_code (use_stmt) != GIMPLE_PHI > + || gimple_bb (use_stmt) != bb > + || !conditional_load_factorable_p (e0, e1, bb, > + as_a<gphi *> (use_stmt))) > + return false; > + continue; > + } > + /* Pure scalar -- it will be speculated (hoisted), so it must be a plain > + non-trapping SSA assignment with no side effects, matching the > re-check > + scc_try_ifconvert applies once the loads are commoned away. */ > + if (TREE_CODE (gimple_assign_lhs (s)) != SSA_NAME > + || gimple_has_side_effects (s) > + || gimple_could_trap_p (s)) > + return false; > + } > + return true; > +} > + > +/* If-convert a data-dependent load diamond merging into BB. */ > +static bool > +sink_common_computations_to_bb (basic_block bb) > +{ > + if (EDGE_COUNT (bb->preds) != 2) > + return false; > + edge e0 = EDGE_PRED (bb, 0); > + edge e1 = EDGE_PRED (bb, 1); > + basic_block arm0 = e0->src; > + basic_block arm1 = e1->src; > + /* Require a clean if/else diamond: each arm is a single block whose only > + predecessor is the branch block and whose only successor is the merge. > + Removing the data-dependent branch is the actual win, so there is no > point > + commoning the load unless the branchless if-conversion below can run -- > + commoning while leaving the branch in place is not profitable. */ > + if (arm0 == arm1 > + || !single_pred_p (arm0) || !single_succ_p (arm0) > + || !single_pred_p (arm1) || !single_succ_p (arm1) > + || single_pred (arm0) != single_pred (arm1)) > + return false; > + basic_block head = single_pred (arm0); > + > + /* No stores in the arms: the factored load must read an unchanged memory > + state. */ > + basic_block arms[2] = { arm0, arm1 }; > + for (int k = 0; k < 2; k++) > + for (gimple_stmt_iterator gi = gsi_start_bb (arms[k]); !gsi_end_p (gi); > + gsi_next (&gi)) > + if (gimple_vdef (gsi_stmt (gi)) || is_gimple_call (gsi_stmt (gi))) > + return false; > + > + /* Find a load PHI -- PHI <*P, *Q> whose two arguments are single-use > loads -- > + to drive the vectorisation guard. */ > + gphi *loadphi = NULL; > + for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); gsi_next > (&gpi)) > + { > + gphi *phi = gpi.phi (); > + if (virtual_operand_p (gimple_phi_result (phi)) > + || gimple_phi_num_args (phi) != 2) > + continue; > + tree a0 = PHI_ARG_DEF_FROM_EDGE (phi, e0); > + tree a1 = PHI_ARG_DEF_FROM_EDGE (phi, e1); > + if (TREE_CODE (a0) != SSA_NAME || TREE_CODE (a1) != SSA_NAME > + || !has_single_use (a0) || !has_single_use (a1)) > + continue; > + gimple *d0 = SSA_NAME_DEF_STMT (a0); > + gimple *d1 = SSA_NAME_DEF_STMT (a1); > + if (is_gimple_assign (d0) && gimple_assign_load_p (d0) > + && is_gimple_assign (d1) && gimple_assign_load_p (d1)) > + { > + loadphi = phi; > + break; > + } > + } > + if (!loadphi) > + return false; > + > + /* If-convert the diamond when doing so cannot harm vectorisation. Outside > + any loop (bb_loop_depth == 0) there is nothing to vectorise, so always > do > + it. Inside a loop, restrict to a data-dependent load-address > recurrence: > + the loaded value feeding its own address around the loop (a pointer > chase) > + already blocks vectorisation, so removing the branch is free; affine > + vectorisable loops are left untouched. */ > + class loop *loop = bb->loop_father; > + tree larg0 = PHI_ARG_DEF_FROM_EDGE (loadphi, e0); > + tree larg1 = PHI_ARG_DEF_FROM_EDGE (loadphi, e1); > + tree lres = gimple_phi_result (loadphi); > + if (bb_loop_depth (bb) != 0 > + && !scc_recurrence_p (larg0, lres, loop) > + && !scc_recurrence_p (larg1, lres, loop)) > + return false; > + > + gimple_stmt_iterator gl = gsi_last_nondebug_bb (head); > + if (gsi_end_p (gl) || gimple_code (gsi_stmt (gl)) != GIMPLE_COND) > + return false; > + gimple *cond_stmt = gsi_stmt (gl); > + > + /* The branchless finish (scc_try_ifconvert, below) is not rolled back, so > + only common when it is guaranteed to succeed: scc_try_ifconvert cannot > + if-convert a volatile condition or rewrite a virtual PHI at the merge > into > + a select, and needs both arms to reduce to pure speculatable scalar. > Check > + all three up front (scc_arms_speculatable_p also covers > scc_try_ifconvert's > + post-DCE re-check, since DCE only removes statements), and assert its > + success below -- by then the load is already commoned, so a failure > would > + be an unrecoverable invariant violation, not a no-op. */ > + if (gimple_has_volatile_ops (cond_stmt)) > + return false; > + for (gphi_iterator vpi = gsi_start_phis (bb); !gsi_end_p (vpi); gsi_next > (&vpi)) > + if (virtual_operand_p (gimple_phi_result (vpi.phi ()))) > + return false; > + if (!scc_arms_speculatable_p (bb, arm0, arm1, e0, e1)) > + return false; > + > + /* Common the conditional load and the operations feeding its address by > + iterating phi-opt's factoring helpers (load -> selected-pointer load, > then > + operand factoring) until nothing more factors, mirroring phi-opt's > loop. */ > + bool any = false, changed = true; > + while (changed) > + { > + changed = false; > + for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);) > + { > + gphi *phi = gpi.phi (); > + if (factor_out_conditional_load (e0, e1, bb, phi) > + || factor_out_conditional_operation (e0, e1, bb, phi, > + cond_stmt, /*early_p=*/true)) > + { > + changed = any = true; > + break; > + } > + gsi_next (&gpi); > + } > + } > + if (!any) > + return false; > + if (dump_file && (dump_flags & TDF_DETAILS)) > + fprintf (dump_file, "Commoned diamond computations into bb %d\n", > bb->index); > + > + /* Having commoned the load(s) to one reg-offset load, finish branchlessly: > + removing the data-dependent branch is the actual win -- commoning alone > + (keeping the branch) regresses. The up-front gate guarantees this > + succeeds, and the load is already commoned. */ > + bool ok = scc_try_ifconvert (head, arm0, arm1, bb, e0, e1); > + gcc_assert (ok); > + > + return true; > +} > + > /* Very simplistic code to sink common stores from the predecessor through > our virtual PHI. We do this before sinking stmts from BB as it might > expose sinking opportunities of the merged stores. > @@ -878,6 +1245,13 @@ pass_sink_code::execute (function *fun) > > int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); > int n = inverted_rev_post_order_compute (fun, rpo); > + /* Run the diamond-commoning at the EARLY sink (sink1, > unsplit_edges==false): > + before the loop optimizers (ivopts/reassoc) so they can fold the sunk > + load into the addressing/recurrence -- the late sink2 is too late. */ > + if (!unsplit_edges) > + for (int i = 0; i < n; ++i) > + if (sink_common_computations_to_bb (BASIC_BLOCK_FOR_FN (fun, rpo[i]))) > + todo |= TODO_cleanup_cfg; As said on the other patch, sink_common_stores_to_bb is possibly an enabler for this, so why do you not do this from inside sink_code_in_bb? > for (int i = 0; i < n; ++i) > todo |= sink_code_in_bb (BASIC_BLOCK_FOR_FN (fun, rpo[i]), vop_live); > free (rpo); > -- Richard Biener <[email protected]> SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Jochen Jaser, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
