This week we continues to explore MIPS.
MIPS does not have while or for loops, so we first translate C to simplified C, and then translate to MIPS. Simplified C does not have while, switch, complex expressions, does have simple if, goto, one-operator expressions, does not have function calls and auto local variables, does have jump-and-remember-where-you-came-from.
C Simplified C MIPS Assembler
------------ ------------ --------------
int x = 5; int x = 5; x: .word 5
int y = 3; int y = 3; y: .word 3
int z; int z; z: .space 4
int t; ...
lw $t0, x
lw $t1, y
z = 5*(x+y); t = x+y; add $t0, $t0, $t1
li $t1, 5
t = 5*t; mul $t0, $t0, $t1
z = t; sw $t0, z
Labels and goto are used to replace loops of C.
Standard C Simplified C (Still valid C)
------------------ ------------------
i = 0; n = 0; i = 0; n = 0;
while (i < 5) { loop:
n = n + i; if (i >= 5) goto end;
i++; n = n + i;
} i++;
goto loop;
end:
Simple example of rendering assignment and sequence
int x; x: .space 4
int y; y: .space 4
x = 2; li $t0, 2
sw $t0, x
y = x; lw $t0, x
sw $t0, y
y = y+3; lw $t0, y
addi $t0, $t0, 3
sw $t0, y
Translate expression evaluation
# x = (1 + y*y) / 2
# assume x and y exist as labels in .data
lw $t0, y # t0 = y
mul $t0, $t0, $t0 # t0 = t0*t0
addi $t0, $t0, 1 # t0 = t0+1
li $t1, 2 # t1 = 2
div $t0, $t1 # Lo = t0/t1 (int div)
mflo $t0 # t0 = Lo
sw $t0, x # x = t0
Translate conditional statements (e.g. if)
Standard C Simplified C
------------------------ ------------------------
if_stat:
if (Cond) t0 = (Cond)
{ Statements1 } if (t0 == 0)
else goto else_part;
{ Statements2 } Statements1
goto end_if;
else_part:
Statements2
end_if:
if_stat:
if (Cond) t0 = evaluate (Cond)
{ Statements1 } beqz $t0, else_part
else execute Statements1
{ Statements2 } j end_if
else_part:
execute Statements2
end_if:
int x; x is $t0
int y; y is $t1
char z; z is $a0
x = getInt(); li $v0, 5
syscall
move $t0, $v0
y = getInt(); li $v0, 5
syscall
move $t1, $v0
if (x == y) bne $t0, $t1, setN
z = 'Y'; setY:
li $a0, 'Y'
j print
else setN:
z = 'N'; li $a0, 'N'
j print # redundant
print:
putChar(z); li $v0, 11
syscall
swtitch can be translated to if
switch (Expr) { tmp = Expr;
case Val1: if (tmp == Val1)
Statements1 ; break; { Statements1; }
case Val2: else if (tmp == Val2
case Val3: || tmp == Val3
case Val4: || tmp == Val4)
Statements2 ; break; { Statements2; }
case Val5: else if (tmp == Val5)
Statements3 ; break; { Statements3; }
default: else
Statements4 ; break; { Statements4; }
}
Alternative implementation of switch (works best for small, dense range of case values)
jump_tab:
.word c1, c2, c2, c2, c3
switch:
t0 = evaluate Expr
switch (Expr) { if (t0 < 1 || t0 > 5)
case 1: jump to default
Statements1 ; break; dest = jump_tab[(t0-1)*4]
case 2: jump to dest
case 3: c1: execute Statements1
case 4: jump to end_switch
Statements2 ; break; c2: execute Statements2
case 5: jump to end_switch
Statements3 ; break; c3: execute Statements3
default: jump to end_switch
Statements4 ; break; default:
} execute Statements4
end_switch:
Translate while
top_while:
while (Cond) { t0 = evaluate Cond
Statements; beqz $t0,end_while
} execute Statements
j top_while
end_while:
for can be translated to while
i = 0
for (i = 0; i < N; i++) { while (i < N) {
Statements; Statements;
} i++;
}
Example of iteration over an array
int sum, i; sum: .word 4 # use reg for i
int a[5] = {1,3,5,7,9}; a: .word 1,3,5,7,9
... ...
sum = 0; li $t0, 0 # i = 0
li $t1, 0 # sum = 0
li $t2, 4 # max index
for (i = 0; i < N; i++) for: bgt $t0, $t2, end_for
move $t3, $t0
mul $t3, $t3, 4
sum += a[i]; add $t1, $t1, a($t3)
printf("%d",sum); addi $t0, $t0, 1 # i++
j for
end_for: sw $t1, sum
move $a0, $t1
li $v0, 1
syscall # printf
When compiling the following C code on https://gcc.godbolt.org to MIPS (gcc 5.4),
int array[10] = {1,0,0,0,0,0,0,0,0,0};
it gives the following output:
array:
.word 1
.word 0
.word 0
.word 0
.word 0
.word 0
.word 0
.word 0
.word 0
.word 0
But in lectures it is written in another way:
array:
.word 1 0 0 0 0 0 0 0 0 0
which all data are combined in one line.
A asked lecturer which one is preferred, lecturer told me that both are valid assembly codes, but the later one is more clear when reading it. It is self evident that word is an array. It is particularly clear when it comes to 2D array, something like this (from assignment):
board:
.byte 1, 0, 0, 0, 0, 0, 0, 0, 0, 0
.byte 1, 1, 0, 0, 0, 0, 0, 0, 0, 0
.byte 0, 0, 0, 1, 0, 0, 0, 0, 0, 0
.byte 0, 0, 1, 0, 1, 0, 0, 0, 0, 0
.byte 0, 0, 0, 0, 1, 0, 0, 0, 0, 0
.byte 0, 0, 0, 0, 1, 1, 1, 0, 0, 0
.byte 0, 0, 0, 1, 0, 0, 1, 0, 0, 0
.byte 0, 0, 1, 0, 0, 0, 0, 0, 0, 0
.byte 0, 0, 1, 0, 0, 0, 0, 0, 0, 0
.byte 0, 0, 1, 0, 0, 0, 0, 0, 0, 0
A 2D board. Much more clear and self-explain.