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 used just in zero equality comparisons. 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_movdiv): New forwprop step where MOD/DIV ops with pow2 divisors can be simplified to BIT_AND/RSHIFT. (pass_forwprop::execute): Call simplify_phi_result_movdiv. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/pr101179.c: New test. --- Changes from v5: - remove 'single_use' and 'phiopt' references from commit message - rename simplify_phi_result_op to simplify_phi_result_movdiv - use remove_phi_node instead of gsi_remove - v5 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-August/726892.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..b60af3c02a3 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_movdiv (gimple *stmt, tree_code code) +{ + 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); + remove_phi_node (&gsi, true); + + 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_movdiv (stmt, code); break; } -- 2.43.0
