CPSC220: Introduction to Computer Architecture (Fall 2013)

Assignment #4.5

Due at the end of class on Thursday, 10/10/2013

Reading

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.

    boolean 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: