Assignment 5, Solutions

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

Background: Consider this loop:

        i = 0;
        while (i < 10) {
                -- code in the loop body --
                i = i + 1;
        }

Assume that register 3 is used for the variable i. Note that the Hawk branch instructions only have an 8-bit displacement field, so they can only change the program counter within plus or minus about 128 halfwords.

a) Give equivalent SMAL/Hawk assembly code, written under the assumption that the unknown code in the loop body takes under 100 machine instructions. (1 point)

        LIS     R3,0            ; i = 0
LOOP:   CMPI    R3,10           ; while (i < 10) {
        BGE     LOOPX

        ------ body of small loop goes here ------

        ADDSI   R3,1            ;    i = i + 1
        BR      LOOP            ; }
LOOPX:

b) Give equivalent SMAL/Hawk assembly code, written under the assumption that the unknown code in the loop body takes over 200 machine instructions. (0.5 point)

        LIS     R3,0            ; i = 0
LOOP:   CMPI    R3,10           ; while (i < 10) {
        BLT     LOOPBOD         ;     -- different from part a
        JUMP    LOOPX           ;     -- different from part a
LOOPBOD:                        ;     -- different from part a
        ------ body of big loop goes here ------

        ADDSI   R3,1            ;    i = i + 1
        JUMP    LOOP            ; }   -- different from part a
LOOPX:

Background: Suppose you have a linked list, where each item in the list consists of just one word, the pointer to the next record in the list. To measure the length of this list in C or C++, you might write code like this, assuming that the variable p is a pointer to the first item word in the list:

        i = 0;
        while (p != null) {
                i = i + 1;
                p = p->next;
        }

In the following, assume that the variable p is register 3 and that the variable i is register 4. Assume that all items in the list are properly word-aligned in memory.

a) Give equivalent SMAL/Hawk assembly code. (.5 point)

        LIS     R4,0            ; i = 0;
LOOP:
        TESTR   R3		; while ( p != null) {
        BZS     LOOPX
        ADDSI   R4,1            ;    i = i + 1
        LOADS   R3,R3           ;    p = p->next
        BR      LOOP            ; }
LOOPX:

b) Give equivalent SMAL/Hawk assembly code assuming that each item in the list is 2 words long, where the second word in each item is the pointer to the next item in the list. (.5 point)

        LIS     R4,0            ; i = 0;
LOOP:
        TESTR   R3		; while ( p != null) {
        BZS     LOOPX
        ADDSI   R4,1            ;    i = i + 1
        LOAD    R3,R3,4         ;    p = p->next -- different!
        BR      LOOP            ; }
LOOPX:

The above is probably the best solution, but here is another that works and may be easier to understand:

        LIS     R4,0            ; i = 0;
LOOP:
        TESTR   R3		; while ( p != null) {
        BZS     LOOPX
        ADDSI   R4,1            ;    i = i + 1
        ADDSI   R3,4            ;                -- added
        LOADS   R3,R3           ;    p = p->next -- reverted
        BR      LOOP            ; }
LOOPX:

c) Where the original loop body said i=i+1 change it to i=i+p->value, so that the loop adds up the values of all the items in the list. Each item is 2 words long, as in part b), where the first word of the item is its value and the second word of each item is the pointer to the next item. You will probably need to use a third register to solve this; use register 5. (.5 point)

        LIS     R4,0            ; i = 0;
LOOP:
        TESTR   R3		; while ( p != null) {
        BZS     LOOPX
        LOADS   R5,R3           ;                     -- added
        ADD     R4,R4,R5        ;    i = i + p->value -- changed
        LOAD    R3,R3,4         ;    p = p->next      -- same as part b
        BR      LOOP            ; }
LOOPX: