Assignment 5, due Sep 26

Solutions

Part of the homework for CS:2630, Fall 2019
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Background: Study machine problem 2.
a) Write a C declaration for the struct representing one vertex in a binary tree containing the same information as is used in MP2. The code in Chapter 6 is similar to what is required, but not identical. (0.5 points)
```
struct treenode {
    struct treenode * left;
    struct treenode * right;
    char * data;
}
```
b) Write a traverse() routine in C that uses the struct type from part a) to do the traversal required by MP2. If you use it to traverse the tree in part c), it should output This is a small tree. (0.5 points)
```
void traverse(struct treenode * n) {
    if (n != NULL) {
        traverse(n->left);
        fputs(n->data,stdout);
        traverse(n->right);
    }
}
```
c) Write code to initialize a small tree where the strings are as follows. (0.5 points)
- "This " – left child
- "is a " – root
- "small " – left child of right child
- "tree." – right child
```
struct treenode lchild = { NULL, NULL, "This " };
struct treenode lrchild = { NULL, NULL, "small " };
struct treenode rchild = { &lrchild, NULL, "tree." };
struct treenode root = { &lchild, &rchild, "is a " };
```
Note: You are welcome to test it, but we won't run your code, we just want the code fragments requested.
The following main program was used to test the above code. It works.
```
int main() {
    traverse(&root);
    return 0;
}
```
Background: First-generation computers designed in the 1950s rarely had a call or jump-to-subroutine instruction. Machine instructions that both saved a return address and jumped to a subroutine were only added to the CPUs of computers after programmers began writing subroutines using the available instructions.
Assignment: Write a calling sequence equivalent to JSR R1,ROUTINE that uses only JUMP ROUTINE plus explicit code to load the return address. There are several ways to do this. (0.5 points)
Here is a solution using absolute addressing:
```
        LIL     R1,HERE
        JUMP    ROUTINE
HERE:
```
Here is a solution using PC-relative addressing:
```
        LEA     R1,HERE
        JUMP    ROUTINE
HERE:
```
A quick question: In Chapter 6, all the examles define RETAD. Is the symbol RETAD used in any of example subroutines? If so, where? If not, why not? (0.5 points)

No. (A simple text search for all instances of the string suffices to discover this.)
As is explained near the middle of the chapter, because RETAD is always defined as zero, we use LOADS and STORES to access that field of the activation record. As a result, the displacement of zero is implicit.
Background: Suppose the Hawk architecture did not sign-extend the displacement field used in the machine's memory reference instructins, so that all displacements were interpreted as positive numbers.
A question: What optomizations done in Chapter 6 would no-longer work?

The hypothetical change to the Hawk prevents use of negative displacements. This prevents us from using ARSIZE-FIELD to access fields of the activation record after R2 has already been incremented.
It also prevents many other useful things, such as PC-relative JUMP or JSR instructions that transfer control to previous locations in the code.