CS:2630, Homework 5, Summer 2018

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!

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:                         ; }
        LOADS   R1,R2
        JUMPS   R1              ; return q -- still in R3

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

if i = 0, i² = 0

if i > 0, i² = (i - 1)² + 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
;RETAD  =       0
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

        ADDSI   R3,-1           ;   -- parameter        
        ADDI    R2,R2,ARSIZE
        JSR     R1,SQUARE       ;   r = square( i - 1 ); -- r is in R3
        ADDI    R2,R2,-ARSIZE

        LOAD    R4,I            ;   -- i now in R4
        ADD     R3,R3,R4
        ADD     R3,R3,R4
        ADDSI   R3,-1           ;   r = r + i + i - 1

DONE:                           ; } else { r = i } because it's still in R3
        LOADS   R1,R2
        JUMPS   R1              ; return r -- still in R3

The above code is close to optimal. It profits from the arguments about what needs to be stored in the activation record from problem 1. It also saves the value of parameter i as late as possible, only saving it inside the if statement; it could have been saved earlier.

Note that the TESTR instruction is just a MOVECC that discards the operand after it sets the condition codes, and TESTR is just a LOADCC that operates similarly.

The trickyest thing is how, when i is zero, the value zero is returned. The above code tries to document this with the else comment. Student solutions that don't optimize as tightly are, of course, entirely OK and expected at this point in the semester.

Assignment 5, due Jun 26