Common Lisp Compilers Internals

[Caps & Mugs] Some of my CL aliens designs

2011-08-13T13:29:00.000-07:00

Sorry for polluting Planet SBCL with these images (also, it is a good idea to remove my blog from the planet, see the previous post on this), but I designed several simple 'Lisp + aliens' images which I want to put into the public domain. They are not complex or artful, and maybe even agressive (not funny, as the traditional Lisp aliens), but I like them:

The first:

The second:

The third:

These are in the public domain, so anyone can use them.

[Note] Crowdfunding and SBCL

2011-08-11T12:34:00.000-07:00

I think that you already know about it, but if not, please see here.

BTW, our 'SBCL Users & Developers' Linkedin group has more than 100 members (105 at the time when I'm writing this post). Thanks to all people who participate.

And the last update is my personal one: there were some changes in my career, and I cannot say that I am a CL developer at this time. But that's okay - people should try other things, even if they started with the best one :) This blog will be silent during my absence in CL community, I think.

[Feature] MAKE-THREAD with the thread arguments

2011-05-02T10:28:00.000-07:00

Today seems to be a features day :)

This feature has the extremely simple implementation (unless I'm missing something here), but it makes the life easier when it comes to the thread function's arguments. So, with this patch you can write the next code:

(defun f (x y) (* x y))

(sb-thread:make-thread #'f :args '(6 7))

without messing with the wrapper lambda.

Maybe this simple thing does not deserve a post, but I am really happy to see it working. The patch is here.

[Feature] Running tests in parallel

2011-05-02T06:51:00.000-07:00

This feature may be interesting for the people who often run SBCL tests. It uses several CPU cores to do that quickly. While it is still not finished, there is some early implementation which can be used to measure the performance boost. In case you want to try it yourself, here are the explanations and instructions:

The idea of the multi-core test launcher is based on the fact that SBCL test files are independent, so they can be loaded and executed in parallel. The classic model with the threads pool and the test files queue fits fine - there is a main, "supervisor" thread, whose job is to spawn additional threads. Every additional thread takes care of one impure test file at a time, and executes it using child SBCL process. The supervisor thread runs all pure tests (most of them are short) and waits for the additional threads to finish.

On my PC with Phenom X4 920, I use three additional threads and all tests run 3 minutes. Without the parallel launcher, they take 8 minutes to finish. Failures seem to be reported correctly, I have tweaked several tests to check that. However, the failures collection needs synchronization, and I hope to finish with it in the future.

The performance may be improved even more by splitting all-threads.impure.lisp on several files, but this is a low-priority task. Just make sure that you rename the original threads.impure.lisp before trying this stuff (the file is so long that a separate thread runs it almost 3 minutes, so it should be the first file in the queue, alphabetically). Also, adjust the number of threads as described in Launchpad. The default value are for quad-core systems.

The issue page and the initial code changes are here:

https://bugs.launchpad.net/sbcl/+bug/742777

In case you find any errors/mistakes in the code, please let me know. I am interested to make this feature stable and ready for the upstream.

[mini-HOWTO] Writing Regression Tests For SBCL

2011-01-11T11:44:00.000-08:00

Most of the complex software systems have some kind of regression tests, and SBCL is not an exception. In this short post, I want to answer the next two questions:

1. Why it is preferable to provide a regression test with the bug report?
2. How to write such a test?

Frankly speaking, regression tests are not necessary for bug reports. One may just say “this code is compiled wrongly”, and then attach the code snippet. However, such reports can be hard to understand, especially when we are trying to figure out the desired behavior. In contrary, regression tests always show the desired behavior, so they make the report more informative.

Moreover, your report with a regression test always saves the time for SBCL developer who will fix the corresponding bug. A regression test is mandatory for the most of patches, so someone should write it anyway. I do not know about the others, but I prefer the next steps while fixing a bug in SBCL:

- write a regression test. Make sure that it fails before the fix;
- fix the bug;
- make sure that all regression tests pass.

The issue originator knows the problem very well, so he or she can provide the best regression test.

So, how to write them? It is surprisingly easy in most cases. First of all, you need to find out the right test file to put your test into. These files are located in /sbcl/tests directory. They have the extension “lisp”, and the two important parts before it: the suffix “pure” or “impure”, and the main part which classifies the subject of the tests – in other words, the functionality which is tested. The main part is something like “compiler”, “loop”, “print” etc. The suffix “pure” means that the file contains no tests with global side effects; “impure” files contain tests which define variables, conditions, classes, functions and so on. For example, “loop.pure.lisp” file contains LOOP macro tests without side effects.

After you have selected a file, it's a time to write the test itself. The only constant element of all tests is a WITH-TEST wrapper, which binds a human-readable name to your test (it can do other things as well, but I use only :name keyword. See the macro definition in test-util.lisp to find out more). The rest of the test body may vary (you can use different assertion clauses, bind handlers for compilation errors or warnings etc.).

Here is a very simple (and pure) test from arith.pure.lisp:

The test passes when ASSERT receives non-NIL value. Obviously, you may use any CL code inside ASSERT. For example:

RAISES-ERROR? is an utility macro (defined in assertoid.lisp). It is useful when you want to test that a form evaluation signals an error. The optional second argument can be used to specify the condition type, as in the above example.

Here is another example – the impure test from mop.impure.lisp:

The test is impure, because it creates a class definition. Some old tests (like this) miss WITH-TEST, but it is strongly recommended for new ones.

It is often required to test that SBCL signals (or does not signals) errors and/or warnings during the particular form compilation. This pure LOOP test can be a good example:

The test idea is to check the return values of COMPILE. Another way to do something similar is to use HANDLER-CASE (the example from compiler.pure.lisp):

This test ensures that a compiler note is printed for the non-optimal operation.

In general, SBCL regression tests are very expressive and powerful - we can test quite complex functionality in the several lines of code.

To run the added tests, execute a command (on Linux):

sh run-tests.sh filename

from sbcl/tests directory. Without a file argument, it runs all tests in the regression suite.

I hope that this short post is helpful for those who have never written any SBCL regression tests. Just try to do it when submitting a new bug report – and you will help SBCL developers a lot.

SBCL platforms

2010-09-18T10:40:00.000-07:00

There was a poll in Linkedin about the SBCL platforms, and you can see the final chart below. I cannot say that it shows the real picture, because the number of responses is very small. But anyway, Linux seems to be the reasonable winner here, which is not a big surprise :)

SB-GPU: the missing part of SBCL

2010-09-05T11:13:00.000-07:00

While there is no single point of view regarding the SSA pass in SBCL compiler (see the early talks on #sbcl channel), I know the modern and interesting feature which is missing for sure. This is the ability to mix CPU and GPU code in a single CL application. That is, the ability to write:

(def-gpu-kernel mulmatrix (m1 m2 m3) ...) ;m3 = m2*m1

(defun my-solver (equation-matrix)
...
(with-gpu-allocated-arrays (a1 a2 a3)
...
(call-gpu-kernel mulmatrix a1 a2 a3 N) ;N only, square stuff
...)
) ;end of the solver

Let us explain the code a bit. mulmatrix is a GPU kernel, defined using some subset of CL (mostly math functions and array operations). It should be compiled to one of the two GPU-specific assembly-like languages (see below). After that it can be launched transparently by call-gpu-kernel (transparency means that call-gpu-kernel is the ordinary CL macro).

After the kernel is defined, we should be able to use it from the plain CL (CPU-targeted) code. To achieve this goal, the next steps are required:

1. Allocate CL data arrays on SBCL side (usually arrays of numbers).
2. Allocate the arrays of same size in GPU memory.
3. Copy the data from CL arrays to GPU arrays.
4. Run the kernels using GPU kernel launcher API (part of ATI Stream / CUDA SDKs) on GPU data arrays.
5. Copy the modified data from GPU arrays to CL data arrays.
6. Use the processed data in your CL application.

This is only one of the possible approaches, and the inputs are not restricted to be arrays (but GPU parallelism is reasonable to use only for quite large data sets, which are represented by arrays).

In fact, the very simple variant of the described above things works fine with one proprietary CL application which we have written here in Ukraine. And it is proven to gain over 500x (yes, 500 times faster) execution speed improvement on comparatively simple O(N*N) algorithms benchmarks. With SBCL there will be no 500x (because our proprietary application is deadly slow for some reasons which I will not list here), but I believe that 10-20x for O(N*N) algorithms class is possible.

The whole architecture for SBCL is here:

CL subset is translated to the intermediate representation GPU-IR, which has no dependency on the underlying device architecture. Then, we produce the GPU assembly for CUDA devices or ATI Stream devices, depending on the platform where our CL code is loaded and executed. In such a way we have our home-made variant of the portable Lisp-like language for the modern parallel computing. SBCL-side part of the system should live in SB-GPU contrib.

The bad news are connected with the estimate: at least 6 man-months for GPU-independent part and at least 1-2 man-years for two GPU backends (6-12 months per the backend). I can do this as a PhD thesis (because there will be some scientific part, connected with parallelism and optimisations), but I need to find the appropriate university and a professor who could be interested in this (not necessarily in Ukraine). The thing is that I want to continue my education, so I would like to join the SBCL development activities with that. Is this possible on Earth?

[SSA] Two ways to implement it

2010-08-14T09:55:00.000-07:00

I have evaluated two different approaches to SSAF in SBCL compiler. Both have some advantages and drawbacks, more or less significant from different points of view. So, here they are:

1. Insert the SSA pass after find-initial-dfo call, and modify the legacy IR1 component slightly (insert phi-functions & ensure unique assignments). Come out of SSA before ir1-phases call.

+ Faster to implement
+ Will probably fix the non-linear LVARs bug
- Does not allow to perform SSA-based optimisations (because it means the IR1 functionality duplication)
- Slows down the compilation process
- Requires a good bidirectional mapping algorithm between SSA form and IR1 representation.

2. Remove all IR1 code after make-functional-from-toplevel-lambda (including this function as well), and compile Lisp forms to SSAF. Apply SSA-based optimisations, and finally convert SSAF into VOPs, to use the existing backend.

+ Count all current IR1 bugs for sure
+ Easier conversion to SSAF (no need to analyse IR1 components)
+ Advanced SSA-based optimization, loops analysis, etc.
+ Probably faster compilation process?
+ More fun and interesting than the first variant
- A really huge project
- New bugs, as usual
- Merging perspectives are unclear (I do not believe that maintainers will throw out almost the whole compiler frontend).

As for now, I would prefer the second approach. I think that it will be a hobby project for me, and it will take a year or two before it can be announced as a beta or so, if at all. From my own development experience I can say that compilers should be designed and implemented by quite large (and preferably not remote) teams, not by a single person. So, this is just my own way to have fun with Common Lisp, and I feel that it is very likely to fail eventually. I do not expect brilliant results here, but I can't stop myself from giving it a try - at least to learn some new and cool things.

[Note] SSA in SBCL (yet another book freeze)

2010-08-06T08:48:00.000-07:00

Yesterday, we had the quite interesting discussion on #lisp, which was originally about this bug. Several long-term SBCL developers confirmed that the optimal way to deal with such issues is to implement the SSA pass in the compiler.

SSA is present in SBCL's TODO list during several years, but there is no implementation yet, and, AFAIK, nobody is working on it now. Since the compilers development is the thing I like the most (and it is my full-time job), I have decided to give it a try.

In this situation, I must call the book activities closed. There are two main reasons for such a decision, and one minor reason:

1. Free time limit.
2. SSA pass is very likely to change the SBCL's frontend. In such a case the book's material may become obsolete, which means that the book writing efforts are spent in vain.
3. Honestly, it is more fun to develop than to write the books (at least for me). And, there are a lot of good compilers books which could be easily mapped on SBCL. One who really wants to learn it will always find the possibility, like many people did before.

I hope that the readers will understand the situation and agree with me (or even forgive me, in case somebody is hurt by this post). From now on, there will be no new chapters here, so it is reasonable to remove the blog from 'Planet SBCL'. Instead, I will put SSA design and progress reports here occasionally.

In case I fail to implement SSA, I will leave the SBCL community. Two failures in the same open-source project mean that it was selected wrongly.

[Book] Chapter 5.1 External References Collection

2010-07-27T09:16:00.000-07:00

Returned by sb-c::find-initial-dfo components are passed to sb-c::compile-component one by one, in the loop which is located inside sb-c::%compile function (src/compiler/main.lisp). Function sb-c::compile-component runs the individual compilation stages for the component. In case we skip the minor things (like the sanity checks), the first function's action is the analysis and collection of the component's external references. Let us discuss this process, along with the corresponding source file ('src/compiler/xref.lisp'). It starts with sb-c::record-component-xrefs function:

This code is pretty simple. For each cblock in the input component, the local function handle-node records the possible external references for every node in that block. The function uses sb-c::record-node-xrefs to analyse the individual node. The analysis is nothing but etypecase form, which handles every kind of node in a particular way. The complicated part comes with sb-c::call-with-block-external-functionals:

This function actually applies handle-node. It defines handle-functional local function, which filters functionals before passing them to the handler. Also, it handles all functionals whose ref nodes point on the initial functional, in the recursive manner.

The reference recording happens in sb-c::record-xref:

To understand the process results better, let us debug it a bit:

In this example, the reference kind is :calls. This means that f calls the global function #'+ (or just +, as you can see on the figure). The context is clambda which corresponds to f, then we see the reference node and nil instead of the source path. At this point we consider the external references collection to be explained enough. The author hopes that the readers also find this process and the related code to be simple.

[Note] My SBCL tree

2010-07-20T10:09:00.000-07:00

Namely, http://repo.or.cz/w/sbcl/rmarynch.git

I have some ideas about the current SBCL compiler development. For example, better loops analysis and automatic vectorization are good things to implement.

However, the constant lack of free time makes these ideas to wait until I will be fired :)

There was a short discussion on #lisp regarding the current patches review problem (the thing is that they stay in Launchpad for a long time). One of the ideas is to have a branch with all patches applied, and to merge from it into CVS once a month or so. Now I think that I am not the right person to manage such a branch - it is definitely a maintainer's task. So, rmarynch.git will be my personal branch only.

[Book] Chapter 4 DFO

2010-07-18T06:08:00.000-07:00

DFO (depth-first ordering) computation is the next code flow graph processing phase, which comes right after the local calls analysis. The corresponding source file is 'src/compiler/dfo.lisp'. But before starting to talk about the code, let us explain DFO itself, for those readers who are not familiar with this concept.
DFO can be considered to be the result of DFS (depth-first search). The latter, along with BFS (breadth-first search), are two different ways to walk a graph. They both can visit all graph's nodes, as shown on this figure (a graph, DFS and BFS):

The main difference between these two methods is that the first one tries to walk the graph by moving between different child levels first, while the second (BFS) visits all children on the same level first, and then moves to the next level. Of course, this explanation is informal – refer to your discrete math book to find out more.
DFS is also useful when we want to classify the graph's edges. A graph may be quite complex, with many edges connecting nodes in a certain way. The next four categories are possible (this classification evolves naturally from DFS algorithm):

- tree edges;
- forward edges;
- back edges;
- cross edges.

However, SBCL uses DFS to find out the independent components and their elements only, and it does not classify the connections between them. Taking this into account, readers should probably consider DFS to be just a tree walk in our case.

We choose sb-c::find-initial-dfo (called in sb-c::%compile, 'src/compiler/main.lisp') as a starting point for the code discussion. It receives the list which contains the exactly one functional – the one we are compiling. Then, it does the next steps:

- fetches the component of the functional, and a list of functionals which are in this component;

- iterates over that list, calling sb-c::dfo-scavenge-dependency-graph for each functional;

- collects the component which was returned by sb-c::dfo-scavenge-dependency-graph (this collection does not happen always – the same component is not collected twice);

- deletes the original component of the input functional, in case the component's kind is :initial;

- after the components are collected, the last two actions: blocks numbering and components classification (in sb-c::separate-toplevelish-components) complete the function body.

Let us move to sb-c::dfo-scavenge-dependency-graph. What is bad about DFO code, is the individual functions size, which is impossible to fit into the book's standard page. So, please find its source (there is also the excellent comment) and then continue with this chapter.

There are four main branches in this function: the first performs a simple check to find out whether the functional is already in the given component, and returns that component. The second merges the old non-initial component into the given component. Third branch is related to the second, it checks the block's 'flag' slot to find the initial components which are already walked during DFO computation (this slot value is set in sb-c::find-initial-dfo-aux).

The most interesting and long branch is the fourth one. Here the function builds DFO for the functional and its elements. It should do the next things to accomplish that:

- move the input clambda structure instance from its old component to the new, as well as clambda bind and return blocks;

- call sb-c::find-initial-dfo-aux (see below);

- declare several local functions: 'scavenge-closure-var', 'scavenge-lambda', 'scavenge-entry' and so on. They all use sb-c::dfo-scavenge-dependency-graph directly or indirectly – after the certain simple checks are done;

- iterate over the dependency list of the input clambda (more precisely, over 'calls-or-closes' sparse set elements) and call one of the inner functions to scavenge every element. Eventually this ends with the recursive call into sb-c::dfo-scavenge-dependency-graph. This is a key point to understand: Python is merging all pieces of the entire functional representation into the single component recursively. In case you understand this sentence, you understand what is DFO computation in SBCL.

Function sb-c::find-initial-dfo-aux is shown here:

As you see, the code is quite simple. The strategy is to join the block's component with the given input component, unless the block's component is initial, the same as the input component, or the block is already processed by this function (its 'flag' slot is set). Actual flag setting occurs in the default branch, which is full of the interesting stuff. First of all, we have a call into sb-c::scavenge-home-dependency-graph here:

This function finds the right component to merge the block's successors into (recall that a block which contains bind node is the first in the functional blocks chain). In sb-c::find-initial-dfo-aux all these successors are recursively processed, and their common component is derived finally. The tiny function sb-c::remove-from-dfo (it is located in ir1util.lisp, as well as sb-c::add-to-dfo) is used to break the old next/prev relations of the block, and sb-c::add-to-dfo is used to insert the block after the component's head block.

The actual code which joins two components, sb-c::join-components, is quite simple and long enough to omit it in this book. We believe that readers also find this function to be easy understandable.

The last function to discuss in this chapter is sb-c::separate-toplevelish-components. It is called as a last form in sb-c::find-initial-dfo. Its job is to classify the toplevel components which were discovered during DFO computation. The function iterates over the list of these components, and creates three lists of them, by category: nontop-components, top-components and hairy-top-components. Classification rules are based on the analysis of the external references and toplevel functionals presence in a component.

As for now, that is all about DFO computation in SBCL. We will meet it again later, in sb-c::dfo-as-needed, but at this time it is enough to know that DFO in Python provides the certain connections between all elements of the same Lisp form representation in the compiler. These connections allow easy and consistent walking of the entire functional, which is important for many compilation-related algorithms.

[Note] New chapters schedule

2010-07-09T02:39:00.000-07:00

I have found that it is better to put complete chapters for the review at once, instead of posting several parts of a chapter. The advantages of this approach:

1) The chapter is solid and more consistent (because I can modify the earlier parts after I have discovered something at the end of a particular topic).

2) It is easier to track changes, comments etc. when we have the less number of posts.

Since a typical chapter has 3-4 parts, it takes a month to write the complete one. So, I plan to post Chapter 4 by the end of this month. I have the first part ready, but I feel that it may be changed while I move across dfo.lisp.

So, please visit this blog at the end of July. Maybe I will finish the chapter earlier, but the end of the month is the guaranteed deadline:)

[Book] Chapter 3.2 Let Conversion

2010-07-02T09:36:00.000-07:00

Let conversion is the second part of the local calls processing, and its goal is to place (inline) the callee's flow graph elements inside the caller's home clambda. The explanation of this short sentence is the subject of this chapter.
The actual conversion for a functional (strictly speaking, for clambda) begins with sb-c::maybe-let-convert call. This function performs all necessary checks to make sure that it is possible to proceed with the conversion. The next things are verified:

- clambda as a leaf is referenced only once;

- clambda represents an ordinary function or is used in local calls several times (see node.lisp about nil and :assignment functional kinds. Note that :assignment functionals are not converted, due to the narrower constraint which follows this one);

- clambda has no XEP;

- the call is :local, and both the destination node and the block this clambda is in are not scheduled for deletion;

- sb-c::ok-initial-convert-p returns t for this clambda. This short predicate filters functions which are likely to have more than one leaf reference in the future;

- clambda is not the home lambda of the destination node.

After the above conditions are satisfied, sb-c::let-convert comes into play. Its job is to arrange the stages of the conversion, as you can see on this figure:

The first step is the insertion of a fresh let body, which happens in sb-c::insert-let-body. We give the code, as well as the explanation for this process:

First of all, home blocks of basic-combination and clambda bind nodes are fetched, along with basic-combination's and bind's home components. When unoptimized component of basic-combination is not the same as clambda has, both components are merged by sb-c::join-components ('src/compiler/dfo.lisp'). This means that the entire clambda component's code now shares the same component with the clambda caller. After that, caller's block is split in such a way that the call (basic-combination) node becomes the last node in the original block. Finally, the block of bind node is inserted right after the call node (block), and the block which was the successor of the call block originally ('next-block') is returned. Recall that (node.lisp comments) bind node marks the beginning of the entire clambda, and includes all computations in that functional to the code flow graph (using control transfers). So, now clambda is literally inside the caller's code.

The next step is sb-c::move-return-stuff call (Figure 3.14). There is a decent comment right above the function in the sources, but anyway let us add a few words to it. Ignoring sb-c::unconvert-tail-calls temporarily, the function begins with fetching return nodes of both caller and callee clambdas. In case the caller has this node, and the node is in cblocks which is scheduled for deletion, the node is removed. Then, a trivial check for non-nil callee's return node is performed. After that, three scenarios are possible:

- there are both the caller's return node and the code after that node (that is, 'next-block' cblock) present, or at least 'next-block' is non-nil; and callee's return nodes' block is not scheduled for deletion (the last requirement stays in the next scenario as well). This situation is handled in sb-c::move-return-uses;

- there is the caller's return node, but there is no code after it (that is, we have a tail call case). This is also a subject to sb-c::move-return-uses, but there is the additional preparation before the actual call – the compiler ensures the caller's return node to be the last node in its block (see sb-c::ensure-block-start in ir1util.lisp, :inside-block case), and assumes 'next-block' to be the same cblock;

- the default scenario: the call itself is assumed to be tail, and the callee's return node is moved to the caller's clambda.

Now it is a time to talk about the skipped function - sb-c::unconvert-tail-calls. Its code is on this figure:

This function iterates over all clambdas which are in use by the callee ('fun'). In case the call is represented by a node in the tail position and the node home clambda is 'fun' itself, the compiler marks the node to be non-tail positioned. Then, the most significant part of the processing occurs for ordinary, cleanup or optional-dispatch kinds of functionals. The block of 'this-call' node is fetched, along with lvar which is the destination of the original (input) call node. Then this block is separated from its first successor, and linked with 'next-block'. As you remember from sb-c::insert-let-body discussion, this 'next-block' contains all the code which was moved into a new block in sb-c::node-ends-block call. Finally, 'this-call' provides the value of the original call node. This connection is done with sb-c::add-lvar-use. See also the sources comments for sb-c::unconvert-tail-calls.

Function sb-c::move-return-stuff uses sb-c::move-return-uses:

Things which happen here are comparatively simple. First of all, the function fetches the callee's return node and the block this node is in. Then, the block is disconnected from its component's tail block ('tail block' is the successor of the exit point, so the unlink operation is valid. See the comment in node.lisp about 'tail' slot of component structure) and linked with 'next-block'. Return node itself is removed from the flow graph. Finally, all nodes which use the value from 'result' are modified to use the value from the converted call node ('lvar'). For the process details, see the small function sb-c::substitute-lvar-uses in ir1util.lisp.

The last function which we should discuss in this chapter is sb-c::merge-lets. It is the final function which is used in sb-c::let-convert body:

We deleted comments and added line numbers, to fit the function on a single page and to provide the way to reference a certain code line during the discussion.
This function does multiple things. First of all, it unlinks and removes the callee's clambda from the caller's component, lines 811-815. Then, callee is removed from its own tail-set structure's functions list (see sb-c::depart-from-tail-set for details), line 817. In lines 818-831 we can see the change of clambda 'home' and related slots, which now contain the values from caller's home clambda. The rest of the code moves external dependencies of clambda to its new “home”. That is, the converted function is not an independent functional anymore.

[Book] Chapter 3 Local Calls Analysis [part 3]

2010-06-25T10:12:00.000-07:00

Function sb-c::convert-lambda-call is a thin wrapper over sb-c::convert-call. It just checks the arguments count match, and delegates the conversion to the latter function. The same can be stated about sb-c::convert-hairy-call, except that it uses both sb-c::convert-call and sb-c::convert-more-call. The last is useful when dealing with those optional-dispatch instances which handle &more or &rest keywords (maybe 'handle' is not the right word here, they just correspond to Lisp forms which were declared with these keywords in their arguments lists).
Since sb-c::convert-call is used more often, let us discuss it first. The sources are shown here:

It begins with sb-c::propagate-to-args call, which uses sb-c::assert-lvar-type to ensure that the actual arguments types will be correct in runtime. Then the kind of call's combination becomes :local, and its arguments lose their 'externally checkable types' due to sb-c::flush-lvar-externally-checkable-type calls ('src/compiler/ir1opt.lisp'). The last function just sets '%externally-checkable-type' slot of lvar instance to nil. The value of this slot is used in sb-c::cast-externally-checkable-p ('src/compiler/checkgen.lisp'), and we will discuss it later in this book. The reason to have a separate function for this simple operation is not so clear, maybe the authors just wanted to have the possibility to debug this flushing. As one can see from the sources, the flushing occurs only when sb-c::call-full-like-p ('src/compiler/ir1util.lisp') returns nil. The last function involves some IR2 stuff, so we are not sure whether we should talk about it in this chapter.

The last new thing to cover in sb-c::convert-call is sb-c::recognize-dynamic-extent-lvars:

This function iterates on both the caller's and callee's arguments (more precisely, for clambda these are lambda-var instances, and for basic-combination there is a list of lvar instances in 'args' slot). In case there is lambda-var instance which denotes a variable with dynamic extent, but the corresponding basic-combination argument has no cleanup instance assigned to it, the result of sb-c::handle-nested-dynamic-extent-lvars call ('src/compiler/ir1util.lisp') is appended to 'dx-lvars'. That function is a bit long to post here, so its analysis is a task for readers. Final actions in the loop are quite simple (except sb-c::node-ends-block call, see below) – the entry/cleanup pair is created, and 'call' node is protected with cleanup. Also, the same cleanup is put into 'dynamic-extent' slot of every lvar instance which misses it initially (and this is the reason why the corresponding variable is in 'dx-lvars' list).

Since we have met it, let us discuss sb-c::node-ends-block ('src/compiler/ir1util/lisp):

The main purpose of this function is to ensure that the given node is the last node in the block, and to make it to be the last node in case it is not. Here are the main steps it does:

- fetch the nodes' block, the block's last node and the nodes' next ctran;

- exit in case the input node is the last node in the block;

- create a new block, which is headed by the nodes' next ctran. The last node in this block is the last node of the original nodes' block. So, we may assume the original code block (cblock) to be split on two blocks, with the nodes' next ctran as the boundary between them. The successor of the new block is the successor of the original block, and they (old and original blocks) are in the same component;

- nodes' next ctran now starts a block, so its kind becomes :block-start. The input node becomes the last node in the original block, and its 'next' slot is now nil;

- for every successor block of the original block, 'new-block' is added to the predecessors list, and the original block is removed from that list;

- the original block successors list is cleared, and the block is linked with 'new block' (see ir1util.lisp and sb-c::link-blocks, it just establishes successor/predecessor relations between cblocks). Function sb-c::add-to-dfo finishes this process by adjusting next/prev slots of cblocks (you may find this small function in ir1util.lisp);

- the original block's component reanalysis is scheduled;

- all ctrans in the new block are updated, so they “know” where they are now;

- the original block is marked as “interesting” for constraint propagation phase (we will discuss this phase later in the book).

There exists the last form to discuss before we return to the second branch of the local analysis (that is, to sb-c::maybe-let-convert). It is sb-c::convert-more-call. But here the author is bound to tell the readers honestly: he has never used '&more' lambda list keyword. Quick scan through SBCL User's Manual also gave no insights about this keyword purpose (it is available only in CMUCL/SBCL, as far as the author knows). So, in the first book draft this conversion description is omitted, and we start with let conversion discussion in Chapter 3.2.

[Book] Chapter 3 Local Calls Analysis [part 2]

2010-06-19T02:58:00.000-07:00

Entry points for optional-dispatch, as well as ordinary functions and escape/cleanup functionals, are further processed by one of these functions: sb-c::convert-mv-call, sb-c::convert-lambda-call or sb-c::convert-hairy-call.

The first one, sb-c::convert-mv-call, is shown on this figure:

Starting from the very beginning, there is sb-c::looks-like-an-mv-bind call ('src/compiler/ir1util.lisp'). This function checks that the input functional is the instance of optional-dispatch structure, and the input arguments conform to the certain set of rules (described in the function's comments). Predicate sb-impl::singleton-p is a tiny form in 'src/code/early-extensions.lisp' file, and it is supposed to check that an input argument is a one-element list. In our context this predicate is used to make sure that there is only one reference to the function object, and only one lvar instance in 'args' slot of the mv-combination instance. Then, the entry point of optional-dispatch, which corresponds to the maximum number of input arguments, is stored in 'ep' variable. In case there are no references to this entry point as to the leaf, the actual call processing begins. First of all, the kind of the call is set to be :local. After this, the entry point 'ep' is added to the set of clambdas which are called by the home clambda of the combination. The set is stored in 'calls-or-closes' slot of clambda instance, and the insertion is performed by sb-c::sset-adjoin function ('src/compiler/sset.lisp'). As a result, the entry point is known to be locally called by the home clambda of 'call' mv-combination.

Then, function sb-c::merge-tail-set is used to join the tail sets of the entry point and the call combination. Let us discuss it briefly:

We suppose our readers to be familiar with the tail call definition, nevertheless there is a short description: a tail call inside a function body is a call whose return value is used as the direct return value of the function. In case a function contains a tail call to itself, it is considered to be tail-recursive. In Python, every clambda instance maintains 'tail-set' slot, which holds an instance of tail-set structure (node.lisp). There is the decent comment about this structure in that file, so please read it. The core tail sets merging algorithm is the next: unless two sets are equal, change all callee's functions tail sets to the caller's tail set instance, and then add all callee's tail set functions to that caller's tail set. In such a way, we end up with the single tail set instance, which represents both caller's and callee's tail sets. Finally, the reanalysis of the caller's return lvar is scheduled.

After this short review, let us come back to sb-c::convert-mv-call. Here is the only interesting thing left – the call of sb-c::assert-lvar-type. This tiny function is defined in 'src/compiler/ir1opt.lisp' file:

It does the additional cast node insertion to make sure that a variable receives the value of the certain type. The original lvar is replaced by the new internal lvar (the replacement is done by sb-c::substitute-lvar function from 'src/compiler/ir1util.lisp'. The substitution idea is to find out the destination node of the old lvar, and to point this node to receive its value from the new lvar. The actual 'pointing' depends on the node type, see the function body for more details). Then, cast node is inserted using sb-c::insert-cast-before (also ir1util.lisp). The whole assertion process is illustrated on Figure 3.8 (the destination node type is assumed to be cif, and the elements names are in accordance with the three above procedures' local variables names):

Let us explain this figure a bit. First of all, we use dashed lines to show the old connections, which were present before the variable type assertion. As one can see, the things were simple. The variable just transfers its value to the node. After cast node insertion, the data flow is the next: the variable value goes to that cast node, and then (after the value type is validated during the runtime code execution) it gets transferred to 'internal-lvar', which finally delivers it to 'dest' node. Regarding the control flow, the compiler inserts cast node just before 'dest' node, by redirecting the control flow after ctran which was pointing to 'dest' node initially. In order to pass the control flow from cast node to 'dest' node, the dummy ctran 'internal-ctran' is created and inserted into the code flow graph appropriately.

[Book] Chapter 3 Local Calls Analysis [part 1]

2010-06-12T01:43:00.000-07:00

In this chapter we are going to discuss the code from 'src/compiler/locall.lisp' file. As the readers know, Chapter 2 was dedicated to sb-c::make-functional-from-toplevel-lambda and to IR1 translation which was started by this function. Then, we meet sb-c::locall-analyze-clambdas-until-done function in the body of sb-c::%compile. This is a point where the next IR1 phase, local calls analysis and inlining, comes into play.

The analysis itself begins with a call into sb-c::locall-analyze-clambdas-until-done. This simple function is the first place where we meet the widely-used SBCL's (and other compilers use it too) approach to the optimization – it may be expressed as “do something until you are sure that there is nothing to do”. The function maintains 'did-something' local variable, and the analysis process runs iteratively until the variable value is not nil.

Each individual iteration is a call into sb-c::locall-analyse-component. This function can do the following:

- just return in case there is no appropriate functional for the analysis in the component;

- delete the functional in case it seems to be not used;

- push the functional into the component's lambdas list and delegate the analysis to sb-c::locall-analyze-fun-1;

- analyse clambdas using sb-c::maybe-let-convert.

The first branch of the analysis is shown here:

This function iterates over the functional reference nodes, and does the next steps during each iteration:

- fetches 'lvar' slot value from the reference node;

- fetches a destination node for the lvar instance;

- checks that the connections between 'ref', 'dest' and 'lvar' are established as shown on this figure:

In case they are, an attempt to convert the call will be made, using sb-c::convert-call-if-possible. How should we understand the figure itself? 'Lvar' receives the value from 'ref' node, and this value is nothing but the function object we are going to call.

When these relations are different, and the combination kind is not :local, the reference node is passed to sb-c::reference-entry-point. Local calls are noted with sb-c::note-local-functional (the result is their names removal from *free-funs* hash table, when these names exist and they are known to be unresolved before the call).

Function sb-c::reference-entry-point calls sb-c::change-ref-leaf after a few checks on the input argument. The latter function is worth to be put here for some discussion:

So, let us see what do we have here. First of all, the reference node is added to the leaf's references list. The surprise comes with the second step, when the reference node is removed from the flow graph using sb-c::delete-ref. This deletion, however, does not mean the instance destruction, as one may think at the first sight. It deals mostly with the related cleanups in the flow graph (the particular steps depend on the reference type. This deletion also may schedule the future flow graph reanalysis, by calling sb-c::reoptimize-component). The next step is the node type derivation, which can be completed directly within sb-c::change-ref-leaf, or by calling sb-c::derive-node-type ('src/compiler/ir1opt.lisp'). Finally, sb-c::reoptimize-lvar prepares the future reanalysis of the stuff which is connected with the reference node target variable.

Function sb-c::convert-call-if-possible performs a lot of checks to make sure that it is permissible to proceed with the call conversion. The most interesting part of the function is here:

There we can see the strange approach to 'entry-fun' slot contents in 'functional' structure. As the comment there (node.lisp) says, it may contain both external entry point (XEP) for the function, or the function itself. So we spend the additional time in let to find out the original function for sure.

Function sb-c::maybe-expand-local-inline (locall.lisp) is quite long to show it here, but it is important to understand what it does. The function attempts to handle the calls to the functions whose 'kind' slot contains :inline. It begins with checking the compilation policies, because inlining is reasonable only when users are interested in the code speed more than in the code size. Then it performs IR1 conversion of the functional inline expansion. When the functional cannot be inlined, the tag locall-already-let-converted will be thrown, and the original functional will be returned. In case of success, sb-c::change-ref-leaf is used to finish with the expansion, and the result of the expansion conversion is returned.

[Book] Chapter 2.5 Custom IR1 Translators [part 3]

2010-06-06T10:17:00.000-07:00

Translation of %primitive form requires some preliminary explanations. First of all, what is %primitive? We haven't meet this construction so far. So, %primitive designates a 'simple enough' operation which is known by IR2 backend and whose name is stored in sb-c::*backend-template-names* hash table ('src/compiler/backend.lisp') as a key. More precisely, 'simple enough' should be read as Virtual Operation (VOP) here. At this time, when we are talking about IR1 phases, it is enough to know that VOP is an abstraction of an elementary operation in the compiler backend. All Lisp forms are eventually represented using VOPs in Python, and VOPs are then translated to machine codes. The virtual operations itself are defined by sb-c::define-vop macro from 'src/compiler/meta-vmdef.lisp' source file.

Processing of %primitive in IR1 translator is simple: a VOP template is fetched for the given VOP name, and the input arguments amount is verified to match that template. After a few more checks, %primitive gets translated into %%primitive. The latter is handled during IR2 phases.

Flet and labels translators share some common functionality, for example, they both use sb-int::parse-body function to deal with the input definition's body. Let us see flet IR1 converter first:

It may be considered to be pretty simple. Notice the usage of sb-c::extract-flet-vars for the local functions definitions analysis (this function is also used in labels converter), the current lexical environment modification (so the defined functions are lexically visible in the inner code), and sb-c::ir1-convert-fbindings call, which is used to finish with flet translation. Since the last function is present in labels converter as well, let us look at it closer:

It has two branches, and the more interesting and complicated one is connected with the dynamic extent of the defined functions. The next figure helps to understand the conversion process:

As one can see, the figure is a typical pattern of the conversions which involve cleanups (for example, compare it with the figure for tagbody). The full meaning of %%allocate-closures form will be clear for us during IR2 phases discussion (note that there is also %%allocate-closures IR1 converter, but it uses %allocate-closures – with a single percent prefix – to express the conversion semantics).

Labels IR1 converter differs from flet due to 'placeholder functions' usage. They reflect the difference between these two approaches to the definition of local functions – when one uses labels, it is permissible to reference the local function within its own body. So, the conversion of local functions in labels goes in two phases - during the first one they are processed with 'dummy functionals' present in the lexical environment, and during the second one the references to these dummies are substituted with the references to the real local functionals. Please refer to the converter code to see this smart solution in more details.

Setq IR1 converter delegates the main part of the process to sb-c::setq-var function. Before calling it, the converter performs a lot of checks and verifications regarding the destination and the source. Function sb-c::setq-var is simple and small – the only specific thing it does is the generation of set node.

The last IR1 converter which we will discuss in this chapter is the one for multiple-value-call. Its code is given below:

We assume our readers to be quite familiar with typical IR1 converters at this time, so we do not give a figure here. Among the important things, please note 'combination/mv-combination' nodes creation, and function's arguments processing in the loop. Obviously, the call itself (we may consider the function's node to represent the 'actual call') occurs after the evaluation of the arguments, as one can guess from the converter code.

It is interesting to see that our initial example, (defun f (x) (* x 3)), also uses combination nodes. To check this, just put the breakpoint in sb-c::ir1-convert-combination. You will see not only the multiplication conversion, but some internal forms (like %verify-arg-count) processing as well.

We consider Chapter 2 to be finished at this point. Author hopes that the readers have some general view of IR1 translators and the raw Lisp forms processing during IR1 phases now. Some special cases, like macrolet conversion, are not covered in this draft of the book, but the key information about early IR1 phases is present.

[Book] Chapter 2.5 Custom IR1 Translators [part 2]

2010-05-30T03:20:00.000-07:00

The special operator tagbody is handled by this translator:

The translator uses a supplementary function to analyze the body, sb-c::parse-tagbody (from the same source file). For the IR1 conversion, it performs the next steps:

- allocates a dummy control transfer, a new entry and a new cleanup node;
- collects a tag and its control transfer for all tags in the body;
- converts all segments using sb-c::ir1-convert-progn-body, and links 'result' lvar with the last segment's return value. Notice the tricky starts/ctrans collection: 'starts' has the dummy control transfer as the first list element, and 'ctrans' has 'next' control transfer as the last list element. This allows to have the elegant solution with mapc later, when control flow goes through all tags and reaches 'next' ctran eventually.

The conversion result is shown on this figure:

The translator uses the value of the last segment as a result, so we show it separately with 'last-tag' control transfer.

Another IR1 translator which is tightly coupled with the above is the one for go special operator. Its code is here:

As one can see, it is pretty simple. The translator searches for the tag to go in the current lexical environment, where the tag has been stored by tagbody converter. Then the code flow will be start → exit → tag-ctran. Notice that 'result' lvar is not touched at all. We do not give the explanatory figure here, due to the trivial nature of the conversion.

Let and let* converters delegate most of their work to other functions. They both use sb-c::extract-let-vars to extract the essential information about the declared variables. After that, the familiar to us functions parse-body, processing-decls, ir1-convert-lambda-body, ir1-convert-aux-bindings and some others do the rest of the conversion. The main idea of both these conversions is that they are performed in the modified 'post-binding-lexenv' lexical environment.

Catch, throw and unwind-protect share some similar principles of the conversion. They are implemented as wrappers over their body code, and use internal forms %within-cleanup, %catch, %throw and %unwind-protect to express the conversion in more low-level terms.

Let us look at %within-cleanup IR1 converter closer. Here is its code:

The things which happen during the conversion are illustrated on this figure:

Some manipulations with lexical environments and cleanups are not shown here, you can read about them in the source code comments.

[Book] Chapter 2.5 Custom IR1 Translators [part 1]

2010-05-23T05:05:00.000-07:00

There are several Lisp operators which require special processing during their translation to IR1. In order to handle them, SBCL developers introduced custom IR1 translators. The advantage of this approach is that we can use sb-c::def-ir1-translator macro to register our own handler, without any static dispatches we have seen earlier in this chapter.

What does this macro do? From the sources in 'src/compiler/macros.lisp' we can say the following: it defines a function named sb-c::ir1-convert-NNN, where 'NNN' is the Lisp operator name one wants to convert using the custom translator. This function is registered as :ir1-convert info value for the Lisp operator, so sb-c::ir1-convert-functoid can fetch it and do the call. 'Info' functionality in SBCL is a wrapper over a hash table and it allows to store some data which corresponds to the key. It may happen that we will discuss 'info' in the appendix A.

The defined converter works using the same input arguments as his static friends (the start ctran, the next ctran and the result lvar). The only difference is that it can have a full lambda list as the first argument. For example, let us look at this translator:

Upon a call it will do the next things:

- allocation of the three control transfers and the three blocks to represent the condition and two execution branches;

- allocation of the appropriate cif node;

- conversion and insertion of the condition testing code after the 'start' control transfer;

- linking together predicate, consequent and alternative cblocks (because in general case execution may go in any of the two branches);

- conversion and insertion of 'then' forms after 'then-ctran' control transfer;

- conversion and insertion of 'else' forms after 'else-ctran' control transfer.

Here is the figure which shows the result of if conversion:

This figure requires some additional explanations. First of all, we use green arrows to show the control flow, and orange arrows to show the data flow. Why do we need such abstractions? Just because there are sb-c::ir1-convert calls inside the converter body. These calls transform 'test', 'then' and 'else' Lisp expressions to some sequences of the blocks. In general we cannot say how to represent these sequences, so we substitute them with 'control flow' concept, and their results assignments with 'data flow' concept. As usual, we show only the slots which are relevant to the figure context. Some structures, like 'start', are shown without any slots at all.

To debug this converter, one should enter the next code in REPL:

(trace :encapsulate nil sb-c::ir1-convert-if :break t)

Notice that :encapsulate keyword is required due to the dynamic nature of the call. The author received this valuable advice from the anonymous reader of this book draft.

There are thirty three custom IR1 translators in SBCL (for version 1.0.38). The author cannot cover them all in this book, so let us look only at the 'interesting for him' ones. They are: block (do not confuse it with cblock data structure), retrun-from, tagbody, go, let, let*, flet, labels, setq, throw, catch, unwind-protect, multiple-value-call. We also will cover some internal forms translators, like %primitive.

Notice that almost all IR1 translators are defined in 'src/compiler/ir1-translators.lisp'.

Block translator is shown on this figure:

The conversion result is illustrated on this figure:

First of all, we have introduced the new symbol “+” on this figure. It means that the marked slot holds a list of values, and the object which is pointed by the arrow is added to that list.

About the block conversion in general, we should say that it involves the new entry and cleanup nodes creation. The entry allows us to exit the block using return-from, and the cleanup handles the exit-related stuff. The dummy control transfer is needed to connect 'entry' node with the in-block code during IR1 conversion in sb-c::ir1-convert-progn-body. You probably know that defun macro wraps the function form into the block whose name is the function's name, and we always can use return-from inside the function.

Since we have touched return-from a bit, let us discuss its IR1 converter as well. Here it is:

The conversion process is illustrated by this figure:

We use “?” symbol to show that the block relationships cannot be determined. This is because 'exit-ctran' is not likely to be :unused at this point, and the results of a call into sb-c::%use-ctran are not known (it has several branches).

Although the idea of return-from conversion is simple, we should explain its connections with block conversion. They can be seen when one analyses the result of sb-c::lexenv-find macro in the return-from converter. This result is the list passed to sb-c::make-lexenv in block converter (after :blocks keyword). This list contains a cons cell with the block name as a symbol, and the value of 'env-entry' variable, defined as a list of 'entry' node, 'next' ctran and 'result' lvar. These three are extracted and used in the return-from converter. Such approach makes it possible to jump out of the code block, by passing the control outside of the block, and by substituting the block's evaluation result with the one evaluated in return-from.

[Question] Is sb-c::ir1-convert-if redundant?

2010-05-19T10:22:00.000-07:00

Well, I have found that my last post contains a mistake. In fact, sb-c::ir1-convert-functoid does not call any IR1 converters dynamically. To check this, just trace sb-c::ir1-convert-if (defined by sb-c::def-ir1-translator macro) when compiling

(defun f (x) (if (= x 2) (+ x 1) (+ x 2)))

and you will see that it is never called.

I have tried several code snippets, but the result is the same.

So, I will probably continue Chapter 2 till the very end of the functional creation.

But can somebody tell me why the code defined by sb-c::def-ir1-translator seems to be not used at all? Should I try some special example to see it invoked?

[Book] Chapter 2.4 From Lisp Forms to IR1 Functionals [part 4]

2010-05-16T01:50:00.000-07:00

In sb-c::ir1-convert-special-bindings the translated Lisp form can go in two branches, depending on the presence of special variables in that form. When talking about our simple example, (defun f (x) (* x 3)), it goes directly to sb-c::ir1-convert-aux-bindings. The second branch adds the cleanup code for these variables. Function sb-c::ir1-convert-special-bindings is called four times during the example compilation, since sb-c::ir1-convert implicitly uses sb-c::ir1-convert-lambda-body, and the recursion occurs. Frankly speaking, recursive nature of IR1 translation code makes the compiler frontend smaller, but inconvenient for analysis and explanation – just because we need to track a lot of recursion levels.

Then, in sb-c::ir1-convert-aux-bindings our example code initially goes directly to sb-c::ir1-convert-progn-body ('src/compiler/ir1tran.lisp'). At this point we should stop and look at the process in a more detailed way.

This function receives 'start' and 'next' ctrans, 'result' lvar and the body – the list of Lisp forms which should be converted. The last form evaluation value will be connected with 'result', and all Lisp forms IR1 translations will be inserted between 'start' and 'next' control transfers.
When the forms list is empty, sb-c::ir1-convert-progn-body assumes these “non-existing” forms evaluation result to be nil, and calls sb-c::reference-constant to put the constant reference into the code flow graph.

Usually the forms list contains one or more expressions, and they are processed in a loop. In general case each form passes two stages: the instrumentation for code coverage (more precisely, for the certain debugger commands) in sb-c::maybe-instrument-progn-like, and further conversion in sb-c::ir1-convert. Let us postpone the instrumentation discussion, and focus on the conversion.

All of the processed in the loop forms receive a new ctran instance, and then they are passed to sb-c::ir1-convert along with that instance.

As the comment says, this conversion ignores all but the last expression value. This is why all but the last Lisp forms are passed to sb-c::ir1-convert with the third (it corresponds to 'result' lvar) argument set to nil.

Variable 'this-start' is needed in order to carry the last control transfer instance between the loop iterations.

Function sb-c::ir1-convert is used not only in the above code, but in many custom IR1 translators (they are the subject of Chapter 3). Here it is:

Function sb-c::ir1-convert is widely used, because it acts like the universal dispatcher – that is, it can convert any valid Lisp expression. The actual job gets delegated to one of the four specialized converters.

The first, sb-c::ir1-convert-var, deals with variables (including alien) and symbol macros. It is easy to understand, because it is comparatively small. The more interesting case is sb-c::reference-leaf, which consists of two parts: the first finds a leaf instance, and the second inserts a reference to it into the flow graph.

We will skip the search code, but focus on the actual insertion instead. The appropriate sb-c::reference-leaf sources fragment is shown on this figure:

First of all, a new ref node instance for the given leaf is created. This node is pushed to 'refs' slot of the leaf, and it is marked to be a “used leaf”. The node is inserted after 'start' control transfer by sb-c::link-node-to-previous-ctran. Then, the special type cast node may be inserted to coerce the result. That's all we should know about a leaf processing at this time.

It should be said that sb-c::reference-constant works in the same way as the simpler (without the type cast) case of sb-c::reference-leaf. So we will discuss the last of the four specialized converters, sb-c::ir1-convert-functoid. As one may guess from the name, it accepts everything which looks like a function call and which does not fit in previous cases. This converter can act in two ways: call (dynamically, through funcall) a particular IR1 translator in case it is defined for the Lisp form, or delegate the job to sb-c::ir1-convert-common-functoid.

The latter function is a dispatcher as well. It uses sb-c::ir1-convert-global-functoid, sb-c::ir1-convert-local-combination, sb-c::ir1-convert-srctran, sb-c::ir1-convert, sb-c::ir1-convert-combination, sb-c::ir1-convert-lambda. The additional thing to say is that all these eventually use sb-c::ir1-convert, so the true recursive mess occurs. At this point we should consider our analysis of IR1 conversion code flow to be finished. The translation process will vary significantly depending on the input form, and it is not very helpful to track our simple example through it.

As a conclusion for this chapter, we should express the main idea of IR1 conversion: the transformation of Lisp forms into individual nodes in the code flow graph. Notice that nodes are inserted linearly, without any flow analysis. It will take place during the next IR1 phases.

However, our analysis of IR1 conversion elements is continued in the next chapter, where we will look at custom IR1 translators, which were mentioned in sb-c::ir1-convert-functoid description. They are quite important and interesting, so we hope that we can cross our simple example boundaries to study them.

[Announcement] Updates schedule

2010-05-12T00:07:00.000-07:00

In order to make the reviewing process to be more convenient, I will put new chapters to this blog once per week - on Sunday.

[Book] Chapter 2.4 From Lisp Forms to IR1 Functionals [part 3]

2010-05-09T03:37:00.000-07:00

Finally, sb-c::process-decls returns control back to sb-c::ir1-convert-lambda. The latter determines whether optimization policies allow wrapping the input forms into the debug catch (by default this does not happen), and also specifies the forms' return value type explicitly by wrapping them into special operator 'the' – only when it is different from the default (or 'wild') type.

In sb-c::ir1-convert-lambda further form conversion can go in two branches. The first is a call into sb-c::ir1-convert-hairy-lambda. It happens in case the lambda has the arguments list with optional or keywords arguments. The simpler lambdas are handled by sb-c::ir1-convert-lambda-body.

Since we are going to follow the easier case, let us say a few words about the complex first. It creates optional-dispatch structure instance to represent the optional arguments, and adds it to 'new-functionals' slot of *current-component*. Actual arguments conversion occurs in sb-c::ir1-convert-hairy-args.

So, in sb-c::ir1-convert-lambda-body our Lisp form is going to be converted into clambda structure. This is a long function, but anyway we will dig into it now, because it makes a lot of important steps towards IR1 representation of the input form.

First of all, sb-c::ir1-convert-lambda-body creates four structures instances: bind, clambda, ctran and lvar. The first represents input arguments bindings, the second is the resulting IR1 functional which will be returned, the third represents the control transfer to the 'result' node, and the last is the variable which will hold this lambda expression result after the body evaluation.

Then 'home' slot of clambda instance is set to itself. It also becomes a home lambda for all input arguments' lambda-var structures. In case the variable is special, the corresponding global-var structure will be added to the bind node lexical environment. Otherwise, the original lambda-var instance will be used, as you can see on this code fragment:

This tiny code snippet is all you need to recollect when your friends ask you how do special variables work in Common Lisp :)
The next part of the function creates the lexical environment which will be effective across the input lambda body, and establishes relationships between it, clambda and bind structures instances:

At this point we have the next connections between the main data structures:

What begins after that is a bit complex. So let us explain this code line by line:

The interesting and widely used function sb-c::ctran-starts-block ('src/compiler/ir1util.lisp') returns a cblock structure instance for the given ctran. The block is started by that ctran. Namely, the next steps are performed to create the block:

- check that 'block' slot of ctran instance is empty;

- a new cblock instance is created and ctran is stored in it's 'start' slot;

- next and previous blocks for the new block in the code flow graph are determined as the last current component's block and its predecessor, respectively;

- references between these three blocks and ctran are set;

- ctran is asserted to be not used, and the new block is returned.

The graphical representation of the result is shown on this figure (old connections between the last and the last but one blocks in the component are shown using dashed lines):

As one can see, the new block is inserted before the last block in the component, and prev/next slots for all three blocks are updated accordingly.

In case ctran already starts some block, sb-c::ctran-starts-block simply returns that block.

But let us go back to the code snippet from sb-c::ir1-convert-lambda-body. The next thing it does is cretrun and tail-set instances creation (both from nodes.lisp file). These two are linked with clambda structure instance appropriate slots. Then the destination of 'return-lvar' variable is set to 'return' node. After that, a tiny function sb-c::link-node-to-previous-ctran from 'src/compiler/ir1tran.lisp' is called to connect the return node with 'result-ctran' control transfer. Finally, 'return' node becomes the last node in our new code block, and this code block is linked with the current component's tail block by sb-c::link-blocks ('src/compiler/ir1util.lisp').

The final part of sb-c::ir1-convert-lambda-body which we should analyse is the next:

First of all, the macro sb-c::with-component-last-block ('src/compiler/macros.lisp') wraps all those expressions and executes them inside unwind-protect, to guarantee that the component state will be consistent upon exiting it. This macro also sets the component's last block to the given one temporarily, as you may guess from both its code and its name:)

What happens inside is quite familiar. Two new ctrans are created, and linked with 'bind' node. A new thing is sb-c::use-ctran from 'src/compiler/ir1tran.lisp'. It is easy and left as an exercise for readers. Function sb-c::ir1-convert-special-bindings continues the conversion process, and we will look into it below. The last two lines make 'bind' block to be the first block in the component's code flow graph, and push the resulting functional into a list from 'new-functionals' slot of the component.

[Book] Chapter 2.4 From Lisp Forms to IR1 Functionals [part 2]

2010-05-05T12:33:00.000-07:00

We will select type declarations, as the most important in this book context. They are handled by sb-c::process-type-decl function from 'src/compiler/ir1tran.lisp'.

Assume that we are compiling a form like this:

(defun h(x) (declare (fixnum x)) (* x 3))

Then sb-c::process-type-decl will receive the next arguments:

- the type declaration form: (fixnum x);
- the instance of lexenv structure;
- the one-element list with lambda-var structure, which corresponds to 'x' variable;
- the declaration context processing keyword, :compile.

Here we should stop and explain what is lexenv structure. We didn't touch it in chapter 2.3, because it is not defined in 'src/compiler/node.lisp' – we should open 'src/compiler/lexenv.lisp' instead. This structure contains all information about a lexical environment in which a Lisp form is being converted into IR1. By default this argument contains a value of *lexenv* global variable, which was bound in sb-c::make-functional-from-toplevel-lambda.

So, sb-c::process-type-decl begins with obtaining a type structure for the given type specifier. Then it iterates over the declared variables names list, calling sb-impl::program-assert-symbol-home-package-unlocked on each name. You probably know that SBCL has COMMON-LISP package locked by default, and all modifications attempts for symbols in that package are checked using that function. This is why the crazy code like this:

(defun ff() (declare (fixnum *standard-output*)) ())

will signal the error:

Compile-time error:
Lock on package COMMON-LISP violated when declaring the type of *STANDARD-OUTPUT*.

When modifications are allowed, a variable name is matched with the appropriate lambda-var structure using sb-c::find-in-bindings function first. In our case this gives the result, because we have declared 'x' as a lambda argument. The alternative ways to find something which is connected with a variable name are sb-c::lexenv-find macro ('src/compiler/macros.lisp') and sb-c::find-free-var function. As one can guess, after the failed lookup in the lambda arguments list, Python tries to find a variable in the lexical environment, and, as the last resort, the global scope is checked.

We have said 'something', because the last two kinds of search are not obligated to return lambda-var structure. It may be also a foreign (alien) variable, as well as a symbol-macro.

Anyway, in our example we got a valid lambda-var structure, and its further processing is connected with the detection of the suitable type. We cannot always use the proposed type, because a variable may be already typed. So Python derives the final type using sb-kernel::type-approx-intersection2 ('src/code/late-type.lisp').

Finally, 'type' slot of lambda-var structure for our 'x' argument will contain fixnum type, which is printed as # <SB-KERNEL:NUMERIC-TYPE FIXNUM> by Lisp printer. That's all about type declarations handling for lambda arguments. For variables from the lexical environment, or unbound variables, the processing of the type declarations involves the lexical environment update instead of setting the variable type in lambda-var structure.

To finish with declarations, we should say a few words about other kinds of them. Special declarations are handled by sb-c::process-special-decl. Its job is to ensure that a variable is not ignored or declared locally special, as well as that a variable is not a symbol-macro. Finally, 'specvar' slot of lambda-var structure will be set to an instance of the appropriate global-var structure, returned by sb-c::specvar-for-binding.

Functional types declarations are processed in sb-c::process-ftype-decl. The things here go similarly to the types processing, what is even stated in the function comment, so we leave this case analysis as an exercise for readers, as well as the below cases:)

Handling of 'inline/notinline/maybe-inline' happens in sb-c::process-inline-decl. These declarations affect 'inlinep' slot of the current IR1 functional, or a member of its lexical environment – depending on the local/global nature of the declaration.

Then, 'ignore/ignorable' case goes to sb-c::process-ignore-decl. We do not stop here at all, that is easy.

Declarations about optimization policies are handled by sb-c::process-optimize-decl. This function's return value is used to update '%policy' slot in the current lexenv structure (strictly speaking, a new instance is created, but it includes the old lexical environment as a source of default values).

Declarations 'muffle-conditions/unmuffle-conditions' also affect the lexical environment. They allow to suppress or to enable compiler's diagnostic messages.

'Values' declaration affects 'result-type' variable, which was discussed above. That is, this declaration specifies a return type of the lambda.

Declarations 'disable-package-locks/enable-package-locks' are connected with changes in 'disabled-package-locks' slot of the current lexical environment's structure instance.

Declarations about dynamic extent belong to a special topics list. We will return to them in the appropriate chapter.

[Book] Chapter 2.4 From Lisp Forms to IR1 Functionals [part 1]

2010-05-03T12:18:00.000-07:00

Now, when we are a bit familiar with IR1 data structures, let us go ahead and see the actual transform mechanism which converts a Lisp form into IR1 functional. It begins with a call to sb-c::make-functional-from-toplevel-lamdba in 'src/compiler/main.lisp'. This function binds *current-component* variable to a new empty component, modifies the component kind to be :initial, and calls sb-c::ir1-convert-lambdalike to obtain the functional entry function. The functional structure as a whole is returned by sb-c::ir1-convert-lambda later. That functional is considered to be :external, and both the functional entry and the functional itself are assumed to have external references. The result of these actions is the initial (unoptimized) IR1 functional.

After this high-level overview let us dig into the process deeper. First of all, what is the empty component? In 'src/compiler/ir1util.lisp' you can find sb-c::make-empty-component function. It does the following:

- creates two empty blocks called 'head' and 'tail';

- creates a new component whose entry and exit points are the above blocks, 'head' is the entry block and 'tail' is the exit block;

- sets up references between the component and blocks;

- sets up references between blocks.

The resulting empty component is shown on the figure:

On the figure arrows begin at the structure which owns a slot, and point at the slot value. Slot names are separated by horizontal lines. 'Res', 'Tail' and 'Head' are variables names from sb-c::make-empty-component function. Structures names are just below them. We show only the slots which are relevant in a figure context, and we will use this approach to illustrations through the whole book.

As one can see, the empty component consists of three structures and may be considered to be simple. Control flow inside this component goes from 'head' block to 'tail' block. Since they are not associated with any nodes, nothing is going to happen in the component scope during its future execution.

Function sb-c::ir1-convert-lambdalike performs different steps to convert the input expression, depending on a kind of the input lambda. We are mostly interested in discussing the named-lambda case, because all functions compilations go through this branch. When talking about the example from previous chapters, there will be two calls of this function. The first handles the toplevel lambda:

and the second handles the named lambda:

Pure lambda case goes directly to sb-c::ir1-convert-lambda. With named-lambda things get a bit complicated:

First of all, the presence of a lambda name is checked, and the lambda expression is obtained. In case the name is valid, IR1 functional for the lambda will be received from sb-c::ir1-convert-lambda. Lambdas with missing or invalid names are converted in the alternative condition branch.

Before the call into sb-c::ir1-convert-lambda, another call to sb-c::get-defined-fun occurs. This function is located in the same file, 'src/compiler/ir1tran-lambda.lisp'. Its job is to check whether there is an entry for the given name in *free-funs* hash, and to create defined-fun structure instance for the named lambda being compiled. This instance will hold IR1 functional from sb-c::ir1-convert-lambda in 'functionals' slot. There may be several functionals corresponding to the single defined function, and this slot holds them in a list.

The most interesting part of the Lisp forms transformation into IR1 begins in sb-c::ir1-convert-lambda. This function starts with verifying an input lambda expression structure and decomposes it on three parts: forms, declarations (decls) and documentation (doc). Also, all lambda form arguments declarations are converted into IR1 representation by passing them to sb-c::make-lambda-vars. We will analyze this process now, since the results are used in the subsequent calls.

So, sb-c::make-lambda-vars begins with the classification of the input variables declarations, by delegating this task to sb-c::parse-lambda-list function from 'src/compiler/parse-lambda-list.lisp'. The latter file is a small one (210 lines in SBCL 1.0.38), and the principles of the parsing are pretty straightforward – sb-c::parse-lambda-list-like-thing acts like a tiny finite state machine (FSM), by iterating over the supplied lambda arguments list and checking their order (more precisely, keywords order) to be right, along with collecting required information about them. Finally, multiple values (twelve! But this is not a limit – I have seen a function returning twenty three values in one Lisp project) are returned to sb-c::make-lambda-vars. The latter handles all kinds of the lambda vars, with one common step – a call into sb-c::varify-lambda-args to obtain a new lambda-var IR1 structure. Then, depending on the kind of an lambda argument (&rest, &optional etc.), 'info' slot of this structure will contain the appropriate arg-info structure instance. Upon exiting from sb-c::make-lambda-vars we do not have arguments declarations – we have a list whose elements are coupled IR1 structures lambda-var and arg-info:

After this short overview of the lambda parameters conversion, let us return to sb-c::ir1-convert-lambda. The next step it performs is connected with declarations analysis – namely, with the second part of the input lambda decomposition. This job goes to sb-c::process-decls ('src/compiler/ir1tran.lisp').

Declarations are the source of type-related information for a Lisp form (not only about types, but compiler is mostly interested in explicit types knowledge – it makes code optimizations easier). In order to handle function return type declarations, sb-c::process-decls maintains 'result-type' local variable, and updates it upon every declaration analysis by calling sb-kernel::values-type-intersection to narrow the result type. Individual declarations are processed in sb-c::process-1-decl. This function dispatches all declarations to more specific handlers, like sb-c::process-inline-decl. Looking into this code is a fast way to learn about all types of declarations in Common Lisp:)

Let us follow the processing of a single declaration till the very end, just to see how they are handled. We also will benefit from the fact that there are common steps in the declarations analysis.

[Book] Chapter 2.3 Primary IR1 Data Structures

2010-05-03T11:21:00.000-07:00

Every code flow representation in a compiler frontend is some kind of a hierarchy, and IR1 is not an exception. This kind of relationships appears due to the same structure of an input construction, for example, a function in general case contains expressions, and expressions usually have operands – and when we build the simplest model, we may create a data structure called 'function', with a slot named 'expressions' and so on. In SBCL we see a bit complicated variant of this approach, because the industrial CL compiler should use a lot of supplementary data in order to perform code optimizations in the excellent way it does these days.

During this chapter we will discuss 'src/compiler/node.lisp' file, where almost all Python internal data structures are defined. We recommend you to read it carefully before going forward – otherwise it may be hard to understand this chapter and the entire IR1 phase as well. There are many useful comments.

For a single structure, we copy its sources without included comments to this chapter. Comments about the slots are present in the original file, and we will not repeat them. Our current goal is to learn about structures relationships and purposes, not about the individual slots.
The first one we should look at is 'functional' structure:

You probably have noticed that this structure includes another one – 'leaf', here it is:

Just to stop that chain of includes, we should explain what is 'sset-element' structure. This one allows a structure which includes it to be an element of a sparse set (defined in 'src/compiler/sset.lisp'). More info on this is not required in this chapter, so let us return to the two above structures.

'Functional' is a basic element of a Lisp form representation in IR1 as a whole, because it is extended by other data structures which add more information about toplevel forms (and finally 'clambda' structure incorporates all info about a Lisp form).

'Leafs' are code flow graph elements which are not connected with the actual code flow (they have no output paths, and can be only referenced by non-leaf elements. Namely, there is a special 'ref' structure for this purpose). However, in SBCL this concept is not so straightforward, because data structures like 'optional-dispatch' may extend 'leaf' and contain code flow graph elements (through references) at the same time. This situation probably can be explained when we take into account that a code unit may be a 'leaf' in the first code flow graph (for example, as a call to the function), and to be the actual second code flow graph itself (which represents that called function definition).

'Component' seems to be the most important data structure in Python. Many compilation stages are operating on components, not functionals. This structure is shown below:

Components have code blocks as their entry and exit points (you may consider these to be a component boundaries in a code flow graph). A code block ('cblock') data structure is shown below:

Code blocks consist of individual nodes (what we have called 'expressions' in the introduction to this chapter, however, this is not a complete analogy), which are defined by 'node' structure:

Nodes which produce a value are represented by 'valued-node' structure:

Nodes which reference leafs are instances of 'ref' structure. Notice that it is derived from 'valued-node' as well:

Combinations (function calls) are represented by special nodes – 'basic-combination', 'combination', 'mv-combination'. The last two do not add any new slots, so we will only show the parent structure:

Type check operations in IR1 involve 'cast' nodes:

Control transfers inside a code block (between nodes) are represented using 'ctran' structure:

Data transfers between nodes use 'lvar' structure:

Lambdas with optional arguments involve 'optional-dispatch' structure to handle them in IR1:

Arguments itself are represented by 'lambda-var' structure:

Finally, there is a 'clambda' structure, the thing which corresponds to the entire Lisp form in IR1:

Return values of a lambda are handled using 'creturn' structure:

Structures which are related to non-local exits, and some IR1 structures which extend the primary structures by adding a few slots are out of this chapter scope. We will talk about them in the appropriate chapters, where they are likely to be met.
Finally, this figure may help you to grasp the nodes/blocks/components relationships in a code flow graph. Flow direction is shown using arrows:

[Announcement] SBCL Users & Developers Group in Linkedin

2010-04-27T13:23:00.000-07:00

I am not sure whether it is a really good idea, as well as that I am a right person to do that when there are many mature SBCL developers around (who are probably better candidates to own such a group), but anyway I have created 'SBCL Users & Developers' group in Linkedin. Its goals are:

- to see how many people use SBCL
- to gather some statistics about OS families/CPU architectures where SBCL is popular
- to discuss CS domains where Lisp and especially SBCL are useful these days
- other questions which are connected with gathering some SBCL-related statistics.

This group is open for everyone. Feel free to join it:)

Also, please note that this group is not a place to report bugs, to ask about SBCL internals or some particulars etc. Please use mailing lists to do that, as you have been doing up to the present.

[Announcement] Some delay of Chapter 2.3

2010-04-26T12:32:00.000-07:00

In order to write Chapter 2.3 "IR1 Data Structures" and make it to be interesting for readers, I need to learn more about these structures usage during IR1 phase. So there will be a delay in a week or two before I start posting that chapter's parts. Thank you for reading the previous ones, your notes were helpful and I have corrected some mistakes in the book using them :)

[Book] Chapter 2.2 Why IR1?

2010-04-23T13:05:00.000-07:00

In the next chapter we will explore IR1 data structures and relationships between them. It is necessary to have a clear vision of these, because Lisp forms transformations into IR1 are hard to understand without the appropriate knowledge about the target representation. But one may ask about the reason to have IR1 in Python, and we should explain this first.

Let us start from the general questions. Why do we need IR1 at all? What is the problem with applying code optimization techniques and algorithms directly to Lisp forms? And what are the advantages of IR1 over the raw Lisp code?

To answer these questions, we should recall that Common Lisp has simple syntax, but complex semantics. It means that its Abstract Syntax Tree (AST) contains a rich set of nodes which require a different kind of processing in the compiler. In case we want to apply code analysis algorithms directly to Lisp forms, we will need to carry a lot of rules to handle every individual node type, as well as these nodes combinations. So, passing the original Lisp code through a complete compiler frontend, with every stage being knowledgeable about the full Common Lisp semantics sounds to be a bad idea.

What is the alternative? We definitely need to have some semantics reductions per node in order to keep our code transformations rules amount moderate. And the best way to simplify code transformations is connected with making the code representation less diverse. It means that we should select some set of primitives which is enough to satisfy the next goals:

- primitives itself should be as simple as possible;

- different primitives count should be as small as possible;

- we can represent the initial language (source code) in terms of these primitives and connections between them without any semantics loss.

So far, so good. But how to select this minimal set of primitives and, what is the hardest thing, how to prove that the selected set satisfies the last, third principle? Primitives selection evolves naturally from the input language we are going to represent. For example, we definitely need something like 'code block', 'unconditional branch', 'conditional branch', 'variable', 'scope' etc. for almost any programming language representation. They may have another names, they may be implicit (represented by relationships, not data structures), but anyway they are fundamental elements.

To prove that the selected primitives set is exactly enough for the language representation means to prove that there is a valid, semantics-preserving representation for any code one may write with that language. Since there is infinite number of ways to combine a language operands into what we call 'a program', there is no way to strictly prove that in general case (or I have missed something here? In case you know such practical verification methods, please correct my words). So, in real-life compilers this primitives set is a bit redundant. Just to match the input language for sure, without trying to reach the theoretically minimal primitives set (here I probably should say something about Turing machine, which is guaranteed to be a valid representation for any computational process, but I think that we should stay closer to daily practices than to the general theory). You probably know that there are a lot of bugs in Python (at least in version 1.0.37). Some of them are connected with IR1 inconsistencies. So, you may be sure that SBCL is a real-life compiler, with good but not ideal internal code representation selected :)

After selecting the primitives set, we should think about relationships between them. One may guess that graphs are the most natural representation of a code flow. They are, due to their definition: code flow graph = primitives (nodes) + relationships (edges). Plus, graphs mining algorithms are established and well-known. So there is no need to reinvent the wheel, we may just apply a lot of proven techniques.

To finish with the theoretical diving, let us say about drawbacks of the simpler representations. We live in the dialectical world, and every win brings some fail as well. In our case the fail is connected with the length of the equivalent IR1 representation – it is much longer than the Lisp code from which it was generated. Semantics is the same, but due to the simpler representation, it takes more elements involved. The obvious analogy is that decimal 256 has the same value (semantics) as binary 10000000, but due to the only two elements – 1 and 0 – used in the latter representation, it takes longer to reflect the same semantics. I am sure that your CS professor has already told you something similar, so I am sorry for such a falling into ABC of the information theory.

After this short introduction, let us see the primitives and relationships which were selected to be a core of IR1 by its architects.

[Book] Chapter 2.1 What Happens With Lisp Forms Before IR1 Stage [part 3]

2010-04-21T11:28:00.000-07:00

After the macroexpansion the input expression in sb-int::simple-eval-in-lexenv is classified by typecase macro. In our case the classification matches list clause, and the inner code of that clause performs further dispatch based on a first element of the list. This dispatch is interesting in all clauses, so let us analyze all of them.

- function case matches, for example, the next input in REPL:

(function (lambda (x) (+ x 1)))

This returns an instance of a built-in class FUNCTION which corresponds to the given function (as you can see from the example, the function may be anonymous). The case code checks that you have passed exactly one argument, and it is a valid function name. In case it is, the operation is delegated to sb-impl::%coerce-name-to-fun (which is a simple getter for a function definition, see 'src/code/fdefinition.lisp' on this), in case it is not, for example when it is a lambda, the job gets done by sb-impl::%simple-eval (src/code/eval.lisp);

- quote case checks that you have passed exactly one argument, and simply returns it (How simple is quote implementation in SBCL! Without any magic I was hoping to see...);

- setq case first of all checks whether you have passed even amount of arguments or odd. When all is right with that, values are assigned to their destinations in a loop, using calls to set and recursive calls to sb-int::simple-eval-in-lexenv in order to evaluate the values which should be assigned;

- progn case passes control directly to sb-impl::simple-eval-progn-body, in the same source file. Note that it is our case (remember the f(x) macroexpansion?), so we are going to look into it below;

- eval-when at this point is respected only in case it includes :execute situation. Then the enclosing form is evaluated by sb-impl::simple-eval-progn-body. Otherwise nil is returned;

- locally handles the special operator with the same name, by calling sb-impl::simple-eval-locally. In case you wonder about what that operator does, here is the citation from CLHS: “Sequentially evaluates a body of forms in a lexical environment where the given declarations have effect.” So sb-impl::simple-eval-locally does just like that – it mutates *lexenv* variable to match the given lexical environment value, handles given declarations using sb-c::process-decls and then calls sb-impl::simple-eval-progn-body with the lexical environment set to what was returned by sb-c::process-decls (I have no idea how to say this in a simpler way);

- macrolet and symbol-macrolet require to much digging into Python in order to explain their handling. Let us skip them now, and return to this question when we will have more IR1 level knowledge;

- if as a toplevel form is evaluated in place; the code for let and let* is also simple. All other list-like structures go to sb-impl::%simple-eval or sb-impl::eval-in-lexenv. These four cases are shown on the figure:

Note that sb-impl::eval-in-lexenv is a pure wrapper over sb-int::simple-eval-in-lexenv when the Lisp evaluator mode is :compile (default, it may be set to :interpret by assigning that keyword to sb-ext::*evaluator-mode* variable):

As it was mentioned above, our function macroexpansion matches progn case first, and gets processed by sb-impl::simple-eval-progn-body. The essential part of this routine is the next:

One thing you should remember when looking at this code is that do* evaluates variables bindings sequentially, and rest does the same job as cdr. The idea of this processing is trivial: evaluate all progn subforms using sb-int::simple-eval-in-lexenv and return the result from the last one.
So you have just seen how recursive nature of Lisp greatly simplifies the Lisp evaluator. In our case there will be many calls into sb-int::simple-eval-in-lexenv. We can name at least some of them: the first deals with defun macroexpansion and matches progn, the second two handle eval-when forms, then time comes to handle sb-impl::%defun and its arguments... The main thing is not to track them all, but to understand the recursive flow of Lisp evaluation and to imagine its approximate call tree for a given form.
Finally, the recursion ends up with the call to sb-impl::%simple-eval (src/code/eval.lisp), in our case the debugger shows it as

This function encloses the input expression into a lambda and passes it to sb-c::compile-in-lexenv (src/compiler/target-main.lisp). At this point we can state that Lisp forms arrived to Python compiler. After a few minor checks they pass to sb-c::actually-compile in the same source file. It binds a lot of compilation-related global variables (I am not sure that it is reasonable to explain all here, so let us introduce them in the actual usage order), and invokes sb-c::%compile function from 'src/compiler/main.lisp' file, passing the expression to compile along with several other arguments to it.
We are very close to the beginning of IR1 stage now, but before moving further, we should talk a bit about this representation elements and structure. This topic is covered in the next chapter. Take a rest before reading it, and let the Lisp evaluator concept to find its place in your mind :)

[Book] Chapter 2.1 What Happens With Lisp Forms Before IR1 Stage [part 2]

2010-04-19T11:49:00.000-07:00

Function sb-int::simple-eval-in-lexenv classifies the input form and handles it accordingly to the form's kind. First of all the input expression is passed through macroexpand, to get rid of any toplevel macros involved in the form. To figure out what is the result in case of our example function, enter this form in REPL (do not forget to remove the breakpoint which was set earlier – use untrace to do that):

(macroexpand '(defun f(x) (* x 3)))

You will get the next result:

Looks a bit complicated? Well, let us see what we have here. You probably know that eval-when is used to control the evaluation of the enclosed form depending on a set of situations - :compile-toplevel, :load-toplevel or :execute. There is a section in CLHS on this called 'Processing of Top Level Forms', and it is worth to look into it before moving forward with this chapter. In our case a call to sb-c::%compiler-defun will happen during the form compilation time, and a call to sb-impl::%defun will be during the form loading time. These two forms are considered to be toplevel forms, since they are inside of the toplevel progn, so eval-when handles them accordingly.
Function sb-c::%compiler-defun from 'src/compiler/ir1tran-lambda.lisp' file registers the first argument (in our case the symbol 'F) to be a known function by calling sb-c::become-defined-fun-name on that argument. It also performs two minor actions depending on the second and third arguments values, but we can move along without digging a much into it. Just remember that sb-c::%compiler-defun notifies Python at the compilation time about our attempts to compile a function definition with the certain name.
The next interesting thing in the macroexpansion is sb-impl::%defun. It does almost the same that sb-c::%compiler-defun, and even uses the latter to perform the necessary tasks (by setting third argument – compile-toplevel – to nil, notice that in the first (compile-time) call it was t). Namely, it registers the function name to be known:

Also it deletes all warnings connected with the earlier references to the undefined function which is being defined now. See sb-c::note-name-defined on this. Obviously, %defun is available only in target SBCL, due to #-sb-xc-host placed before its definition.
The last but one tricky thing is sb-int::named-lambda. It serves as a marker of a named form during IR1 phase, for example, it is taken into account by sb-c::ir1-convert-lambdalike.
Finally, what is a call to sb-c::source-location which is present at the end of the macroexpansion? There is an example of a compiler macro usage. It is defined in 'src/code/source-location.lisp', and it's job is to instantiate sb-c::definition-source-location structure during the compile-time expansion. In such a way Python records origins of the compiled definitions, namely in 'namestring' field of that structure instance. To learn more about compiler macros, refer to CLHS, as usual:)
You may wonder how our simple definition became such a monster? It is due to defun being a macro. That macro is a bit long to post it here completely, so we will show only the part which contributed the most:

As you see, all above newcomers are present in that macro body.
Okay, let us return to sb-int::simple-eval-in-lexenv and see what happens there with the macroexpansion result. But I almost hear the reader's question: “What will be the result of a defmacro form macroexpansion?” To get the answer, enter

(macroexpand '(defmacro f(x) `(+ ,x 1)))

and observe even bigger monster:

Do not ask me to interpret that:) Let us stick to functions at this time, when we are young and the sun is shining so brightly in Ukraine (I hope that the weather in your country is also nice these days...)

[Book] Chapter 2.1 What Happens With Lisp Forms Before IR1 Stage [part 1]

2010-04-18T05:46:00.000-07:00

In this chapter we are going to gain some practical experience with SBCL Compiler. In case you have not downloaded the sources yet, it is a good time to do that. Go to SBCL download page and get the latest sources there. We also hope that you know what is SLIME and have some experience with it. Obviously, you can use any other editor/IDE you have been using for Lisp development by this time. After downloading the sources, build and install SBCL as described in the 'INSTALL' document from the archive root folder. Eventually you should get version 1.0.37 (current at this time, when I am writing this chapter) up and running.
So, what will be discussed in this chapter? The thing is that Lisp forms do not come to IR1 converters directly from Lisp reader. They are processed by several functions before IR1, and we are interested in understanding their role in compilation process.
The easiest way to see what is going on is to place a breakpoint on sb-c::make-functional-from-toplevel-lambda function, which starts IR1 conversion process. In such a simple way we will discover all chain of major Lisp forms processors. So, let us do that by entering this code in REPL (enter this in SBCL launched directly from console, and do not use SLIME, because in the latter case you will reach the breakpoint immediately due to internal SLIME calls into SBCL, which involve compilations):

(trace sb-c::make-functional-from-toplevel-lambda :break t)

Then we may enter some function definition in REPL, for example:

(defun f(x) (* x 3))

After this the debugger will be invoked. In the debugger prompt type 'backtrace' and hit enter. You will see all the calls chain, from toplevel-init to %compile. Since we have just met a function whose name starts with '%', let us explain this naming convention. It means that the function is strictly internal and should be used only by the same function without leading '%' in the name. Maybe this rule has exceptions, but it seems to exist.
In the backtrace we will start with the sb-imp::repl-fun, because SBCL initialization process is not very interesting for compilers developers:). This function is not a part of Python (Python package is 'sb-c'), and it is defined in 'src/code/toplevel.lisp' file:

This function enters infinite REPL cycle, and on every iteration does three important things: prints REPL prompt string “* “ to *standard-output* stream by making funcall into sb-impl::repl-prompt-fun through *repl-prompt-fun* variable; calls the Lisp reader (through a thin wrapper over read, whose function is bound to *repl-read-form-fun* variable), and passes the obtained Lisp form to sb-impl::interactive-eval. Two things to notice are also the argument 'noprint', which allows to suppress printing REPL prompt and evaluation results, and debugging macro /show0, used widely in SBCL for internal code tracing (this macro prints its argument to console). By default this macro does nothing – to enable its functionality, go to 'src/base-target-features.lisp-expr' file, uncomment ':sb-show' feature and rebuild SBCL. However, it produces a lot of info, so do think six times or more before doing that. We will not enable /show0 in this book.
Well, we have just seen who calls the Lisp reader in REPL. Lets move along to the next function in our backtrace – sb-impl::interactive-eval. In the debugger you can see that it receives the entered form as it is:

(INTERACTIVE-EVAL (DEFUN F (X) (* X 3)))

This function calls into sb-int::simple-eval-in-lexenv, and the only useful things it does itself are updates of many variables with interesting names - +++, ++, *** and so on. Luckily, these variables are defined and well-documented just above the function definition. They are connected with saving old evaluation and reading results before computing new ones:

With the call to sb-int::simple-eval-in-lexenv the serious game begins. This function is quite large, so we will not give its full source code here. Find it in the file 'src/code/eval.lisp' and then follow the rest of this chapter.

[Book] Chapter 1.2 General Python Anatomy

2010-04-16T13:49:00.000-07:00

In this chapter we are going to compose the high-level code flow diagram for Python. But before starting this amazing activity, let us say a few words about compilers in general. It might be useful for people who have too little compilers engineering experience to know the basics from the field. We are not going to be academic, so do not refer to the below as to the scientific definitions.

On the simplest abstraction level a compiler is a computer program which converts a 'source code' into a code which is considered to be a 'target code'. These two kinds of codes obey some set of rules, given by their languages. In general case a source code is represented using a high-level language, and a target code is expressed in terms of a low-level language. Python compiles from the high-level language Common Lisp into a machine code (low-level assembly language) which is specific for a target CPU architecture (x86, x86-64, SPARC etc.).

There are many different compilers in the world, but most of them do a common set of steps (sometimes called 'phases') in order to do their job. First of all they parse the source code to make sure that it is syntactically valid and follows the source language syntax rules. In Python this phase is absent – the syntax of the input forms is checked by the Lisp reader.

The next phase is connected with the source code semantics checks and code optimizations. This step usually requires a special intermediate representation of the input sources, in Python there are two such representations: higher-level IR1 and closer to target code – IR2 (based on Virtual OPerations, VOPs for a virtual machine). IR abbreviation stands for the Intermediate Representation, for sure:). Such representations are better suitable for the code optimization and control flow analysis algorithms, since they often use directed graphs as the underlying data structure.
After all the optimizations and checks are done, time comes to generate the target code. As we have already mentioned above, Python emits assembly instructions for the certain CPU architecture during this phase.
We are going to cover all compilation phases in the next chapters. Let us summarize the above info on this figure:

Obviously, the above figure is a high-level abstraction, which hides a lot of particular code transformations inside Python. We decided to avoid making things complicated in advance:) It will be a good time to see them in more detail later.
To finish with the Python overview, we should say a few words about its source tree structure. In case we call the SBCL sources root directory 'src', most of Python code is in 'src/compiler' subfolder. Things which depend on CPU architecture are further separated to subfolders like 'src/compiler/sparc', 'src/compiler/x86' and so on. Some machine-independent Python source code (mostly related to IR2 phases and code dumping) is in 'src/compiler/generic' subfolder.
We will not talk about individual source files now. It will be better to cover them later in the appropriate chapters along with their functionality and role in Python.

[Book] Chapter 1.1 What Is Python, And What It Is Not

2010-04-16T11:46:00.000-07:00

This chapter contains the very basic things which should be clarified before we start the actual Python code analysis. In case you are an experienced SBCL developer, you should probably skip this and move along to the Chapter 2 where we examine the first stage of the compiler. But if you have just started with SBCL development, it might be worth reading the current chapter.

First of all we should figure out the relationships between Python and other parts of SBCL system. A Common Lisp implementation by SBCL is not only a compiler, but several coupled subsystems, as shown on this figure:

This decomposition is done by functionality, physically there are two main separate components: the runtime application and the Lisp image. The latter includes Common Lisp Object System (CLOS, the implementation is know as Portable Common Loops (PCL)) and Python compiler code as well. But we are more interested in functional differences, so we have selected the SBCL subsystems as shown on that figure.

Before concentrating on Python, let us say few words about each subsystem. We will not try to give the full definitions, it will be enough for us to know the main responsibility of the each part of SBCL system:

- Runtime application is intended to handle memory allocation, garbage collection, OS interrupts, OS-dependent multithreading stuff and OS-dependent I/O. It loads the Lisp image upon SBCL startup and serves the necessary OS requests.

- Lisp Image (Core) contains all the compiled code of Common Lisp implementation. All standard CL functions and some SBCL-specific extensions are saved in this image. This core also contains runtime Lisp data which allows to restore the saved SBCL system state after the core file is loaded.

- CLOS code is also a part of Lisp image. We separated it because it has a somewhat specific purpose – it is intended to extend Common Lisp with powerful object-oriented programming (metaprogramming!) possibilities. CLOS implementation in SBCL and the runtime application are out of this book scope.

- Python may be considered to be a heart of SBCL system. It compiles Lisp forms, as you see them in REPL or Lisp source files, into a machine code suitable for actual execution on a particular CPU architecture. A compiler code is also present in Lisp image, that compiler code is generated by a cross-compiler during SBCL build. There is an excellent article about this on SBCL Internals Wiki, and we recommend you to look there in case you are interested in SBCL build process. At this point you should understand that all code in the Lisp image file was produced by Python.

So, the main thing to remember after you have read the paragraph is that SBCL system and SBCL compiler (Python) are not the same thing. Do not confuse them. We are also sure that you will never confuse SBCL compiler and the famous and popular Python programming language :) Sorry for falling into such obvious cautions, but it will be sad in case such misunderstanding happens.

Intro. Why this blog was launched

2010-04-16T11:13:00.001-07:00

As you may guess from the blog title, it is dedicated to Common Lisp compilers. During my attempts to fix several bugs in SBCL I understood that it would be good to have some SBCL Compiler (Python) internals manual first. It happened that there are only three or fours papers about the subject at this time, and they are not very detailed. Since I have some experience with other compilers internals, I thought that it would be good to try writing such a manual myself.

Maybe it sounds crazy:), especially because I cannot say that I am a Lisp guru. Yes, I have been using Common Lisp on my daily job for almost three years, and yes, I participate in the development of industrial-level compilers on that job. Is that enough to think that it is a time to write my own book? Probably not... But anyway I have started this manual, because I need it at least for my own SBCL hacking goals. In case somebody else finds it to be useful, I will be happy.

This blog will hold chapters from the book. In case you find some grammar/logical/fundamental mistakes in these chapters, I will appreciate notes and comments about them.

Also I will probably post other Lisp-related things here, in case I consider them to be interesting.

The last thing to mention: I am not a native English speaker, so I apologise for any grammar mistakes you may see in my posts:)