CS 39 -- Virtual Machine Description

Overview

The instruction format is designed to be simple for the virtual machine to decode and for a user to read. It is not like a real machine code format in that it is human-readable bytes of text. As a result, though, the machine code format looks much like assembly code.

Note that this instruction format is also not as extensive as a real instruction set would be. For example, only integer manipulation is directly supported -- no floating point numbers.

Although it is simple, this instruction set is sufficient to perform significant computations. Therefore, it will allow us to create short- and long-lived processes that are performing actual computation. This page documents the instruction set, including the registers that can be used as well as the interrupts and interrupt handling mechanisms.

The register set

Below are listed the registers available for this machine.

• There are 32 addressable registers. These may be put to any use, and a process should be able to rely on them across context switches. Note, however, that assembly convention assigns specific uses to these registers as follows:
  1. Register 0 (%zero) is the zero register which always holds the value 0. Attempts to assign other values into this register will fail silently.
  2. Register 1 (%sp) is the stack pointer.
  3. Register 2 (%fp) is the frame pointer.
  4. Register 3 (%ra) holds the return address for the CALL instruction (see the instruction listing below).
  5. Registers 4 - 7 (%s0 - %s3) are the system registers. These hold values used for communication between a process and the kernel, including arguments and return values for system calls. While programs are not prevented from using these registers, their content may be overwritten at any moment by a trap.
  6. Registers 8 - 15 (%a0 - %a7) are the argument registers used for passing arguments during function calling.
  7. Registers 16 - 23 (%t0 - %t7) are the temporary registers. These are not preserved on a function call, and can be used for anything.
  8. Registers 24 - 31 (%g0 - g7) are the general registers. These also can be used for anything, but are expected to be preserved at function calls.
• The program counter (pc) register points to the current instruction in the executable image loaded into memory. Note that the PC value is an offset into the memory space of the process. That is, to obtain the actual address of the current instruction, this value is added to the base offset (see below).
• The trap base register (tbr) register holds the trap base address, which is the address at which the trap table begins. This table contains pointers to the various kernel trap handlers.
• The clock register holds the count of the number of cycles (that is, fetch-decode-execute cycles) performed since the processor was initialized.
• The base and limit registers which mark the lower and upper valid addresses for the currently running process.

Traps and trap register values

Below are listed all of the traps that the virtual machine may generate, and that the kernel may receive. Along with each trap, we provide the offset into the trap table (that is, the trap table entry number) for that trap. In that trap table entry must be a pointer to the kernel trap handler function for that type of trap. We also list, for each trap, the values placed into the system registers (%s0 - %s3) before execution is vectored into the kernel.

• System call trap, offset = 0: This trap allows the process to request a particular service from the kernel. It is essentially a requested interrupt. The system registers are expected to contain the following values:
  • %s0: System call number, which is a code that indicates which service the process is requesting. The mapping of codes to services is provided by the kernel.
  • %s1 - %s3: Arguments 1 - 3, which is a value interpreted differently by each system call service. The kernel determines which of these are used for a given system call.
• Clock interrupt trap, offset = 1: This trap occurs so that the kernel is guaranteed control periodically.
  • %s0 - %s3: Unused.
• Memory access trap, offset = 2: This trap is the result of an attempt to access (via memory access or branching instruction) a memory location that is not valid.
  • %s0: The opcode of the offending instruction.
  • %s1: The address that the instruction was attempting to access.
  • %s2 - %s3: Unused.

Advancing the PC

The processor will normally advance the PC to the next instruction after executing the current instruction. However, there are some circumstances under which the PC is not advanced. These are the exceptions:

1. An invalid instruction interrupt occurs. These are raised when an opcode cannot be decoded, or when the operands provided are not valid.

2. An invalid memory access interrupt occurs. If an instruction fetch, load, or store attempts to use an invalid address, this interrupt is generated.

3. A successful branch or jump occurs. When such an instruction succeeds in setting the PC to a new value, that new PC value is not incremented.

In all other circumstances the PC is advanced. Note that the setting of the PC by the kernel does not form an exception to its normal advancement.

Instruction format

Each instruction is exactly 32 bytes, irrespective of the instruction used. The simple multiplication of two constants, in machine code format, would look something like this:

STRI 00000005 103ef200 00000000
STRI 0000001c 00000004 00000000
MULR 0000000b 00000005 0000001c
    

• Line 1: Use the STRI instruction (SeT Register from Immediate value) to set register 0x5 (where the prefix 0x means that the number which follows is in hexidecimal) to hold the value 0x103ef200. Note that the third operand is ignored by this instruction.
• Line 2: Use the STRI instruction again to set register 0x1c to 0x4.
• Line 3: Use the MULR instruction (MULtiply Register values) to multiply the values found in registers 0x5 and 0x1c; store the result in register 0xb.

More generally, notice the common characteristics of every instruction:

• Each begins with a four character opcode.
• The opcode is followed by a single space character.
• Next is an eight character, hexidecimal operand.
• The first operand is followed by a single space character.
• Next is a second eight character, hexidecimal operand.
• The second operand is followed by a single space character.
• Next is the third and final eight character, hexidecimal operand.
• The final operand is followed by a newline character.

This exact format must be followed. If it is not, then the decoding component of the virtual machine will likely get confused, and complain that some part of the code contains an illegal instruction, an illegal address, or an invalid register number.

(Note that, technically, the space characters between the opcode and operands could be any character, including, say, a tab character. There must be *some* character, though, that the decoder can skip before examining the next piece.)

Instruction Index

Below is a catalog of instructions and their associated interpretation of the operands that follow. Specifically, in each description, we will refer to the opcode, as well as operand-0, operand-1, and operand-2.

• SYSC -- SYStem Call

  This instruction generates an intention interrupt that forces the processor to trap into the kernel. It is the method by which a program can perform an unusual kind of procedure call, where the procedure is inside the kernel and the arguments are passed in the system registers.

  All three operands are unused by this instruction. However, the setting of the system registers are the means of communication to the kernel. The convention for how these registers are used are determine by the kernel itself, which may define how values are passed into and returned from the system call.

• STRR -- SeT Register from Register

  Copy a value from one register into another. Set register operand-0 to hold the value contained in register operand-1.

• STRI -- SeT Register from Immediate

  Copy an immediate value into a register. Set register operand-0 to hold the immediate value operand-1.

• LOAD -- LOAD from main memory into register

  Copy a value from a main memory location into a register. The main memory address is computed by adding register operand-1 to immediate operand-2. The value at this address is copied into register operand-0. Note that the address must be a word-aligned location.

• STOR -- STORe from register into main memory

  Copy a value from a register into a main memory location. The main memory address is computed by adding register operand-1 to immediate operand-2. The value in register operand-0 is copied into this address. Note that the address must be a word-aligned location.

• ADDR -- ADD Register to register

  Add register operand-1 to register operand-2 and store the result in register operand-0.

• ADDI -- ADD Immediate to register

  Add register operand-1 to immediate operand-2 and store the result in register operand-0.

• SUBR -- SUBtract Register from register

  Subtract register operand-2 from register operand-1 and store the result in register operand-0.

• SUBI -- SUBtract Immediate from register

  Subtract register operand-2 from immediate operand-1 and store the result in register operand-0.

• MULR -- MULtiply Register and register

  Multiply register operand-1 with register operand-2 and store the result in register operand-0.

• MULI -- MULtiply Immediate and register

  Multiply register operand-1 with immediate operand-2 and store the result in register operand-0.

• DIVR -- DIVide register by Register

  Divide register operand-1 by register operand-2 and store the result in register operand-0.

• DIVI -- DIVide register by Immediate

  Divide register operand-1 by immediate operand-2 and store the result in register operand-0.

• ANDR -- AND bitwise Register and register

  Bitwise AND register operand-1 with register operand-2 and store the result in register operand-0.

• ANDI -- AND bitwise Immediate and register

  Bitwise AND register operand-1 with immediate operand-2 and store the result in register operand-0.

• ORR_ -- OR bitwise Register and register

  Bitwise OR register operand-1 with register operand-2 and store the result in register operand-0. The trailing underscore (_) is critical to ensure a four-byte opcode.

• ORI_ -- OR bitwise Immediate and register

  Bitwise OR register operand-1 with immediate operand-2 and store the result in register operand-0. The trailing underscore (_) is critical to ensure a four-byte opcode.

• NOTR -- NOT bitwise Register

  Bitwise NOT register operand-1 and store the result in register operand-0.

• NOTI -- NOT bitwise Immediate

  Bitwise NOT immediate operand-1 and store the result in register operand-0.

• SHRL -- SHift Register Left

  Shift register opcode-1 by the number of bits specified in immediate opcode-2, and store the result in register opcode-0. Note that bits with the value 0 are inserted into the word from the right end.

• SHRR -- SHift Register Right

  Shift register opcode-1 by the number of bits specified in immediate opcode-2, and store the result in register opcode-0. Note that bits with the value 0 are inserted into the word from the left end.

• JMPR -- JuMP Register

  Jump to the address in register opcode-0. This instruction causes the virtual machine to set the program counter to the new address in the executable.

• JMPI -- JuMP Immediate

  Jump to the address in immediate opcode-0. This instruction causes the virtual machine to set the program counter to the new address in the executable.

• BREQ -- BRanch if EQual

  If register opcode-1 is equal to register opcode-2, jump to the address in immediate opcode-0.

• BRNE -- BRanch if Not Equal

  If register opcode-1 is not equal to register opcode-2, jump to the address in immediate opcode-0.

• BRGT -- BRanch if Greater Than

  If register opcode-1 is greater than register opcode-2, jump to the address in immediate opcode-0.

• BRLT -- BRanch if Less Than

  If register opcode-1 is less than register opcode-2, jump to the address in immediate opcode-0.

• BRGE -- BRanch if Greater Than or Equal

  If register opcode-1 is greater than or equal to register opcode-2, jump to the address in immediate opcode-0.

• BRLE -- BRanch if Less Than or Equal

  If register opcode-1 is less than or equal to register opcode-2, jump to the address in immediate opcode-0.

• CALL -- CALL a procedure

  Jump to the address in immediate opcode-0. Before jumping, store PC + 32 (that is, the address of the next instruction) into the return address register (%ra).