Re: [PATCH v5] forwprop: add simplify_phi_result_op() [PR101179]

On Sat, Aug 8, 2026 at 2:38 AM Daniel Barboza
<[email protected]> wrote:
>
> This new forwprop  step is my attempt to implement Richi's suggestions from
> v1 of this work [1] where he suggested to push things out of match.pd.
>
> The idea is to simplify DIV/MOD into RSHIFT/BIT_AND ops in which the
> divisor are pow2 integers in a PHI.  E.g.:
>
> phi_var = PHI <16,4>
> _x = _y % phi_var
>
> Can be turned into:
>
> phi_var = PHI <15,3>
> _x = _y & phi_var
>
> As long as we know that _y is a positive number or '_x' is a single use
> with a zero comparison.

`single use` part is no longer true as you use use_in_zero_equality now.

>
> Most of 101179 use cases are solved by this change.  PHI with 2+ args
> are supported as long as every phi_arg meets the criteria.
>
> Boostrapped and regression tested with x86_64, aarch64 and riscv64.
>
> [1] https://gcc.gnu.org/pipermail/gcc-patches/2026-May/716303.html
>
>         PR tree-optimization/101179
>
> gcc/ChangeLog:
>
>         * tree-ssa-forwprop.cc (simplify_phi_result_op): New phiopt step
>         where MOD/DIV ops with pow2 divisors can be simplified to
>         BIT_AND/RSHIFT.
>         (pass_forwprop::execute): Call simplify_phi_result_op.

Just a few minor comments below that I thought of recently (sorry about that).

>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/pr101179.c: New test.
> ---
>
> Changes from v4:
> - replaced the single_imm_use + EQ|NE 0 comparison code by a
>   use_in_zero_equality call, as suggested by Andrea.
> - v4 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-August/726441.html
>
>  gcc/testsuite/gcc.dg/tree-ssa/pr101179.c |  77 +++++++++++++++++
>  gcc/tree-ssa-forwprop.cc                 | 104 +++++++++++++++++++++++
>  2 files changed, 181 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr101179.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr101179.c b/gcc/testsuite/gcc.dg/tree-ssa/pr101179.c
> new file mode 100644
> index 00000000000..5f996e7260d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr101179.c
> @@ -0,0 +1,77 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -fdump-tree-phiopt1" } */
> +
> +typedef unsigned uint;
> +
> +int f1 (int y, _Bool x)
> +{
> +  return y % (x ? 16 : 4) == 0;
> +}
> +
> +/* We can't turn this into bit_and because there's no
> +   guarantee 'y' is a positive val.  */
> +int f2 (int y, _Bool x)
> +{
> +  return y % (x ? 16 : 4);
> +}
> +
> +uint f3 (uint y, _Bool x)
> +{
> +  return y % (x ? 16 : 4) == 0;
> +}
> +
> +uint f4 (uint y, _Bool x)
> +{
> +  return y % (x ? 16 : 4);
> +}
> +
> +int f5 (int y, int x)
> +{
> +  int op = 64;
> +
> +  if (x > 40) op = 32;
> +  else if (x > 20) op = 16;
> +  else if (x > 10) op = 4;
> +
> +  return y % op == 0;
> +}
> +
> +int g1 (int y, _Bool x)
> +{
> +  return y / (x ? 16 : 4) == 0;
> +}
> +
> +/* We can't turn this into rshift because there's no
> +   guarantee 'y' is a positive val.  */
> +int g2 (int y, _Bool x)
> +{
> +  return y / (x ? 16 : 4);
> +}
> +
> +/* This will be turned by match.pd into:
> +   "(X / Y) == 0 -> X < Y if X, Y are unsigned."
> +   We're adding it here for completioness.  */
> +uint g3 (uint y, _Bool x)
> +{
> +  return y / (x ? 16 : 4) == 0;
> +}
> +
> +uint g4 (uint y, _Bool x)
> +{
> +  return y / (x ? 16 : 4);
> +}
> +
> +int g5 (int y, int x)
> +{
> +  int op = 64;
> +
> +  if (x > 40) op = 32;
> +  else if (x > 20) op = 16;
> +  else if (x > 10) op = 4;
> +
> +  return y / op == 0;
> +}
> +/* { dg-final { scan-tree-dump-times " \& " 4 "phiopt1" } } */
> +/* { dg-final { scan-tree-dump-times " \% " 1 "phiopt1" } } */
> +/* { dg-final { scan-tree-dump-times " >> " 3 "phiopt1" } } */
> +/* { dg-final { scan-tree-dump-times " \\/ " 1 "phiopt1" } } */
> diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
> index 75f06c6ba41..c7b6d3f510f 100644
> --- a/gcc/tree-ssa-forwprop.cc
> +++ b/gcc/tree-ssa-forwprop.cc
> @@ -3623,6 +3623,102 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)
>    return true;
>  }
>
> +/* Verify if we have the following structure:
> +
> +   iftmp1 = PHI <pow2a, pow2b, pow2c, ...>
> +   _ssa1 = _ssa2 MOD|DIV iftmp1;
> +   _ssa3 = _ssa1 EQ|NE 0;
> +
> +   And, as long as "_ssa2" is either known to be positive or
> +   "_ssa1" is single use in a zero comparison, change the PHI
> +   args and "_ssa1" stmt to a cheaper alternative.
> +
> +   For MOD:
> +
> +   iftmp1 = PHI <(pow2a - 1), (pow2b - 1), (pow2c - 1), ...>
> +   _ssa1 = _ssa2 & iftmp1;
> +
> +   For DIV:
> +
> +   iftmp1 = PHI <log2 (pow2a), log2 (pow2b), log2 (pow2c), ...>
> +   _ssa1 = _ssa2 >> iftmp1;  */
> +static bool
> +simplify_phi_result_op (gimple *stmt, tree_code code)

Maybe this should be named:
simplify_phi_result_moddiv since op here is mod/div.

> +{
> +  tree_code new_code;
> +  switch (code)
> +    {
> +      case TRUNC_MOD_EXPR:
> +      case CEIL_MOD_EXPR:
> +      case FLOOR_MOD_EXPR:
> +      case ROUND_MOD_EXPR:
> +       new_code = BIT_AND_EXPR;
> +       break;
> +      case TRUNC_DIV_EXPR:
> +      case CEIL_DIV_EXPR:
> +      case FLOOR_DIV_EXPR:
> +      case ROUND_DIV_EXPR:
> +       new_code = RSHIFT_EXPR;
> +       break;
> +
> +     default:
> +       return false;
> +    }
> +
> +  /* If rhs1 is a known positive value we can always apply these
> +     simplification.  Otherwise see if lhs is used just with
> +     zero equality comparisons.  */
> +  tree rhs1 = gimple_assign_rhs1 (stmt);
> +  if (!tree_expr_nonnegative_p (rhs1)
> +      && !use_in_zero_equality (gimple_assign_lhs (stmt), true))
> +    return false;
> +
> +  gphi *phi = as_a<gphi *> (SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)));
> +
> +  for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
> +    if (!integer_pow2p (gimple_phi_arg_def (phi, i)))
> +      return false;
> +
> +  tree type = TREE_TYPE (gimple_phi_result (phi));
> +  tree new_phires = make_ssa_name (type);
> +  gphi *new_phi = create_phi_node (new_phires, phi->bb);
> +
> +  for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
> +    {
> +      tree phi_arg = gimple_phi_arg_def (phi, i);
> +      tree arg;
> +
> +      if (new_code == RSHIFT_EXPR)
> +       arg = wide_int_to_tree (type, wi::exact_log2 (wi::to_wide (phi_arg)));
> +      else
> +       arg = wide_int_to_tree (type, wi::to_wide (phi_arg) - 1);
> +
> +      SET_PHI_ARG_DEF (new_phi, i, arg);
> +    }
> +
> +  /* Add a gimple_convert to integer_type_node for new_phires
> +     since it might be a long long which we want to convert
> +     into an integer or a bit_int that we want to convert into
> +     an integer.  */
> +  gimple_stmt_iterator gsi;
> +  if (new_code == RSHIFT_EXPR)
> +    {
> +      gsi = gsi_for_stmt (stmt);
> +      new_phires = gimple_convert (&gsi, true, GSI_SAME_STMT,
> +                                  gimple_location (stmt),
> +                                  integer_type_node, new_phires);
> +    }
> +
> +  gimple_assign_set_rhs1 (stmt, rhs1);
> +  gimple_assign_set_rhs2 (stmt, new_phires);
> +  gimple_assign_set_rhs_code (stmt, new_code);
> +  update_stmt (stmt);
> +
> +  gsi = gsi_for_phi (phi);
> +  gsi_remove (&gsi, true);

Use remove_phi_node instead.

> +
> +  return true;
> +}
>
>  /* Determine whether applying the 2 permutations (mask1 then mask2)
>     gives back one of the input.  */
> @@ -5894,6 +5990,14 @@ pass_forwprop::execute (function *fun)
>                       changed |= simplify_vector_constructor (&gsi);
>                     else if (code == ARRAY_REF)
>                       changed |= simplify_count_zeroes (&gsi);
> +                   else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS
> +                            && TREE_CODE (
> +                                   gimple_assign_rhs2 (stmt)) == SSA_NAME
> +                            && has_single_use (gimple_assign_rhs2 (stmt))
> +                            && SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt))
> +                            && is_a<gphi*> (SSA_NAME_DEF_STMT (
> +                                               gimple_assign_rhs2 (stmt))))
> +                     changed |= simplify_phi_result_op (stmt, code);
>                     break;
>                   }
>
> --
> 2.43.0
>