CSE378 Fall 1998 Homework 4

CSE378 Fall 1998 Homeworks 5/6

DUE: Homework 5 - November 9; Homework 6 - November 16

Java is a general purpose high-level programming language, initially developed to address the problems of building software for networked consumer devices. It was designed to support multiple host architectures, in such a way that compiled Java code could be transported over a network, from one machine to another. It is the ease with which compiled Java code can be transferred over a network that has made Java a particularily attractive programming language for Web browsers.

The Java Virtual Machine (JVM) is the cornerstone of the Java programming language. It is the component of Java technology that is responsible for the cross-platform delivery, and for the small size of compiled Java code. The task of a Java compiler is to convert the high-level Java language into JVM bytecodes, and these bytecodes are the compiled form of the language that is then transferred over the network.

The JVM is an abstract computing machine. Like a real computing machine, it has an instruction set and uses various regions of memory. However, the JVM does not assume any particular implementation technology or host platform. The particular implementation technology that we will investigate in this assignment is direct interpretation (simulation).

For this assignment, we will build an interpreter for a set of byte codes, much like the JVM (although, based on a smaller set of instructions, to make it do-able). Just as SPIM provides an interpreter for the MIPS instruction set, we will build an interpreter that processes the bytecodes described in the below table.

Instruction Bytecode Byte Format Stack Ops Description

IADD 0x60 IADD POP v1, POP v2, PUSH result Integer add

ISUB 0x64 ISUB POP v1, POP v2, PUSH result Integer subtd

IMUL 0x68 IMUL POP v1, POP v2, PUSH result Integer multiply

IDIV 0x72 IDIV POP v1, POP v2, PUSH result Integer divide

ILOAD 0x15 ILOAD index PUSH result Load from local variable at index

ISTORE 0x36 ISTORE index POP v1 Store to local variable at index

PUSH 0x10 PUSH immed1 PUSH v1 rPush value

POP 0x57 POP POP v1 Pop value, discard

IFEQ 0x99 IFEQ offset1 POP v1 Branch on v1 == 0

IFNE 0x9a IFNE offset1 POP v1 Branch v1 != 0

IFLT 0x9b IFLT offset1 POP v1 Branch on v1 < 0

IFLE 0x9e IFLE offset1 POP v1 Branch on v1 <= 0

IFGT 0x9d IFGT offset1 POP v1 Branch on v1 > 0

IFGE 0x9c IFGE offset1 POP v1 Branch on v1 >= 0

GOTO 0xa7 GOTO offset1 none Unconditional branch

IRETURN 0xac IRETURN POP v1 Integer return

Instruction	Bytecode	Byte Format	Stack Ops	Description
IADD	0x60	IADD	POP v1, POP v2, PUSH result	Integer add
ISUB	0x64	ISUB	POP v1, POP v2, PUSH result	Integer subtd
IMUL	0x68	IMUL	POP v1, POP v2, PUSH result	Integer multiply
IDIV	0x72	IDIV	POP v1, POP v2, PUSH result	Integer divide
ILOAD	0x15	ILOAD index	PUSH result	Load from local variable at index
ISTORE	0x36	ISTORE index	POP v1	Store to local variable at index
PUSH	0x10	PUSH immed1	PUSH v1	rPush value
POP	0x57	POP	POP v1	Pop value, discard
IFEQ	0x99	IFEQ offset1	POP v1	Branch on v1 == 0
IFNE	0x9a	IFNE offset1	POP v1	Branch v1 != 0
IFLT	0x9b	IFLT offset1	POP v1	Branch on v1 < 0
IFLE	0x9e	IFLE offset1	POP v1	Branch on v1 <= 0
IFGT	0x9d	IFGT offset1	POP v1	Branch on v1 > 0
IFGE	0x9c	IFGE offset1	POP v1	Branch on v1 >= 0
GOTO	0xa7	GOTO offset1	none	Unconditional branch
IRETURN	0xac	IRETURN	POP v1	Integer return

Storage

The JVM is a stack machine. This means that instructions implicitly use a stack to fetch their operands and to store their results. The Stack Ops column in the above table describes the implicit stack operations performed by each of the above instructions. In addition to the stack, the JVM also provides local variable storage. The local variable storage is accessed by the ILOAD and ISTORE instructions described below.

Instruction Details

The arithmetic instructions (IADD,ISUB,IMUL,IDIV) all operate on signed 8-bit integers, but none of them should generate overflow exceptions when overflow occurs. For ISUB, the result is (v2 - v1), and for IDIV, the result is v2 / v1, whereas for IADD and IMUL the operand order does not matter.

The local variable instructions (ILOAD,ISTORE) are each followed by an 8-bit unsigned index value which determines the location within the local variable array that should be read or written. You may assume that there are no more than 256 local variables, and you do not have to check that the index is valid (although a real JVM interpreter would have to perform this check). Each entry in the local variable array is a 8-bit word.

The PUSH instruction is followed by a 8-bit signed immediate value. The immediate value is sign extended to a 8-bit integer, and then pushed on to the stack. The 8-bit result of the POP instruction is simply discarded.

The branch instructions (GOTO,IFNE,IFEQ,IFLE,IFLT,IFGE,IFGT) are followed by a byte which specifies a signed offset relative to the start address of the branch instruction. All of the comparison operations for the above conditional branch instructions are signed comparisons.

The IRETURN instruction signals the end of the computation (our simplified model of the JVM only handles interpreting a single Java method). The 8-bit value at the top of the stack is popped and then used as the return value.

What we provide for you:

We provide the file javamain.s which contains the main routine that you will use to invoke your interpreter. You'll need to copy this file from /cse/courses/cse378/1998au/.
Our javamain.s program allocates the array where the program is stored, as well as the storage for the java operand stack and the storage for the local variable array. You can assume that the JVM test programs will not exceed the resources that we've allocated for you.
Within javamain.s, we provide a sample test program for your interpreter. When you create new JVM test programs, you'll need to edit the javamain.s file, and you should use our sample test program as a model. Also, if you want to rename the "java_interpret" routine to have a different name, you'll need to edit javamain.s. The interface between "main" and "java_interpret" is detailed in the javamain.s file.

What you need to do:

Homework 5:

Build your JVM interpreter (an implementation of the "java_interpret" routine) which handles the following instructions from in the above table: IADD, ISUB, IMUL, IDIV, PUSH, POP, and IRETURN. The basic structure of your interpreter should be a loop that looks something like the following:
- fetch the next bytecode
- decode the operation
- fetch the operands
- execute the operation
- store the results
Implement your interpreter using MIPS subroutines, and follow the MIPS calling convention. This means that you should not implement your solution as one monstrous subroutine. If you do, your solution will be more difficult for me to read, and the total amount of code you have to write will be more than necessary.

Homework 6:

Implement the remaining instructions in your interpreter.
Make sure that your interpreter handles the following error conditions gracefully:
- Stack underflow: when a bytecode needs to get its arguments from the operand stack, but the operand stack does not contain enough operands to perform the operation, then the interpreter should print an error message and terminate the computation. The return value from the java_interpret routine in this case should be -1.
- Illegal Operation: when the operand decoded by the interpreter is not one of the ones listed in the table above, then the interpreter should print an error message and terminate the computation. The return value from the java_interpret routine in this case should be -1.
Build some programs to test your interpreter. Build programs following the model of test1 in javamain.s At the top of your code, clearly indicate, in comments, the names of these programs and what they are expected to do. Included in these should be a program which computes the nth fibonacci value, where n is on top of the stack. Make sure that every instruction listed above is used in at least one of your test programs.