Project 1
MIPS Assembler Programming in Java
Acknowledgment: Adapted from Brandon Mayers (Univ. of Iowa)
Goals
· Learn how to translate MAL (MIPS assembly language) instructions to TAL (true assembly language)
· Learn how to translate TAL to machine code (binary)
· Learn how an assembler calculates addresses for (labeled) branches
Before you start
This project is fairly involved, so start early. Read the document as soon as you can and ask questions in TA office hours. It is possible to get it working one phase at a time (there are 3 phases), so you can pace yourself. Download the assembler code skeleton here.
Assembler Skeleton
In this project, you will be writing some components of a basic assembler for MIPS. You will be writing it in Java, a language you are already comfortable with, so that you can focus your attention on the translation of MIPS programs.
The input to your assembler is an array of Instruction objects. The Instruction class has several fields indicating different aspects of the instruction. Note it does not include a parser to turn a text file into Instruction objects, so you will write programs in terms of Instruction objects.
The assembler has three basic phases for translating a MIPS program into binary. The next three sections describe these phases. The section after that “What you need to do” will describe your job in Project 1.
Phase 1: Convert MAL to TAL
In this phase, the assembler converts any pseudo instructions into TAL instructions. Specifically, a new output array of Instruction objects is created to store the TAL instructions into it in the original order. For any true instruction in the input, you just need to copy the instruction from the input to the output. For any pseudo instruction, you will need to translate it into 1-3 real instructions and store them in the output. You may refer to the full list of MIPS pseudo-instructions here.
We used at (the assembler register) to store the result of the comparison. Since MIPS programmers are not allowed to use at themselves, we know we can safely use it for passing data between generated TAL instructions.
IMPORTANT: Notice that branch instructions do NOT have an Immediate in Phase 1. Rather, they specify the target using branch_label. In Phase 2, the branch_label will get translated into the correct immediate.
You must also make sure that you detect I-type instructions that use an immediate using more than the bottom 16 bits of the immediate field and translate them to the appropriate sequence of instructions.
Phase 2: Convert labels into addresses
This phase converts logical labels into actual addresses. This process requires two passes over the instruction array.
· Pass one: find the mapping of labels to the PC where that label occurs
· Pass two: for each instruction with a non-zero branch_label (jumps and branches) calculate the appropriate address using the mapping.
Phase 3: Translate instructions to binary
This phase converts each Instruction to a 32-bit integer using the MIPS instruction encoding, as specified by the MIPS reference card. We will be able to test the output of this final phase by using MARs to translate the same input instructions and compare them byte-for-byte.
Here are the ID numbers for the instruction_id field of the Instruction objects. IMPORTANT: these IDs are used as internal encoding for the type of an Instruction object. Instruction_id is not the same as the opcode or funct fields of binary MIPS instructions.
The assembler only needs to support the following instructions
If a MAL Instruction is already in TAL format, then you should just copy that Instruction object into your output list. You should not change input instructions. If you need to copy an instruction in any phase, then use Instruction.copy.
If a MAL Instruction is a pseudo-instruction, such as blt, then you should create the TAL Instructions that it translates to in order in the buffer and return the number of instructions.
You must check I-type instructions for the case where the immediate does not fit into 16 bits and translate it to lui, ori, followed by the appropriate r-type instruction. Remember: the 16-bit immediate check does not need to be done on branch instructions because they do not have immediate in phase 1 (see phase 1 description above).
Use the following translations for pseudo instructions. These examples of translations are the same as MARS uses.
Running and testing your code
The three phases are run on a test case by running the JUnit test file AssemblerTest.java. The provided test, test1, will run each of the 3 phases in order. Each phase is followed by a check that the output is correct up to that point. If the test fails, JUnit will produce a useful error message.
You can add your own tests to AssemblerTest.java. Use test1 as an example; notice that it uses a helper function to actually run the tests.
You must add at least one additional test to AssemblerTest.java. Significantly different means you must test things that test1 doesn’t cover, such as other input instructions and I-type instructions that do not exceed 16 bits.
You are responsible for testing your assembler beyond test1. We will use more tests during grading.
Note that the assembler skeleton does not currently have a parser, so you must provide the input program as a sequence Instruction objects (see the list called input in test1).
What to submit
For full credit your implementation must compile and run correctly. You should not depend on modifications to Instruction.java or add additional java files!
You need to modify the following files:
Phase1.java
Phase2.java
Phase3.java
AssemberTest.java
How to run your tests
If you are not familiar with Junit tests, you can follow those steps:
1. go to https://github.com/junit-team/junit4/wiki/download-and-install and download junit.jar and add it to your project folder. (for example: junit-4.13-beta-2.jar)
2. go to https://code.google.com/archive/p/hamcrest/downloads and download the hamcrest-all jar and add it to your project folder (for example: hamcrest-all-1.3.jar)
Now when you compile and test, you just need to include these libraries on your classpath. So, to compile, do (inside the project directory):
$ javac -cp .:hamcrest-all-1.3.jar:junit-4.13-beta-2.jar *.java
To run the tests, you need to use one of the JUnit runners and pass AssemblerTest as test class:
$ java -cp .:hamcrest-all-1.3.jar:junit-4.13-beta-2.jar org.junit.runner.JUnitCore AssemblerTest
