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. factor_out_conditional_load commons the two arm loads into
one load of a run-time-selected pointer (P' = PHI <P, Q>; *P'),
factor_out_conditional_operation (reused from phi-opt) then sinks the address
arithmetic into the merge so the select lands on the offset and folds into the
reg-offset load, and scc_try_ifconvert removes the data-dependent branch. The
transform fires only on a genuine load diamond (where a load is actually
factorable), leaving pure operation/value diamonds to phi-opt as before.
This is the dual of sink_common_stores_to_bb, so it lives in the sink pass and
is invoked from sink_code_in_bb right beside the store sinking. No speculative
load is introduced (the merged load reads through whichever pointer the taken
edge selected), and the load is commoned only when both arms reduce to pure
speculatable scalar (scc_arms_speculatable_p), so the branchless finish always
succeeds; no commoned-but-still-branching diamond is ever left behind.
The transform is gated so it cannot harm vectorisation: outside any loop it
always fires (there is nothing to vectorise); inside a loop it fires only at the
last fold (fold_before_rtl_expansion_p), after the vectorisers have run, so
affine vectorisable loops are vectorised first and left alone. This avoids
regressing 772.marian_r in SPEC2026, whose vectorised code is unchanged.
With this patch the Snappy hot loop gets if-converted optimally and
decompression (UFlatMedley) 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
* tree-ssa-phiopt.cc (factor_out_conditional_operation): No longer
static.
* tree-ssa-phiopt.h: New file.
* tree-ssa-sink.cc: Include tree-ssa-dce.h, gimple-fold.h, alias.h,
builtins.h and tree-ssa-phiopt.h.
(remove_factored_arm_defs, conditional_load_factorable_p,
factor_out_conditional_load, scc_try_ifconvert, scc_arms_speculatable_p,
sink_common_computations_to_bb): New.
(sink_code_in_bb): Call sink_common_computations_to_bb.
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.dg/tree-ssa/scc-diamond-4.c: New test.
* gcc.target/aarch64/scc-diamond-2.c: New test.
---
gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-1.c | 38 ++
gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-3.c | 49 ++
gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-4.c | 23 +
.../gcc.target/aarch64/scc-diamond-2.c | 32 ++
gcc/tree-ssa-phiopt.cc | 2 +-
gcc/tree-ssa-phiopt.h | 27 ++
gcc/tree-ssa-sink.cc | 437 ++++++++++++++++++
7 files changed, 607 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.dg/tree-ssa/scc-diamond-4.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/scc-diamond-2.c
create mode 100644 gcc/tree-ssa-phiopt.h
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..4494cbadcf2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-1.c
@@ -0,0 +1,38 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sink2-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. In a loop this fires only at the late sink, after the
+ vectorisers have run (gated on fold_before_rtl_expansion_p), so a
+ vectorisable loop is vectorised first and left alone. */
+
+#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" "sink2" } } */
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..231380fe294
--- /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-sink2-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" "sink2" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-4.c
b/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-4.c
new file mode 100644
index 00000000000..d5b057f50cb
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-4.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sink1-details" } */
+
+/* PR tree-optimization/125557: outside any loop, a diamond that selects
between
+ two loads PHI <*p, *q> is if-converted by the sink pass
+ (sink_common_computations_to_bb): the two conditional loads are commoned
into
+ a single load of a run-time-selected pointer and the branch is removed. Out
+ of any loop there is nothing to vectorise, so this fires already at the
early
+ sink. */
+
+int
+f (int *p, int *q, int c)
+{
+ int x;
+ if (c)
+ x = *p;
+ else
+ x = *q;
+ return x;
+}
+
+/* The two arm loads collapse to a single selected-pointer load, branchless.
*/
+/* { 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..f8282900ce9
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/scc-diamond-2.c
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -march=armv8.2-a+sve -fdump-tree-sink2-details
-fdump-tree-vect-details" } */
+
+/* Counterpart to scc-diamond-1.c, showing why sink_common_computations_to_bb
+ defers in-loop if-conversion until after vectorisation. The conditional
+ loads a[i] / b[i] are affine in the induction variable and do NOT depend on
+ any loaded value, so the loop vectorises (masked/blended contiguous loads).
+ The late-sink gate (fold_before_rtl_expansion_p) only runs after the
+ vectorisers, so the loop is vectorised first; were the diamond instead
+ if-converted into one selected-address load it would become a gather and
lose
+ the cheap contiguous vectorisation. */
+
+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 loop vectorises, so by the late sink there is no scalar diamond to
+ if-convert ... */
+/* { dg-final { scan-tree-dump-not "If-converted diamond" "sink2" } } */
+/* ... and it vectorises with cheap contiguous loads instead of a gather. */
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index 82e67dc15d7..196386abce5 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -322,7 +322,7 @@ is_factor_profitable (gimple *def_stmt, basic_block merge,
const gimple_match_op
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
new file mode 100644
index 00000000000..2ccf514e669
--- /dev/null
+++ b/gcc/tree-ssa-phiopt.h
@@ -0,0 +1,27 @@
+/* Copyright The GNU Toolchain Authors
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#ifndef TREE_SSA_PHIOPT_H
+#define TREE_SSA_PHIOPT_H
+/* Factor a common operation (unary, conversion, or N-ary with one differing
+ operand) out of a 2-argument PHI. Exported for the sink pass, which reuses
+ it to common the address computation of a factored conditional load. */
+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..7f8396896e1 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 "tree-ssa-phiopt.h"
+#include "tree-ssa-dce.h"
+#include "gimple-fold.h"
+#include "alias.h"
+#include "builtins.h"
/* TODO:
1. Sinking store only using scalar promotion (IE without moving the RHS):
@@ -513,6 +518,431 @@ statement_sink_location (gimple *stmt, basic_block frombb,
return true;
}
+/* Remove the two arm-defining load statements D0 and D1 once their results
have
+ been factored into the merge. Used only by factor_out_conditional_load
below,
+ which validates both arms as real (non-volatile, single-use) load statements
+ via conditional_load_factorable_p, so neither D0 nor D1 is ever NULL. */
+
+static void
+remove_factored_arm_defs (gimple *d0, gimple *d1)
+{
+ gimple_stmt_iterator gsi = gsi_for_stmt (d0);
+ gsi_remove (&gsi, true);
+ release_defs (d0);
+ gsi = gsi_for_stmt (d1);
+ gsi_remove (&gsi, true);
+ release_defs (d1);
+}
+
+/* Return true if factor_out_conditional_load (below) would factor the load PHI
+ at MERGE. E0/E1 are the arm->MERGE edges. Eligible when PHI is a
+ two-argument non-virtual PHI at a merge with no virtual PHI, both arguments
+ are single-use SSA loads sharing one VUSE, and each is a plain zero-offset
+ *P MEM_REF of a compatible, naturally-aligned scalar type reached through
+ compatible pointer types. This is factor_out_conditional_load's eligibility
+ test, split out so callers (the sink pass) can gate on commonability without
+ mutating: the two MUST stay in lockstep, otherwise a caller could common a
+ load the sink then cannot finish if-converting. */
+
+static bool
+conditional_load_factorable_p (edge e0, edge e1, basic_block merge, gphi *phi)
+{
+ if (virtual_operand_p (gimple_phi_result (phi))
+ || gimple_phi_num_args (phi) != 2
+ || get_virtual_phi (merge))
+ return false;
+
+ tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
+ tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
+ if (TREE_CODE (arg0) != SSA_NAME || TREE_CODE (arg1) != SSA_NAME
+ || !has_single_use (arg0) || !has_single_use (arg1))
+ return false;
+
+ gimple *d0 = SSA_NAME_DEF_STMT (arg0);
+ gimple *d1 = SSA_NAME_DEF_STMT (arg1);
+ if (!is_gimple_assign (d0) || !gimple_assign_load_p (d0)
+ || !is_gimple_assign (d1) || !gimple_assign_load_p (d1)
+ || gimple_has_volatile_ops (d0) || gimple_has_volatile_ops (d1)
+ || gimple_vuse (d0) != gimple_vuse (d1))
+ return false;
+
+ tree ref0 = gimple_assign_rhs1 (d0);
+ tree ref1 = gimple_assign_rhs1 (d1);
+ /* Both must be plain *P loads (zero offset) of a compatible value type. The
+ TBAA alias-ptr type carried by MEM_REF operand 1 need not match; it is
+ merged the way get_alias_type_for_stmts does when the load is built. */
+ if (TREE_CODE (ref0) != MEM_REF || TREE_CODE (ref1) != MEM_REF
+ || !integer_zerop (TREE_OPERAND (ref0, 1))
+ || !integer_zerop (TREE_OPERAND (ref1, 1))
+ || !types_compatible_p (TREE_TYPE (ref0), TREE_TYPE (ref1)))
+ return false;
+
+ /* The merged load selects either pointer at run time and carries no
+ pointer-alignment info, so it is built with the access type's natural
+ alignment. Refuse to factor when an arm is less aligned than that (e.g. a
+ packed/under-aligned access), so we never over-align that arm's pointer.
*/
+ unsigned int nat_align = min_align_of_type (TREE_TYPE (ref0)) *
BITS_PER_UNIT;
+ if (get_object_alignment (ref0) < nat_align
+ || get_object_alignment (ref1) < nat_align)
+ return false;
+
+ tree p0 = TREE_OPERAND (ref0, 0);
+ tree p1 = TREE_OPERAND (ref1, 0);
+ if (!types_compatible_p (TREE_TYPE (p0), TREE_TYPE (p1)))
+ return false;
+
+
+ return true;
+}
+
+/* If PHI at MERGE is a "load PHI", PHI <*P, *Q> whose two arguments are
+ single-use, non-volatile scalar MEM_REF loads reading the same memory state
+ (same VUSE), factor the load out: introduce P' = PHI <P, Q> and a single
+ load *P' replacing the PHI. No speculative load is introduced (the load
uses
+ whichever pointer the taken edge selected). Together with operand factoring
+ this leaves a single load in place of the diamond's two. E0/E1 are the
+ arm->MERGE edges. Eligibility is exactly conditional_load_factorable_p
+ (above), which the sink pass also checks before committing to the branchless
+ conversion, so the two must stay in sync. Returns true if the load was
+ factored out. */
+
+static bool
+factor_out_conditional_load (edge e0, edge e1, basic_block merge, gphi *phi)
+{
+ if (!conditional_load_factorable_p (e0, e1, merge, phi))
+ return false;
+
+ /* Re-derive the loads and pointers validated by the predicate above. */
+ gimple *d0 = SSA_NAME_DEF_STMT (gimple_phi_arg_def (phi, e0->dest_idx));
+ gimple *d1 = SSA_NAME_DEF_STMT (gimple_phi_arg_def (phi, e1->dest_idx));
+ tree ref0 = gimple_assign_rhs1 (d0);
+ tree ref1 = gimple_assign_rhs1 (d1);
+ tree p0 = TREE_OPERAND (ref0, 0);
+ tree p1 = TREE_OPERAND (ref1, 0);
+
+ /* Build P' = PHI <P, Q> and the single load result = *P'. */
+ tree res = gimple_phi_result (phi);
+ tree ptr = make_ssa_name (TREE_TYPE (p0));
+ gphi *pphi = create_phi_node (ptr, merge);
+ add_phi_arg (pphi, p0, e0, gimple_phi_arg_location (phi, e0->dest_idx));
+ add_phi_arg (pphi, p1, e1, gimple_phi_arg_location (phi, e1->dest_idx));
+
+ /* Merge the two arms' TBAA info as get_alias_type_for_stmts does: keep the
+ common alias-ptr type and dependence clique/base when the arms agree,
+ otherwise fall back to ptr_type_node (alias-everything) and drop the
+ clique/base, so the combined load conservatively conflicts with any store
+ either original arm could. */
+ unsigned short clique = MR_DEPENDENCE_CLIQUE (ref0);
+ unsigned short base = MR_DEPENDENCE_BASE (ref0);
+ if (clique != MR_DEPENDENCE_CLIQUE (ref1) || base != MR_DEPENDENCE_BASE
(ref1))
+ clique = base = 0;
+ tree atype = TREE_TYPE (TREE_OPERAND (ref0, 1));
+ if (!alias_ptr_types_compatible_p (atype, TREE_TYPE (TREE_OPERAND (ref1,
1))))
+ {
+ atype = ptr_type_node;
+ clique = base = 0;
+ }
+
+ /* Build the combined load RES = *PTR, reusing the PHI result so any range
+ info on it is preserved (as factor_out_conditional_operation does). */
+ tree nref = build2 (MEM_REF, TREE_TYPE (ref0), ptr, build_int_cst (atype,
0));
+ MR_DEPENDENCE_CLIQUE (nref) = clique;
+ MR_DEPENDENCE_BASE (nref) = base;
+ gassign *load = gimple_build_assign (res, nref);
+ gimple_set_vuse (load, gimple_vuse (d0));
+ gimple_stmt_iterator gsi = gsi_after_labels (merge);
+ gsi_insert_before (&gsi, load, GSI_SAME_STMT);
+
+ /* RES is now defined by the load; drop the original PHI. */
+ gsi = gsi_for_stmt (phi);
+ gsi_remove (&gsi, true);
+
+ /* The two arm loads are now dead. */
+ remove_factored_arm_defs (d0, d1);
+
+ statistics_counter_event (cfun, "factored load out of COND_EXPR", 1);
+ return true;
+}
+
+/* If-convert a data-dependent load diamond into a single unconditional 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 with branchless selects.
+ The transform is gated so it cannot harm vectorisation:
+ outside any loop it always fires, and inside a loop only at the last fold
+ (fold_before_rtl_expansion_p), after the vectorisers have run, so affine
+ vectorisable loops are vectorised first and left alone.
+
+ 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. The branch
+ condition's operands are computed in HEAD and dominate both arms, and a
+ GIMPLE_COND defines no SSA name, so an arm statement can only reference
+ values that already dominate this point; hoisting keeps them valid. */
+ 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;
+}
+
+/* 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. 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-convert the diamond only where it cannot harm vectorisation: outside
+ any loop (bb_loop_depth == 0) there is nothing to vectorise; inside a
+ loop, defer to the last fold (fold_before_rtl_expansion_p, after the
+ vectorisers have run), so commoning the load and removing the branch can
+ no longer prevent vectorisation. */
+ if (bb_loop_depth (bb) != 0 && !fold_before_rtl_expansion_p ())
+ return false;
+ 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);
+
+ 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);
+ if (gimple_has_volatile_ops (cond_stmt))
+ return false;
+
+ /* Only act on a genuine load diamond: require a conditional load that
+ factor_out_conditional_load can common (PHI <*P, *Q>). Pure operation or
+ value diamonds are left to phi-opt, which handles them later without the
+ sink pre-empting its straightline-conversion or uninit-location
bookkeeping.
+ conditional_load_factorable_p also rejects a virtual PHI at the merge, so
a
+ match guarantees scc_try_ifconvert can rewrite every merge PHI. */
+ bool has_load = false;
+ for (gphi_iterator lpi = gsi_start_phis (bb);
+ !gsi_end_p (lpi) && !has_load; gsi_next (&lpi))
+ has_load = conditional_load_factorable_p (e0, e1, bb, lpi.phi ());
+ if (!has_load)
+ return false;
+
+ /* The branchless finish (scc_try_ifconvert, below) is not rolled back, so
+ common only when it is guaranteed to succeed: it needs both arms to reduce
+ to pure speculatable scalar. scc_arms_speculatable_p, which walks the arm
+ bodies last, also rejects any store or call (so the factored load reads an
+ unchanged memory state) and covers scc_try_ifconvert's post-DCE re-check
+ (DCE only removes statements). Its success is asserted below; by then the
+ load is already commoned, so a failure would be an unrecoverable invariant
+ violation, not a no-op. */
+ 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 conditional load(s), finish branchlessly: removing the
+ data-dependent branch is the actual win; commoning the load while leaving
+ the branch in place is not profitable. 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.
@@ -699,6 +1129,13 @@ sink_code_in_bb (basic_block bb, virtual_operand_live
&vop_live)
/* Sink common stores from the predecessor through our virtual PHI. */
todo |= sink_common_stores_to_bb (bb);
+ /* If-convert a data-dependent load diamond merging into BB, the dual of
+ the common-store sinking above. In a loop this self-gates on
+ fold_before_rtl_expansion_p, so it only fires after the vectorisers; out
+ of any loop it always fires. */
+ if (sink_common_computations_to_bb (bb))
+ todo |= TODO_cleanup_cfg;
+
/* If this block doesn't dominate anything, there can't be any place to sink
the statements to. */
if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
--
2.50.1 (Apple Git-155)
