Lab3 RISC-V procedures

1 Objectives

Following completion of this lab you should be able to:

Call and pass arguments to procedures in RISC-V programs.
Return from procedures.
Discuss register allocation strategies.
Save and restore registers.
Correctly manage the stack.

2 General

Get a copy of the question sheet to edit (Word doc version)
Be sure to follow the RISC-V procedure calling conventions as described in your book (Section 2.8)

3 Sorting an Array

NOTE: You may not use the callee-saved (s) registers for this portion of the lab. Make sure to avoid x8-x9 (s0-s1), or x18-x25 (s2-s11). We recommend you use register names (t0-t6 and a0-a7) instead of numbers (xN).

Pull your repository. Open the files lab03/p7/p7-loop.asm and lab03/p7/p7-swap.asm in RARS.

Note the two locations marked for adding your code.
In a previous lab, you worked with a program for swapping the maximum element of an array with the last element. Extract your code for "swapping the maximum value of an array with the last element of the array". You'll need all the code between the label p5: and the 'jalr'. Don't copy the label or the 'jalr'.

If you have not already addressed the issue discussed in the last step of "Finding the Maximum" in lab 2, you'll need to do so now.
Add your code to p7-swap.asm in the spot indicated below the label SwapMaxWithLast:.
Modify your swap code so that it complies with the documentation and specifications in p7-swap.asm. Note, SwapMaxWithLast is a procedure which takes 2 arguments - the location (address) of an array of words in memory and the length (in words) of the array - and order matters. Be sure your code conforms with the RISC-V procedure calling conventions. Specifically, you will need to:
1. Get the address of "A" from an argument register rather than doing a "la" on a label.
2. Get the value of "N" from an argument register rather than loading it from memory.
3. Return from the procedure by doing a "jalr x0, 0(x1)" (this should already be done in the code provided in p7-swap.asm).
4. You may need to reallocate registers or manage the stack to comply with the RISC-V procedure calling convention. Especially to avoid s registers x8-x9 or x18-x25.
Modify the p7 procedure in p7-loop.asm so that it calls SwapMaxWithLast a single time with A and N as arguments. What output do you expect when you run p7-loop.asm?
Run p7-loop.asm. Is the actual output what you expected?
Replace your call to "SwapMaxWithLast" with a call to the procedure "ProcedureConventionTester". This procedure takes the same arguments as SwapMaxWithLast and calls "SwapMaxWithLast", but also checks for compliance with the RISC-V procedure call convention. Run the program with the new call. If the test fails, fix your code so it can pass the test.
Modify the procedure p7 in p7-loop.asm so that it calls SwapMaxWithLast $ N-1 $ times and with each successive call the length of the array passed is decreased by 1. See the comments in p7-loop.asm for exactly where to put your code. Do not use s registers. In pseudocode:
```
  for (i=N; i>1; i--) {
    SwapMaxWithLast(A, i);
  }
```
What output do you expect when you run p7-loop.asm?
Run p7-loop.asm. Is the actual output what you expected?
Again test your compliance with the RISC-V procedure calling convention by calling "ProcedureConventionTester" instead of "SwapMaxWithLast"
If SwapMaxWithLast needed to return a value how would that be accomplished?
What changes would you need to make if SwapMaxWithLast needed more than 8 arguments?
What changes would you need to make if SwapMaxWithLast called another procedure?
The code in p7-loop.asm works almost like a procedure. Describe the changes you would make to convert the p7-loop.asm code into a sort procedure which is called and which in turn calls SwapMaxWithLast.

4 Recursive Procedures

The procedure call example on page 108-110 of the book and the factorial example posted on Moodle may be helpful in understanding recursive procedures.

5 The Fibonacci Sequence

The Fibonacci sequence is defined over nonnegative integers as follows:

$$ \begin{align*} F(0) = 0\\ F(1) = 1\\ F(i) = F(i-1) + F(i-2), i \geq 2\\ \end{align*}$$

While there are several ways to calculate the Fibonacci sequence, for this lab you must use a recursive procedure.

The sequence should be:

N	0	1	2	3	4	5	6	7	8	9	10	..
Fibonacci number	0	1	1	2	3	5	8	13	21	34	55	..

6 Recursive Procedures Revisited

Open lab03/fib/fib.asm in RARS.
This file contains code to execute a recursive procedure which takes one argument i and returns F(i). Pseudo code is provided below - your final code must follow the algorithm presented below.
```
int
fib(int n)
{
  if (n == 0) {
    return 0;
  }
  else if (n == 1) {
    return 1;
  }
  else {
    return fib(n-1)+fib(n-2);
  }
}
```
The provided code does not follow the RISC-V calling conventions, therefore it loops infinitely. You need to edit this code to follow the conventions.

We recommend you begin by renaming all the registers from x1-x30 to their named counterparts (e.g., t0, sp, ra, s3, etc).
Next, look at the registers being used and identify whether they are caller-saves or callee-saves (look at the green sheet).
Once you've identified the saving strategy, implement them using a stack frame inside your fib procedure. Note that fib is both caller and callee because it is recursive!
The comment block at the top of fib.asm describes how you should arrange stack frames for this code. Be sure any changes you make to your code conforms with these specifications as well as the RISC-V procedure calling conventions. Your code will work with alternative stack frames, but you will not receive full credit if you do not follow these requirements. You should only have to modify the code where the comments suggest allocation and deallocation of the stack.

When you have correctly implemented the calling conventions run fib.asm. Does it behave as expected?
In your fib procedure, replace the calls to fib with calls to fibtest. This is similar to the ProcedureConventionTester from the previous lab.
Test your program with the new fibtest calls. If there are any issues, fix them. Once your program works correctly, restore the original calls to fib. Note: this test confirms that your code follows most of the calling conventions, but doesn't test them all. You should check the green sheet to make sure you haven't missed anything.
Complete the lab question sheet. You will need to trace the execution of the program and record values from the stack. You can view the stack in RARS: in Execute view, the Data Segment window has a drop down that allows you to check memory at current x2. Use this to see the stack frames.

7 Turning It In

Submit the answers to the questions contained in the lab guide using the question sheet via gradescope, only 1 per team (make sure all team member's names are included). In gradescope you are able add your team members names to the submission, make sure you do so. When you are prompted to indicate where the "code question" is on the answer sheet, just select the first page of the assignment, you DO NOT upload code to gradescope.

Lab code will be submitted to EVERY team member's git repository.