CPSC220: Introduction to Computer Architecture (Fall 2014)

Lab #3

Due at the start of class on Friday, 10/03/2014

Reading

Study

We've spent this week discussing the MIPS conventions for supporting procedure call and return. Though the details are specific to the long-obsolete MIPS processor, the ideas behind them recur in most architectures:

Elaboration

It is important to understand that there is nothing magic about procedure/function calls, recursive or not. A procedure is just a block of code with a label. There is no mechanism in the MIPS ISA that makes the passing of arguments in registers $a0–$a3 mandatory. Even the use of the $ra register is optional (though the jal instruction does privilege it over other choices).

Similarly, the "call stack" is nothing more than a convention for using the dynamic area of program memory: there is no such thing as built-in "push" or "pop" operations, nor is there any special mechanism for allocating or deallocating activation records. Similarly, there is nothing in the MIPS ISA itself that forces saved registers to actually be saved. All of these things are conventions, agreed upon by compilers that target this ISA. What you are learning is what these conventions are and how to implement them.

Details



Example from class: the factorial function:

int fact(int n) {
    if (n == 0) 
        return 1;
    else
        return n * fact(n - 1);
}

MIPS version:

fact:   sw $a0, 0($sp)      # prelude:  save argument register, 
        sw $ra, 4($sp)      #           call site,
        sw $s0, 8($sp)      #           and local saved register,
        addi $sp, $sp, 12   #       then advance the stack pointer ("push")
        
        # the body of the function:
        
        bne $a0, $zero, rec # base case
        li $v0, 1           # return value is 1
        j return

rec:    add $s0, $a0, $zero # save n, as we're going to need it 
        addi $a0, $a0, -1   # setup up the argument for the call:  n-1
        jal fact
        mult $s0,$v0         # return value is n * fact(n-1)
        mflo $v0    
        
return: lw $s0, -4($sp)     # postlude: restore registers,
        lw $ra, -8($sp)     #           ...
        lw $a0, -12($sp)    #           ...
        addi $sp, $sp, -12  #       and put the stack pointer back ("pop").
        
        jr $ra              # return
        

To do

  1. Translate the following functions into MIPS assembly code, using as few instructions as possible:

    int pos(int a, int b) {
        return abs(a) + abs(b);
    }
    
    int abs(int x) {
        if (x < 0) {
            return x * -1;
        } else {
            return x;
        }
    }
    
  2. Functions can often be implemented during compilation by "inlining" them, copying the body of the function in place of a call (in the C++ language, there is even an inline keyword, which directs a compiler to attempt this). In an inlining transformation, the body of a function is substituted in place of a call to that function, eliminating the overhead of the function call during runtime.

    Implement a version of pos from the previous problem, with an in-line version of abs.

  3. Translate the following function into MIPS assembly code, using as few instructions as possible.

    int fib(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fib(n-1) + fib(n-2);
        }
    }
    
  4. Recursive functions that are written in tail form (i.e. with all function calls structured as tail calls) facilitate a comparatively easy transformation to an equivalent version, avoiding the overhead of handling the nested call/return structure (see pp. 121–122 of Patterson and Hennessy).

    Even without the transformation to a loop version, however, tail calls support useful optimization. When no further operations occur after the call returns, it is unnecessary to save any argument or local variable registers. Indeed, the function's activation record can simply be overwritten by the recursive call, so that only one record is necessary on the call stack for the complete recursion.

    Consider this tail form implementation of the factorial function:

    int fact(int n) {
        return factIter(n,1);
    }
    
    int factIter(int n, int a) {
        if (n == 0)
            return a;
        else
            return factIter(n-1,n*a);
    }
    

    Implement these functions in MIPS assembly, using only one activation record for factIter() (obviously, you need another for fact() itself).

Turn in:

To hand in your files: