[PATCH v8] forwprop: add simplify_phi_result_movdiv() [PR101179]

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 positive integers in a PHI.  E.g.:

- for TRUNC_MOD and FLOOR_MOD, if either "_y" is known positive or
  "_x" is used just in zero comparisons:

phi_var = PHI <16,4>
_x = _y % phi_var

Can be turned into:

phi_var = PHI <15,3>
_x = _y & phi_var

- for TRUNC_DIV, FLOOR_DIV and EXACT_DIV, if "_y" is a known positive:

phi_var = PHI <16,4>
_x = _y / phi_var

Can be turned into:

phi_var = PHI <4,2>
_x = _y >> phi_var

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 v7:
- removed CEIL_MOD_EXPR, ROUND_MOD_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
- added EXACT_DIV_EXPR
- use add_phi_arg() and gimple_phi_arg_location()
- added explicit PHI arg not negative check to cover corner cases of
  checking just for integer_pow2p
- v7 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-August/727370.html

 gcc/testsuite/gcc.dg/tree-ssa/pr101179.c |  77 ++++++++++++++++
 gcc/tree-ssa-forwprop.cc                 | 106 +++++++++++++++++++++++
 2 files changed, 183 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..23b7c2acb06
--- /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;
+}
+
+/* Fail: can't guarantee y is positive.  */
+int g1 (int y, _Bool x)
+{
+  return y / (x ? 16 : 4) == 0;
+}
+
+/* Fail: can't guarantee y is positive.  */
+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 (uint y, uint 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 " >> " 1 "phiopt1" } } */
+/* { dg-final { scan-tree-dump-times " \\/ " 2 "phiopt1" } } */
diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
index 75f06c6ba41..90a1ae60b65 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -3623,6 +3623,104 @@ 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, if the right conditions are met, change the PHI args
+   and "_ssa1" stmt to a cheaper alternative.
+
+   - for MOD, if either "_ssa2" is known to be positive or
+   "_ssa1" is used just in zero comparisons:
+
+   iftmp1 = PHI <(pow2a - 1), (pow2b - 1), (pow2c - 1), ...>
+   _ssa1 = _ssa2 & iftmp1;
+
+   - for DIV, if "_ssa2" is known to be positive:
+
+   iftmp1 = PHI <log2 (pow2a), log2 (pow2b), log2 (pow2c), ...>
+   _ssa1 = _ssa2 >> iftmp1;  */
+static bool
+simplify_phi_result_movdiv (gimple *stmt, tree_code code)
+{
+  tree rhs1 = gimple_assign_rhs1 (stmt);
+  tree_code new_code;
+
+  switch (code)
+    {
+      case TRUNC_MOD_EXPR:
+      case FLOOR_MOD_EXPR:
+	if (!tree_expr_nonnegative_p (rhs1)
+	    && !use_in_zero_equality (gimple_assign_lhs (stmt), true))
+	  return false;
+
+	new_code = BIT_AND_EXPR;
+	break;
+
+      case TRUNC_DIV_EXPR:
+      case FLOOR_DIV_EXPR:
+      case EXACT_DIV_EXPR:
+	if (!tree_expr_nonnegative_p (rhs1))
+	  return false;
+
+	new_code = RSHIFT_EXPR;
+	break;
+
+     default:
+	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))
+	|| tree_int_cst_sgn (gimple_phi_arg_def (phi, i)) < 0)
+      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);
+      edge e = gimple_phi_arg_edge (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);
+
+      add_phi_arg (new_phi, arg, e,
+		   gimple_phi_arg_location (phi, e->dest_idx));
+    }
+
+  /* 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 +5992,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