[Bug rtl-optimization/97459] New: __uint128_t remainder for division by 3

[tkoenig at gcc dot gnu.org]

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

            Bug ID: 97459
           Summary: __uint128_t remainder for division by 3
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tkoenig at gcc dot gnu.org
  Target Milestone: ---

The following two functions are equivalent:

unsigned r3_128u_v1 (__uint128_t n)
{
  unsigned long a;
  a = (n >> 64) + (n & 0xffffffffffffffff);
  return a % 3;
}

unsigned r3_128u_v2 (__uint128_t n)
{
  return (unsigned) (n%3);
}

and the first one is definitely faster.

(The approach is due to Hacker's Delight, 2nd edition, "Remainder by
Summing Digits". There are also other interesting approaches there.)