Description

This assignment has five parts.

First, you will complete Question 3 from Assignment 5. Then, you will extend the SM213 implementation to add the instructions we have discussed in class that support static control flow, including static procedure calls and procedure return (which is dynamic, actually).

Third, you’ll examine the assembly code for for-loops and if-statements using snippet files in the simulator and then translate a simple C file containing these control-follow statements into assembly. Fourth, you will write a fairly substantial assembly-language program that uses all of the language concepts we have discussed so far.

Finally, you will examine how programs use the runtime stack to store local variables, arguments and the return address. You will do this using a set of snippets and you will answer questions about their execution. Then, you will examine two SM213 programs that contain procedure calls to determine what they do.

Question 3 (A5) – Reference Counting [35%]

The program in the q3 directory can be built using make while in that directory. You can then run the program by typing ./main A B C D The program takes an arbitrary number of string arguments. It is supposed to print out a binary search tree, which is formed out of a subset of arguments, twice.

However, as you can clearly see, the program does not produce this output; it correctly prints only one tree. It has a bug. To see the correct output of the program, you can remove all the free() calls in the program, replacing the dangling pointer bug with a memory leak.

The implementation uses two libraries, list and tree, implementing a doubly-linked list and a binary search tree respectively. Both libraries are free of bugs if used independently, but exhibit a bug when used together.

1. Find the bug and write a careful description of it in the file q3.txt. The bug is a dangling pointer somewhere. You may also want to read the header files carefully to see whether the libraries are being misused.

2. Now, fix the bug using reference counting. You must use the provided refcount.c and .h files for reference counting (the Makefile is already setup to use them; add “#include “refcount.h”” to C files as needed). You can change the interface in element.h and any of the implementation in element.c (retaining its ability to store strings and numbers).

You should not change any of the other .h files, and make minimal changes to the other .c files aside from adding reference counting (e.g. calls to element-specific keep_ref/free_ref functions that you define). Elements must still be shared between the list and tree – you should not simply make copies of the elements (which would introduce inefficiency).

3. After fixing the bug, test your program to ensure that it produces the correct output and that valgrind reports no memory leaks. To do so, you must run the program through valgrind, which is available on the undergrad servers but likely not on other platforms you might use for other parts of the assignment.

The test you need to run is the following: valgrind –tool=memcheck –leak-check=yes ./main If you have a memory leak you will see an error that looks something like this: ==31419== LEAK SUMMARY: ==31419== definitely lost: 240 bytes in 2 blocks ==31419== indirectly lost: 240 bytes in 2 blocks If you have a dangling pointer you may see an error that looks something like this: ==31993== Invalid read of size 1 ==31993== at 0x4E7D000: vfprintf (vfprintf.c:1629) If you eliminate both bugs (your goal) then you should see output something like this: ==1272== HEAP SUMMARY: ==1272== in use at exit: 0 bytes in 0 blocks ==1272== total heap usage: 4 allocs, 4 frees, 480 bytes allocated ==1272== ==1272== All heap blocks were freed — no leaks are possible ==1272== ==1272== For counts of detected and suppressed errors, rerun with: -v ==1272== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2) Or you might see (depending on which version of valgrind you use): ==9402== LEAK SUMMARY: ==9402== definitely lost: 0 bytes in 0 blocks ==9402== indirectly lost: 0 bytes in 0 blocks ==9402== possibly lost: 0 bytes in 0 blocks ==9402== still reachable: 4,096 bytes in 1 blocks ==9402== suppressed: 25,084 bytes in 373 blocks

Question 1 (A6): Extending the ISA [10%]

Implement the following six control-flow instructions in CPU.java. The code provided with this assignment in www.students.cs.ubc.ca/~cs-213/cur/assignments/a6/code.zip includes the file CPU.java that you can use as the starting point for this assignment. Alternatively you can use the version you implemented yourself for Assignment 2.

Note that in the “Format” column below, capital letters are hex digit literals and lower-case letters represent hex values referenced in the “Assembly” and “Semantics” columns. Note that the indirect-jump offset is unsigned and so for indirect jump, pp ranges from 0 to 255. On the other hand, the branch pc-relative value is signed and so for branches, pp ranges from -128 to 127.

Question 2: Assembly code of if and loops [20%]

Example the Execution of Assembly Snippets The file www.students.cs.ubc.ca/~cs-213/cur/assignments/a6/code.zip contains the following files: • S5-loop.{java,c,s} • S5a-loop-unrolled.{c,s} Instruction Assembly Format Semantics branch br A 8-pp pc ← (A = pc + pp*2) branch if equal beq rc, A 9cpp pc ← (A = pc + pp*2) if r[c]==0 branch if greater bgt rc, A Acpp pc ← (A = pc + pp*2) if r[c]>0 jump j A B— AAAAAAAA pc ← A get pc gpc $o, rd 6Fpd r[d] ← pc + (o == p*2) indirect jump j o(rt) Ctpp pc ← r[t] + (o == pp*2) • S6-if.{java,c,s} Run each of these snippets through the simulator – your version if you completed Question 1 correctly, or the reference implementation if you didn’t.

Carefully observe what happens as they execute so that you could explain this code to someone if they asked. This step is not for marks. Q1: Translate C to assembly Translate q2.c into commented assembly code, placing your code in a file named q2.s. Labels for variables should be the name of the variable.

Run your code in the simulator and examine every variable to be sure they have the correct value when execution halts.

Question 3: Write a program in assembly [50%]

Implement an assembly-language program that examines a list of student grades and finds the student with the median average grade; this student’s id should be placed in the variable m.

Your program must correspond to a C program where the input list of students, and the output student id are given as follows. struct Student { int sid; int grade[4]; int average; // this is computed by your program }; int n; // number of students int m; // you store the median student’s id here struct Student* s; // a dynamic array of n students Your assembly file must format student records exactly as C would; i.e., a struct with 6 integers.

You must use the following assembly declarations for this input and output data. Note: this example is for an array with one student. You should obviously test your code on larger arrays. n: .long 1 # just one student m: .long 0 # put the answer here s: .long base # address of the array base: .long 1234 # student ID .long 80 # grade 0 .long 60 # grade 1 .long 78 # grade 2 .long 90 # grade 3 .long 0 # computed average Put your solution in a file named q3.s.

Work Incrementally – Do each of these steps separately! This is a very challenging programming problem. It will stretch (and strengthen) your ability manage a large number of programming details, as is required when writing assembly.

To be successful with this you must be very disciplined to program and test incrementally. Observe that the program breaks down into several subproblems. You should tackle them one at a time and thoroughly test each step before moving to the next. Here’s a list of the key subproblems.

You might want to further sub-divide things, but do not try to combine steps. 1. Compute the average grade for a single student and store it in the struct. For simplicity, you can ignore the fractional part of the average; i.e., you do not need to round. 2. Iterate through the list of students and compute their average grades and store them. 3. Swap the position of two adjacent students in the list. 4. Compare the average grades of two adjacent students and swap their position conditionally, using your code from Step 3.

5. Now consider creating a procedure to encapsulate either Step 3 or Step 4 as described in the Use Procedures section below.

6. Sort the list by average grade in ascending order. You are free to use any sort algorithm you like, but Bubble Sort is the simplest. Here’s a version of bubble (sinking) sort in C that you might consider. void sort (int* a, int n) { for (int i=n-1; i>0; i–) for (int j=1; j<=i; j++) if (a[j-1] > a[j]) { int t = a[j]; a[j] = a[j-1]; a[j-1] = t; } } Take this step by step and incorporate your work from Step 3-5 above.

For Bubble Sort, here are two subproblems. a. First, write a loop that iterates through the list once, bubbling the student with the lowest average to the top (or sinking the lowest student to the bottom). If you created a procedure in Step 5, then the inner part of this loop is a call to this procedure; otherwise it is the code from Step 4. b. Then, add the outer loop that repeats the inner loop on the unsorted sublist repeatedly until the entire list is sorted.

7. Find the median entry in the sorted list and store that student’s sid in m. For simplicity you can assume the list contains an odd number of students. Ordering and Combining Steps Notice that it is not necessary to do these steps in the order listed above. Steps 1 and 2, for example, are completely independent from Steps 3-7. Step 7 is independent from the other steps.

You could do Step 6 before Steps 3-5 and then incorporate the conditional swap once the other parts of Step 6 are working. Similarly, you can do Step 5 before Steps 3 or 4 and incorporate them into the procedure later. The key thing here is work on each piece independently and then careful combine steps to eventually produce the program.

The program itself will be on the order of 70 to 100 assembly-language instructions. That sounds like a lot … and it is. But if you think of this as seven steps each with 15 or so instructions (some will have less), its not so bad. Or maybe it will be bad, but at least not impossible. Be sure to comment every line of your code and to separate subproblems with comments and labels so that it is easy for you to see what each part of the code does without having to read the code.

Multiplying and Dividing by 24 You will have noticed that the variable s is a dynamic array of type “struct Student” and that “sizeof(struct Student)” is 24. And so you might find that you’d like to multiply or divide by 24 (i.e., to convert between an array index and a byte-offset), but you’ll recall that you can’t do this with a single instruction in our ISA. Then you’ll notice that x*24 = x*16 + x*8 and you’ll see that you can multiple by 24 (or divide) using 3 instructions (or 4 depending on how you count).

Register Allocation Keeping track of registers is going to be a challenge. Note that this program is too big for you to use a distinct register for every value in the program. You are going to have to re-use registers to store different things in different parts of the program. This will add complexity, for example, when combining two steps or when adding a step to the rest of the program.

For example, if your code for Step 4 uses register r0 and one of the loops you write in Step 6 also uses r0, you’re going to have to change one of them to use a different register (or use a procedure as described in the next section). So, for parts of the code that connect like this, some pre-planning will help. Another useful strategy is to group sections of code (one or maybe a few steps) and treat them as independent stages with respect to registers.

At the beginning of a stage you assume nothing about the current value of registers and you are free to use any registers you like within that stage. At the end of the stage, any register values that are needed by subsequent stages should be written to memory.

You may want to create some additional variables to store these temporary values. Using Procedures One way to divide code into stages is to use procedures. Step 5 suggests that you do this to encapsulate the code that conditionally swaps two adjacent elements of the list (i.e., Steps 3 and 4).

You can use this approach to simplify register management by having the procedure save registers to memory before it starts and restore them from memory before it returns (e.g., using temporary variables).

Any register the procedure saves in this way is a register it is free to use without interfering with the registers used in the two loops in Step 6 that call it. This swap procedure needs one argument / parameter: i.e., the index of one of the array elements to swap. The index of the other element is this value plus or minus one, depending on how you do it.

The caller should pass this value in a register; for example if the loop has the index in r4 then the procedure should just use r4 to get this value. Use gpc and j to call the procedure and use the indirect jump to return.

Do not worry about creating a stack. All of this is optional, and you can do this for other parts of your program as well. Partial Marks — Work Incrementally Finally, partial marks (if you need them … probably not!) will be awarded based on the number of the steps listed above that you’ve written correctly. Submitting a big blob of assembly that doesn’t do any of the steps right won’t be worth anything. So, work incrementally. Test each step separately. Once you have a step working, save it in an auxiliary file just in case.

Question 4 – The Stack [20%]

The file provided code contains the following files. • S7-static-call.{java,c} and S7-static-call-{stack,reg}.s • S8-locals-args.{java,c,s} • S9-args.{java,c} and S9-args-{stack,regs}.s Evaluating Snippets using Simulator Familiarize yourself with snippets 7-9 by running them in the simulator and asking yourself the following questions.

This part is not for marks. • Carefully examine the execution of S7-static-call-stack in the simulator and compare it to S7-static-call-regs. Run the snippets and look carefully at what happens. Ask yourself these questions. a) What is the difference between the two approaches? b) What is one benefit the approach followed in stack? c) What is one benefit of the approach followed in reg? • Carefully examine the execution of S8-locals-args.s in the simulator.

Ask yourself these questions. d) What lines of foo and b allocate b’s stack frame? e) What the lines of foo and b de-allocate b’s stack frame? The next two questions ask you to consider changing b so that it has 3 arguments and 4 local variables. Ask yourself these questions. f) What changes required in b to add the arguments and locals; note that you do not actually use these new variables in any way? g) What changes required in foo to call b(0,1,2)?

• Carefully examine both versions of S9-args-stack.s and S9-args-regs in the simulator. Ask yourself these questions. h) What memory accesses does stack makes that regs doesn’t make? i) How many more memory accesses does stack make, compared to regs?

Questions 4a and 4b [20%] The next two question use these files found in code.zip. • q4a.s • q4b.s Answer the next two questions by modifying the .s files and by writing .c files. The .c files must compile and execute. When they execute they must perform the same computation as the .s file and print out the value of its static variables, one per line as a decimal number (nothing other than that number on each line). This means that q4a.c must print 10 lines of numbers and q4b.c must print 16. 1. [10%] Examine q4a.s and its execution in the simulator.

Add a comment to every line that explains what that line does in as high-level a way as possible. Then, write an equivalent C program called q4a.c that is the most likely candidate for the file that was compiled into q4a.s. Use the same variable and procedure names in this program that you used in the assembly-file comments. Ensure that there is a correspondence between lines in the assembly file and lines of the C program, but do not include the start procedure in q4a.c; this procedure is added automatically by the c compiler to initialize the stack and call main.

The end of your main procedure should print the value of the program’s ten static variables as described above. You may notice a register that is used in a way that is best explained by saying that it is a local variable, even if its value is never read from or written to the stack. Avoiding these memory accesses is a common optimization compilers make for local variables. 2.

[10%] Do the same for q4b.s. What to Hand In Use the handin program. The assignment directory is ~/cs-213/a6, it should contain a directory named q3 and the following plain-text files. 1. in the q3 directory: q3.txt, element.c, element.h, list.c, main.c, and tree.c. 2. CPU.java that contains your implementation of the new instructions listed in Question 1 as well as a correct implementation of the part of the ISA you implemented previously. 3. q2.s that contain your answer to Question 2. 4. q3.s that contains your answer to Question 3. 5. q4a.s, q4a.c, q4b.s, and q4b.c that contain your answers to Question 4.