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

On 8/8/2026 3:59 PM, Andrea Pinski wrote:
> 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

And looks like there's a "phiopt" hanging around here too.  I'll fix that
for v6.


Cheers,
Daniel

>>          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
>>