public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
* [Bug c/105521] New: missed optimization in modulo arithmetic @ 2022-05-08 4:08 goswin-v-b at web dot de 2022-05-08 4:38 ` [Bug target/105521] " pinskia at gcc dot gnu.org ` (3 more replies) 0 siblings, 4 replies; 5+ messages in thread From: goswin-v-b at web dot de @ 2022-05-08 4:08 UTC (permalink / raw) To: gcc-bugs https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105521 Bug ID: 105521 Summary: missed optimization in modulo arithmetic Product: gcc Version: 11.3.0 Status: UNCONFIRMED Severity: normal Priority: P3 Component: c Assignee: unassigned at gcc dot gnu.org Reporter: goswin-v-b at web dot de Target Milestone: --- I'm trying to compute (a*a)%n for uint64_t types on x86_64 using "gcc -O2 -W -Wall" like this: #include <stdint.h> #include <assert.h> uint64_t sqrmod(uint64_t a, uint64_t n) { assert(a < n); unsigned __int128 x = a; x *= a; return x % n; } I expected to get the following code: sqrmod: cmpq %rsi, %rdi jnb .L13 // assert(a < n) failure movq %rdi, %rax mul %rdi div %rsi movq %rdx, %rax ret The compiler does get the "mul" right but instead of the "div" it throws in a call to "__umodti3". The "__umodti3" function is horribly long code that will be worlds slower than a simple div. Note: The "asset(a < n);" should tell the compiler that the "div" instruction can not overflow and will not cause a #DivisionError. Without the assert the compiler could (conditionally) add "a %= n;" for the same effect. https://godbolt.org/z/cd57Wd4oo ^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug target/105521] missed optimization in modulo arithmetic 2022-05-08 4:08 [Bug c/105521] New: missed optimization in modulo arithmetic goswin-v-b at web dot de @ 2022-05-08 4:38 ` pinskia at gcc dot gnu.org 2022-05-08 4:38 ` pinskia at gcc dot gnu.org ` (2 subsequent siblings) 3 siblings, 0 replies; 5+ messages in thread From: pinskia at gcc dot gnu.org @ 2022-05-08 4:38 UTC (permalink / raw) To: gcc-bugs https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105521 Andrew Pinski <pinskia at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Component|middle-end |target Target| |x86_64-*-* --- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> --- This requires having a, 64bit/32bit (and 128bit/64bit) pattern really. So this is both a middle-end issue and a target issue. Note there might be another bug asking for the same optimization. Also note x86_64 might be the only popular target which has this kind of div instruction so this might not get any attention as it is also a small peephole where most people don't use 128bit integers either (they are non-standard even). ^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug target/105521] missed optimization in modulo arithmetic 2022-05-08 4:08 [Bug c/105521] New: missed optimization in modulo arithmetic goswin-v-b at web dot de 2022-05-08 4:38 ` [Bug target/105521] " pinskia at gcc dot gnu.org @ 2022-05-08 4:38 ` pinskia at gcc dot gnu.org 2022-05-08 4:40 ` pinskia at gcc dot gnu.org 2022-05-08 12:45 ` goswin-v-b at web dot de 3 siblings, 0 replies; 5+ messages in thread From: pinskia at gcc dot gnu.org @ 2022-05-08 4:38 UTC (permalink / raw) To: gcc-bugs https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105521 Andrew Pinski <pinskia at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Last reconfirmed| |2022-05-08 Ever confirmed|0 |1 Status|UNCONFIRMED |NEW --- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> --- . ^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug target/105521] missed optimization in modulo arithmetic 2022-05-08 4:08 [Bug c/105521] New: missed optimization in modulo arithmetic goswin-v-b at web dot de 2022-05-08 4:38 ` [Bug target/105521] " pinskia at gcc dot gnu.org 2022-05-08 4:38 ` pinskia at gcc dot gnu.org @ 2022-05-08 4:40 ` pinskia at gcc dot gnu.org 2022-05-08 12:45 ` goswin-v-b at web dot de 3 siblings, 0 replies; 5+ messages in thread From: pinskia at gcc dot gnu.org @ 2022-05-08 4:40 UTC (permalink / raw) To: gcc-bugs https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105521 Andrew Pinski <pinskia at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Severity|normal |enhancement ^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug target/105521] missed optimization in modulo arithmetic 2022-05-08 4:08 [Bug c/105521] New: missed optimization in modulo arithmetic goswin-v-b at web dot de ` (2 preceding siblings ...) 2022-05-08 4:40 ` pinskia at gcc dot gnu.org @ 2022-05-08 12:45 ` goswin-v-b at web dot de 3 siblings, 0 replies; 5+ messages in thread From: goswin-v-b at web dot de @ 2022-05-08 12:45 UTC (permalink / raw) To: gcc-bugs https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105521 --- Comment #3 from Goswin von Brederlow <goswin-v-b at web dot de> --- (In reply to Andrew Pinski from comment #1) > This requires having a, 64bit/32bit (and 128bit/64bit) pattern really. So > this is both a middle-end issue and a target issue. > > Note there might be another bug asking for the same optimization. > > Also note x86_64 might be the only popular target which has this kind of div > instruction so this might not get any attention as it is also a small > peephole where most people don't use 128bit integers either (they are > non-standard even). I know m68k had a 64bit/32bit pattern but it is indeed rare. On x86_64 a (32bit * 32bit = 64bit) % 32bit uses the 128bit/64bit DIV instruction and two extra truncation to 32bit for the input registers. On many cpus that is significantly (factor 3-10) slower than the 64bit/32bit version. This could potentially affect every / and % operation and preceding *, allowing for the faster opcodes with fewer bits to be used where the compiler can reason about the magnitude of the arguments. ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2022-05-08 12:45 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-05-08 4:08 [Bug c/105521] New: missed optimization in modulo arithmetic goswin-v-b at web dot de 2022-05-08 4:38 ` [Bug target/105521] " pinskia at gcc dot gnu.org 2022-05-08 4:38 ` pinskia at gcc dot gnu.org 2022-05-08 4:40 ` pinskia at gcc dot gnu.org 2022-05-08 12:45 ` goswin-v-b at web dot de
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).