Spim versions

Some of you told me that my MIPS examples do not run on the PC version of spim downloaded from the class web page. The PC versions I uploaded were version 6, but the lab machines use version 4. I found that the problem is not that version 6 do not recognize the pseudoinstructions in my code. Pseudoinstructions are just "instructions" that translate into 2 or more MIPS instructions. All versions of spim recognize pseudoinstructions. The exceptions here are "done", "putc" and "getc" (and possibly some others), which are macros and found only in version 4, and which you should take note of if you are reading notes from previous semesters. The real problem with version 6 is that the trap handlers are different, which requires only minor changes to your MIPS code.

To make your program run in version 6, do the following:

1. Change the __start: label to main:

2. Change the done at the end of the program to jr $31 (which was what we wanted to do in the first lab)

One thing we screwed up is that the subi instruction is not a valid MIPS instruction, not on any of the versions of spim. Use addi with a negative immediate instead.

Version 4 was different because it was modified from the original spim to accomodate a slightly higher-level assembly language for use with the Goodman & Miller book. Patterson's book is written for the original spim implementation, so it is possible that we will change the lab versions to version 6 to be consistent with his book.

MIPS register convention

Conventions exist to ensure consistency and correctness of code written by different programmers. They may seem to be an unneccessary overhead in simple programs, but remember that you may not be the only programmer working on the program, and you must agree with the other programmers on register and stack usage, etc.

Here's a quick summary of the MIPS conventions:

Caller
1. Must save $t0-$t9, $a0-$a3, $ra if it wants to use them again after the function call. Especially for $ra if it will call another function.

2. Assumes $s0-$s7 will not be modified by the callee.

Callee
1. Must save $s0-$s7 if it want to use them.

2. It is free to use any other general register (e.g. don't use $at)

Calling a function

1. Before calling a function, the caller will put the arguments into $a0-$a3. If there are more than 4 arguments, the additional arguments will be saved on the stack, with $sp modofied accordingly.

2. To call a function, use jal. This will save the current PC into $ra and jumps to specified address.

3. The callee now gets control. It will save $s0-$s7 if they are to be used, and if it is going to call yet another function, it has to follow the caller conventions as well.

4. Before returning from the callee, place the return value in $v0 and/or $v1, pop the stack and modify $sp accordingly.

5. To return from a function, use jr $31 or jr $ra.

Registers are saved on the stack. The stack convention we use is that $sp points to the top element of the stack (i.e. there is data stored at the location where $sp points to). This means that the initial location pointed to by $sp is not used. You have to move the stack pointer first before storing data there.

Example:

To push 3 registers on the stack:          To pop 3 registers:

addi $sp, $sp, -12                         lw   $t0, 0($sp)
sw   $t0, 0($sp)                           lw   $t1, 4($sp)
sw   $t1, 4($sp)                           lw   $t2, 8($sp)
sw   $t2, 8($sp)                           addi $sp, $sp, 12

Note that the stack pointer starts at the higher end of memory, and moves toward the lower end, so pushing involves decreasing the stack pointer and popping involves incrementing it.

Why not specialized push/pop instructions? That would be inefficient, because you'll be moving $sp three times in the above example.

An example: the recursive Fibonacci function (from CS61C Spring 1998)

Recall the Fibonacci series: 0 1 1 2 3 5 8 13 ...

They can be calculated with the recursive formula: F(0)=0, F(1)=1, and F(n) = F(n-1) + F(n-2)

Recursive functions best illustrate the register and stack usage conventions and why we need them.

C code:

int F (int n) {
  if (n==0) {
    return 0;
  } else if (n==1) {
    return 1;
  } else {
    return F(n-1) + F(n-2);
  }
}


MIPS code:

    .text
main:
    addi $a0, $zero, 5        # suppose we want to find F(5)
    jr   $ra

fib:                          # start of the Fibonacci function
    addi $sp, $sp, -12        # save registers
    sw   $ra, 0($sp)
    sw   $a0, 4($sp)
    sw   $s0, 8($sp)
    bgt  $a0, $zero, testmore
    add  $v0, $zero, $zero    # fib(0)=0
    j    rtn
testmore:
    addi $t0, $zero, 1
    bne  $a0, $t0, recur
    add  $v0, $t0m $zero      # fib(1)=1
    j    rtn
recur:
    addi $a0, $a0, -1         # find fib(n-1)
    jal  fib
    addi $s0, $v0, $zero      # result of fib(n-1). 
                              # Why not put it in $v0? 
                              # And why $s0 instead of $t0?

    lw   $a0, 4($sp)          # restore $a0. 
                              # Why? Don't we already know it is n-1?
    addi $a0, $a0, -2         # find fib(n-2)
    jal  fib
    add  $v0, $v0, $s0        # fib(n)=fib(n-1)+fib(n-2)
rtn:
    lw   $s0, 8($sp)          # restore (almost) all registers
    lw   $ra, 0($sp)
    add  $sp, $sp, 12
    jr   $ra

Note the use of the rtn block. It is good to have such a block at the end of your function to perform common bookkeeping tasks before returning from the function. This also ensures one entry/exit point in your code, avoiding certain bugs.

We use $s0 and $a0 (look at the questions in my comments) the way we did because of the register conventions. The function that is to be called makes no guarantees that $v0, $a0, $t0, etc will be the same after the function call. $s0 is used because the callee promises not to touch the $s0-$s7 registers in accordance with the register conventions. But because here the caller is the same as the callee, the $s0 register must be saved in accordance with callee rules, and restores it before it returns.

It is a good exercise to see what happens to the stack as the functions get called.

Written by : Gek Siong Low (cs61c-tb), Spring 1999