CS232, Spring 2008

Wombat Programming assignments W5-1 & W5-2

due Friday, April 4

The Wombat5 Computer

Create the Wombat5 from the Wombat4 by adding subroutine calls and indexed addressing versions of the load and store instructions. To do so, you will need to add "call", "return", "loadi", and "storei" machine instructions.  Give them opcodes D, E, F, and 10 (all in hexadecimal), respectively. The call instruction has format "op relAddr11", the return instruction has format "op un11", and the loadi and storei instructions have format "op reg delta5[reg]".

To create such formats, you will need to create some new fields:

1. A field "relAddr11" which is identical to the relAddr field except it uses 11 bits instead of 8
2. A field "delta5" which is identical to the delta8 field except it uses 5 bits instead of 8.
3. Two fields "[" and "]" that are required and use 0 bits (the other parameters don't matter).

In assembly language, the call instructions are of the form "call mysub" where "mysub" is a label on the first line of the subroutine.  The call instruction's execute sequence should push the return address (RA) on the Stack and then jump to the beginning of the subroutine.  The starting address of the subroutine is stored in the last 11 bits of the call machine instruction in relative addressing mode, just like the jump instructions use. That is, the last 11 bits actually store the offset of the start of the subroutine from the instruction following the call instruction.  The return instruction is just "return" with no operands.  The return instruction's execute sequence should pop the return address off the top of the Stack and then jump to that address.

When the subroutine begins execution and needs an argument for a computation, it will need to load the argument from the stack into a register.  To do so, it should use the "loadi" instruction.  The loadi instruction uses "indexed" addressing in that it takes a 3-bit operand indicating the index of the A register into which the data is to be loaded and a 5-bit offset (a 5-bit 2's complement positive or negative integer) and a 3-bit operand indicating a second A register. The instruction finds the address (on the Stack) of the data to be loaded into the first register by adding the offset to the contents of the second register  For example, to load into A[1] the data at the top of the stack, your instruction would look like "loadi A1 0[A7]", since the stack pointer always contains the address of the topmost value on the stack.  Offsets from A7 should always be zero or a negative even integer--that is, you should never access data past the top of the stack.  Similarly for storei instructions.

One of the significant advantages of indexed addressing in that it allows access to the data on the stack without having to pop the data off.  As a result, almost the only time pushing is needed is when you need to push arguments for a subroutine before calling it.  Similarly, almost the only time popping is needed is when a subroutine is about to return and it needs to pop the data it used off the stack.

Keep in mind that a routine must be as self-contained as possible and, in particular, it must specify in a header comment what data it needs as parameters (and in what order) and what result it produces.  For example, the subroutine you are asked to write in Exercise W5-1 below should have a header such as:

;; function mod
;; parameters:  integers n and m
;; returns:   n % m

A subroutine should never assume anything about the routine that called it (even in the case of recursion) other than the fact that the caller pushed the parameters for the subroutine in the correct order and pushed the return address on the stack.  Also, a routine should never assume anything about any subroutine it calls (even itself) other than what is specifically addressed in the subroutine's header comment.  In particular, if the header says nothing about the A registers, then the caller of the subroutine should not assume anything about how the called subroutine uses the A registers.  In particular, a caller should not assume that values that were in the A registers before a subroutine was called will still be there after the subroutine returns. Therefore if a routine has any values in the registers that it needs to use again after it calls a subroutine, it better store them on the stack in a local variable before calling the subroutine and load them back into the registers after the subroutine returns.

A good check to see whether your subroutine is as self-contained as possible is to cut and paste it into a different program and see whether it still works correctly.

Each routine (the main routine as well as subroutines) operates in a "stack frame", which is a set of consecutive stack addresses that the routine is allowed to access.  A stack frame for a routine on the Wombat5 has three parts:

      (a)  space at the bottom for all parameters,
      (b)  space in the middle for the return address,
      (c)  space at the top for local variables (if any)

When a routine wants to call a subroutine, it must push the values for the parameters for the subroutine onto the stack in the order the subroutine expects them.  Then it must execute the "call" instruction, which pushes the return address on the stack.

Then the subroutine can, if it wishes, push space on the stack for any local variables.

Similarly, just before the subroutine is to return--when it needs to dispose of its stack frame--it should pop the whole stack frame except for the return address and, if it is a function, the value to be returned by the function.  That is, a subroutine should leave only the return address on top of the stack before returning, unless it is a function, in which case it must also leave its return value on the stack just below the return address.  So, as noted above, the caller is responsible for pushing the arguments for the subroutine onto the stack, but the called subroutine is responsible for popping those arguments off the stack before returning.

• From now on, the only .data pseudo-instructions that are allowed in your code are those that store constants that are to be treated as read-only.  All non-constant variables are stored on the Stack in a stack frame and so, from now on, writing to Main memory is not allowed except for IO.  In other words, the load instruction, which still refers to the Main memory, may be used to access constants in Main memory, but the store instruction, which also refers to Main memory, should be used only to write output to IO.
• The subroutines you write need to have a comment header similar to a header you would write for a method in Java. It should include the number and order of the parameters the subroutine expects, a brief description of what the subroutine does (in general terms) and what value the subroutine returns (if any). For example, your fact function in W5-2 (described below) should have a header something like the following:

  ;; function fact 
  ;; parameter: a positive integer n 
  ;; returns: n factorial
  ;; It crashes if n < 0. 

• Your subroutines should only get data from and pass data back to their callers by way of the Stack. That is, your subroutines should not expect any particular values to be in any of the registers (except A7) when they start executing. To check this, I will take your subroutine, copy it from your code, and paste it into my code using my own main program. My main program may use different registers for different purposes and so, if your subroutine assumes certain values are in certain registers when it starts, it will not work correctly. Similarly, the main program should not assume a subroutine leaves a particular value in a register when it returns.
• Don't add any extra parameters to your subroutines. I want them to follow the format I gave you in the assignment. You can, however, add as many local variables as you want.
• Your fact function in W5-2 must be recursive. That is, it shouldn't have any loops and instead should have the following outline:

  fact: <initialize the stack frame and registers>
        <check for n=0 or n=1 and, if so, return 1>
        <otherwise push n-1 and call fact>
        <multiply n and the result of fact(n-1)> 
        <clean up the stack frame and return the product>

• Every subroutine must execute a return statement as the last thing it does. Therefore, for example, a subroutine cannot have a stop command in it, nor can it jump to somewhere outside of its body (such as into the main program or into a different subroutine) using jump or jmpn or jmpz.
• Since stack offsets are now used to refer to local variables or parameters, it is recommended, but not required that you define EQUs in your program to make the code easier to read.  For example, if local variable n is stored 6 bytes down from the stack pointer in the mod subroutine's stack frame in Exercise W5-1, then you should define "n EQU -6", which allows you to write code such as"loadi A1 n[A7]" instead of "loadi A1 -6[A7]", which doesn't tell you what variable is being loaded. These EQUs are used just in this program and so should be defined at the top of the program file instead of as part of the Wombat5's global EQUs.
• Don't leave these programs for the last minute! Recursive programs in assembly language can be confusing.

Test your new Wombat5 machine by writing a program "W5-1.a" that reads in two positive integers n and m and then calls a function subroutine "mod" to compute n % m (i.e., the remainder when n is divided by m), which the main program then writes out.  Remember, the answer calculated by the subroutine should be put on the Stack underneath the return address just before the subroutine returns.  The main program should just read in n and m, call the subroutine, write out the result returned by the subroutine and stop.  It is okay for your program to crash if n or m are negative or zero.  Hint:  It is possible to write your subroutine without any loops or recursion or other forms of iteration.

Exercise W5-2

Write and test a Wombat5 program "W5-2.a" that reads a positive integer n and computes n! (n factorial) recursively using a function fact.  The recursive way to compute fact(n) is as follows:  if n = 0 or n = 1 then fact(n) = 1 else fact(n) = n * fact(n-1).  The main program should just read in n, call fact, output the result returned by fact, and then stop.  It is okay for your program to crash if n < 0. Here is what your main program should look like:

  load A0 IO  ; *MAIN*: read n into A0
  push A0     ; push n onto the Stack as a parameter
  call fact   ; call the fact procedure
  pop A0      ; pop the result returned by fact into A[0]
  store A0 IO ; output it
  exit        ; end of main program

What to hand in

As usual, hand in hard copies of your two Wombat5 assembly language programs. Also create a folder called "W5-1,2.your-last-name(s)", drag a copy of your "Wombat5.cpu" file and your two assembly language program files to that folder, zip the folder up, and attach the zipped file to an email message to me.