Introduction to Smalltalk bytecodes

Hi all. It this post I will give you a quick overview and introduction to bytecodes. I won’t talk that much because this topic is well explained in the Blue book, in the code, etc. In the previous posts we saw that a CompiledMethod is all about bytecodes and literals (ok, and a header and a trailer). To really follow the post, I recommend you to have an image with VMMaker. If you don’t know how to do it, please see the title “Prepare the image” of a previous post.

Bytecodes introduction

Let’s start from the beginning: What is a bytecode?  A bytecode is a compact and platform neutral representation of machine code instructions, interpreted by VM. When you code and then save a method in Smalltalk, the Compiler generates an instance of CompiledMethod. Your method’s code is decomposed by the Compiler into a set of basic instructions so that the VM can interpret them.

We have also seen that a CompiledMethod is just an array of bytes. And “BYTEcode” has the prefix “byte”. So, as you can imagine, every bytecode is represented by a byte. One bytecode, one byte (sure?? mmmm). One byte, 8 bits, 2^8 -1 = 255 possible different bytecodes.

Imagine that we code the following basic method:

MyClass >> foo
self name.

To see the bytecodes there are two possibilities: print the answer of  the message #symbolic to the CompiledMethod instance. For example, (MyClass >> #foo) symbolic or use the SystemBrowser, button “View” -> “byte codes”. The bytecodes from the previous method are:

17 <70> self
18 <D0> send: name
19 <87> pop
20 <78> returnSelf

So…how do we interpret such symbolic representation?

Understanding bytecodes printing

Let’s start from left to right. First “column” is a number. In this case, from 17 to 20. What do those number mean?  Explore or inspect the CompiledMethod:

So, those number represent just the position in the whole array. We said a CM (CompiledMethod) was an array of bytes. So, those number represent the position. The CM has two regions: the literal frame (the first bytes of the CM where the literals are stored) and the bytecodes. These numbers are called “Program Counter” (PC) when they are in the bytecode part. For example, if we send the message #endPC to this CM instance, we will get 20 which is the last byte of the CM that represents bytecodes. The next one, 21, is already representing the trailer. The same way, #initialPC answers 17. And how those two methods are implemented?  the #initialPC uses the header’s encoded information such as the number of literals. And #endPC delegates to its trailer since he knows the size of the trailer.

The second column is an hexadecimal surrounded by <> which represents the bytecode number. For example, <70>,, etc. This hexadecimal represent the unique number of bytecode. ’70’ is the bytecode push receiver, ‘D0’ is a send bytecode, 85 pop stack, and push receiver. Since these numbers are encoded in 1 byte it follows that there are 255 possible differnt type of bytecodes.

The third column is just a text describing the type of bytecode.

If we analyze now the bytecodes generated for our simple method that does a “self name” we have that:  the first bytecode (number 17) it just pushes the receiver (self) into the stack. We need that in the stack because in the next bytecode we send a message to it. The second bytecode, 18, sends the message #name to what it is in the stack. When this bytecode finishes, it pushes in the stack the result of the send. But our method doesn’t do anything with it and instead it just answers self (because there is not explicit return). So, we need to do a pop first, bytecode number 19, to remove the result from stack and let the receiver in the top of the stack. And now, we can finally do the return with bytecode number 20.

Mapping bytecodes from image side to VM side

So far we saw how the bytecodes in the CM look like, but we didn’t see how they are map to the VM. So, take your image with VMMaker loaded, and inspect the method #initializeBytecodeTable. You will see that such method is something like this:

The table follows much more but I cut it for the post. So as you see it is just a table that maps numbers to methods 😉  We saw that the symbolic representation has 3 columns, and the second one which was surrounded by <> and an hexadecimal value represents the number of the bytecode. That number is exactly this one used in this table, with the difference that it is in decimal. So, for example the bytecode “<78> returnSelf”, if we translate 78 from hexa to decimal (just print 16r78)  we get 120, which maps to the method #returnReceiver. So, you can now just browse the method and look what it does 🙂  Remember that this is part of VMMaker and this code is written is SLANG. For more details read my old posts.

StackInterpreter >> returnReceiver
localReturnValue := self receiver.
self commonReturn

You have now learned how to see the bytecodes of a method and how to see its implementation in the VM. Cool!!  You deserve a break (or a beer) 🙂

Did you notice that some bytecodes are mapped directly to one only number (like #returnReceiver) but some other like #pushLiteralVariableBytecode are mapped to a range of numbers?  We will see later why.

More complicated bytecodes

Now, let’s see a more advance method, for example, this one:

fooComplicated: aBool and: aNumber
| something aName |
aName := self name.
Transcript show: aName.
aBool
ifTrue: [ ^ aName ].
^ nil

Which generates the following bytecodes:

25 <70> self
26  send: name
27 <6B> popIntoTemp: 3
28 <42> pushLit: Transcript
29 <13> pushTemp: 3
30  send: show:
31 <87> pop
32 <10> pushTemp: 0
33 <99> jumpFalse: 36
34 <13> pushTemp: 3
35 <7C> returnTop
36 <7B> return: nil

There are a couple of new bytecodes in this method. Bytecode 27, does a pop of the return of “self name” and push it in the temp number 3. Notice that temps are both, parameters and temp variables. In this case, temp 0 is ‘aBool’, temp 1 ‘aNumber’, temp 2 ‘something’ and temp 3 is ‘aName’. Bytecode 28 needs to push the literal “Transcript” into the stack since in the next bytecode a message is sent to it. Bytecode 29 pushes ‘aName’ to the stack since it will be the parameter for the send.  Bytecode 30 does the send and 31 does a pop because we don’t do anything with the return of the message.

With bytecode 32 we put ‘aBool’ into the stack and then….then…shouldn’t we have something like 33 send: ifTrue:ifFalse:  ???  Yes, we should. But the compiler does an optimization and replaces the message send by a jump bytecode. In this case, a jump bytecode saying that when it is false jump to bytecode number 36 which does the return nil. Otherwise (if true), continue with bytecode 34 which pushes ‘aName’ into the stack and finally bytecode 35 does the return of the top of the stack (where we can ‘aName’).

How do we represent parameters in bytecodes?

We shouldn’t forget that btyecodes are just a number between 0 and 255. The bytecode <78> returnSelf  is number 120, which was we can see in #initializeBytecodeTable it is mapped by  (120 returnReceiver). Does this method requires any kind of parameter? No. It just returns the receiver. Now,  let’s analyze the bytecode <6B> popIntoTemp: 3 from the previous example. 16r6B -> 107.  Ok, cool. So, number 107 does a pop and puts that into the temp number 3. But….all what we have in the CompiledMethod is the bytecode, the byte that contains the number 107. Nothing more. Imagine the method in the VM that is mapped to this bytecode….how can it knows the temp number?   The same with bytecode “<42> pushLit: Transcript”. It is just a number,  66. Where is the “Transcript” stored?

So…the generic question is, if we only have a bytecode number, how do we solve the bytecodes that require some parameters ? Ok, this will sound a little weird. Or smart?  The truth is that this missing information is sometimes (we will see later why sometimes) encoded using offsets in the range of bytecodes. Let’s see the example of the  <6B> popIntoTemp: 3, which is bytecode number 107. In #initializeBytecodeTable, we can see: “(104 111 storeAndPopTemporaryVariableBytecode)“. So we have a range of bytecode between 104 and 111. In this case we want to do a pop and put the result in the temp number 3. If we can assume that 104 is for temp 0, 105, temp1, 106 temp2 and 107 temp3 🙂 we now understand why out bytecode number is 107. That bytecode number encodes that the number of the temp is the 3. The method storeAndPopTemporaryVariableBytecode  will be able to get a diff between the current number (107) and the start of this range (104) and finally know that the temp number is the 3th.

The same happens with the other example <42> pushLit: Transcript, number 66. In #initializeBytecodeTable we can see “( 64  95 pushLiteralVariableBytecode)“. 64 is for literal at 1, 65 at 2, and 66 at 3.   Now, do (MyClass >> #fooComplicated:and:) literalAt: 3 -> #Transcript->Transcript  🙂

Now, if we analyze “(104 111 storeAndPopTemporaryVariableBytecode)” we can understand that the maximum amount of temporal variable is 7 (111-104). However, in this post, we saw the class comment of CompiledMethod says “(index 18)    6 bits:    number of temporary variables (#numTemps)”. That means that maximum number of temps is 2^6-1=63 . So…..something is wrong. Let’s find out what.

Extended bytecodes

“(104 111 storeAndPopTemporaryVariableBytecode)”  supports 7 temps, but CompiledMethod class comment says 63 are supported. So, let’s create a method with more than 7 temps and let’s see its bytecodes. If we continue with our example we now modify the method to this:

fooComplicated: aBool and: aNumber
| something aName a b c d e f g h i j k |
d := self name.
Transcript show: aName.
aBool
ifTrue: [ ^ aName ].
^ nil

In this case, “d := self name” we are assigning ‘name’ to ‘d’ which is the temp number 7 (remember they start in 0 and the parameters are count together with the temp variables). Hence, the bytecodes are:

 25 <70> self
 26  send: name
 27 <6F> popIntoTemp: 7
 28 <42> pushLit: Transcript
 29 <13> pushTemp: 3
 30  send: show:
 31 <87> pop
 32 <10> pushTemp: 0
 33 <99> jumpFalse: 36
 34 <13> pushTemp: 3
 35 <7C> returnTop
 36 <7B> return: nil

Now, if we just change “d := self name.” to “e := self name.” we would be using the parameter number 8. What would happen? Ok, if you change it you will see that the bytecode changes from “27 <6F> popIntoTemp: 7” to “27 <82 48> popIntoTemp: 8”. Chan! Chan! Chan! What is that???? It seems the bytecode is using in fact 2 bytecodes? (82 and 48).

These kind of bytecodes are called “extended bytecodes”. If we check in #initializeBytecodeTable bytecode 16r82 = 130 is #extendedStoreAndPopBytecode. So at least we know which method is it. Now, what does the 2 bytecode mean (48 in our example) ?  Somehow such second byte should tell us the number of the temp (8 in our example). If we do 16r48 = 72 and check the bytecode 72 we get it is #pushLiteralVariableBytecode, which doesn’t seem to be correct. So, this second byte does not represent a bytecode. Instead, it represents just a byte that encodes information. That information is usually a type and an index, both encoded in one single byte.

In this particular example of #extendedStoreAndPopBytecode uses 2 bits for a type and 6 bits for an index:

extendedStoreBytecode
| descriptor variableType variableIndex association |
<inline: true>
descriptor := self fetchByte.
self fetchNextBytecode.
variableType := descriptor >> 6 bitAnd: 3.
variableIndex := descriptor bitAnd: 63.
variableType = 0 ifTrue:
[^objectMemory storePointer: variableIndex ofObject: self receiver withValue: self internalStackTop].
variableType = 1 ifTrue:
[^self temporary: variableIndex in: localFP put: self internalStackTop].
variableType = 3 ifTrue:
[association := self literal: variableIndex.
^objectMemory storePointer: ValueIndex ofObject: association withValue: self internalStackTop].
self error: 'illegal store'.
^nil

We can see that in our example, 16r48 = 72.  (72 >> 6) bitAnd: 3  -> 1. So, type is 1. The 3 is because it uses 2 bits for the type (2^2-1=3). And 72 bitAnd: 63 -> 8  (which correctly is the number of temp we need). 63 is because 2^6-1=63.  As you can notice, each bytecode is responsible of decoding the information of the second byte. The compiler of course, needs to correctly generate the bytecodes. #extendedStoreAndPopBytecode was an example so that you can understand and learn, but there are much more extended bytecodes. There are even “single extended bytecodes” and “double extended bytecodes”.

Why do we need extended bytecodes?

Well, I am not an expert at all in this subject but I can guess it is because of the size of CompiledMethod. In the previous example of the extended bytecode, it uses two bytes instead of one, as we can see in the explorer:

Notice that bytecode number 27 occupies two (28 is not shown). At the beginning we saw that when we have a “range” in the bytecodes it means that the difference encodes a number, usually an index. But if we need a range of bytecodes for the maximum supported, we would need much more than 255. Hence, more bytes per bytecode.  Since most methods in Smalltalk are short and encode few number of instance variables, parameters, temporal variables, etc, it was decided to use 255 and just use more bytes per bytecode for those cases that was needed. For example:

(CompiledMethod allInstances select: [:each | each numTemps > 7]) size  -> 1337
CompiledMethod instanceCount -> 75786
((1337 * 100) / 75786) asFloat -> 1.7641780803842397

So…only a 1.76% of the CompiledMethod of my image have more than 7 temporal variables. And remember that this was just an example, but there are extended bytecodes for more things. Maybe (I have no idea) with today computers this is not worth it and maybe having 3 or 4 bytes for every bytecode is enough. But since it is like this and working correctly, why to change it?

Groups of bytecodes

Since the specification of the blue book of Smalltalk-80, bytecodes are known to be grouped in different groups. And since the core of Squeak/Pharo VM is implemented in a subset of Smalltalk called SLANG and since we have classes with methods that represents Interpreters….how would these groups be represented? Of course, as method categories!!! So, you can map each of the following group, with a method category of an Interpreter class:

• Stack manipulation bytecodes: all things related to push and pop.
• Message sending bytecodes: bytecodes that are used when sending messages.
• Return bytecodes: are used for different kinds of return.
• Jump bytecodes are related to conditionals

Look the attached screenshot:

Books and links

In this post it is easy: just read the blue book 🙂   As always, you can download it in pdf from http://stephane.ducasse.free.fr/FreeBooks.html or directly browse the web version provided by Eliot Miranda. For a bytecode introduction read the end of chapter 26  and for more details the whole chapter 28. Notice that the specification has changed a bit from the 80’s and there are now there are more bytecodes but the general idea is still valid.