So how does one write a just-in-time compiler<\/a> (or JIT for short)? First, why<\/i> write a JIT? Essentially dynamic languages defer certain performance-critical computations to run-time. These languages are "late-bound<\/a>". Type information is kept in objects themselves and this type information is used at run-time to bind operation names to operation implementations. In static languages such as C the programmer declares the type information to the compiler which is therefore able to bind operation names to operation implementations at compile and link time, but at the cost of writing the software within a potentially inflexible and constraining type system, and having to do without any modification of the executable at run-time. This is the essential trade-off and which side you choose depends on what works for you. Teleplace<\/a>‘s Croquet<\/a>-based system is written in Smalltalk<\/a> so they’ve chose dynamism. If you’re reading this blog chances are you’re a Smalltalk user so it presumably works for you too. Writing a JIT for a dynamic language allows the implementation to generate code of much higher efficiency than an interpreter for invoking late-bound operations by deferring code generation until run-time, there-by regaining some of the advantages a static language compiler has. The primary optimization is applied to message sending, and one effective technique is inline cacheing<\/a>.<\/p>\n So how does<\/i> one write a JIT? There are two answers I like. One is "one step at a time" and the other is "the way you know how".<\/p>\n I’ve described the first two chunks which were to add closures and build a VM that used a stack organization under the covers, the Cog Stack Interpreter<\/a>. This was deployed towards the end of 2008, and provided modest performance improvements while proving one of the more complex parts of the VM, context-to-stack mapping. Mapping Smalltalk’s contexts to a stack organization enables the use of call instructions for message sends, an essential feature of inine cacheing. The next step has been to write a simple JIT with a naïve code generator but good send performance which I’ll describe in this and the next few posts.<\/p>\n Later steps are to write a more sophisticated code generator, to improve the garbage collector and object model, and to tackle adaptive-optimization\/speculative inlining in an innovative way. I’ve completed the first of these, and will write it up subsequently. I’ve yet to start work on the garbage collector and object model, although I have a design in mind. For two weeks in February I’ve worked with Marcus Denker<\/a> of INRIA on the infrastructure for adaptive-optimization\/speculative inlining in Cog and Squeak and it’s been fun!<\/p>\n In approaching writing the JIT, I had one big problem, how to execute the x86 machine code the JIT would generate in the simulator. One thought was to attempt to auto-generate a Smalltalk implementation of an x86 given some formal definition, but I couldn’t find one. Instead I followed my colleague Josh Gargus<\/a>‘ suggestion and used the Bochs pc-compatible emulator<\/a>, making it a Squeak plugin, accessed through suitable primitives. As described previously<\/a>, I took the core processor code, wrote a different memory interface for it and mated it to the byte array the simulator uses to hold the Smalltalk heap. Hence I am able to generate x86 machine code into the byte array and execute this with Bochs, with Bochs catching all errors and returning them as primitive failures which are translated into exceptions.<\/p>\n Inline cacheing is the technique of speeding up sends by cacheing the results of method lookups at send sites instead of in the first-level method lookup cache. Let’s remind ourselves of what a first-level method lookup cache probe looks like. We start with the interpreter’s implementation of a generic zero-argument send. In the below the green code between <>’s are "method tags", method metadata we use to communicate with the Smalltalk to C translator.<\/p>\n \t StackInterpreter methods for send bytecodes<\/i> \t StackInterpreter methods for message sending<\/i>One Step at a Time<\/H2>
\nWhen I joined Teleplace, née Qwaq, I had a pretty good idea of the JIT I wanted to build. It would be architecturally similar to the VisualWorks VM’s execution engine, a medium performance JIT with good inline cacheing. But that would take quite a while and folks at Teleplace much prefer smaller steps over giant leaps; even if climbing the stairs takes longer there’s less chance of breaking one’s neck. So the project has been divided into smaller chunks.<\/p>\nThe Way One Knows How<\/H2>
\nKnowing what one’s doing in software engineering is a very privileged and advantageous position to be in. Not having to spend time exploring unknown parts of the solution space, being guided by past successes and failures, knowing valid overall architectures, writing the code cleanly from the start, all help increase quality and reduce development time. It also means less surprises for both developer and customer. In the past I’ve written a couple of bytecode-to-threaded code JITs and spent a decade working on HPS, the VisualWorks VM, so I’m in the lucky position of knowing how to write performant Smalltalk VMs. So while there are other ways to write a JIT, such as the in-vogue tracing JIT<\/a>, I’ve taken a tried and tested approach, bytecode-to-machine-code translation with good inline cacheing. Better the devil you know than the devil you don’t.<\/p>\nBut Wait!<\/H2>
\nExcept of course what I’ve been talking about is how to architect a VM, not actually how to develop it, what language to write it in and how to debug it. One thing I have<\/i> learnt that’s new is that writing a VM in a high-level language (the Squeak Interpreter and the Cog Stack Interpreter are written in Smalltalk) instead of a machine-oriented language (my BrouHaHa VMs and the HPS VM are written in C) is a great idea. At first I was really sceptical about the approach taken to write the original Squeak interpreter<\/a>. This is to write the VM in a subset of Smalltalk, the source being derived from the blue-book VM specification in Smalltalk<\/a>, and then to translate this into C via a Smalltalk program called Slang. As I developed the stack interpreter I soon grew to love being able to use the Smalltalk IDE to browse and debug the VM. It meant some compromise; one doesn’t write pure Smalltalk and sometimes using Slang feels like being hit over the head by a Kensei<\/a> without any resultant enlightenment, but it proved way better than C. Some terminology, when working with the Smalltalk form of the VM in the Smalltalk IDE we’re working in the simulator.<\/p>\nOK, let’s go<\/H2>
\nOk, so now I’m ready to dive into the VM. I could start with the overall architecture, but that’s going to delay showing you real code for a while. In subsequent posts I’ll discuss marrying the JIT and the interpreter, code generation and simulation and method management and method metadata and its uses. But let’s start with inline cacheing, the main rationale behind the JIT. <\/p>\n
\n\t sendLiteralSelector0ArgsBytecode<\/b>
\n\t \t <\/font>"Can use any of the first 16 literals for the selector."<\/font>
\n\t \t <\/font>|<\/font> <\/font>rcvr<\/font> <\/font>|<\/font>
\n\t \t <\/font>messageSelector<\/font> <\/font>:=<\/b> <\/font>self<\/font> <\/font>literal:<\/font> <\/font>(<\/font>currentBytecode<\/font> <\/font>bitAnd:<\/font> <\/font>16rF<\/font>)<\/font>.<\/font>
\n\t \t <\/font>argumentCount<\/font> <\/font>:=<\/b> <\/font>0<\/font>.<\/font>
\n\t \t <\/font>rcvr<\/font> <\/font>:=<\/b> <\/font>self<\/font> <\/font>internalStackValue:<\/font> <\/font>0<\/font>.<\/font>
\n\t \t <\/font>lkupClass<\/font> <\/font>:=<\/b> <\/font>objectMemory<\/font> <\/font>fetchClassOf:<\/font> <\/font>rcvr<\/font>.<\/font>
\n\t \t <\/font>self<\/font> <\/font>commonSend<\/font><\/p>\n
\n\t commonSend<\/b>
\n\t \t <\/font>"Send a message, starting lookup with the receiver’s class."<\/font>
\n\t \t <\/font>"Assume: messageSelector and argumentCount have been set, and that <\/font>
\n\t \t the receiver and arguments have been pushed onto the stack,"<\/font>
\n\t \t <\/font>"Note: This method is inlined into the interpreter dispatch loop."<\/font>
\n\t \t <\/font><<\/font>sharedCodeNamed:<\/b><\/font> <\/font>‘commonSend’<\/font> <\/font>inCase:<\/b><\/font> <\/font>131<\/font>><\/font>
\n\t \t <\/font>self<\/font> <\/font>internalFindNewMethod<\/font>.<\/font>
\n\t \t <\/font>self<\/font> <\/font>internalExecuteNewMethod<\/font>.<\/font>
\n\t \t <\/font>self<\/font> <\/font>fetchNextBytecode
\n<\/font>
\n\t internalFindNewMethod<\/b>
\n\t \t <\/font>"Find the compiled method to be run when the current messageSelector is sent
\n\t \t to the class ‘lkupClass’, setting the values of ‘newMethod’ and ‘primitiveIndex’."<\/font>
\n\t \t <\/font>|<\/font> <\/font>ok<\/font> <\/font>|<\/font> <\/font>
\n\t \t <\/font><<\/font>inline:<\/b><\/font> <\/font>true<\/font>><\/font>
\n\t \t <\/font>ok<\/font> <\/font>:=<\/b> <\/font>self<\/font> <\/font>lookupInMethodCacheSel:<\/font> <\/font>messageSelector<\/font> <\/font>class:<\/font> <\/font>lkupClass<\/font>.<\/font>
\n\t \t <\/font>ok<\/font> <\/font>ifFalse:<\/font> <\/font>"entry was not found in the cache; look it up the hard way"<\/font>
\n\t \t \t <\/font>[<\/font>self<\/font> <\/font>externalizeIPandSP<\/font>.<\/font>
\n\t \t \t <\/font>self<\/font> <\/font>lookupMethodInClass:<\/font> <\/font>lkupClass<\/font>.<\/font>
\n\t \t \t <\/font>self<\/font> <\/font>internalizeIPandSP<\/font>.<\/font>
\n\t \t \t <\/font>self<\/font> <\/font>addNewMethodToCache:<\/font> <\/font>lkupClass<\/font>]
\n<\/font>
\n<\/font>The confusing bits about the above are details to do with the translation of the code to C for the production interpreter. The internal prefix implies that such an interpreter method gets inlined into a single large interpreter function and that it uses local stack frame and instruction pointers that we expect the C compiler to place in registers (that’s what <\/font>externalizeIPandSP<\/font> and <\/font>internalizeIPandSP<\/font> do, export the local to the global pointers and import the global to the local pointers respectively). The <\/font>sharedCodeNamed:<\/b><\/font> pragma causes one copy of the commonSend\/internalFindNewMethod\/<\/font>lookupInMethodCacheSel:<\/font>class: code to be generated in the interpreter loop (at bytecode 131, <\/font>singleExtendedSendBytecode<\/font>) and for all other users, such as sendLiteralSelector0ArgsBytecode to jump to that code. So here’s the actual lookup. It does up to three probes to avoid collisions:
\n<\/font>
\n\t StackInterpreter methods for message sending<\/i>
\n\t <\/font>lookupInMethodCacheSel:<\/b> <\/font>selector<\/font> <\/font>class:<\/b> <\/font>class<\/font>
\n\t \t <\/font>"This method implements a simple method lookup cache. If an entry for the given selector and
\n\t \t class is found in the cache, set the values of ‘newMethod’ and ‘primitiveFunctionPointer’ and
\n\t \t return true. Otherwise, return false."<\/font>
\n\t \t <\/font>"About the re-probe scheme: The hash is the low bits of the XOR of two large addresses, minus their
\n\t \t useless lowest two bits. If a probe doesn’t get a hit, the hash is shifted right one bit to compute the
\n\t \t next probe, introducing a new randomish bit. The cache is probed 3 times before giving up."<\/font>
\n\t \t <\/font>"WARNING: Since the hash computation is based on the object addresses of the class and selector, we
\n\t \t must rehash or flush when compacting storage. We’ve chosen to flush, since that also saves the trouble
\n\t \t of updating the addresses of the objects in the cache."<\/font>
\n\t
\n\t \t <\/font>|<\/font> <\/font>hash<\/font> <\/font>probe<\/font> <\/font>|<\/font>
\n\t \t <\/font><<\/font>inline:<\/b><\/font> <\/font>true<\/font>>
\n\t \t <\/font>hash<\/font> <\/font>:=<\/b> <\/font>selector<\/font> <\/font>bitXor:<\/font> <\/font>class<\/font>.<\/font> <\/font>"shift drops two low-order zeros from addresses"<\/font>
\n\t
\n\t \t <\/font>probe<\/font> <\/font>:=<\/b> <\/font>hash<\/font> <\/font>bitAnd:<\/font> <\/font>MethodCacheMask<\/font>.<\/font> <\/font>"first probe"<\/font>
\n\t \t <\/font>(<\/font>(<\/font>(<\/font>methodCache<\/font> <\/font>at:<\/font> <\/font>probe<\/font> <\/font>+<\/font>