Assignment 6, due Feb 28

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
           LOADS   R3,R3	; use the address to get the value
   

   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
           EXT     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
   ;RETAD  =       0
   
   ; the main program
   MAIN:   STORES  R1,R2
           ADDI    R2,R2,ARSIZE
   
           LIL     R8,HEAD         ; p = head
   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:
           ADDI    R2,R2,-ARSIZE
           LOADS   R1,R2
           JUMPS   R1              ; return to the monitor to stop
   

   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
   RETAD   =       0       ; return address
   A       =       4       ; parameter a
   B       =       8       ; parameter b
   ARSIZE  =       12
   
   ; code for F
   F:      ; expects R3 = parameter a
           ;         R4 = parameter b
           STORE   R1,R2,RETAD
           STORE   R3,R2,A
           STORE   R4,R2,B         ; -- save parameters
   
           LOAD    R3,R2,A
           CMPI    R3,0
           BNE     FELSE           ; if (a == 0) {
   
           LIS     R3,0
           LOAD    R1,R2,RETAD
           JUMPS   R1              ;   return 0
   
           BR      FENDIF
   FELSE:                          ; } else {
   
           LOAD    R3,R2,B         ;   -- parameter b
           LOAD    R4,R2,A
           ADDI    R4,R4,-1        ;   -- parameter a - 1
           ADDI    R2,R2,ARSIZE
           JSR     R1,F
           ADDI    R2,R2,-ARSIZE   ;   -- f(b, a - 1)
           LOAD    R4,R2,B
           ADD     R3,R3,R4        ;   -- f(b, a - 1) + b
           LOAD    R1,R2,RETAD
           JUMPS   R1              ;   return f(b, a - 1) + b
   
   FENDIF:                         ; }
           LOAD    R1,R2,RETAD
           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
   ;RETAD  =       0       ; return address
   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
           ADDI    R2,R2,ARSIZE
           JSR     R1,F
           ADDI    R2,R2,-ARSIZE   ;   -- f(b, a - 1)
           LOAD    R4,R2,B
           ADD     R3,R3,R4        ;   r = f(b, a - 1) + b
   
                                   ; } else {
                                   ;   r = 0  -- this is true from BZS
   FENDIF:                         ; }
   
           LOADS   R1,R2
           JUMPS   R1              ; return r
   

   The above code is harder to write and harder to read.

   b) The function f discussed here is very common. You spent considerable time studying it in elementary school. What is the proper name for f. (0.2 points)

   f(a,b) = a × b

   That is, f returns the product of its two arguments, computed by repeated addition.