``Nothing will ever be attempted, if all possible objections must first be overcome.''  Samuel Johnson

Some history

We are pulled in many directions, including:

        [...]
        A high performance VM

This last is one for which we have a lot of enthusiasm, as well as a fair
amount of experience, but we simply don't have enough cycles to keep it on
our list.  Also, on the positive side, it is a project that could be done
quite independently, and then merged with mainline Squeak when it was done.
[...]
Beyond this, we have the sense that you might actually be interested in
working on such a project.

The first version was called ``Jitter'', which supposedly stood for: ``just-in-time transformation of executable representation''.  The idea was to generate threaded code, ... code inside image ... translator written in Slang ... run simulated or in generated code with platdep macros...

The second was called ``Jitter-2'', which soon became abbreviated to ``J2''.

The first two Jitters were not a complete waste of time.  Apart from the experience gained in the internals of the Squeak Interpreter and ObjectMemory, they contributed several important ideas both to the design of J3 and to the optimisations used in the regular bytecode Interpreter.  To cite just two examples: the prefetching of threaded opcodes in Jitter-1 was adopted in the Interpreter by moving the send of ``fetchNextBytecode'' out of the interpreter loop and into each of the bytecode implementations (placing it as early as possible in the method), and the idea of using a combination of the inline cache and method specialisation for indexable classes for sends of #at: and #at:put: in Jitter-2 (to eliminate overheads associated with decoding the format of the receiver on each send of #at: and #at:put:) led to the inclusion of the ``at cache'' in the Interpreter.

What's in a J3?

The major breakthroughs in understanding which led to J3 were therefore:

• threaded code is every bit as complicated to generate and maintain as is real native code, so why pretend?

• the context cache is every bit as complicated to manage as is the real hardware stack, so why pretend?

• complexity is exponentially proportional to the amount of state that has to be managed: keeping two sets of interpreter state in sync was much, much more complicated than simply ditching the least interesting of the two interpreters (the bytecoded one) and concentrating on simply making everything run in the other (optimising) interpreter.

All of this, I hope, is still thoroughly in keeping with the Squeak philosophy of portability, openness, and accessibility to everyone.  The code generator contains maybe a hundred lines of platform-specific code, and the runtime support routines (the ``glue'' that connects Smalltalk methods and primitives together, and the ``trampolines'' that connect C with Smalltalk code and kick-start the initial Process) represent no more than another hundred lines.  Porting J3 to a new processor (given a suitable runtime assembler -- but that's another story) should be the work of a few days, not weeks or months.

Architecture

The code generator

• a compilation loop which transforms bytecodes into a high-level abstract intermediate representation called ``SAM'';

 
• a linear optimiser that accepts a stream of SAM operations and converts them into an equivalent stream of low-level abstract NAM operations;

 
• a collection of platform-specific output routines which map NAM operations onto the native machine instructions of the host processor.

1. The encoding is optimised for space, not for ease of decoding.  A given operation can be implemented in several different bytecodes, each allowing a different range of parameters (selector indices in sends, argument counts, field indices in loads/stores, jump displacements, and so on).  This would not matter if it were merely a matter of converting bytecodes on an individual basis into native code.  Unfortunatey there are many situations in which good code can only be generated by looking at adjacent bytecodes.  An obvious example is translating

 
            push    X
            pop     Y


into a single native instruction
 

            move    X, Y


or into a pair of instructions
 

            load    register, X
            store   register, Y


on load-store machines.  (This is desirable because modern processors are essentially memory-bound, and halving the number of memory references will often double the execution speed of a given piece of code.)  In Smalltalk, decoding just the push-pop pairs involves all the possibile permutations of 4 sources and 3 destinations, and up to three different encodings of a given operation with a given source or destination.  Combinatorial explosion would soon force the translator to spend (waste) most of its time frantically trying to match patterns.
 

2. Conditional jump ranges are asymmetrical, which forces the majority of backward ``jump-if-true'' operations

 
priorLabel: ...
            ...
            jumpTrue:  priorLabel
            ...


to appear rewritten with inverted forward conditional branches
 

priorLabel: ...
            ...
            jumpFalse: tempLabel
            jumpTo:    priorLabel
tempLabel:  ...


in the bytecode.  This would add yet another bunch of expensive pattern matching to the generator.  What's more, jump chains are not uncommon.  The following (thoroughly amusing or highly depressing, depending on your disposition) example is from Object>>doesNotUnderstand:
 

33        receiver of #and:           33        receiver of #and:
34                                    34
35 <9B> jumpFalse: 40                 35      jumpFalse: 46
36                                    36
37        argument of #and:           37        argument of #and:
38                                    38
39 <90> jumpTo: 41                    39      jumpFalse: 46
40 <72> pushConstant: false           40        deleted
41 <9B> jumpFalse: 46                 41        deleted
42                                    42
43        consequent...               43        consequent...


(The original is on left, and the spaghetti-free version on the right.  Pedantics requires me to explain that the only path to the bytecode at 40 is from the jump at 35, and that the jump at 41 is only reached from the bytecode preceding it.)

Squeak Abstract Machine

Note that the Special operator could be removed if we made the selector explicit in message send, for example using LdLit to supply the selector to Super and Send, and using a LdSpecial operator to provided a selector from the SpecialSelectors Array, transforming any subsequent Send into the equivalent of the existing Special operator.  This would be a better solution because it is more general, allowing special selectors to be used in Super sends (for example) or as literal values in programs, without consuming literal frame slots.

Note also that many of the Smalltalk bytecodes are converted into two or more SAM operations, for example:

            popLiteralVariable: N

            LdLit: N
            StVal
            Pop
            Pop

32 of the Smalltalk bytecodes are ``pre-encoded'' sends of ``special'' selectors.  (The original pupose of these special sends was two-fold: first to allow a microcoded virtual machine (and later a software interpreter) to ``inline'' the evaluation of all sends of arithmetic messages having SmallInteger or Float receivers and arguments, without ever needing to send a real message; and second to reduce literal frame pressure due to frequently-used selectors.)  The Special send operation subsumes the 16 special send bytecodes which are therefore all converted into Special operations, with two exceptions. Class and Equivalent can never ``fail'' their inlined response and be converted into a full send; they are therefore retained as separate operations in SAM to simplify (slightly) the analysis that has to be done by the optimiser for the Special operation.  The 16 arithmetic operations are also retained for similar reasons.  (Athough they do not reduce the amount of analysis performed by the optimiser, they spread it out more evenly and help make the final artifact easier to understand and maintain.)
 

Jump rewriting

Jump rewriting is also important because the optimiser performs a limited form of dataflow analysis to track the types of the objects that will appear in the runtime stack.  Since, in general, the stack contents can only be tracked reliably during the execution of linear sequences of instructions, the type information must be recombined at each basic block entry point based on information propagated along each of the possible paths into the block.  Reducing the number of jumps in the code therefore also reduces the number of points at which the optimiser is forced to discard potentially valuable type information.

Optimisation

Having converted the bytecode into SAM, and then performed the initial jump rewriting, the compiler iterates over the SAM code and calls a ``generator'' function in the optimiser for each SAM opcode.  The optimiser implements a separate generator function for each of the SAM operations defined above.

Optimisation is based on a technique called delayed code generation (DCG) [Piu92], which has the interesting property that only one iteration over the intermediate form (or walk through a parse tree) is necessary to generate very high quality final code.  DCG works by manipulating an explicit representation of the machine operands representing quantities with which the program  reasons.  For example, in Smalltalk these quantities include literal constants, the receiver, temporary variables, and locations on the runtime stack.

Code generation is entirely operand-driven.  The optimiser's main job is to combine operands (that it has accumulated from previous operations) according to the operation implied by each of its generator functions.  The optimiser tries hard to combine operands without generating native code, and emits instructions only when such implicit combination becomes impossible.  In order to do this, some kind of state must be retained to propagate operands between successive generator functions.  In the case of Smalltalk, the most suitable structure in which to keep this state is a simulation stack, which models the contents of the runtime stack that will exist when the method is later executed.  An example should make all of this much clearer.  Consider the Smalltalk statement

        | a |
        a := 3 + 4.

                LdConst #3
                LdConst #4
                Add
                StTemp  0
                Pop

                moviT(#7, 0)

                movl    $15, 0(%(tempBaseReg))

                li      r9, 15
                stw     r9, 0(r(tempBaseReg))

In the case of the Pentium, the descriptor returned by move_i_t represents the constant #7; in the case of the PowerPC it represents the register r9.  Since the generator function replaces the descriptor on top of the simulation stack with the output operand descriptor returned by the output routine, instructions generated to move input operands to registers on load-store architctures are not repeated a second time if the same value is reused in a given statement.  Consequently, on the PowerPC, the statement

| a b |
a := b := 42.

                li      r9, 85                   ; input operand = #42
                stw     r9, 4(r(tempBaseReg))    ; output operand = r9
                stw     r9, 0(r(tempBaseReg))    ; input operand = r9

Contexts

Speed goes up because a significant amount the CPU time in the bytecode Interpreter goes into activating and returning from methods.  The benchFibs benchmark, running fully optimised native code, is approximately ten times slower when executing in heap Contexts compared to executing directly on the hardware stack.  On the Pentium, the shortest possible path through activateNewMethod executes 83 instructions.  The same activation on the hardware stack requires [VERIFY THIS] 7 instructions.  A similar bottleneck exists with returns, which execute 44 Pentium instructions in the best case for heap-allocated Contexts and only [VERIFY THIS] 4 when executing on the stack.

The price to be paid is additional complexity elsewhere in the system.  Heap-allocated Contexts are tolerant of many evils, including outliving their activation (e.g. the home contexts of blocks) and having arbitrary changes made to their internal fields and stack contents (the Debugger, Exceptions, brace stacks, ContextPart release code run from Process termination, and so on) -- of which by far the most evil has to be a stores into the sender field.  Stack frames, on the other hand, are inherently LIFO.  A significant amount of effort has to be spent to reconcile this intrinsic LIFOness with any non-linear behaviour induced by BlockContexts or explicit program modifications to the internals of Context objects.
 

Stack frames

Handling modifications to Contexts

The answer is PseudoContexts.  These are ``proxies'' which exhibit perfectly Context-like behaviour at the Smalltalk level, but which in reality are active objects that ``reflect'' onto the underlying execution state held in stack Frames.  Reading any field of a PseudoContext causes the appropriate value to be calculated according to the current state of the Frame on which it reflects.  This is straightforward, since all of the state that would be present in a real Context can be reconstructed trivially from the state contained in a Frame.  Writing a field of a PseudoContext causes a corresponding modification to the state of the associated Frame.  Such  modifications range from delicate (e.g. writing a new value into the stack, or changing the pc, stackp, receiver, method or home field) to downright violent (writing the sender field of a PseudoContext, for example, can result in the wholesale reconstruction of the stack ``under the feet'' of the running Process).  Such modifications are seldom trivial: some kind of special ``corrective'' action is almost always required to ensure that the program continues to exhibit correct behaviour.  This is due to the type analysis performed by the optimiser.  Simply modifying the receiver or a location in the stack, for example, can invalidate certain optimisation assumptions that were in effect during translation of the Frame's associated CompiledMethod, causing the program to function incorrectly.  (A trivial example would be storing a non-SmallInteger receiver into a Frame executing a method in class SmallInteger.  The optimiser has at the very least eliminated redundant tag checks for inlined arithmetic operations on the receiver, which would suddenly become relevant again.)

A PseudoContext has the following form:
 

The most obvious thing to notice about PseudoContexts is that they have the same format and almost the same layout as normal Context objects.  This is for three reasons.  First it helps to simplify the process of stabilisation, since only the first three fields need to be reinitialised and the final stack contents copied into the indexable part of the PseudoContext.  Second it allows the fourth, fifth and sixth fields to be read directly by Smalltalk without any further computation (since they have the same values as they would in a normal MethodContext or BlockContext object).  Third it allows the runtime to distinguish between PseudoContexts for method frames and those for block frames simply by inspecting the fourth field: if its value is tagged then the corresponding Frame is executing a block.

A raw pointer to the associated frame can be stored directly in PseudoContexts since they have the same ``special'' header type as do MethodContexts and BlockContexts.  During garbage collection, the collector inspects the stackp field (which is always 0 for a PseudoContext) and ignores all indexable fields above this index; in other words, the garbage collector never tries to trace or remap the raw pointer to the frame.

PseudoContexts are created on demand, in only four situations:

1. when the program refers explicitly to thisContext, a PseudoContext is created for the active frame;
2. when a BlockContext receives a #value message, the receiver is converted into a PseudoContext associated with the frame executing the block;
3. when a field of an existing PseudoContext is read and its value would normally be a Context object, but the value refers to a frame rather than an existing in-heap context, a PseudoContext is created and associated with the frame and returned as the ``contents'' of the field; and finally
4. when a Process is suspended, a PseudoContext is created for the active frame and stored in the suspendedContext slot of the outgoing Process.

Some indirect modifications to Frame (via writes into the associated PseudoContext) have immediatel consequences.  The glue routines respond to modifications of the receiver or stackp, and stores of the stack portion of the frame, by immediately redirecting the method of the frame to a non-optimised version (compiling it if necessary, based on the original CompiledMethod), updating the pc value accordingly to resume execution at the same point in the method.  Other modifications to Frames have effects that are only felt when the frame exits.  These situations are handled lazily (to avoid repeated work when several such modifications are made to the same frame) using a ``context fault'' mechanism.  One such situation is the creation of the PseudoContext itself, which must be stabilised (converted into the equivalent Method- or BlockContext) when the frame exits.

Most frames (around 85% in a typical Smalltalk application) do not have an associated PseudoContext.  It is therefore highly desirable to avoid checking if any associated PseudoContext needs to be stabilised each time a frame exits.  Smalltalk also requires that returns check to see if the returning Context's sender is nil, and if so the returning Context is itself sent the #cannotReturn: message with the return value as the argument.  J3 avoids these tests by making then implicit in the ``normal'' exit from the frame.

Frames always exit in the most efficient manner possible: they reload the sender's frame and stack pointers and transfer control to the pc value saved in the sender's frame.  This is typically no more than three or four machine instructions.  Frames for which ``special'' action is required upon exit are ``marked'' by changing the saved pc in their sender's frame to point to a ``context fault'' handler.  The original saved pc value is copied into the ``obscured pc'' slot of the sender's frame.  When the callee frame exits, control is transferred to the context fault handler which takes the appropriate remedial action and then restarts execution in the sender frame by jumping to the location stored in the obscured pc.  Three situations are currently ``repaired'' lazily using this mechanism:

1. stabilisation of a PseudoContext associated with the callee frame.  The return pc is redirected to the context fault handler when the PseudoContext for the callee frame is created;
2. any frame whose sender is ``nil'' has a dummy frame just below it on the stack, whose saved pc points to the context fault handler and whose obscured pc is zero.  (This dummy frame occupies very little stack space, since it does not need to contain space for the indexable portion of the frame.)  The handler responds to this situation by reinstating the exiting frame, creating a PseudoContext for it if it didn't already have one, and then synthesising a send of #cannotReturn: to its PseudoContext.  In effect, the Process fell of the bottom of its stack and drowned;
3. reloading the stack because of a store into the sender field of the PseudoContext associated with the callee frame.  The actual value is written into the first (sender) field of the PseudoContext, and if the context fault handler sees that this field is not nil it flushes the stack (stabilising all of the frames, from the sender right down to the base frame of the Process), and then calls the ``trampoline'' used to ``kick-start'' the initial Process.  This trampoline ``reloads'' the entire stack (starting from the Context stored in the sender field of the callee's PseudoContext) and then resumes execution in the topmost frame of the reloaded stack.

Was it really worth the bother?

That's the evidence.  I leave you to make up your own mind.

Acknowledgements

I am also deeply indebted to Neilze Dorta, who lent me her PowerBook G3 whenever it wasn't needed, thus turning many hours of painful waiting for egcs to compile the PowerPC version of J3 on my rather slow PowerMac 6400 into many minutes of significantly less painful waiting.

References