Lab 2: Branch Counting

Introduction

The goal of this lab is to count the number of forward and backward branch instructions in a RISC-V program binary. The solution must identify branches by checking their opcode. The branch offset encoded in the instruction determines whether the branch is forward or backward.

RISC-V Branch Instructions

There are six different types of branch instructions in RISC-V:

All branch instructions in RISC-V are encoded in the SB Type format:

In RISC-V, the relative offset of a branch instruction is encoded in bits 7-11 and 25-31 of the branch instruction. Adding this offset to the current program counter (PC) gives us the destination address. The offset is positive when jumping forwards and negative when jumping backwards.

Assignment

This assignment consists of writing a RISC-V assembly program that counts forward and backward branches in a RISC-V program. The solution must implement the branchCounting function.

The instructions array of a program is an array of RISC-V instructions in binary representation, where the instructions in the array are the instructions in the program. Each instruction is 32 bits (one instruction word) long.

The instruction array is terminated by the sentinel value 0xFFFFFFFF.

branchCounting
  This function receives a pointer to the instruction array and
  returns the number of forward and backward branches in the program.

  Arguments:
    a0: Pointer to an array of instructions terminated by the sentinel
      value 0xFFFFFFFF.

  Returns:
    a0: Number of forward branches.
    a1: Number of backward branches.

Input Guarantees

• The instructions array is terminated by the sentinel value 0xFFFFFFFF.
• All instructions in the input file are valid RISC-V instructions.
• No branches will have an offset of zero.
• There are at most 100 instructions in the input file.

Resources

• Class slides used for this lab (.pptx) (.pdf).

Testing your Lab

To execute RARS on Windows, or if you do not have rars aliased to execute RARS as a Java executable, you need to replace rars with java -jar </path/to/rars> , where </path/to/rars> is the path to RARS on your file system.

To test your lab, you must first generate your input file: the binary files for the test program. You can use any RISC-V .s files to generate the test program as long as it satisfies the constraints in the Input Guarantees section (two sample files are provided in the Tests directory). To generate the binary file, test.bin, for the test program, test.s, you can run the following command:

rars a dump .text Binary test.bin test.s

Once you have a binary, you should run branchCounting.s with RARS and must provide the binary file as the program argument.

rars branchCounting.s pa test.bin nc > lab.out

This command runs your lab solution on test.bin. The provided common.s formats and prints the return values of your branchCounting function.

CheckMyLab

This lab is supported in CheckMyLab. To get started, navigate to the BranchCounting lab in CheckMyLab found in the dashboard. From there, students can upload test cases in the My test cases table. Test cases follow the format described below. Additionally, students can upload their branchCounting.s file in the My solutions table, which will then be tested against all other valid test cases.

Uploading a Test Case

To create a test case for CheckMyLab, create the binary file for your input assembly:

[NAME].bin

where [NAME] is the name of the test case. The resulting [NAME].bin file can be uploaded to CheckMyLab.

Marking Guide

Assignments too short to be adequately judged for code quality will be given a zero for that portion of the evaluation.

• 40% for correct number of forward branches
• 40% for correct number of backward branches
• 20% for code cleanliness, readability, and comments.
• Marksheet used to mark the lab (.txt)

Submission

There is a single file to be submitted for this lab. The file name is branchCounting.s and it should contain only the code for your solution. A template branchCounting.s is provided in the code directory. You should directly modify that when solving the lab.

• Do not add a main label to branchCounting.s.
• Do not modify the line .include "common.s".
• Keep the file branchCounting.s in the Code folder of the git repository.
• Push your repository to GitHub before the deadline. Just committing will not upload your code. Check online to ensure your solution is submitted.