4.7 The compiler

4.7.1 The compiler translates to C

The ECL compiler is essentially a translator from Common-Lisp to C. Given a Lisp source file, the compiler first generates three intermediate files:

The ECL compiler then invokes the C compiler to compile the C-file into an object file. Finally, the contents of the Data-file is appended to the object file to make a Fasl-file. The generated Fasl-file can be loaded into the ECL system by the Common-Lisp function load. By default, the three intermediate files are deleted after the compilation, but, if asked, the compiler leaves them.

The merits of the use of C as the intermediate language are:

The demerits are:

4.7.2 The compiler mimics human C programmer

The format of the intermediate C code generated by the ECL compiler is the same as the hand-coded C code of the ECL source programs. For example, supposing that the Lisp source file contains the following function definition:

(defvar *delta* 2)
(defun add1 (x) (+ *delta* x))

The compiler generates the following intermediate C code.

/*      function definition for ADD1                                  */
/*      optimize speed 3, debug 0, space 0, safety 2                  */
static cl_object L1add1(cl_object v1x)
{
 cl_object env0 = ECL_NIL;
 const cl_env_ptr cl_env_copy = ecl_process_env();
 cl_object value0;
 ecl_cs_check(cl_env_copy,value0);
 {
TTL:
  value0 = ecl_plus(ecl_symbol_value(VV[0]),v1x);
  cl_env_copy->nvalues = 1;
  return value0;
 }
}

/*      initialization of this module                                 */
ECL_DLLEXPORT void init_fas_CODE(cl_object flag)
{
 const cl_env_ptr cl_env_copy = ecl_process_env();
 cl_object value0;
 cl_object *VVtemp;
 if (flag != OBJNULL){
 Cblock = flag;
 #ifndef ECL_DYNAMIC_VV
 flag->cblock.data = VV;
 #endif
 flag->cblock.data_size = VM;
 flag->cblock.temp_data_size = VMtemp;
 flag->cblock.data_text = compiler_data_text;
 flag->cblock.cfuns_size = compiler_cfuns_size;
 flag->cblock.cfuns = compiler_cfuns;
 flag->cblock.source = make_constant_base_string("test.lisp");
 return;}
 #ifdef ECL_DYNAMIC_VV
 VV = Cblock->cblock.data;
 #endif
 Cblock->cblock.data_text = (const cl_object *)"@EcLtAg:init_fas_CODE@";
 VVtemp = Cblock->cblock.temp_data;
 ECL_DEFINE_SETF_FUNCTIONS
  si_Xmake_special(VV[0]);
  if (ecl_boundp(cl_env_copy,VV[0])) { goto L2; }
  cl_set(VV[0],ecl_make_fixnum(2));
L2:;
  ecl_cmp_defun(VV[2]);                           /*  ADD1            */
}

The C function L1add1 implements the Lisp function add1. This relation is established by ecl_cmp_defun in the initialization function init_fas_CODE, which is invoked at load time. There, the vector VV consists of Lisp objects; VV[0] and VV[1] in this example hold the Lisp symbols *delta* and add1, while VV[2] holds the function object for add1, which is created during initialization of the module. VM in the definition of L1add1 is a C macro declared in the corresponding H-file. The actual value of VM is the number of value stack locations used by this module, i.e., 3 in this example. Thus the following macro definition is found in the H-file.

#define VM 3

4.7.3 Implementation of Compiled Closures

The ECL compiler takes two passes before it invokes the C compiler. The major role of the first pass is to detect function closures and to detect, for each function closure, those lexical objects (i.e., lexical variable, local function definitions, tags, and block-names) to be enclosed within the closure. This check must be done before the C code generation in the second pass, because lexical objects to be enclosed in function closures are treated in a different way from those not enclosed.

Ordinarily, lexical variables in a compiled function f are allocated on the C stack. However, if a lexical variable is to be enclosed in function closures, it is allocated on a list, called the "environment list", which is local to f. In addition, a local variable is created which points to the lexical variable’s location (within the environment list), so that the variable may be accessed through an indirection rather than by list traversal.

The environment list is a pushdown list: It is empty when f is called. An element is pushed on the environment list when a variable to be enclosed in closures is bound, and is popped when the binding is no more in effect. That is, at any moment during execution of f, the environment list contains those lexical variables whose binding is still in effect and which should be enclosed in closures. When a compiled closure is created during execution of f, the compiled code for the closure is coupled with the environment list at that moment to form the compiled closure.

Later, when the compiled closure is invoked, a pointer is set up to each lexical variable in the environment list, so that each object may be referenced through a memory indirection.

Let us see an example. Suppose the following function has been compiled.

(defun foo (x)
  (let ((a #'(lambda () (incf x)))
        (y x))
    (values a #'(lambda () (incf x y)))))

foo returns two compiled closures. The first closure increments x by one, whereas the second closure increments x by the initial value of x. Both closures return the incremented value of x.

>(multiple-value-setq (f g) (foo 10))
#<compiled-closure nil>

>(funcall f)
11

>(funcall g)
21

>

After this, the two compiled closures look like:

  second closure       y:                     x:
  |-------|------|      |-------|------|       |------|------| 
  |  **   |    --|----->|  10   |    --|------>|  21  | nil  |
  |-------|------|      |-------|------|       |------|------| 
  ^
  first closure             |
  |-------|------|          |
  |   *   |    --|----------| 
  |-------|------| 

  * : address of the compiled code for #'(lambda () (incf x))
  ** : address of the compiled code for #'(lambda () (incf x y))

4.7.4 Use of Declarations to Improve Efficiency

Declarations, especially type and function declarations, increase the efficiency of the compiled code. For example, for the following Lisp source file, with two Common-Lisp declarations added,

(eval-when (:compile-toplevel)
  (proclaim '(ftype (function (fixnum fixnum) fixnum) tak))
  (proclaim '(optimize (speed 3) (debug 0) (safety 0))))

(defun tak (x y)
  (declare (fixnum x y))
  (if (not (< y x))
    y
    (tak (tak (1- x) y)
         (tak (1- y) x))))

The compiler generates the following C code (Note that the tail-recursive call of tak was replaced by iteration):

/*      function definition for TAK                                   */
/*      optimize speed 3, debug 0, space 0, safety 0                  */
static cl_object L1tak(cl_object v1x, cl_object v2y)
{
 cl_object env0 = ECL_NIL;
 const cl_env_ptr cl_env_copy = ecl_process_env();
 cl_object value0;
 cl_fixnum v3x;
 cl_fixnum v4y;
 v3x = ecl_fixnum(v1x);
 v4y = ecl_fixnum(v2y);
TTL:
 if ((v4y)<(v3x)) { goto L1; }
 value0 = ecl_make_fixnum(v4y);
 cl_env_copy->nvalues = 1;
 return value0;
L1:;
 {
  cl_fixnum v5;
  {
   cl_fixnum v6;
   v6 = (v3x)-1;
   v5 = ecl_fixnum(L1tak(ecl_make_fixnum(v6), ecl_make_fixnum(v4y)));
  }
  {
   cl_fixnum v6;
   v6 = (v4y)-1;
   v4y = ecl_fixnum(L1tak(ecl_make_fixnum(v6), ecl_make_fixnum(v3x)));
  }
  v3x = v5;
 }
 goto TTL;
}

4.7.5 Inspecting generated C code

Common-Lisp defines a function disassemble, which is supposed to disassemble a compiled function and to display the assembler code. According to Common-Lisp: The Language,

This is primary useful for debugging the compiler, ..\\

This is, however, useless in our case, because we are not concerned with assembly language. Rather, we are interested in the C code generated by the ECL compiler. Thus the disassemble function in ECL accepts not-yet-compiled functions only and displays the translated C code.

> (defun add1 (x) (1+ x))

ADD1
> (disassemble *)

/*      function definition for ADD1                                  */
/*      optimize speed 3, debug 0, space 0, safety 2                  */
static cl_object L1add1(cl_object v1x)
{
 cl_object env0 = ECL_NIL;
 const cl_env_ptr cl_env_copy = ecl_process_env();
 cl_object value0;
 ecl_cs_check(cl_env_copy,value0);
 {
TTL:
  value0 = ecl_one_plus(v1x);
  cl_env_copy->nvalues = 1;
  return value0;
 }
}