Next: Extension to REQUIRE, Previous: Dynamic-Extent Declarations, Up: Design Choices and Extensions [Contents][Index]
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 (logand
exp mask)
, where exp
is a tree of such “good” functions
and mask
is known to be of type (unsigned-byte
w)
, where 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
type (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 logxor
and lognot
with versions cutting results to 32 bits, and
because terminals (here—expressions x
and y
)
are also of type (unsigned-byte 32)
, 32-bit machine
arithmetic can be used.
Currently “good” functions
are +
, -
, *
; logand
, logior
,
logxor
, lognot
and their combinations;
and 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
implemented.
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.
Next: Extension to REQUIRE, Previous: Dynamic-Extent Declarations, Up: Design Choices and Extensions [Contents][Index]