CPSC 213: Assignment 4
Due Tue Oct 9 2012, 6pm
Goal
Building upon the previous assignments, this assignment extends the HLL
constructs that you will be required to understand how to implement in Asm
to include structures and procedures with parameters and local variables.
In addition, in a similar fashion to the previous assignment, you will also
practice decompiling from machine instructions HLL statements that use these
new constructs.
Provided Code
Download the example code snippets for
this assignment and carefully inspect them, comparing the HLL (.c)
versions with the SM213 Assembly (.s) version. They contain examples
of the types of statements you will be expected to be able to translate to and
from SM213 assembly language: everything from the previous assignment, plus
structure accesses, procedure calls, procedures with parameters and local
variables. Using the reference simulator, step through and convince yourself
of the correspondence between the high-level expression and the instructions
the machine executes. Note that the examples all perform some possibly useful
computation, as described in the section below. You are not expected to understand
the algorithms, but are encouraged to experiment with modifying their inputs and
running in the simulator to observe their result.
Your Task
Download the code snippets to work on and carefully
inspect them. Your task for this assignment is to produce commented SM213
Assembly versions for the first two code snippets, and produce a C version of
the last two (supplied as a .s file.) For the first snippet, some of the functions
have been provided for you; you will only need to fill in the body of the functions
marked with "**** FOR YOU TO COMPLETE ****", following the suggested stack
layout. When writing your solutions, refer to the provided examples and keep in mind
the following points:
- Follow the SM213 stack-based calling convention
for the procedures you write.
- Do not assume any initial value for the registers, except as specified by
the calling convention.
- You may optimise within individual procedures in the snippet; as with the
previous assignment, you are encouraged to make use of the constants and
invariants within a single statement. The only constraint is that the state of
memory after its execution conform to the same effect it would have in calling
the C function. Treat each function/procedure independently and do not optimise
across them (conform to the calling convention).
- Local variables may be kept in a register, unless there are insufficient
registers or their value needs to persist across e.g. a recursive call, in which
case they should be kept on the stack. Local arrays must be kept on the stack.
- Add comments to denote the correspondence between expressions and/or parts
thereof in the HLL snippet, and the machine instructions you generated.
- Use the reference simulator for syntax checking and testing. The code you
produce must load without syntax errors in order to receive credit for it.
- Provide a "stub", as shown in the examples, to set up the stack and call the
initial function (passing parameters, if any). End the stub with a halt instruction.
- It is recommended to start the top of the stack at the 32K position (initial
stack pointer of 0x8000, to leave plenty of available stack space.
- These are snippets, not complete programs; thus they will not compile
and run (despite looking very much like they will). In particular, notice that the
stub code cannot be expressed in C or Java.
- Assume any pointer variables have been already initialised to hold the address
of an array of unspecified but adequate size. For testing purposes you may do this
initialisation statically in the respective .long, as illustrated in the
examples. Several of the snippets also use a separate variable to hold the size of
the dynamic array. (You will learn how this happens at runtime later.)
- There are both C and Java versions of the HLL snippets. Note that the C version
is closer to the Asm as Java contains additional features (like implicit array
bounds checking) that do not appear in the Asm. Treat the Java version as a loose
conceptual equivalent, not a direct translation.
- For the third and fourth snippets, produce a .c file which contains a possible
set of functions corresponding to the machine instructions. Note that there are
many possibilities which are correct; to receive full credit, it is
sufficient that you provide one possibility that matches the algorithm
the given code implements. For example, for() and while() are
equivalent (but not do...while() --- beware!), conditional
expressions can be expressed using if(), etc. It is important that
the algorithm be explicitly present in the code, so for example if the Asm
version was an exponentiation function, you will receive no credit for
submitting only a call to pow(). Similarly, deciding whether an area
of memory is holding an array, a structure, or simply "loose" variables may be
difficult (and is impossible in general), but any possible, correct variation
will receive full credit.
- In relation to the above point, consider that arrays may be accessed by index
and iterating over its elements, while structures and loose variables cannot.
Hints
- Understand the overall structure of the code, and "linearise" the nested
block structure into ifs and goto before writing any Asm.
Do one function at a time. Inside each function, proceed as you would for the
previous assignment, with the exception of observing the calling convention.
- Notice that although SM213 has only two types of branches, thinking about
how to order the basic blocks (e.g. "top-check" vs. "bottom-check" for loops,
the order of the two clauses for an if) and the order of subtraction
in the test may eliminate any need to branch around a branch. This is shown
in the examples.
- Analyse where variables are used and their values need to be preserved
("live" in compiler terminology) and plan their allocation in registers to
help reduce unnecessary reads from memory and/or optimise register usage. One
suitable strategy is to use up the caller-save registers first (r0-r3), then
the callee-save registers (be sure to save and restore their existing values),
and any variables left over can go on the stack. The example snippets contain
comments on the stack allocation, and you are encouraged to do similarly to
keep track of what is stored where.
- For decompiling the 3rd and 4th snippet, work "backwards" from the steps you
took in writing the code for the 1st and 2nd; identify the functions, then try
to "delinearise" it into the HLL block structure, noting where branches go
and how execution flows through it, then understand how the stack is used to
recover local variables and parameters, and finally look at the operations of
the individual instructions. An assumed register allocation may be provided for you;
make use of it in commenting it to help you derive the individual HLL statements
that each may correpond to multiple machine instructions.
Provided Materials
- Example code snippets containing:
- a4_ex1.c, a4_ex1.java, and a4_ex1.s
- a4_ex2.c, a4_ex2.java, and a4_ex2.s
- a4_ex3.c, a4_ex3.java, and a4_ex3.s
- a4_ex4.c, a4_ex4.java, and a43ex4.s
- Code snippets to work on containing:
- a4_1.c and incomplete a4_1.s
- a4_2.c
- a4_3.s
- a4_4.s
Handing In
Use the handin program. The assignment directory is a4.
Please hand in exactly and only the following files with the specified names.
- README.txt that contains
- The first three lines should be your name, student number, and 4-character CS account
name, with each on a separate line, like:
John Doe
12345678
a0b1
- The statement "I have read and understood the plagiarism policies at
http://www.ugrad.cs.ubc.ca/~cs213/winter12t1/cheat.html"
Of course, make sure that's true!
- Any additional assumptions or comments you would like to make.
Following the academic conduct guidelines, if you discussed the
assignment in detail with anybody besides the instructor or TAs, say
so explicitly and list their names here.
- a4_1.s containing your solution for a4_1.c
- a4_2.s containing your solution for a4_2.c
- a4_3.c containing your solution for a4_3.s
- a3_4.c containing your solution for a4_4.s
File Format Requirements
Refer to
the section of the same name in the second assignment. Your a4_3.c and a4_4.c
should conform to the same requirements.
Snippet Descriptions
The 4 examples and snippets that you are to work on implement possibly
useful and/or interesting algorithms. This section provides a brief
description of each. Alternatively, try to figure out what they do by
experimenting, before reading this section.
a4_ex1: The Quicksort sorting algorithm.
a4_ex2: Traversing a linked list and
performing a simple operation on each node of it.
a4_ex3: Traversing a binary tree in
preorder, inorder, and postorder sequences. The contents of each node are added to an array.
a4_ex4: Searching a binary search tree
implemented using array indices instead of pointers (instead of left and right children fields of each node
being addresses, they are indices into the array, with -1 indicating there is no subtree.)
a4_1: A simple (and slow) Sudoku solver.
a4_2: Evaluating an arithmetic expression represented as a binary tree stored in
"parallel array" format.
a4_3: Description omitted deliberately, for you to think about as you
attempt to derive the corresponding HLL code for it.
a3_4: Description omitted deliberately, for you to think about as you
attempt to derive the corresponding HLL code for it.
Last modified 2012-09-29 18:15