match.pd: Canonicalize unsigned division by power of two into right shift [PR118637]

match.pd: Canonicalize unsigned division by power of two into right shift [PR118637]

We already do this canonicalization in
simplify_using_ranges::simplify_div_or_mod_using_ranges, but that means
that it is not done at -O1 or when vrp is otherwise disabled, and that
it can be done too late in some cases when e.g. the r8-2064
"X / C1 op C2 into a simple range test." optimization triggers first.
Note, for unsigned modulo we already have
 (simplify
  (mod @0 (convert? (power_of_two_cand@1 @2)))
  (if ((TYPE_UNSIGNED (type) || tree_expr_nonnegative_p (@0))
...
optimization which duplicates what
simplify_using_ranges::simplify_div_or_mod_using_ranges
does in case ranges aren't needed.

For GCC 16 I think we should improve the niters pattern recognition
and handle even what r8-2064 comes with, after all as I've tried to show
in the PR the user could have written it that way.
I've guarded this optimization on #if GIMPLE just in case this would stand
in any way to the various divmult etc. simplification, guess that can be
lifted for GCC 16 too.  In the modulo case we also handle
unsigned % (power_of_two << n), but not really sure if we could do that
for the division, because unsigned / (power_of_two << n) is not simple
unsigned >> (log2 (power_of_two) + n), one can shift the bit out and then
it becomes just 0.

2025-01-27  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/118637
	* match.pd: Canonicalize unsigned division by power of two to
	right shift.

	* gcc.dg/tree-ssa/pr118637.c: New test.