University of Iowa, 2020 CS2630: Computer Organization Project 1 MiniMa: (mini) MIPS assembler written in C Goals for this assignment • Translate MAL instructions to TAL, and TAL to binary • Resolve the addresses of branch and jump labels • Build an assembler Before you start This project is fairly involved, so start early. To be prepared, you should: • review the readings from Ch 6 • complete the Stored Programs inquiry activity • take the Knowledge Check on pseudoinstructions Read the document as soon as you can and ask questions in Debug Your Brain/discussion board/office hours. The testing infrastructure is designed so that it is possible to get MiniMa working one phase at a time (there are 3 phases), so you can pace yourself. So that we know who is working together: you must declare your partner at https://uiowa.instructure.com/courses/101698/pages/sign-up-for-project-1-partner Rubric See the assignment on ICON for the rubric. Notice that non-compiling programs and programs that don’t pass any tests earn 0 points. Therefore, we cannot stress enough that you should approach this project incrementally. Consider the following stories: • Team 0xBA51C: got a few tests working each day, running the code frequently to check. They ended up passing all tests except a couple tricky cases and got an A (> 90 %). • Team 0xCOFFEE: wrote all functionality in one all-night coding fever. They are pretty sure they covered every single case for all 3 phases. However, they never compiled or ran their code until the due date. When they did, they found it didn’t even compile. They didn’t have time to fix it and had to turn it in as is. Grade: F (0%). University of Iowa, 2020 Setup You can git clone (or download zip) the project from https://research-git.uiowa.edu/cs2630-assignments/minima-c Log into this website using your hawkid and password. A note on collaboration: We encourage you and your partner to create a https://research- git.uiowa.edu/ repository to collaborate on your code more effectively. If you do so, you must mark your repository Private and add your partner by going to Members and inviting your partner by hawkid. Repositories marked Internal or Public will be considered an intent to cheat by sharing code with other students. Introduction In this project, you will be writing some components of a basic assembler for MIPS, called MiniMa (mini MIPS assembler). You will be writing MiniMa in Java. The input to MiniMa is an array of Instruction objects. The Instruction class has several fields indicating different aspects of the instruction. MiniMa does not include a parser to turn a text file into Instruction objects, so you will write programs using the functions in InstructionFactory, which creates Instructions. struct Instruction { enum ID instruction_id; // id indicating the instruction uint8_t rd; // register number destination University of Iowa, 2020 uint8_t rs; // register number source uint8_t rt; // register number secondary source int32_t immediate; // immediate, may use up to 32 bits uint32_t jump_address; // jump address uint8_t shift_amount; // shift amount char label[MAX_LABEL_LENGTH]; // label of the line this Instruction appears on char branch_label[MAX_LABEL_LENGTH]; // label used by branch or jump instructions }; MiniMa 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. 1. Convert MAL to TAL In this phase, MiniMa converts any pseudo instructions into TAL instructions. Specifically, MiniMa creates a new output array of Instruction objects and stores the TAL instructions into it in order. For any true instruction in the input, MiniMa just copies it from the input to the output. For any pseudo instruction, MiniMa writes 1-3 real instructions into the output. Examples: Ex a) label2: addu $t0,$zero,$zero This instruction will be provided to you as the Instruction object: Instruction_id rd rs rt imm jump_address shift_amount label branch_label addu 8 0 0 0 0 0 “label2” 0 Because this instruction is already a TAL instruction, you will just copy it into the output array. Ex b) blt $s0, $t0, label3 This pseudo instruction, will be provided to you as the instruction object: Instruction_id rd rs rt imm jump_address shift_amount label branch_label blt 8 0 0 0 0 0 “” “label3″ Note that label=”” because the line the instruction was on is unlabeled. This instruction is a pseudo instruction, so we must translate it to TAL instructions. In this case: slt $at,$s0,$t0 University of Iowa, 2020 bne $at,$zero,label3 Which you will represent with the following two Instruction objects. Instruction_id rd rs rt imm jump_address shift_amount label branch_label slt 1 16 8 0 0 0 “” “” Instruction_id rd rs rt imm jump_address shift_amount label branch_label bne 0 1 0 0 0 0 “” “label3″ 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 have Immediate=0 in phase 1. Instead, 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. This is just the end of the Part 1 background information. There are no tasks to do yet, so keep reading! 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. Example before phase2: branch target for branch instructions indicated using branch_label field Address Label Instruction Important instruction field values 0x00400000 label1: addu $t0,$t0,$t1 label=”label1″ 0x00400004 ori $t0,$t0,0xFF 0x00400008 label2: beq $t0,$t2,label1 label=”label2″, branch_label=”label1″ 0x0040000C addiu $t1,$t1,-1 0x00400010 label3: addiu $t2,$t2,-1 label=”label3″ after phase2: branch target for branch instructions indicated using immediate field Address Label Instruction Important instruction field values 0x00400000 label1: addu $t0,$t0,$t1 University of Iowa, 2020 0x00400004 ori $t0,$t0,0xFF 0x00400008 label2: beq $t0,$t2,-3 immediate = -3 0x0040000C addiu $t1,$t1,-1 0x00400010 label3: addiu $t2,$t2,-1 This is just the end of the Part 2 background information. There are no tasks to do yet, so keep reading! 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. To limit the work you have to do, MiniMa only needs to support the following instructions: Instruction addiu (whether it is MAL depends on imm) sll addu or beq bne slt lui move (always MAL) ori (whether it is MAL depends on imm) blt (always MAL) bge (always MAL) This is just the end of the Part 3 background information. Your tasks begin in the next section. What you need to do 1. You will complete the implementation of phase 1 by modifying the file Phase1.c. Do not modify Phase1.h. /* Translates the MAL instruction to 1-3 TAL instructions * and returns the TAL instructions in a list * * mals: input pro
gram as a list of Instruction objects * tals: after the function returns, will contain TAL instructions (should be same size or longer than input list) */ void mal_to_tal(struct ArrayList *mals, struct ArrayList *tals); University of Iowa, 2020 If a MAL Instruction is already in TAL format, then you should just copy that Instruction object into your output list. • It is strongly discouraged to modify the fields of an Instruction object individually. Instead you should do the below. • To create an Instruction with specific fields, see the functions in InstructionFactory.h. Find examples of their usage in AssemblerTest.c. 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 result ArrayList. 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 immediates in phase 1 (see phase 1 description above). Use the following translations for pseudo instructions. These translations are the same as MARS uses. I. Instruction passed to mal_to_tal: addiu r1,r2,Immediate # when immediate is too large (note that addi/addiu RTL has sign extension) => Instructions returned from mal_to_tal: lui $at,Upper 16-bit immediate ori $at,$at,Lower 16-bit immediate addu r1,r2,$at Note that lui will never be given an immediate too large because it is not well-defined for more than 16 bits (MARS also disallows lui with >16-bit immediate, try it yourself). II. Instruction passed to mal_to_tal: blt r1,r2,gohere => Instructions returned from mal_to_tal: slt $at,r1,r2 bne $at,$zero,gohere III. Instruction passed to mal_to_tal: bge rs,rt,hello => Instructions returned from mal_to_tal: slt $at,r1,r2 beq $at,$zero,hello University of Iowa, 2020 IV. Instruction passed to mal_to_tal: ori r1,r2,Immediate # when immediate is too large (note that ori RTL has zero extension) => Instructions returned from mal_to_tal: lui $at,Upper 16-bit immediate ori $at,$at,Lower 16-bit immediate or r1,r2,$at V. Instruction passed to mal_to_tal: move r1,r2 => Instructions returned from mal_to_tal: addu r1, $0, r2 NOTES: If in doubt about a case of translation there are things you can do before asking for help. 1) examine the test cases, and 2) assemble the test program in MARS to see what it produces You only need to support the instructions that are already uncommented in Instruction.c. You should not change Instruction.c or InstructionFactory.c. 2. You will complete the implementation of phase 2 by implementing the 2-pass address resolution in a function called resolve_addresses in Phase2.c. Do not modify Phase2.h. /* Returns a list of copies of the Instructions with the * immediate field (i-type) or jump_address (j-type) of the instruction filled in * with the address calculated from the branch_label. * * The instruction should not be changed if it is not a branch or jump instruction. * * unresolved: input program, whose branch/jump instructions don’t have resolved immediate/jump_address * first_pc: address where the first instruction of the program will eventually be placed in memory * resolved: after the function returns, resolved contains the resulting instructions */ void resolve_addresses(struct ArrayList *unresolved, uint32_t first_pc, struct ArrayList *resolved); Using our example from the phase 2 description: Address Label Instruction Important instruction field values University of Iowa, 2020 0x00400000 label1: addu $t0,$t0,$t1 label=”label1″ 0x00400004 ori $t0,$t0,0xFF 0x00400008 label2: beq $t0,$t2,label1 label=”label2″, branch_label=1 0x0040000C addiu $t1,$t1,-1 0x00400010 label3: addiu $t2,$t2,-1 label=”label3” The first_pc argument is the address where the first instruction in unresolved would be written to memory after phase 3. Using the above example, resolve_addresses would be called with first_pc=0x00400000. Refer to the earlier description of phase 2 for how to calculate the immediate field. 3. You will complete the implementation of phase 3 by implementing the function translate_instruction in Phase3.c. Do not modify Phase3.h. /* Translate each Instruction object into * a 32-bit number. * * tals: list of Instructions to translate * * returns a list of instructions in their 32-bit binary representation * */ public static List translate_instructions(List tals) This function produces an encoding of each R-type, I-type, or J-type instruction. Refer to the MIPS reference sheet for format of the 32-bit format. Make sure to set unused fields to 0. This default value is not required by the MIPS architecture, but it is required by the provided MiniMa test code. You’ll also notice that MARS chooses to use 0 for unused fields. General implementation help • .h files are header files, which declare symbols (functions, structs, enums) that are defined elsewhere in a .c file. The idea of putting declarations in an .h file and definitions in a .c file is roughly analogous to putting declarations in an interface and definitions in a class in Java. • If you need a function or struct declared in a .h file, then put the following at the top of your .c file. #include “filename.h” University of Iowa, 2020 For example, if your code needed to refer to struct Instruction, then put #include “Instruction.h” • We’ve structured the skeleton code so that you only need to modify… o Phase1.c o Phase2.c o Phase3.c o AssemblerTest.c (optional but recommended) Running and testing your code The three phases are run on several test inputs by … make ./AssemblerTest The provided test cases separately test the three Phases. Therefore, you’ll have good evidence for a correct Phase when all tests named by that Phase # are passing. You can add your own tests to AssemblerTest.java. Use an existing test as a template. If you don’t want to manually calculate what phase3_expected should be for your test, you can let MARS do it for you: assemble your input program in MARS and look at the Code column in the Text Segment. You should add additional test cases to AssemblerTest.java. Find corner cases the tests do not cover: • other input instructions • I-type instructions that do or do not exceed 16 bits • different label positions • different combinations of instructions You are responsible for testing your assembler beyond the given tests. We will use additional tests during grading. Testing tips When you run the tests, you’ll get a message like. Assertion failed: (size(expectedP1) == size(tals)), function testHelperPhase1, file AssemblerTest.c, line 18. Since many tests call testHelperPhase1, this information alone is not enough to know which test failed. You’ll need a stack trace. To get one, use gdb. Here’s an example interaction. University of Iowa, 2020 gdb ./AssemblerTest (gdb) run (gdb) bt #0 0x00007ffff7deee35 in raise () from /lib64/libc.so.6 #1 0x00007ffff7dd9895 in abort () from /lib64/libc.so.6 #2 0x00007ffff7dd9769 in __assert_fail_base.cold () from /lib64/libc.so.6 #3 0x00007ffff7de7566 in __assert_fail () from /lib64/libc.so.6 #4 0x000000000040249d in testHelperPhase1 (input=0x40b2a0, expectedP1=0x40b650) at AssemblerTest.c:18 #5 0x0000000000402c17 in test1Phase1 () at AssemblerTest.c:80 #6 0x00000000004067b0 in main () at AssemblerTest.c:1174 Aha! It was test1Phase1 that failed. From here you could examine the variable values by adding print statements or by continuing your gdb interaction. Tip: the frame command in gdb takes an argument N and goes to the function call labeled #N in the stack trace. (gdb) frame 4 #4 0x000000000040249d in testHelperPhase1 (input=0x40b2a0, expectedP1=0x40b650) at AssemblerTest.c:18 18 assert(size(expectedP
1) == size(tals)); (gdb) display size(expectedP1) 1: size(expectedP1) = 7 (gdb) display size(tals) 2: size(tals) = 0 What to submit For credit your MiniMa implementation must at least compile and be runnable. You should not depend on modifications to files other than those you are submitting: Required: • Phase1.c (method implemented) • Phase2.c (method implemented) • Phase3.c (method implemented) Both partners are responsible for double-double-checking that 3 files submitted to ICON are the version of the files that you intended. Good job! Once you have completed this project, if you added support for the rest of the MIPS instructions and the dot (.) directives you could replace the assembler of MARS (i.e., the code behind this button ). The only piece we’ve excluded is the parser that turns text files of MIPS code into our internal representation of instructions: a list of Instruction objects.
