On Tue, Sep 15, 2026 at 5:37 PM <[email protected]> wrote:
>
> From: Kyrylo Tkachov <[email protected]>
>
> Loop if-conversion can emit separate comparisons for a predicate and its
> inverse. Reuse an available comparison and swap the select arms.
>
> For example, miniBUDE has this form with finite-math assumptions:
>
> p = distbb < 0.0;
> a = p ? v1 : v2;
> q = distbb >= 0.0;
> b = q ? v3 : v4;
>
> The last two statements become:
>
> b = p ? v4 : v3;
>
> Index comparisons once in block-combination order and look up the inverse
> predicate for each PHI. This avoids repeated scans of an operand's uses.
> Use invert_tree_comparison with the operand type's HONOR_NANS setting to
> preserve NaN semantics. Look up after factoring and reject deleted
> statements, since factoring can remove an indexed comparison.
There is already code to do exactly such transform:
cond = bb_predicate (first_edge->src);
cond_set.add ({ cond, 1 });
if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
std::swap (first_edge, second_edge);
So I wonder when you scan comparisons they are likely all generated
from the recorded predicates and their gimplified compoents. Would
it not be more useful to work on that representation, before those
stmts are inserted?
We also apply CSE after if-conversion, and scalar code written
as the example above would also benefit from that being able
to perform the simplification.
That said, it feels like the wrong place to optimize this.
Richard.
> On Grace, this removes one comparison and one mask copy from each hot
> Advanced SIMD loop. This improves miniBUDE 20210901 throughput by ~10%.
>
> Bootstrapped and regression tested on aarch64-unknown-linux-gnu.
>
> Ok for trunk?
> Thanks,
> Kyrill
>
> gcc/ChangeLog:
>
> * tree-if-conv.cc (comparison_key): New function.
> (lookup_inverted_predicate): Likewise.
> (predicate_scalar_phi): Add COMPARISONS parameter. Reuse an available
> inverse comparison and swap the arms of the select.
> (predicate_all_scalar_phis): Index comparisons in block-combination
> order and pass them to predicate_scalar_phi.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/ifc-cmp-inverse-1.c: New test.
> * gcc.dg/tree-ssa/ifc-cmp-inverse-2.c: New test.
> * gcc.dg/tree-ssa/ifc-cmp-inverse-3.c: New test.
> * gcc.dg/tree-ssa/ifc-cmp-inverse-4.c: New test.
> * gcc.dg/tree-ssa/ifc-cmp-inverse-5.c: New test.
>
> Signed-off-by: Kyrylo Tkachov <[email protected]>
> ---
> .../gcc.dg/tree-ssa/ifc-cmp-inverse-1.c | 35 ++++++++
> .../gcc.dg/tree-ssa/ifc-cmp-inverse-2.c | 33 ++++++++
> .../gcc.dg/tree-ssa/ifc-cmp-inverse-3.c | 34 ++++++++
> .../gcc.dg/tree-ssa/ifc-cmp-inverse-4.c | 83 +++++++++++++++++++
> .../gcc.dg/tree-ssa/ifc-cmp-inverse-5.c | 60 ++++++++++++++
> gcc/tree-if-conv.cc | 76 ++++++++++++++++-
> 6 files changed, 318 insertions(+), 3 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-1.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-2.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-3.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-4.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-5.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-1.c
> new file mode 100644
> index 00000000000..8d291d0b789
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-1.c
> @@ -0,0 +1,35 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Ofast -fdump-tree-ifcvt" } */
> +
> +/* The two merge points are predicated on DISTBB < 0 and on DISTBB >= 0.
> + With NaNs out of the way the second predicate is the inverse of the
> + first, so if-conversion has to reuse it with the arms of the select
> + swapped instead of emitting a second comparison. */
> +
> +void
> +f (float *restrict etot, const float *restrict lx, float radij, float
> r_radij,
> + float elcdst, float elcdst1, float distdslv, float r_distdslv,
> + float chrg_init, float dslv_init, int n)
> +{
> + for (int l = 0; l < n; l++)
> + {
> + float distij = lx[l];
> + float distbb = distij - radij;
> + int zone1 = distbb < 0.f;
> +
> + etot[l] += (1.f - distij * r_radij) * (zone1 ? 76.f : 0.f);
> +
> + float chrg_e = chrg_init
> + * ((zone1 ? 1.f : 1.f - distbb * elcdst1)
> + * (distbb < elcdst ? 1.f : 0.f));
> + etot[l] += chrg_e * 45.f;
> +
> + float coeff = 1.f - distbb * r_distdslv;
> + float dslv_e = dslv_init * (distbb < distdslv ? 1.f : 0.f);
> + dslv_e *= distbb >= 0.f ? coeff : 1.f;
> + etot[l] += dslv_e;
> + }
> +}
> +
> +/* { dg-final { scan-tree-dump-times {= \S+ < 0\.0;} 1 "ifcvt" } } */
> +/* { dg-final { scan-tree-dump-not {= \S+ >= 0\.0;} "ifcvt" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-2.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-2.c
> new file mode 100644
> index 00000000000..76eef5bf586
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-2.c
> @@ -0,0 +1,33 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Ofast -fno-finite-math-only -fdump-tree-ifcvt" } */
> +
> +/* Same kernel as ifc-cmp-inverse-1.c. With NaNs honoured DISTBB >= 0 is
> + not the inverse of DISTBB < 0, so both comparisons have to stay. */
> +
> +void
> +f (float *restrict etot, const float *restrict lx, float radij, float
> r_radij,
> + float elcdst, float elcdst1, float distdslv, float r_distdslv,
> + float chrg_init, float dslv_init, int n)
> +{
> + for (int l = 0; l < n; l++)
> + {
> + float distij = lx[l];
> + float distbb = distij - radij;
> + int zone1 = distbb < 0.f;
> +
> + etot[l] += (1.f - distij * r_radij) * (zone1 ? 76.f : 0.f);
> +
> + float chrg_e = chrg_init
> + * ((zone1 ? 1.f : 1.f - distbb * elcdst1)
> + * (distbb < elcdst ? 1.f : 0.f));
> + etot[l] += chrg_e * 45.f;
> +
> + float coeff = 1.f - distbb * r_distdslv;
> + float dslv_e = dslv_init * (distbb < distdslv ? 1.f : 0.f);
> + dslv_e *= distbb >= 0.f ? coeff : 1.f;
> + etot[l] += dslv_e;
> + }
> +}
> +
> +/* { dg-final { scan-tree-dump-times {= \S+ < 0\.0;} 1 "ifcvt" } } */
> +/* { dg-final { scan-tree-dump-times {= \S+ >= 0\.0;} 1 "ifcvt" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-3.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-3.c
> new file mode 100644
> index 00000000000..022aa52fd26
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-3.c
> @@ -0,0 +1,34 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Ofast -fno-finite-math-only -fdump-tree-ifcvt" } */
> +
> +/* When the source spells the second test as the arms of a select, GCC
> + builds the else predicate as DISTBB u>= 0, which is the inverse of
> + DISTBB < 0 even with NaNs honoured, so one comparison is enough. */
> +
> +void
> +f (float *restrict etot, const float *restrict lx, float radij, float
> r_radij,
> + float elcdst, float elcdst1, float distdslv, float r_distdslv,
> + float chrg_init, float dslv_init, int n)
> +{
> + for (int l = 0; l < n; l++)
> + {
> + float distij = lx[l];
> + float distbb = distij - radij;
> + int zone1 = distbb < 0.f;
> +
> + etot[l] += (1.f - distij * r_radij) * (zone1 ? 76.f : 0.f);
> +
> + float chrg_e = chrg_init
> + * ((zone1 ? 1.f : 1.f - distbb * elcdst1)
> + * (distbb < elcdst ? 1.f : 0.f));
> + etot[l] += chrg_e * 45.f;
> +
> + float coeff = 1.f - distbb * r_distdslv;
> + float dslv_e = dslv_init * (distbb < distdslv ? 1.f : 0.f);
> + dslv_e *= zone1 ? 1.f : coeff;
> + etot[l] += dslv_e;
> + }
> +}
> +
> +/* { dg-final { scan-tree-dump-times {= \S+ < 0\.0;} 1 "ifcvt" } } */
> +/* { dg-final { scan-tree-dump-not {= \S+ u>= 0\.0;} "ifcvt" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-4.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-4.c
> new file mode 100644
> index 00000000000..867a7381a96
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-4.c
> @@ -0,0 +1,83 @@
> +/* { dg-do run } */
> +/* { dg-options "-Ofast" } */
> +
> +/* Swapping the arms of a select and testing the inverse predicate has to
> + pick the same value. Every input and every intermediate value here is a
> + small integer, so the result does not depend on the order in which the
> + fast-math flags let the compiler evaluate the expression. */
> +
> +#define N 41
> +
> +static float lx[N], etot[N], ref[N];
> +
> +__attribute__ ((noipa))
> +static void
> +kernel (float *restrict etot, const float *restrict lx, float radij,
> + float r_radij, float elcdst, float elcdst1, float distdslv,
> + float r_distdslv, float chrg_init, float dslv_init, int n)
> +{
> + for (int l = 0; l < n; l++)
> + {
> + float distij = lx[l];
> + float distbb = distij - radij;
> + int zone1 = distbb < 0.f;
> +
> + etot[l] += (1.f - distij * r_radij) * (zone1 ? 76.f : 0.f);
> +
> + float chrg_e = chrg_init
> + * ((zone1 ? 1.f : 1.f - distbb * elcdst1)
> + * (distbb < elcdst ? 1.f : 0.f));
> + etot[l] += chrg_e * 45.f;
> +
> + float coeff = 1.f - distbb * r_distdslv;
> + float dslv_e = dslv_init * (distbb < distdslv ? 1.f : 0.f);
> + dslv_e *= distbb >= 0.f ? coeff : 1.f;
> + etot[l] += dslv_e;
> + }
> +}
> +
> +__attribute__ ((noipa, optimize ("O0")))
> +static void
> +reference (float *restrict etot, const float *restrict lx, float radij,
> + float r_radij, float elcdst, float elcdst1, float distdslv,
> + float r_distdslv, float chrg_init, float dslv_init, int n)
> +{
> + for (int l = 0; l < n; l++)
> + {
> + float distij = lx[l];
> + float distbb = distij - radij;
> + int zone1 = distbb < 0.f;
> +
> + etot[l] += (1.f - distij * r_radij) * (zone1 ? 76.f : 0.f);
> +
> + float chrg_e = chrg_init
> + * ((zone1 ? 1.f : 1.f - distbb * elcdst1)
> + * (distbb < elcdst ? 1.f : 0.f));
> + etot[l] += chrg_e * 45.f;
> +
> + float coeff = 1.f - distbb * r_distdslv;
> + float dslv_e = dslv_init * (distbb < distdslv ? 1.f : 0.f);
> + dslv_e *= distbb >= 0.f ? coeff : 1.f;
> + etot[l] += dslv_e;
> + }
> +}
> +
> +int
> +main (void)
> +{
> + for (int i = 0; i < N; i++)
> + {
> + lx[i] = i - N / 2;
> + etot[i] = i & 3;
> + ref[i] = etot[i];
> + }
> +
> + kernel (etot, lx, 3.f, 2.f, 5.f, 1.f, 4.f, 2.f, 3.f, 2.f, N);
> + reference (ref, lx, 3.f, 2.f, 5.f, 1.f, 4.f, 2.f, 3.f, 2.f, N);
> +
> + for (int i = 0; i < N; i++)
> + if (etot[i] != ref[i])
> + __builtin_abort ();
> +
> + return 0;
> +}
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-5.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-5.c
> new file mode 100644
> index 00000000000..2b624516c0f
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cmp-inverse-5.c
> @@ -0,0 +1,60 @@
> +/* { dg-do run } */
> +/* { dg-options "-O3 -ffast-math -fno-ssa-phiopt" } */
> +
> +/* Factoring the first select removes a comparison that can be an inverse
> + predicate for the second select. */
> +
> +__attribute__ ((noipa))
> +static void
> +kernel (float *restrict out, const float *restrict in, float z, int n)
> +{
> + for (int i = 0; i < n; ++i)
> + {
> + float x = in[i * 3];
> + float y = in[i * 3 + 1];
> + float w = in[i * 3 + 2];
> + int p;
> + if (x < 0)
> + p = y < z;
> + else
> + p = w < z;
> + out[i * 2] = p;
> + float q;
> + if (y >= z)
> + q = x * 3 + 1;
> + else
> + q = x * 2 - 1;
> + out[i * 2 + 1] = q;
> + }
> +}
> +
> +__attribute__ ((noipa, optimize ("O0")))
> +static void
> +check (const float *out, const float *in, float z, int n)
> +{
> + for (int i = 0; i < n; ++i)
> + {
> + float x = in[i * 3];
> + float y = in[i * 3 + 1];
> + float w = in[i * 3 + 2];
> + float p = x < 0 ? y < z : w < z;
> + float q = y >= z ? x * 3 + 1 : x * 2 - 1;
> + if (out[i * 2] != p || out[i * 2 + 1] != q)
> + __builtin_abort ();
> + }
> +}
> +
> +int
> +main (void)
> +{
> + float in[3 * 257], out[2 * 257];
> + for (int i = 0; i < 3 * 257; ++i)
> + in[i] = (i * 13 % 41) - 20;
> + for (int n = 0; n <= 257; ++n)
> + for (int z = -2; z <= 2; ++z)
> + {
> + kernel (out, in, z, n);
> + check (out, in, z, n);
> + }
> + return 0;
> +}
> diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc
> index fe749f94bd0..80161a2f0d9 100644
> --- a/gcc/tree-if-conv.cc
> +++ b/gcc/tree-if-conv.cc
> @@ -2093,6 +2093,46 @@ gen_simplified_condition (tree cond,
> scalar_cond_masked_set_type &cond_set)
> return cond;
> }
>
> +/* Return a canonical key for the comparison CODE of OP0 and OP1. */
> +
> +static tree
> +comparison_key (tree_code code, tree op0, tree op1)
> +{
> + if (tree_swap_operands_p (op0, op1))
> + {
> + std::swap (op0, op1);
> + code = swap_tree_comparison (code);
> + }
> + return build2 (code, boolean_type_node, op0, op1);
> +}
> +
> +/* Return an SSA name from COMPARISONS holding the inverse of COND, or
> + NULL_TREE. The caller must swap the select arms when using it. */
> +
> +static tree
> +lookup_inverted_predicate (tree cond,
> + hash_map<tree_operand_hash, gassign *>
> &comparisons)
> +{
> + tree op0, op1;
> + tree_code code = parse_predicate (cond, &op0, &op1);
> + if (code == ERROR_MARK)
> + return NULL_TREE;
> +
> + code = invert_tree_comparison (code, HONOR_NANS (TREE_TYPE (op0)));
> + if (code == ERROR_MARK)
> + return NULL_TREE;
> +
> + gassign **inverse = comparisons.get (comparison_key (code, op0, op1));
> + /* Factoring a previous PHI can remove an indexed comparison. */
> + if (inverse && gimple_bb (*inverse))
> + {
> + tree lhs = gimple_assign_lhs (*inverse);
> + if (useless_type_conversion_p (TREE_TYPE (cond), TREE_TYPE (lhs)))
> + return lhs;
> + }
> + return NULL_TREE;
> +}
> +
> /* Structure used to track meta-data on PHI arguments used to generate
> most efficient comparison sequence to slatten a PHI node. */
>
> @@ -2388,11 +2428,13 @@ cmp_arg_entry (const void *p1, const void *p2, void *
> /* data. */)
> The generated code is inserted at GSI that points to the top of
> basic block's statement list.
> If PHI node has more than two arguments a chain of conditional
> - expression is produced. */
> + expression is produced.
> + COMPARISONS holds comparisons available before the insertion point. */
>
>
> static void
> -predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
> +predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi,
> + hash_map<tree_operand_hash, gassign *> &comparisons)
> {
> gimple *new_stmt = NULL, *reduc, *nop_reduc;
> tree rhs, res, arg0, arg1, op0, op1, scev;
> @@ -2454,6 +2496,7 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator
> *gsi)
> cond = gen_simplified_condition (cond, cond_set);
> cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
> NULL_TREE, true, GSI_SAME_STMT);
> +
> true_bb = first_edge->src;
> if (EDGE_PRED (bb, 1)->src == true_bb)
> {
> @@ -2470,6 +2513,15 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator
> *gsi)
> for PHI with 2 elements. */
> factor_out_operators (&res, gsi, &arg0, &arg1, phi);
>
> + /* Reuse an inverse comparison and select the other predecessor. */
> + tree inverted = lookup_inverted_predicate (cond, comparisons);
> + if (inverted)
> + {
> + cond = inverted;
> + std::swap (arg0, arg1);
> + true_bb = EDGE_PRED (bb, first_edge == EDGE_PRED (bb, 0))->src;
> + }
> +
> if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
> &op0, &op1, false, &has_nop,
> &nop_reduc))
> @@ -2607,11 +2659,29 @@ predicate_all_scalar_phis (class loop *loop)
> unsigned int orig_loop_num_nodes = loop->num_nodes;
> unsigned int i;
>
> + /* Index comparisons that precede the current block after merging. */
> + hash_map<tree_operand_hash, gassign *> comparisons;
> + basic_block exit_bb = single_exit (loop)->src;
> +
> for (i = 1; i < orig_loop_num_nodes; i++)
> {
> gphi *phi;
> gimple_stmt_iterator gsi;
> gphi_iterator phi_gsi;
> + bb = ifc_bbs[i - 1];
> + if (bb != exit_bb && bb != loop->latch)
> + for (gimple_stmt_iterator si = gsi_start_bb (bb);
> + !gsi_end_p (si); gsi_next (&si))
> + if (gassign *def = dyn_cast <gassign *> (gsi_stmt (si)))
> + if (TREE_CODE_CLASS (gimple_assign_rhs_code (def))
> + == tcc_comparison)
> + {
> + tree key = comparison_key (gimple_assign_rhs_code (def),
> + gimple_assign_rhs1 (def),
> + gimple_assign_rhs2 (def));
> + comparisons.put (key, def);
> + }
> +
> bb = ifc_bbs[i];
>
> if (bb == loop->header)
> @@ -2629,7 +2699,7 @@ predicate_all_scalar_phis (class loop *loop)
> gsi_next (&phi_gsi);
> else
> {
> - predicate_scalar_phi (phi, &gsi);
> + predicate_scalar_phi (phi, &gsi, comparisons);
> remove_phi_node (&phi_gsi, false);
> }
> }
> --
> 2.50.1 (Apple Git-155)
>
