Calling Conventions

Overview

In this lab you will re-visit the fibonacci programs that you worked on in P2.

The Fibonacci sequence is defined as follows: start with 0, 1; for the code you are implementing, the zeroth Fibonacci number is defined to be 0, and the first Fibonacci number is defined to be 1. To obtain subsequent numbers in the sequence, we take the sum of the previous two numbers in the sequence. Thus, the second number in the seqeuence is 0 + 1 = 1, and the third number in the sequence is 1 + 1 = 2. The function you implement will return the nth Fibonacci number, where the value n is an input to your function.

There are several ways to compute the Fibonacci sequence. You will implement the recursive method below. Please do not submit RISC-V code with any form of main function (e.g. instruction that set n to a specific value), we will run it with our own values.

• Recursive Fibonacci: Simple but inefficient. Logisim would be too slow to use this version except when the index is small.

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

Implement this version of the Fibonacci function using RISC-V assembly code. It must work on the online simulator, though you will have to be careful when testing to select indices whose Fibonacci number can be computed in a reasonable time.

Testing and input for Fibonacci functions

Your Fibonacci function should follow the calling convention covered in lecture. In particular, it should get its inputs from the argument registers (a0, a1, etc.) and return its outputs in the result register a0. If you want to test the function, you can create a "main" program which initializes the stack (by setting sp and fp to something reasonable and usable) and calls the function on an input. If you add testing code to a file, make sure to turn in a version without the testing code. Since your function will follow the calling convention, you'll invoke them from your main program by loading the input registers, saving caller-saved registers if necessary, and then executing a JAL instruction.

As a reminder, don't forget to save the previous value in callee-saved registers before you use them in your function!

You can use the following template as your main function, however, you must change the values for the function to work:

    addi sp, x0, 1000
    addi fp, x0, 1000
    addi a0, x0, n //change n to an integer argument
    jal ra, r_fibonacci
    jal x0, exit

    r_fibonacci:
    // Your function here, starting with the prologue

    exit:

RISC-V (subset) Assembly Syntax

Submitting

Bonus!

Recursive fibonacci only uses one argument and doesn't access memory. Binary search takes four arguments and accesses array elements stored in memory. For a bit more challenge, implement the following in RISC-V assembly code.

    // Find index of x in arr within the bounds l and r
    int binarySearch(int arr[], int l, int r, int x) {
        if (r >= l) {
            int mid = l + (r - l)/2; // How do you divide by two??

            if (arr[mid] == x)
                return mid;

            if (arr[mid] > x)
                return binarySearch(arr, l, mid-1, x);

            return binarySearch(arr, mid+1, r, x);
        }
        return -1;
    }

    // Convert the following main function to run your code
    int main(void) {
        int arr[] = {2, 3, 4, 10, 40}; //Store these values in memory somewhere
        int n = 5;
        int x = 10;
        int result = binarySearch(arr, 0, n-1, x);
        return result;
    }