https://gcc.gnu.org/bugzilla/show_bug.cgi?id=126114
Bug ID: 126114
Summary: Missed Optimisation Bug - Unsigned divide by 7 (and
19, 21 etc)
Product: gcc
Version: 16.1.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: william.gibbons at gmail dot com
Target Milestone: ---
Hi
It seems like GCC's routine for unsigned divide by 7 (or various other numbers)
is sub-optimal.
GCC seems to be using a version of the algorithm in Hacker's Delight, which
(for 32 bit divides) requires multiplication by a constant spanning 33 bits.
Essentially for an unsigned integer x, division by 7 is implemented by
multiplying by (2^35+3)/7 (which spans 33 bits) and then shifting right 35
bits. This is expensive because it requires breaking the multiplication into
two components, and performing an addition (which then requires handling
overflows appropriately).
A better strategy is to implement division by 7 as (x*c+c)>>33 where
c=(2^33-1)/7 (spanning only 31 bits). In this case there's no possibility of
overflow, and several fewer instructions can be used. I created a thread on
this example here:
https://stackoverflow.com/questions/79969064/faster-unsigned-divide-7-and-19-etc-on-aarch64-gcc-clang
As Peter Cordes and myself demonstrated, unsigned division by 7 could be
implemented much more efficiently than it is.
The same thing occurs for dividing by 19, 21 and various other numbers where
GCC's approach is to multiply by numbers spanning 33 bits. It is possible to
implement these divides the same way (x*c+c)>>n for constants c spanning 32
bits or fewer. I believe the approach is first mentioned in a paper of Arch
Robison (though I'm not sure the fact it works so generally has been
appreciated). I have some brief & elementary mathematical proofs of the
general case which I can share if useful.
