Assignment 5, due Sep 26

        LIS     R8,1
        LIS     R10,0
L1:
        CMPI    R8,10
        BGT     L3
        LIS     R9,1
L2:
        ADDSI   R10,1
        ADDSI   R9,1
        CMP     R9,R8
        BLE     L2
        ADDSI   R8,1
        BR      L1
L3: 

a) Reverse engineer this code and give equivalent code in a language like C, C++, Java or Python. Use the letters i, j, and k as variable names, and to the extent possible, write your code using for loops, while loops and similar high-level constructs. (1 point)

Here is a first attempt, keeping the original assembly language and adding the high level language as comments.

        LIS     R8,1   ; i = 1
        LIS     R10,0  ; j = 0
L1:                    ; while
        CMPI    R8,10  ;       (i <= 10)
        BGT     L3     ;                      {
        LIS     R9,1   ;    k = 1;
L2:                    ;    do {
        ADDSI   R10,1  ;       j = j + 1;
        ADDSI   R9,1   ;       k = k + 1;
        CMP     R9,R8  ;    } while
        BLE     L2     ;            (k <= i);
        ADDSI   R8,1   ;    i = i + 1;
        BR      L1     ;
L3:                    ; }

We can do better, working from the comments above to a somewhat higher level formulation:

j = 0;
for (i = 0; i <= 10; i = i + 1) {
    k = 1;
    do {
        j = j + 1;
        k = k + 1;
    while (k < i);
}

Reducing the inner while loop to a for loop is not really correct because the for loop (in the vast majority of programming languages) allows for zero iterations like a pre-test while loop. The post-test inner loop guarantees at least one iteration. Proving that there is a pre-test formulation equivalent to the post test formulation is not trivial.

b) What is the final value of the R10 at the time control reaches L3. (0.5 points).

You can solve this by analyzing the high-level language code, by running the high-level-language code, or by running the code under the Hawk emulator. Here is the output of the emulator after running the code:

 HAWK EMULATOR
   /------------------CPU------------------\   /----MEMORY----\
   PC:  00000018                R8: 0000000B   00000C: ADDSI   RA,#1
   PSW: 0000FF01  R1: 00000000  R9: 0000000B   00000E: ADDSI   R9,#1
   NZVC: 0 0 0 1  R2: 00000000  RA: 00000037   000010: SUB     R0,R9,R8
                  R3: 00000000  RB: 00000000   000012: BLE     #00000C
                  R4: 00000000  RC: 00000000   000014: ADDSI   R8,#1
                  R5: 00000000  RD: 00000000   000016: BR      #000004
                  R6: 00000000  RE: 00000000 -*000018: NOP
                  R7: 00000000  RF: 00000000   00001A: NOP

You can see the tail end of the code in the memory display, with the program counter pointing just beyond the final branch instruction. At this point, R10 is 37₁₆ which is 55₁₀.

A question: Why is an ALIGN directive required before ITEM2. (0.5 points)

Suggestion: One way to think about this is to experiment. What happens if you leave the directive out? You can study the assembly listing for mp2data.a with and without alignment. Or, you can try linking it, with and without alignment, with your solution to MP2. The other option is to study what the ALIGN directive does and figure from that what the consequences are.

An answer: The ASCII directive that comes before the ALIGN directive could leave the assembly location counter pointing to any byte within a word. Since the next assembly directive after the ALIGN directive is a W directive that is being used to assemble one-word operands into memory, the ALIGN directive assures that these operands will be stored properly starting at a word boundary in memory.

Discussion: Following the suggestion to experiment. Here is part of the assembly listing with the align directive included:

+00000018: 48  65  6C  6C       13          ASCII   "Hello",0
+0000001C: 6F  00
                                14          ALIGN   4
+00000020: 00000001             15  ITEM2:  W       1,2

Here is the same part with the align directive removed:

+00000018: 48  65  6C  6C       13          ASCII   "Hello",0
+0000001C: 6F  00
+0000001E: 00000001             14  ITEM2:  W       1,2

Notice that, in the original, the words at ITEM2 are assembled starting at address 20_{16, while when the ALIGN directive is excluded, the words are assembled starting at 1E16. That address is not divisible by 4, so using it as a word address won't necessarily get the expected value.}

The ALIGN directive does similar things in SMAL as it does in the assemblers for the Intel x86 architecture and many others. As a result, you can do a web search for information about it and not be seriously mislead. The Wikipedia article on Data Structure Alignment is helpful, giving an extended discussion of alignment.

The ALIGN directive is listed in the index of the SMAL manual, where it is defined as a macro in Section 6.4 of the SMAL manual. The accompanying text explains that the ALIGN directive is used "to achieve halfword and word alignment in SMAL programs." The same macro text given in the manual is also included in the hawk.h file.

Recall that the 32-bit Hawk memory address has 30 bits that specify a word in memory, while the 2 least-significant bits specify the byte within the word. As a result, the memory addresses 0, 1, 2 and 3 all refer to the first word in memory, while the addresses 4, 5, 6 and 7 all refer to the second word. This is discussed in detail in the Hawk Manual in Section 1.2. Memory Resources.

Note that the Hawk monitor contains TIMES and TIMESU subroutines for multiplying signed and unsigned integers.

Note also that Section 14.1 of the Hawk manual gives efficient sequences of instructions for multiplying by small constants. Notably, to multiply the contents of register x by 4, use SL x,2. You do not need to know how this works for this problem, only that it works with no side effects (except on the condition codes).

A Problem: Given that the symbol ARRAY is the constant memory address of an a, an array of 4-byte words in memory, and given that the value i is stored in R8, write a fragment of SMAL Hawk assembly code to load the value of a[i] into R9. (1 point)

Here is a "slow and stupid" but universal solution:

        MOVE    R4,R8           ; parameter 1, i
        LIS     R5,4            ; parameter 2, 4
        LIL     R1,TIMES
        JSRS    R1,R1           ; compute 4 * i
        LIL     R9,ARRAY
        ADD     R9,R3           ; compute ARRAY + 4 * i which is ARRAY[i]
        LOADS   R9,R9           ; get the value of ARRAY[i]

Here is a "pretty smart" moderately efficient solution, the best expected of students at this point:

        MOVE    R3,R8
        SL      R3,2            ; compute 4 * i;
        LIL     R9,ARRAY
        ADD     R9,R3           ; compute ARRAY + 4 * i which is ARRAY[i]
        LOADS   R9,R9           ; get the value of ARRAY[i]

Here are two even better solutions, using tricks that students are unlikely to have found at this point:

        MOVESL  R3,R8,2         ; compute 4 * i;
        LIL     R9,ARRAY
        ADD     R9,R3           ; compute ARRAY + 4 * i which is ARRAY[i]
        LOADS   R9,R9           ; get the value of ARRAY[i]

        MOVE    R9,R8
        LIL     R3,ARRAY
        ADDSL   R9,R3,2         ; compute ARRAY + 4 * i which is ARRAY[i]
        LOADS   R9,R9           ; get the value of ARRAY[i]