Problems and Solutions for the MIPS Handout
Notes: 1. These
problems are similar (but not the same) as the problems that we did in section.
2. It is very likely that there are errors in my
solutions. If you think that you have spotted one (or something that I did
confused you), then please email me.
1.
[Easier] Translate the following C
into MIPS:
a. s0++;
addi $s0 $s0 0
b. s1 =
*s0++; (for ints)
lw $s1 0
($s0)
addi $s0 $s0 4
c. s1 =
(s1 – 7) + (3 + s2);
addi $t1 $s1 -7
addi $t2 $s2 3
addi $s1 $t1 $t2
d.
s1[2] = s2[1] + s3[2]; (for ints)
lw $t0 4 ($s2)
lw $t1 8 ($s3)
add $t2 $t0 $t1
sw $t2 8 ($s1)
2.
[Harder] Translate this into MIPS:
a. if
(s0 == 3) then s1 = 7
else if (s0 < 3) then s1
= 9;
else if (s0 > 3) then s1
= 2;
Start: addi $t0 $0 3 #load constant 3
bne $s0 $t0 L1 #if
s0 != 3, goto L1
addi $s1 $0 7 #
s1 = 7
j done
L1: slti $t0 $s0 3 #
bne $t0 $0 L2 #if
$s0 !< 3, goto L2
addi $s1 $0 9 #
s1 = 9
j done
L2: #
no test necessary. $s0 > 3
# must be true at this point
addi $s1 $0 2 #
s1 = 2
Done:
b. for
(I = 0; I < 10, I++) { /* for ints!
*/
s1[I] = s2[I] + s3[I];
}
addi $t0 $0 0 #
I = 0
Loop: slti $t1 $t0 10 # keep looping as long as I < 10
beq $t1 $0 done #
add $t2 $t0 $t0 # i * 2
add $t2 $t2 $t2 # i * 4
lw $t3 0 ( $s2 ) # s2[ I ]
lw $t4 0
( $s3 ) # s3[ I ]
add $t5 $t3 $t4
sw $t5 0 ( $s1 ) # s1 [ I ]
j Loop #
always jump to top
done:
c.
do {
/* for s0 and s1[] as chars!!! */
if ( s0
< s1[i] ) {
goto
done;
}
s0--;
i++;
} while (i < 10);
Start: addi $t1 $t0 $s1 # Not x4 because characters!!!
lw $t2 0
($t1)
slt $t3 $s0 $t2 #
s0 < s1[ i]
bne $t3 $0 done
addi $s0 $s0 -1 #
s0--;
addi $t0 $t0 1
slti $t4 $t0 10 #
i < 10
bne $t4 $0 Start
done
3. [Real Hard] Recall the MIPS implementation of C
switch statements given in lecture. That implementation, which used nested ifs,
had a approximate running time O( n ) in the number of cases. For large n, this
is too slow. In this problem, you will design a MIPS implementation of switch
that runs in constant time.
In this problem, you can assume that the switch
statement will be run multiple times. I.e., you can have sections of MIPS code
that are run only once at the beginning of the first switch (This would be a
good place to do memory stores, etc.) and also sections that are run every time
that the switch is run.
You will need these two new
MIPS instructions:
la $reg LABEL : Will load the address of LABEL into $reg.
jr $reg :
Will jump to the address in $reg.
(e.g. with these new instructions, you could do a
jump (j instruction) to label FOO by executing:
la $t0 FOO
jr $t0 )
You can also assume that register $s1 points to a
large, open memory space that you can freely use. (Perhaps for a jump table?)
a. Switch
(s2) {
Case 1:
foo(s2); break;
Case 2:
bar(s2); break;
Case 4:
s2++; break;
Default:
baz(s2); /* Default is executed
whenever none
of the other cases match */
}
# run once at the beginning
of the program
# later, we’ll learn how to set up static tables like this in mips
la $t0 case1 # load the address of the label
of case1
sw $t0 4 ( $s1 ) #
to 1 * 4 off of $s1
la $t0 case2 # load the address of the label
of case2
sw $t0 8 ( $s1 ) #
to 2 * 4 off of $s1
la $t0 default # load the address of the label of
default
sw $t0 12 ( $s1 ) #
to 3 * 4 off of $s1
la $t0 case4 # load the address of the label
of case3
sw $t0 16 ( $s1 ) #
to 4 * 4 off of $s1
# now, this is run every
time that we call switch
switch: slti $t0 $s2 1
bne $t0 $0 default #jump
to default if s2 < 1
slti $t0 $s2 5
beq $t0 $0 default #jump
to default if s2 > 4
addi $t1 $s2 $s2 #
$s2 * 2
addi $t1 $t1 $t1 #
$s2 * 4
addi $t2 $s1 $t1 #
= $s1 + 4 (s2)
lw $t3 0 ($t2) # lookup in jump table from above
j $t3 #
$t3 has address of proper case
case1: addi $a0 $s2 0 # this is case one; set arg0 = s2
jal foo #
call foo
j done
case2: addi $a0 $s2 0 # this is case two; set arg0 = s2
jal bar #
call bar
j done
case4: addi $s2 $s2 1 # this is case four; s2++;
j done
default: addi $a0 $s2 0 # this is case one; set arg0 = s2
jal baz #
call baz
j done
done: