Next: , Previous: , Up: Top   [Contents]


4 The Implicit Continuation Representation

The set of special forms recognized is exactly that specified in the Common Lisp manual. Everything that is described as a macro in CLTL 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.

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. This control and value flow is indicated in the node primarily by pointing to continuations.

The continuation structure represents information sufficiently related to the normal notion of a continuation that naming it so seems sensible. Basically, a continuation represents a place in the code, or alternatively the destination of an expression result and a transfer of control. These two notions are bound together for the same reasons that they are related in the standard functional continuation interpretation.

A continuation may be deprived of either or both of its value or control significance. If the value of a continuation is unused due to evaluation for effect, then the continuation will have a null dest. If the next node for a continuation is deleted by some optimization, then next will be :none.

[### Continuation kinds...]

The block structure represents a basic block, in the the normal sense. Control transfers other than simple sequencing are represented by information in the block structure. The continuation for the last node in a block represents only the destination for the result.

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 section 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.


Next: , Previous: , Up: Top   [Contents]