Assignment 6, due Oct 3

;RETAD  =       0
X       =       4
Y       =       8
V       =       16
ARSIZE  =       20

SUBR:
        STORES  R1,R2
        STORE   R3,R2,X
        STORE   R4,R2,Y

        LOADCC  R0,R2,X
        BZS     SUBELS

        LOAD    R3,R2,Y
        LOAD    R4,R2,X
        ADDSI   R4,-1
        ADDI    R2,R2,ARSIZE
        JSR     R1,SUBR
        ADDI    R2,R2,-ARSIZE
        STORE   R3,R2,V

        LOAD    R3,R2,V
        LOAD    R4,R2,Y
        ADD     R3,R3,R4
        STORE   R3,R2,V

        BR      SUBEND
SUBELS:

        LIS     R3,0
        STORE   R3,R2,V

SUBEND:

        LOAD    R3,R2,V
        LOADS   R1,R2
        JUMPS   R1

Note that this code is "as dumb as cement" with no optimization, a boiler-plate receiving sequence, boiler-plate return sequence, and all variables stored in RAM between what could be high-level-language statements.

Also note that this is just a subroutine. There is no main program. You cannot test it without writing a main program to call it, passing the appropriate parameters wherever this code expects parameters. In the process, you will have to add all the material from the skeleton of a main program, including things like USE "hawk.h" and things like that. Of course, the assignment does not require testing it.

a) Reverse engineer this subroutine and give equivalent high-level language code, for example, as a C or C++ function or a Java or Python method. Use the letters x, y, z and v as parameter and variable names, and to the extent possible, write your code using appropriate high-level control structures. (0.5 points)

Here is a solution, the way you might express it as comments on the original code. That takes up an awful lot of space, but it clearly relates each line of reverse enginered code to the original assembly language.

;RETAD  =       0
X       =       4
Y       =       8
V       =       16
ARSIZE  =       20

SUBR:
        STORES  R1,R2
        STORE   R3,R2,X
        STORE   R4,R2,Y         ; int subr( int x, int y ) {

        LOADCC  R0,R2,X
        BZS     SUBELS          ;    if (x != 0) {

        LOAD    R3,R2,Y         ;       -- parameter 1: y
        LOAD    R4,R2,X      
        ADDSI   R4,-1           ;       -- parameter 2: x
        ADDI    R2,R2,ARSIZE
        JSR     R1,SUBR         ;       v = subr( y, x - 1 )
        ADDI    R2,R2,-ARSIZE
        STORE   R3,R2,V

        LOAD    R3,R2,V
        LOAD    R4,R2,Y
        ADD     R3,R3,R4
        STORE   R3,R2,V         ;       v = v + y

        BR      SUBEND
SUBELS:                         ;    } else {

        LIS     R3,0
        STORE   R3,R2,V         ;       v = 0

SUBEND:                         ;    }

        LOAD    R3,R2,V
        LOADS   R1,R2
        JUMPS   R1              ;    return v
                                ; }

Here is a more compact solution, the kind of thing you might type up down after scribbling something like the above into the margins of the original code. The high level code is easier to read if you get rid of all the white space. This solution is given in the C language, but of course, students are free to use other languages here:

int subr( int x, int y ) {
   if (x != 0) {
      v = subr( y, x - 1 ) + y;
   } else {
      v = 0;
   }
   return v;
}

At this point, the reverse engineering is done, but the code still doesn't explain itself. You can optimize the code without understanding it!

b) Write optimal code for this subroutine. You will find, in doing this, that you can eliminate many load and store instructions and entire fields of the activation record. (Your optimization should not change the algorithm! It should just make the algorithm run as fast as you can.) (1.0 point)

Here is a solution that is better than most students are expected to get, at this point. Comments are fare more important here than above, because there are lots of optimizations that make the code less obvious while it is compacted.

;RETAD  =       0
Y       =       8
ARSIZE  =       4

SUBR:                           ; int subr( x, y )
        STORES  R1,R2
        STORE   R4,R2,Y         ;    -- save y; x remains in R3

        MOVECC  R4,R3           ;    -- move x for recursive call, and test it
        BZS     SUBELS          ;    if (x != 0) {

        ADDSI   R4,-1           ;       -- parameter 2: x - 1
        LOAD    R3,R2,Y         ;       -- parameter 1: y
        ADDSI   R4,-1
	ADDI    R2,R2,ARSIZE
        JSR     R1,SUBR
	ADDI    R2,R2,-ARSIZE
        LOAD    R4,R2,Y
        ADD     R3,R3,R4        ;       v = subr( y, x - 1 )
SUBELS:                         ;    } else {
                                ;       -- here, either R3 = v or R3 = 0
                                ;    }
                                ;    return v -- which is in R3
        LOADS   R1,R2       
        JUMPS   R1              ; }

Students should get most of the credit for many solutions that are less optimal than the above. You can't eliminate the y from the activation record, though, and students who didn't eliminate both x and v from the activation record shouldn't get full credit. The most subtle optimization is to use a MOVECC instruction to both test x and move it to another register.

Another subtle optimization is to note that when control reaches SUBELS from the conditional branch, R3 is already zero, so there is no need for any code in the else clause. Because of that, there is no need for a branch to the endif either.

c) What does it do? If you ignore English grammar, there are some good one and two word answers. (0.5 points)

The call subr(a,b) computes the unsigned integer product of a and b. The shortest reasonable answer to this question is just one word multiply.

The algorithm uses recursion to repeatedly subtract one from one of the multiplicands while adding in a copy of the other multiplicand to the result. Normally, you'd always subtract one from the same multiplicand while you add in the other one repeatedly, but you still get the same result if you switch the multiplicands at any point in this process, or as in this code, you switch the multiplicands after every step.

One way to understand the code is to trace through the two different ways it could run. If you call subr(0,y), it does this:

int subr( int x, int y ) {
   return 0;
}

Otherwise, if x is nonzero, subr(x,y) does this:

int subr( int x, int y ) {
   return subr( y, x - 1 ) + y;
}

That is to say, whether or not the first parameter is zero, any call to subr() always returns so long as the recursive call nested within it returns. The only way this could lead to an infinite recursion is if the first parameter never eventually reaches zero. Since the parameters are exchanged at every recursion, and one of them is always decremented, we know that one or the other parameter must eventually reach zero, so we know that there is no loop.

a) Write a function that a C programmer might call twotothe() that, given a value of i as a parameter, returns 2ⁱ as its value. Use the standard Hawk rules for parameter passing and function return values. You can use iterated multiplication by two to do this. (0.5 points)

Note: The optimal solution uses just 8 halfword instructions, but appropriate comments might expand this to as much as 15 lines of code.

It turns out that the optimal solution was just 7 halfwords long:

TWOTOTHE:       ; expects R3 -- the integer parameter i
                ; returns R3 -- r = 2 to the i th power
                ; uses    R4 -- a working copy of i
        MOVE    R4,R3           ; -- move i out of r

        LIS     R3,1            ; r = 1 -- the result, note twotothe(0) = 1

TWOTOLP:                        ; do {
        ADDSI   R4,-1           ;    i = i - 1
        BNS     TWOTOQT         ;    if (i < 0) break
        SL      R3,1            ;    r = r << 1

        BR      TWOTOLP         ; } until break

	JUMPS	R1              ; return r

Students were, of course, not expected to develop optimal solutions. A correct solution using "dumb as cement" coding rules might be twice as long, with a 12 byte activation record holding two local variables and a return address. It should, however, be at least as easy to read.

b) If each little triangle making up the entire Serpinski triangle is plotted as follows:

__
\/

That is, composed of two underscores atop a V made of a backslash and slash. In what orders can you plot the left, right and bottom triangles in order to guarantee that the horizontal lines plot correctly, avoiding outcomes like this (among others):

________________
\__/\__/\__/\__/
 \____/  \____/
  \__/    \__/
   \________/
    \__/\__/
     \____/
      \__/
       \/

And yes, you really can get this output from your program if you plot the subsidiary triangles in the wrong order. (0.5 points)

Note: There are three subsidiary triangles. Three things can be done in 6 possible orders. Only some of these orders avoid messed up results (and there are several ways to mess things up.

If we call the three subsidiary triangles left, right and bottom, you only get the correct result if you plot the bottom triangle first. So, the correct orders for the recursive calls are either:

• bottom, left, right
• bottom, right, left

As an aside, not part of the required answer: The outcome shown above, just one of the incorrect results, is what you get if you plot the bottom triangle last, in either of these two orders:

• left, right, bottom
• right, left, bottom

The other two possible orders give hybrid results between the correct outcome and the incorrect outcome shown above.