This section is mostly taken, with permission, from the documentation for SBCL.
Some numeric functions have a property:
N lower bits of
the result depend only on
N lower bits of (all or some)
arguments. If the compiler sees an expression of form
exp mask), where
exp is a tree of such “good” functions
mask is known to be of type
w is a "good" width, all intermediate results
will be cut to
w bits (but it is not done for variables
and constants!). This often results in an ability to use simple
machine instructions for the functions.
Consider an example.
(defun i (x y) (declare (type (unsigned-byte 32) x y)) (ldb (byte 32 0) (logxor x (lognot y))))
The result of
(lognot y) will be negative and of
(signed-byte 33), so a naive implementation on a 32-bit
platform is unable to use 32-bit arithmetic here. But modular
arithmetic optimizer is able to do it: because the result is cut down
to 32 bits, the compiler will replace
lognot with versions cutting results to 32 bits, and
because terminals (here—expressions
are also of type
(unsigned-byte 32), 32-bit machine
arithmetic can be used.
Currently “good” functions
lognot and their combinations;
ash with the positive second argument. “Good” widths
are 32 on HPPA, MIPS, PPC, Sparc and X86 and 64 on Alpha. While it is
possible to support smaller widths as well, currently it is not
A more extensive description of modular arithmetic can be found in the paper “Efficient Hardware Arithmetic in Common Lisp” by Alexey Dejneka, and Christophe Rhodes, to be published.