Assignment 6, Solutions

Part of the homework for 22C:60, Fall 2010
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Here is the mp1test program, with some unfinished pieces in it:

    The problem: Fix the above code. Several small pieces have been deleted. If you correctly repair the code, it will work as a test program for MP1. Comments in the code indicate each deletion of one or more lines. Parts a, b, c, d and e above are indicated by comments in the code. (0.4 points each, for a total of 2 points)

    The solution is given below, in the commented lines following the comments indicating missing material. 

            TITLE   "mp1test.a, test program for MP1 by Douglas Jones"
        S       START
        USE     "hawk.macs"
        USE     "monitor.h"
        EXT     UNUSED
        EXT     ROOT

; description of the structure of each node:
LEFT    =       0
RIGHT   =       4
TEXT    =       8

; activation record structure for TRAVERSE
NODE    =       4
;ARSIZE  =       ????(a)????
ARSIZE  =       8               ;====(a)====

TRAVERSE:
        STORES  R1,R2
        TESTR   R3
        BZS     TRAVQT          ; if node not null
        STORE   R3,R2,NODE

        LIS     R3,'('          ;   print '('
        ADDI    R2,R2,ARSIZE
        LIL     R1,DSPCH
        JSRS    R1,R1
        ADDI    R2,R2,-ARSIZE

        LOAD    R3,R2,NODE      ;   traverse(node->left)
        LOAD    R3,R3,LEFT
        ADDI    R2,R2,ARSIZE
        JSR     R1,TRAVERSE
        ADDI    R2,R2,-ARSIZE

        LOAD    R3,R2,NODE      ;   print(node->text)
;       ?????(b)?????
        LEA     R3,R3,TEXT	;====(b)==== compute address of text
        ADDI    R2,R2,ARSIZE    ;====(b)====
        LIL     R1,DSPST
        JSRS    R1,R1
;       ?????(b)?????
        ADDI    R2,R2,-ARSIZE   ;====(b)====

        LOAD    R3,R2,NODE      ;   traverse(node->right)
;       ?????(c)?????           ;   something big is missing here
        LOAD    R3,R3,RIGHT     ;====(c)==== (code block cribbed
        ADDI    R2,R2,ARSIZE    ;====(c)====  from block for left subtree)
        JSR     R1,TRAVERSE     ;====(c)====
        ADDI    R2,R2,-ARSIZE   ;====(c)====

;       ?????(d)?????           ;   something else big is missing here
        LIS     R3,')'          ;====(d)==== print ')'
        ADDI    R2,R2,ARSIZE    ;====(d)====
        LIL     R1,DSPCH        ;====(d)==== (code block cribbed 
        JSRS    R1,R1           ;====(d)====  from block for left paren)
        ADDI    R2,R2,-ARSIZE   ;====(d)====

TRAVQT:                         ; endif
;       ?????(e)?????           ; return
        LOADS   R1,R2           ;====(e)====
        JUMPS   R1              ;====(e)====

; the program starts here!
START:  LIL     R2,UNUSED       ; set up the stack
                                ;  --- begin aplication code
        LIL     R1,DSPINI
        JSRS    R1,R1           ; initialize the display

        LIL     R3,ROOT
        JSR     R1,TRAVERSE     ; traverse the tree

                                ;  --- end aplication code
        LIL     R1,EXIT
        JSRS    R1,R1           ; stop!

        END

    The problem: Fix the above code. Several small pieces have been deleted. If you correctly repair the code, it will work as a test program for MP1. Comments in the code indicate each deletion of one or more lines. Parts a, b, c, d and e above are indicated by comments in the code. (0.4 points each, for a total of 2 points)

  2. Background: Chapter 6 discusses numerous approaches to optimization.

    The Problem: Apply all of them that you can to your solution to problem 1. (1 point)

    The solution is given below, cut and pasted from above. comments relating to problem 1 are deleted, comments added indicate changes. 

            TITLE   "mp1test.a, test program for MP1 by Douglas Jones"
        S       START
        USE     "hawk.macs"
        USE     "monitor.h"
        EXT     UNUSED
        EXT     ROOT

; description of the structure of each node:
LEFT    =       0
RIGHT   =       4
TEXT    =       8

; activation record structure for TRAVERSE
NODE    =       4
ARSIZE  =       8

TRAVERSE:
        TESTR   R3
        BZS     TRAVQT          ; if node not null
        STORES  R1,R2                   ; ======= moved
        STORE   R3,R2,NODE

        LIS     R3,'('          ;   print '('
        ADDI    R2,R2,ARSIZE
        LIL     R1,DSPCH
        JSRS    R1,R1
;------ ADDI    R2,R2,-ARSIZE           ; ------- deleted

        LOAD    R3,R2,NODE-ARSIZE       ; ======= changed
        LOAD    R3,R3,LEFT
;------ ADDI    R2,R2,ARSIZE            ; ------- deleted
        JSR     R1,TRAVERSE     ;   traverse(node->left)
;------ ADDI    R2,R2,-ARSIZE           ; ------- deleted

        LOAD    R3,R2,NODE-ARSIZE       ; ======= changed
        LEA     R3,R3,TEXT
;------ ADDI    R2,R2,ARSIZE            ; ------- deleted
        LIL     R1,DSPST
        JSRS    R1,R1           ;   print(node->text)
;------ ADDI    R2,R2,-ARSIZE           ; ------- deleted

        LOAD    R3,R2,NODE-ARSIZE       ; ======= changed
        LOAD    R3,R3,RIGHT
;------ ADDI    R2,R2,ARSIZE            ; ------- deleted
        JSR     R1,TRAVERSE     ;   traverse(node->right)
;------ ADDI    R2,R2,-ARSIZE           ; ------- deleted

        LIS     R3,')'          ;   print ')'
;------ ADDI    R2,R2,ARSIZE            ; ------- deleted
        LIL     R1,DSPCH
        JSRS    R1,R1
        ADDI    R2,R2,-ARSIZE

        LOADS   R1,R2                   ; ======= moved
TRAVQT:                         ; endif
        JUMPS   R1              ; return