https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97459
--- Comment #22 from CVS Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Jakub Jelinek <ja...@gcc.gnu.org>: https://gcc.gnu.org/g:4d87bd39bafae86747944b2f8c53fdbc43b8dac3 commit r11-5533-g4d87bd39bafae86747944b2f8c53fdbc43b8dac3 Author: Jakub Jelinek <ja...@redhat.com> Date: Mon Nov 30 10:55:43 2020 +0100 expansion: Improve double-word modulo by certain constant divisors [PR97459] As discussed in the PR, e.g. on x86_64 (both -m32 and -m64) there is no double-word modulo and so we expand it to a __{,u}mod[dt]i3 call. For certain constant divisors we can do better. E.g. consider 32-bit word-size, 0x100000000ULL % 3 == 1, so we can use partly the Hacker's delight modulo by summing digits approach and optimize unsigned long long foo (unsigned long long x) { return x % 3; } as unsigned long long foo (unsigned long long x) { unsigned int sum, carry; carry = __builtin_add_overflow ((unsigned int) x, (unsigned int) (x >> 32), &sum); sum += carry; return sum % 3; } Similarly, 0x10000000ULL % 5 == 1 (note, 1 << 28), so unsigned long long bar (unsigned long long x) { return x % 5; } as unsigned long long bar (unsigned long long x) { unsigned int sum = x & ((1 << 28) - 1); sum += (x >> 28) & ((1 << 28) - 1); sum += (x >> 56); return sum % 5; } etc. And we can do also signed modulo, long long baz (long long x) { return x % 5; } as long long baz (long long x) { unsigned int sum = x & ((1 << 28) - 1); sum += ((unsigned long long) x >> 28) & ((1 << 28) - 1); sum += ((unsigned long long) x >> 56); /* Sum adjustment for negative x. */ sum += (x >> 63) & 3; unsigned int rem = sum % 5; /* And finally adjust it to the right interval for negative values. */ return (int) (rem + ((x >> 63) & -4)); } 2020-11-30 Jakub Jelinek <ja...@redhat.com> PR rtl-optimization/97459 * internal-fn.h (expand_addsub_overflow): Declare. * internal-fn.c (expand_addsub_overflow): No longer static. * optabs.c (expand_doubleword_mod): New function. (expand_binop): Optimize double-word mod with constant divisor. * gcc.dg/pr97459-1.c: New test. * gcc.dg/pr97459-2.c: New test.
