On Fri, Jun 12, 2026 at 10:19 AM <[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. 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
A few comments about the sink code. That I found even after my simple patch.
> 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;
/* The alignment of the two accesses need to be the same. */
if (TYPE_ALIGN (TREE_TYPE (ref0)) != TYPE_ALIGN (TREE_TYPE (ref1)))
return false;
We can come back to getting a more decent alignment check/change later
on. This is what I used in my simple case.
> +
> + 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));
I changed d0/d1 to load0/load1 since it is easier to understand what
it refers too.
> + 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));
we can do better for the `p0 == p1` case and not create a new phi.
> +
> + /* 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);
It would be a good idea to have some kind of printing to the details
dump here on what was done.
> +
> + 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;
cond will never have volatile ops so that check is useless.
> +
> + /* 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;
Just simply this:
if (get_virtual_phi (join))
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);
So you are doing a DCE for the middle bbs? When does this show up and
why? By the time we get here things should have already been dce'd.
Also this is before commoning away things. Or you talking about
stores? I can't understand why this would show up.
> +
> + /* 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));
> + }
This is doing the exact opposite of sink. I don't think this should be
here at all.
> +
> + /* 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;
> +}
This should NOT be done in sink but rather later on in late phiopt or
isel. Also I am not sure this should be done if your target does not
have a movcc for that mode (or promoted mode).
Plus doing it in sink1 will cause some missed optimizations because we
don't optimize COND_EXPR as well.
> +
> +/* 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++)
I would factor this out into its own function and just call it with
arm0 and arm1 instead of using a for loop.
> + 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;
Why do you check GIMPLE_PHI here? PHIs better not show up in the bb's body.
Also I think it is better to do:
if (is_gimple_debug (*gi))
continue;
gassign *s = dyn_cast<gassign*>(*gi);
if (!s || gimple_vdef (s))
return false;
Note factor_out_conditional_operation does handle calls in some cases.
E.g. const internal functions. Like SQRT. Or some builtins like
sin/cos (with -fno-math-errno).
So the above check is very conserative.
> + 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
!is_a<gphi*> (use_stmt)
> + || gimple_bb (use_stmt) != bb
This check only allows the load at the end of sequence rather than in
the middle where it might also be factored out.
> + || !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)
>
