This is a simplified version that I was mentioning.
It is based on https://gcc.gnu.org/pipermail/gcc-patches/2026-June/720170.html
but only handing in phi-opt. It is able to optimize
what is requested and will not have the regression dealing
with vectorization. There are some more tweaks we can do
to handle some more stuff.
Like before vectorization, if the two pointers are the same we should do
the factoring. Or handling stores before the load which will allow
us to iterate better with cs-elim limited. We can also tweak the
before vectorization cost to be rather based on if it just inside
a loop into what was done in the full patch. For the benchmark improvement
that was not needed.
PR tree-optimization/125557
gcc/ChangeLog:
* tree-ssa-phiopt.cc (factor_out_conditional_load): New function.
(factor_out_all): Call factor_out_conditional_load.
gcc/testsuite/ChangeLog:
* 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.
Co-Authored-by: Kyrylo Tkachov <[email protected]>
Signed-off-by: Kyrylo Tkachov <[email protected]>
Signed-off-by: Andrew Pinski <[email protected]>
---
gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-1.c | 40 ++++
gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-3.c | 51 ++++++
gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-4.c | 23 +++
.../gcc.target/aarch64/scc-diamond-2.c | 34 ++++
gcc/tree-ssa-phiopt.cc | 171 +++++++++++++++++-
5 files changed, 312 insertions(+), 7 deletions(-)
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
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..de4f003bcf3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-1.c
@@ -0,0 +1,40 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-phiopt-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-times "changed to factor out load from" 1
"phiopt4" } } */
+/* { dg-final { scan-tree-dump-times "changed to factor operation out from" 1
"phiopt4" } } */
+/* { dg-final { scan-tree-dump-times "changed to factor operation out from" 2
"phiopt1" } } */
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..8f9f6a4dead
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scc-diamond-3.c
@@ -0,0 +1,51 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fstrict-aliasing -fdump-tree-phiopt-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-times "changed to factor out load from" 1
"phiopt4" } } */
+/* { dg-final { scan-tree-dump-times "changed to factor operation out from" 1
"phiopt4" } } */
+/* { dg-final { scan-tree-dump-times "changed to factor operation out from" 2
"phiopt1" } } */
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..5b22469eb80
--- /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-phiopt2-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 "changed to factor out load from COND_EXPR"
"phiopt2" } } */
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..220c3eb944c
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/scc-diamond-2.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -march=armv8.2-a+sve -fdump-tree-phiopt-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 "changed to factor out load from" "phiopt1"
} } */
+/* { dg-final { scan-tree-dump-not "changed to factor out load from" "phiopt2"
} } */
+/* { dg-final { scan-tree-dump-not "changed to factor out load from" "phiopt3"
} } */
+/* ... 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 e926aa8200d..58267281745 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -54,6 +54,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-ssa-dce.h"
#include "tree-ssa-loop-niter.h"
#include "gimple-predict.h"
+#include "alias.h"
/* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
@@ -3649,6 +3650,157 @@ cond_if_else_store_replacement (basic_block then_bb,
basic_block else_bb,
return ok;
}
+/* 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).
+ E0/E1 are the middle bbs to MERGE edges.
+ EARLY_P is set when the first phiopt is run.
+ BEFORE_VECT is true if this is before vectorization, where some extra checks
+ are needed for profitability.
+ Returns true if a load was factored out. */
+
+static bool
+factor_out_conditional_load (edge e0, edge e1, basic_block merge, gphi *phi,
+ bool early_p, bool before_vect)
+{
+ /* Factoring out a load during the first phi means we can't
+ trust if this is inside a loop or not; due to before inlining. */
+ if (early_p)
+ return false;
+
+ /* Before vectorization, we don't want to factor out loads unless not inside
a loop. */
+ if (before_vect && bb_loop_depth (merge) != 0)
+ return false;
+
+ /* Not a virtual operand. */
+ if (virtual_operand_p (gimple_phi_result (phi))
+ /* can only handle the merge bb having 2 predecessors. */
+ || gimple_phi_num_args (phi) != 2
+ /* No calls nor stores in the middle bbs.
+ FIXME: handle the case where there are stores before the load. */
+ || 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);
+ /* The load needs to be only used in the phi. */
+ if (TREE_CODE (arg0) != SSA_NAME || TREE_CODE (arg1) != SSA_NAME
+ || !has_single_use (arg0) || !has_single_use (arg1))
+ return false;
+
+ /* Re-derive the loads and pointers validated by the predicate above. */
+ gimple *load0 = SSA_NAME_DEF_STMT (arg0);
+ gimple *load1 = SSA_NAME_DEF_STMT (arg1);
+
+ /* The load needs to be a load with NO volatile ops. */
+ if (!gimple_assign_load_p (load0) || !gimple_assign_load_p (load1)
+ || gimple_has_volatile_ops (load0) || gimple_has_volatile_ops (load1)
+ /* Assert that the vuse is the same, this will be true since there
+ are no stores either bb. */
+ || gimple_vuse (load0) != gimple_vuse (load1))
+ return false;
+
+ tree ref0 = gimple_assign_rhs1 (load0);
+ tree ref1 = gimple_assign_rhs1 (load1);
+
+ /* 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 alignment of the two accesses need to be the same. */
+ if (TYPE_ALIGN (TREE_TYPE (ref0)) != TYPE_ALIGN (TREE_TYPE (ref1)))
+ return false;
+
+ tree p0 = TREE_OPERAND (ref0, 0);
+ tree p1 = TREE_OPERAND (ref1, 0);
+
+ tree newptr;
+ if (p0 != p1)
+ {
+ /* We can't factor out a non-ssa named based load
+ as it might cause a variable not taken an
+ address to become needing the address taken.
+ An example is in go.
+ Were we produce:
+ _24 = PHI <&crypto/tls.cipherSuitesPreferenceOrder(36),
&crypto/tls.cipherSuitesPreferenceOrderNoAES(37)>
+ And &crypto/tls.cipherSuitesPreferenceOrder address bit was not set.
+ FIXME: Refine to check ADDRESSABLE bit. */
+ if (TREE_CODE (p0) != SSA_NAME || TREE_CODE (p1) != SSA_NAME)
+ return false;
+ /* Build P' = PHI <P, Q> and the single load result = *P'. */
+ newptr = make_ssa_name (TREE_TYPE (p0));
+ gphi *pphi = create_phi_node (newptr, 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));
+ }
+ else
+ newptr = p0;
+
+ /* 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), newptr, build_int_cst (atype,
0));
+ MR_DEPENDENCE_CLIQUE (nref) = clique;
+ MR_DEPENDENCE_BASE (nref) = base;
+ tree res = gimple_phi_result (phi);
+ gassign *load = gimple_build_assign (res, nref);
+ gimple_set_vuse (load, gimple_vuse (load0));
+ 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. */
+ gsi = gsi_for_stmt (load0);
+ gsi_remove (&gsi, true);
+ release_defs (load0);
+ gsi = gsi_for_stmt (load1);
+ gsi_remove (&gsi, true);
+ release_defs (load1);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "PHI ");
+ print_generic_expr (dump_file, res);
+ fprintf (dump_file,
+ " changed to factor out load from COND_EXPR.\n");
+ if (p0 != p1)
+ {
+ fprintf (dump_file, "new PHI ");
+ print_generic_expr (dump_file, newptr);
+ fprintf (dump_file,
+ " was created for the pointers.\n");
+ }
+ }
+
+ statistics_counter_event (cfun, "factored load out of COND_EXPR", 1);
+ return true;
+}
+
/* Factor out operations and stores from the phi of the MERGE block coming
in from the edges E1 and E2 if possible. COND_STMT is the conditional
statement of the origin block. DIAMOND_P says that both E1 and E2 src
@@ -3679,13 +3831,18 @@ factor_out_all (edge e1, edge e2, basic_block merge,
break;
gphi_iterator gsi;
for (gsi = gsi_start_phis (merge); !gsi_end_p (gsi); gsi_next (&gsi))
- if (factor_out_conditional_operation (e1, e2, merge, *gsi,
- cond_stmt, early_p))
- {
- changed = true;
- do_over = true;
- break;
- }
+ {
+ gphi *phi = *gsi;
+ if (factor_out_conditional_load (e1, e2, merge, phi, early_p,
+ !fold_before_rtl_expansion_p ())
+ || factor_out_conditional_operation (e1, e2, merge, phi,
+ cond_stmt, early_p))
+ {
+ changed = true;
+ do_over = true;
+ break;
+ }
+ }
} while (do_over);
return changed;
}
--
2.43.0
