CS232, Spring 2008

JVM Programming assignments JVM3-1, 3-2

Due: Wednesday, April 30 at class time

The JVM3

The JVM3 is an enhancement of the JVM2 that allows the user to work with integer arrays.  The JVM3 is constructed by adding one new RAM and three new machine instructions to the JVM2.  The three new instructions are the newarray, iaload, and iastore instructions, with opcodes 0xBC, 0x2E, and 0x4F, respectively.

Arrays in the JVM3 are stored in the heap, which is where dynamic data structures such as objects are stored in the real JVM (and in most other programming languages).  In our case, the heap will be a new RAM that you need to create.

To access the heap, the JVM3 should use the "heap" register, which is 32 bits wide.  The heap register should contain a pointer to (that is, the address of) the next available cell in the heap RAM for allocation to a new object. This heap register has already been added to the JVM2 machine that I gave to you for the previous project.

The newarray instruction is a 1-byte instruction that is used to allocate space on the heap for new integer arrays.  (The newarray instruction in the real JVM is actually a 2-byte instruction and the second byte tells what kind of array to create.  Since we are dealing with only integer arrays, we will use a simpler form of the newarray instruction.)  This instruction pops the top value (call it n) off the stack and uses n as the size of the array (that is, the number of integers that can be stored in the array).  It then allocates 4n bytes for the array (remember that each entry in the array is an integer that needs 4 bytes) from the heap starting at the location pointed to by the heap register and pushes on the stack the value of the heap register, which gives the address of the first array location (that is, the array slot with index 0).  The newarray instruction will then need to increment the heap pointer by 4n so that the heap pointer again points to available heap space for the next new array object to be allocated.

In your JVM assembly language programs, the newarray instruction is typically followed by an istore instruction that stores the array pointer in a local variable.

The iaload instruction is a 1-byte instruction that pushes on the operand stack a value from the array. The iaload instruction pops the top value on the stack to use as the index into the array for the data that is to be pushed on the stack.  The iaload instruction also pops the second-to-top value on the stack to use as a pointer to the start of the array (that is, the address of B[0], if B is the name of the array). For example, if the top of the operand stack contains a 3 and the second-to-top value on the stack contains a pointer to array B, then the iaload command pops those two values from the stack and pushes the value of B[3] on the stack.

The iastore instruction is a 1-byte instruction that stores the top value from the operand stack in an array. The second-to-top value on the stack gives the index into the array where the top stack value is to be stored.  The third-to-top value on the stack contains a pointer to (that is, the address of) the start of the array (that is, the address of B[0], if B is the name of the array). For example, if the top of the operand stack contains a 5, the second-to-top value is a 3 and the third-to-top value is the starting address of array B in the Heap, then the iastore command will pop the three values from the stack and store the value 5 in B[3].

Here is a sample JVM3 program that creates an array of length 4, stores a 9 in location B[3] and then pushes the value of B[3] on top of the stack. It assumes that the sp and lv registers are initialized to 0 and so there is already a slot on the stack for the local variable with index 0.

Exercise JVM3-1

Step 1:  Create the JVM3. You need to create the new Heap RAM and then create the newarray, iaload, and iastore instructions.

Step 2:  Write a JVM3 program that reads in an integer n followed by n more integers. Your program stores the n integers in an array of size n in the heap.  It then uses a findIndexOfMax function to help it find and output the largest of the n integers in the array.  You may assume that n >= 1. 

Details

• The findIndexOfMax subroutine should take two parameters (in addition to the unused 0-th parameter):  the value n (the first parameter) and the starting address of the array in the heap (the second parameter).  It should return the index of the maximum value of the first n values in the array (it should not return the maximum value). For example, if the array is [-3, 1, 5, 4, 2, 0], then the findIndexOfMax function with n = 6 should return 2 (the index of the value 5 in the array). Using the same array, the findIndexOfMax function with n = 2 should return 1 (the index of the largest of the first two values in the array).
• You can assume that the array contains at least one integer if you wish.
• Here is how findIndexOfMax looks in Java:

   public int findIndexOfMax(int n, int[] B) {
     int indexOfMax = 0; //the index of the largest value so far
     for (int j = 1; j < n; j++) {
         if (B[j] > B[indexOfMax])
             indexOfMax = j;
     }
     return indexOfMax;
   }

• Your program should first set up the main program's stack frame by pushing as many 0's as necessary to make room for local variables for the main program, including a local variable that contains n and a local variable that will point to the array.
• Next your program should read in n and create an array B of size n in the heap.  Then it should read in the array values and store them appropriately, storing the first value in B[0], the second value in B[1], etc.  Use the iinc command for incrementing the index as you step through the array. Note that you are supposed to load all n integers into the array before you start searching for the max.
• Next call the findIndexOfMax routine to find the index of the maximum value.
• Finally the main program should output the maximum value in the array (not the index of the maximum value).
• Do not modify the main program's local variable that contains the array pointer or the local variable containing n.  You will, of course, need to modify other local variables.
• The findIndexOfMax function should not modify the array B.
• Note that the findIndexOfMax function should return the index of the maximum value, not the actual address of the maximum value.
• Your findIndexOfMax function should not assume that the array starts at address 0 in the Heap. The function should work correctly regardless of where the array is in the Heap.

Write a JVM3 program that reads in a positive integer n followed by n more integers. Your program stores the n integers in an array of size n in the heap.  It then sorts the n integers in the array in place using the findIndexOfMax function from the preceding exercise and a SelectionSort subroutine.  After it is done sorting, your program writes out the n integers from smallest to largest.

Details

• The SelectionSort subroutine should take two parameters (in addition to the unused 0^th parameter):  the value n (the first parameter) and the starting address of the array in the heap (the second parameter).
• You may find that your program is too big to fit in Main memory.  Feel free to enlarge Main memory (or any other RAM) if you wish.
• As with the preceding exercise, your program should first set up the main program's stack frame by pushing as many 0's as necessary to make room for the local variables for the main program, including a local variable that contains n and a local variable that will point to the array. Next your program should read in n, create an array B of size n in the heap, and then read in the n array values and store them appropriately.  Do not sort as you are reading in the integers. Next call the sort routine to sort the array. Finally the main program should output the array's values in sorted order.
• Do not modify the main program's local variable that contains the array pointer or the local variable containing n.  You will, of course, need to modify other local variables.

General Notes

• I have to read (and grade) your code, so I want you to make it as readable as possible. Therefore, it is extremely important that you have well-organized and well-documented code if you want to maximize the credit you will receive. The harder it is for me to read and understand your code, the fewer points you will get for it, even if it works correctly!
• It is very helpful, for readability, to have EQU's for each local variable.  For example, if n is stored in local variable 1, then add a statement "n EQU 1" to your code.  Then whenever you want to load n, you can write "iload n" instead of "iload 1". The former is far more readable than the latter.
• You are welcome to work by yourself or with another student (a team of two) for Exercises JVM3-1 and JVM3-2.

Please hand in a hard copy of your JVM3-1 and JVM3-2 assembly language code, create a folder called "JVM3.your-last-name(s)", drag a copy of your JVM3.cpu machine file and your two assembly code files into that folder and then zip up the folder and attach it to an email message to me.