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.
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;
for (int i = 0; i < n; ++i)
todo |= sink_code_in_bb (BASIC_BLOCK_FOR_FN (fun, rpo[i]), vop_live);
free (rpo);
--
2.50.1 (Apple Git-155)
