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

On Mon, Aug 3, 2026 at 10:26 AM Daniel Henrique Barboza
<[email protected]> wrote:
>
>
>
> On 8/2/2026 11:12 PM, Andrea Pinski wrote:
> > On Fri, Jul 31, 2026 at 4:57 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.
> >>
> >> Most of 101179 use cases are solved by this change.
> >>
> >> 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.
> >>
> >> gcc/testsuite/ChangeLog:
> >>
> >>          * gcc.dg/tree-ssa/pr101179.c: New test.
> >> ---
> >>
> >> Changes from v2:
> >> - moved the implementation from phiopt to forwprop.  It resulted in a
> >>    smaller and a bit cleaner logic.
> >> - v2 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-July/724039.html
> >>
> >>   gcc/testsuite/gcc.dg/tree-ssa/pr101179.c |  56 ++++++++++++
> >>   gcc/tree-ssa-forwprop.cc                 | 110 +++++++++++++++++++++++
> >>   2 files changed, 166 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..478bdc6fcd3
> >> --- /dev/null
> >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr101179.c
> >> @@ -0,0 +1,56 @@
> >> +/* { 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 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);
> >> +}
> >> +
> >> +/* { dg-final { scan-tree-dump-times " \& " 3 "phiopt1" } } */
> >> +/* { dg-final { scan-tree-dump-times " \% " 1 "phiopt1" } } */
> >> +/* { dg-final { scan-tree-dump-times " >> " 2 "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..32a9fee560c 100644
> >> --- a/gcc/tree-ssa-forwprop.cc
> >> +++ b/gcc/tree-ssa-forwprop.cc
> >> @@ -3623,6 +3623,108 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)
> >>     return true;
> >>   }
> >>
> >> +/* Verify if we have the following structure:
> >> +
> >> +   iftmp1 = PHI <pow2a, pow2b>
> >> +   _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)>
> >> +   _ssa1 = _ssa2 & iftmp1;
> >> +
> >> +   For DIV:
> >> +
> >> +   iftmp1 = PHI <log2 (pow2a), log2 (pow2b)>
> >> +   _ssa1 = _ssa2 >> iftmp1;  */
> >> +static bool
> >> +simplify_phi_result_op (gimple *stmt, tree_code code)
> >> +{
> >> +  gphi *phi = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)));
> > Need a check for nullptr after dyn_cast.
>
>
> Hmmmm I thought the nullptr case would be covered by the checks I'm doing before calling
> the function:
>
>
> +                            && 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);
>
>
> Maybe it's clearer to fold these checks inside the function ...

Then you can just use as_a<gphi*> instead of dyn_cast. The dyn_cast is
what confused me really; as_a would have made it clear that it was
asserted a phi beforehand.

>
>
>
> >
> >> +  if (gimple_phi_num_args (phi) != 2)
> >> +    return false;
> >
> > Instead of just handling 2 argument phis. why not handle N argument phis here.
>
>
> Mostly because I didn't though about that :D I just came up with a simple
> C code that generates a PHI with 4 args that we could reduce.
>
> I'll rework the code to support this use case.


Thanks,
Andrea

>
> >
> >
> >> +
> >> +  tree arg0 = gimple_phi_arg_def (phi, 0);
> >> +  tree arg1 = gimple_phi_arg_def (phi, 1);
> >> +
> >> +  if (!integer_pow2p (arg0) || !tree_fits_uhwi_p (arg0)
> >> +      || !integer_pow2p (arg1) || !tree_fits_uhwi_p (arg1))
> >> +    return false;
> >
> > That is 2 loops.
> > One to reject if the argument is not a power of 2. I don't think you
> > need tree_fits_uhwi_p (see below on why).
> >
> >> +
> >> +  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 single_use with a
> >> +     EQ|NE 0 cmp.  */
> >> +  tree rhs1 = gimple_assign_rhs1 (stmt);
> >> +  if (!tree_expr_nonnegative_p (rhs1))
> >> +    {
> >> +      gimple *cmp_stmt;
> >> +      use_operand_p use_p;
> >> +
> >> +      if (!single_imm_use (gimple_assign_lhs (stmt), &use_p, &cmp_stmt)
> >> +         || !cmp_stmt
> >> +         || !is_gimple_assign (cmp_stmt))
> >> +       return false;
> >> +
> >> +      if (!(gimple_assign_rhs_code (cmp_stmt) == NE_EXPR
> >> +           || gimple_assign_rhs_code (cmp_stmt) == EQ_EXPR))
> >> +       return false;
> >> +
> >> +      if (!integer_zerop (gimple_assign_rhs2 (cmp_stmt)))
> >> +       return false;
> >> +    }
> >
> > Put this before the phi check loop.
> >
> >> +
> >> +  tree phires = gimple_phi_result (phi);
> >> +  tree type = TREE_TYPE (phires);
> >> +  tree new_arg0, new_arg1;
> >> +
> >> +  if (new_code == RSHIFT_EXPR)
> >> +    {
> >> +      new_arg0 = build_int_cst (type, wi::exact_log2 (tree_to_uhwi (arg0)));
> >> +      new_arg1 = build_int_cst (type, wi::exact_log2 (tree_to_uhwi (arg1)));
> >
> > Use wi::to_wide here.
> > For RSHIFT_EXPR, add a gimple_convert to integer_type_node for the new
> > rhs. That is 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.
> >
> >> +    }
> >> +  else
> >> +    {
> >> +      new_arg0 = build_int_cst (type, tree_to_uhwi (arg0) - 1);
> >> +      new_arg1 = build_int_cst (type, tree_to_uhwi (arg1) - 1);
> >
> > Likewise. (this removes the need for the tree_fits_uhwi_p check)
> >
> >> +    }
> >> +
> >> +  SET_PHI_ARG_DEF (phi, 0, new_arg0);
> >> +  SET_PHI_ARG_DEF (phi, 1, new_arg1);
> >> +  if (SSA_NAME_RANGE_INFO (phires))
> >> +    reset_flow_sensitive_info (phires);
> >
> > Maybe it is better to insert a new phi rather than reuse the current
> > phi for debug info reasons. You might want to fixup the debug info
> > too.
>
> If we create a new phi do we need to do stuff w.r.t debug info of the older
> phi?
>
>
> Thanks,
> Daniel
>
> >
> > Thanks,
> > Andrea
> >
> >> +
> >> +  gimple_assign_set_rhs1 (stmt, rhs1);
> >> +  gimple_assign_set_rhs2 (stmt, phires);
> >> +  gimple_assign_set_rhs_code (stmt, new_code);
> >> +  update_stmt (stmt);
> >> +
> >> +  return true;
> >> +}
> >>
> >>   /* Determine whether applying the 2 permutations (mask1 then mask2)
> >>      gives back one of the input.  */
> >> @@ -5894,6 +5996,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
> >>
>