Franz Inc Tech Corner

Support/Doc | About | Purchase | Advanced Search

Success
Resources
Learn More About Knowledge Graph Databases

An example showing how to get the compiler to inline

Many standard Common Lisp functions, particularly those which do simple calculations or access data from arrays or structures, can be compiled inline by the compiler. Inline compilation results in faster, often significantly faster run times as the function call and return overheads are saved.

But there are tricks to getting the compiler to inline, and there are tools which assist is expalining what the compiler is doing. In this note, we take a simple function with a call to the math function round, and try to get the call to round to inline. Here is the function:

(defun foo (x) 
   (declare (optimize (speed 3) (safety 0) (debug 0)) (double-float x)) 
   (round (* x x)))

round looks like a good candidate for inlining: the type of its argument is known and speed, safety, and debug have values calling for maximum speed. But when it is compiled and the compiled function is disassembled, we see that round was not inlined:

cl-user(10): (compile 'foo)
foo
nil
nil
cl-user(11): (disassemble 'foo)
;; disassembly of #<Function foo>
;; formals: x
;; constant vector:
0: round

;; code start: #x10003508c80:
   0: 48 83 ec 68    sub	rsp,$104
   4: 4c 89 74 24 08 movq	[rsp+8],r14
   9: f2 44 0f 10 6f movsd	xmm13,[rdi-10]
      f6 
  15: f2 45 0f 59 ed mulsd	xmm13,xmm13
  20: f2 45 0f 10 fd movsd	xmm15,xmm13
  25: 31 c0          xorl	eax,eax
  27: 41 ff 97 d7 03 call	*[r15+983]   ; sys::new-double-float
      00 00 
  34: 4c 89 7c 24 18 movq	[rsp+24],r15
  39: 48 8d 64 24 68 leaq	rsp,[rsp+104]
  44: 49 8b 6e 36    movq	rbp,[r14+54] ; round
  48: b0 08          movb	al,$8
  50: ff e3          jmp	*rbx
cl-user(11):

The line labeled 44 is the jump to the round function.

So what went wrong? Spoiler alert: there are two problems: first round returns two values and there is no indication whether both or just the first are needed. Second, the type of the first return value is not known. We know it is an integer but not whether it is a fixnum or a bignum. Without that information, the compiler cannot inline the call. (The user may not know whether the result will be a fixnum or a bignum, in which case inlining is not possible, but if the user knows the value will be a fixnum, then that information should be supplied.)

So how do we find out what to do? First, Allegro CL supports an :explain declaration (see the section Help with declarations: the :explain declaration in compiling.htm). Adding that declaraion with types :inlining and :types will cause the compiler to print out reports on what it is doing with respect the inlining and type propagation:

(compile
  (defun foo (x)
     (declare (optimize (speed 3) (safety 0) (debug 0)) (double-float x) 
        (:explain :types :inlining))
     (round (* x x))))
;;; Note: The compilation of (ROUND (* X X)) might be done more
;;;       efficiently if only one value is used from its call.
; While compiling FOO:
;Tgen1:Examined a (possibly unboxed) call to *_2OP with arguments:
;Targ2:  symeval X type (DOUBLE-FLOAT * *)
;Tinf1:     VARIABLE-information: LEXICAL: ((TYPE (DOUBLE-FLOAT * *)))
;Targ2:  symeval X type (DOUBLE-FLOAT * *)
;Tinf1:     VARIABLE-information: LEXICAL: ((TYPE (DOUBLE-FLOAT * *)))
;Tres1:   which returns a value of type (DOUBLE-FLOAT * *)
;Igen1:  Node: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Node: type is unboxable as DOUBLE-FLOAT
;Igen3:Attempt to inline an unboxed call to *_2OP while trusting declarations:
;Igen5:  Node: checking for notinline declaration for EXCL::*_2OP: none
;Igen1:  Arg0: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg0: type is unboxable as DOUBLE-FLOAT
;Igen1:  Arg1: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg1: type is unboxable as DOUBLE-FLOAT
;Igen4:Inline attempt succeeded.
;Igen8: Unboxed result must be boxed - consider expanding scope of unboxed forms.
;Tgen1:Examined a call to ROUND with arguments:
;Targ1:  call to *_2OP
 type (DOUBLE-FLOAT * *)
;Tres1:   which returns a value of type (INTEGER * *)
;Igen1:  Node: checking (INTEGER * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Node: type is not unboxable
;Igen3:Attempt to inline a boxed call to ROUND while trusting declarations:
;Igen5:  Node: checking for notinline declaration for ROUND: none
;Igen9:  No info available to inline ROUND as boxed
;Igen4:Inline attempt failed.
FOO
NIL
NIL
CL-USER(12):

The first note comments on the fact that round returns two values and the compiler could do better if it knew that only one value was required. So let us force a single value from round:

(compile
  (defun foo (x)
     (declare (optimize (speed 3) (safety 0) (debug 0)) (double-float x) 
        (:explain :types :inlining))
     (values (round (* x x)))))
; While compiling FOO:
;Tgen1:Examined a (possibly unboxed) call to *_2OP with arguments:
;Targ2:  symeval X type (DOUBLE-FLOAT * *)
;Tinf1:     VARIABLE-information: LEXICAL: ((TYPE (DOUBLE-FLOAT * *)))
;Targ2:  symeval X type (DOUBLE-FLOAT * *)
;Tinf1:     VARIABLE-information: LEXICAL: ((TYPE (DOUBLE-FLOAT * *)))
;Tres1:   which returns a value of type (DOUBLE-FLOAT * *)
;Igen1:  Node: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Node: type is unboxable as DOUBLE-FLOAT
;Igen3:Attempt to inline an unboxed call to *_2OP while trusting declarations:
;Igen5:  Node: checking for notinline declaration for EXCL::*_2OP: none
;Igen1:  Arg0: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg0: type is unboxable as DOUBLE-FLOAT
;Igen1:  Arg1: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg1: type is unboxable as DOUBLE-FLOAT
;Igen4:Inline attempt succeeded.
;Igen8: Unboxed result must be boxed - consider expanding scope of unboxed forms.
;Tgen1:Examined a call to ROUND_1RET with arguments:
;Targ1:  call to *_2OP
 type (DOUBLE-FLOAT * *)
;Tres1:   which returns a value of type (INTEGER * *)
;Igen1:  Node: checking (INTEGER * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Node: type is not unboxable
;Igen3:Attempt to inline a boxed call to ROUND_1RET while trusting declarations:
;Igen5:  Node: checking for notinline declaration for EXCL::ROUND_1RET:
;Igen5:  none
;Igen1:  Arg0: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg0: type is unboxable as DOUBLE-FLOAT
;Ityp1:  Node: looking for FIXNUM - failed
;Igen4:Inline attempt failed.
;Tgen1:Examined a call to VALUES with arguments:
;Targ1:  call to ROUND_1RET
 type (INTEGER * *)
;Tres1:   which returns a value of type T
;Igen1:  Node: checking T for implied unboxable type (floats, or
;Igen1:  machine-integer):
;Igen2:  Node: type is not unboxable
;Igen3:Attempt to inline a boxed call to VALUES while trusting declarations:
;Igen5:  Node: checking for notinline declaration for VALUES: none
;Igen4:Inline attempt succeeded.
FOO
NIL
NIL
CL-USER(13):

Progess but round_1ret is still not inlining (;Igen3:Attempt to inline a boxed call to ROUND_1RET while trusting declarations: [...] ;Ityp1: Node: looking for FIXNUM - failed ;Igen4:Inline attempt failed.) The compiler looked to see if the result was a fixnum and could not be sure. Also, because round_1ret is not inlining, its argument (the double-float (* x x) must be boxed. This is confiirmed by looking at the diaassembly:

CL-USER(13): (disassemble 'foo)
;; disassembly of #<Function FOO>
;; formals: X
;; constant vector:
0: EXCL::ROUND_1RET

;; code start: #x10001671aa0:
   0: 48 83 ec 68    sub	rsp,$104
   4: 4c 89 74 24 08 movq	[rsp+8],r14
   9: f2 44 0f 10 6f movsd	xmm13,[rdi-10]
      f6 
  15: f2 45 0f 59 ed mulsd	xmm13,xmm13
  20: f2 45 0f 10 fd movsd	xmm15,xmm13
  25: 31 c0          xorl	eax,eax
  27: 41 ff 97 d7 03 call	*[r15+983]      ; SYS::NEW-DOUBLE-FLOAT
      00 00 
  34: 49 8b 6e 36    movq	rbp,[r14+54]    ; EXCL::ROUND_1RET
  38: b0 08          movb	al,$8
  40: ff d3          call	*rbx
  42: f8             clc
  43: 4c 8b 74 24 78 movq	r14,[rsp+120]
  48: 4c 89 7c 24 18 movq	[rsp+24],r15
  53: 48 8d 64 24 68 leaq	rsp,[rsp+104]
  58: c3             ret
  59: 90             nop
CL-USER(14):

Now you have to decide whether the call to round will always return a fixnum. The is a program decision: it cannot be determined by examing this snippet of code. The question is, will round ever be called with a double-float value larger than 1 greater than most-positive-fixnum, meaning the absolute value of x is roughly bigger than the square root of that value. If you (the programmer) are sure that will not happen, then we can tell the compiler the result will be a fixnum:

(compile
  (defun foo (x)
     (declare (optimize (speed 3) (safety 0) (debug 0)) (double-float x) 
        (:explain :types :inlining))
     (values (the fixnum (round (* x x))))))
; While compiling FOO:
;Tgen1:Examined a (possibly unboxed) call to *_2OP with arguments:
;Targ2:  symeval X type (DOUBLE-FLOAT * *)
;Tinf1:     VARIABLE-information: LEXICAL: ((TYPE (DOUBLE-FLOAT * *)))
;Targ2:  symeval X type (DOUBLE-FLOAT * *)
;Tinf1:     VARIABLE-information: LEXICAL: ((TYPE (DOUBLE-FLOAT * *)))
;Tres1:   which returns a value of type (DOUBLE-FLOAT * *)
;Igen1:  Node: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Node: type is unboxable as DOUBLE-FLOAT
;Igen3:Attempt to inline an unboxed call to *_2OP while trusting declarations:
;Igen5:  Node: checking for notinline declaration for EXCL::*_2OP: none
;Igen1:  Arg0: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg0: type is unboxable as DOUBLE-FLOAT
;Igen1:  Arg1: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg1: type is unboxable as DOUBLE-FLOAT
;Igen4:Inline attempt succeeded.
;Tgen1:Examined a call to ROUND_1RET with arguments:
;Targ1:  call to *_2OP
 type (DOUBLE-FLOAT * *)
;Tres1:   which returns a value in fixnum range of type
;Tres1:   (INTEGER -1152921504606846976 1152921504606846975)
;Igen1:  Node: checking
;Igen1:  (INTEGER -1152921504606846976 1152921504606846975) for implied
;Igen1:  unboxable type (floats, or machine-integer):
;Igen2:  Node: type is not unboxable
;Igen3:Attempt to inline a boxed call to ROUND_1RET while trusting declarations:
;Igen5:  Node: checking for notinline declaration for EXCL::ROUND_1RET:
;Igen5:  none
;Igen1:  Arg0: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg0: type is unboxable as DOUBLE-FLOAT
;Ityp1:  Node: looking for FIXNUM - got
;Ityp1:  (INTEGER -1152921504606846976 1152921504606846975)
;Igen4:Inline attempt succeeded.
;Tgen1:Examined a call to VALUES with arguments:
;Targ1:  call to ROUND_1RET
 type in fixnum range (INTEGER -1152921504606846976 1152921504606846975)
;Tres1:   which returns a value of type T
;Igen1:  Node: checking T for implied unboxable type (floats, or
;Igen1:  machine-integer):
;Igen2:  Node: type is not unboxable
;Igen3:Attempt to inline a boxed call to VALUES while trusting declarations:
;Igen5:  Node: checking for notinline declaration for VALUES: none
;Igen4:Inline attempt succeeded.
FOO
NIL
NIL
CL-USER(15):

Now the inlining of round_1op has succeeded, and the Igen8 message has gone away. And the disassembled code:

CL-USER(15): (disassemble 'foo)
;; disassembly of #<Function FOO>
;; formals: X

;; code start: #x1000167a300:
   0: 48 83 ec 78    sub	rsp,$120
   4: 4c 89 74 24 08 movq	[rsp+8],r14
   9: f2 44 0f 10 6f movsd	xmm13,[rdi-10]
      f6 
  15: f2 45 0f 59 ed mulsd	xmm13,xmm13
  20: 0f ae 5c 24 70 stmxcsrl	[rsp+112]
  25: 0f ae 5c 24 74 stmxcsrl	[rsp+116]
  30: 81 64 24 70 ff andl	[rsp+112],$40959
      9f 00 00 
  38: 0f ae 54 24 70 ldmxcsrl	[rsp+112]
  43: f2 49 0f 2d c5 cvtsd2siq	rax,xmm13
  48: 0f ae 54 24 74 ldmxcsrl	[rsp+116]
  53: 48 c1 e0 03    sal	rax,$3
  57: 49 89 c5       movq	r13,rax
  60: 4c 89 ef       movq	rdi,r13
  63: f8             clc
  64: 4c 8b b4 24 88 movq	r14,[rsp+136]
      00 00 00 
  72: 4c 89 7c 24 18 movq	[rsp+24],r15
  77: 48 8d 64 24 78 leaq	rsp,[rsp+120]
  82: c3             ret
  83: 90             nop
CL-USER(16):

also does no consing. A slight rewrite gets rid of the call to values and a simpler set of explanations:

CL-USER(16): (compile
              (defun foo (x)
                (declare (optimize (speed 3) (safety 0) (debug 0)) 
                         (double-float x) (:explain :types :inlining))
                (let ((res (the fixnum (round (* x x)))))
                   res)))
; While compiling FOO:
;Tgen1:Examined a (possibly unboxed) call to *_2OP with arguments:
;Targ2:  symeval X type (DOUBLE-FLOAT * *)
;Tinf1:     VARIABLE-information: LEXICAL: ((TYPE (DOUBLE-FLOAT * *)))
;Targ2:  symeval X type (DOUBLE-FLOAT * *)
;Tinf1:     VARIABLE-information: LEXICAL: ((TYPE (DOUBLE-FLOAT * *)))
;Tres1:   which returns a value of type (DOUBLE-FLOAT * *)
;Igen1:  Node: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Node: type is unboxable as DOUBLE-FLOAT
;Igen3:Attempt to inline an unboxed call to *_2OP while trusting declarations:
;Igen5:  Node: checking for notinline declaration for EXCL::*_2OP: none
;Igen1:  Arg0: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg0: type is unboxable as DOUBLE-FLOAT
;Igen1:  Arg1: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg1: type is unboxable as DOUBLE-FLOAT
;Igen4:Inline attempt succeeded.
;Tgen1:Examined a call to ROUND_1RET with arguments:
;Targ1:  call to *_2OP
 type (DOUBLE-FLOAT * *)
;Tres1:   which returns a value in fixnum range of type
;Tres1:   (INTEGER -1152921504606846976 1152921504606846975)
;Igen1:  Node: checking
;Igen1:  (INTEGER -1152921504606846976 1152921504606846975) for implied
;Igen1:  unboxable type (floats, or machine-integer):
;Igen2:  Node: type is not unboxable
;Igen3:Attempt to inline a boxed call to ROUND_1RET while trusting declarations:
;Igen5:  Node: checking for notinline declaration for EXCL::ROUND_1RET:
;Igen5:  none
;Igen1:  Arg0: checking (DOUBLE-FLOAT * *) for implied unboxable type
;Igen1:  (floats, or machine-integer):
;Igen2:  Arg0: type is unboxable as DOUBLE-FLOAT
;Ityp1:  Node: looking for FIXNUM - got
;Ityp1:  (INTEGER -1152921504606846976 1152921504606846975)
;Igen4:Inline attempt succeeded.
FOO
NIL
NIL
CL-USER(117): (disassemble *)
;; disassembly of #<Function FOO>
;; formals: X

;; code start: #x10001683ab0:
   0: 48 83 ec 78    sub	rsp,$120
   4: 4c 89 74 24 08 movq	[rsp+8],r14
   9: f2 44 0f 10 6f movsd	xmm13,[rdi-10]
      f6 
  15: f2 45 0f 59 ed mulsd	xmm13,xmm13
  20: 0f ae 5c 24 70 stmxcsrl	[rsp+112]
  25: 0f ae 5c 24 74 stmxcsrl	[rsp+116]
  30: 81 64 24 70 ff andl	[rsp+112],$40959
      9f 00 00 
  38: 0f ae 54 24 70 ldmxcsrl	[rsp+112]
  43: f2 49 0f 2d c5 cvtsd2siq	rax,xmm13
  48: 0f ae 54 24 74 ldmxcsrl	[rsp+116]
  53: 48 c1 e0 03    sal	rax,$3
  57: 49 89 c5       movq	r13,rax
  60: 4c 89 ef       movq	rdi,r13
  63: f8             clc
  64: 4c 8b b4 24 88 movq	r14,[rsp+136]
      00 00 00 
  72: 4c 89 7c 24 18 movq	[rsp+24],r15
  77: 48 8d 64 24 78 leaq	rsp,[rsp+120]
  82: c3             ret
  83: 90             nop
CL-USER(18):

But be warned: if a call to round does return a bignum, the result will be very wrong:

cl-user(19): (setq big (float (+ 5 most-positive-fixnum) 1.0d0))
1.152921504606847d+18
cl-user(20): (foo big)
0
cl-user(21):