Programming musings

Another important couple of phases have been implemented. These implement the creation of the code flow graph and several stages of simplification of this graph.

The call flow graph is a graph that describes the different execution paths of a program. There are many possibilities for encoding the CFG. A very low level form would be based on linked lists, with one node per statement. This seems very flexible and consistent, but in my opinion it introduces far too many connections, many more than are actually needed. It makes discovery of code units not so obvious.

My current choice is to collect statements into blocks and build a graph of the connections among these blocks. Each connection will amount to a jump statement, which can have one, two or more destinations, that can be unconditional or dependent on a variable. This information —the destination and the type of jump—, will be encoded in the block itself.

Let us consider the following piece of code as an example:

;;; (LET ((X 1))
;;;   (TAGBODY
;;;    BEGIN
;;;     (LET ((X 1))
;;;       (DECLARE (SPECIAL X)))
;;;     (GO BEGIN)))

The current algorithm is driven by the function create-call-flow-graph, located  at ssa-blocks.lisp. The first step in split-blocks is to take the list of SL statements and group those statements into block. A block is defined to be the statements that lay between two labels, or between a label and a jump statement, the latter included. At this step we make sure that every block has a name, which is either the label it started with, or a newly created label. After this phase we will obtain the following list of blocks:

(CODE-BLOCK [:L2-2] NIL NIL)
 (JMP :L1-1)
(CODE-BLOCK [:L3-3] NIL NIL)
(CODE-BLOCK [:L1-1] NIL NIL)
(CODE-BLOCK [:BEGIN] NIL NIL)
 (GLOBAL-BIND X 1)
 (UNBIND-GLOBAL X)
 (JMP :BEGIN)

The notation should be obvious. The beginning of a block is marked by a list containing the symbol CODE-BLOCK, followed by the name of the block, and the incoming and outgoing connections (none at this stage). After this list we find the statements that actually belong to the block.

Only after locating the blocks, we find out their connections, in the function discover-connections. Each block has two kind of connections: incoming, from other blocks, and outgoing. The outgoing connections can be of four kinds: implicit, to the blocks that simply followed us; explicit unconditional jumps; explicit JMP-IF-NOT jumps and explicit JMP-NTH jump tables generated for TAGBODY.

;;; Connecting NIL and [:L2-2]
;;; Connecting [:L2-2] and [:L1-1]
;;; Connecting NIL and [:L1-1]
;;; Connecting [:L1-1] and [:BEGIN]
;;; Connecting [:BEGIN] and [:BEGIN]
(CODE-BLOCK [:L2-2] NIL ([:L1-1]))
(CODE-BLOCK [:L3-3] NIL NIL)
(CODE-BLOCK [:L1-1] ([:L2-2]) ([:BEGIN]))
(CODE-BLOCK [:BEGIN] ([:BEGIN] [:L1-1]) ([:BEGIN]))
 (GLOBAL-BIND X 1)
 (UNBIND-GLOBAL X)

Note that the connections have been established and that there are many empty blocks which only connect blocks among each other, having no statements. We can get rid of them in the phase eliminate-empty-blocks, taking care, of course, that the structure of the graph is preserved. In the previous case this all simplifies to a single block.

;;; Function name:      ANONYMOUS-1
;;; Required arguments: 1
;;; Needs closure:      NIL
(CODE-BLOCK [:BEGIN] ([:BEGIN]) ([:BEGIN]))
 (GLOBAL-BIND X 1)
 (UNBIND-GLOBAL X)

So far we have advanced a lot. It now seems reasonable to go back into testing mode, adding checks for the generated and optimized code. The most sensible way, in my humble opinion, is to write a flexible interpreter that understands and executes our intermediate language, either in the form of lists or in the CFG form.

First of all, in the last version of the intermediate language there was a very important omission, namely UNSETJMP, an instruction to remove jump frames from the stack, so that they are no longer active. Furthermore, the version of GO that we implemented did not undo special variable bindings, nor calls to SETJMP.

In addition to this we have changed the semantics of SETJMP, so that it now behaves as an assignment to a variable, which is immediately followed by a JMP-IF-NOT that tests whether we arrive from a nonlocal LONGJMP or just from the preceding statements. This will make our life easier because we will only have three jump statments, JMP, JMP-IF-NOT and JMP-NTH, a kind of computed goto which is used by TAGBODY.

I have fixed this and added three more passes. One of them looks for calls to SETJMP and eliminates them if the jump point that it creates has not been referenced by any RETURN or GO statement. This will happen whenever a BLOCK or a TAGBODY is not referenced from a child function.

The other pass looks for local variables added using GROW-ENV and sees whether these variables are actually referenced by children functions. If this is not the case, we can eliminate the call to GROW-ENV all together and replace this environment variable with the immediately previous one. At the end of this pass we may call a function that identifies which functions do actually have a closure environment and which ones do not. This step is tricky to get right and we have mostly borrowed the code from current ECL.

The final pass runs over the code from the end to the beginning, eliminating occurrences of SET and CALL whose destination is an unused variable, but in the case of CALL only if the function has no side effects. By doing it from bottom to top we can eliminate temporaries that were created, as in the following two statements

SET <TMP-1> 10
SET <X> <TMP-1>

All together these three passes compactify the code significantly, and leave it ready for analyzing the code flow graph and removing unused branches. Note the difference between the two pieces of code, before,

;;;
;;; Compiling:
;;; (LET ((X 1))
;;;   (TAGBODY
;;;    FOO
;;;     (TAGBODY
;;;      BEGIN
;;;       (LET ((X 1))
;;;         (DECLARE (SPECIAL X)))
;;;       (GO FOO))))
;;;
;;; Function name:      ANONYMOUS-1
;;; Required arguments: 1
;;; Needs closure:      NIL
    CALL <TMP-1> [GLOBAL/GET-REQUIRED] 0
    GROW-ENV <ENV-1> <CBLOCK> NIL
    SET <CBLOCK> <TMP-1>
    GROW-ENV <ENV-2> <X> NIL
    SET <X> 1
    GROW-ENV <ENV-3> :TAGBODY-4 OLD-ENV-VAR
    CALL :TAGBODY-4 [GLOBAL/UNIQUE-ID]
    SETJMP <TMP-3> <TMP-2> :TAGBODY-4
    JMP-IF-NOT <TMP-3> :L1-1
    JMP-NTH <TMP-2> :TAGBODY-4 :FOO
:L1-1:
:FOO:
    GROW-ENV <ENV-4> :TAGBODY-5 OLD-ENV-VAR
    CALL :TAGBODY-5 [GLOBAL/UNIQUE-ID]
    SETJMP <TMP-5> <TMP-4> :TAGBODY-5
    JMP-IF-NOT <TMP-5> :L2-2
    JMP-NTH <TMP-4> :TAGBODY-5 :BEGIN
:L2-2:
:BEGIN:
    GLOBAL-BIND X 1
    UNBIND-GLOBAL X
    UNSETJMP :TAGBODY-5
    JMP :FOO
    UNSETJMP :TAGBODY-5
    UNSETJMP :TAGBODY-4
    SET <MV-1275>

and after the two pases

    JMP :L1-1
:L1-1:
:FOO:
    JMP :L2-2
:L2-2:
    GLOBAL-BIND X 1
    UNBIND-GLOBAL X
    JMP :FOO

There has been a lot of talking about the problems of one-man open source projects and the bus, but little is said about the story from the other side. Like when one has too many ideas and too many goals and knows how to achieve them but fails on finding the 25th hour of the day or the two additional hands and another half a brain to code what has to be coded.

That said, right now the highest priority in ECL is to get the library component stable and going, and to solve problems like stability against interrupts or against stack overflows, or to optimize key functions and fix a bunch of bugs that are left around. That means this all thing with the compiler gets slowed down significantly.

On the other hand when looking at optimizations one sees that most of the library is quite fast, but the current lisp compiler is failing to identify simple types, simple inline forms, unless a lot of declarations are spread around the code. ECL does for instance pretty bad at the cl-bench benchmarks. We know what the problem is, we know the solution: move forward with the new compiler.

So some more work has been done. I have fixed the “Simple Language” or “Simple Lisp” if you want to call it that way, which is a set of s-expressions that will make our intermediate language for the compiler. It is simple enough and consists only on assignments to variables and three kinds of jumps that will be probably reduced to two. You can find the specification at the beginning of ssa-translate.lisp which is a rather new addition to the code.

Some of the names are pretty obvious, including JMP, JMP-IF-NOT, SET and CALL. The first two are jumps, with or without a condition, and the second two are assignments to a variable, either direct or from the output of a function. The creation of variables is of three types:

• We just assign it with SET, which means that the variable is really local to the function.
• We bind it to the lexical environment in two steps, first growing the environment with GROW-ENV and the assigning a value. Here UNBIND-LEXICAL is used, but it will be little more than a mark for when a variable stops being used.
• We bind it as a special variable with BIND-GLOBAL and then after some statements undo the binding with UNBIND-GLOBAL.

Note that the lexical environment is just treated as a set of variables, which keep an object that is grown or shrinked for adding new variables that can be closed over by children functions. These environment variables are already in SSA forms which means once we know how many variables are really used in closures we will be able to do a simplification pass and eliminate most of them.

The final ingredient is SETJMP/LONGJMP, which implement exactly what they name: unconditional jumps across function boundaries. They have these names because they are implemented using C’s setjmp() and longjmp(), but do a little more: they allow to pass a number of variables and the destination of the jumps is discriminated using some unique ids. We use these special operators to implement RETURN, nonlocal GOs, CATCH, UNWIND-PROTECT, etc. There is no innovation here, for this is indeed the mechanism used by ECL right now.

With all these ingredients we are currently able to translate almost any Common Lisp form to this intermediate language. Whatever is not provided by these forms can be implemented using macros and function calls. This is for instance how we encode the parsing of arguments. Take for instance

;;;
;;; Compiling:
;;; (LET ((X 1))
;;;   #'(LAMBDA (Y) (+ X Y)))
;;; [...]
;;; Function name:      ANONYMOUS-2
;;; Required arguments: 1
    CALL <TMP-2> [GLOBAL/GET-REQUIRED] 0
    GROW-ENV <ENV-3> <Y> NIL
    SET <Y> <TMP-2>
    SET <TMP-3> <X>
    SET <TMP-4> <Y>
    CALL <MV-635> [GLOBAL/+] <TMP-3> <TMP-4>
    UNBIND-LEXICAL Y

At some later point we can inline the call to GLOBAL/GET-REQUIRED, but for all purposes we need not add special forms to this simple language and complicate the compiler.

Right now the translator is pretty functional and allows for almost everything that we contemplate in the current compiler. To see a few examples, just load “ssa.lisp” into your favourite lisp implementation and let it run.

The following steps to take are, in some random order, identifying function closures, simplification of GROW-ENV statements, splitting of code into connected blocks forming possibly cyclic graphs, eliminating dead code, eliminating unused variables, introducing unique names for the variables (i.e. SSA form), introducing phi forms, finding out variable lifetimes, first code emitter…

We have just started and there is already a mistake. I must admit that I had envisioned already that problem in the previous post. The trick is that a MACROLET and a SYMBOL-MACROLET form must take into account outer defitinitions when creating the new definitions. For instance, here

(macrolet ((a () 5))
  (macrolet ((b () (a)))
    (b)))

in order to expand the definition (b), the form (a) is evaluated at compilation time and thus we need the definition of that macro to be present. The appropriate fix has been added together with a new test case.

The code repository here is beginning to become populated. If you go to the ecl-ssa tree view, and in particular you focus on the tag 2008.09.20, corresponding to this post, you will find already a few files.. One is ssa.lisp and it will be the file responsible for loading the rest of the compiler now and in the near future. I could have chosen to use ASDF, but since this is going to be integrated into the ECL build process, that does not seem like a sensible idea.

The second file is ssa-defs.lisp. This one contains the object definitions for the compiler structures. You may notice that I have currently chosen to use CLOS for these structures. That is for ease of work. At some point we will have to move back to lisp structures, or even something simpler, for most of this code is to run much before the whole of Common Lisp is loaded. As far as we keep things well encapsulated, hide all uses of make-instance and other details of the inheritance, this should pose no problem afterwards.

The third thing you will notice is that there are quite many objects right now.

+ named-object
   + reference
      + variable
         + lisp-variable
            + global-variable
         + lisp-block
         + lisp-tagbody
         + lisp-function
   + lisp-macroexpander
      + lisp-macro
      + lisp-symbol-macro
+ code-block

They split into two families. First we have objects that can be referenced. These objects are created by lisp forms during the translation process, they are stored in an environment structure (a list ) and become accessible to other, inner forms. This is the largest family and here we find local and global variables, labels, blocks, tagbodies, functions and macros. Can you think of any other objects you may need? I would be surprised since those are already more than what the current ECL compiler uses.

Then we have the data structures which are used by the SSA compiler. Right now these only include an object named CODE-BLOCK that groups statements together and which implements the nodes of the code flow graph. Unlike in the previous version of the lisp2c compiler, we will not create a data structure for statements. Right now I find it more convenient to keep the intermediate representation in lisp form, instead of dealing with structures. At least experience in the previous compiler showed that the latter leads to uglier code.

Another minor detail is that we handle names ourselves. We have a named-object class that contains a symbol and a suffix, and which is used to create many versions of the same name. This is useful for creating anonymous variables, environment variables, labels, tagbodies, etc. All in all, objects which not only have EQ identity, but which we also want to be distinguishable when printed. We could have used gensym for that, but that really leads to ugly code, since we cannot control the numbering.

Then we have another file, ssa-env.lisp, which contains all functions for manipulating the compilation environment. We distinguish two sets of functions. First there are those that allow us to enlarge and environment with new objects or to look symbols up. These are the functions used during the translation process to convert symbols into variable references, find out which is the block a RETURN statement belongs to, etc.

Then there are functions which use this environment for macro-expansion. These ones are a bit cumbersome because they have to call MACROEXPAND or EVAL, both functions which expect the environment object to have the old format. Thus you find MAKE-MACROEXPAND-ENVIRONMENT and MAKE-EVAL-ENVIRONMENT, which will tell you a bit more about how environments are handled right now. Please do not be scared about the messy format for the old legacy environments, they are just simple enough for C to process them without much effort

Finally I have prepared some simple tests for the environment. This suite has to be enlarged, for there are many subtle issues that have to be fixed before we move on. For instance, we have to test that a MACROLET definition is processed in an environment that contains all previous MACROLET definitions. And by this I do not mean at macroexpansion time, but that all previous MACROLET definitions apply to the body of the MACROLET definitions as well. Well, lots of things that were not so easy to get right at the beginning with neither the interpreted nor the C compilers. Help is welcome on this point.

Before getting into the task of coding one should sit down and think clearly not only about the objectives, but also about what we have achieved so far and what are the problems that the current ECL codebase faced and solved.

So, first of all, how does ECL compile and execute code right now? We have a redundant architecutre, with two compilers: one that transforms lisp code into bytecodes and another one that uses C as a backend. The first one is barely a single pass compiler: code is macroexpanded and, once expressed with a subset of Common Lisp, it can be directly translated into a set of bytecodes that match the structure of that language. While extremely simple, the development from scratch of such compiler taught this guy some lessons
More… »

This post opens a blog related to programming, but with a strong focus on a particular project, namely, to write a compiler for Common Lisp that can be used in the implementation I maintain, ECL.

This project was born one week ago, with a post I wrote to the mailing list. As I mentioned there, “one sometimes needs an additional motivation to keep working.” In my case the motivation is learning, not just polishing code, and writing compilers has always been my pet subject.

Before you continue reading any of my posts, beware: I am a selft taught programmer. I have taken no courses on programming from a university, though back in my youth I got a title as Functional Analyst. What does this mean? It means that I will write things that may be obvious to some people, things which are wrong, I will rediscover algorithms that everybody knows about… But if you do not care about this, I will be more than happy to “show you the code” as I write.

Welcome aboard!