Learn Shen
Community Wiki
OS Kernel
OS Library
Shen Professional


The Griffon Compiler
1. Introduction

The Griffon compiler is the successor to the Merlin compiler which was found in the last marks of Qi. Both compilers were named after engines that powered the WWII Spitfire fighter aircraft. The Merlin powered all variants of the Spitfire up to the mark IX and the more powerful Griffon powered the later marks up to the mark XXIV.

The Griffon is built into the SP image; it is not downloaded from the web.

The Griffon compiler optimises certain code patterns where patterns 'overlap'. That is to say list destructuring and token recognition are repeated between different patterns in different rules within the same function.

We will look at an example in the following sections.

1. Introduction

2. Motivation

3 Inlining and Expansion

3.1 Inlining
3.2 Expansion

4. The Action of the Griffon on the Object Code

5. Choosing a Compiler Setting

2. Motivation

Consider the Shen definition in figure 1.

(define f
    {(list symbol) --> symbol}
      [a] -> a
      [a b] -> b
      [a b c] -> c)      

The corresponding KLambda is:

(defun f (V1925)
 (cond ((and (cons? V1925) 
              (and (= a (hd V1925)) 
                   (= () (tl V1925)))) 
       ((and (cons? V1925)
         (and (= a (hd V1925))
              (and (cons? (tl V1925))
                   (and (= b (hd (tl V1925))) 
                        (= () (tl (tl V1925)))))))
       ((and (cons? V1925)
             (and (= a (hd V1925))
                  (and (cons? (tl V1925))
                       (and (= b (hd (tl V1925)))
                            (and (cons? (tl (tl V1925)))
                                 (and (= c (hd (tl (tl V1925))))
                                      (= () (tl (tl (tl V1925))))))))))
  (true (shen.f_error f))))      

This code is not optimal; several tests like (cons? V1925) are potentially repeated in the course of evaluation. The problem arises from the overlapping patterns in the orginal definition which generate repeated tests. TBoS 3rd edition remarks (p 180).

.... KLambda code is not factorised and the optimisation of factorisation is deferred to a platform level.  Efficient factorisation relies on having a platform which can jump out of the flow of control and direct it to the procedural code under some label or heading ...using the notorious goto.  The resulting code [is] highly unreadable, but so efficient than faster code [can] only be written by a Lisp programmer with considerable effort.

The motivation of the Griffon compiler is to factorise these repeated tests in the object code by replacing code sections with GOTO calls.

3. Inlining and Expansion

The Griffon depends for its optimisations on two operations: inlining and expansion, and the degree to which both operations are carried out is determined by the user. The SP top level contains two entries labelled inline and expand which are both set to 0 (the default value). At these settings the Griffon is not activated. Changing the values in these entries to a positive integer invokes the Griffon. We will explain these two operations.

3.1 Inlining

Positive values for expand or for inline cause Shen to search for overlapping patterns in pattern matching and to expand code in search of optimisations. These optimisations may result in the generation of GOTO calls.

The inline setting causes the compiler to inline GOTO calls to their actual procedures which enables certain local optimisations to be performed by bringing these procedures within the scope of local assignments which prevent the repeated evaluation of expressions within the body of of the procedure. The value of this key determines the maximum number of inline replacements allowed wrt any procedure.

3.2 Expansion

Expansion causes Shen to trade (if (and p q) r s) for (if p (if q r s) s) to a depth equal to the expand setting. Both inlining and expansion create optimisation opportunities at the expense of repeating code.

4. The Action of the Griffon on the CL Object Code

A good way of appreciating the action of the Griffin is to observe the object code produced from the definition in figure 1 at different compiler settings. First inline = expansion = 0.

(DEFUN f (V1925)                \\ version 1                  
   (COND ((AND (CONSP V1925) 
                (AND (EQ (QUOTE a) (CAR V1925)) 
                     (NULL (CDR V1925)))) (QUOTE a)) 
           ((AND (CONSP V1925) 
                 (AND (EQ (QUOTE a) (CAR V1925)) 
                      (AND (CONSP (CDR V1925)) 
                           (AND (EQ (QUOTE b) 
                                    (CAR (CDR V1925)))
                                (NULL (CDR (CDR V1925))))))) 
            (QUOTE b)) 
          ((AND (CONSP V1925) 
                (AND (EQ (QUOTE a) (CAR V1925)) 
                     (AND (CONSP (CDR V1925)) 
                          (AND (EQ (QUOTE b) (CAR (CDR V1925))) 
                               (AND (CONSP (CDR (CDR V1925))) 
                                 (AND (EQ (QUOTE c) 
                                      (CAR (CDR (CDR V1925)))) 
                           (NULL (CDR (CDR (CDR V1925)))))))))) 
            (QUOTE c)) 
         (T (shen.f_error (QUOTE f)))))      

Second inline = expansion = 1

(DEFUN f (V16478)                                \\ version 2
                (IF (CONSP V16478) 
                    (IF (EQ (QUOTE a) (CAR V16478)) 
                        (GO tag16497) 
                        (GO tag16494)) 
                    (GO tag16494)) 
                    (IF (NULL (CDR V16478)) 
                        (RETURN (QUOTE a)) 
                        (IF (CONSP (CDR V16478)) 
                            (GO tag16499) 
                            (GO tag16494))) 
                    (IF (EQ (QUOTE b) (CAR (CDR V16478))) 
                        (IF (NULL (CDR (CDR V16478))) 
                            (RETURN (QUOTE b)) 
                            (GO tag16504)) 
                        (GO tag16494)) 
                    (IF (CONSP (CDR (CDR V16478))) 
                        (IF (AND (EQ (QUOTE c) 
                                 (CAR (CDR (CDR V16478)))) 
                                 (NULL (CDR (CDR (CDR V16478)))))
                            (RETURN (QUOTE c)) (GO tag16494)) 
                            (GO tag16494)) 
                    (RETURN (shen.f_error (QUOTE f))))))      

Finally inline = expansion = 10.

(DEFUN f (V16570)                                \\ version 3
   (IF (CONSP V16570) 
        (LET ((H16601 (CAR V16570)) (T16602 (CDR V16570))) 
           (IF (EQ (QUOTE a) H16601) 
               (IF (NULL T16602) (RETURN (QUOTE a)) 
                   (IF (CONSP T16602) 
                   (LET ((H16603 (CAR T16602)) (T16604 (CDR T16602))) 
                             (IF (EQ (QUOTE b) H16603) 
                                 (IF (NULL T16604) (RETURN (QUOTE b)) 
                                     (IF (CONSP T16604) 
                                         (IF (AND (EQ (QUOTE c) 
                                                      (CAR T16604))
                                             (NULL (CDR T16604))) 
                                             (RETURN (QUOTE c)) 
                                             (GO tag16590)) 
                                         (GO tag16590))) 
                                 (GO tag16590))) 
                             (GO tag16590))) 
                      (GO tag16590))) 
             (GO tag16590)) 
          (RETURN (shen.f_error (QUOTE f))))))      

Figure 2 shows the timings on the code for 108 iterations of (f [a b c]).

Version 1 8.15s
Version 2 4.98s
Version 3 3.9s

5 Choosing a Compiler Setting

There is no upper limit on the value for inline and expand, but higher settings can cause exponential runaways during compilation and out of memory messages. Generally it is best to start with lower settings and observe the performance changes before increasing the values for these settings.