public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "wschmidt at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug rtl-optimization/48077] New: [Code Improvement] Use multiplication by magic number for integer division by constant Date: Fri, 11 Mar 2011 16:41:00 -0000 [thread overview] Message-ID: <bug-48077-4@http.gcc.gnu.org/bugzilla/> (raw) http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48077 Summary: [Code Improvement] Use multiplication by magic number for integer division by constant Product: gcc Version: 4.6.0 Status: UNCONFIRMED Severity: normal Priority: P3 Component: rtl-optimization AssignedTo: unassigned@gcc.gnu.org ReportedBy: wschmidt@gcc.gnu.org CC: bergner@gcc.gnu.org, pthaugen@gcc.gnu.org, meissner@gcc.gnu.org, dje.gcc@gmail.com, wschmidt@gcc.gnu.org Target: powerpc64-linux, others We noticed a significant performance difference between gcc and xlc at all optimization levels for a small application that repeatedly takes a value modulo an integer constant. Gcc expands division by a constant into a sequence of shifts, adds, and subtracts. Xlc converts division by a constant into multiplication by a corresponding magic number. See H.S. Warren's _Hacker's Delight_ for details. See http://www.hackersdelight.org/magic.htm for a magic number calculator. A small test case shows the difference: ----------------------------------------- int *values; int *hash_table; int demonstrate (int i) { return hash_table [values [i] % 1000]; } ----------------------------------------- On powerpc64-linux, xlc -c -S -O3 -q32 test.c produces: demonstrate: addis r4,r0,values@ha rlwinm r3,r3,2,0,29 addis r6,r0,hash_table@ha addis r5,r0,4194 addi r0,r5,19923 lwz r4,values@l(r4) lwz r5,hash_table@l(r6) lwzx r3,r4,r3 rlwinm r4,r3,1,31,31 mulhw r0,r3,r0 srawi r0,r0,6 add r6,r0,r4 rlwinm r0,r6,10,0,21 rlwinm r4,r6,5,0,26 subf r0,r4,r0 rlwinm r6,r6,3,0,28 add r4,r0,r6 subf r0,r4,r3 rlwinm r3,r0,2,0,29 lwzx r3,r5,r3 bclr BO_ALWAYS,CR0_LT Note the multiply by 274877907, built by: addis r5,r0,4194 addi r0,r5,19923 If you plug 1000 into the magic number calculator at the website above, that's the magic number produced. By contrast, gcc -c -S -O3 -m32 test.c produces: .L.demonstrate: addis 9,2,.LC0@toc@ha ld 9,.LC0@toc@l(9) sldi 3,3,2 addis 11,2,.LC1@toc@ha ld 9,0(9) ld 10,.LC1@toc@l(11) lwzx 9,9,3 extsw 0,9 sldi 8,0,7 sldi 11,0,9 add 11,8,11 subf 11,0,11 sldi 11,11,3 add 11,11,0 sldi 8,11,2 add 11,11,8 sldi 11,11,2 add 11,11,0 sldi 11,11,3 add 11,11,0 sldi 8,11,3 subf 11,11,8 sldi 11,11,4 add 0,11,0 sldi 11,0,2 subf 0,0,11 srdi 0,0,32 srawi 11,9,31 srawi 0,0,6 subf 0,11,0 slwi 8,0,7 slwi 11,0,2 subf 11,11,8 add 0,11,0 ld 11,0(10) slwi 0,0,3 subf 9,0,9 extsw 9,9 sldi 9,9,2 lwax 3,11,9 blr Note the long string of dependencies in the gcc code; not only is the code quite a bit larger, but there is very little ILP. Consider converting integer division to multiplication by a magic number when appropriate for the target machine.
next reply other threads:[~2011-03-11 16:41 UTC|newest] Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top 2011-03-11 16:41 wschmidt at gcc dot gnu.org [this message] 2011-03-11 17:11 ` [Bug rtl-optimization/48077] " pinskia at gcc dot gnu.org 2011-03-11 18:34 ` wschmidt at gcc dot gnu.org 2011-03-11 19:22 ` [Bug target/48077] [Code Improvement] Poor expansion of multiply on powerpc64-linux wschmidt at gcc dot gnu.org 2011-03-11 20:43 ` meissner at gcc dot gnu.org 2011-03-11 21:28 ` wschmidt at gcc dot gnu.org 2011-03-14 10:26 ` rguenth at gcc dot gnu.org
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-48077-4@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
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).