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)

   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)

   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)

2. 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)