Compiler
********

This chapter will discuss most compiler issues other than efficiency, including compiler error messages, the SBCL compiler's unusual approach to type safety in the presence of type declarations, the effects of various compiler optimization policies, and the way that inlining and open coding may cause optimized code to differ from a naive translation. Efficiency issues are sufficiently varied and separate that they have their own chapter, Efficiency.

Diagnostic Messages
===================

Controlling Verbosity
---------------------

The compiler can be quite verbose in its diagnostic reporting, rather more then some users would prefer -- the amount of noise emitted can be controlled, however.

To control emission of compiler diagnostics (of any severity other than error: see Diagnostic Severity) use the sb-ext:muffle-conditions and sb-ext:unmuffle-conditions declarations, specifying the type of condition that is to be muffled (the muffling is done using an associated muffle-warning restart).

Global control:

     ;;; Muffle compiler-notes globally
     (declaim (sb-ext:muffle-conditions sb-ext:compiler-note))

Local control:

     ;;; Muffle compiler-notes based on lexical scope
     (defun foo (x)
       (declare (optimize speed) (fixnum x)
                (sb-ext:muffle-conditions sb-ext:compiler-note))
       (values (* x 5) ; no compiler note from this
         (locally
           (declare (sb-ext:unmuffle-conditions sb-ext:compiler-note))
           ;; this one gives a compiler note
           (* x -5))))

 -- Declaration: sb-ext:muffle-conditions
     Syntax: type*

     Muffles the diagnostic messages that would be caused by compile-time signals of given types.

 -- Declaration: sb-ext:unmuffle-conditions
     Syntax: type*

     Cancels the effect of a previous sb-ext:muffle-condition declaration.

Various details of how the compiler messages are printed can be controlled via the alist sb-ext:*compiler-print-variable-alist*.

     [file var-sb-ext-star-compiler-print-variable-alist-star.texinfo not included]

For information about muffling warnings signaled outside of the compiler, see Customization Hooks for Users.

Diagnostic Severity
-------------------

There are four levels of compiler diagnostic severity:

 1. error

 2. warning

 3. style warning

 4. note

The first three levels correspond to condition classes which are defined in the ANSI standard for Common Lisp and which have special significance to the compile and compile-file functions. These levels of compiler error severity occur when the compiler handles conditions of these classes.

The fourth level of compiler error severity, note, corresponds to the sb-ext:compiler-note, and is used for problems which are too mild for the standard condition classes, typically hints about how efficiency might be improved. The sb-ext:code-deletion-note, a subtype of compiler-note, is signalled when the compiler deletes user-supplied code after proving that the code in question is unreachable.

Future work for SBCL includes expanding this hierarchy of types to allow more fine-grained control over emission of diagnostic messages.

     [file condition-sb-ext-compiler-note.texinfo not included]
     [file condition-sb-ext-code-deletion-note.texinfo not included]

Understanding Compile Diagnostics
---------------------------------

The messages emitted by the compiler contain a lot of detail in a terse format, so they may be confusing at first. The messages will be illustrated using this example program:

     (defmacro zoq (x)
       `(roq (ploq (+ ,x 3))))

     (defun foo (y)
       (declare (symbol y))
       (zoq y))

The main problem with this program is that it is trying to add 3 to a symbol. Note also that the functions roq and ploq aren't defined anywhere.

The Parts of a Compiler Diagnostic
..................................

When processing this program, the compiler will produce this warning:

     ; file: /tmp/foo.lisp
     ; in: DEFUN FOO
     ;     (ZOQ Y)
     ; --> ROQ PLOQ
     ; ==>
     ;   (+ Y 3)
     ;
     ; caught WARNING:
     ;   Asserted type NUMBER conflicts with derived type (VALUES SYMBOL &OPTIONAL).

In this example we see each of the six possible parts of a compiler diagnostic:

 1. file: /tmp/foo.lisp This is the name of the file that the compiler read the relevant code from.  The file name is displayed because it may not be immediately obvious when there is an error during compilation of a large system, especially when with-compilation-unit is used to delay undefined warnings.

 2. in: DEFUN FOO This is the definition top level form responsible for the diagnostic. It is obtained by taking the first two elements of the enclosing form whose first element is a symbol beginning with ``def''. If there is no such enclosing ``def'' form, then the outermost form is used. If there are multiple def forms, then they are all printed from the outside in, separated by =>'s. In this example, the problem was in the defun for foo.

 3. (ZOQ Y) This is the original source form responsible for the diagnostic. Original source means that the form directly appeared in the original input to the compiler, i.e. in the lambda passed to compile or in the top level form read from the source file. In this example, the expansion of the zoq macro was responsible for the message.

 4. --> ROQ PLOQ This is the processing path that the compiler used to produce the code that caused the message to be emitted. The processing path is a representation of the evaluated forms enclosing the actual source that the compiler encountered when processing the original source. The path is the first element of each form, or the form itself if the form is not a list. These forms result from the expansion of macros or source-to-source transformation done by the compiler. In this example, the enclosing evaluated forms are the calls to roq and ploq. These calls resulted from the expansion of the zoq macro.

 5. ==> (+ Y 3) This is the actual source responsible for the diagnostic. If the actual source appears in the explanation, then we print the next enclosing evaluated form, instead of printing the actual source twice. (This is the form that would otherwise have been the last form of the processing path.) In this example, the problem is with the evaluation of the reference to the variable y.

 6. caught WARNING: Asserted type NUMBER conflicts with derived type (VALUES SYMBOL &OPTIONAL).  This is the explanation of the problem. In this example, the problem is that, while the call to + requires that its arguments are all of type number, the compiler has derived that y will evaluate to a symbol.  Note that (VALUES SYMBOL &OPTIONAL) expresses that y evaluates to precisely one value.

Note that each part of the message is distinctively marked:

  * file: and in: mark the file and definition, respectively.

  * The original source is an indented form with no prefix.

  * Each line of the processing path is prefixed with -->

  * The actual source form is indented like the original source, but is marked by a preceding ==> line.

  * The explanation is prefixed with the diagnostic severity, which can be caught ERROR:, caught WARNING:, caught STYLE-WARNING:, or note:.

Each part of the message is more specific than the preceding one. If consecutive messages are for nearby locations, then the front part of the messages would be the same. In this case, the compiler omits as much of the second message as in common with the first. For example:

     ; file: /tmp/foo.lisp
     ; in: DEFUN FOO
     ;     (ZOQ Y)
     ; --> ROQ
     ; ==>
     ;   (PLOQ (+ Y 3))
     ;
     ; caught STYLE-WARNING:
     ;   undefined function: PLOQ

     ; ==>
     ;   (ROQ (PLOQ (+ Y 3)))
     ;
     ; caught STYLE-WARNING:
     ;   undefined function: ROQ

In this example, the file, definition and original source are identical for the two messages, so the compiler omits them in the second message. If consecutive messages are entirely identical, then the compiler prints only the first message, followed by: [Last message occurs REPEATS times] where REPEATS is the number of times the message was given.

If the source was not from a file, then no file line is printed. If the actual source is the same as the original source, then the processing path and actual source will be omitted. If no forms intervene between the original source and the actual source, then the processing path will also be omitted.

The Original and Actual Source
..............................

The original source displayed will almost always be a list. If the actual source for an message is a symbol, the original source will be the immediately enclosing evaluated list form. So even if the offending symbol does appear in the original source, the compiler will print the enclosing list and then print the symbol as the actual source (as though the symbol were introduced by a macro.)

When the actual source is displayed (and is not a symbol), it will always be code that resulted from the expansion of a macro or a source-to-source compiler optimization. This is code that did not appear in the original source program; it was introduced by the compiler.

Keep in mind that when the compiler displays a source form in an diagnostic message, it always displays the most specific (innermost) responsible form. For example, compiling this function

     (defun bar (x)
       (let (a)
         (declare (fixnum a))
         (setq a (foo x))
         a))

gives this error message

     ; file: /tmp/foo.lisp
     ; in: DEFUN BAR
     ;     (LET (A)
     ;     (DECLARE (FIXNUM A))
     ;     (SETQ A (FOO X))
     ;     A)
     ;
     ; caught WARNING:
     ;   Asserted type FIXNUM conflicts with derived type (VALUES NULL &OPTIONAL).

This message is not saying ``there is a problem somewhere in this let'' -- it is saying that there is a problem with the let itself. In this example, the problem is that a's nil initial value is not a fixnum.

The Processing Path
...................

The processing path is mainly useful for debugging macros, so if you don't write macros, you can probably ignore it. Consider this example:

     (defun foo (n)
       (dotimes (i n *undefined*)))

Compiling results in this error message:

     ; in: DEFUN FOO
     ;     (DOTIMES (I N *UNDEFINED*))
     ; --> DO BLOCK LET TAGBODY RETURN-FROM
     ; ==>
     ;   (PROGN *UNDEFINED*)
     ;
     ; caught WARNING:
     ;   undefined variable: *UNDEFINED*

Note that do appears in the processing path. This is because dotimes expands into:

     (do ((i 0 (1+ i)) (#:g1 n))
         ((>= i #:g1) *undefined*)
       (declare (type unsigned-byte i)))

The rest of the processing path results from the expansion of do:

     (block nil
       (let ((i 0) (#:g1 n))
         (declare (type unsigned-byte i))
         (tagbody (go #:g3)
           #:g2    (psetq i (1+ i))
           #:g3    (unless (>= i #:g1) (go #:g2))
           (return-from nil (progn *undefined*)))))

In this example, the compiler descended into the block, let, tagbody and return-from to reach the progn printed as the actual source. This is a place where the ``actual source appears in explanation'' rule was applied. The innermost actual source form was the symbol *undefined* itself, but that also appeared in the explanation, so the compiler backed out one level.

Handling of Types
=================

One of the most important features of the SBCL compiler (similar to the original CMUCL compiler, also known as Python) is its fairly sophisticated understanding of the Common Lisp type system and its conservative approach to the implementation of type declarations.

These two features reward the use of type declarations throughout development, even when high performance is not a concern. Also, as discussed in the chapter on performance (see Efficiency), the use of appropriate type declarations can be very important for performance as well.

The SBCL compiler also has a greater knowledge of the Common Lisp type system than other compilers. Support is incomplete only for types involving the satisfies type specifier.

Declarations as Assertions
--------------------------

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.

     Remaining bugs in the compiler's handling of types unfortunately provide some exceptions to this rule, see Implementation Limitations.

CLOS slot types form a notable exception. Types declared using the :type slot option in defclass are asserted if and only if the class was defined in safe code and the slot access location is in safe code as well. This laxness does not pose any internal consistency issues, as the CLOS slot types are not available for the type inferencer, nor do CLOS slot types provide any efficiency benefits.

There are three type checking policies available in SBCL, selectable via optimize declarations.

Full Type Checks
     All declarations are considered assertions to be checked at runtime, and all type checks are precise. The default compilation policy provides full type checks.

     Used when (or (>= safety 2) (>= safety speed 1)).

Weak Type Checks
     Declared types may be simplified into faster to check supertypes: for example, (or (integer -17 -7) (integer 7 17)) is simplified into (integer -17 17).

     Note: it is relatively easy to corrupt the heap when weak type checks are used if the program contains type-errors.

     Used when (and (< safety 2) (< safety speed))

No Type Checks
     All declarations are believed without assertions. Also disables argument count and array bounds checking.

     Note: any type errors in code where type checks are not performed are liable to corrupt the heap.

     Used when (= safety 0).

Precise Type Checking
---------------------

Precise checking means that the check is done as though typep had been called with the exact type specifier that appeared in the declaration.

If a variable is declared to be (integer 3 17) then its value must always be an integer between 3 and 17. If multiple type declarations apply to a single variable, then all the declarations must be correct; it is as though all the types were intersected producing a single and type specifier.

To gain maximum benefit from the compiler's type checking, you should always declare the types of function arguments and structure slots as precisely as possible. This often involves the use of or, member, and other list-style type specifiers.

Getting Existing Programs to Run
--------------------------------

Since SBCL's compiler does much more comprehensive type checking than most Lisp compilers, SBCL may detect type errors in programs that have been debugged using other compilers. These errors are mostly incorrect declarations, although compile-time type errors can find actual bugs if parts of the program have never been tested.

Some incorrect declarations can only be detected by run-time type checking. It is very important to initially compile a program with full type checks (high safety optimization) and then test this safe version. After the checking version has been tested, then you can consider weakening or eliminating type checks.  This applies even to previously debugged programs, because the SBCL compiler does much more type inference than other Common Lisp compilers, so an incorrect declaration can do more damage.

The most common problem is with variables whose constant initial value doesn't match the type declaration. Incorrect constant initial values will always be flagged by a compile-time type error, and they are simple to fix once located. Consider this code fragment:

     (prog (foo)
       (declare (fixnum foo))
       (setq foo ...)
       ...)

Here foo is given an initial value of nil, but is declared to be a fixnum.  Even if it is never read, the initial value of a variable must match the declared type.  There are two ways to fix this problem. Change the declaration

     (prog (foo)
       (declare (type (or fixnum null) foo))
       (setq foo ...)
       ...)

or change the initial value

     (prog ((foo 0))
       (declare (fixnum foo))
       (setq foo ...)
       ...)

It is generally preferable to change to a legal initial value rather than to weaken the declaration, but sometimes it is simpler to weaken the declaration than to try to make an initial value of the appropriate type.

Another declaration problem occasionally encountered is incorrect declarations on defmacro arguments. This can happen when a function is converted into a macro. Consider this macro:

     (defmacro my-1+ (x)
       (declare (fixnum x))
       `(the fixnum (1+ ,x)))

Although legal and well-defined Common Lisp code, this meaning of this definition is almost certainly not what the writer intended. For example, this call is illegal:

     (my-1+ (+ 4 5))

This call is illegal because the argument to the macro is (+ 4 5), which is a list, not a fixnum.  Because of macro semantics, it is hardly ever useful to declare the types of macro arguments.  If you really want to assert something about the type of the result of evaluating a macro argument, then put a the in the expansion:

     (defmacro my-1+ (x)
       `(the fixnum (1+ (the fixnum ,x))))

In this case, it would be stylistically preferable to change this macro back to a function and declare it inline.

Some more subtle problems are caused by incorrect declarations that can't be detected at compile time.  Consider this code:

     (do ((pos 0 (position #\a string :start (1+ pos))))
       ((null pos))
       (declare (fixnum pos))
       ...)

Although pos is almost always a fixnum, it is nil at the end of the loop. If this example is compiled with full type checks (the default), then running it will signal a type error at the end of the loop. If compiled without type checks, the program will go into an infinite loop (or perhaps position will complain because (1+ nil) isn't a sensible start.) Why? Because if you compile without type checks, the compiler just quietly believes the type declaration. Since the compiler believes that pos is always a fixnum, it believes that pos is never nil, so (null pos) is never true, and the loop exit test is optimized away. Such errors are sometimes flagged by unreachable code notes, but it is still important to initially compile and test any system with full type checks, even if the system works fine when compiled using other compilers.

In this case, the fix is to weaken the type declaration to (or fixnum null)  (Actually, this declaration is unnecessary in SBCL, since it already knows that position returns a non-negative fixnum or nil.).

Note that there is usually little performance penalty for weakening a declaration in this way. Any numeric operations in the body can still assume that the variable is a fixnum, since nil is not a legal numeric argument. Another possible fix would be to say:

     (do ((pos 0 (position #\a string :start (1+ pos))))
         ((null pos))
       (let ((pos pos))
         (declare (fixnum pos))
         ...))

This would be preferable in some circumstances, since it would allow a non-standard representation to be used for the local pos variable in the loop body.

Implementation Limitations
--------------------------

Ideally, the compiler would consider all type declarations to be assertions, so that adding type declarations to a program, no matter how incorrect they might be, would never cause undefined behavior. However, the compiler is known to fall short of this goal in two areas:

  * Proclaimed constraints on argument and result types of a function are supposed to be checked by the function. If the function type is proclaimed before function definition, type checks are inserted by the compiler, but the standard allows the reversed order, in which case the compiler will trust the declaration.

  * The compiler cannot check types of an unknown number of values; if the number of generated values is unknown, but the number of consumed is known, only consumed values are checked.

     For example,

          (defun foo (x)
            (the integer (bar x)))

     causes the following compiler diagnostic to be emitted:

          ; note: type assertion too complex to check:
          ;  (VALUES INTEGER &REST T).

     A partial workaround is instead write:

          (defun foo (x)
            (the (values integer &optional) (bar x)))

These are important issues, but are not necessarily easy to fix, so they may, alas, remain in the system for a while.

Compiler Policy
===============

Compiler policy is controlled by the optimize declaration, supporting all ANSI optimization qualities (debug, safety, space, and speed). (A deprecated extension sb-ext:inhibit-warnings is still supported, but liable to go away at any time.)

For effects of various optimization qualities on type-safety and debuggability see Declarations as Assertions and Debugger Policy Control.

Ordinarily, when the speed quality is high, the compiler emits notes to notify the programmer about its inability to apply various optimizations. For selective muffling of these notes see Controlling Verbosity.

The value of space mostly influences the compiler's decision whether to inline operations, which tend to increase the size of programs. Use the value 0 with caution, since it can cause the compiler to inline operations so indiscriminately that the net effect is to slow the program by causing cache misses or even swapping.

Compiler Errors
===============

Type Errors at Compile Time
---------------------------

If the compiler can prove at compile time that some portion of the program cannot be executed without a type error, then it will give a warning at compile time.

It is possible that the offending code would never actually be executed at run-time due to some higher level consistency constraint unknown to the compiler, so a type warning doesn't always indicate an incorrect program.

For example, consider this code fragment:

     (defun raz (foo)
       (let ((x (case foo
                   (:this 13)
                   (:that 9)
                   (:the-other 42))))
         (declare (fixnum x))
         (foo x)))

Compilation produces this warning:

     ; in: DEFUN RAZ
     ;     (CASE FOO (:THIS 13) (:THAT 9) (:THE-OTHER 42))
     ; --> LET COND IF COND IF COND IF
     ; ==>
     ;   (COND)
     ;
     ; caught WARNING:
     ;   This is not a FIXNUM:
     ;   NIL

In this case, the warning means that if foo isn't any of :this, :that or :the-other, then x will be initialized to nil, which the fixnum declaration makes illegal. The warning will go away if ecase is used instead of case, or if :the-other is changed to t.

This sort of spurious type warning happens moderately often in the expansion of complex macros and in inline functions. In such cases, there may be dead code that is impossible to correctly execute. The compiler can't always prove this code is dead (could never be executed), so it compiles the erroneous code (which will always signal an error if it is executed) and gives a warning.

Errors During Macroexpansion
----------------------------

The compiler handles errors that happen during macroexpansion, turning them into compiler errors. If you want to debug the error (to debug a macro), you can set *break-on-signals* to error. For example, this definition:

     (defun foo (e l)
       (do ((current l (cdr current))
            ((atom current) nil))
           (when (eq (car current) e) (return current))))

gives this error:

     ; in: DEFUN FOO
     ;     (DO ((CURRENT L (CDR CURRENT))
     ;        ((ATOM CURRENT) NIL))
     ;       (WHEN (EQ (CAR CURRENT) E) (RETURN CURRENT)))
     ;
     ; caught ERROR:
     ;   (in macroexpansion of (DO # #))
     ;   (hint: For more precise location, try *BREAK-ON-SIGNALS*.)
     ;   DO step variable is not a symbol: (ATOM CURRENT)

Read Errors
-----------

SBCL's compiler does not attempt to recover from read errors when reading a source file, but instead just reports the offending character position and gives up on the entire source file.

Open Coding and Inline Expansion
================================

Since Common Lisp forbids the redefinition of standard functions, the compiler can have special knowledge of these standard functions embedded in it. This special knowledge is used in various ways (open coding, inline expansion, source transformation), but the implications to the user are basically the same:

  * Attempts to redefine standard functions may be frustrated, since the function may never be called. Although it is technically illegal to redefine standard functions, users sometimes want to implicitly redefine these functions when they are debugging using the trace macro.  Special-casing of standard functions can be inhibited using the notinline declaration, but even then some phases of analysis such as type inferencing are applied by the compiler.

  * The compiler can have multiple alternate implementations of standard functions that implement different trade-offs of speed, space and safety.  This selection is based on the compiler policy, Compiler Policy.

When a function call is open coded, inline code whose effect is equivalent to the function call is substituted for that function call. When a function call is closed coded, it is usually left as is, although it might be turned into a call to a different function with different arguments. As an example, if nthcdr were to be open coded, then

     (nthcdr 4 foobar)

might turn into

     (cdr (cdr (cdr (cdr foobar))))

or even

     (do ((i 0 (1+ i))
       (list foobar (cdr foobar)))
       ((= i 4) list))

If nth is closed coded, then

     (nth x l)

might stay the same, or turn into something like

     (car (nthcdr x l))

In general, open coding sacrifices space for speed, but some functions (such as car) are so simple that they are always open-coded. Even when not open-coded, a call to a standard function may be transformed into a different function call (as in the last example) or compiled as static call. Static function call uses a more efficient calling convention that forbids redefinition.

Interpreter
===========

By default SBCL implements eval by calling the native code compiler. SBCL also includes an interpreter for use in special cases where using the compiler is undesirable, for example due to compilation overhead. Unlike in some other Lisp implementations, in SBCL interpreted code is not safer or more debuggable than compiled code.

Switching between the compiler and the interpreter is done using the special variable sb-ext:*evaluator-mode*. As of 0.9.17, valid values for sb-ext:*evaluator-mode* are :compile and :interpret.