In the post before last we saw the closure design in Cog and its prototype implementation above an unmodified VM. This post looks at the opcodes used to implement Closures in the image. The image level implementation is in InsructionStream, ContextPart and MethodContext is used by the debugger and some of the image-level browsing facilities. The next post will probably present the VM implementation. <\/p>\n
Before we dive in, let’s recap. The closure implementation has one key aim for performance. The activation of a closure should be independent of its enclosing activation. This simplifies stack management meaning that while the closure is running it doesn’t need to access its lexically enclosing activation to run. This is achieved by a simple transformation in two parts. Any closed-over variable that does not change after being closed-over is copied into the closure which accesses the copy. Any closed-over variable which does change after being closed over is put in a heap-allocated "indirection vector" (a simple array, one element per closed-over variable) and the indirection vector is copied into the closure. All accesses to the variable are made through the indirection vector. Here’s the transformation applied at the source level to inject:into:<\/p>\n
Collection methods for enumerating<\/i> So let’s implement this with bytecodes, so that we can bootstrap closures in something close to the current VM, something that will run both the existing system and a system recompiled to use closures. Before we do so we need to digress a bit on bytecode set design.<\/p>\n Eventually we’ll design a new bytecode set which will be chosen to encode the opcodes we find in the current system as efficiently as we can. That means What do I mean? Well, look at the Push Receiver Variable opcode which has several bytecodes in the current Squeak VM:<\/p>\n \t 0-15 \t 0000iiii \t \t \t Push Receiver Variable #iiii Push Receiver Variable has both high dynamic frequency (how often an opcode is evaluated) and static frequency (how often an operation occurs in methods). Most objects have few instance variables. In my Croquet image only 20% of classes (ignoring metaclasses) have more than 15 instance variables. So there is both a high static and high dynamic frequency of pushing instance variables with a small offset. Hence the design above where there are 16 one-byte bytecodes to access the instance variables with offsets 0 through 15, a two byte bytecode that can access instance variables with offsets 0 through 63 and a three byte bytecode that can access instance variables with offsets 0 through 255, the maximum imposed by a class’s instance format word (the largest class in my image has 139 instance variables).<\/p>\n Interpreting the short forms 0-15 \t 0000iiii Push Receiver Variable #iiii is a lot quicker than interpreting the longer forms. One piece of code I ran to measure the sizes of bytecoded methods in two images, one which used only the long-forms and one which used the shortest forms available, ran 40% slower in the image which used only the long forms. So the game in designing a bytecode set is to divide up the available bytecode space amongst the opcodes to achieve a compromise between dynamic and static frequency. In practice optimizing on the basis of static frequency is a good heuristic since static frequency is a fair predictor of dynamic frequency.<\/p>\n But the design of a bytecode set for the closure system is something that can wait until we’ve bootstraped the closure system and can start to perform some measurements. The first order of business is to bootstrap closures in the existing Squeak VM. To do that we need to find room. Only if we can’t find room do we need to make room. Luckily, the existing Squeak VM has 8 unused bytecodes, and that’s more than enough.<\/p>\n Here are the unused entries in the method that defines the VM’s bytecodes, Interpreter class>>initializeBytecodeTable: We’ll use 5 of the 6 experimental bytecodes. These aren’t generated by the compiler (and implement an optimization we hope to outdo). We don’t have many to play with so we can’t do much space optimization. Because we only have 6 and each opcode needs at least one index we’ll have to use multi-byte encodings and include the indices in trailing bytes.<\/p>\n Here are all 5 bytecodes. We’ll go through each separately three times. First we’ll define the bytecodes. Then we’ll implement them in the image’s execution simulation machinery, which we can use to test the bytecode before we generate a VM, and which is used by the debugger and also by the printing machinery that disassembles methods. lastly we’ll go through the VM code.<\/p>\n \t 138 \t 10001010 jkkkkkkk \t \t \t \t Push (Array new: kkkkkkk)\/Pop kkkkkkk into: (Array new: kkkkkkk) The first opcode can be used to create indirect temp vectors. Because Squeak stack frames are limited in size (50-ish slots) we don’t need to be able to create an Array with 265 elements. We can make our bytecode more useful if it can either create a new Array initialized with nils or initialize a new Array with elements popped off the stack.<\/p>\n \t 138 \t 10001010 jkkkkkkk Push (Array new: kkkkkkk)\/Pop kkkkkkk into: (Array new: kkkkkkk)<\/p>\n So we can use it to compile brace expressions. In Squeak Bezier3Segment methods for vector functions is compiled to Question, why does the compiler limit itself to only 4 elements max?<\/i><\/p>\n With the new bytecode this compiles to So in compiling inject:into: the first two bytecodes look like We could have designed the bytecode to include the offset of the local into which we want to store the new array since in our compiler Push (Array new: kkkkkkk) is always followed by a popIntoTemp: n. But since there can currently be up to 32 locals we’d either be limited in the size of the array or use a three byte bytecode. Neither of these is a win. A bytecode that does both Push (Array new: kkkkkkk) and Pop kkkkkkk into: (Array new: kkkkkkk) is more flexible and just as compact because we frequently get to use the short-form for the following popIntoTemp.<\/p>\n Answer, if the compiler used the same approach for very large brace expressions then for one thing we’d need a lot of braceWith:……with: methods, but more importantly we’d soon get stack overflow given the small finite stack size of Smalltalk’s contexts. So large brace expressions are compiled to stream code that is equivalent to Now the Push Temp At m In Temp Vector At: n opcode. In a moment of weakness I decided to go for a short-form here. But then I recovered my sanity. There were only 2700 occurrences of the short form in my image, which is about a 0.01% saving. The unused bytecode is probably much more valuable. But this explains the mysterious gap in the new bytecodes at 139. So the opcode’s bytecode is<\/p>\n \t 140 \t 10001100 kkkkkkkk jjjjjjjj \t \t Push Temp At kkkkkkkk In Temp Vector At: jjjjjjjj<\/p>\n This fetches the local at offset j..j on the stack and push the k..k’th element in it.<\/p>\n The next two store into the k..k’th element of the local at j..j, one version popping the result off the stack. This is a general convention in the Smalltalk-80 compiler. These are store and store-pop forms of almost every store opcode. The store form is used in the stores into vat and vax in things like \t 141 \t 10001101 kkkkkkkk jjjjjjjj \t \t Store Temp At kkkkkkkk In Temp Vector At: jjjjjjjj The final bytecode is more interesting.<\/p>\n \t 143 \t 10001111 llllkkkk jjjjjjjj iiiiiiii\t Push Closure Num Copied llll Num Args kkkk BlockSize jjjjjjjjiiiiiiii<\/p>\n This creates a closure, initializing it from the arguments and the current context. Because I’m doing The Simplest Thing That Could Possibly Work this is very closely modelled on the old BlockContext scheme. We don’t use a separate method for the block’s code. Instead we embed the code for a block within the code for its enclosing block or method. This has pros and cons. Its arguably more compact because blocks and methods get to share literals if they access the same ones, and because there is only one CompiledMethod object, but this is offset by the fact that we will need larger ranges and hence more long-form bytecodes to access the literals because the CompiledMethod’s literal frame contains the literals for the method and its blocks.<\/p>\n In the old scheme a block is created by sending blockCopy: to the active context with the block’s argument count as its argument and then jumping around the bytecodes for the block. The primitive for blockCopy: takes into account the size of the jump and the compiler always generates a 2 byte jump. Its a hack but it works:<\/p>\n \t 20 <89> pushThisContext The bytecode set has short forms for push -1, 0, 1 and 2 where you see <76> being used above but if a block has more than 2 arguments then we need 4 bytes for the literal as well as the push. But we’ll say that creating a block costs 5 bytecodes. One problem is that the long jump only has a 10-bit range so we can’t have blocks with more than 1023 bytes of bytecode in them. Collapsing these 4 separate bytecodes down into 1 multibyte code saves time and space, and easily allows a 16-bit jump size. <\/p>\n So now the same block creation code compiles to the following bytecode: We’ve gained a byte. The above looks worse (its our old friend Collection>>inject:into: which uses those bulky indirect temp bytecodes). In the common case we save, but any savings are offset by the bytecodes to push copied temps. We’ll gather full measurements in the next post.<\/p>\n To implement a new bytecode one needs to alter a few parts of the system. One place is the VM. We’ll do that at the end of this post. There are two main places in the image. One is the compiler, to generate the bytecode. I’m going to defer discussing the compiler changes for now because there are enough changes to justify a post on its own. Another is in the execution simulation machinery which is used for several things This all revolves around InstructionStream which is the class that manages the interpretation of bytecoded methods at the image level, the image’s dual of the VM itself.<\/p>\n Object <\/font>subclass:<\/font> <\/font>#InstructionStream<\/font> <\/font><\/font>InstructionStream interprets bytecodes in two methods <\/font>InstructionStream methods for instruction decoding<\/i><\/font> <\/font>doDup<\/b> <\/font>doPop<\/b> <\/font>jump:<\/b> <\/font>offset<\/font> <\/font>methodReturnConstant:<\/b> <\/font>value<\/font> <\/font>methodReturnReceiver<\/b> <\/font>methodReturnTop<\/b> <\/font>popIntoLiteralVariable:<\/b> <\/font>anAssociation<\/font> <\/font>popIntoReceiverVariable:<\/b> <\/font>offset<\/font> <\/font>popIntoTemporaryVariable:<\/b> <\/font>offset<\/font> <\/font>pushActiveContext<\/b> <\/font>pushConstant:<\/b> <\/font>value<\/font> <\/font>pushLiteralVariable:<\/b> <\/font>
\ninject:<\/b> <\/font>thisValue<\/font> <\/font>into:<\/b> <\/font>binaryBlock<\/font>
\n\t <\/font>|<\/font> <\/font>nextValue<\/font> <\/font>|<\/font>
\n\t <\/font>nextValue<\/font> <\/font>:=<\/b> <\/font>thisValue<\/font>.
\n\t <\/font>self<\/font> <\/font>do:<\/font> [:<\/font>each<\/font> <\/font>|<\/font> <\/font>nextValue<\/font> <\/font>:=<\/b> <\/font>binaryBlock<\/font> <\/font>value:<\/font> <\/font>nextValue<\/font> <\/font>value:<\/font> <\/font>each<\/font>].
\n\t <\/font>^<\/font>nextValue
\n<\/font>
\ntransforms to<\/i>
\ninject:<\/b> <\/font>thisValue<\/font> <\/font>into:<\/b> <\/font>binaryBlock<\/font>
\n\t <\/font>|<\/font> <\/font>indirectTemps<\/font> <\/font>|<\/font>
\n\t <\/font>indirectTemps<\/font> <\/font>:=<\/b> Array <\/font>new:<\/font> <\/font>1<\/font>.
\n\t <\/font>indirectTemps<\/font> <\/font>at:<\/font> <\/font>1<\/font> <\/font>put:<\/font> <\/font>thisValue<\/font>.
\n\t <\/font>self<\/font> <\/font>do:<\/font> [:<\/font>each<\/font> <\/font>|<\/font> <\/font>indirectTemps<\/font> <\/font>at:<\/font> <\/font>1<\/font> <\/font>put:<\/font> <\/font>(<\/font>binaryBlock<\/font> <\/font>value:<\/font> <\/font>(<\/font>indirectTemps<\/font> <\/font>at:<\/font> <\/font>1<\/font>)<\/font> <\/font>value:<\/font> <\/font>each<\/font>)<\/font>].
\n\t <\/font>^<\/font>(<\/font>indirectTemps<\/font> <\/font>at:<\/font> <\/font>1<\/font>)<\/font><\/p>\n
\n– making sure that opcodes with high dynamic frequency have short bytecodes that are quick to interpret
\n– that opcodes with high static frequency have short bytecodes that represent them compactly
\n– and that bytecodes exist to ensure all opcodes have large enough ranges to implement the system without restriction.<\/p>\n
\n\t 128 \t 10000000 jjkkkkkk \t Push (Receiver Variable, Temporary Location, Literal Constant, Literal Variable) [jj] #kkkkkk
\n\t 132 \t 10000100 iiijjjjj kkkkkkkk \t (Send, Send Super, Push Receiver Variable,
\n\t \t \t \t \t \t \t Push Literal Constant,
\n\t \t \t \t \t \t \t Push Literal Variable, Store Receiver Variable,
\n\t \t \t \t \t \t \t Store-Pop Receiver Variable, Store Literal Variable)[iii] #kkkkkkkk jjjjj<\/p>\n
\n\t \t \t …
\n\t \t (126 127 unknownBytecode)
\n\t \t \t …
\n\t \t (138 143 experimentalBytecode)
\n\t \t \t …<\/p>\nNew Closure Bytecodes<\/H2><\/p>\n
\n\t 140 \t 10001100 kkkkkkkk jjjjjjjj \t \t Push Temp At kkkkkkkk In Temp Vector At: jjjjjjjj
\n\t 141 \t 10001101 kkkkkkkk jjjjjjjj \t \t Store Temp At kkkkkkkk In Temp Vector At: jjjjjjjj
\n\t 142 \t 10001110 kkkkkkkk jjjjjjjj \t \t Pop and Store Temp At kkkkkkkk In Temp Vector At: jjjjjjjj
\n\t 143 \t 10001111 llllkkkk jjjjjjjj iiiiiiii\t Push Closure Num Copied llll Num Args kkkk BlockSize jjjjjjjjiiiiiiii<\/p>\n
\n\t { expr1. expr2. expr3. }
\nis convenient short-hand for
\n\t Array with: expr1 with: expr2 with: expr3
\nand more flexible because brace expressions can have any number of elements. The existing Squeak compiler compiles brace expressions with up to 4 elements as sends of braceWith:[with:[with:[with:]]]. e.g.<\/p>\n
\n<\/i>controlPoints<\/b>
\n\t <\/font>^<\/font>{start. via1. via2. end}<\/font><\/p>\n
\n\t 21 <41> pushLit: Array
\n\t 22 <00> pushRcvr: 0
\n\t 23 <02> pushRcvr: 2
\n\t 24 <03> pushRcvr: 3
\n\t 25 <01> pushRcvr: 1
\n\t 26 <83 80> send: braceWith:with:with:with:
\n\t 28 <7C> returnTop<\/p>\n
\n\t 13 <00> pushRcvr: 0
\n\t 14 <02> pushRcvr: 2
\n\t 15 <03> pushRcvr: 3
\n\t 16 <01> pushRcvr: 1
\n\t 17 <8A 84> pop 4 into (Array new: 4)
\n\t 19 <7C> returnTop
\nThe top bit of the following byte (bit j in the specification) is set and indicates popping 4 elements off the stack into the new array. The VM already knows the class Array because it is used e.g. in doesNotUnderstand: processing. We save 8 bytes by not having to have the literals for the class Array and the message selector #braceWith:with:with:with: in the compiled method. We save a further byte avoiding the pushLit: instruction. And of course the bytecode is much quicker to interpret than the old code. We’re saving time and space. Way to go.<\/p>\n
\n\t 17 <8A 01> push: (Array new: 1)
\n\t 19 <6A> popIntoTemp: 2<\/p>\n
\n\t (Array braceStream: N) nextPut: expr1; nextPut: expr2; nextPut: expr3; … nextPut: exprN
\nand the closure compiler limits itself to 8 elements before using the stream implementation.<\/i><\/p>\n
\n\t 139 \t 10001011 jjjjkkkk \t \t \t Push Temp At kkkk In Temp Vector At: jjjj
\n\t 140 \t 10001100 kkkkkkkk jjjjjjjj \t \t Push Temp At kkkkkkkk In Temp Vector At: jjjjjjjj<\/p>\n
\n\t var := vat := vax := expr
\nwhereas the pop form gets used in the store into var.<\/p>\n
\n\t 142 \t 10001110 kkkkkkkk jjjjjjjj \t \t Pop and Store Temp At kkkkkkkk In Temp Vector At: jjjjjjjj<\/p>\n
\n\t 21 <76> pushConstant: 1
\n\t 22 <C8> send: blockCopy:
\n\t 23 <A4 08> jumpTo: 33
\n\t \t … the bytecodes for the block …
\n\t 33 … the continuation of the method …<\/p>\n
\n\t 27 <8F 21 00 09> closureCopyNumCopied: 2 numArgs: 1 bytes 31 to 40
\n\t \t … the bytecodes for the block …
\n\t 40 … the continuation of the method …<\/p>\nImplementing the Closure Bytecodes at the Image Level<\/H2><\/p>\n
\n– implementing the debugger
\n– implementing the decompiler
\n– implementing method disassembling
\n– implementing browser support<\/p>\n
\n\t <\/font>instanceVariableNames:<\/font> <\/font>‘sender pc’<\/font><\/font>
\n\t <\/font>classVariableNames:<\/font> <\/font>‘SpecialConstants’<\/font><\/font>
\n\t <\/font>poolDictionaries:<\/font> <\/font>”<\/font><\/font>
\n\t <\/font>category:<\/font> <\/font>‘Kernel-Methods’<\/p>\n
\n\t interpretNextInstructionFor:<\/b> <\/font>client<\/font>
\n\t \t <\/font>"Send to the argument, client, a message that specifies the type of the
\n\t \t next instruction."<\/font>
\n\t interpretExtension:<\/b> <\/font>offset<\/font> <\/font>in:<\/b> <\/font>method<\/font> <\/font>for:<\/b> <\/font>client<\/font>
\nthe latter takes care of the decoding of bytecodes 128 through 143 which are complex enough to need their own method. The interpretation causes the sending of messages to the client, one per opcode. Here’s the entire opcode set for Smalltalk-80. As you can see its a small set, and more or less each opcode corresponds to a single token in the source language. InstructionClient is an abstract superclass for classes that implement these opcodes:<\/p>\n
\n<\/font>blockReturnTop<\/b>
\n\t <\/font>"Return Top Of Stack bytecode."<\/font><\/p>\n
\n\t <\/font>"Duplicate Top Of Stack bytecode."<\/font><\/p>\n
\n\t <\/font>"Remove Top Of Stack bytecode."<\/font>
\n<\/font>
\njump:<\/b> <\/font>offset<\/font>
\n\t <\/font>"Unconditional Jump bytecode."<\/font><\/p>\n
\n\t <\/font>"Unconditional Jump bytecode."<\/font><\/p>\n
\n\t <\/font>"Return Constant bytecode."<\/font><\/p>\n
\n\t <\/font>"Return Self bytecode."<\/font><\/p>\n
\n\t <\/font>"Return Top Of Stack bytecode."<\/font><\/p>\n
\n\t <\/font>"Remove Top Of Stack And Store Into Literal Variable bytecode."<\/font><\/p>\n
\n\t <\/font>"Remove Top Of Stack And Store Into Instance Variable bytecode."<\/font><\/p>\n
\n\t <\/font>"Remove Top Of Stack And Store Into Temporary Variable bytecode."<\/font><\/p>\n
\n\t <\/font>"Push Active Context On Top Of Its Own Stack bytecode."<\/font><\/p>\n
\n\t <\/font>"Push Constant, value, on Top Of Stack bytecode."<\/font><\/p>\n