Lab 3: RISC-V Coding and Procedures

1 Objectives

Following completion of this lab you should be able to:

Write loops in RISC-V programs.
Understand the limitations of beq/bne/blt/bge, jal, and jalr.
Properly access memory in RISC-V programs.
Understand some of the issues surrounding register allocation.

Your Tasks

This lab will be done alone, each student is expected to write their own code and demonstrate an understanding of assembly programming.

1 Setup RARS

Install

RARS is a Java program and should work on any machine that supports a Java Virtual Machine. If you need java, you can get it here. Download RARS from here or from the main RARS webpage: https://github.com/TheThirdOne/rars/releases.

On Windows and MacOS you should be able to double click the .jar file.

Sometimes you need to launch it from a command line. Example for running it from a linux command line:

> java -jar rars1_6.jar

Note some MacOS machines will not allow normal file navigation unless you launch the jar from the command line using the linux instructions above.

Some help and info pages are available on the RARS github page.

Navigation

Launch RARS. A window should appear named similar to "RARS 1.5" with three panes.

The right-most pane shows the contents of the registers. At the bottom of the register list is the pc register, which tracks the address of the current instruction. The tabs at the top of the pane allow you to look at control and status registers. If an error occurs in your code, the simulator might automatically show you the values of the "control and status" registers. We will not use these for a while, so you should switch back to the general registers for now.
The large upper-left pane shows the contents of the currently loaded file. It should be blank when you start up RARS. There are two tabs at the top of the pane.
1. The Edit tab allows you to edit the currently loaded assembly file.
2. The Execute tab shows the assembled code and processor state as the code runs.
The bottom panel is the output console. The 'Messages' tab displays messages from the simulator. The 'Run I/O' tab shows any messages generated from the running program.

Running a program

There should be a lab03 directory in your repository. Inside, there should be a p1 folder. Inside that directory there should be a p1.asm file.
Open it in RARS, by going to File > Open and browse to your lab01/p1 folder. The file's contents should appear in the editor panel. Look over the file.
1. This file contains two main parts the .globl part defines what is in memory, this file simply defines a global variable main which allows us to refer to the label main: in this file from other files. We can define and add new data to memory here, including lists, constants, etc.
2. The .text part defines the actual assembly code in this program. Labels can be added arbitrarily to this code (no need to declare a global variable for most labels). You can refer to registers by number or name.
Click the Assemble button or go to Run > Assemble to assemble the file. The assembler will translate the assembly instructions into machine code ready for execution. RARS will automatically switch to the Execute tab. The execute tab shows two views of memory: the "text segment" (the program's instructions) and the "data segment" (the data stored for the program).
1. The text segment window looks messy, but each instruction has five columns of data. The first column is a checkbox that allows us to set a breakpoint. The second is the address of the instruction. The third item is the hexadecimal representation of the machine instruction. The fourth item is (basically) the assembly language representation of the machine instruction. The fifth item (if it's present) is the actual line of code (and line number) from the source file that generated the machine instruction shown in the "Basic" column.
2. The data segment window shows the contents of memory, including the stack contents. You can jump to different regions in memory using the drop-down selector. For now, we'll only be concerned with the (.data) region.
Look at the text segment tab. Notice that instructions start at address 0x00400000 and continues to address 0x00400018. Also notice that the PC (program counter) register has the value 0x0400000.
When the program is assembled, the "ori x2, x0, 0x00000028" instruction will be highlighted.
Notice the value of the PC.
Notice that register 0 currently contains zero and register 2 currently contains a big number.
Click Run > Step or use the Step button to run the currently highlighted line. Notice that the contents of register 2 have changed, and that the new value is shown in hexadecimal form. Finally, notice the value of the PC.
Click Run > Reset or use the reset button. The register and text segment contents will return to the state prior to you running the program. This allows you to rerun the program easily.
Practice editing, navigating through the code, and executing it until you are comfortable using RARS.

2 Summing an array

In writing these and other assembly language programs you should follow this process:

Solve the problem before coding the solution. Usually this means writing the code in a high-level language or pseudo-code first, then converting it to assembly language.
IMPORTANT: Write down (perhaps in a comment in your code) the purpose that you have in mind for each register that you use. Here's an example of how you might document register use in your code.
```
  ; x3 = i
  ; x4 = j
  ; x5 = n
  ; x6 = key
  ; x7 = ptr (address of array)
  ; x8 = test
  ; x9 = temp
```
These programs involve many loops, so it will be helpful to set breakpoints. Breakpoints mark positions in the code where execution should pause. After assembling a program, click the Bkpt checkbox to set a breakpoint at that line. Execution will stop before that line is run and you can observe the state of the program. Note: All breakpoints are deleted when you assemble the program!
All of these programs require RARS to be configured to assemble all files in the directory. To do so, enable Settings > Assemble all files in directory.
IMPORTANT: Do not use registers 1 and 2 for this lab.
Your solutions to these labs should not use any pseudoinstructions. The only exception is the li pseudoinstruction.

Items below marked with a Q are to be answered on the lab worksheet.

Open the p2/p2.asm file in RARS. This goal of this program is to sum the integers between 0 and an $N$.
Q Where are main, loop, done, N and Sum located (i.e. what address)? Hint: Assemble and use Settings > Show Labels Window in the Execute view.
Before you run the program, calculate the number of instructions that will be executed within p2 and the final value of Sum. Only count the instructions that run between the test setup and teardown (the jal and the jalr).
Q Assemble the code and set a breakpoint at address 0x00400004. Use Run > Go to run the program and it should stop at the breakpoint. Single step to the end of the program. How many instructions were actually executed? Remember, only count the instructions that execute between the 'jal' and the 'jalr'. What is the final value of Sum?
Modify p2.asm so that it will set calculate the sum correctly if N is equal to 0. Be sure to test your modifications to make sure they work. You can do this by changing the value of the test0 variable from 0 to 1. You should also test that it works with N equal to values 1 to 5. Set the testN variable to 1 to test this.
Q How many instructions does your modified program execute when N is equal to 5? Can this number be improved? If so, how? Hint: If your modified program executes more than 1 additional instruction, you can do better.
Q Will your modified program work if N is less than 0? You do not need to make any additional modifications.

3 Swap max with last

Note: You can use whatever registers you want in this part, but you will have an easier time on future parts if you avoid using any s-registers now.

Open the p3/p3.asm file. This goal of this program is to find the maximum element in an array and put it at the end of the array.
Assemble the code and set a breakpoint at address 0x00400004. This is the start of the program. Set another breakpoint at address 0x00400050. This is the end of your program (should be a jalr).
Q Run p3.asm until your second breakpoint. What is the value of max and maxindex at the end of the program? Are they what you expect?
Q Comment out slli x10, x7, 2 and rerun the program. What happens? Why?
Undo the changes made in Step 4.
Modify p3.asm so that the largest element of A is swapped with the last element of A. Be sure to adequately test your modified program. Hint: change the elements and size of A, then check your results in the Data segment.
Q If you repeatedly apply your modified program to the subarrays of A from 0 to $ N-i $ where $i$ is the number of times you've applied your program, what is the final state of A?
Q Like p2.asm this program doesn't work if N is equal to 0. It is brittle in other ways as well. For example, what happens if all of the elements are less than -1? Is there a more robust way to set the maximum value, instead of using the magic constant of -1?
Try to fix p2.asm so that it works with all values (including all negative values).

4 Making a procedure

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).

Open the files p4/p4-loop.asm and p4/p4-swap.asm in RARS.

Note the two locations marked for adding your code.
In the previous part of this lab, you worked with a program for swapping the maximum element of an array with the last element. Copy 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 p3: and the 'jalr'. Don't copy the label or the 'jalr'.

If you have not already addressed the issue discussed in the last step (7) of "Swap max with last", you'll need to do so now.
Add your code to p4-swap.asm in the spot indicated below the label SwapMaxWithLast:.
Modify your swap code so that it complies with the documentation and specifications in p4-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 p4-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.
5. Note that you will not be able to assemble and run this file on it's own now. Since you made this a procedure the arguments must be set up by some other piece of code. You'll write that next. If you get weird behavior while debugging stop and check if you tried to assemble this file on its own. Always check what is in the argument registers first while debugging.
Modify the p4 procedure in p4-loop.asm so that it calls SwapMaxWithLast a single time with A and N as arguments. What output do you expect when you run p4-loop.asm?
Run p4-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 p4 in p4-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 p4-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 p4-loop.asm?
Run p4-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"
Q If SwapMaxWithLast needed to return a value how would that be accomplished?
Q What changes would you need to make if SwapMaxWithLast needed more than 8 arguments?
Q What changes would you need to make if SwapMaxWithLast called another procedure?
Q The code in p4-loop.asm works almost like a procedure. Describe the changes you would make to convert the p4-loop.asm code into a sort procedure which is called and which in turn calls SwapMaxWithLast.

5 Fixing a broken procedure

You have been given a broken implementation of a recursive procedure. 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.

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	..

Note: You can (and must) use s-registers for this part of the lab.

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. Your stack frame should be exactly 4 words, specified in the comments at the top of the file. 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 question.
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 sp. Use this to see the stack frames.

Grading Rubric

All the labs for CSSE232 have these general requirements:

General Requirements for all Labs

The solution fits the need
Aspects of performance are discussed
The solution is tested for correctness
The submission shows iteration and documentation

Some labs will hit some of these requirements more than others. But you should always be thinking about them.

Fill out the Lab Worksheet

In the worksheet, explain how you satisfy each of these items. Some guidelines:

None of these answers should be more than 100 words. (Unless otherwise indicated on the worksheet.)
You will upload this sheet to gradescope. Make sure you indicate your partner when you upload. TODO: Talk about these rubrics, should the test cases be separate from each entry? or should I pool that somehow?

Lab 1 Rubric items Possible Points

Lab Worksheet 30

Sum (p2) 10

Swap (p3) 20

Sort (p4) 20

Fib 20

Total out of 100

Lab 1 Rubric items	Possible Points
Lab Worksheet	30
Sum (p2)	10
Swap (p3)	20
Sort (p4)	20
Fib	20
Total out of	100

Submit your completed worksheet to gradescope. You will not upload code to gradescope for this lab. For the "Code" question just select the first page of your worksheet if gradescope prompts you to assign one.
Push your code to your github repo. (Make sure you push, dont just commit.)