Description
Goal
The first goal is examine dynamic allocation and de-allocation in C. You will see the danger of dangling
pointers and get a taste for how to avoid them.
Then you will extend the SM213 implementation to support static control flow, including static
procedure calls. You will use this expanded machine to examine the compiler implementation of forloops, if-then-else statements, procedure calls and return. One goal is to understand the role of pcrelative addressing, conditional and unconditional branch statements in support of high-level language
constructs such as loops and if, connecting your existing understanding of these language features to
what you now know about the execution of programs in hardware. Another goal is to understand the
role of the PC register in implementing jumps to see that a jump is really just an assignment of a new
value to this register. The final goal is to contrast the use of static and dynamic jumps in implement
procedure call and return and to understand how the return instruction knows to which instruction it
should jump.
Groups
To encourage you to be more interactive with each other in labs and to give you an additional way to get
help with the learning goals of assignments — helping each other — you may do this assignment in
groups of two if you like. If you do, be sure that you both contribute equally to the assignment and that
you each work on every part of the assignment. Do not split up the assignment in such a way that one of
you does one part and the other does another part. Keep in mind that the core benefit to you of doing the
assignment is the learning that happens while you do it. Each assignment is worth only around 1.8% of
your grade, but what you learn while doing the assignment goes a long way to determining the other
85%.
If you choose to do the entire assignment with a partner, submit one solution via handin and list both of
your names, student numbers, and computer-science login ids in the README file.
Alternatively, you can also choose to collaborate with another student for a portion of the assignment
and have your work marked individually. Do do this, simply submit your own version via handin and
list the other student as a collaborator in your README file. Just don’t do this if you and your partner are
turning in identical solutions, as we would like to realize marking efficiency where possible. You may
have at most one collaborator for the assignment; i.e., you can not collaborate with one student for one
part of the assignment and another student for another part.
Download
Download the file www.ugrad.cs.ubc.ca/~cs213/cur/Assignments/a4/code.zip, containing:
1. dangling-pointers.c
2. S5-loop.{java,c,s}
3. S5a-loop-unrolled.{c,s}
4. S6-if.{java,c,s}
5. S7-static-call.c
6. S7-static-call-regs.s
Part I: Dangling Pointers in C
The program dangling-pointers.c that you downloaded implements a stack data structure and
consists of 6 tests that can be performed on it. A stack has two operations: push and pop. Push adds
strings to the stack and pop removes them, in last-in-first-out order. So, if you push “one”, “two”, and
then “three”, in that order, three pops will give you “three”, “two”, “one”, in that order.
Compile the program and run it from the command line. The program takes one parameter, the test
number to run. For example, these two lines typed at the command line compile the program and
execute Test 1.
gcc -o dangling-pointers dangling-pointers.c
./dangling-pointers 1
Odd numbered tests appear to work while even numbered tests demonstrate symptoms of one or more
bugs. For Tests 2 and 4 the bug is in the test itself. Test 6, however, demonstrates a bug in the stack
implementation. Tests 1-4 are really a warm up for this one. The key observation you should make is
that even though Test 5 appears to work, there really is a serious bug lurking. If your test suite included
only tests like Test 5, you might miss this bug. Then when your customer ran something along the lines
of Test 6 and saw crazy behaviour, they might stop payment on their cheque.
Identify and correct each of the bugs in tests 2, 4 and 6. Clearly explain the cause of the bug and how
you fixed it. Fixing the bug in the stack implementation, the bug illustrated by test 6, is not easy. The
solution involves considering the key C deallocation issues we discussed in class. Consider these issues
and make a decision about how to solve the problem. You will likely need to change the interface to the
stack procedures. The basic structure of the tests should remain the same, however. And, importantly,
you must eliminate the bug. That is, ANY test that conforms to your new interface, including those that
push an arbitrary number of items onto the stack, must work without showing the symptoms that test 6
does.
Part II: Static Control Flow
Extending the ISA
Implement these six control-flow instructions in CPU.java. Note that in the “Format” column, capital
letters are hex digit literals and lower-case letters represent hex values referenced in the “Assembly” and
“Semantics” columns.
Do the Following
Here are the problems to solve for this week’s assignment.
1. Implement the six control-flow instructions one at a time.
2. Extend your test.s test program to include tests for each of the new instructions.
3. Compare the C versions of snippets S5 and S5a, then compare their assembly code by running
them in the simulator, S5a first. Document the changes you see in memory and registers for the
first few iterations of the loop and the last one.
4. Examine S6 and S7. Step the assembly through the simulator. Document the changes you see in
memory and registers.
What to Hand In
Use the handin program. The assignment directory is a4.
1. A single file called “README.txt” that includes your name, student number, four- or five-digit csdepartment undergraduate id (e.g., the one that’s something like a0b1).
2. If you had a partner for the entire assignment, turn in only one copy of your joint solution under
one of your ids and list both student’s complete information in the README.txt file and include
the text “PARTNER – MARK JOINTLY”.
3. If, on the other hand, you collaborated with another student for a portion of the assignment, but
your solutions are not identical and you want them marked individually, each of you should
include the other student’s complete information in your README.txt file, include the text
“COLLABORATOR – MARK SEPARATELY”, and turn in copies separately via handin.
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)
4. The README.txt file must also include all written material required by the assignment as listed
below.
5. In README.txt: description of the bugs in dangling-pointers.c tests 2, 4, and 6 and how you fixed
them.
6. You modified dangling-pointers.c with the bugs fixed.
7. Your modified CPU.java
8. Your extended test program, test.s.
9. In README.txt: your test description. Did all of the tests succeed? Does your implementation
work?
10. In README.txt: a written description of the key things you noted about the machine execution
while running snippets (S5, S6, and S7), including observations required by Questions 3 and 4.
Keep it brief, but point out what each instruction read and wrote etc.
