.macro SAVE_T_REGISTERS
# brace yourself for a long, unrolled loop...
sw $t0, ($sp)
subiu $sp, $sp, 4
sw $t1, ($sp)
subiu $sp, $sp, 4
sw $t2, ($sp)
subiu $sp, $sp, 4
sw $t3, ($sp)
subiu $sp, $sp, 4
sw $t4, ($sp)
subiu $sp, $sp, 4
sw $t5, ($sp)
subiu $sp, $sp, 4
sw $t6, ($sp)
subiu $sp, $sp, 4
sw $t7, ($sp)
subiu $sp, $sp, 4
sw $t8, ($sp)
subiu $sp, $sp, 4
sw $t9, ($sp)
subiu $sp, $sp, 4
.end_macro
.macro RESTORE_T_REGISTERS
# brace yourself for a long, unrolled loop...
addiu $sp, $sp, 4
lw $t9, ($sp)
addiu $sp, $sp, 4
lw $t8, ($sp)
addiu $sp, $sp, 4
lw $t7, ($sp)
addiu $sp, $sp, 4
lw $t6, ($sp)
addiu $sp, $sp, 4
lw $t5, ($sp)
addiu $sp, $sp, 4
lw $t4, ($sp)
addiu $sp, $sp, 4
lw $t3, ($sp)
addiu $sp, $sp, 4
lw $t2, ($sp)
addiu $sp, $sp, 4
lw $t1, ($sp)
addiu $sp, $sp, 4
lw $t0, ($sp)
.end_macro
.macro SAVE_SPILL_MEM
# brace yourself for a long, unrolled loop...
lw $a3, SPILL_MEMORY
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 4
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 8
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 12
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 16
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 20
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 24
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 28
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 32
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 36
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 40
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 44
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 48
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 52
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 56
sw $a3, ($sp)
subiu $sp, $sp, 4
lw $a3, SPILL_MEMORY + 60
sw $a3, ($sp)
subiu $sp, $sp, 4
.end_macro
.macro RESTORE_SPILL_MEM
# brace yourself for a long, unrolled loop...
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 60
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 56
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 52
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 48
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 44
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 40
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 36
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 32
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 28
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 24
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 20
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 16
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 12
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 8
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY + 4
addiu $sp, $sp, 4
lw $a3, ($sp)
sw $a3, SPILL_MEMORY
.end_macro
.macro CALLEE_FUNCTION_PROLOGUE (%variable_size)
# set $fp to the proper spot by recovering the value from $a0
add $fp, $a0, $zero
# allocate stack space for variables ($sp = $sp - space for variables)
li $a0, 4
mulu $a1, $a0, %variable_size
sub $sp, $sp, $a1
.end_macro
.macro CALLEE_FUNCTION_EPILOGUE
# de-allocate the memory used for local variables and parameters
add $sp, $fp, $zero
# jump back to the caller
jr $ra
.end_macro
.macro CALLER_FUNCTION_PROLOGUE
# caller should save it's own $ra, $fp, and registers
sw $ra, ($sp)
subiu $sp, $sp, 4
sw $fp, ($sp)
subiu $sp, $sp, 4
# caller pushes registers and spill memory onto the stack as well
SAVE_T_REGISTERS()
SAVE_SPILL_MEM()
# save the value of $sp here into $a0 as temporary storage until the arguments are moved
# $fp needs to stay where it's at while the arguments are copied after this macro
add $a0, $sp, $zero
.end_macro
.macro CALLER_FUNCTION_EPILOGUE
# recover the spill memory and the stored registers
RESTORE_SPILL_MEM()
RESTORE_T_REGISTERS()
# recover the caller's $fp and $ra
addiu $sp, $sp, 4
lw $fp, ($sp)
addiu $sp, $sp, 4
lw $ra, ($sp)
.end_macro
.macro __LAND (%lhs, %rhs)
beqz %lhs, __LAND_FALSE
beqz %rhs, __LAND_FALSE
li $a2, 1
j __LAND_END
__LAND_FALSE:
li $a2, 0
__LAND_END:
.end_macro
.macro __LOR (%lhs, %rhs)
beqz %lhs, __LOR_TRUE
beqz %rhs, __LOR_TRUE
li $a2, 0
j __LOR_END
__LOR_TRUE:
li $a2, 1
__LOR_END:
.end_macro
.data
SPILL_MEMORY: .space 64
.text
add $fp, $sp, $zero
add $a0, $fp, $zero
jal main
j PROG_END
main:
CALLEE_FUNCTION_PROLOGUE(2)
la $t0, ($fp)
li $t1, 5
sw $t1, ($t0)
la $t0, -4($fp)
CALLER_FUNCTION_PROLOGUE()
lw $t1, ($fp)
sw $t1, ($sp)
sub $sp, $sp, 4
jal factorial
CALLER_FUNCTION_EPILOGUE()
add $t1, $v0, $zero
sw $t1, ($t0)
CALLER_FUNCTION_PROLOGUE()
lw $t0, ($fp)
sw $t0, ($sp)
sub $sp, $sp, 4
jal print_int
CALLER_FUNCTION_EPILOGUE()
add $t0, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
li $t0, 10
sw $t0, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t0, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
lw $t0, -4($fp)
sw $t0, ($sp)
sub $sp, $sp, 4
jal print_int
CALLER_FUNCTION_EPILOGUE()
add $t0, $v0, $zero
li $t0, 0
add $v0, $t0, $zero
CALLEE_FUNCTION_EPILOGUE()
CALLEE_FUNCTION_EPILOGUE()
factorial:
CALLEE_FUNCTION_PROLOGUE(0)
lw $t0, ($fp)
li $t1, 1
sgt $t2, $t0, $t1
bne $t2, $zero, IF_TRUE_00000
IF_FALSE_00000:
li $t1, 1
add $v0, $t1, $zero
CALLEE_FUNCTION_EPILOGUE()
j ENDIF_00000
IF_TRUE_00000:
lw $t0, ($fp)
CALLER_FUNCTION_PROLOGUE()
lw $t3, ($fp)
li $t4, 1
sub $t5, $t3, $t4
sw $t5, ($sp)
sub $sp, $sp, 4
jal factorial
CALLER_FUNCTION_EPILOGUE()
add $t5, $v0, $zero
mul $t4, $t0, $t5
add $v0, $t4, $zero
CALLEE_FUNCTION_EPILOGUE()
ENDIF_00000:
CALLEE_FUNCTION_EPILOGUE()
print_char:
CALLEE_FUNCTION_PROLOGUE(0)
# load $v0 with the value for the print char syscall
li $v0, 11
# the first (and only) argument is the value to print
lw $a0, ($fp)
syscall
CALLEE_FUNCTION_EPILOGUE()
print_int:
CALLEE_FUNCTION_PROLOGUE(0)
# load $v0 with the value for the print int syscall
li $v0, 1
# the first (and only) argument is the value to print
lw $a0, ($fp)
syscall
CALLEE_FUNCTION_EPILOGUE()
print_string:
CALLEE_FUNCTION_PROLOGUE(0)
# load $v0 with the value for the print string syscall
li $v0, 4
# the first (and only) argument is the base address of the null terminated ascii string
la $a0, ($fp)
syscall
CALLEE_FUNCTION_EPILOGUE()
print_float:
CALLEE_FUNCTION_PROLOGUE(0)
# load $v0 with the value for the print float syscall
li $v0, 2
# the first (and only) argument is the base address of the null terminated ascii string
lwc1 $f12, ($fp)
syscall
CALLEE_FUNCTION_EPILOGUE()
PROG_END:
add $a0, $v0, $zero
li $v0, 17
syscall
Recursive Factorial
Input
int factorial(int x);
int main() {
int x = 5;
int result = factorial(x);
print_int(x); // expect to see 5
print_char('\n');
print_int(result); // expect to see 120
return 0;
}
int factorial(int x) {
if (x > 1) {
return x*factorial(x - 1);
} else {
return 1;
}
}
MIPS
Output
5
120
3AC (Three-Address Code)
.data
.text
JAL , main , - , -
BR , PROG_END , - , -
main:
PROCENTRY , 8 , - , -
LA , ireg_00000 , ($FP) , -
LI , ireg_00001 , 5 , -
STORE , ireg_00001 , (ireg_00000) , 4
KICK , ireg_00001 , - , -
KICK , ireg_00000 , - , -
LA , ireg_00002 , -4($FP) , -
CALL_PROC , factorial , 4 , -
LOAD , ireg_00004 , ($FP) , 4
STORE , ireg_00004 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00004 , - , -
JAL , factorial , - , -
END_PROC , 4 , - , -
ADD , ireg_00003 , $RV , $ZERO
STORE , ireg_00003 , (ireg_00002) , 4
KICK , ireg_00003 , - , -
KICK , ireg_00002 , - , -
CALL_PROC , print_int , 0 , -
LOAD , ireg_00006 , ($FP) , 4
STORE , ireg_00006 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00006 , - , -
JAL , print_int , - , -
END_PROC , 0 , - , -
ADD , ireg_00005 , $RV , $ZERO
KICK , ireg_00005 , - , -
CALL_PROC , print_char , 0 , -
LI , ireg_00008 , 10 , -
STORE , ireg_00008 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00008 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00007 , $RV , $ZERO
KICK , ireg_00007 , - , -
CALL_PROC , print_int , 0 , -
LOAD , ireg_00010 , -4($FP) , 4
STORE , ireg_00010 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00010 , - , -
JAL , print_int , - , -
END_PROC , 0 , - , -
ADD , ireg_00009 , $RV , $ZERO
KICK , ireg_00009 , - , -
LI , ireg_00011 , 0 , -
RETURN , ireg_00011 , - , -
ENDPROC , - , - , -
factorial:
PROCENTRY , 0 , - , -
LOAD , ireg_00012 , ($FP) , 4
LI , ireg_00013 , 1 , -
GT , ireg_00014 , ireg_00012 , ireg_00013
KICK , ireg_00012 , - , -
KICK , ireg_00013 , - , -
BRNE , IF_TRUE_00000 , ireg_00014 , $ZERO
IF_FALSE_00000:
LI , ireg_00015 , 1 , -
RETURN , ireg_00015 , - , -
BR , ENDIF_00000 , - , -
IF_TRUE_00000:
LOAD , ireg_00016 , ($FP) , 4
CALL_PROC , factorial , 4 , -
LOAD , ireg_00018 , ($FP) , 4
LI , ireg_00019 , 1 , -
SUB , ireg_00020 , ireg_00018 , ireg_00019
KICK , ireg_00018 , - , -
KICK , ireg_00019 , - , -
STORE , ireg_00020 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00020 , - , -
JAL , factorial , - , -
END_PROC , 4 , - , -
ADD , ireg_00017 , $RV , $ZERO
MUL , ireg_00021 , ireg_00016 , ireg_00017
KICK , ireg_00016 , - , -
KICK , ireg_00017 , - , -
RETURN , ireg_00021 , - , -
ENDIF_00000:
KICK , ireg_00014 , - , -
ENDPROC , - , - , -
PROG_END: