This new phiopt 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-phiopt.cc (simplify_phi_result_op): New phiopt step where MOD/DIV ops with pow2 divisors can be simplified to BIT_AND/RSHIFT. (pass_phiopt::execute): Call simplify_phi_result_op. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/pr101179.c: New test. --- Changes from v1: - do not use match.pd; - add a phiopt step where MOD/DIV operations where the divisor is given by pow2 CSTs inside a PHI can be simplified to BIT_AND/RSHIFT; - v1 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-May/717078.html gcc/testsuite/gcc.dg/tree-ssa/pr101179.c | 56 +++++++++++ gcc/tree-ssa-phiopt.cc | 115 +++++++++++++++++++++++ 2 files changed, 171 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-phiopt.cc b/gcc/tree-ssa-phiopt.cc index e12dc7a8b0c..dae594ee6c6 100644 --- a/gcc/tree-ssa-phiopt.cc +++ b/gcc/tree-ssa-phiopt.cc @@ -4121,6 +4121,119 @@ hoist_adjacent_loads (basic_block bb0, basic_block bb1, } } +/* 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 (gphi *phi, tree arg0, tree arg1, edge e1, edge e2) +{ + if (!integer_pow2p (arg0) || !tree_fits_uhwi_p (arg0) + || !integer_pow2p (arg1) || !tree_fits_uhwi_p (arg1)) + return false; + + /* The phi result must have a single use. */ + tree phires = gimple_phi_result (phi); + use_operand_p use_p; + gimple *op_stmt; + + if (!single_imm_use (phires, &use_p, &op_stmt) + || !op_stmt + || !is_gimple_assign (op_stmt)) + return false; + + tree_code op_code = gimple_assign_rhs_code (op_stmt); + tree_code new_op_code; + switch (op_code) + { + case TRUNC_MOD_EXPR: + case CEIL_MOD_EXPR: + case FLOOR_MOD_EXPR: + case ROUND_MOD_EXPR: + new_op_code = BIT_AND_EXPR; + break; + + case TRUNC_DIV_EXPR: + case CEIL_DIV_EXPR: + case FLOOR_DIV_EXPR: + case ROUND_DIV_EXPR: + new_op_code = RSHIFT_EXPR; + break; + + default: + return false; + } + + tree op_other; + + /* phires needs to be the divisor. */ + if (gimple_assign_rhs2 (op_stmt) != phires) + return false; + + op_other = gimple_assign_rhs1 (op_stmt); + + /* If 'op_other' is a known positive value we can + always apply the MOD simplificatios. Otherwise see if + the op_result is single_use with a EQ|NE 0 cmp. */ + if (!tree_expr_nonnegative_p (op_other)) + { + gimple *cmp_stmt; + + if (!single_imm_use (gimple_assign_lhs (op_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; + } + + tree type = TREE_TYPE (phires); + tree new_arg0, new_arg1; + + if (new_op_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))); + } + else + { + new_arg0 = build_int_cst (type, tree_to_uhwi (arg0) - 1); + new_arg1 = build_int_cst (type, tree_to_uhwi (arg1) - 1); + } + + SET_PHI_ARG_DEF (phi, e1->dest_idx, new_arg0); + SET_PHI_ARG_DEF (phi, e2->dest_idx, new_arg1); + if (SSA_NAME_RANGE_INFO (phires)) + reset_flow_sensitive_info (phires); + + gimple_assign_set_rhs1 (op_stmt, op_other); + gimple_assign_set_rhs2 (op_stmt, phires); + gimple_assign_set_rhs_code (op_stmt, new_op_code); + update_stmt (op_stmt); + + return true; +} + /* Determine whether we should attempt to hoist adjacent loads out of diamond patterns in pass_phiopt. Always hoist loads if -fhoist-adjacent-loads is specified and the target machine has @@ -4482,6 +4595,8 @@ pass_phiopt::execute (function *) node. */ gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE); + if (simplify_phi_result_op (phi, arg0, arg1, e1, e2)) + cfgchanged = true; /* Do the replacement of conditional if it can be done. */ if (match_simplify_replacement (bb, bb1, bb2, e1, e2, phi, -- 2.43.0
