[Bug tree-optimization/102888] New: missing case for combining / and % into one operation

[Bug tree-optimization/102888] New: missing case for combining / and % into one operation

[vanyacpp at gmail dot com]

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

            Bug ID: 102888
           Summary: missing case for combining / and % into one operation
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vanyacpp at gmail dot com
  Target Milestone: ---

Normally GCC combines a/b and a%b into one operation when they are computed in
the same basic-block. The example below has two functions. For one GCC is able
to combine the operations and for other not (presumably because of complicated
control-flow). I believe the two functions are functionally equivalent. 

unsigned long long reduce(unsigned long long a, unsigned long long b)
{
    while ((a % b) == 0)
        a /= b;

    return a;
}

unsigned long long reduce_opt(unsigned long long a, unsigned long long b)
{
    for (;;)
    {
        unsigned long long quot = a / b;
        unsigned long long rem = a % b;
        if (rem != 0)
            break;
        a = quot;
    }

    return a;
}

reduce.L3:
        mov     rax, r8
        xor     edx, edx
        div     rsi
        xor     edx, edx
        mov     r8, rax
        div     rsi
        test    rdx, rdx
        je      .L3

reduce_opt.L8:
        xor     edx, edx
        mov     r8, rax
        div     rsi
        test    rdx, rdx
        je      .L8

https://godbolt.org/z/9dqs8avE5

It would be great if GCC generated the same code for both of these functions.

[Bug tree-optimization/102888] missing case for combining / and % into one operation

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-10-22

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  The complication is that the loop is rotated to do { } while ()
form
and that puts div and mod of different iterations next to each other:

  <bb 2> [local count: 118111600]:
  _8 = a_3(D) % b_4(D);
  if (_8 == 0)
    goto <bb 5>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 5> [local count: 105119324]:

  <bb 3> [local count: 955630225]:
  # a_9 = PHI <a_7(6), a_3(D)(5)>
  a_7 = a_9 / b_4(D);
  _1 = a_7 % b_4(D);
  if (_1 == 0)
    goto <bb 6>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 6> [local count: 850510901]:
  goto <bb 3>; [100.00%]

  <bb 4> [local count: 118111600]:
  # a_10 = PHI <a_7(3), a_3(D)(2)>
  return a_10;