[Bug tree-optimization/118637] gcc fails to optimize unsigned division by 2 to shift right by 1

[rguenth at gcc dot gnu.org via Gcc-bugs]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118637

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2025-01-24
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
The difference is we end up with

  <bb 2> [local count: 118111600]:
  x_9 = x_3(D) >> 1;
  if (x_3(D) > 1)
    goto <bb 3>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 3> [local count: 955630224]:
  # result_10 = PHI <result_6(3), 0(2)>
  # x_12 = PHI <x_4(3), x_9(2)>
  result_6 = result_10 + 1;
  x_4 = x_12 >> 1;
  if (x_12 > 1) 
    goto <bb 3>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 4> [local count: 118111600]:
  # result_11 = PHI <result_6(3), 0(2)>
  return result_11;

for the log2_divide case and

  <bb 2> [local count: 118111600]:
  x_9 = x_3(D) >> 1;
  if (x_9 != 0)
    goto <bb 3>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 3> [local count: 955630224]:
  # result_10 = PHI <result_6(3), 0(2)>
  # x_12 = PHI <x_4(3), x_9(2)>
  result_6 = result_10 + 1;
  x_4 = x_12 >> 1;
  if (x_4 != 0)
    goto <bb 3>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 4> [local count: 118111600]:
  # result_11 = PHI <result_6(3), 0(2)>
  return result_11;

for the log2_shift case which we can pattern-match to CLZ.

This is done by

/* X / C1 op C2 into a simple range test.  */
(for cmp (simple_comparison)
 (simplify
  (cmp (trunc_div:s @0 INTEGER_CST@1) INTEGER_CST@2)
...
     (if (code == NE_EXPR && !lo)
      (gt @0 { hi; }))

note that ':s' isn't effective for this result.

EVRP is the pass turning x / 2 into x >> 1:

Folding statement: x_5 = x_1 / 2;
Global Exported: x_5 = [irange] unsigned int [0, 2147483647] MASK 0x7fffffff
VALUE 0x0
Folded into: x_5 = x_1 >> 1;