compiler-rt implements the 64-bit division routines __divdi3(),
__moddi3(), __udivdi3() and __umoddi3() for IA32 alias x86 in
assembler (see the directory compiler-rt/lib/builtins/i386/)
While Stephen Canon did a decent job back in December 2008, he
left QUITE some room for improvement^Woptimisation: see the
All 4 routines have two almost identical code branches of 20+
and 22+ instructions, with just TWO additional instructions in
the second branch:
- divdi3.S lines 72-102 vs. 103-104
- moddi3.S lines 71-104 vs. 104-144
- udivdi3.S lines 43-67 vs. 68-100
- umoddi3.S lines 44-72 vs. 73-108
These two branches can of course be folded into just one branch,
saving 20+ instructions.
The third branch, where both dividend and divisor are below 2**32,
always performs a "long division", even if a single DIV would be
sufficient, at the expense of an additional CMP and Jcc: adding
these 2 instructions saves the execution of a DIV and QUITE some
processor cycles (on average about 10-16 cycles per call, from a
total of about 42-56 cycles).
See <Not Quite so “Optimising” (and Buggy) Microsoft® Visual C Compilers> for
comparision of these improved routines with other implementations.
PS: is there any special reason why __divmoddi4() and __udivmoddi4()
are not implemented in assembler?
What about __udivmodti4() etc. for AMD64 alias x86-64?
See the directory compiler-rt/lib/builtins/x86_64/
i386_di3.patch (26.6 KB)