1.1 Source Tree Structure

The CMUCL source tree has subdirectories for each major subsystem:

assembly/

Holds the CMU CL source-file assembler, and has machine specific subdirectories holding assembly code for that architecture.

clx/

The CLX interface to the X11 window system.

code/

The Lisp code for the runtime system and standard CL utilities.

compiler/

The Python compiler. Has architecture-specific subdirectories which hold backends for different machines. The generic subdirectory holds code that is shared across most backends.

hemlock/

The Hemlock editor.

lisp/

The C runtime system code and low-level Lisp debugger.

pcl/

CMUCL version of the PCL implementation of CLOS.

tools/

System building command files and source management tools.

1.2 Package structure

Goals: with the single exception of LISP, we want to be able to export from the package that the code lives in.

Mach, CLX...

— These Implementation-dependent system-interface packages provide direct access to specific features available in the operating system environment, but hide details of how OS communication is done.

system

contains code that must know about the operating system environment: I/O, etc. Hides the operating system environment. Provides OS interface extensions such as print-directory, etc.

kernel

hides state and types used for system integration: package system, error system, streams (?), reader, printer. Also, hides the VM, in that we don’t export anything that reveals the VM interface. Contains code that needs to use the VM and SYSTEM interface, but is independent of OS and VM details. This code shouldn’t need to be changed in any port of CMU CL, but won’t work when plopped into an arbitrary CL. Uses SYSTEM, VM, EXTENSIONS. We export "hidden" symbols related to implementation of CL: setf-inverses, possibly some global variables.

The boundary between KERNEL and VM is fuzzy, but this fuzziness reflects the fuzziness in the definition of the VM. We can make the VM large, and bring everything inside, or we can make it small. Obviously, we want the VM to be as small as possible, subject to efficiency constraints. Pretty much all of the code in KERNEL could be put in VM. The issue is more what VM hides from KERNEL: VM knows about everything.

lisp

Originally, this package had all the system code in it. The current ideal is that this package should have no code in it, and only exist to export the standard interface. Note that the name has been changed by x3j13 to common-lisp.

extensions

contains code that any random user could have written: list operations, syntactic sugar macros. Uses only LISP, so code in EXTENSIONS is pure CL. Exports everything defined within that is useful elsewhere. This package doesn’t hide much, so it is relatively safe for users to use EXTENSIONS, since they aren’t getting anything they couldn’t have written themselves. Contrast this to KERNEL, which exports additional operations on CL’s primitive data structures: PACKAGE-INTERNAL-SYMBOL-COUNT, etc. Although some of the functionality exported from KERNEL could have been defined in CL, the kernel implementation is much more efficient because it knows about implementation internals. Currently this package contains only extensions to CL, but in the ideal scheme of things, it should contain the implementations of all CL functions that are in KERNEL (the library.)

VM

hides information about the hardware and data structure representations. Contains all code that knows about this sort of thing: parts of the compiler, GC, etc. The bulk of the code is the compiler back-end. Exports useful things that are meaningful across all implementations, such as operations for examining compiled functions, system constants. Uses COMPILER and whatever else it wants. Actually, there are different machine-VM packages for each target implementation. VM is a nickname for whatever implementation we are currently targeting for.

compiler

hides the algorithms used to map Lisp semantics onto the operations supplied by the VM. Exports the mechanisms used for defining the VM. All the VM-independent code in the compiler, partially hiding the compiler intermediate representations. Uses KERNEL.

eval

holds code that does direct execution of the compiler’s ICR. Uses KERNEL, COMPILER. Exports debugger interface to interpreted code.

debug-internals

presents a reasonable, unified interface to manipulation of the state of both compiled and interpreted code. (could be in KERNEL) Uses VM, INTERPRETER, EVAL, KERNEL.

debug

holds the standard debugger, and exports the debugger

2.1 Compiling the C Startup Code

There is a circular dependancy between lisp/internals.h and lisp/lisp.map that causes bootstrapping problems. The easiest way to get around this problem is to make a fake lisp.nm file that has nothing in it but a version number:

        % echo "Map file for lisp version 0" > lisp.nm

and then run genesis with NIL for the list of files:

        * (load ".../compiler/generic/new-genesis") ; compile before loading
        * (lisp::genesis nil ".../lisp/lisp.nm" "/dev/null"
                ".../lisp/lisp.map" ".../lisp/lisp.h")

It will generate a whole bunch of warnings about things being undefined, but ignore that, because it will also generate a correct lisp.h. You can then compile lisp producing a correct lisp.map:

        % make

and then use tools/do-worldbuild and tools/mk-lisp to build kernel.core and lisp.core (see section building-cores.)

2.2 Compiling the Lisp Code

The tools directory contains various lisp and C-shell utilities for building CMU CL:

compile-all*

Will compile lisp files and build a kernel core. It has numerous command-line options to control what to compile and how. Try -help to see a description. It runs a separate Lisp process to compile each subsystem. Error output is generated in files with “.log” extension in the root of the build area.

setup.lisp

Some lisp utilities used for compiling changed files in batch mode and collecting the error output. Sort of a crude defsystem. Loads into the “user” package. See with-compiler-log-file and comf.

foocom.lisp

Each system has a “.lisp” file in tools/ which compiles that system.

2.3 Building Core Images

Both the kernel and final core build are normally done using shell script drivers:

do-worldbuild*

Builds a kernel core for the current machine. The version to build is indicated by an optional argument, which defaults to “alpha”. The kernel.core file is written either in the lisp/ directory in the build area, or in /usr/tmp/. The directory which already contains kernel.core is chosen. You can create a dummy version with e.g. “touch” to select the initial build location.

mk-lisp*

Builds a full core, with conditional loading of subsystems. The version is the first argument, which defaults to “alpha”. Any additional arguments are added to the *features* list, which controls system loading (among other things.) The lisp.core file is written in the current working directory.

These scripts load Lisp command files. When tools/worldbuild.lisp is loaded, it calls genesis with the correct arguments to build a kernel core. Similarly, worldload.lisp builds a full core. Adding certain symbols to *features* before loading worldload.lisp suppresses loading of different parts of the system. These symbols are:

:no-compiler

don’t load the compiler.

:no-clx

don’t load CLX.

:no-clm

don’t load CLM.

:no-hemlock

don’t load Hemlock.

:no-pcl

don’t load PCL.

:runtime

build a runtime code, implies all of the above, and then some.

Note: if you don’t load the compiler, you can’t (successfully) load the pretty-printer or pcl. And if you compiled hemlock with CLX loaded, you can’t load it without CLX also being loaded.

These features are only used during the worldload process; they are not propagated to the generated lisp.core file.

4.1 Tail sets

#| Probably want to have a GTN-like function result equivalence class mechanism for ICR type inference. This would be like the return value propagation being done by Propagate-From-Calls, but more powerful, less hackish, and known to terminate. The ICR equivalence classes could probably be used by GTN, as well.

What we do is have local call analysis eagerly maintain the equivalence classes of functions that return the same way by annotating functions with a Tail-Info structure shared between all functions whose value could be the value of this function. We don’t require that the calls actually be tail-recursive, only that the call deliver its value to the result continuation. [### Actually now done by ICR-OPTIMIZE-RETURN, which is currently making ICR optimize mandatory.]

We can then use the Tail-Set during ICR type inference. It would have a type that is the union across all equivalent functions of the types of all the uses other than in local calls. This type would be recomputed during optimization of return nodes. When the type changes, we would propagate it to all calls to any of the equivalent functions. How do we know when and how to recompute the type for a tail-set? Recomputation is driven by type propagation on the result continuation.

This is really special-casing of RETURN nodes. The return node has the type which is the union of all the non-call uses of the result. The tail-set is found though the lambda. We can then recompute the overall union by taking the union of the type per return node, rather than per-use.

How do result type assertions work? We can’t intersect the assertions across all functions in the equivalence class, since some of the call combinations may not happen (or even be possible). We can intersect the assertion of the result with the derived types for non-call uses.

When we do a tail call, we obviously can’t check that the returned value matches our assertion. Although in principle, we would like to be able to check all assertions, to preserve system integrity, we only need to check assertions that we depend on. We can afford to lose some assertion information as long as we entirely lose it, ignoring it for type inference as well as for type checking.

Things will work out, since the caller will see the tail-info type as the derived type for the call, and will emit a type check if it needs a stronger result.

A remaining question is whether we should intersect the assertion with per-RETURN derived types from the very beginning (i.e. before the type check pass). I think the answer is yes. We delay the type check pass so that we can get our best guess for the derived type before we decide whether a check is necessary. But with the function return type, we aren’t committing to doing any type check when we intersect with the type assertion; the need to type check is still determined in the type check pass by examination of the result continuation.

What is the relationship between the per-RETURN types and the types in the result continuation? The assertion is exactly the Continuation-Asserted-Type (note that the asserted type of result continuations will never change after ICR conversion). The per-RETURN derived type is different than the Continuation-Derived-Type, since it is intersected with the asserted type even before Type Check runs. Ignoring the Continuation-Derived-Type probably makes life simpler anyway, since this breaks the potential circularity of the Tail-Info-Type will affecting the Continuation-Derived-Type, which affects...

When a given return has no non-call uses, we represent this by using *empty-type*. This is consistent with the interpretation that a return type of NIL means the function can’t return.

4.2 Hairy function representation

Non-fixed-arg functions are represented using Optional-Dispatch. An Optional-Dispatch has an entry-point function for each legal number of optionals, and one for when extra args are present. Each entry point function is a simple lambda. The entry point function for an optional is passed the arguments which were actually supplied; the entry point function is expected to default any remaining parameters and evaluate the actual function body.

If no supplied-p arg is present, then we can do this fairly easily by having each entry point supply its default and call the next entry point, with the last entry point containing the body. If there are supplied-p args, then entry point function is replaced with a function that calls the original entry function with T’s inserted at the position of all the supplied args with supplied-p parameters.

We want to be a bit clever about how we handle arguments declared special when doing optional defaulting, or we will emit really gross code for special optionals. If we bound the arg specially over the entire entry-point function, then the entry point function would be caused to be non-tail-recursive. What we can do is only bind the variable specially around the evaluation of the default, and then read the special and store the final value of the special into a lexical variable which we then pass as the argument. In the common case where the default is a constant, we don’t have to special-bind at all, since the computation of the default is not affected by and cannot affect any special bindings.

Keyword and rest args are both implemented using a LEXPR-like “more args” convention. The More-Entry takes two arguments in addition to the fixed and optional arguments: the argument context and count. (ARG <context> <n>) accesses the N’th additional argument. Keyword args are implemented directly using this mechanism. Rest args are created by calling %Listify-Rest-Args with the context and count.

The More-Entry parses the keyword arguments and passes the values to the main function as positional arguments. If a keyword default is not constant, then we pass a supplied-p parameter into the main entry and let it worry about defaulting the argument. Since the main entry accepts keywords in parsed form, we can parse keywords at compile time for calls to known functions. We keep around the original parsed lambda-list and related information so that people can figure out how to call the main entry.

4.3 ICR representation of non-local exits

All exits are initially represented by EXIT nodes: How about an Exit node:

    (defstruct (exit (:include node))
      value)

The Exit node uses the continuation that is to receive the thrown Value. During optimization, if we discover that the Cont’s home-lambda is the same as the exit node’s, then we can delete the Exit node, substituting the Cont for all of the Value’s uses.

The successor block of an EXIT is the entry block in the entered environment. So we use the Exit node to mark the place where exit code is inserted. During environment analysis, we need only insert a single block containing the entry point stub.

We ensure that all Exits that aren’t for a NLX don’t have any Value, so that local exits never require any value massaging.

The Entry node marks the beginning of a block or tagbody:

    (defstruct (entry (:include node))
      (continuations nil :type list)) 

It contains a list of all the continuations that the body could exit to. The Entry node is used as a marker for the place to snapshot state, including the control stack pointer. Each lambda has a list of its Entries so that environment analysis can figure out which continuations are really being closed over. There is no reason for optimization to delete Entry nodes, since they are harmless in the degenerate case: we just emit no code (like a no-var let).

We represent CATCH using the lexical exit mechanism. We do a transformation like this:

   (catch 'foo xxx)  ==>
   (block #:foo
     (%catch #'(lambda () (return-from #:foo (%unknown-values))) 'foo)
     (%within-cleanup :catch
       xxx))

%CATCH just sets up the catch frame which points to the exit function. %Catch is an ordinary function as far as ICR is concerned. The fact that the catcher needs to be cleaned up is expressed by the Cleanup slots in the continuations in the body. %UNKNOWN-VALUES is a dummy function call which represents the fact that we don’t know what values will be thrown.

%WITHIN-CLEANUP is a special special form that instantiates its first argument as the current cleanup when converting the body. In reality, the lambda is also created by the special special form %ESCAPE-FUNCTION, which gives the lambda a special :ESCAPE kind so that the back end knows not to generate any code for it.

We use a similar hack in Unwind-Protect to represent the fact that the cleanup forms can be invoked at arbitrarily random times.

    (unwind-protect p c)  ==>
    (flet ((#:cleanup () c))
      (block #:return
	(multiple-value-bind
	    (#:next #:start #:count)
	    (block #:unwind
              (%unwind-protect #'(lambda (x) (return-from #:unwind x)))
              (%within-cleanup :unwind-protect
		(return-from #:return p)))
	  (#:cleanup)
          (%continue-unwind #:next #:start #:count))))

We use the block #:unwind to represent the entry to cleanup code in the case where we are non-locally unwound. Calling of the cleanup function in the drop-through case (or any local exit) is handled by cleanup generation. We make the cleanup a function so that cleanup generation can add calls at local exits from the protected form. #:next, #:start and #:count are state used in the case where we are unwound. They indicate where to go after doing the cleanup and what values are being thrown. The cleanup encloses only the protected form. As in CATCH, the escape function is specially tagged as :ESCAPE. The cleanup function is tagged as :CLEANUP to inhibit let conversion (since references are added in environment analysis.)

Notice that implementing these forms using closures over continuations eliminates any need to special-case ICR flow analysis. Obviously we don’t really want to make heap-closures here. In reality these functions are special-cased by the back-end according to their KIND.

4.4 Block compilation

One of the properties of ICR is that it supports “block compilation” by allowing arbitrarily large amounts of code to be converted at once, with actual compilation of the code being done at will.

In order to preserve the normal semantics we must recognize that proclamations (possibly implicit) are scoped. A proclamation is in effect only from the time of appearance of the proclamation to the time it is contradicted. The current global environment at the end of a block is not necessarily the correct global environment for compilation of all the code within the block. We solve this problem by closing over the relevant information in the ICR at the time it is converted. For example, each functional variable reference is marked as inline, notinline or don’t care. Similarly, each node contains a structure known as a Cookie which contains the appropriate settings of the compiler policy switches.

We actually convert each form in the file separately, creating a separate “initial component” for each one. Later on, these components are merged as needed. The main reason for doing this is to cause EVAL-WHEN processing to be interleaved with reading.

4.5 Entry points

#|

Since we need to evaluate potentially arbitrary code in the XEP argument forms (for type checking), we can’t leave the arguments in the wired passing locations. Instead, it seems better to give the XEP max-args fixed arguments, with the passing locations being the true passing locations. Instead of using %XEP-ARG, we reference the appropriate variable.

Also, it might be a good idea to do argument count checking and dispatching with explicit conditional code in the XEP. This would simplify both the code that creates the XEP and the VMR conversion of XEPs. Also, argument count dispatching would automatically benefit from any cleverness in compilation of case-like forms (jump tables, etc). On the downside, this would push some assumptions about how arg dispatching is done into ICR. But then we are currently violating abstraction at least as badly in VMR conversion, which is also supposed to be implementation independent. |#

As a side-effect of finding which references to known functions can be converted to local calls, we find any references that cannot be converted. References that cannot be converted to a local call must evaluate to a “function object” (or function-entry) that can be called using the full call convention. A function that can be called from outside the component is called an “entry-point”.

Lots of stuff that happens at compile-time with local function calls must be done at run-time when an entry-point is called.

It is desirable for optimization and other purposes if all the calls to every function were directly present in ICR as local calls. We cannot directly do this with entry-point functions, since we don’t know where and how the entry-point will be called until run-time.

What we do is represent all the calls possible from outside the component by local calls within the component. For each entry-point function, we create a corresponding lambda called the external entry point or XEP. This is a function which takes the number of arguments passed as the first argument, followed by arguments corresponding to each required or optional argument.

If an optional argument is unsupplied, the value passed into the XEP is undefined. The XEP is responsible for doing argument count checking and dispatching.

In the case of a fixed-arg lambda, we emit a call to the %VERIFY-ARGUMENT-COUNT funny function (conditional on policy), then call the real function on the passed arguments. Even in this simple case, we benefit several ways from having a separate XEP:

• The argument count checking is factored out, and only needs to be done in full calls.
• Argument type checking happens automatically as a consequence of passing the XEP arguments in a local call to the real function. This type checking is also only done in full calls.
• The real function may use a non-standard calling convention for the benefit of recursive or block-compiled calls. The XEP converts arguments/return values to/from the standard convention. This also requires little special-casing of XEPs.

If the function has variable argument count (represented by an OPTIONAL-DISPATCH), then the XEP contains a COND which dispatches off of the argument count, calling the appropriate entry-point function (which then does defaulting). If there is a more entry (for keyword or rest args), then the XEP obtains the more arg context and count by calling the %MORE-ARG-CONTEXT funny function.

All non-local-call references to functions are replaced with references to the corresponding XEP. ICR optimization may discover a local call that was previously a non-local reference. When we delete the reference to the XEP, we may find that it has no references. In this case, we can delete the XEP, causing the function to no longer be an entry-point.

5.1 Canonical forms

#|

Would be useful to have a Freeze-Type proclamation. Its primary use would be to say that the indicated type won’t acquire any new subtypes in the future. This allows better open-coding of structure type predicates, since the possible types that would satisfy the predicate will be constant at compile time, and thus can be compiled as a skip-chain of EQ tests.

Of course, this is only a big win when the subtypes are few: the most important case is when there are none. If the closure of the subtypes is much larger than the average number of supertypes of an inferior, then it is better to grab the list of superiors out of the object’s type, and test for membership in that list.

Should type-specific numeric equality be done by EQL rather than =? i.e. should = on two fixnums become EQL and then convert to EQL/FIXNUM? Currently we transform EQL into =, which is complicated, since we have to prove the operands are the class of numeric type before we do it. Also, when EQL sees one operand is a FIXNUM, it transforms to EQ, but the generator for EQ isn’t expecting numbers, so it doesn’t use an immediate compare.

• Array hackery

     (or (simple-string-p x)
	 (and (complex-array-p x)
	      (= (array-rank x) 1)
	      (simple-string-p (%array-data x))))  

    (aref x y)
==>
    (let ((#:len (array-dimension x 0)))
      (%unchecked-aref x (%check-in-bounds y #:len)))  

Endp  ==>  (NULL (THE LIST ...))
(NOT xxx) or (NULL xxx) => (IF xxx NIL T)

(typep x '<simple type>) => (<simple predicate> x)
(typep x '<complex type>) => ...composition of simpler operations...

    (apply #'foo a b c)
==>
    (multiple-value-call #'foo (values a) (values b) (values-list c))

Make-String => Make-Array
N-arg predicates associated into two-arg versions.
Associate N-arg arithmetic ops.
Expand CxxxR and FIRST...nTH
Zerop, Plusp, Minusp, 1+, 1-, Min, Max, Rem, Mod
(Values x), (Identity x) => (Prog1 x)

All specialized aref functions => (aref (the xxx) ...)

5.2 Inline functions

[### Inline expansion is especially powerful in the presence of good lisp-level optimization (“partial evaluation”). Many “optimizations” usually done in Lisp compilers by special-case source-to-source transforms can be had simply by making the source of the general case function available for inline expansion. This is especially helpful in Common Lisp, which has many commonly used functions with simple special cases but bad general cases (list and sequence functions, for example.)

Inline expansion of recursive functions is allowed, and is not as silly as it sounds. When expanded in a specific context, much of the overhead of the recursive calls may be eliminated (especially if there are many keyword arguments, etc.)

[Also have MAYBE-INLINE] ]

We only record a function’s inline expansion in the global environment when the function is in the null lexical environment, since the expansion must be represented as source.

We do inline expansion of functions locally defined by FLET or LABELS even when the environment is not null. Since the appearances of the local function must be nested within the desired environment, it is possible to expand local functions inline even when they use the environment. We just stash the source form and environments in the Functional for the local function. When we convert a call to it, we just reconvert the source in the saved environment.

An interesting alternative to the inline/full-call dichotomy is “semi-inline” coding. Whenever we have an inline expansion for a function, we can expand it only once per block compilation, and then use local call to call this copied version. This should get most of the speed advantage of real inline coding with much less code bloat. This is especially attractive for simple system functions such as Read-Char.

The main place where true inline expansion would still be worth doing is where large amounts of the function could be optimized away by constant folding or other optimizations that depend on the exact arguments to the call.

5.3 Compilation policy

We want more sophisticated control of compilation safety than is offered in CL, so that we can emit only those type checks that are likely to discover something (i.e. external interfaces.)

5.4 Notes

Generalized back-end notion provides dynamic retargeting? (for byte code)

The current node type annotations seem to be somewhat unsatisfactory, since we lose information when we do a THE on a continuation that already has uses, or when we convert a let where the actual result continuation has other uses.

But the case with THE isn’t really all that bad, since the test of whether there are any uses happens before conversion of the argument, thus THE loses information only when there are uses outside of the declared form. The LET case may not be a big deal either.

Note also that losing user assertions isn’t really all that bad, since it won’t damage system integrity. At worst, it will cause a bug to go undetected. More likely, it will just cause the error to be signaled in a different place (and possibly in a less informative way). Of course, there is an efficiency hit for losing type information, but if it only happens in strange cases, then this isn’t a big deal.

8.1 Goals for ICR optimizations

#|

When an optimization is disabled, code should still be correct and not ridiculously inefficient. Phases shouldn’t be made mandatory when they have lots of non-required stuff jammed into them.

|#

This pass is optional, but is desirable if anything is more important than compilation speed.

This phase is a grab-bag of optimizations that concern themselves with the flow of values through the code representation. The main things done are type inference, constant folding and dead expression elimination. This phase can be understood as a walk of the expression tree that propagates assertions down the tree and propagates derived information up the tree. The main complication is that there isn’t any expression tree, since ICR is flow-graph based.

We repeat this pass until we don’t discover anything new. This is a bit of feat, since we dispatch to arbitrary functions which may do arbitrary things, making it hard to tell if anything really happened. Even if we solve this problem by requiring people to flag when they changed or by checking to see if they changed something, there are serious efficiency problems due to massive redundant computation, since in many cases the only way to tell if anything changed is to recompute the value and see if it is different from the old one.

We solve this problem by requiring that optimizations for a node only depend on the properties of the CONT and the continuations that have the node as their DEST. If the continuations haven’t changed since the last pass, then we don’t attempt to re-optimize the node, since we know nothing interesting will happen.

We keep track of which continuations have changed by a REOPTIMIZE flag that is set whenever something about the continuation’s value changes.

When doing the bottom up pass, we dispatch to type specific code that knows how to tell when a node needs to be reoptimized and does the optimization. These node types are special-cased: COMBINATION, IF, RETURN, EXIT, SET.

The REOPTIMIZE flag in the COMBINATION-FUN is used to detect when the function information might have changed, so that we know when there are new assertions that could be propagated from the function type to the arguments.

When we discover something about a leaf, or substitute for leaf, we reoptimize the CONT for all the REF and SET nodes.

We have flags in each block that indicate when any nodes or continuations in the block need to be re-optimized, so we don’t have to scan blocks where there is no chance of anything happening.

It is important for efficiency purposes that optimizers never say that they did something when they didn’t, but this by itself doesn’t guarantee timely termination. I believe that with the type system implemented, type inference will converge in finite time, but as a practical matter, it can take far too long to discover not much. For this reason, ICR optimization is terminated after three consecutive passes that don’t add or delete code. This premature termination only happens 2% of the time.

8.2 Flow graph simplification

Things done:

• Delete blocks with no predecessors.
• Merge blocks that can be merged.
• Convert local calls to Let calls.
• Eliminate degenerate IFs.

We take care not to merge blocks that are in different functions or have different cleanups. This guarantees that non-local exits are always at block ends and that cleanup code never needs to be inserted within a block.

We eliminate IFs with identical consequent and alternative. This would most likely happen if both the consequent and alternative were optimized away.

[Could also be done if the consequent and alternative were different blocks, but computed the same value. This could be done by a sort of cross-jumping optimization that looked at the predecessors for a block and merged code shared between predecessors. IFs with identical branches would eventually be left with nothing in their branches.]

We eliminate IF-IF constructs:

    (IF (IF A B C) D E) ==>
    (IF A (IF B D E) (IF C D E))

In reality, what we do is replicate blocks containing only an IF node where the predicate continuation is the block start. We make one copy of the IF node for each use, leaving the consequent and alternative the same. If you look at the flow graph representation, you will see that this is really the same thing as the above source to source transformation.

8.3 Forward ICR optimizations

In the forward pass, we scan the code in forward depth-first order. We examine each call to a known function, and:

• Eliminate any bindings for unused variables.
• Do top-down type assertion propagation. In local calls, we propagate asserted and derived types between the call and the called lambda.
• Replace calls of foldable functions with constant arguments with the result. We don’t have to actually delete the call node, since Top-Down optimize will delete it now that its value is unused.
• Run any Optimizer for the current function. The optimizer does arbitrary transformations by hacking directly on the IR. This is useful primarily for arithmetic simplification and similar things that may need to examine and modify calls other than the current call. The optimizer is responsible for recording any changes that it makes. An optimizer can inhibit further optimization of the node during the current pass by returning true. This is useful when deleting the node.
• Do ICR transformations, replacing a global function call with equivalent inline lisp code.
• Do bottom-up type propagation/inferencing. For some functions such as Coerce we will dispatch to a function to find the result type. The Derive-Type function just returns a type structure, and we check if it is different from the old type in order to see if there was a change.
• Eliminate IFs with predicates known to be true or false.
• Substitute the value for unset let variables that are bound to constants, unset lambda variables or functionals.
• Propagate types from local call args to var refs.

We use type info from the function continuation to find result types for functions that don’t have a derive-type method.

• ICR transformation

8.4 Backward ICR optimizations

In the backward pass, we scan each block in reverse order, and eliminate any effectless nodes with unused values. In ICR this is the only way that code is deleted other than the elimination of unreachable blocks.

17.1 VMR Control representation

We represent all control transfer explicitly. In particular, :Conditional VOPs take a single Target continuation and a Not-P flag indicating whether the sense of the test is negated. Then an unconditional Branch VOP will be emitted afterward if the other path isn’t a drop-through.

So we linearize the code before VMR-conversion. This isn’t a problem, since there isn’t much change in control flow after VMR conversion (none until loop optimization requires introduction of header blocks.) It does make cost-based branch prediction a bit ucky, though, since we don’t have any cost information in ICR. Actually, I guess we do have pretty good cost information after LTN even before VMR conversion, since the most important thing to know is which functions are open-coded.

|#

VMR preserves the block structure of ICR, but replaces the nodes with a target dependent virtual machine (VM) representation. Different implementations may use different VMs without making major changes in the back end. The two main components of VMR are Temporary Names (TNs) and Virtual OPerations (VOPs). TNs represent the locations that hold values, and VOPs represent the operations performed on the values.

A “primitive type” is a type meaningful at the VM level. Examples are Fixnum, String-Char, Short-Float. During VMR conversion we use the primitive type of an expression to determine both where we can store the result of the expression and which type-specific implementations of an operation can be applied to the value. [Ptype is a set of SCs == representation choices and representation specific operations]

The VM specific definitions provide functions that do stuff like find the primitive type corresponding to a type and test for primitive type subtypep. Usually primitive types will be disjoint except for T, which represents all types.

The primitive type T is special-cased. Not only does it overlap with all the other types, but it implies a descriptor (“boxed” or “pointer”) representation. For efficiency reasons, we sometimes want to use alternate representations for some objects such as numbers. The majority of operations cannot exploit alternate representations, and would only be complicated if they had to be able to convert alternate representations into descriptors. A template can require an operand to be a descriptor by constraining the operand to be of type T.

A TN can only represent a single value, so we bare the implementation of MVs at this point. When we know the number of multiple values being handled, we use multiple TNs to hold them. When the number of values is actually unknown, we use a convention that is compatible with full function call.

Everything that is done is done by a VOP in VMR. Calls to simple primitive functions such as + and CAR are translated to VOP equivalents by a table-driven mechanism. This translation is specified by the particular VM definition; VMR conversion makes no assumptions about which operations are primitive or what operand types are worth special-casing. The default calling mechanisms and other miscellaneous builtin features are implemented using standard VOPs that must be implemented by each VM.

Type information can be forgotten after VMR conversion, since all type-specific operation selections have been made.

Simple type checking is explicitly done using CHECK-xxx VOPs. They act like innocuous effectless/unaffected VOPs which return the checked thing as a result. This allows loop-invariant optimization and common subexpression elimination to remove redundant checks. All type checking is done at the time the continuation is used.

Note that we need only check asserted types, since if type inference works, the derived types will also be satisfied. We can check whichever is more convenient, since both should be true.

Constants are turned into special Constant TNs, which are wired down in a SC that is determined by their type. The VM definition provides a function that returns a constant TN to represent a Constant Leaf.

Each component has a constant pool. There is a register dedicated to holding the constant pool for the current component. The back end allocates non-immediate constants in the constant pool when it discovers them during translation from ICR.

[### Check that we are describing what is actually implemented. But this really isn’t very good in the presence of interesting unboxed representations...] Since LTN only deals with values from the viewpoint of the receiver, we must be prepared during the translation pass to do stuff to the continuation at the time it is used. – If a VOP yields more values than are desired, then we must create TNs to hold the discarded results. An important special-case is continuations whose value is discarded. These continuations won’t be annotated at all. In the case of a Ref, we can simply skip evaluation of the reference when the continuation hasn’t been annotated. Although this will eliminate bogus references that for some reason weren’t optimized away, the real purpose is to handle deferred references. – If a VOP yields fewer values than desired, then we must default the extra values to NIL. – If a continuation has its type-check flag set, then we must check the type of the value before moving it into the result location. In general, this requires computing the result in a temporary, and having the type-check operation deliver it in the actual result location. – If the template’s result type is T, then we must generate a boxed temporary to compute the result in when the continuation’s type isn’t T.

We may also need to do stuff to the arguments when we generate code for a template. If an argument continuation isn’t annotated, then it must be a deferred reference. We use the leaf’s TN instead. We may have to do any of the above use-time actions also. Alternatively, we could avoid hair by not deferring references that must be type-checked or may need to be boxed.

17.2 Stack analysis

Think of this as a lifetime problem: a values generator is a write and a values receiver is a read. We want to annotate each VMR-Block with the unknown-values continuations that are live at that point. If we do a control transfer to a place where fewer continuations are live, then we must deallocate the newly dead continuations.

We want to convince ourselves that values deallocation based on lifetime analysis actually works. In particular, we need to be sure that it doesn’t violate the required stack discipline. It is clear that it is impossible to deallocate the values before they become dead, since later code may decide to use them. So the only thing we need to ensure is that the “right” time isn’t later than the time that the continuation becomes dead.

The only reason why we couldn’t deallocate continuation A as soon as it becomes dead would be that there is another continuation B on top of it that isn’t dead (since we can only deallocate the topmost continuation).

The key to understanding why this can’t happen is that each continuation has only one read (receiver). If B is on top of A, then it must be the case that A is live at the receiver for B. This means that it is impossible for B to be live without A being live.

The reason that we don’t solve this problem using a normal iterative flow analysis is that we also need to know the ordering of the continuations on the stack so that we can do deallocation. When it comes time to discard values, we want to know which discarded continuation is on the bottom so that we can reset SP to its start.

[I suppose we could also decrement SP by the aggregate size of the discarded continuations.] Another advantage of knowing the order in which we expect continuations to be on the stack is that it allows us to do some consistency checking. Also doing a localized graph walk around the values-receiver is likely to be much more efficient than doing an iterative flow analysis problem over all the code in the component (not that big a consideration.)

#| Actually, what we do is a backward graph walk from each unknown-values receiver. As we go, we mark each walked block with the ordered list of continuations we believe are on the stack. Starting with an empty stack, we: – When we encounter another unknown-values receiver, we push that continuation on our simulated stack. – When we encounter a receiver (which had better be for the topmost continuation), we pop that continuation. – When we pop all continuations, we terminate our walk.

[### not quite right... It seems we may run into “dead values” during the graph walk too. It seems that we have to check if the pushed continuation is on stack top, and if not, add it to the ending stack so that the post-pass will discard it.]

[### Also, we can’t terminate our walk just because we hit a block previously walked. We have to compare the End-Stack with the values received along the current path: if we have more values on our current walk than on the walk that last touched the block, then we need to re-walk the subgraph reachable from that block, using our larger set of continuations. It seems that our actual termination condition is reaching a block whose End-Stack is already EQ to our current stack.]

If at the start, the block containing the values receiver has already been walked, we skip the walk for that continuation, since it has already been handled by an enclosing values receiver. Once a walk has started, we ignore any signs of a previous walk, clobbering the old result with our own, since we enclose that continuation, and the previous walk doesn’t take into consideration the fact that our values block underlies its own.

When we are done, we have annotated each block with the stack current both at the beginning and at the end of that block. Blocks that aren’t walked don’t have anything on the stack either place (although they may hack MVs internally).

We then scan all the blocks in the component, looking for blocks that have predecessors with a different ending stack than that block’s starting stack. (The starting stack had better be a tail of the predecessor’s ending stack.) We insert a block intervening between all of these predecessors that sets SP to the end of the values for the continuation that should be on stack top. Of course, this pass needn’t be done if there aren’t any global unknown MVs.

Also, if we find any block that wasn’t reached during the walk, but that USEs an outside unknown-values continuation, then we know that the DEST can’t be reached from this point, so the values are unused. We either insert code to pop the values, or somehow mark the code to prevent the values from ever being pushed. (We could cause the popping to be done by the normal pass if we iterated over the pushes beforehand, assigning a correct END-STACK.)

[### But I think that we have to be a bit clever within blocks, given the possibility of blocks being joined. We could collect some unknown MVs in a block, then do a control transfer out of the receiver, and this control transfer could be squeezed out by merging blocks. How about:

    (tagbody
      (return
       (multiple-value-prog1 (foo)
	 (when bar
	   (go UNWIND))))

     UNWIND
      (return
       (multiple-value-prog1 (baz)
	 bletch)))

But the problem doesn’t happen here (can’t happen in general?) since a node buried within a block can’t use a continuation outside of the block. In fact, no block can have more then one PUSH continuation, and this must always be the last continuation. So it is trivially (structurally) true that all pops come before any push.

[### But not really: the DEST of an embedded continuation may be outside the block. There can be multiple pushes, and we must find them by iterating over the uses of MV receivers in LTN. But it would be hard to get the order right this way. We could easily get the order right if we added the generators as we saw the uses, except that we can’t guarantee that the continuations will be annotated at that point. (Actually, I think we only need the order for consistency checks, but that is probably worthwhile). I guess the thing to do is when we process the receiver, add the generator blocks to the Values-Generators, then do a post-pass that re-scans the blocks adding the pushes.]

I believe that above concern with a dead use getting mashed inside a block can’t happen, since the use inside the block must be the only use, and if the use isn’t reachable from the push, then the use is totally unreachable, and should have been deleted, which would prevent it from ever being annotated. ] ] |#

We find the partial ordering of the values globs for unknown values continuations in each environment. We don’t have to scan the code looking for unknown values continuations since LTN annotates each block with the continuations that were popped and not pushed or pushed and not popped. This is all we need to do the inter-block analysis.

After we have found out what stuff is on the stack at each block boundary, we look for blocks with predecessors that have junk on the stack. For each such block, we introduce a new block containing code to restore the stack pointer. Since unknown-values continuations are represented as <start, count>, we can easily pop a continuation using the Start TN.

Note that there is only doubt about how much stuff is on the control stack, since only it is used for unknown values. Any special stacks such as number stacks will always have a fixed allocation.

17.3 Non-local exit

If the starting and ending continuations are not in the same environment, then the control transfer is a non-local exit. In this case just call Unwind with the appropriate stack pointer, and let the code at the re-entry point worry about fixing things up.

It seems like maybe a good way to organize VMR conversion of NLX would be to have environment analysis insert funny functions in new interposed cleanup blocks. The thing is that we need some way for VMR conversion to: 1] Get its hands on the returned values. 2] Do weird control shit. 3] Deliver the values to the original continuation destination. I.e. we need some way to interpose arbitrary code in the path of value delivery.

What we do is replace the NLX uses of the continuation with another continuation that is received by a MV-Call to %NLX-VALUES in a cleanup block that is interposed between the NLX uses and the old continuation’s block. The MV-Call uses the original continuation to deliver its values to.

[Actually, it’s not really important that this be an MV-Call, since it has to be special-cased by LTN anyway. Or maybe we would want it to be an MV call. If we did normal LTN analysis of an MV call, it would force the returned values into the unknown values convention, which is probably pretty convenient for use in NLX.

Then the entry code would have to use some special VOPs to receive the unknown values. But we probably need special VOPs for NLX entry anyway, and the code can share with the call VOPs. Also we probably need the technology anyway, since THROW will use truly unknown values.]

On entry to a dynamic extent that has non-local-exists into it (always at an ENTRY node), we take a complete snapshot of the dynamic state:

• the top pointers for all stacks
• current Catch and Unwind-Protect
• current special binding (binding stack pointer in shallow binding)

We insert code at the re-entry point which restores the saved dynamic state. All TNs live at an NLX EP are forced onto the stack, so we don’t have to restore them, and we don’t have to worry about getting them saved.

20.1 Flow analysis

It seems we could use the global-conflicts structures during compute the inter-block lifetime information. The pre-pass creates all the global-conflicts for blocks that global TNs are referenced in. The flow analysis pass just adds always-live global-conflicts for the other blocks the TNs are live in. In addition to possibly being more efficient than SSets, this would directly result in the desired global-conflicts information, rather than having to create it from another representation.

The DFO sorted per-TN global-conflicts thread suggests some kind of algorithm based on the manipulation of the sets of blocks each TN is live in (which is what we really want), rather than the set of TNs live in each block.

If we sorted the per-TN global-conflicts in reverse DFO (which is just as good for determining conflicts between TNs), then it seems we could scan though the conflicts simultaneously with our flow-analysis scan through the blocks.

The flow analysis step is the following: If a TN is always-live or read-before-written in a successor block, then we make it always-live in the current block unless there are already global-conflicts recorded for that TN in this block.

The iteration terminates when we don’t add any new global-conflicts during a pass.

We may also want to promote TNs only read within a block to always-live when the TN is live in a successor. This should be easy enough as long as the global-conflicts structure contains this kind of info.

The critical operation here is determining whether a given global TN has global conflicts in a given block. Note that since we scan the blocks in DFO, and the global-conflicts are sorted in DFO, if we give each global TN a pointer to the global-conflicts for the last block we checked the TN was in, then we can guarantee that the global-conflicts we are looking for are always at or after that pointer. If we need to insert a new structure, then the pointer will help us rapidly find the place to do the insertion.]

20.2 Conflict detection

[### Environment, :more TNs.]

This phase makes use of the results of lifetime analysis to find the set of TNs that have lifetimes overlapping with those of each TN. We also annotate call VOPs with information about the live TNs so that code generation knows which registers need to be saved.

The basic action is a backward scan of each block, looking at each TN-Ref and maintaining a set of the currently live TNs. When we see a read, we check if the TN is in the live set. If not, we: – Add the TN to the conflict set for every currently live TN, – Union the set of currently live TNs with the conflict set for the TN, and – Add the TN to the set of live TNs.

When we see a write for a live TN, we just remove it from the live set. If we see a write to a dead TN, then we update the conflicts sets as for a read, but don’t add the TN to the live set. We have to do this so that the bogus write doesn’t clobber anything.

[We don’t consider always-live TNs at all in this process, since the conflict of always-live TNs with other TNs in the block is implicit in the global-conflicts structures.

Before we do the scan on a block, we go through the global-conflicts structures of TNs that change liveness in the block, assigning the recorded LTN number to the TN’s LTN number for the duration of processing of that block.]

Efficiently computing and representing this information calls for some cleverness. It would be prohibitively expensive to represent the full conflict set for every TN with sparse sets, as is done at the block-level. Although it wouldn’t cause non-linear behavior, it would require a complex linked structure containing tens of elements to be created for every TN. Fortunately we can improve on this if we take into account the fact that most TNs are “local” TNs: TNs which have all their uses in one block.

First, many global TNs will be either live or dead for the entire duration of a given block. We can represent the conflict between global TNs live throughout the block and TNs local to the block by storing the set of always-live global TNs in the block. This reduces the number of global TNs that must be represented in the conflicts for local TNs.

Second, we can represent conflicts within a block using bit-vectors. Each TN that changes liveness within a block is assigned a local TN number. Local conflicts are represented using a fixed-size bit-vector of 64 elements or so which has a 1 for the local TN number of every TN live at that time. The block has a simple-vector which maps from local TN numbers to TNs. Fixed-size vectors reduce the hassle of doing allocations and allow operations to be open-coded in a maximally tense fashion.

We can represent the conflicts for a local TN by a single bit-vector indexed by the local TN numbers for that block, but in the global TN case, we need to be able to represent conflicts with arbitrary TNs. We could use a list-like sparse set representation, but then we would have to either special-case global TNs by using the sparse representation within the block, or convert the local conflicts bit-vector to the sparse representation at the block end. Instead, we give each global TN a list of the local conflicts bit-vectors for each block that the TN is live in. If the TN is always-live in a block, then we record that fact instead. This gives us a major reduction in the amount of work we have to do in lifetime analysis at the cost of some increase in the time to iterate over the set during Pack.

Since we build the lists of local conflict vectors a block at a time, the blocks in the lists for each TN will be sorted by the block number. The structure also contains the local TN number for the TN in that block. These features allow pack to efficiently determine whether two arbitrary TNs conflict. You just scan the lists in order, skipping blocks that are in only one list by using the block numbers. When we find a block that both TNs are live in, we just check the local TN number of one TN in the local conflicts vector of the other.

In order to do these optimizations, we must do a pre-pass that finds the always-live TNs and breaks blocks up into small enough pieces so that we don’t run out of local TN numbers. If we can make a block arbitrarily small, then we can guarantee that an arbitrarily small number of TNs change liveness within the block. We must be prepared to make the arguments to unbounded arg count VOPs (such as function call) always-live even when they really aren’t. This is enabled by a panic mode in the block splitter: if we discover that the block only contains one VOP and there are still too many TNs that aren’t always-live, then we promote the arguments (which we’d better be able to do...).

This is done during the pre-scan in lifetime analysis. We can do this because all TNs that change liveness within a block can be found by examining that block: the flow analysis only adds always-live TNs.

When we are doing the conflict detection pass, we set the LTN number of global TNs. We can easily detect global TNs that have not been locally mapped because this slot is initially null for global TNs and we null it out after processing each block. We assign all Always-Live TNs to the same local number so that we don’t need to treat references to them specially when making the scan.

We also annotate call VOPs that do register saving with the TNs that are live during the call, and thus would need to be saved if they are packed in registers.

We adjust the costs for TNs that need to be saved so that TNs costing more to save and restore than to reference get packed on the stack. We would also like more often saved TNs to get higher costs so that they are packed in more savable locations.

25.1 Error Message Utilities

25.2 Source Paths

29.1 Lifetime model

#| Note in doc that the same TN may not be used as both a more operand and as any other operand to the same VOP, to simplify more operand LTN number coalescing. |#

It seems we need a fairly elaborate model for intra-VOP conflicts in order to allocate temporaries without introducing spurious conflicts. Consider the important case of a VOP such as a miscop that must have operands in certain registers. We allocate a wired temporary, create a local preference for the corresponding operand, and move to (or from) the temporary. If all temporaries conflict with all arguments, the result will be correct, but arguments could never be packed in the actual passing register. If temporaries didn’t conflict with any arguments, then the temporary for an earlier argument might get packed in the same location as the operand for a later argument; loading would then destroy an argument before it was read.

A temporary’s intra-VOP lifetime is represented by the times at which its life starts and ends. There are various instants during the evaluation that start and end VOP lifetimes. Two TNs conflict if the live intervals overlap. Lifetimes are open intervals: if one TN’s lifetime begins at a point where another’s ends, then the TNs don’t conflict.

The times within a VOP are the following:

:Load This is the beginning of the argument’s lives, as far as intra-vop conflicts are concerned. If load-TNs are allocated, then this is the beginning of their lives.

(:Argument <n>) The point at which the N’th argument is read for the last time (by this VOP). If the argument is dead after this VOP, then the argument becomes dead at this time, and may be reused as a temporary or result load-TN.

(:Eval <n>) The N’th evaluation step. There may be any number of evaluation steps, but it is unlikely that more than two are needed.

(:Result <n>) The point at which the N’th result is first written into. This is the point at which that result becomes live.

:Save Similar to :Load, but marks the end of time. This is the point at which result load-TNs are stored back to the actual location.

In any of the list-style time specifications, the keyword by itself stands for the first such time, i.e.

    :argument  <==>  (:argument 0)

Note that argument/result read/write times don’t actually have to be in the order specified, but they must *appear* to happen in that order as far as conflict analysis is concerned. For example, the arguments can be read in any order as long as no TN is written that has a life beginning at or after (:Argument <n>), where N is the number of an argument whose reading was postponed.

[### (???)

We probably also want some syntactic sugar in Define-VOP for automatically moving operands to/from explicitly allocated temporaries so that this kind of thing is somewhat easy. There isn’t really any reason to consider the temporary to be a load-TN, but we want to compute costs as though it was and want to use the same operand loading routines.

We also might consider allowing the lifetime of an argument/result to be extended forward/backward. This would in many cases eliminate the need for temporaries when operands are read/written out of order. ]

29.2 VOP Cost model

Note that in this model, if an operand has no restrictions, it has no cost. This makes sense, since the purpose of the cost is to indicate the relative value of packing in different SCs. If the operand isn’t required to be in a good SC (i.e. a register), then we might as well leave it in memory. The SC restriction mechanism can be used even when doing a move into the SC is too complex to be generated automatically (perhaps requiring temporary registers), since Define-VOP allows operand loading to be done explicitly.

29.3 Efficiency notes

In addition to being used to tell whether a particular unsafe template might get emitted, we can also use it to give better efficiency notes: – We can say what is wrong with the call types, rather than just saying we failed to open-code. – We can tell whether any of the “better” templates could possibly apply, i.e. is the inapplicability of a template because of inadequate type information or because the type is just plain wrong. We don’t want to flame people when a template that couldn’t possibly match doesn’t match, e.g. complaining that we can’t use fixnum+ when the arguments are known to be floats.

This is how we give better efficiency notes:

The Template-Note is a short noun-like string without capitalization or punctuation that describes what the template “does”, i.e. we say “Unable to do ~A, doing ~A instead.”

The Cost is moved from the Vop-Info to the Template structure, and is used to determine the “goodness” of possibly applicable templates. [Could flush Template/Vop-Info distinction] The cost is used to choose the best applicable template to emit, and also to determine what better templates we might have been able to use.

A template is possibly applicable if there is an intersection between all of the arg/result types and the corresponding arg/result restrictions, i.e. the template is not clearly impossible: more declarations might allow it to be emitted.

32.1 Function Call

• Registers and frame format
• Full call
• Unknown values return
• External Entry Points

Allocate-Frame
Copy-More-Arg <nargs-tn> 'fixed {in a3} => <context>, <count>
Setup-Environment
Setup-Closure-Environment => <closure>
Verify-Argument-Count <nargs-tn> 'count {for fixed-arg lambdas}
Argument-Count-Error <nargs-tn> {Drop-thru on hairy arg dispatching}
Use fast-if-=/fixnum and fast-if-</fixnum for dispatching.

make-closure <fun entry> <slot count> => <closure>
closure-init <closure> <values> 'slot

32.2 Calls

Calling VOP’s are a cross product of the following sets (with some members missing): Return values multiple (all values) fixed (calling with unknown values conventions, wanting a certain number.) known (only in local call where caller/callee agree on number of values.) tail (doesn’t return but does tail call) What function local named (going through symbol, like full but stash fun name for error sys) full (have a function) Args fixed (number of args are known at compile-time) variable (MULTIPLE-VALUE-CALL and APPLY)

Note on all jumps for calls and returns that we want to put some instruction in the jump’s delay slot(s).

Register usage at the time of the call:

LEXENV This holds the lexical environment to use during the call if it’s a closure, and it is undefined otherwise.

CNAME This holds the symbol for a named call and garbage otherwise.

OCFP This holds the frame pointer, which the system restores upon return. The callee saves this if necessary; this is passed as a pseudo-argument.

A0 ... An These holds the first n+1 arguments.

NARGS This holds the number of arguments, as a fixnum.

LRA This holds the lisp-return-address object which indicates where to return. For a tail call, this retains its current value. The callee saves this if necessary; this is passed as a pseudo-argument.

CODE This holds the function object being called.

CSP The caller ignores this. The callee sets it as necessary based on CFP.

CFP This holds the callee’s frame pointer. Caller sets this to the new frame pointer, which it remembered when it started computing arguments; this is CSP if there were no stack arguments. For a tail call CFP retains its current value.

NSP The system uses this within a single function. A function using NSP must allocate and deallocate before returning or making a tail call.

Register usage at the time of the return for single value return, which goes with the unknown-values convention the caller used.

A0 This holds the value.

CODE This holds the lisp-return-address at which the system continues executing.

CSP This holds the CFP. That is, the stack is guaranteed to be clean, and there is no code at the return site to adjust the CSP.

CFP This holds the OCFP.

Additional register usage for multiple value return:

NARGS This holds the number of values returned.

A0 ... An These holds the first n+1 values, or NIL if there are less than n+1 values.

CSP Returner stores CSP to hold its CFP + NARGS * <address units per word>

OCFP Returner stores this as its CFP, so the returnee has a handle on either the start of the returned values on the stack.

ALLOCATE FULL CALL FRAME.

If the number of call arguments (passed to the VOP as an info argument) indicates that there are stack arguments, then it makes some callee frame for arguments:

   VOP-result <- CSP
   CSP <- CSP + value of VOP info arg times address units per word.

In a call sequence, move some arguments to the right places.

There’s a variety of MOVE-ARGUMENT VOP’s.

FULL CALL VOP’S (variations determined by whether it’s named, it’s a tail call, there is a variable arg count, etc.)

  if variable number of arguments
    NARGS <- (CSP - value of VOP argument) shift right by address units per word.
    A0...An <- values off of VOP argument (just fill them all)
  else
    NARGS <- value of VOP info argument (always a constant)

  if tail call
    OCFP <- value from VOP argument
    LRA <- value from VOP argument
    CFP stays the same since we reuse the frame
    NSP <- NFP
  else
    OCFP <- CFP
    LRA <- compute LRA by adding an assemble-time determined constant to
    	   CODE.
    CFP <- new frame pointer (remembered when starting to compute args)
           This is CSP if no stack args.
    when (current-nfp-tn VOP-self-pointer)
      stack-temp <- NFP

  if named
    CNAME <- function symbol name
    the-fun <- function object out of symbol

  LEXENV <- the-fun (from previous line or VOP argument)
  CODE <- function-entry (the first word after the-fun)
  LIP <- calc first instruction addr (CODE + constant-offset)
  jump and run off temp

  <emit Lisp return address data-block>
  <default and move return values OR receive return values>
  when (current-nfp-tn VOP-self-pointer)
    NFP <- stack-temp

Callee:

XEP-ALLOCATE-FRAME
  emit function header (maybe initializes offset back to component start,
  			but other pointers are set up at load-time.  Pads
			to dual-word boundary.)
  CSP <- CFP + compile-time determined constant (frame size)
  if the function uses the number stack
    NFP <- NSP
    NSP <- NSP + compile-time determined constant (number stack frame size)

SETUP-ENVIRONMENT
(either use this or the next one)

CODE <- CODE - assembler-time determined offset from function-entry back to
	       the code data-block address.

SETUP-CLOSURE-ENVIRONMENT
(either use this or the previous one)
After this the CLOSURE-REF VOP can reference closure variables.

VOP-result <- LEXENV
CODE <- CODE - assembler-time determined offset from function-entry back to
	       the code data-block address.

Return VOP’s RETURN and RETURN-MULTIPLE are for the unknown-values return convention. For some previous caller this is either it wants n values (and it doesn’t know how many are coming), or it wants all the values returned (and it doesn’t know how many are coming).

RETURN (known fixed number of values, used with the unknown-values convention in the caller.) When compiler invokes VOP, all values are already where they should be; just get back to caller.

when (current-nfp-tn VOP-self-pointer)
  ;; The number stack grows down in memory.
  NSP <- NFP + number stack frame size for calls within the currently
                  compiling component
	       times address units per word
CODE <- value of VOP argument with LRA
if VOP info arg is 1 (number of values we know we're returning)
  CSP <- CFP
  LIP <- calc target addr
          (CODE + skip over LRA header word + skip over address units per branch)
	  (The branch is in the caller to skip down to the MV code.)
else
  NARGS <- value of VOP info arg
  nil out unused arg regs
  OCFP <- CFP  (This indicates the start of return values on the stack,
  		but you leave space for those in registers for convenience.)
  CSP <- CFP + NARGS * address-units-per-word
  LIP <- calc target addr (CODE + skip over LRA header word)
CFP <- value of VOP argument with OCFP
jump and run off LIP

RETURN-MULTIPLE (unknown number of values, used with the unknown-values convention in the caller.) When compiler invokes VOP, it gets TN’s representing a pointer to the values on the stack and how many values were computed.

when (current-nfp-tn VOP-self-pointer)
  ;; The number stack grows down in memory.
  NSP <- NFP + number stack frame size for calls within the currently
                  compiling component
	       times address units per word
NARGS <- value of VOP argument
copy the args to the beginning of the current (returner's) frame.
   Actually some go into the argument registers.  When putting the rest at
   the beginning of the frame, leave room for those in the argument registers.
CSP <- CFP + NARGS * address-units-per-word
nil out unused arg regs
OCFP <- CFP  (This indicates the start of return values on the stack,
	      but you leave space for those in registers for convenience.)
CFP <- value of VOP argument with OCFP
CODE <- value of VOP argument with LRA
LIP <- calc target addr (CODE + skip over LRA header word)
jump and run off LIP

Returnee The call VOP’s call DEFAULT-UNKNOWN-VALUES or RECEIVE-UNKNOWN-VALUES after spitting out transfer control to get stuff from the returner.

DEFAULT-UNKNOWN-VALUES (We know what we want and we got something.) If returnee wants one value, it never does anything to deal with a shortage of return values. However, if start at PC, then it has to adjust the stack pointer to dump extra values (move OCFP into CSP). If it starts at PC+N, then it just goes along with the “want one value, got it” case. If the returnee wants multiple values, and there’s a shortage of return values, there are two cases to handle. One, if the returnee wants fewer values than there are return registers, and we start at PC+N, then it fills in return registers A1..A<desired values necessary>; if we start at PC, then the returnee is fine since the returning conventions have filled in the unused return registers with nil, but the returnee must adjust the stack pointer to dump possible stack return values (move OCFP to CSP). Two, if the returnee wants more values than the number of return registers, and it starts at PC+N (got one value), then it sets up returnee state as if an unknown number of values came back:

   A0 has the one value
   A1..An get nil
   NARGS gets 1
   OCFP gets CSP, so general code described below can move OCFP into CSP
If we start at PC, then branch down to the general ``got k values, wanted n''
code which takes care of the following issues:
   If k < n, fill in stack return values of nil for shortage of return
      values and move OCFP into CSP
   If k >= n, move OCFP into CSP
This also restores CODE from LRA by subtracting an assemble-time constant.

RECEIVE-UKNOWN-VALUES (I want whatever I get.) We want these at the end of our frame. When the returnee starts at PC, it moves the return value registers to OCFP..OCFP[An] ignoring where the end of the stack is and whether all the return value registers had values. The returner left room on the stack before the stack return values for the register return values. When the returnee starts at PC+N, bump CSP by 1 and copy A0 there. This also restores CODE from LRA by subtracting an assemble-time constant.

Local call

There are three flavors: 1] KNOWN-CALL-LOCAL Uses known call convention where caller and callee agree where all the values are, and there’s a fixed number of return values. 2] CALL-LOCAL Uses the unknown-values convention, but we expect a particular number of values in return. 3] MULTIPLE-CALL-LOCAL Uses the unknown-values convention, but we want all values returned.

ALLOCATE-FRAME

If the number of call arguments (passed to the VOP as an info argument) indicates that there are stack arguments, then it makes some callee frame for arguments:

   VOP-result1 <- CSP
   CSP <- CSP + control stack frame size for calls within the currently
   		   compiling component
   		times address units per word.
   when (callee-nfp-tn <VOP info arg holding callee>)
     ;; The number stack grows down.
     ;; May have to round to dual-word boundary if machines C calling
     ;;    conventions demand this.
     NSP <- NSP - number stack frame size for calls within the currently
     		     compiling component
		  times address units per word
     VOP-result2 <- NSP

KNOWN-CALL-LOCAL, CALL-LOCAL, MULTIPLE-CALL-LOCAL KNOWN-CALL-LOCAL has no need to affect CODE since CODE is the same for the caller/returnee and the returner. This uses KNOWN-RETURN. With CALL-LOCAL and MULTIPLE-CALL-LOCAL, the caller/returnee must fixup CODE since the callee may do a tail full call. This happens in the code emitted by DEFAULT-UNKNOWN-VALUES and RECEIVE-UNKNOWN-VALUES. We use these return conventions since we don’t know what kind of values the returner will give us. This could happen due to a tail full call to an unknown function, or because the callee had different return points that returned various numbers of values.

when (current-nfp-tn VOP-self-pointer)   ;Get VOP self-pointer with
					 ;DEFINE-VOP switch :vop-var.
  stack-temp <- NFP
CFP <- value of VOP arg
when (callee-nfp-tn <VOP info arg holding callee>)
  <where-callee-wants-NFP-tn>  <-  value of VOP arg
<where-callee-wants-LRA-tn>  <-  compute LRA by adding an assemble-time
				 determined constant to CODE.
jump and run off VOP info arg holding start instruction for callee

<emit Lisp return address data-block>
<case call convention
  known: do nothing
  call: default and move return values
  multiple: receive return values
>
when (current-nfp-tn VOP-self-pointer)   
  NFP <- stack-temp

KNOWN-RETURN

CSP <- CFP
when (current-nfp-tn VOP-self-pointer)
  ;; number stack grows down in memory.
  NSP <- NFP + number stack frame size for calls within the currently
                  compiling component
	       times address units per word
LIP <- calc target addr (value of VOP arg + skip over LRA header word)
CFP <- value of VOP arg
jump and run off LIP

34.1 Constant Operands

If the code emitted for a VOP when an argument is constant is very different than the non-constant case, then it may be desirable to special-case the operation in VMR conversion by emitting different VOPs. An example would be if SVREF is only open-coded when the index is a constant, and turns into a miscop call otherwise. We wouldn’t want constant references to spuriously allocate all the miscop linkage registers on the off chance that the offset might not be constant. See the :constant feature of VOP primitive type restrictions.

34.2 Supporting Multiple Hardware Configurations

A winning way to change emitted code depending on the hardware configuration, i.e. what FPA is present is to do this using primitive types. Note that the Primitive-Type function is VM supplied, and can look at any appropriate hardware configuration switches. Short-Float can become 6881-Short-Float, AFPA-Short-Float, etc. There would be separate SBs and SCs for the registers of each kind of FP hardware, with each hardware-specific primitive type using the appropriate float register SC. Then the hardware specific templates would provide AFPA-Short-Float as the argument type restriction.

Primitive type changes:

The primitive-type structure is given a new %Type slot, which is the CType structure that is equivalent to this type. There is also a Guard slot, which, if true is a function that control whether this primitive type is allowed (due to hardware configuration, etc.)

We add new :Type and :Guard keywords to Def-Primitive-Type. Type is the type specifier that is equivalent (default to the primitive-type name), and Guard is an expression evaluated in the null environment that controls whether this type applies (default to none, i.e. constant T).

The Primitive-Type-Type function returns the Lisp CType corresponding to a primitive type. This is the %Type unless there is a guard that returns false, in which case it is the empty type (i.e. NIL).

[But this doesn’t do what we want it to do, since we will compute the function type for a template at load-time, so they will correspond to whatever configuration was in effect then. Maybe we don’t want to dick with guards here (if at all). I guess we can defer this issue until we actually support different FP configurations. But it would seem pretty losing to separately flame about all the different FP configurations that could be used to open-code + whenever we are forced to closed-code +.

If we separately report each better possibly applicable template that we couldn’t use, then it would be reasonable to report any conditional template allowed by the configuration.

But it would probably also be good to give some sort of hint that perhaps it would be a good time to make sure you understand how to tell the compiler to compile for a particular configuration. Perhaps if there is a template that applies *but for the guard*, then we could give a note. This way, if someone thinks they are being efficient by throwing in lots of declarations, we can let them know that they may have to do more.

I guess the guard should be associated with the template rather than the primitive type. This would allow LTN and friends to easily tell whether a template applies in this configuration. It is also probably more natural for some sorts of things: with some hardware variants, it may be that the SBs and representations (SCs) are really the same, but there are some different allowed operations. In this case, we could easily conditionalize VOPs without the increased complexity due to bogus SCs. If there are different storage resources, then we would conditionalize Primitive-Type as well.

34.3 Special-case VMR convert methods

(defun continuation-tn (cont &optional (check-p t)) ...) Return the TN which holds Continuation’s first result value. In general this may emit code to load the value into a TN. If Check-P is true, then when policy indicates, code should be emitted to check that the value satisfies the continuation asserted type.

(defun result-tn (cont) ...) Return the TN that Continuation’s first value is delivered in. In general, may emit code to default any additional values to NIL.

(defun result-tns (cont n) ...) Similar to Result-TN, except that it returns a list of N result TNs, one for each of the first N values.

Nearly all open-coded functions should be handled using standard template selection. Some (all?) exceptions:

• List, List* and Vector take arbitrary numbers of arguments. Could implement Vector as a source transform. Could even do List in a transform if we explicitly represent the stack args using %More-Args or something.
• %Typep varies a lot depending on the type specifier. We don’t want to transform it, since we want %Typep as a canonical form so that we can do type optimizations.
• Apply is weird.
• Funny functions emitted by the compiler: %Listify-Rest-Args, Arg, %More-Args, %Special-Bind, %Catch, %Unknown-Values (?), %Unwind-Protect, %Unwind, %%Primitive.

37.1 Use of %PRIMITIVE

Note: %PRIMITIVE can only be used in compiled code. It is a trapdoor into the compiler, not a general syntax for accessing “sub-primitives”. It’s main use is in implementation-dependent compiler transforms. It saves us the effort of defining a “phony function” (that is not really defined), and also allows direct communication with the code generator through codegen-info arguments.

Some primitives may be exported from the VM so that %PRIMITIVE can be used to make it explicit that an escape routine or interpreter stub is assuming an operation is implemented by the compiler.

38.1 Tracing and Breakpoints

Here are a few notes on how tracing of compiled code works.

When a function is traced, a breakpoint instruction is placed at the start of the function, replacing the instruction that was there. (This is a :function-start breakpoint.) (This appears to be one instruction after the no-arg parsing entry point.) The breakpoint instruction is, of course, architecture-specific, but it must signal a trap_Breakpoint trap.

When the code is run, the breakpoint instruction is executed causing a trap. The trap handler runs HANDLE-BREAKPOINT to process it. After doing the appropriate processing, we now need to continue. Of course, since the real instruction has been replaced, we to run the original instruction. This is done by now inserting a new breakpoint after the original breakpoint. This breakpoint must be of the type trap_AfterBreakpoint. The original instruction is restored and execution continues from there. Then the trap_AfterBreakpoint instruction gets executed. The handler for this puts back the original breakpoint, thereby preserving the breakpoint. Then we replace the AfterBreakpoint with the original instruction and continue from there.

That’s all pretty straightforward in concept.

When tracing, additional information is needed. Breakpoints have the ability to run arbitrary lisp code to process the breakpoint. Tracing uses this feature.

When this breakpoint is reached, HANDLE-BREAKPOINT runs the breakpoint hook function. This function figures out where this function would return to and creates a new return area and replaces the original return address with this new address. Thus, when the function returns, it returns to this new location instead of the original.

This new return address is a specially created bogus LRA object. It is a code-component whose body consists of a code template copied from an assembly routine into the body. The assembly routine is the code in function_end_breakpoint_guts. This bogus LRA object stores the real LRA for the function, and also an indication if the known-return convention is used for this function.

The bogus LRA object contains a function-end breakpoint (trap_FunctionEndBreakpoint). When it’s executed the trap handler handles this breakpoint. It figures out where this trap come from and calls HANDLE-BREAKPOINT to handle it. HANDLE-BREAKPOINT returns and the trap handler arranges it so that this bogus LRA returns to the real LRA.

Thus, we can do something when a Lisp function returns, like printing out the return value for the function for tracing.

There are lots of internal details left out here, but gives a short overview of how this works. For more info, look at code/debug-int.lisp and lisp/breakpoint.c, and, of course, the various <foo>-arch.c files.

39.1 The Debug-Info Structure

The Debug-Info structure directly represents information about the source code, and points to other structures that describe the layout of run-time data structures.

Make some sort of minimal debug-info format that would support at least the common cases of level 1 (since that is what we would release), and perhaps level 0. Actually, it seems it wouldn’t be hard to crunch nearly all of the debug-function structure and debug-info function map into a single byte-vector. We could have an uncrunch function that restored the current format. This would be used by the debugger, and also could be used by purify to delete parts of the debug-info even when the compiler dumps it in crunched form. [Note that this isn’t terribly important if purify is smart about debug-info...]

Compiled source map representation:

[### store in debug-function PC at which env is properly initialized, i.e. args (and return-pc, etc.) in internal locations. This is where a :function-start breakpoint would break.]

[### Note that that we can easily cache the form-number => source-path or form-number => form translation using a vector indexed by form numbers that we build during a walk.]

Instead of using source paths in the debug-info, use “form numbers”. The form number of a form is the number of forms that we walk to reach that form when doing a pre-order walk of the source form. [Might want to use a post-order walk, as that would more closely approximate evaluation order.]

We probably want to continue using source-paths in the compiler, since they are quick to compute and to get you to a particular form. [### But actually, I guess we don’t have to precompute the source paths and annotate nodes with them: instead we could annotate the nodes with the actual original source form. Then if we wanted to find the location of that form, we could walk the root source form, looking that original form. But we might still need to enter all the forms in a hashtable so that we can tell during IR1 conversion that a given form appeared in the original source.]

Note that form numbers have an interesting property: it is quite efficient to determine whether an arbitrary form is a subform of some other form, since the form number of B will be > than A’s number and < A’s next sibling’s number iff B is a subform of A.

This should be quite useful for doing the source=>pc mapping in the debugger, since that problem reduces to finding the subset of the known locations that are for subforms of the specified form.

Assume a byte vector with a standard variable-length integer format, something like this:

    0..253 => the integer
    254 => read next two bytes for integer
    255 => read next four bytes for integer

Then a compiled debug block is just a sequence of variable-length integers in a particular order, something like this:

    number of successors
    ...offsets of each successor in the function's blocks vector...
    first PC
    [offset of first top-level form (in forms) (only if not component default)]
    form number of first source form
    first live mask (length in bytes determined by number of VARIABLES)
    ...more <PC, top-level form offset, form-number, live-set> tuples...

We determine the number of locations recorded in a block by finding the start of the next compiled debug block in the blocks vector.

[### Actually, only need 2 bits for number of successors {0,1,2}. We might want to use other bits in the first byte to indicate the kind of location.] [### We could support local packing by having a general concept of “alternate locations” instead of just regular and save locations. The location would have a bit indicating that there are alternate locations, in which case we read the number of alternate locations and then that many more SC-OFFSETs. In the debug-block, we would have a second bit mask with bits set for TNs that are in an alternate location. We then read a number for each such TN, with the value being interpreted as an index into the Location’s alternate locations.]

It looks like using structures for the compiled-location-info is too bulky. Instead we need some packed binary representation.

First, let’s represent an SC/offset pair with an “SC-Offset”, which is an integer with the SC in the low 5 bits and the offset in the remaining bits:

    ----------------------------------------------------
    | Offset (as many bits as necessary) | SC (5 bits) |
    ----------------------------------------------------

Probably the result should be constrained to fit in a fixnum, since it will be more efficient and gives more than enough possible offsets.

We can then represent a compiled location like this:

    single byte of boolean flags:
	uninterned name
	packaged name
	environment-live
	has distinct save location
        has ID (name not unique in this fun)
    name length in bytes (as var-length integer)
    ...name bytes...
    [if packaged, var-length integer that is package name length]
     ...package name bytes...]
    [If has ID, ID as var-length integer]
    SC-Offset of primary location (as var-length integer)
    [If has save SC, SC-Offset of save location (as var-length integer)]

But for a whizzy breakpoint facility, we would need a good source=>code map. Dumping a complete code=>source map might be as good a way as any to represent this, due to the one-to-many relationship between source and code locations.

We might be able to get away with just storing the source locations for the beginnings of blocks and maintaining a mapping from code ranges to blocks. This would be fine both for the profiler and for the “where am I running now” indication. Users might also be convinced that it was most interesting to break at block starts, but I don’t really know how easily people could develop an understanding of basic blocks.

It could also be a bit tricky to map an arbitrary user-designated source location to some “closest” source location actually in the debug info. This problem probably exists to some degree even with a full source map, since some forms will never appear as the source of any node. It seems you might have to negotiate with the user. He would mouse something, and then you would highlight some source form that has a common prefix (i.e. is a prefix of the user path, or vice-versa.) If they aren’t happy with the result, they could try something else. In some cases, the designated path might be a prefix of several paths. This ambiguity might be resolved by picking the shortest path or letting the user choose.

At the primitive level, I guess what this means is that the structure of source locations (i.e. source paths) must be known, and the source=>code operation should return a list of <source,code> pairs, rather than just a list of code locations. This allows the debugger to resolve the ambiguity however it wants.

I guess the formal definition of which source paths we would return is:

All source paths in the debug info that have a maximal common prefix with the specified path. i.e. if several paths have the complete specified path as a prefix, we return them all. Otherwise, all paths with an equally large common prefix are returned: if the path with the most in common matches only the first three elements, then we return all paths that match in the first three elements. As a degenerate case (which probably shouldn’t happen), if there is no path with anything in common, then we return *all* of the paths.

In the DEBUG-SOURCE structure we may ultimately want a vector of the start positions of each source form, since that would make it easier for the debugger to locate the source. It could just open the file, FILE-POSITION to the form, do a READ, then loop down the source path. Of course, it could read each form starting from the beginning, but that might be too slow.

Do XEPs really need Debug-Functions? The only time that we will commonly end up in the debugger on an XEP is when an argument type check fails. But I suppose it would be nice to be able to print the arguments passed...

Note that assembler-level code motion such as pipeline reorganization can cause problems with our PC maps. The assembler needs to know that debug info markers are different from real labels anyway, so I suppose it could inhibit motion across debug markers conditional on policy. It seems unworthwhile to remember the node for each individual instruction.

For tracing block-compiled calls:

    Info about return value passing locations?
    Info about where all the returns are?

We definitely need the return-value passing locations for debug-return. The question is what the interface should be. We don’t really want to have a visible debug-function-return-locations operation, since there are various value passing conventions, and we want to paper over the differences.

Probably should be a compiler option to initialize stack frame to a special uninitialized object (some random immediate type). This would aid debugging, and would also help GC problems. For the latter reason especially, this should be locally-turn-onable (off of policy? the new debug-info quality?).

What about the interface between the evaluator and the debugger? (i.e. what happens on an error, etc.) Compiler error handling should be integrated with run-time error handling. Ideally the error messages should look the same. Practically, in some cases the run-time errors will have less information. But the error should look the same to the debugger (or at least similar).

• Debugger Interface
• Variable maps
• Stack parsing

Location:
	The constant information about the place where a value is stored,
        everything but which particular frame it is in.  Operations:
        location name, type, etc.
        location-value frame location (setf'able)
	monitor-location location function
            Function is called whenever location is set with the location,
            frame and old value.  If active values aren't supported, then we
            dummy the effect using breakpoints, in which case the change won't
            be noticed until the end of the block (and intermediate changes
            will be lost.)
debug info:
        All the debug information for a component.
Frame:
	frame-changed-locations frame => location*
            Return a list of the locations in frame that were changed since the
            last time this function was called.  Or something.  This is for
            displaying interesting state changes at breakpoints.
	save-frame-state frame => frame-state
	restore-frame-state frame frame-state
	    These operations allow the debugger to back up evaluation, modulo
	    side-effects and non-local control transfers.  This copies and
	    restores all variables, temporaries, etc, local to the frame, and
	    also the current PC and dynamic environment (current catch, etc.)

	    At the time of the save, the frame must be for the running function
	    (not waiting for a call to return.)  When we restore, the frame
	    becomes current again, effectively exiting from any frames on top.
	    (Of course, frame must not already be exited.)
       
Thread:
        Representation of which stack to use, etc.
Block:
        What successors the block has, what calls there are in the block.
        (Don't need to know where calls are as long as we know called function,
        since can breakpoint at the function.)  Whether code in this block is
        wildly out of order due to being the result of loop-invariant
        optimization, etc.  Operations:
        block-successors block => code-location*
        block-forms block => (source-location code-location)*
            Return the corresponding source locations and code locations for
            all forms (and form fragments) in the block.

(defstruct var-info
  ;;
  ;; This variable's name. (symbol-name of the symbol)
  (name nil :type simple-string)
  ;;
  ;; The SC, ID and offset, encoded as bit-fields.
  (bits nil :type fixnum)
  ;;
  ;; The set of blocks this variable is live in.  If a bit-vector, then it has
  ;; a 1 when indexed by the number of a block that it is live in.  If an
  ;; I-vector, then it lists the live block numbers.  If a fixnum, then that is
  ;; the number of the sole live block.
  (lifetime nil :type (or vector fixnum))
  ;;
  ;; The variable's type, represented as list-style type descriptor.
  type)

40.1 Tagging

The following is a key of the three bit low-tagging scheme:

000

even fixnum

001

function pointer

010

even other-immediate (header-words, characters, symbol-value trap value, etc.)

011

list pointer

100

odd fixnum

101

structure pointer

110

odd other immediate

111

other-pointer to data-blocks (other than conses, structures, and functions)

This tagging scheme forces a dual-word alignment of data-blocks on the heap, but this can be pretty negligible:

• RATIOS and COMPLEX must have a header-word anyway since they are not a major type. This wastes one word for these infrequent data-blocks since they require two words for the data.
• BIGNUMS must have a header-word and probably contain only one other word anyway, so we probably don’t waste any words here. Most bignums just barely overflow fixnums, that is by a bit or two.
• Single and double FLOATS? no waste, or one word wasted
• SYMBOLS have a pad slot (current called the setf function, but unused.)

Everything else is vector-like including code, so these probably take up so many words that one extra one doesn’t matter.

40.2 GC Comments

Data-Blocks comprise only descriptors, or they contain immediate data and raw bits interpreted by the system. GC must skip the latter when scanning the heap, so it does not look at a word of raw bits and interpret it as a pointer descriptor. These data-blocks require headers for GC as well as for operations that need to know how to interpret the raw bits. When GC is scanning, and it sees a header-word, then it can determine how to skip that data-block if necessary. Header-Words are tagged as other-immediates. See sec-other-immediates and sec-data-blocks-and-header for comments on distinguishing header-words from other-immediate data. This distinction is necessary since we scan through data-blocks containing only descriptors just as we scan through the heap looking for header-words introducing data-blocks.

Data-Blocks containing only descriptors do not require header-words for GC since the entire data-block can be scanned by GC a word at a time, taking whatever action is necessary or appropriate for the data in that slot. For example, a cons is referenced by a descriptor with a specific tag, and the system always knows the size of this data-block. When GC encounters a pointer to a cons, it can transport it into the new space, and when scanning, it can simply scan the two words manifesting the cons interpreting each word as a descriptor. Actually there is no cons tag, but a list tag, so we make sure the cons is not nil when appropriate. A header may still be desired if the pointer to the data-block does not contain enough information to adequately maintain the data-block. An example of this is a simple-vector containing only descriptor slots, and we attach a header-word because the descriptor pointing to the vector lacks necessary information – the type of the vector’s elements, its length, etc.

There is no need for a major tag for GC forwarding pointers. Since the tag bits are in the low end of the word, a range check on the start and end of old space tells you if you need to move the thing. This is all GC overhead.

40.3 Structures

A structure descriptor has the structure lowtag type code, making structurep a fast operation. A structure data-block has the following format:

    -------------------------------------------------------
    |   length (24 bits) | Structure header type (8 bits) |
    -------------------------------------------------------
    |   structure type name (a symbol)                    |
    -------------------------------------------------------
    |   structure slot 0                                  |
    -------------------------------------------------------
    |   ... structure slot length - 2                     |
    -------------------------------------------------------

The header word contains the structure length, which is the number of words (other than the header word.) The length is always at least one, since the first word of the structure data is the structure type name.

40.4 Fixnums

A fixnum has one of the following formats in 32 bits:

    -------------------------------------------------------
    |        30 bit 2's complement even integer   | 0 0 0 |
    -------------------------------------------------------

or

    -------------------------------------------------------
    |        30 bit 2's complement odd integer    | 1 0 0 |
    -------------------------------------------------------

Effectively, there is one tag for immediate integers, two zeros. This buys one more bit for fixnums, and now when these numbers index into simple-vectors or offset into memory, they point to word boundaries on 32-bit, byte-addressable machines. That is, no shifting need occur to use the number directly as an offset.

This format has another advantage on byte-addressable machines when fixnums are offsets into vector-like data-blocks, including structures. Even though we previously mentioned data-blocks are dual-word aligned, most indexing and slot accessing is word aligned, and so are fixnums with effectively two tag bits.

Two tags also allow better usage of special instructions on some machines that can deal with two low-tag bits but not three.

Since the two bits are zeros, we avoid having to mask them off before using the words for arithmetic, but division and multiplication require special shifting.

40.5 Other-immediates

As for fixnums, there are two different three-bit lowtag codes for other-immediate, allowing 64 other-immediate types:

----------------------------------------------------------------
|   Data (24 bits)        | Type (8 bits with low-tag)   | 1 0 |
----------------------------------------------------------------

The type-code for an other-immediate type is considered to include the two lowtag bits. This supports the concept of a single “type code” namespace for all descriptors, since the normal lowtag codes are disjoint from the other-immediate codes.

For other-pointer objects, the full eight bits of the header type code are used as the type code for that kind of object. This is why we use two lowtag codes for other-immediate types: each other-pointer object needs a distinct other-immediate type to mark its header.

The system uses the other-immediate format for characters, the symbol-value unbound trap value, and header-words for data-blocks on the heap. The type codes are laid out to facilitate range checks for common subtypes; for example, all numbers will have contiguous type codes which are distinct from the contiguous array type codes. See sec-data-blocks-and-o-i for details.

40.6 Data-Blocks and Header-Word Format

Pointers to data-blocks have the following format:

----------------------------------------------------------------
|      Dual-word address of data-block (29 bits)       | 1 1 1 |
----------------------------------------------------------------

The word pointed to by the above descriptor is a header-word, and it has the same format as an other-immediate:

----------------------------------------------------------------
|   Data (24 bits)        | Type (8 bits with low-tag) | 0 1 0 |
----------------------------------------------------------------

This is convenient for scanning the heap when GC’ing, but it does mean that whenever GC encounters an other-immediate word, it has to do a range check on the low byte to see if it is a header-word or just a character (for example). This is easily acceptable performance hit for scanning.

The system interprets the data portion of the header-word for non-vector data-blocks as the word length excluding the header-word. For example, the data field of the header for ratio and complex numbers is two, one word each for the numerator and denominator or for the real and imaginary parts.

For vectors and data-blocks representing Lisp objects stored like vectors, the system (usually) ignores the data portion of the header-word:

----------------------------------------------------------------
| Unused Data (24 bits)   | Type (8 bits with low-tag) | 0 1 0 |
----------------------------------------------------------------
|           Element Length of Vector (30 bits)           | 0 0 | 
----------------------------------------------------------------

Using a separate word allows for much larger vectors, and it allows length to simply access a single word without masking or shifting. Similarly, the header for complex arrays and vectors has a second word, following the header-word, the system uses for the fill pointer, so computing the length of any array is the same code sequence.

For normal Lisp vectors, the data portion MUST be zero. For hash tables, a vector is used to store information about the hash key and value, and the data portion is non-zero to indicate to GC that this is the key/value vector for the hash table. GENCGC uses this to determine scavenge the key/value pairs correctly. Cheney GC also uses this to determine if rehashing (for EQ hash tables) is needed.

40.7 Data-Blocks and Other-immediates Typing

These are the other-immediate types. We specify them including all low eight bits, including the other-immediate tag, so we can think of the type bits as one type – not an other-immediate major type and a subtype. Also, fetching a byte and comparing it against a constant is more efficient than wasting even a small amount of time shifting out the other-immediate tag to compare against a five bit constant. (The current values can be obtained from the generated internals.h file.)

                                                         HEX
Number   (< 36)
  bignum                                           10     0A
    ratio                                          14     0E
    single-float                                   18     12
    double-float                                   22     16
    double-double-float                            26     1A
    complex                                        30     1E
    (complex single-float)                         34     22
    (complex double-float)                         38     26
    (complex double-double-float)                  42     2A

Array   (<= 46 code 118)
   Simple-Array   (<= 46 code 118)
         simple-array                              46     2E
      Vector  (<= 50 code 118)
         simple-string                             50     32
         simple-bit-vector                         54     36
         simple-vector                             58     3A
         (simple-array (unsigned-byte 2) (*))      62     3E
         (simple-array (unsigned-byte 4) (*))      66     42
         (simple-array (unsigned-byte 8) (*))      70     46
         (simple-array (unsigned-byte 16) (*))     74     4A
         (simple-array (unsigned-byte 32) (*))     78     4E
         (simple-array (signed-byte 8) (*))        82     52
         (simple-array (signed-byte 16) (*))       86     56
         (simple-array (signed-byte 30) (*))       90     5A
         (simple-array (signed-byte 32) (*))       94     5E
         (simple-array single-float (*))           98     62
         (simple-array double-float (*))           102    66
         (simple-array double-double-float (*))    106    6A
         (simple-array (complex single-float) (*)  110    6E
         (simple-array (complex double-float) (*)  114    72
         (simple-array (complex double-double) (*) 118    76
      complex-string                               122    7A
      complex-bit-vector                           126    7E
      (array * (*))   -- general complex vector.   130    82
   complex-array                                   134    86

code-header-type                                   138    8A
function-header-type                               142    8E
closure-header-type                                146    92
funcallable-instance-header-type                   150    96
byte-code-function-header-type                     154    9A
byte-code-closure-header-type                      158    9E
closure-function-header-type                       162    A2
return-pc-header-type (a.k.a LRA)                  166    A6
value-cell-header-type                             170    AA
symbol-header-type                                 174    AE
base-character-type                                178    B2
system-area-pointer-type (header type)             182    B6
unbound-marker                                     186    BA
weak-pointer-type                                  190    BE
instance-header-type                               194    C2
fdefn-type                                         198    C6
scavenger-hook-type                                202    CA

40.8 Strings

All strings in the system are C-null terminated. This saves copying the bytes when calling out to C. The only time this wastes memory is when the string contains a multiple of eight characters, and then the system allocates two more words (since Lisp objects are dual-word aligned) to hold the C-null byte. Since the system will make heavy use of C routines for systems calls and libraries that save reimplementation of higher level operating system functionality (such as pathname resolution or current directory computation), saving on copying strings for C should make C call out more efficient.

The length word in a string header, See sec-data-blocks-and-header, counts only the characters truly in the Common Lisp string. Allocation and GC will have to know to handle the extra C-null byte, and GC already has to deal with rounding up various objects to dual-word alignment.

40.9 Symbols and NIL

Symbol data-block has the following format:

-------------------------------------------------------
|     5 (data-block words)     | Symbol Type (8 bits) |
-------------------------------------------------------
|                       Value Descriptor              |
-------------------------------------------------------
|  Hash Value (x86/amd64/sparc) Unused (other arch.)  |
-------------------------------------------------------
|                        Property List                |
-------------------------------------------------------
|                          Print Name                 |
-------------------------------------------------------
|                           Package                   |
-------------------------------------------------------

All of these slots are self-explanatory given what symbols must do in Common Lisp.

The issues with nil are that we want it to act like a symbol, and we need list operations such as CAR and CDR to be fast on it. CMU Common Lisp solves this by putting nil as the first object in static space, where other global values reside, so it has a known address in the system:

-------------------------------------------------------  <-- space
|     6 (data-block words)     |         0            |      start
-------------------------------------------------------
|     0 (data-block words)     | Symbol Type (8 bits) |
-------------------------------------------------------  <-- nil
|                           Value/CAR                 |
-------------------------------------------------------
|                         Hash Value/CDR              |
-------------------------------------------------------
|                         Property List               |
-------------------------------------------------------
|                           Print Name                |
-------------------------------------------------------
|                            Package                  |
-------------------------------------------------------
|                              ...                    |
-------------------------------------------------------

In addition, we make the list typed pointer to nil actually point past the header word of the nil symbol data-block. This has usefulness explained below. The value and hash-value of nil are nil. Therefore, any reference to nil used as a list has quick list type checking, and CAR and CDR can go right through the first and second words as if nil were a cons object.

When there is a reference to nil used as a symbol, the system adds offsets to the address the same as it does for any symbol. This works due to a combination of nil pointing past the symbol header-word and the chosen list and other-pointer type tags. The list type tag is four less than the other-pointer type tag, but nil points four additional bytes into its symbol data-block.

40.10 Array Headers

The array-header data-block has the following format:

----------------------------------------------------------------
| Header Len (24 bits) = Array Rank +6   | Array Type (8 bits) |
----------------------------------------------------------------
|               Fill Pointer (30 bits)                   | 0 0 | 
----------------------------------------------------------------
|               Fill Pointer p (29 bits) -- t or nil   | 1 1 1 |
----------------------------------------------------------------
|               Available Elements (30 bits)             | 0 0 | 
----------------------------------------------------------------
|               Data Vector (29 bits)                  | 1 1 1 | 
----------------------------------------------------------------
|               Displacement (30 bits)                   | 0 0 | 
----------------------------------------------------------------
|               Displacedp (29 bits) -- t or nil       | 1 1 1 | 
----------------------------------------------------------------
|               Range of First Index (30 bits)           | 0 0 | 
----------------------------------------------------------------
                              .
                              .
                              .

The array type in the header-word is one of the eight-bit patterns from “Data-Blocks and Other-immediates Typing”, sec-data-blocks-and-header, indicating that this is a complex string, complex vector, complex bit-vector, or a multi-dimensional array. The data portion of the other-immediate word is the length of the array header data-block. Due to its format, its length is always six greater than the array’s number of dimensions. The following words have the following interpretations and types:

Fill Pointer:

This is a fixnum indicating the number of elements in the data vector actually in use. This is the logical length of the array, and it is typically the same value as the next slot. This is the second word, so LENGTH of any array, with or without an array header, is just four bytes off the pointer to it.

Fill Pointer P:

This is either T or NIL and indicates whether the array uses the fill-pointer or not.

Available Elements:

This is a fixnum indicating the number of elements for which there is space in the data vector. This is greater than or equal to the logical length of the array when it is a vector having a fill pointer.

Data Vector:

This is a pointer descriptor referencing the actual data of the array. This a data-block whose first word is a header-word with an array type as described in “Data-Blocks and Header-Word Format”, sec-data-blocks-and-header and “Data-Blocks and Other-immediates Typing”, sec-data-blocks-and-o-i

Displacement:

This is a fixnum added to the computed row-major index for any array. This is typically zero.

Displacedp:

This is either t or nil. This is separate from the displacement slot, so most array accesses can simply add in the displacement slot. The rare need to know if an array is displaced costs one extra word in array headers which probably aren’t very frequent anyway.

Range of First Index:

This is a fixnum indicating the number of elements in the first dimension of the array. Legal index values are zero to one less than this number inclusively. IF the array is zero-dimensional, this slot is non-existent.

... (remaining slots):

There is an additional slot in the header for each dimension of the array. These are the same as the Range of First Index slot.

40.11 Bignums

Bignum data-blocks have the following format:

-------------------------------------------------------
|      Length (24 bits)        | Bignum Type (8 bits) |
-------------------------------------------------------
|             least significant bits                  |
-------------------------------------------------------
                            .
                            .
                            .

The elements contain the two’s complement representation of the integer with the least significant bits in the first element or closer to the header. The sign information is in the high end of the last element.

40.12 Code Data-Blocks

A code data-block is the run-time representation of a “component”. A component is a connected portion of a program’s flow graph that is compiled as a single unit, and it contains code for many functions. Some of these functions are callable from outside of the component, and these are termed “entry points”.

Each entry point has an associated user-visible function data-block (of type function). The full call convention provides for calling an entry point specified by a function object.

Although all of the function data-blocks for a component’s entry points appear to the user as distinct objects, the system keeps all of the code in a single code data-block. The user-visible function object is actually a pointer into the middle of a code data-block. This allows any control transfer within a component to be done using a relative branch.

Besides a function object, there are other kinds of references into the middle of a code data-block. Control transfer into a function also occurs at the return-PC for a call. The system represents a return-PC somewhat similarly to a function, so GC can also recognize a return-PC as a reference to a code data-block. This representation is known as a Lisp Return Address (LRA).

It is incorrect to think of a code data-block as a concatenation of “function data-blocks”. Code for a function is not emitted in any particular order with respect to that function’s function-header (if any). The code following a function-header may only be a branch to some other location where the function’s “real” definition is.

The following are the three kinds of pointers to code data-blocks:

Code pointer (labeled A below):

A code pointer is a descriptor, with other-pointer low-tag bits, pointing to the beginning of the code data-block. The code pointer for the currently running function is always kept in a register (CODE). In addition to allowing loading of non-immediate constants, this also serves to represent the currently running function to the debugger.

LRA (labeled B below):

The LRA is a descriptor, with other-pointer low-tag bits, pointing to a location for a function call. Note that this location contains no descriptors other than the one word of immediate data, so GC can treat LRA locations the same as instructions.

Function (labeled C below):

A function is a descriptor, with function low-tag bits, that is user callable. When a function header is referenced from a closure or from the function header’s self-pointer, the pointer has other-pointer low-tag bits, instead of function low-tag bits. This ensures that the internal function data-block associated with a closure appears to be uncallable (although users should never see such an object anyway).

Information about functions that is only useful for entry points is kept in some descriptors following the function’s self-pointer descriptor. All of these together with the function’s header-word are known as the “function header”. GC must be able to locate the function header. We provide for this by chaining together the function headers in a NIL terminated list kept in a known slot in the code data-block.

A code data-block has the following format:

A -->
****************************************************************
|  Header-Word count (24 bits)    |   Code-Type (8 bits)       |
----------------------------------------------------------------
|  Number of code words (fixnum tag)                           |
----------------------------------------------------------------
|  Pointer to first function header (other-pointer tag)        |
----------------------------------------------------------------
|  Debug information (structure tag)                           |
----------------------------------------------------------------
|  First constant (a descriptor)                               |
----------------------------------------------------------------
|  ...                                                         |
----------------------------------------------------------------
|  Last constant (and last word of code header)                |
----------------------------------------------------------------
|  Some instructions (non-descriptor)                          |
----------------------------------------------------------------
|     (pad to dual-word boundary if necessary)                 |

B -->
****************************************************************
|  Word offset from code header (24)   |   Return-PC-Type (8)  |
----------------------------------------------------------------
|  First instruction after return                              |
----------------------------------------------------------------
|  ... more code and LRA header-words                          |
----------------------------------------------------------------
|     (pad to dual-word boundary if necessary)                 |

C -->
****************************************************************
|  Offset from code header (24)  |   Function-Header-Type (8)  |
----------------------------------------------------------------
|  x86/amd64/sparc: Address of start of instructions for       |
|  function (non-descriptor)                                   |
|  other architectures:                                        |
|  Self-pointer back to previous word (with other-pointer tag) |
----------------------------------------------------------------
|  Pointer to next function (other-pointer low-tag) or NIL     |
----------------------------------------------------------------
|  Function name (a string or a symbol)                        |
----------------------------------------------------------------
|  Function debug arglist (a string)                           |
----------------------------------------------------------------
|  Function type (a list-style function type specifier)        |
----------------------------------------------------------------
|  Start of instructions for function (non-descriptor)         |
----------------------------------------------------------------
|  More function headers and instructions and return PCs,      |
|  until we reach the total size of header-words + code        |
|  words.                                                      |
----------------------------------------------------------------

The following are detailed slot descriptions:

Code data-block header-word:

The immediate data in the code data-block’s header-word is the number of leading descriptors in the code data-block, the fixed overhead words plus the number of constants. The first non-descriptor word, some code, appears at this word offset from the header.

Number of code words:

The total number of non-header-words in the code data-block. The total word size of the code data-block is the sum of this slot and the immediate header-word data of the previous slot. header-word.

Pointer to first function header:

A NIL-terminated list of the function headers for all entry points to this component.

Debug information:

The DEBUG-INFO structure describing this component. All information that the debugger wants to get from a running function is kept in this structure. Since there are many functions, the current PC is used to locate the appropriate debug information. The system keeps the debug information separate from the function data-block, since the currently running function may not be an entry point. There is no way to recover the function object for the currently running function, since this data-block may not exist.

First constant ... last constant:

These are the constants referenced by the component, if there are any.

LRA header word:

The immediate header-word data is the word offset from the enclosing code data-block’s header-word to this word. This allows GC and the debugger to easily recover the code data-block from an LRA. The code at the return point restores the current code pointer using a subtract immediate of the offset, which is known at compile time.

Function entry point header-word:

The immediate header-word data is the word offset from the enclosing code data-block’s header-word to this word. This is the same as for the return-PC header-word.

Address of start of instructions for function:

This is implemented on x86, amd64, and sparc only. In a non-closure function, this address allows the call sequence to always indirect through the second word in a user callable function. See section “Closure Format”. With a closure, indirecting through the second word also gets you the start of instructions of a function. This pointer is a raw address, not a descriptor.

Self-pointer back to header-word:

In a non-closure function, this self-pointer to the previous header-word allows the call sequence to always indirect through the second word in a user callable function. See section “Closure Format”. With a closure, indirecting through the second word gets you a function header-word. The system ignores this slot in the function header for a closure, since it has already indirected once, and this slot could be some random thing that causes an error if you jump to it. This pointer has an other-pointer tag instead of a function pointer tag, indicating it is not a user callable Lisp object.

Pointer to next function:

This is the next link in the thread of entry point functions found in this component. This value is NIL when the current header is the last entry point in the component.

Function name:

This function’s name (for printing). If the user defined this function with DEFUN, then this is the defined symbol, otherwise it is a descriptive string.

Function debug arglist:

A printed string representing the function’s argument list, for human readability. If it is a macroexpansion function, then this is the original DEFMACRO arglist, not the actual expander function arglist.

Function type:

A list-style function type specifier representing the argument signature and return types for this function. For example,

(function (fixnum fixnum fixnum) fixnum)

or

(function (string &key (:start unsigned-byte)) string)

This information is intended for machine readablilty, such as by the compiler.

40.13 Closure Format

A closure data-block has the following format:

----------------------------------------------------------------
|  Word size (24 bits)           |  Closure-Type (8 bits)      |
----------------------------------------------------------------
|  Pointer to function header (other-pointer low-tag)          |
----------------------------------------------------------------
|                                 .                            |
|                      Environment information                 |
|                                 .                            |
----------------------------------------------------------------

A closure descriptor has function low-tag bits. This means that a descriptor with function low-tag bits may point to either a function header or to a closure. The idea is that any callable Lisp object has function low-tag bits. Insofar as call is concerned, we make the format of closures and non-closure functions compatible. This is the reason for the self-pointer in a function header. Whenever you have a callable object, you just jump through the second word, offset some bytes, and go.

40.14 Function call

Due to alignment requirements and low-tag codes, it is not possible to use a hardware call instruction to compute the LRA. Instead the LRA for a call is computed by doing an add-immediate to the start of the code data-block.

An advantage of using a single data-block to represent both the descriptor and non-descriptor parts of a function is that both can be represented by a single pointer. This reduces the number of memory accesses that have to be done in a full call. For example, since the constant pool is implicit in an LRA, a call need only save the LRA, rather than saving both the return PC and the constant pool.

40.15 Memory Layout

CMUCL has four spaces, read-only, static, dynamic-0, and dynamic-1. Read-only contains objects that the system never modifies, moves, or reclaims. Static space contains some global objects necessary for the system’s runtime or performance (since they are located at a known offset at a known address), and the system never moves or reclaims these. However, GC does need to scan static space for references to moved objects. Dynamic-0 and dynamic-1 are the two heap areas for stop-and-copy GC algorithms.

What global objects are at the head of static space???

   NIL
   eval::*top-of-stack*
   lisp::*current-catch-block*
   lisp::*current-unwind-protect*
   FLAGS (RT only)
   BSP (RT only)
   HEAP (RT only)

In addition to the above spaces, the system has a control stack, binding stack, and a number stack. The binding stack contains pairs of descriptors, a symbol and its previous value. The number stack is the same as the C stack, and the system uses it for non-Lisp objects such as raw system pointers, saving non-Lisp registers, parts of bignum computations, etc.

40.16 System Pointers

The system pointers reference raw allocated memory, data returned by foreign function calls, etc. The system uses these when you need a pointer to a non-Lisp block of memory, using an other-pointer. This provides the greatest flexibility by relieving contraints placed by having more direct references that require descriptor type tags.

A system area pointer data-block has the following format:

-------------------------------------------------------
|     1 (data-block words)        | SAP Type (8 bits) |
-------------------------------------------------------
|             system area pointer                     |
-------------------------------------------------------

“SAP” means “system area pointer”, and much of our code contains this naming scheme. We don’t currently restrict system pointers to one area of memory, but if they do point onto the heap, it is up to the user to prevent being screwed by GC or whatever.

40.17 Weak Pointers

A weak-pointer data-block has the following format:

-------------------------------------------------------
|  4 (data-block words) |  Weak pointer Type (8 bits) |
-------------------------------------------------------
|                 weak-pointer-value                  |
-------------------------------------------------------
|                 weak-pointer-broken                 |
-------------------------------------------------------
|                 mark-bit (T or NIL)                 |
-------------------------------------------------------
|                   next                              |
-------------------------------------------------------

The mark-bit is used when gencgc is available. It’s used to note if this weak pointer has been visited before so that scavenging weak-pointers isn’t an $O(n^2)$ process.

The last slot is an internal slot used by the C runtime to chain all the weak pointers together for GC.

41.1 Stacks and Globals

41.2 Heap Layout

41.3 Garbage Collection

42.1 Linkage Table

The linkage table feature is based on how dynamic libraries dispatch. A table of functions is used which is filled in with the appropriate code to jump to the correct address.

For CMUCL, this table is stored at target-foreign-linkage-space-start. Each entry is target-foreign-linkage-entry-size bytes long.

At startup, the table is initialized with default values in os_foreign_linkage_init. On x86 platforms, the first entry is code to call the routine resolve_linkage_tramp. All other entries jump to the first entry. The function resolve_linkage_tramp looks at where it was called from to figure out which entry in the table was used. It calls lazy_resolve_linkage with the address of the linkage entry. This routine then fills in the appropriate linkage entry with code to jump to where the real routine is located, and returns the address of the entry. On return, resolve_linkage_tramp then just jumps to the returned address to call the desired function. On all subsequent calls, the entry no longer points to resolve_linkage_tramp but to the real function.

This describes how function calls are made. For foreign data, lazy_resolve_linkage stuffs the address of the actual foreign data into the linkage table. The lisp code then just loads the address from there to get the actual address of the foreign data.

For sparc, the linkage table is slightly different. The first entry is the entry for call_into_c so we never have to look this up. All other entries are for resolve_linkage_tramp. This has the advantage that resolve_linkage_tramp can be much simpler since all calls to foreign code go through call_into_c anyway, and that means all live Lisp registers have already been saved. Also, to make life simpler, we lie about closure_tramp and undefined_tramp in the Lisp code. These are really functions, but we treat them as foreign data since these two routines are only used as addresses in the Lisp code to stuff into a lisp function header.

On the Lisp side, there are two supporting data structures for the linkage table: *linkage-table-data* and *foreign-linkage-symbols*. The latter is a hash table whose key is the foreign symbol (a string) and whose value is an index into *linkage-table-data*.

*linkage-table-data* is a vector with an unlispy layout. Each entry has 3 parts:

• symbol name
• type, a fixnum, 1 = code, 2 = data
• library list - the library list at the time the symbol is registered.

Whenever a new foreign symbol is defined, a new *linkage-table-data* entry is created. *foreign-linkage-symbols* is updated with the symbol and the entry number into *linkage-table-data*.

The *linkage-table-data* is accessed from C (hence the unlispy layout), to figure out the symbol name and the type so that the address of the symbol can be determined. The type tells the C code how to fill in the entry in the linkage-table itself.

45.1 General

The purpose of Fasload files is to allow concise storage and rapid loading of Lisp data, particularly function definitions. The intent is that loading a Fasload file has the same effect as loading the source file from which the Fasload file was compiled, but accomplishes the tasks more efficiently. One noticeable difference, of course, is that function definitions may be in compiled form rather than S-expression form. Another is that Fasload files may specify in what parts of memory the Lisp data should be allocated. For example, constant lists used by compiled code may be regarded as read-only.

In some Lisp implementations, Fasload file formats are designed to allow sharing of code parts of the file, possibly by direct mapping of pages of the file into the address space of a process. This technique produces great performance improvements in a paged time-sharing system. Since the Mach project is to produce a distributed personal-computer network system rather than a time-sharing system, efficiencies of this type are explicitly not a goal for the CMU Common Lisp Fasload file format.

On the other hand, CMU Common Lisp is intended to be portable, as it will eventually run on a variety of machines. Therefore an explicit goal is that Fasload files shall be transportable among various implementations, to permit efficient distribution of programs in compiled form. The representations of data objects in Fasload files shall be relatively independent of such considerations as word length, number of type bits, and so on. If two implementations interpret the same macrocode (compiled code format), then Fasload files should be completely compatible. If they do not, then files not containing compiled code (so-called “Fasdump” data files) should still be compatible. While this may lead to a format which is not maximally efficient for a particular implementation, the sacrifice of a small amount of performance is deemed a worthwhile price to pay to achieve portability.

The primary assumption about data format compatibility is that all implementations can support I/O on finite streams of eight-bit bytes. By “finite” we mean that a definite end-of-file point can be detected irrespective of the content of the data stream. A Fasload file will be regarded as such a byte stream.

45.2 Strategy

A Fasload file may be regarded as a human-readable prefix followed by code in a funny little language. When interpreted, this code will cause the construction of the encoded data structures. The virtual machine which interprets this code has a stack and a table, both initially empty. The table may be thought of as an expandable register file; it is used to remember quantities which are needed more than once. The elements of both the stack and the table are Lisp data objects. Operators of the funny language may take as operands following bytes of the data stream, or items popped from the stack. Results may be pushed back onto the stack or pushed onto the table. The table is an indexable stack that is never popped; it is indexed relative to the base, not the top, so that an item once pushed always has the same index.

More precisely, a Fasload file has the following macroscopic organization. It is a sequence of zero or more groups concatenated together. End-of-file must occur at the end of the last group. Each group begins with a series of seven-bit ASCII characters terminated by one or more bytes of all ones #xFF; this is called the header. Following the bytes which terminate the header is the body, a stream of bytes in the funny binary language. The body of necessity begins with a byte other than #xFF. The body is terminated by the operation FOP-END-GROUP.

The first nine characters of the header must be FASL FILE in upper-case letters. The rest may be any ASCII text, but by convention it is formatted in a certain way. The header is divided into lines, which are grouped into paragraphs. A paragraph begins with a line which does not begin with a space or tab character, and contains all lines up to, but not including, the next such line. The first word of a paragraph, defined to be all characters up to but not including the first space, tab, or end-of-line character, is the name of the paragraph. A Fasload file header might look something like this:

FASL FILE >SteelesPerq>User>Guy>IoHacks>Pretty-Print.Slisp
Package Pretty-Print
Compiled 31-Mar-1988 09:01:32 by some random luser
Compiler Version 1.6, Lisp Version 3.0.
Functions: INITIALIZE DRIVER HACK HACK1 MUNGE MUNGE1 GAZORCH
	   MINGLE MUDDLE PERTURB OVERDRIVE GOBBLE-KEYBOARD
	   FRY-USER DROP-DEAD HELP CLEAR-MICROCODE
	    %AOS-TRIANGLE %HARASS-READTABLE-MAYBE
Macros:    PUSH POP FROB TWIDDLE

one or more bytes of #xFF.

The particular paragraph names and contents shown here are only intended as suggestions.

45.3 Fasload Language

Each operation in the binary Fasload language is an eight-bit (one-byte) opcode. Each has a name beginning with “FOP-”. In the following descriptions, the name is followed by operand descriptors. Each descriptor denotes operands that follow the opcode in the input stream. A quantity in parentheses indicates the number of bytes of data from the stream making up the operand. Operands which implicitly come from the stack are noted in the text. The notation “⇒ stack” means that the result is pushed onto the stack; “⇒ table” similarly means that the result is added to the table. A construction like “n(1) value(n)” means that first a single byte n is read from the input stream, and this byte specifies how many bytes to read as the operand named value. All numeric values are unsigned binary integers unless otherwise specified. Values described as “signed” are in two’s-complement form unless otherwise specified. When an integer read from the stream occupies more than one byte, the first byte read is the least significant byte, and the last byte read is the most significant (and contains the sign bit as its high-order bit if the entire integer is signed).

Some of the operations are not necessary, but are rather special cases of or combinations of others. These are included to reduce the size of the file or to speed up important cases. As an example, nearly all strings are less than 256 bytes long, and so a special form of string operation might take a one-byte length rather than a four-byte length. As another example, some implementations may choose to store bits in an array in a left-to-right format within each word, rather than right-to-left. The Fasload file format may support both formats, with one being significantly more efficient than the other for a given implementation. The compiler for any implementation may generate the more efficient form for that implementation, and yet compatibility can be maintained by requiring all implementations to support both formats in Fasload files.

Measurements are to be made to determine which operation codes are worthwhile; little-used operations may be discarded and new ones added. After a point the definition will be “frozen”, meaning that existing operations may not be deleted (though new ones may be added; some operations codes will be reserved for that purpose).

0: FOP-NOP

No operation. (This is included because it is recognized that some implementations may benefit from alignment of operands to some operations, for example to 32-bit boundaries. This operation can be used to pad the instruction stream to a desired boundary.)

1: FOP-POP ⇒ table

One item is popped from the stack and added to the table.

2: FOP-PUSH index(4) ⇒ stack

Item number index of the table is pushed onto the stack. The first element of the table is item number zero.

3: FOP-BYTE-PUSH index(1) ⇒ stack

Item number index of the table is pushed onto the stack. The first element of the table is item number zero.

4: FOP-EMPTY-LIST ⇒ stack

The empty list (()) is pushed onto the stack.

5: FOP-TRUTH ⇒ stack

The standard truth value (T) is pushed onto the stack.

6: FOP-SYMBOL-SAVE n(4) name(n)

⇒ stack & table The four-byte operand n specifies the length of the print name of a symbol. The name follows, one character per byte, with the first byte of the print name being the first read. The name is interned in the default package, and the resulting symbol is both pushed onto the stack and added to the table.

7: FOP-SMALL-SYMBOL-SAVE n(1) name(n) ⇒ stack & table

The one-byte operand n specifies the length of the print name of a symbol. The name follows, one character per byte, with the first byte of the print name being the first read. The name is interned in the default package, and the resulting symbol is both pushed onto the stack and added to the table.

8: FOP-SYMBOL-IN-PACKAGE-SAVE index(4)

n(4) name(n) ⇒ stack & table The four-byte index specifies a package stored in the table. The four-byte operand n specifies the length of the print name of a symbol. The name follows, one character per byte, with the first byte of the print name being the first read. The name is interned in the specified package, and the resulting symbol is both pushed onto the stack and added to the table.

9: FOP-SMALL-SYMBOL-IN-PACKAGE-SAVE index(4)

n(1) name(n) ⇒ stack & table The four-byte index specifies a package stored in the table. The one-byte operand n specifies the length of the print name of a symbol. The name follows, one character per byte, with the first byte of the print name being the first read. The name is interned in the specified package, and the resulting symbol is both pushed onto the stack and added to the table.

10: FOP-SYMBOL-IN-BYTE-PACKAGE-SAVE index(1)

n(4) name(n) ⇒ stack & table The one-byte index specifies a package stored in the table. The four-byte operand n specifies the length of the print name of a symbol. The name follows, one character per byte, with the first byte of the print name being the first read. The name is interned in the specified package, and the resulting symbol is both pushed onto the stack and added to the table.

11: FOP-SMALL-SYMBOL-IN-BYTE-PACKAGE-SAVE index(1) n(1) name(n) ⇒ stack & table

The one-byte index specifies a package stored in the table. The one-byte operand n specifies the length of the print name of a symbol. The name follows, one character per byte, with the first byte of the print name being the first read. The name is interned in the specified package, and the resulting symbol is both pushed onto the stack and added to the table.

12: FOP-UNINTERNED-SYMBOL-SAVE n(4) name(n) ⇒ stack & table

Like FOP-SYMBOL-SAVE, except that it creates an uninterned symbol.

13: FOP-UNINTERNED-SMALL-SYMBOL-SAVE n(1) name(n) ⇒ stack & table

Like FOP-SMALL-SYMBOL-SAVE, except that it creates an uninterned symbol.

14: FOP-PACKAGE ⇒ table

An item is popped from the stack; it must be a symbol. The package of that name is located and pushed onto the table.

15: FOP-LIST length(1) ⇒ stack

The unsigned operand length specifies a number of operands to be popped from the stack. These are made into a list of that length, and the list is pushed onto the stack. The first item popped from the stack becomes the last element of the list, and so on. Hence an iterative loop can start with the empty list and perform “pop an item and cons it onto the list” length times. (Lists of length greater than 255 can be made by using FOP-LIST* repeatedly.)

16: FOP-LIST* length(1) ⇒ stack

This is like FOP-LIST except that the constructed list is terminated not by () (the empty list), but by an item popped from the stack before any others are. Therefore length+1 items are popped in all. Hence an iterative loop can start with a popped item and perform “pop an item and cons it onto the list” length+1 times.

17-24: FOP-LIST-1, FOP-LIST-2, ..., FOP-LIST-8

FOP-LIST-k is like FOP-LIST with a byte containing k following it. These exist purely to reduce the size of Fasload files. Measurements need to be made to determine the useful values of k.

25-32: FOP-LIST*-1, FOP-LIST*-2, ..., FOP-LIST*-8

FOP-LIST*-k is like FOP-LIST* with a byte containing k following it. These exist purely to reduce the size of Fasload files. Measurements need to be made to determine the useful values of k.

33: FOP-INTEGER n(4) value(n)

⇒ stack A four-byte unsigned operand specifies the number of following bytes. These bytes define the value of a signed integer in two’s-complement form. The first byte of the value is the least significant byte.

34: FOP-SMALL-INTEGER n(1) value(n)

⇒ stack A one-byte unsigned operand specifies the number of following bytes. These bytes define the value of a signed integer in two’s-complement form. The first byte of the value is the least significant byte.

35: FOP-WORD-INTEGER value(4) ⇒ stack

A four-byte signed integer (in the range -2^{31} to 2^{31}-1) follows the operation code. A LISP integer (fixnum or bignum) with that value is constructed and pushed onto the stack.

36: FOP-BYTE-INTEGER value(1) ⇒ stack

A one-byte signed integer (in the range -128 to 127) follows the operation code. A LISP integer (fixnum or bignum) with that value is constructed and pushed onto the stack.

37: FOP-STRING n(4) name(n)

⇒ stack The four-byte operand n specifies the length of a string to construct. The characters of the string follow, one per byte. The constructed string is pushed onto the stack.

38: FOP-SMALL-STRING n(1) name(n) ⇒ stack

The one-byte operand n specifies the length of a string to construct. The characters of the string follow, one per byte. The constructed string is pushed onto the stack.

39: FOP-VECTOR n(4) ⇒ stack

The four-byte operand n specifies the length of a vector of LISP objects to construct. The elements of the vector are popped off the stack; the first one popped becomes the last element of the vector. The constructed vector is pushed onto the stack.

40: FOP-SMALL-VECTOR n(1) ⇒ stack

The one-byte operand n specifies the length of a vector of LISP objects to construct. The elements of the vector are popped off the stack; the first one popped becomes the last element of the vector. The constructed vector is pushed onto the stack.

41: FOP-UNIFORM-VECTOR n(4) ⇒ stack

The four-byte operand n specifies the length of a vector of LISP objects to construct. A single item is popped from the stack and used to initialize all elements of the vector. The constructed vector is pushed onto the stack.

42: FOP-SMALL-UNIFORM-VECTOR n(1) ⇒ stack

The one-byte operand n specifies the length of a vector of LISP objects to construct. A single item is popped from the stack and used to initialize all elements of the vector. The constructed vector is pushed onto the stack.

43: FOP-INT-VECTOR len(4) size(1) data(\left\lceil len*count/8\right\rceil ⇒ stack

The four-byte operand n specifies the length of a vector of unsigned integers to be constructed. Each integer is size bits long, and is packed according to the machine’s native byte ordering. size must be a directly supported i-vector element size. Currently supported values are 1,2,4,8,16 and 32.

44: FOP-UNIFORM-INT-VECTOR n(4) size(1) value(\lceil size/8\rceil) ⇒ stack

The four-byte operand n specifies the length of a vector of unsigned integers to construct. Each integer is size bits big, and is initialized to the value of the operand value. The constructed vector is pushed onto the stack.

45: FOP-LAYOUT

Pops the stack four times to get the name, length, inheritance and depth for a layout object.

46: FOP-SINGLE-FLOAT data(4)

⇒ stack The data bytes are read as an integer, then turned into an IEEE single float (as though by make-single-float).

47: FOP-DOUBLE-FLOAT data(8)

⇒ stack The data bytes are read as an integer, then turned into an IEEE double float (as though by make-double-float).

48: FOP-STRUCT n(4) ⇒ stack

The four-byte operand n specifies the length structure to construct. The elements of the vector are popped off the stack; the first one popped becomes the last element of the structure. The constructed vector is pushed onto the stack.

49: FOP-SMALL-STRUCT n(1) ⇒ stack

The one-byte operand n specifies the length structure to construct. The elements of the vector are popped off the stack; the first one popped becomes the last element of the structure. The constructed vector is pushed onto the stack.

50-52: Unused

53: FOP-EVAL ⇒ stack

Pop an item from the stack and evaluate it (give it to EVAL). Push the result back onto the stack.

54: FOP-EVAL-FOR-EFFECT

Pop an item from the stack and evaluate it (give it to EVAL). The result is ignored.

55: FOP-FUNCALL nargs(1) ⇒ stack

Pop nargs+1 items from the stack and apply the last one popped as a function to all the rest as arguments (the first one popped being the last argument). Push the result back onto the stack.

56: FOP-FUNCALL-FOR-EFFECT nargs(1)

Pop nargs+1 items from the stack and apply the last one popped as a function to all the rest as arguments (the first one popped being the last argument). The result is ignored.

57: FOP-CODE-FORMAT implementation(1)

version(1) This FOP specifiers the code format for following code objects. The operations FOP-CODE and its relatives may not occur in a group until after FOP-CODE-FORMAT has appeared; there is no default format. The implementation is an integer indicating the target hardware and environment. See compiler/generic/vm-macs.lisp for the currently defined implementations. version for an implementation is increased whenever there is a change that renders old fasl files unusable.

58: FOP-CODE nitems(4) size(4)

code(size) ⇒ stack A compiled function is constructed and pushed onto the stack. This object is in the format specified by the most recent occurrence of FOP-CODE-FORMAT. The operand nitems specifies a number of items to pop off the stack to use in the “boxed storage” section. The operand code is a string of bytes constituting the compiled executable code.

59: FOP-SMALL-CODE nitems(1) size(2)

code(size) ⇒ stack A compiled function is constructed and pushed onto the stack. This object is in the format specified by the most recent occurrence of FOP-CODE-FORMAT. The operand nitems specifies a number of items to pop off the stack to use in the “boxed storage” section. The operand code is a string of bytes constituting the compiled executable code.

60 FOP-FDEFINITION

Pops the stack to get an fdefinition.

61 FOP-SANCTIFY-FOR-EXECUTION

A code component is popped from the stack, and the necessary magic is applied to the code so that it can be executed.

62: FOP-VERIFY-TABLE-SIZE size(4)

If the current size of the table is not equal to size, then an inconsistency has been detected. This operation is inserted into a Fasload file purely for error-checking purposes. It is good practice for a compiler to output this at least at the end of every group, if not more often.

63: FOP-VERIFY-EMPTY-STACK

If the stack is not currently empty, then an inconsistency has been detected. This operation is inserted into a Fasload file purely for error-checking purposes. It is good practice for a compiler to output this at least at the end of every group, if not more often.

64: FOP-END-GROUP

This is the last operation of a group. If this is not the last byte of the file, then a new group follows; the next nine bytes must be “FASL FILE”.

65: FOP-POP-FOR-EFFECT stack ⇒

One item is popped from the stack.

66: FOP-MISC-TRAP ⇒ stack

A trap object is pushed onto the stack.

67: FOP-DOUBLE-DOUBLE-FLOAT double-double-float(8) ⇒ stack

The next 8 bytes are read, and a double-double-float number is constructed.

68: FOP-CHARACTER character(3) ⇒ stack

The three bytes are read as an integer then converted to a character. This FOP is currently rather useless, as extended characters are not supported.

69: FOP-SHORT-CHARACTER character(1)

⇒ stack The one byte specifies the code of a Common Lisp character object. A character is constructed and pushed onto the stack.

70: FOP-RATIO ⇒ stack

Creates a ratio from two integers popped from the stack. The denominator is popped first, the numerator second.

71: FOP-COMPLEX ⇒ stack

Creates a complex number from two numbers popped from the stack. The imaginary part is popped first, the real part second.

72 FOP-COMPLEX-SINGLE-FLOAT real(4) imag(4) ⇒ stack

Creates a complex single-float number from the following 8 bytes.

73 FOP-COMPLEX-DOUBLE-FLOAT real(8) imag(8) ⇒ stack

Creates a complex double-float number from the following 16 bytes.

74: FOP-FSET

Except in the cold loader (Genesis), this is a no-op with two stack arguments. In the initial core this is used to make DEFUN functions defined at cold-load time so that global functions can be called before top-level forms are run (which normally installs definitions.) Genesis pops the top two things off of the stack and effectively does (SETF SYMBOL-FUNCTION).

75: FOP-LISP-SYMBOL-SAVE n(4) name(n)

⇒ stack & table Like FOP-SYMBOL-SAVE, except that it creates a symbol in the LISP package.

76: FOP-LISP-SMALL-SYMBOL-SAVE n(1)

name(n) ⇒ stack & table Like FOP-SMALL-SYMBOL-SAVE, except that it creates a symbol in the LISP package.

77: FOP-KEYWORD-SYMBOL-SAVE n(4) name(n)

⇒ stack & table Like FOP-SYMBOL-SAVE, except that it creates a symbol in the KEYWORD package.

78: FOP-KEYWORD-SMALL-SYMBOL-SAVE n(1)

name(n) ⇒ stack & table Like FOP-SMALL-SYMBOL-SAVE, except that it creates a symbol in the KEYWORD package.

79-80: Unused

81: FOP-NORMAL-LOAD

This FOP is used in conjunction with the cold loader (Genesis) to read top-level package manipulation forms. These forms are to be read as though by the normal loaded, so that they can be evaluated at cold load time, instead of being dumped into the initial core image. A no-op in normal loading.

82: FOP-MAYBE-COLD-LOAD

Undoes the effect of FOP-NORMAL-LOAD.

83: FOP-ARRAY rank(4) ⇒ stack

This operation creates a simple array header (used for simple-arrays with rank /= 1). The data vector is popped off of the stack, and then rank dimensions are popped off of the stack (the highest dimensions is on top.)

84: FOP-SINGLE-FLOAT-VECTOR length(4) data(n) ⇒ stack

Creates a (simple-array single-float (*)) object. The number of single-floats is length.

85: FOP-DOUBLE-FLOAT-VECTOR length(4) data(n) ⇒ stack

Creates a (simple-array double-float (*)) object. The number of double-floats is length.

86: FOP-COMPLEX-SINGLE-FLOAT-VECTOR length(4) data(n) ⇒ stack

Creates a (simple-array (complex single-float) (*)) object. The number of complex single-floats is length.

87: FOP-COMPLEX-DOUBLE-FLOAT-VECTOR length(4) data(n) ⇒ stack

Creates a (simple-array (complex double-float) (*)) object. The number of complex double-floats is length.

88: FOP-DOUBLE-DOUBLE-FLOAT-VECTOR length(4) data(n) ⇒ stack

Creates a (simple-array double-double-float (*)) object. The number of double-double-floats is length.

89: FOP-COMPLEX-DOUBLE-DOUBLE-FLOAT data(32) ⇒ stack

Creates a (complex double-double-float) object from the following 32 bytes of data.

90: FOP-COMPLEX-DOUBLE-DOUBLE-FLOAT-VECTOR length(4) data(n) ⇒ stack

Creates a (simple-arra (complex double-double-float) (*)) object. The number of complex double-double-floats is length.

91-139: Unused

140: FOP-ALTER-CODE index(4)

This operation modifies the constants part of a code object (necessary for creating certain circular function references.) It pops the new value and code object are off of the stack, storing the new value at the specified index.

141: FOP-BYTE-ALTER-CODE index(1)

Like FOP-ALTER-CODE, but has only a one byte offset.

142: FOP-FUNCTION-ENTRY index(4) ⇒ stack

Initializes a function-entry header inside of a pre-existing code object, and returns the corresponding function descriptor. index is the byte offset inside of the code object where the header should be plunked down. The stack arguments to this operation are the code object, function name, function debug arglist and function type.

143: FOP-MAKE-BYTE-COMPILED-FUNCTION size(1) ⇒ stack

Create a byte-compiled function. FIXME: describe what’s on the stack.

144: FOP-ASSEMBLER-CODE length(4) ⇒ stack

This operation creates a code object holding assembly routines. length bytes of code are read and placed in the code object, and the code object descriptor is pushed on the stack. This FOP is only recognized by the cold loader (Genesis.)

145: FOP-ASSEMBLER-ROUTINE offset(4) ⇒ stack

This operation records an entry point into an assembler code object (for use with FOP-ASSEMBLER-FIXUP). The routine name (a symbol) is on stack top. The code object is underneath. The entry point is defined at offset bytes inside the code area of the code object, and the code object is left on stack top (allowing multiple uses of this FOP to be chained.) This FOP is only recognized by the cold loader (Genesis.)

146: Unused

147: FOP-FOREIGN-FIXUP len(1) name(len) offset(4) ⇒ stack

This operation resolves a reference to a foreign (C) symbol. len bytes are read and interpreted as the symbol name. First the kind and the code-object to patch are popped from the stack. The kind is a target-dependent symbol indicating the instruction format of the patch target (at offset bytes from the start of the code area.) The code object is left on stack top (allowing multiple uses of this FOP to be chained.)

148: FOP-ASSEMBLER-FIXUP offset(4) ⇒ stack

This operation resolves a reference to an assembler routine. The stack args are (routine-name, kind and code-object). The kind is a target-dependent symbol indicating the instruction format of the patch target (at offset bytes from the start of the code area.) The code object is left on stack top (allowing multiple uses of this FOP to be chained.)

149: FOP-CODE-OBJECT-FIXUP ⇒ stack

FIXME: Describe what this does!

150: FOP-FOREIGN-DATA-FIXUP ⇒ stack

FIXME: Describe what this does!

151-156: Unused

157: FOP-LONG-CODE-FORMAT implementation(1) version(4)

Like FOP-CODE-FORMAT, except that the version is 32 bits long.

158-199: Unused

200: FOP-RPLACA table-idx(4) cdr-offset(4)

201: FOP-RPLACD table-idx(4) cdr-offset(4)

These operations destructively modify a list entered in the table. table-idx is the table entry holding the list, and cdr-offset designates the cons in the list to modify (like the argument to nthcdr.) The new value is popped off of the stack, and stored in the car or cdr, respectively.

202: FOP-SVSET table-idx(4) vector-idx(4)

Destructively modifies a simple-vector entered in the table. Pops the new value off of the stack, and stores it in the vector-idx element of the contents of the table entry table-idx.

203: FOP-NTHCDR cdr-offset(4) ⇒ stack

Does nthcdr on the top-of stack, leaving the result there.

204: FOP-STRUCTSET table-idx(4) vector-idx(4)

Like FOP-SVSET, except it alters structure slots.

205-254: Unused

255: FOP-END-HEADER

Indicates the end of a group header, as described above.