Logical shift Project home

Analysis: Bytecode design

This section begins with a brief discussion of pre-existing bytecode interpreters that are in current practicle use. Although the literature is full of articles discussing improvements and modifications that can be made to bytecode languages, it is remarkable poor in articles discussing the design of the languages themselves. This discussion will focus on zcode, one of the earliest examples of a portable bytecode language, and the byte code used by Moscow ML (itself a variant of that designed for Caml light). Tied up with the definition of the bytecode language is the definition of the virtual machine it will run under.

A study of existing bytecode languages

ZCode[8]

ZCode was designed by the company Infocom in 1979 and was designed to allow the cross-platform execution of text adventure games. Of particular concern to its designers was the design of the target platforms. The home computers that were emerging at that time were very limited in terms of memory, processor power and permanent storage space. To solve these problems, some complex operation were designed to be executed by the interpreter (notably the parsing of an input string), and the language incorporates several special-purpose structures for their support (dictionaries and grammar tables).

Briefly, ZCode runs on a virtual machine called the Z-Machine. This is a virtual 16-bit computer, which, owing to its long history of adaptations to improving computer hardware, has a complex structure. Version 8 is the most recent revision of the Z-Machine (although this revision was created by Graham Nelson after Infocom had ceased trading). Its architecture specifies three memory areas - 'Dynamic' memory, whose initial contents are specified in the file, but which may be changed at runtime, 'Static' memory, which follows dynamic memory and may not be changed, and 'High' memory, which follows the Static memory and may break the 64k boundary that is imposed on Static and Dynamic memory. In games compiled using Inform, dynamic memory is used for storing the object tree, object properties, global variables and arrays. Static memory stores various constant tables, and high memory contains the code and any static strings. The design of Z-Code really prohibits anything apart from strings and code being stored in high memory, as regions beyond the 64k marker do not have suitable load/storage commands in the Z-Code language, and are accessed using a special 'packed format' address (a 16-bit value), which is transformed by a formula to find the real address. The formula has tended to change between Z-Machine versions, but in version 8, it is simply the packed value multiplied by 8.

Figure 1 - design of the Z-Machine

Z-Machine instructions that take operands, for example add, can take their operands as constants or variables. Local variables, numbers 1-15, are allocated by the Z-Machine onto the stack when a routine is entered. Global variables, numbers 16-255 are allocated in dynamic memory, and the special variable number 0 can be used to refer to the number on the top of the stack. This design takes the business of allocating space for variables away from the compiler, but imposes limits on the number of variables that can be sensibly maintained. The Z-Machine has no registers and no accumulator; often bytecode languages are written to just manipulate the stack. This design style makes the design of compilers easier, as stack maintainance is the responsibility of the interpreter.

A Z-Code program is divided up into routines that may be accessed using the call directive. A routine is accompanied by a set of data that details things like the number of local variables. Branch operations are restricted to inside the routine.

Z-Code provides many types of instructions, which can be broadly placed into several groups:

Arithmetic instructions

Operations such as add, sub(tract) and mul(tiply). These operations typically have three parameters - two operands and a destination. The destination has to be a variable (or the top of the stack). Note that logical operations such as and are included in this group.

Memory operations

These operations deal with loading and storing values to and from dyanmic and static memory.

Stack operations

These operations help manipulate the stack - push new values on, or pop old values off. Note, in Z-Code, pop takes no operands and discards its result (pull provides the ability to store the popped value somewhere)

Branch operations

In Z-Code, these operations double as comparason operations as well. They perform a comparason and branch to a new location if the result of the comparason is true.

Routine operations

These operations branch to and return from Z-Code 'routines'. A Z-Code routine is analogous to a function in a language like C. There are several of these operations in Z-Code, probably owing to its heritage, but they all push the current program counter onto the stack, allocate space for the new routine's global variable, and branch to the new routine (return is an exception here, as it returns to the old routine, popping the PC that was pushed to do so)

Miscellaneous operations

These operations include such things as print and read, that access facilities in the virtual machine (in this case, the IO subsystem). While there is no common theme, they are mostly routines that would be implemented by a library in a 'traditional' system.

The Z-Machine Standards Document[8] goes into far more detail about the Z-Machine's design, and I will not continue to discuss the minutae of the machine's design. It does, however, have one noteworthy feature - it can save complete details of its internal state to a file (dynamic memory, the stack and the current program counter), and restore that state on demand. This is a feature that is almost unique on this low-level, and which is very applicable for operating systems such as PalmOS, which requires such a state save when the user switches applications.

Moscow ML/Caml Light

Moscow ML[9] is an implementation of standard ML based around Caml Light[10]. Design documentmentation for these languages does not seem to be readily available, so this discussion is based on analysis of the source code of Moscow ML 2.00. The bytecode was originally designed as an intermediate code between the ML compiler and interpreter, but is now also employed as a format for pre-compiled programs, as well as the format which the Moscow ML bootstrap compiler is written in.

The bytecode in Moscow ML is very obviously of an ad-hoc design. Each code is represented using one byte followed by a variable amount of data. The 'virtual machine' used by Moscow ML consists of a program counter, a stack and an accumulator. (Caml Light, for contrast has two stacks - one for arguments and one for return values). Arithmetic operators use the accumulator and the value on top of the stack, and store their results back into the accumulator.

The accumulator is a 32-bit int (actually, a long int, but it is apparent that the designers intended this to be 32-bits), and the stack is a list of 32-bit ints. The design of the stack is full-descending, although this is never exposed to the bytecode. The bytecode tends to use multiple instructions rather than arguments, possibly for reasons of performance (saving a read of an argument), but this means that the list of codes is very long. For instance, there are 8 different ACC commands - these commands set the accumulator to a value on the stack. ACC0 sets the accumulator to the top value (no popping is performed), to ACC7, which sets the accumulator to the value seventh from the top of the stack. This design may increase execution speed, but it starts to become limiting.

The bytecode commands employed by Moscow ML fit into the same categories as the ZCode commands, although there are multiple varieties of some commands (such as ACC, and also many different types of arithmetic operator - ADDINT, SMLADDFLOAT, and SMLADDINT, for instance). Overall, much of its design may be too limiting for the design of this bytecode.

Virtual Machine design

The virtual machine's design is based around Z-Code, and also the memory models used in current computers. The memory has addresses from 0x0 to 0xfffffff (4 gigabytes), but no address can be accessed until memory has been allocated to that space. The bytecode program itself is stored outside that memory, and so cannot be altered while running. The bytecode program may contain an amount of 'static' memory, which is placed beginning at virtual address 0x0. It may also contain some pre-initialised settings for dynamic memory - this is placed after the static memory ends. It may also request that more memory be allocated later on.

Many current processors have a 32-bit address bus, and are most efficient at reading values that are stored aligned to a 4-byte boundary. 4-byte values will be referred to as words from now on. Static and dynamic memory size must be a multiple of 4, and 32-bit and higher values must be aligned to a word boundary. This design descision also eases the design of the interpreter for processors with these constraints.

Also present is a stack, which is also kept seperate from the main memory, and is used to store local variables, routine return addresses and intermediate values in calculations. In a secure implementation, the interpreter will check that a routine does not attempt to leave its stack 'frame', that is, pop values that come before its return address.

There is no accumulator or registers as such - all values being processed are stored in dynamic or static memory, or on the stack. Arguments to an operation that uses stack values will use a short notation that is faster to process than the notation used to store memory addresses.

Bytecode instruction set

The tables here indicate the instruction, the number of arguments and a suggested syntax for a disassembly. An instruction may take arguments, which can be a constant ('immediate') value, a reference to the top of the stack (which is popped, or pushed if a destination argument), a reference to a local variable, a direct reference to a memory location or an indirect reference to a memory location. When manipulating the stack, values are popped from left to right.

For example, the instruction ADD (stack) (stack) -> (stack) will pop two values from the stack, compute the result, and push the answer onto the top of the stack. The other addressing modes are covered more fully in the section on bytecode encoding.

Keeping to the categories outlined in the analysis of ZCode design above, the instructions supported will be as follows:

Arithmetic operations

Table 1 - arithmetic operations

Memory operations

These operations handle the allocation and deallocation of memory. Note that load/store operations are handled by the data transfer instructions (MOVE, MOVES, MOVED) with memory address arguments. Unless stated otherwise, all arguments are 32-bit integers.

Table 2 - memory operations

Stack operations

These instructions are synonyms for the MOVE* instructions.

Table 3 - stack operations

Branch operations

As for ZCode, these instructions also serve as the comparason operators. All branch locations are a 32-bit twos complement number, and they represent an offset from the location of the branch instruction. The comparason operators listed here are the 32-bit integer versions. All of the comparason operations have floating point equivalents, their names being formed by postfixing S or D to their integer equivalent (as for the floating point operations).

Table 4 - Branch operations

Routine operations

These operations deal with entering and leaving 'routines'. These correspond to functions in a high-level language. The 'TRAP' and 'TRAPPOINT' instructions allow for a language to implement exceptions, both generated by the program, and generated by internal errors (such as floating point errors).

Table 5 - Routine operations

Miscellaneous operations

There is only one miscellaneous operation allocated for this language:

Table 6 - Miscellaneous operations

Bytecode encoding

Due to the width of the address bus on many modern processors, reading memory in 32-bit chunks is generally much quicker than reading it a byte at a time. (Some processors, such as the ARM, have designed their instruction sets around this fact). Consequently, all instructions will be aligned to word addresses to take maximum advantage of these architectures (future systems may use 64-bit or 128-bit words - these systems may need further optimisation depending on their architecture and compiler designs). Where a value is intended to be read as a complete word, the value is little-endian. Note that operations on blocks 32-bits or larger must be to word-aligned locations (local variables and the stack are always kept word-aligned).

An instruction is encoded as a single byte indicating its type, followed by a variable number of bytes indicating its arguments, possibly followed by a selection of bytes and words that indicate more detail about its arguments (constants, for example)

For instructions that can take variable numbers of elements, the first argument byte indicates the number of following arguments (so these instructions are limited to a maximum of 255 arguments). Instructions which take a fixed number of arguments do not have this value. The rest of the arguments can have a value as follows:

Table 7 - Argument types

For argument values that require more information (1, 2, 3, 4 and 5), this information is encoded into two blocks that follow the instruction. The first of these blocks incorporates data that is represented by a single byte, and the second incorporates data that is represented by words (this block is word-aligned). The encoding for these types is as follows:

Table 8 - Additional data required by argument types

Values are pushed onto both blocks in a left to right manner, so if an instruction has (for example), one constant value, one indirect value and one stack value, the byte block will contain 2 bytes corresponding to the second argument, and the word block will contain 1 word corresponding to the constant followed by 2 words corresponding to the indirect value. The byte block will also contain some bytes of padding to ensure that the word block is word aligned (in this case 2, as the instruction uses 1 byte, followed by 3 bytes indicating the argument types, followed by the 2 bytes of the byte block. From this point, the next word aligned position is 2 bytes away)

Figure 2 - layout of a typical instruction

Bytecode files have some additional information stored in them to initialise the static and dynamic memory areas, and to give information about the version of the file itself. All offsets are in bytes unless otherwise stated.

The files start with a header:

Table 9 - Header stored in bytecode file

The routine table indicates the properties of routines that may be accessed using CALL. Execution begins by calling routine 0 (which can take no arguments), and ends when this routine returns. The routine table consits of a list of entries in the following format. The first entry describes routine 0, and successive entries describe successive routines. If a file is not intended to be run, routine 0 should reference offset 0.

Table 10 - Format of an entry in the routine table

The symbol table is used to resolve references (argument type 6) at run- or link-time. A reference can either be to a routine or a memory location. The table consists of a list of entries, each with the following format. Memory references are dereferenced as direct memory accesses, and routine references are dereferenced as constants:

Table 11 - Format of an entry in the reference table

Finally, the opcodes described in the previous section need to have numbers assigned:

Table 12 - Opcode numbers