SBCL Internals : IR1

SBCL Internals
The pages on this CLiki-driven site can be edited by anybody at any time. No warranty of any kind can therefore be made; any implied warranties of merchantability or fitness for a particular purpose are expressly disclaimed

[ Home ]

[ Recent Changes ]

[ About CLiki ]

[ Text Formatting ]

[aside by WHN: The data representation of IR1 was set up before OO design was commonplace and before CLOS was part of the standard, and it shows it. On the other hand, a lot of things in it show good taste and anticipate OO design. On the third hand, a lot of things are done by mutating data structures which could be done much more cleanly by other methods, often simply by initializing something completely at constructor time. So the system could really benefit from some refactoring to take advantage of more modern design ideas (OO, invariants..) and the existence of CLOS. However, since we can't use CLOS to implement the target compiler until we restructure the system so that CLOS is built by the cross-compiler (to dodge the bootstrap problem of trying to build CLOS using the target compiler which is defined in terms of CLOS..) most of those refactorings, even the obvious ones, can't be done as of sbcl-0.pre7.x.]

IR1 is the Implicit Continuation Representation, as used in the Compiler Frontend (and quite a lot of the compiler middle, too). The information below came directly from the CMUCL internals document and was slightly edit for SBCL changes so may be untrue

The set of special operators recognized is exactly that specified in the Common Lisp manual. Everything that is described as a macro in CLtS is a macro.

Large amounts of syntactic information are thrown away by the conversion to an anonymous flow graph representation. The elimination of names eliminates the need to represent most environment manipulation special forms. The explicit representation of control eliminates the need to represent BLOCK and GO, and makes flow analysis easy. The full Common Lisp LAMBDA is implemented with a simple fixed-arg lambda, which greatly simplifies later code.

The elimination of syntactic information eliminates the need for most of the "beta transformation" optimizations in Rabbit. There are no progns, no tagbodys and no returns. There are no "close parens" which get in the way of determining which node receives a given value.

In ICR, computation is represented by Nodes. These are the node types:

[if] Represents all conditionals.
[set] Represents a setq.
[ref] Represents a constant or variable reference.
[cast] Represents type assertions.
[combination] Represents a normal function call.
[MV-combination] Represents a multiple-value-call. This is used to implement all multiple value receiving forms except for multiple-value-prog1, which is implicit.
[bind] This represents the allocation and initialization of the variables in a lambda.
[return] This collects the return value from a lambda and represents the control transfer on return.
[entry] Marks the start of a dynamic extent that can have non-local exits to it. Dynamic state can be saved at this point for restoration on re-entry.
[exit] Marks a potentially non-local exit. This node is interposed between the non-local uses of a continuation and the dest so that code to do a non-local exit can be inserted if necessary.

Some slots are shared between all node types (via defstruct inheritance.) This information held in common between all nodes often makes it possible to avoid special-casing nodes on the basis of type. This shared information is primarily concerned with the order of evaluation and destinations and properties of results.

The block structure represents a basic block, in the almost normal sense (see JOIN-SUCCESSOR-IF-POSSIBLE for details). Control transfers inside a block are represented with CTRAN?s; between blocks - with BLOCK-SUCC/BLOCK-PRED. Last node in a block does not has CTRAN.

Value transfers are represented with LVAR?s. LVAR has a dest consuming values and set of uses, generating them. When dest is deleted, we delete LVAR too.

In some situations (mostly in IR1 conversion and in NLX?es) a pair (CTRAN, LVAR) behaves like a continuation?.

It is very difficult to reconstruct anything resembling the original source from ICR, so we record the original source form in each node. The location of the source form within the input is also recorded, allowing for interfaces such as "Edit Compiler Warnings". See source-paths?.

Forms such as special-bind and catch need to have cleanup code executed at all exit points from the form. We represent this constraint in ICR by annotating the code syntactically within the form with a Cleanup structure describing what needs to be cleaned up. Environment analysis determines the cleanup locations by watching for a change in the cleanup between two continuations. We can't emit cleanup code during ICR conversion, since we don't know which exits will be local until after ICR optimizations are done.

Special binding is represented by a call to the funny function %Special-Bind. The first argument is the Global-Var structure for the variable bound and the second argument is the value to bind it to.

Some subprimitives are implemented using a macro-like mechanism for translating %PRIMITIVE forms into arbitrary lisp code. Subprimitives special-cased by VMR conversion are represented by a call to the funny function %%Primitive. The corresponding Template structure is passed as the first argument.

We check global function calls for syntactic legality with respect to any defined function type function. If the call is illegal or we are unable to tell if it is legal due to non-constant keywords, then we give a warning and mark the function reference as :NOTINLINE to force a full call and cause subsequent phases to ignore the call. If the call is legal and is to a known function, then we annotate the Combination node with the Function-Info structure that contains the compiler information for the function.

This page is linked from: Compiler Declarations are Assertions Frontend ICR index IR2 Vectorizing VOP

CLiki pages can be edited by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively