Assignment 6, Solutions
Part of
the homework for 22C:60 (CS:2630), Fall 2011
|
; subroutine to add two numbers
ADDTWO: ; conforms to standard Hawk calling conventions
; given R3 = a, an unsigned integer
; given R4 = b, an unsighed integer
; returns R3 = a + b
ADD R3,R3,R4
JUMPS R1
A problem: Modify the above code so that it prints out its operands and their sum. For example, if the subroutine was called with the parameters 3 and 4, the output would be: 3+4=7. This should cause no observable change in the behavior of ADDTWO from the perspective of programs that call it. (1.0 points).
Note: To solve this problem within the standard Hawk calling conventions, you will be forced to create and use an activation record for ADDTWO. No main program should be turned in, but you are welcome to write one to test your code.
Here is a solution that was coded with no optimization, just brute-force cookbook-style programming.
; subroutine to add two numbers ; activation record format ;RETAD = 0 A = 4 B = 8 ARSIZE = 12 ADDTWO: ; conforms to standard Hawk calling conventions ; given R3 = a, an unsigned integer ; given R4 = b, an unsighed integer ; returns R3 = a + b STORES R1,R2 ; save retad STORE R3,R2,A STORE R4,R2,B ; save the params LOAD R3,R2,A ; -- param LIS R4,1 ; -- param ADDI R2,R2,ARSIZE LIL R1,PUTDECU JSRS R1,R1 ; putdecu(a,1) ADDI R2,R2,-ARSIZE LIS R3,'+' ; -- param ADDI R2,R2,ARSIZE LIL R1,PUTCHAR JSRS R1,R1 ; putchar('+') ADDI R2,R2,-ARSIZE LOAD R3,R2,B ; -- param LIS R4,1 ; -- param ADDI R2,R2,ARSIZE LIL R1,PUTDECU JSRS R1,R1 ; putdecu(b,1) ADDI R2,R2,-ARSIZE LIS R3,'=' ; -- param ADDI R2,R2,ARSIZE LIL R1,PUTCHAR JSRS R1,R1 ; putchar('=') ADDI R2,R2,-ARSIZE LOAD R3,R2,A LOAD R4,R2,B ADD R3,R3,R4 STORE R3,R2,A ; a = a + b LOAD R3,R2,A ; -- param LIS R4,1 ; -- param ADDI R2,R2,ARSIZE LIL R1,PUTDECU JSRS R1,R1 ; putdecu(a) ADDI R2,R2,-ARSIZE LOAD R3,R2,A LOADS R1,R2 ; restore retad JUMPS R1 ; return(a)Here is what happens when you optimize:
; subroutine to add two numbers ; activation record format ;RETAD = 0 A = 4 B = 8 ARSIZE = 12 ADDTWO: ; conforms to standard Hawk calling conventions ; given R3 = a, an unsigned integer ; given R4 = b, an unsighed integer ; returns R3 = a + b STORES R1,R2 ; save retad STORE R3,R2,A STORE R4,R2,B ; save the params LIS R4,1 ; -- param (R3 already set) ADDI R2,R2,ARSIZE LIL R1,PUTDECU JSRS R1,R1 ; putdecu(a,1) LIS R3,'+' ; -- param LIL R1,PUTCHAR JSRS R1,R1 ; putchar('+') LOAD R3,R2,B-ARSIZE ; -- param LIS R4,1 ; -- param LIL R1,PUTDECU JSRS R1,R1 ; putdecu(b,1) LIS R3,'=' ; -- param LIL R1,PUTCHAR JSRS R1,R1 ; putchar('=') LOAD R3,R2,A-ARSIZE LOAD R4,R2,B-ARSIZE ADD R3,R3,R4 STORE R3,R2,A-ARSIZE ; a = a + b LIS R4,1 ; -- param (R3 already set) LIL R1,PUTDECU JSRS R1,R1 ; putdecu(a) ADDI R2,R2,-ARSIZE LOAD R3,R2,A LOADS R1,R2 ; restore retad JUMPS R1 ; return(a)
unsigned int times( unsigned int a, unsigned int b) {
/* return the product of two numbers, a and b */
unsigned int p;
if (a == 0) {
p = 0;
} else {
p = times( b, a - 1 );
p = p + b;
}
return p;
}
a) The correctness of this code is not trivial. Consider the call times(5,0). Why does the code work without a check for the second parameter equal to zero? (0.5 points)
times(5,0) becomes
times(0,4)+0 which terminates the recursion.times(5,2) becomes
times(2,4)+2 becomes
times(4,1)+4+2 becomes
times(1,3)+1+4+2 becomes
times(3,0)+3+1+4+2 becomes
times(0,2)+0+3+1+4+2 which terminates the recursion.Because the parameters are switched with each recursive call, it is possible to test just one of them for zero.
b) Write SMAL Hawk assembly code that exactly preserves the logic of the above multiplication routine. (1.5 points)
Note: Again, no main program should be turned in, but you are welcome to write one to test your code.
Here is a version that is pure cookbook programming with no optimization:
; times routine ; activation record ;RETAD = 0 A = 4 B = 8 P = 12 ARSIZE = 16 TIMES: ; expects R3 = a, R4 = b, unsigned integers ; returns R3 = a * b; STORES R1,R2 STORE R3,R2,A STORE R4,R2,B ; save parameters LOAD R3,R2,A TESTR R3 BZR TIMELS ; if (a == 0) { LIS R3,0 STORE R3,R2,P ; p = 0 BR TIMEIF TIMELS: ; } else { LOAD R3,R2,B LOAD R4,R2,A ADDI R4,R4,-1 ADDI R2,R2,ARSIZE JSR R1,TIMES ADDI R2,R2,-ARSIZE STORE R3,R2,P ; p = times( b, a - 1 ) LOAD R3,R2,P LOAD R4,R2,B ADD R3,R3,R4 STORE R3,R2,P ; p = p + b TIMEIF: ; } LOAD R3,R2,P LOADS R1,R2 JUMPS R1 ; return p;Here is optimized code that still preserves the essential structure of the recursion:
; times routine ; activation record ;RETAD = 0 A = 4 ARSIZE = 8 TIMES: ; expects R3 = a, R4 = b, unsigned integers ; returns R3 = a * b; STORES R1,R2 STORE R4,R2,B ; save parameters TESTR R3 ; -- note a is already in R3 BZS TIMEIF ; if (a == 0) { ; p = 0 -- now, p is in R3 ; } else { MOVE R4,R3 ; -- note, a was already in R3 LOAD R3,R2,B ; -- parameter ADDI R4,R4,-1 ADDI R2,R2,ARSIZE JSR R1,TIMES ADDI R2,R2,-ARSIZE ; p = times( b, a - 1 ) LOAD R4,R2,B ADD R3,R3,R4 ; p = p + b TIMEIF: ; } LOADS R1,R2 JUMPS R1 ; return p -- which is already in R3