Optimize integer division by a constant in several cases.
authorLutz Euler <lutz.euler@freenet.de>
Mon, 25 Jul 2011 00:47:43 +0000 (02:47 +0200)
committerNikodemus Siivola <nikodemus@sb-studio.net>
Fri, 5 Aug 2011 13:10:13 +0000 (16:10 +0300)
commit7ab4cdd5eaf3dce3cc596b348bfc98aaa27469d5
tree92eb1745e70ad1e90e06cf307b2c061a1d6d1bd9
parentfb15ad0ff2373a50b3b0717f705c49339b39f996
Optimize integer division by a constant in several cases.

Convert integer division by a constant into multiplication to gain
a large speedup as the machine instructions for multiplication are
typically executed much faster than those for division.

This is implemented using a deftransform on TRUNCATE that triggers
if the dividend is known to fit in an unsigned machine word and if
the divisor is a constant, also fitting in an unsigned machine word.
(The cases that are optimized by other existing transforms, for example
if the divisor is a power of two, are left to these transforms.)

The replacement code is based on a widening multiply (that is already
available as bignum calculations need it) and possibly some shifts and
an addition to calculate the quotient. If the remainder is needed,
additionally a (normal) multiplication and a subtraction are generated.

As several other integer division operations are implemented using
TRUNCATE, this also affects CEILING, FLOOR, MOD and REM with the same
argument types. CEILING and FLOOR, however, are optimized only when
SAFETY=0 since they are declared MAYBE-INLINE.
NEWS
src/compiler/srctran.lisp
tests/arith.pure.lisp