Cog Blog

Apologies for this appearing out of order. I should be finishing the Closures posts but I can’t for the moment. I crave your indulgence.

As I’ve said in the first post, both TSTTCPW and the Principles imply I’m keeping the existing CompiledMethod format. In Squeak, as in the Blue Book CompiledMethod is an anomalous hybrid , its first part being object references used mainly for literals, and its second part being raw bytes used mainly for bytecodes. The first word of a CompiledMethod is a SmallInteger that encodes amongst other things the size of the first part, the literal frame. This format is a good choice for an interpreter since both literals and bytecodes can be fetched from the same object, although it causes minor complications in the garbage collector since the GC must not misinterpret the bytecode as pointers.

In VisualWorks, which is a JIT on all platforms, CompiledMethod is a normal object and the bytecodes are held in a ByteArray referred to by a “bytes” instance variable. To reduce the footprint overhead of adding a separate object for bytecodes, short methods of 6 bytes of bytecode or less get their bytecodes encoded in a pair of SmallIntegers, one in the bytecode inst var and one in an additional literal. Because VisualWorks CompiledMethods are ordinary objects adding instance variables to CompiledMethod and its subclasses is directly supported by the system.

These are fine design decisions for a JIT but hopeless for an interpreter. Both interpreting the 6 bytes of bytecode in two SmallIntegers and skipping over the named instance variables on each literal access would slow an interpreter down significantly.

So the hybrid CompiledMethod format stays, but the pressure to add instance variables to CompiledMethod is high. In fact Squeak has had a per-CompiledMethod holder for extra instance variables for a while. Its called MethodProperties and while its useful it is IMO a tragic hack. I’ve always taken tragedy to mean drama driven by a character flaw – see Hamartia or Tragic Flaw. Hamlet and Othello are tragedies because events are driven by both characters’ insecurities. Titus Andronicus, on the other hand, is merely a bloodbath.

I’m willing to bet that reason for CompiledMethod having a hybrid format was to save space in the original 16-bit Xerox implementations. This hybrid format is exactly what complicates adding named instance variables and subclasses to CompiledMethod. So it is tragic to see every CompiledMethod in the system get another object (at least another 20 bytes per CompiledMethod, 4 bytes for the literal slot, 16 bytes for the MethodProperties instance) that in most cases merely adds a selector instance variable (4 bytes). So how to we square the circle?

On starting at Qwaq I immediately wanted to get to work on restructuring the compiler to allow for easy migration of bytecode sets. This would give me free rein in when I wanted to redefine the bytecode set later on and permit implementing closures in a cleaned-up compiler. But I soon found out there were two compilers, one for base Smalltalk and one for Andreas Raab’s Tweak. The Tweak compiler differs in allowing a class to define certain “instance varables” to be implemented as dynamically added properties. This is a similar idea to accessing instance variables through messages, something Gilad Bracha is quite rightly pushing in Newspeak.

In the Tweak compiler a class communicates what properties it uses by supplying a set of Field nodes, one for each property. The compiler compiles Field nodes as message sends. In the base compiler instance variables are always accessed directly using bytecodes containing the offset of a given instance varable. Other than that the differences between the compilers are minor. So the first order of business was to merge the Tweak compiler into the base compiler and restructure one compiler instead of two. In doing so I was given a working implementation of compiling accessors within the Tweak compiler. These field definitions can easily be adapted to implementing instance variables in CompiledMethod and subclasses.

A CompiledMethod’s literals occupy the first N slots following the header word. The last literal is used by the super send bytecodes to fetch the class in which the current method is defined, whose superclass is the class to begin a super send lookup. The last literal is located by the VM extracting the literal count from the header word. All other literals used by the bytecode are accessed by encoding their literal index in each bytecode as appropriate, the slot immediately following the header word being literal 0. All bytecodes are position-independent, jumps being relative. So one can add literals immediately before the last literal without invalidating the method. The system needs to update the literal count in the header to reflect the extra literal slot but otherwise a method is unaffected. So the scheme is to store instance variables of CompiledMethod and subclasses at the end of the literal frame and access them by messages.

Whitewash alert. There are some details.

Either CompiledMethod class>>newMethod:header: or its callers need to be redefined to add in the relevant number of literals for the named instance variables. Methods such as CompiledMethod>>numLiterals need to be redefined to subtract the number of named instance variables from the literal count. For example

CompiledMethod methods for accessing
numNonHeaderPointerFields
        “Answer the number of pointer objects in the receiver.”
        ^(self header bitShift: -9) bitAnd: 16rFF
numLiterals
        “Answer the number of literals used by the receiver.”
        ^self numNonHeaderPointerFields – self class instSize

The compiler needs to keep these accessors hidden and prevent their accidental redefinition. Something we did in Newspeak was to keep accessors out of the class’s organization. With a little polish one can easily ensure that the system does not file-out unorganized methods. Additionally the accessors should be name-mangled so their message names are not legal Smalltalk message selectors or variable names so they can’t be accidentally redefined, for example prepend an underscore. So each instance variable needs a pair of messages that look like the following. Let’s say that methodClassAssociation is the first instance variable, selector is the second, and pragmas is the third (and in a subclass of CompiledMethod). Then the accessors would be equivalent to

_methodClassAssociation
        ^self objectAt: self numNonHeaderPointerFields + 1
_methodClassAssociation: anObject
        ^self objectAt: self numNonHeaderPointerFields + 1 put: anObject
_selector
        ^self objectAt: self numNonHeaderPointerFields
_selector: anObject
        ^self objectAt: self numNonHeaderPointerFields put: anObject
_pragmas
        ^self objectAt: self numNonHeaderPointerFields – 1
_pragmas: anObject
        ^self objectAt: self numNonHeaderPointerFields – 1 put: anObject

etc…

The setters must answer the value assigned rather than self to simplify compiling
        instVar1 := instVar2 := expr

The accessors need to be created as a side-effect of the ClassBuilder redefining CompiledMethod or a subclass. setInstVarNames: seems to be the right hook here.

The ClassBuilder needs to allow the creation of subclasses of CompiledMethod, giving them an instSpec of 12. The instSpec of 12 is the magic number that the garbage collector uses to identify objects that are part pointers, part bytes. See Behavior>>instSpec and Interpreter>>formatOf:. The ClassBuilder also needs special instance mutation code for CompiledMethod and subclasses that would use objectAt: and objectAt:put: to copy state between mutated instances and keep the header up-to-date accurately reflecting the number of literals in the header word. IMO, the bulk of this code belongs on the class side CompiledMethod.
Once we have this done we can say bye bye to MethodProperties, gaining about a megabyte in a 20 megabyte image and make adding extensions such as pragmas cheap and localised.

So who wants the brush? Don’t everyone step forward at once…. Anyone? Why is everyone backing away mumbling to themselves? I have always depended on the comfort of strangers…

P.S. Anyone who does want to work on this can either contact me in email or wait a few days until I can start publishing code to a Croquet repostory near you.

2008/06/23
P.P.S. As Joshua Gargus, one of my colleagues at Qwaq, astutely pointed out today one also needs to deal with the changes to the pc in existing contexts when one shape-changes compiled methods. So one would need to enumerate all context objects to fix up their pcs and this gets tricky since those contexts could be in-use by the ClassBuilder. So some care is required to pull this off. Thanks Josh!