# Assignment 5, due Jun 26

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 (Tuesday or Thursday). 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. Background: The Hawk monitor has an unsigned divide routine, DIVIDEU, but no signed divide. If you wanted to write a signed divide in C or Java based on an unsigned divide routine, it might look like this:
```int divide( a, b ) {
bool flip = false;
if (a < 0) {
a = -a;
flip = !flip
}
if (b < 0) {
b = -b;
flip = !flip
}
int q = divideu( a, b ); /* unsigned division */    /* c */
if (flip) {                                         /* c */
q = -q;                                         /* c */
}                                                   /* c */
return q;                                           /* c */
}
```

You can assume that the parameters a and b are passed in R3 and R4; this applies equally to DIVIDEU and DIVIDE. Assume the standard Hawk calling conventions apply everywhere, that is, assume that DIVIDEU obeys them and that any code you write for DIVIDE must obey them. Ignore the remainder after division.

This code has 4 named variables, including its parameters, the the largest sensible activation record would hold 5 fields, the return address plus the saved values of a, b, flip, and q.

a) Suppose we decided to use R8 to hold flip. Does doing this change the size of the activation record? Do not answer this until you have reviewed the Hawk calling conventions. (0.5 points)

The location for saving R8 would be in the activation record in place of the location to hold flip, so the activation redord size would be unchanged.

Here is some more detail: If the called subroutine uses R8, the Hawk calling conventions require that it first save the previous value of R8 and then, when done with R8, it must restore the saved value.

b) Which variables mentioned above must be stored in the activation record, and which variable can be held in a register for its entire lifetime, eliminating the need for a field in the activation record? For each variable that must be stored in an activation record, what code above wipes out the register it would otherwise occupy. The goal of this question is to shrink the activation record to its minimum necessary size. (0.5 points)

a is received in R3 and can stay there until the call to DIVIDEU, which expects the same value in R3. After the call, a is no longer needed, so it need not be saved in the activation record.

b is received in R4 and passed to DIVIDEU in R4, and never needs to be saved, just like a.

flip is set before the call to DIVIDEU and inspected afterwards. Therefore, flip must be saved in the activation record or something else must be saved, as suggested in part a). In either case, we must reserve one word of the activation record because of the need to preserve flip.

q holds the value returned by DIVIDEU in R3 and then it is returned to the caller of DIVIDEU, also in R3. Therefore, it may as well stay in R3 the whole time.

c) Assuming that FLIP is a local variable in the activation record, write SMAL Hawk code for the part of the above code commented with /* c */ (0.5 points)

In the following code, following the arguments from part b) above, we assume that R3 already holds a and R4 already holds b.

```        ADDI    R1,R1,ARSIZE
LIL     R1,DIVIDEU
JSRS    R1,R1
ADDI    R1,R1,-ARSIZE   ; q = divideu( a, b ) -- q is in R3

TEST    R2,FLIP
BZS     NOFLIP          ; if (flip) {
NEG     R3,R3           ;   q = -q
NOFLIP:                         ; }
JUMPS   R1              ; return q -- still in R3
```

2. Background: In class on Thursday, we wrote an iterative program to compute squares using mathematical formulation similar to this:

if i = 0, i2 = 0

if i > 0, i2 = (i - 1)2 + 2i - 1

This formula is recursive, so naturally, we can write a recursive function, square to compute the square of a number.

A problem: Reduce this to well commented SMAL Hawk code. (1.5 points)

```; activation record layout for SQUARE
I       =       4       ; save location for parameter
ARSIZE  =       8
SQUARE:         ; expects parameter i in R3
STORES  R1,R2

TESTR   R3
BZS     DONE            ; if (i != 0) {
STORE   R3,I

JSR     R1,SQUARE       ;   r = square( i - 1 ); -- r is in R3

LOAD    R4,I            ;   -- i now in R4