.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(3)
la $t0, ($fp)
li $t1, 0
sw $t1, ($t0)
la $t0, -4($fp)
li $t1, 10
sw $t1, ($t0)
la $t0, -8($fp)
li $t1, 15
sw $t1, ($t0)
la $t0, ($fp)
li $t1, 0
sw $t1, ($t0)
LOOP_CONDITION_00000:
lw $t1, ($fp)
li $t0, 5
sle $t2, $t1, $t0
bne $t2, $zero, LOOP_BODY_00000
j LOOP_EXIT_00000
LOOP_BODY_00000:
LOOP_CONDITION_00001:
lw $t0, -4($fp)
li $t1, 15
sle $t3, $t0, $t1
bne $t3, $zero, LOOP_BODY_00001
j LOOP_EXIT_00001
LOOP_BODY_00001:
j LOOP_BODY_00002
LOOP_CONDITION_00002:
lw $t1, -8($fp)
li $t0, 20
sle $t4, $t1, $t0
bne $t4, $zero, LOOP_BODY_00002
j LOOP_EXIT_00002
LOOP_BODY_00002:
CALLER_FUNCTION_PROLOGUE()
li $t0, 107
sw $t0, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t0, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
li $t0, 58
sw $t0, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t0, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
li $t0, 32
sw $t0, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t0, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
lw $t0, -8($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
la $t0, -8($fp)
lw $t1, ($t0)
add $t5, $t1, $zero
addiu $t1, $t1, 1
sw $t1, ($t0)
j LOOP_CONDITION_00002
LOOP_EXIT_00002:
CALLER_FUNCTION_PROLOGUE()
li $t5, 106
sw $t5, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t5, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
li $t5, 58
sw $t5, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t5, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
li $t5, 32
sw $t5, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t5, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
lw $t5, -4($fp)
sw $t5, ($sp)
sub $sp, $sp, 4
jal print_int
CALLER_FUNCTION_EPILOGUE()
add $t5, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
li $t5, 10
sw $t5, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t5, $v0, $zero
la $t5, -4($fp)
lw $t1, ($t5)
add $t0, $t1, $zero
addiu $t1, $t1, 1
sw $t1, ($t5)
j LOOP_CONDITION_00001
LOOP_EXIT_00001:
CALLER_FUNCTION_PROLOGUE()
li $t0, 105
sw $t0, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t0, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
li $t0, 58
sw $t0, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t0, $v0, $zero
CALLER_FUNCTION_PROLOGUE()
li $t0, 32
sw $t0, ($sp)
sub $sp, $sp, 4
jal print_char
CALLER_FUNCTION_EPILOGUE()
add $t0, $v0, $zero
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
la $t0, ($fp)
lw $t1, ($t0)
add $t5, $t1, $zero
addiu $t1, $t1, 1
sw $t1, ($t0)
j LOOP_CONDITION_00000
LOOP_EXIT_00000:
li $t5, 0
add $v0, $t5, $zero
CALLEE_FUNCTION_EPILOGUE()
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
Triple Nested Loops
Input
int main() {
/**
* The following test is an interesting composition of loops.
* First the _do-while_ runs through all of its iterations.
* Then the _while_ loop runs, but with each of its iterations, a "do" is
* forced, so we see a _do-while_ iteration along with each _while_ iteration.
* Finally, the _for_ is allowed to progress without additional _while_ iterations.
* This is further discussed in the comments on each line
*/
int i = 0;
int j = 10;
int k = 15;
// test for loop
for( i = 0; i <= 5; i ++ ) {
// test while loops
while( j <= 15 ) {
// test do while loops
do{
// expect to see 15-20, then 21-25 interspersed with numbers from js
print_char('k'); print_char(':'); print_char(' '); print_int(k);
print_char('\n');
k++;
} while( k <= 20 );
// expect to see 10-15 interspersed with the numbers from the ks do
print_char('j'); print_char(':'); print_char(' '); print_int(j);
print_char('\n');
j++;
}
// expect to see 0-5
print_char('i'); print_char(':'); print_char(' '); print_int(i);
print_char('\n');
}
return 0;
}
MIPS
Output
k: 15
k: 16
k: 17
k: 18
k: 19
k: 20
j: 10
k: 21
j: 11
k: 22
j: 12
k: 23
j: 13
k: 24
j: 14
k: 25
j: 15
i: 0
i: 1
i: 2
i: 3
i: 4
i: 5
3AC (Three-Address Code)
.data
.text
JAL , main , - , -
BR , PROG_END , - , -
main:
PROCENTRY , 12 , - , -
LA , ireg_00000 , ($FP) , -
LI , ireg_00001 , 0 , -
STORE , ireg_00001 , (ireg_00000) , 4
KICK , ireg_00001 , - , -
KICK , ireg_00000 , - , -
LA , ireg_00002 , -4($FP) , -
LI , ireg_00003 , 10 , -
STORE , ireg_00003 , (ireg_00002) , 4
KICK , ireg_00003 , - , -
KICK , ireg_00002 , - , -
LA , ireg_00004 , -8($FP) , -
LI , ireg_00005 , 15 , -
STORE , ireg_00005 , (ireg_00004) , 4
KICK , ireg_00005 , - , -
KICK , ireg_00004 , - , -
LA , ireg_00006 , ($FP) , -
LI , ireg_00007 , 0 , -
STORE , ireg_00007 , (ireg_00006) , 4
KICK , ireg_00006 , - , -
KICK , ireg_00007 , - , -
LOOP_CONDITION_00000:
LOAD , ireg_00008 , ($FP) , 4
LI , ireg_00009 , 5 , -
LE , ireg_00010 , ireg_00008 , ireg_00009
KICK , ireg_00008 , - , -
KICK , ireg_00009 , - , -
BRNE , LOOP_BODY_00000, ireg_00010 , $ZERO
BR , LOOP_EXIT_00000, - , -
LOOP_BODY_00000:
LOOP_CONDITION_00001:
LOAD , ireg_00011 , -4($FP) , 4
LI , ireg_00012 , 15 , -
LE , ireg_00013 , ireg_00011 , ireg_00012
KICK , ireg_00011 , - , -
KICK , ireg_00012 , - , -
BRNE , LOOP_BODY_00001, ireg_00013 , $ZERO
BR , LOOP_EXIT_00001, - , -
LOOP_BODY_00001:
BR , LOOP_BODY_00002, - , -
LOOP_CONDITION_00002:
LOAD , ireg_00014 , -8($FP) , 4
LI , ireg_00015 , 20 , -
LE , ireg_00016 , ireg_00014 , ireg_00015
KICK , ireg_00014 , - , -
KICK , ireg_00015 , - , -
BRNE , LOOP_BODY_00002, ireg_00016 , $ZERO
BR , LOOP_EXIT_00002, - , -
LOOP_BODY_00002:
CALL_PROC , print_char , 0 , -
LI , ireg_00018 , 107 , -
STORE , ireg_00018 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00018 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00017 , $RV , $ZERO
KICK , ireg_00017 , - , -
CALL_PROC , print_char , 0 , -
LI , ireg_00020 , 58 , -
STORE , ireg_00020 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00020 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00019 , $RV , $ZERO
KICK , ireg_00019 , - , -
CALL_PROC , print_char , 0 , -
LI , ireg_00022 , 32 , -
STORE , ireg_00022 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00022 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00021 , $RV , $ZERO
KICK , ireg_00021 , - , -
CALL_PROC , print_int , 0 , -
LOAD , ireg_00024 , -8($FP) , 4
STORE , ireg_00024 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00024 , - , -
JAL , print_int , - , -
END_PROC , 0 , - , -
ADD , ireg_00023 , $RV , $ZERO
KICK , ireg_00023 , - , -
CALL_PROC , print_char , 0 , -
LI , ireg_00026 , 10 , -
STORE , ireg_00026 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00026 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00025 , $RV , $ZERO
KICK , ireg_00025 , - , -
LA , ireg_00027 , -8($FP) , -
LOAD , ireg_00028 , (ireg_00027) , 4
ADD , ireg_00029 , ireg_00028 , $ZERO
ADDIU , ireg_00028 , ireg_00028 , 1
STORE , ireg_00028 , (ireg_00027) , 4
KICK , ireg_00027 , - , -
KICK , ireg_00028 , - , -
KICK , ireg_00029 , - , -
BR , LOOP_CONDITION_00002, - , -
LOOP_EXIT_00002:
CALL_PROC , print_char , 0 , -
LI , ireg_00031 , 106 , -
STORE , ireg_00031 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00031 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00030 , $RV , $ZERO
KICK , ireg_00030 , - , -
CALL_PROC , print_char , 0 , -
LI , ireg_00033 , 58 , -
STORE , ireg_00033 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00033 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00032 , $RV , $ZERO
KICK , ireg_00032 , - , -
CALL_PROC , print_char , 0 , -
LI , ireg_00035 , 32 , -
STORE , ireg_00035 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00035 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00034 , $RV , $ZERO
KICK , ireg_00034 , - , -
CALL_PROC , print_int , 0 , -
LOAD , ireg_00037 , -4($FP) , 4
STORE , ireg_00037 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00037 , - , -
JAL , print_int , - , -
END_PROC , 0 , - , -
ADD , ireg_00036 , $RV , $ZERO
KICK , ireg_00036 , - , -
CALL_PROC , print_char , 0 , -
LI , ireg_00039 , 10 , -
STORE , ireg_00039 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00039 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00038 , $RV , $ZERO
KICK , ireg_00038 , - , -
LA , ireg_00040 , -4($FP) , -
LOAD , ireg_00041 , (ireg_00040) , 4
ADD , ireg_00042 , ireg_00041 , $ZERO
ADDIU , ireg_00041 , ireg_00041 , 1
STORE , ireg_00041 , (ireg_00040) , 4
KICK , ireg_00040 , - , -
KICK , ireg_00041 , - , -
KICK , ireg_00042 , - , -
BR , LOOP_CONDITION_00001, - , -
LOOP_EXIT_00001:
CALL_PROC , print_char , 0 , -
LI , ireg_00044 , 105 , -
STORE , ireg_00044 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00044 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00043 , $RV , $ZERO
KICK , ireg_00043 , - , -
CALL_PROC , print_char , 0 , -
LI , ireg_00046 , 58 , -
STORE , ireg_00046 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00046 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00045 , $RV , $ZERO
KICK , ireg_00045 , - , -
CALL_PROC , print_char , 0 , -
LI , ireg_00048 , 32 , -
STORE , ireg_00048 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00048 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00047 , $RV , $ZERO
KICK , ireg_00047 , - , -
CALL_PROC , print_int , 0 , -
LOAD , ireg_00050 , ($FP) , 4
STORE , ireg_00050 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00050 , - , -
JAL , print_int , - , -
END_PROC , 0 , - , -
ADD , ireg_00049 , $RV , $ZERO
KICK , ireg_00049 , - , -
CALL_PROC , print_char , 0 , -
LI , ireg_00052 , 10 , -
STORE , ireg_00052 , ($SP) , 4
SUB , $SP , $SP , 4
KICK , ireg_00052 , - , -
JAL , print_char , - , -
END_PROC , 0 , - , -
ADD , ireg_00051 , $RV , $ZERO
KICK , ireg_00051 , - , -
LA , ireg_00053 , ($FP) , -
LOAD , ireg_00054 , (ireg_00053) , 4
ADD , ireg_00055 , ireg_00054 , $ZERO
ADDIU , ireg_00054 , ireg_00054 , 1
STORE , ireg_00054 , (ireg_00053) , 4
KICK , ireg_00053 , - , -
KICK , ireg_00054 , - , -
KICK , ireg_00055 , - , -
BR , LOOP_CONDITION_00000, - , -
LOOP_EXIT_00000:
LI , ireg_00056 , 0 , -
RETURN , ireg_00056 , - , -
ENDPROC , - , - , -
PROG_END: