Lab 4: RISC-V Functions, Pointers

Deadline: Monday, February 28, 11:59:59 PM PT

Lab Section Slides

Setup

In your `labs` directory, pull the files for this lab with:

``````git pull starter main
``````

If you get an error like the following:

``````fatal: 'starter' does not appear to be a git repository
fatal: Could not read from remote repository.
``````

make sure to set the starter remote as follows:

``````git remote add starter https://github.com/61c-teach/sp22-lab-starter.git
``````

and run the original command again.

RISC-V Simulator

Like last week, we will be using the Venus RISC-V simulator. Also, please refer to the Venus reference on our course website when you need a refresher on any of the Venus features.

Mount the lab 4 files as you did with Lab 3.

Once you've got `discrete_fn.s` open, you're ready to move on to Exercise 1!

Exercise 1: Array Practice

Consider the discrete-valued function `f` defined on integers in the set `{-3, -2, -1, 0, 1, 2, 3}`. Here's the function definition:

``````f(-3) = 6
f(-2) = 61
f(-1) = 17
f(0) = -38
f(1) = 19
f(2) = 42
f(3) = 5
``````

Action Item

1. Implement the function in `discrete_fn.s` in RISC-V, with the condition that your code may NOT use any branch and/or jump instructions! Make sure that your code is saved locally. We have provided some hints in case you get stuck.

Note that you can shorten `jal ra, label` to `jal label`. These two lines do the same thing.

Hint 1

All of the output values are stored in the output array which is passed to `f` through register a1. You can index into that array to get the output corresponding to the input.

Hint 2

You can access the values of the array using `lw`.

Hint 3

`lw` requires that the offset is an immediate value. When we compute the offset for this problem, it will be stored in a register. Since we cannot use a register as the offset, we can add the value stored in the register to the base address to compute the address of the index that we are interested in. Then we can perform a `lw` with an offset of `0`.

In the following example, the index is stored in `t0` and the pointer to the array is stored in `t1`. The size of each element is 4 bytes. In RISC-V, we have to do our own pointer arithmetic, so (1) we need to multiply the index by the size of the elements of the array. (2) Then we add this offset to the address of the array to get the address of the element that we wish to read and then (3) read the element.

``````slli t2, t0, 2 # step 1 (see above)
add t2, t2, t1  # step 2 (see above)
lw t3, 0(t2) # step 3 (see above)
``````

Exercise 2: Calling Convention Checker

Calling convention errors can cause bugs in your code that are difficult to find. The calling convention checker is used to detect calling convention violations in your code. To enable the calling convention checker, go to the Venus tab at the top of the page. In the settings box, click on "Calling Convention" and click "Enable"

Run `cc_tests.s` in the simlator tab.

Alternatively, you can run Venus locally with the following command:

``````java -jar tools/venus.jar -cc lab04/cc_test.s
``````

The `-cc` flag enables the calling convention checker, and detects some basic violations.

In the terminal, you should see something simlar to the following.

``````[CC Violation]: (PC=0x0000004C) Setting of a saved register (s0) which has not been saved! cc_test.s:56 li s0, 1
[CC Violation]: (PC=0x00000054) Setting of a saved register (s0) which has not been saved! cc_test.s:59 mul s0, s0, a0
[CC Violation]: (PC=0x00000054) Setting of a saved register (s0) which has not been saved! cc_test.s:59 mul s0, s0, a0
[CC Violation]: (PC=0x00000054) Setting of a saved register (s0) which has not been saved! cc_test.s:59 mul s0, s0, a0
[CC Violation]: (PC=0x00000054) Setting of a saved register (s0) which has not been saved! cc_test.s:59 mul s0, s0, a0
[CC Violation]: (PC=0x00000054) Setting of a saved register (s0) which has not been saved! cc_test.s:59 mul s0, s0, a0
[CC Violation]: (PC=0x00000054) Setting of a saved register (s0) which has not been saved! cc_test.s:59 mul s0, s0, a0
[CC Violation]: (PC=0x00000054) Setting of a saved register (s0) which has not been saved! cc_test.s:59 mul s0, s0, a0
[CC Violation]: (PC=0x00000064) Save register s0 not correctly restored before return! Expected 0x00000000, Actual 0x00000080. cc_test.s:66 ret
[CC Violation]: (PC=0x00000070) Setting of a saved register (s0) which has not been saved! cc_test.s:80 mv s0, a0 # Copy start of array to saved register
[CC Violation]: (PC=0x00000074) Setting of a saved register (s1) which has not been saved! cc_test.s:81 mv s1, a1 # Copy length of array to saved register
[CC Violation]: (PC=0x000000A4) Setting of a saved register (s0) which has not been saved! cc_test.s:115 addi s0, t1, 1
Found 12 warnings!
--------------------
[ERROR] An error has occurred!

Error:
`SimulatorError: Attempting to access uninitialized memory between the stack and heap. Attempting to access '4' bytes at address '0x63080013'.
``````

Note: Venus's calling convention checker will not report all calling convention bugs; it is intended to be used primarily as a basic check. Most importantly, it will only look for bugs in functions that are exported with the `.globl` directive - the meaning of `.globl` is explained in more detail in the Venus reference.

Action Items

1. Resolve all the calling convention errors in `cc_test.s`.

The fixes for all of these errors (both the ones reported by the CC checker and the ones it can't find) should be added near the lines marked by the `FIXME` comments in the starter code.

2. Once you have answered these, run Venus with the calling convention checker on `discrete_fn.s` from the last exercise as well. Make sure to fix any bugs you find.

3. After you finish the exercise, be sure that you can answer the following questions.

Is `next_test` a function?

No, it's just a label that is used to skip over the call to `failure`. If a label is a function, we will jump and link to it because we always want our functions to return back to us. In this case, we just jumped to `next_test`.

What caused the errors in `pow`, and `inc_arr` that were reported by the Venus CC checker?
• `pow`: Missing epilogue and prologue.

• `inc_arr`: Failure to save `s0`, `s1` in prologue/epilogue, and failure to save `t0` before calling `helper_fn`.

In RISC-V, we call functions by jumping to them and storing the return address in the `ra` register. Does calling convention apply to the jumps to the `pow_loop` or `pow_end` labels?

No, since they're not functions, we don't need to return to the location the function was called.

Why do we need to store `ra` in the prologue for `inc_arr`, but not in any other function?

`inc_arr` itself calls another function - `ra` holds the address of the instruction to continue executing after returning, which is overwritten when we call another function since we need to be able to return to the body of `inc_arr`.

Why wasn't the calling convention error in `helper_fn` reported by the CC checker? (Hint: it's mentioned above in the exercise instructions.)

It's not declared `.globl`. The calling convention checker will not test functions that are not declared `.globl`. Note: The bug in helper_fn will initially be reported by the checker, but when the bugs in the function that calls it are fixed, this one is no longer reported.

Testing

After fixing the errors in `cc_test.s`, rerun the program to make sure the behavior of the functions hasn't changed and that you've remedied all calling convention violations.

Once you have fixed everything, running the above Venus command should output the following:

``````Sanity checks passed! Make sure there are no CC violations.
Found 0 warnings!
``````

Exercise 3: Debugging `megalistmanips.s`

In Lab 3, you completed a RISC-V procedure that applied a function to every element of a linked list. In this lab, you will be working with a similar (but slightly more complex) version of that procedure.

Now, instead of having a linked list of `int`'s, our data structure is a linked list of `int` arrays. Remember that when dealing with arrays within `struct`'s, we need to explicitly store the size of the array. In C code, here's what the data structure looks like:

``````struct node {
int *arr;
int size;
struct node *next;
};
``````

Also, here's what the new `map` function does: it traverses the linked list and for each element in each array of each `node`, it applies the passed-in function to it, and stores it back into the array.

``````void map(struct node *curr_node, int (*f)(int)) {
if (!curr_node) { return; }
for (int i = 0; i < curr_node->size; i++) {
curr_node->arr[i] = f(curr_node->arr[i]);
}
map(curr_node->next, f);
}
``````

You can pass arguments into function pointers just like you do with normal functions. You can read more about function pointers here).

Action Item

For this exercise, we are requiring that you don't use any extra save registers in your implementation. While you normally can use the save registers to store values that you want to use after returning from a function (in this case, when we're calling `f` in `map`), we want you to use temporary registers instead and follow their caller/callee conventions. The provided `map` implementation only uses the `s0` and `s1` registers, so we'll require that you don't use `s2`-`s11`.

Note: The CC checker won't check if you are using registers besides `s0` and `s1`, but you need to implement this requirement in order to pass the autograder.

Fix all of the mistakes inside the `map` function. Read all of the commented lines under the `map` function in `megalistmanips.s` and make sure that the lines do what the comments say. All bugs are within the `map` function, `mapLoop`, and `done` but it's worth understanding the full program. We have provided some hints in case you get stuck.

If I have a register that contains the address of a node that is stored in memory, what instruction would I use to read elements from that node?

You would use the load word instruction. Load word is used to read values from the memory, so if I have a pointer to something that is located in memory, I need to use load word to read it.

What are the steps of executing a function?
1. If you will be calling another function, make sure that you save register `ra` on the stack. (When you call another function, you will end up overwritting register `ra` so that the function you are calling knows where to return to.

2. If you need to overwrite any callee-saved registers, make room for them on the stack and save them.

4. Restore the registers that were saved and move the stack pointer back up.

5. Return

How do we read an element from an array given a pointer to the beginning of an int array (a0) and the index of the element that we want to read (a1)? Assume sizeof(int) = 4.

In the following example, the index is stored in `t0` and the pointer to the array is stored in `t1`. The size of each element is 4 bytes. In RISC-V, we have to do our own pointer arithmetic, so (1) we need to multiply the index by the size of the elements of the array. (2) Then we add this offset to the address of the array to get the address of the element that we wish to read and then (3) read the element.

``````slli t2, t0, 2 # step 1 (see above)
add t2, t2, t1  # step 2 (see above)
lw t3, 0(t2) # step 3 (see above)
``````

Testing

Save your corrected code in the `megalistmanips.s` file. Use the `-cc` flag to run a basic calling convention check on your code locally:

``````java -jar tools/venus.jar -cc lab04/megalistmanips.s
``````

The CC checker should report 0 warnings.

For reference, running `megalistmanips` on the web interface should give the following output:

``````Lists before:
5 2 7 8 1
1 6 3 8 4
5 2 7 4 3
1 2 3 4 7
5 6 7 8 9

Lists after:
30 6 56 72 2
2 42 12 72 20
30 6 56 20 12
2 6 12 20 56
30 42 56 72 90
``````

Survey

Please fill out this short survey about your experience with the lab. Your responses will be used to improve the lab in the future. The survey will be collecting your email to verify that you have submitted it, but your responses will be anonymized when the data is analyzed. Thank you!

Submission

Save, commit, and push your work, then submit to the Lab 4 assignment on Gradescope.