On 7/20/2026 10:34 PM, Andrea Pinski wrote:
On Wed, Jul 15, 2026 at 7:12 AM Daniel Barboza
<[email protected]> wrote:
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;
So this is more like a phiprop type of thing.
And it seems more like what I am trying to do with
https://inbox.sourceware.org/gcc-patches/[email protected]/
but handling a more complex pattern simplification.
That is I am not sure this phiopt is the correct place for this. Maybe
phiprop would be better.
Fair enough. I tend to fall back into tree-ssa-phiopt because I'm more
acquainted with that code.
I'll check out your patch and see if I can implement this in phiprop instead.
Thanks,
Daniel
+
+ 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)
+{
Since this only works with 2 args you don't check if phi is only 2
operands. For normal phiopt, it can be more than 2.
+ 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
