How to convince Lisp SBCL to do inline fixnum arithmetic?

Question

I've found some techniques in other SO answers, but apparently I've been unable to convince SBCL to do inline fixnum arithmetic:

(declaim (optimize (speed 2) (safety 1)))

(declaim (ftype (function (fixnum fixnum) double-float) fixnumtest) (inline fixnumtest))
(defun fixnumtest (i j)
  (declare (type fixnum i j))
  (let* ((n (the fixnum (+ i j)))
         (n+1 (the fixnum (1+ n))))
    (declare (type fixnum n n+1))
    (/ 1.0d0 (the fixnum (* n n+1)) )
  )
)

(defun main () 
  (format t "~11,9F~%" (fixnumtest 2 3))
) 

:results in forced to do GENERIC-* (cost 30)

What else should I try?

$ sbcl --eval '(load (compile-file "play.lisp"))'
This is SBCL 1.5.1,
…
; compiling file "/opt/tmp/play.lisp" (written 16 OCT 2019 08:03:15 PM):
; compiling (DECLAIM (OPTIMIZE # ...))
; compiling (DECLAIM (FTYPE # ...) ...)
; compiling (DEFUN FIXNUMTEST ...)
; file: /opt/tmp/play.lisp
; in: DEFUN FIXNUMTEST
;     (* N N+1)
; 
; note: forced to do GENERIC-* (cost 30)
;       unable to do inline fixnum arithmetic (cost 4) because:
;       The result is a (VALUES
;                        (INTEGER -21267647932558653961849226946058125312
;                         21267647932558653961849226946058125312)
;                        &OPTIONAL), not a (VALUES FIXNUM &REST T).
;       unable to do inline (signed-byte 64) arithmetic (cost 5) because:
;       The result is a (VALUES
;                        (INTEGER -21267647932558653961849226946058125312
;                         21267647932558653961849226946058125312)
;                        &OPTIONAL), not a (VALUES (SIGNED-BYTE 64) &REST T).
;       etc.

Also, am I correct to think that doing float to pointer coercion (cost 13) is the ordinary consequence of returning a float from a function?

;     (DEFUN FIXNUMTEST (I J)
;       (DECLARE (TYPE FIXNUM I J))
;       (LET* ((N (THE FIXNUM #)) (N+1 (THE FIXNUM #)))
;         (DECLARE (TYPE FIXNUM N N+1))
;         (/ 1.0d0 (THE FIXNUM (* N N+1)))))
; --> PROGN SB-IMPL::%DEFUN SB-IMPL::%DEFUN SB-INT:NAMED-LAMBDA 
; ==>
;   #'(SB-INT:NAMED-LAMBDA FIXNUMTEST
;         (I J)
;       (DECLARE (SB-C::TOP-LEVEL-FORM))
;       (DECLARE (TYPE FIXNUM I J))
;       (BLOCK FIXNUMTEST
;         (LET* ((N #) (N+1 #))
;           (DECLARE (TYPE FIXNUM N N+1))
;           (/ 1.0d0 (THE FIXNUM #)))))
; 
; note: doing float to pointer coercion (cost 13) to "<return value>"

Answer 1

Well, the compiler is telling you the answer, perhaps in a slightly unhelpful way. If you have two fixnums then it is not the case that, for instance, adding them results in a fixnum: the type fixnum is not closed under arithmetic operations (not even under +, - and *, disregarding /).

From the SBCL manual:

The SBCL compiler treats type declarations differently from most other Lisp compilers. Under default compilation policy the compiler doesn’t blindly believe type declarations, but considers them assertions about the program that should be checked: all type declarations that have not been proven to always hold are asserted at runtime.

What you need to do if you want to compile machine arithmetic is to tell the compiler that the types it is using are good enough that it can know that the result types are good enough that they can be represented immediately.

Given the arithmetic you have in the function, and assuming a 64-bit implementation, then a good type is (signed-byte 31): it's tempting to use (signed-byte 32) but this fails, because you end up with something that is bigger than a (signed-byte 64).

So this code does not warn except for consing the final double float on return:

(deftype smallish-integer (&optional (bits 31))
  `(signed-byte ,bits))


(declaim (ftype (function (smallish-integer smallish-integer) double-float)
                fixnumtest)
         (inline fixnumtest))

(defun fixnumtest (i j)
  (declare (optimize (speed 2)))
  (declare (type smallish-integer i j))
  (let* ((n (+ i j))
         (n+1 (1+ n)))
    (/ 1.0d0 (* n n+1))))

It's worth noting that a (signed-byte 64) is quite a lot larger than a fixnum: this is OK, because within a function the compiler can cope with numbers which fit in registers even though they are bigger than fixnums.

I am not familiar enough with x64 assembler to check that all the arithmetic is compiled as machine instructions, but it looks like it is.

It may be possible to persuade the SBCL compiler that you don't care about getting the correct answer and that it should just do machine arithmetic even though it knows it may overflow. I have no idea how to do that.

Answer 2

Seems that the answer tfb provided allows the code snippet to be reduced a little more:

(declaim (optimize (speed 2)))

(deftype smallish-integer (&optional (bits 31))
  `(signed-byte ,bits))

(declaim (inline smallishtest))
(defun smallishtest (i j)
  (declare (type smallish-integer i j))
  (/ 1.0d0 (* (+ i j) (+ i j 1))))

(defun main () 
  (format t "~11,9F~%" (smallishtest 2 3))
)

:and still give only one compilation note:

; note: doing float to pointer coercion (cost 13) to "<return value>"

Then reduced just a little more:

(deftype smallish-integer (&optional (bits 31))
  `(signed-byte ,bits))

(declaim (inline smallishtest))
(defun smallishtest (i j)
  (declare (type smallish-integer i j))
  (/ 1.0d0 (* (+ i j) (+ i j 1))))

(defun main () 
  (format t "~11,9F~%" (smallishtest 2 3))
)

Answer 3

I found a good answer in the paper Efficient Hardware Arithmetic in Common Lisp. The key problem is well described by @tfb. Arithmetic operations may cause a value to go out of the range than can be represented by a fixed with integer.

Ok Way

The first way to resolve this is to declare the resulting type is still a fixnum. However, it if overflows the result is undefined:

(defun add-e (x y)
  (declare (type (unsigned-byte 32) x y))
  (the (unsigned-byte 32) (+ x y)))

Better Way

A better way is to use bitwise operations on the result:

(defun add-d (x y)
  (declare (type (unsigned-byte 32) x y))
  (logand (+ x y) #xffffffff))

Even if it overflows, the result is still what you would expect.

Modern compilers will optimize this away to seeing that the result lies within an acceptable range to use hardware representations. Here is quote from chapter 6.3 of the SBCL manual:

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.

Here is a link to the paper and the sbcl manual for more detail.