Practical 3: RISC-V Coding and Procedures

Objectives

Following completion of this practical you should be able to:

Guidelines

Time Estimate This practical is estimated to take about 6-8 hours per student varying based on your depth of understanding about RISC-V coding and procedure calling conventions. Even if you do not have a full grasp of the concepts, this practical is designed to elevate your understanding upon completion.

Preliminary Tasks

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

1. Install Java and RARS

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.

2. Clone your practical repo

Follow this link to get your new repository for this practical. Follow the instructions in Practical 1 if you have trouble getting access or setting up authentication.

1 Using RARS

Navigation

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

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

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

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

  4. There is a setting we need to set up. Under Settings, check Assemble all files in the directory:

Running a program

  1. There should be a p1 directory in your repository. Inside that directory there should be a p1.asm file.
  2. Open it in RARS, by going to File > Open and browse to your repository's p1 folder. The file's contents should appear in the editor panel. Look over the file in your Edit panel.

.globl, .data, and .text segments

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.

The .data portion is not used for p1, however it will be used for later problems. For each array/constant declared in the .globl segment, we will instantiate its value in the .data segment. We will see this in p2 and onwards.

The .text part defines the actual assembly code of the program. Labels can be added arbitrarily in this segment and you can use registers by number or by name.

Assembling and Executing

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

    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.

    The bottom of this panel is a dropdown menu that allows you to switch what portion of memory you want to look at. The .data, current sp, and .text portions are the most important for us. Select the .text option to pull up the contents of the instruction memory:

    Look at the text segment tab and the data view when the text segment is chosen from that drop-down menu. Notice that instructions start at address 0x00400000. Also notice that the PC (program counter) register has the value 0x0400000.

    Take a look at how memory is being displayed. It runs as a table that reads left to right in 4-byte (32-bit) words. The addresses in the first column are the "starting" address for the bytes in the row, and the column headers show the offset for each word from that starting address.

    Orient yourself with this view so you can identify the address of various bytes displayed.

  2. Once the program is assembled, the ori x2, x0, 0x00000028 instruction will be highlighted.

  3. Notice the value of the PC.

  4. Notice that register 0 currently contains zero and register 2 currently contains a big number.

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

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

  7. Practice editing, navigating through the code, and executing it until you are comfortable using RARS.

2 Summing an array (p2)

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

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

Starting Code

  1. Open the p2/p2.asm file in RARS. This goal of this program is to sum the integers between 0 and an \(N\).

    The first portion of p2 is a chunk of comments. Read this carefully as it lays out a lot of defined uses of registers and expected behaviors. Make sure you regularly reference this documentation to ensure you follow its conventions.

    x5 has several uses throughout the program. These three uses are summarized in the comments at the top of p2. Each of these three uses correspond to specific lines in the program, identify which these lines so you are clear about x5’s different uses before continuing. (Q)

  2. To help us orient where PC will be jumping to, identify where the labels main, loop, and done are located in the .text portion of memory. Additionally, identify where the constants N and Sum are in the .data segment of memory. To ease this sleuthing process, bring up the Labels panel via Settings -> Show Labels Window (symbol table).

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

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

  4. Execute the program and verify that the program sums the values between 0 and N correctly.

Modifying p2.asm

  1. Modify p2.asm so that it will still 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.

  2. (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 instruction does your modified program execute when N is equal to 5? Can this be improved? If so, how? Hint: If your modified program executes more than 1 additional instruction, you can do better.

  3. (Q) Will your modified program work if N is less than 0? You do not need to make any additional modifications yet, but answer the question and consider how you might address any problems.

  4. Commit and push any files you changed while working on p2 files to git.

3 Swap max with last (p3)

In this part of the practical, you will be given code with an array of integers A and its size N and you must swap the maximum element of the array with the last element.

Note: You can use whatever registers you want in this part except for x1 and x2, but you will have an easier time on p4 if you avoid using s0-s11 (x8, x9, x18-x27) now.**

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

    Review both the commented documentation at the top of p3.asm and the constants defined as .globl and the instantiations inside the .data segment.

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

  3. (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?

  4. (Q) Comment out slli x10, x7, 2 and re-assemble and run the program. What happens? Compare the address table between the program with and without slli. Which is correct and why?

    You may need to scroll the Messages box to the right to read the entire message. (Q) Examine the value of x10 and its use in lw x10, 0(x10). What does “Load address not aligned to word boundary 0x10010001” mean? Why did commenting out the slli instruction invalidate the program? Explain in the context of the x10, x10’s value, and how the .data memory segment is organized.

  5. Undo the changes made in Step 4.

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

    Be sure you adequately test your modified program. You can do so by changing the contents of the array A defined in the .data segment alongside the value of N if needed and check the final contents of the array in the .data memory segment in the Execute tab. Note that if you customize the initial array contents and/or the size of the array, the Run I/O will default to [FAIL] as it’s only checking for the initial array configuration. You will have to manually verify the .data contents.

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

  8. (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? What if they are all -2^{31}, the max negative value? Is there a more robust way to ensure the max value is identified?

  9. Make additional modifications to p3 so that it will still swap the maximum value in the array with the last element even if all initial values of the array are negative values. Similar to p2, this should require the definitively minimal number of changes. If you are unsure how to approach this, consult your instructor on where to begin.

  10. Commit and push any files you changed while working on p3 files to git. Get in the habit of committing your changed files periodically when you make progress because we are going to stop reminding you.

4 Writing and calling a procedure (p4)

The goal of p4 is write a loop that repeatedly calls p3’s SwapMaxWithLast as a procedure on increasingly smaller subarrays of A to sort A, all while following RISC-V procedure calling conventions. You must have a working p3 implementation as p4 will use your modified p3 program.

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

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

    Note the two locations marked for adding your code.

  2. In the previous part of this practical, 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'.

  3. Paste your copied code into p4-swap.asm in the spot indicated below the label SwapMaxWithLast:.

    This copied/pasted code will not immediately work.

    • First, the p3 implementation may not follow RISC-V procedure calling conventions. You'll need to fix that.
    • Second, the constants are not defined in p4-swap, so you'll need to pass them in as arguments and modify your implementation to use the calling conventions for arguments.

  4. 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 and the documentation comments in the p4 files.

    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 refactor your code to use t registers or manage the stack to comply with the RISC-V procedure calling convention. You are strictly forbidden from using 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.

  5. Modify the p4 procedure in p4-loop.asm so that it calls SwapMaxWithLast a single time with A and N as arguments. Here's some sample code:

    p4:
    la  a0, A          # put address of array into x10
    la  a1, N          # put address of N into x11
    lw  a1, 0(a1)      # get the *value* of N and put into x11

    jal ra, SwapMaxWithLast

    What output do you expect when you run p4-loop.asm?

  6. Run p4-loop.asm. Is the actual output what you expected? You can check the results in a similar way as you did with p3.

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

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

  9. Run p4-loop.asm. Is the actual output what you expected?

  10. Again test your compliance with the RISC-V procedure calling convention by calling "ProcedureConventionTester" instead of "SwapMaxWithLast"

    If you are having trouble: Remember, RISC-V procedure calling convention dictates that all procedures must be written abiding the same set of rules. Even if you are the author of both p4-loop and p4-swap and know the exact register usage across both files, you must still abide by all the rules set by the conventions (e.g., even if your p4-loop doesn’t modify a0 and a1, p4-loop must assume they are modified when it calls SwapMaxWithLast.)

  11. With a working p4-loop and p4-swap that follows RISC-V procedure calling conventions, consider the following questions.

    • ˆ(Q) If SwapMaxWithLast needed to return two values — the two values swapped in its execution — for debugging purposes, what changes to p4-swap would need to be made to accomplish this?
    • (Q) ˆ If SwapMaxWithLast needs to call another procedure in its execution, what changes to p4-swap would need to be made to accomplish this?
    • (Q) ˆ If p4-loop needs to be converted into a procedure — similar to what you did when refactoring p3 into p4-swap, what changes to p4-loop would need to be made to accomplish this?

    You do not have to implement any of these items, you just describe it with enough detail for an experienced RISC-V programmer to implement.

5 Fixing a broken procedure (p5)

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

  1. Open fib/fib.asm in RARS.

  2. 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);
  }
}

    Open fib.asm and testfib.asm. A portion of fib is implemented for you; take time to read through the commented documentation to understand fib’s specifications. Additionally, take time to read through the starting implementation of fib to familiarize yourself with what has been completed.

    Namely, the first base case N==0 is implemented on lines 40–42. The second base case N==1 is implemented on lines 45–48. Review these thoroughly to fully understand how the conditionals are being checked and how the return values are being handled.

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

    • The recursive case is implemented after label CALC on line 50. Notice that the starting implementation currently uses s-registers — s0 to hold N and s1 to hold the return value of fib(N-1).

    • (Q) An alternative is to use t-registers instead. What are the differences between using s and t registers to implement fib? Are there any performance differences between the two? Which would you choose and explain why.

  4. Choose whether you want to finish fib using s or t-registers, and modify fib accordingly. If you choose to use s-registers, you must preserve/restore them before changing their values; if you choose to use t-registers, you must preserve/restore them across the recursive fib procedure calls. Be sure to follow all procedure calling conventions, not just the ones associated with s and t-registers.

  5. Implement and test fib with your choice of registers.

    • Implement your choice of saving strategy 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 register use and allocation. Update the comments to reflect your design indicating which registers you chose.

    • To check compliance with calling conventions, replace your fib calls with fibtest. This is similar to ProcedureConventionTester from p4.

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

  6. With a working implementation of fib, answer the following questions.

    • (Q) With your chosen approach, how is your stack frame organized for each fib call? Create a table describing how your stack frame is organized (each table row illustrates a word on the stack, detail the SP offset, content on the stack, etc.).

    • (Q) If you call fib(5), does it behave as expected? How many times is fib recursively called?

  7. In fib, you should have two internal calls to fib. Assemble and set a breakpoint at the line right AFTER the first internal call to fib. Then, while calculating fib(5), observe the state of the stack when the breakpoint is hit (i.e., when the first recursive jal ra, fib returns).

    Recall that the stack “grows downwards” (sp decrements), therefore you will be reading the table “backwards”. You may also want to uncheck the Hexadecimal Values checkbox to read the stack contents in decimal.

    • (Q) Take a screenshot of the stack in RARS (Execute tab → Data Segment panel → dropdown Menu → current sp), and use colored boxes to box out each stack frame

      The screenshot below demonstrates what is expected for the worksheet. Note that this is running fib(8) with the stack frames contain some junk values for demonstration — your stack should be minimally set up to implement fib.

      If you are stuck on this: the start of fib calls main in testfib, therefore by the time fib is called for the first time sp will have already moved by quite a few bytes away from the top of the stack (0x7FFFEFC). When fib is first called, sp should be at or near 0x7FFFEFBC.

  8. (Q) What happens if fib does not restore the return address before using jalr x0, 0(ra)?

  9. Complete the practical 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.

Working Ahead

If you so choose, work ahead into homework 10 to implement relPrime in RISC-V. A working version of relPrime is needed for the final practicals 9 and 10.

Submission and Grading

Functional Requirements

At the end of the practical you should have done these things:

Git Requirements

In addition to the list below, you should regularly commit and push whenever you fix a bug, work to a stopping point, or make any incremental updates. At minimum, you must have at least 5 commits in your repo for this practical (one for each function):

Commit and push via git either using VSCode’s built-in source control or with the git bash terminal. Be sure to copy your final commit ID number for the final question on the worksheet. This ID number can be found on the commit history tab on your Github repository.

Worksheet Requirement

All the practicals for CSSE232 have these general requirements:

General Requirements for all Practicals

  1. The solution fits the need
  2. Aspects of performance are discussed
  3. The solution is tested for correctness
  4. The submission shows iteration and documentation

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

Complete the worksheet. Some guidelines:

Final Checklist

Grading Breakdown

Practical 3 Rubric items Possible Points Weight
Worksheet 88 55%
Code 70 45%
Total out of 100%