# Assignment 6, due Feb 28

## Solutions

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (usually Friday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

1. A collection of small problems related to addressing modes:

a) Assume that the identifier A has been defined as some ASCII character. Write SMAL Hawk assembly code to load A into R3. (0.2 points)

```        LIS     R3,A
```

b) Assume that the identifier B is the memory address of a global variable. Write SMAL Hawk assembly code to load the value of the variable at B into R3. (0.2 points)

```        LIL     R3,B    ; get the address of B
```

c) Assume that the identifier C is the displacement of a local variable from the start of the activation record. Write SMAL Hawk assembly code to load the value of the variable at C into R3. (0.2 points)

```        LOAD    R3,R2,C
```

d) Assume that R3 holds the address of a variable in memory. Write SMAL Hawk assembly code to load the value of that variable into R4. (0.2 points)

```        LOADS   R4,R3
```

e) Assume that the identifier E is the displacement of a field of a record pointed to by R3 Write SMAL Hawk assembly code to load the value of the record field E into R4. (0.2 points)

```        LOAD    R4,R3,E
```

2. Background: Here is the source code for the program mp1test.a that was used to test MP1. A few lines have been deleted, but all the comments are still there.
```        TITLE   "mp1test.a test program for MP1"

USE     "hawk.h"
USE     "monitor.h"

INT     MAIN
S       MAIN

; traverse a list of records starting with HEAD

; each record contains the following fields:
NEXT    =       0       ; 32-bit pointer to the next record, or NULL
X       =       4       ; 32-bit X coordinate
Y       =       8       ; 32-bit Y coordinate
TEXT    =       12      ; 32-bit pointer to the text to output at X and Y

; the main program activation record
ARSIZE  =       4

; the main program
MAIN:   STORES  R1,R2

LOOP:
TESTR   R8
BZS     QUIT            ; while (p != NULL) do {

_LOAD____R3,R8,X____     ;   -- parameter p->x    (a)
_LOAD____R4,R8,Y____     ;   -- parameter p->y    (b)
LIL     R1,PUTAT
JSRS    R1,R1           ;   putat( p->x, p->y )

_LOAD____R3,R8,TEXT_     ;   -- parameter p->text (c)
LIL     R1,PUTS
JSRS    R1,R1           ;   puts( p->text )

_LOAD____R8,R8,NEXT_     ;   p = p->next          (d)

BR      LOOP            ; }
QUIT:
```

A Problem Give the correct code for the comments for the the lines with the blanks and the right marginal (a) (b) (c) and (d). (0.2 points each)

The blanks have been filled in above.

Note: Please do not turn in the whole program. Just indicate the correct line of code for each part.

Aside: You can test your code by assembling it and linking the object of your assembly with your solution to MP1 in order to demonstrate that it does exactly the same thing as the official MP1 test program.

3. Background: Consider this definition of a mathematical function f defined over non-negative integers:

if a = 0: f(a,b) = 0

if a ≠ 0: f(a,b) = f(b,a – 1) + b

For example: f(1,2) = f(2,0) + 2 = (f(0,1) + 0) + 2 = (0 + 0) + 2 = 2

a) Write SMAL code for a recursive Hawk subroutine to compute f. The subroutine should be called (creatively) F, and of course, you should write clear and easy to read code. (1.0 points)

The first version of the code given here is stupid, completely non-optimized

```; activation record for F
A       =       4       ; parameter a
B       =       8       ; parameter b
ARSIZE  =       12

; code for F
F:      ; expects R3 = parameter a
;         R4 = parameter b
STORE   R3,R2,A
STORE   R4,R2,B         ; -- save parameters

CMPI    R3,0
BNE     FELSE           ; if (a == 0) {

LIS     R3,0
JUMPS   R1              ;   return 0

BR      FENDIF
FELSE:                          ; } else {

LOAD    R3,R2,B         ;   -- parameter b
ADDI    R4,R4,-1        ;   -- parameter a - 1
JSR     R1,F
ADDI    R2,R2,-ARSIZE   ;   -- f(b, a - 1)
ADD     R3,R3,R4        ;   -- f(b, a - 1) + b
JUMPS   R1              ;   return f(b, a - 1) + b

FENDIF:                         ; }
JUMPS   R1              ; return ?
```

You might have noticed some weaknesses in the above code. The function body consists of an if-then-else construct which was coded before paying any attention to the statements in the two branches of the code. As a result, there is dead code (an extra return at the end of the function, and a branch instruction that is never used. Not very smart, but that is what happens when you write code mindlessly, first writing high-level code in the comments and then writing the assembly code for each line of the comments without any attention to the global structure of the code. Here is the result of optimizing the above code:

```; activation record for F
B       =       4       ; parameter b
ARSIZE  =       8

; code for F
F:      ; expects R3 = parameter a
;         R4 = parameter b
STORES  R1,R2
STORE   R3,R2,A
STORE   R4,R2,B         ; -- save parameters

TESTR   R3
BZS     FENDIF          ; if (a != 0) {

ADDI    R4,R3,-1        ;   -- second parameter a - 1
LOAD    R3,R2,B         ;   -- first parameter b
JSR     R1,F
ADDI    R2,R2,-ARSIZE   ;   -- f(b, a - 1)
ADD     R3,R3,R4        ;   r = f(b, a - 1) + b

; } else {
;   r = 0  -- this is true from BZS
FENDIF:                         ; }