MIPS assembly language problems

Question 1 (Retake Exam Spring 2016) Programming in MIPS assembly language

Write the utility function Avg_of_Avgs in MIPS assembly language which takes 6 input values
(3 in $a0, $a1 and $a2, and 3 on the stack), and returns one single-precision floating point
output value in $fv0. $a0, $a1 and $a2 each contain the starting address in main memory of an
array (A, B, and C, respectively), where each item in the arrays is an 32-bit floating point
number in IEEE 754 format. The 3 top locations on the stack (TOS, TOS-1 and TOS-2) contain
the values lengthA, lengthB and lengthC, which are the numbers of values in each array.

Your Avg_of_Avgs routine will find the average of averages, and should return that value in
$fv0. It will randomly select two of the arrays (either A & B, A & C, or B & C), find the average
of the floating point numbers in each of the 2 chosen arrays, and then take the average of these
averages. It should make use of calls to Choose1 and to FPAvg, both of which are library
functions that are written, debugged and available to you.

int Choose1 (int x, y, z) is the C header for a routine that takes 3 integers as inputs, randomly
chooses one of them, and returns that value. How it is implemented is unknown to you, but you
know that it obeys the MIPS convention for the use of registers.

float FPAvg (float &Array, int length) is the C header for a routine that takes as 1 input an
address of an array of floating point values, and takes as the other input the length of the array. It
calculates the average of all the values in the array, and returns this floating point average as its
return value. Again, you do not know how it is implemented, but you know that it obeys the
MIPS convention for the use of registers.

To convert an integer into a floating point number, you may use the following sequence
mtc1 $a0, $ft0 # move the integer into a floating point register
cvt.s.w $fv0, $ft0 # convert it into a single-precision FP value

--Your Avg_of_Avgs should obey the MIPS convention for the use of registers, just as the calling
program, Choose1 and FPAvg will obey it.
--Your code for Avg_of_Avgs may use pseudo-instructions, but you may not use psuedo-syntax.
--Code performance is important, but correctness is more important!
--Explain your code with comments and a header.

Use the outline of the code below, to help guide you as you write the MIPS.

# push the needed registers onto stack, before changing them

Avg_of_Avgs: addi $sp, $sp, -20
swc1 $fs0, 16($sp) # push $fs0, to store single-precision values
sw $s2, 12($sp) # $s2 will store the address of C passed in $a2
sw $s1, 8($sp) # $s1 will store the address of B passed in $a1
sw $s0, 4($sp) # $s0 will store the address of A passed in $a0
1
 sw $ra, 0($sp) # save $ra since Avg_of_Avgs is non-leaf

# initialization of registers
move $s0, $a0 # put address of A in $s0
move $s1, $a1 # put address of B in $s1
move $s2, $a2 # put address of C in $s2

# choose 2 arrays, and eliminate 1, branching to the correct pair

jal Choose1 # the v0 return value is the eliminated one
beq $v0, $s0, notA # if v0==address of A, process B and C in notA
beq $v0, $s1, notB # if v0==address of B, process A and C in notB
# else v0==addr of C, so process A & B in notC

# find the average of values in A and average of values in B

notC: move $a0, $s0 # move address of A into a0
lw $a1, 20 ($sp) # load the lengthA value from stack
# $sp+20 is the location of original TOS
jal FPAvg # obtain the FP average of the values in A
move $fs0, $fv0 # move the result into $fs0 to save it
move $a0, $s1 # move address of B into a0
lw $a1, 24 ($sp) # load the lengthB value from stack
# $sp+24 is the location of original TOS-1
jal FPAvg # obtain the FP average of the values in B
j findAvg

# find the average of values in A and average of values in C

notB: move $a0, $s0 # move address of A into a0
lw $a1, 20 ($sp) # load the lengthA value from stack
jal FPAvg # obtain the FP average of the values in A
move $fs0, $fv0 # move the result into $fs0 to save it
move $a0, $s2 # move address of C into a0
lw $a1, 28 ($sp) # load the lengthC value from stack
# $sp+28 is the location of original TOS-2
jal FPAvg # obtain the FP average of the values in C
j findAvg

# find the average of values in B and average of values in C

notA: move $a0, $s1 # move address of B into a0
lw $a1, 24 ($sp) # load the lengthB value from stack
jal FPAvg # obtain the FP average of the values in B
move $fs0, $fv0 # move the result into $fs0 to save it
move $a0, $s2 # move address of C into a0
lw $a1, 28 ($sp) # load the lengthC value from stack
jal FPAvg # obtain the FP average of the values in C

2
 # find the average of the 2 averages
findAvg: add.s $fs0, $fs0, $fv0 # add the two average values together
addi $t0, $0, 2 # put 2 into $t0
mtc1 $t0, $ft0 # move the 2 into $ft0
cvt.s.w $fv0, $ft0 # convert it into a single-precision FP value
div.s $fv0, $fs0, $fv0 # divide the sum of averages by 2; put result in $fv0

# pop the stack values to restore the registers

lwc1 $fs0, 16($sp)
lw $s2, 12($sp)
lw $s1, 8($sp)
lw $s0, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 20

# return to caller
jr $ra

Question 1 (MT #2 Spring 2016) Fixing MIPS Programs

In the following MIPS code, there may be inefficiencies that cause it to execute slowly,
violations of the MIPS convention for register usage, and errors that will cause it execute
incorrectly. Find and fix all such problems in the space next to the given code. Use only real
MIPS instructions.
Q1: addi $sp, $sp, -12
sw $t0, -8 ($sp) // no need to push a t-register; must be +8
sw $s0, -4 ($sp) // don’t use $s0--this push can be skipped; +4
sw $s1, 0 ($sp) // useless push, since $s1 is not used

Top: addi $s0, $a0, 0 // useless transfer, just use $a0! (But if done, do
// it before the loop, since it initializes $s0)
mul $t0, $s0, $a1
add $v0, $v0, $t0 // $v0 is used here with first initializing it
subi $s0, $s0, 1 // no such instruction “subi”; just use $s0
bne $s0, $0, Top // just use $a0

lw $t0, -8 ($sp) // useless pop; must be +8

lw $s0, -4 ($sp) // pop can be avoided by not using $s0; +4
lw $s1, 0 ($sp) // useless pop
addi $sp, $sp, 12 // also useless
jr $ra

Solution Q1: addi $v0, $0, 0 // initialize $v0

3
 Top: mul $t0, $a0, $a1
add $v0, $v0, $t0
addi $a0, $a0, -1
bne $a0, $0, Top

jr $ra

Question 2 (MT #1 Spring 2016) MIPS Programming for Floating Point Average

Write the utility function FPaverage in MIPS assembly language which takes 2 input values in
$a0 and $a1, gets n integer inputs from main memory, and returns one double-precision floating
point output value in $fv0.

$a0 contains the starting address in main memory of an array, where each item in the array is an
integer. $a1 contains the value n, which is the number of integers in the array.

Your FPaverage routine will obtain n double-precision floating point numbers with the help of
intToFP, and use those floating point values in making its calculation. FPaverage should return
in $fv0 the average of the n floating point numbers.

intToFP takes 1 input argument: it receives an integer in $a0. It converts that integer into its
floating point representation, and returns the double-precision floating point result in $fv0.
Assume intToFP is already written, debugged, and available to you as a library function.

intToFP: mtc1 $a0, $ft0 # move the integer into a floating point register
cvt.d.w $fv0, $ft0 # convert it into a double-precision FP value
jr $ra # return to caller, with the result in $fv0

--Your FPaverage should obey the MIPS convention for the use of registers, just as the calling
program and intToFP will obey it.
--Your code for FPaverage may use pseudo-instructions, but you may not use psuedo-syntax.
--Code performance is important, but correctness is more important!
--Explain your code with comments and a header.

FPaverage: # push the needed registers onto stack, before changing them
addi $sp, $sp, -24
sdc1 $fs0, 16($sp) # push $fs0, to store double-precision Sum
sw $s2, 12($sp) # $s2 will store pointer to memory array
sw $s1, 8($sp) # $s1 will store n
sw $s0, 4($sp) # $s0 will store count
sw $ra, 0($sp) # save $ra since FPaverage is non-leaf

# initialization of registers
mtc1 $0, $fs0 # move 0 into a floating point register

4
 cvt.d.w $fs0, $fs0 # convert 0 into a double-precision FP Sum
addi $s0, $0, 0 # count = 0
move $s1, $a1 # n is now stored in $s1
move $s2, $a0 # memory array pointer is stored in $s1

# Loop to repeatedly get an integer from the array in memory,

# call intToFP to convert it, and add it into the running Sum

Top: lw $a0, 0($s2) # get next integer value from array in memory
jal intToFP # call intToFP to convert it to floating point
add.d $fs0, $fs0, $fv0 # add new FP value into Sum
addi $s0, $s0, 1 # increment count
addi $s2, $s2, 4 # increment pointer to next integer’s address
bne $s0, $s1, Top # until count = n, keep iterating the loop

# calculate the FP average

move $a0, $s1 # move n into a0
jal intToFP # convert n into a double-precision FP
div.d $fv0, $fs0, $fv0 # divide Sum by n to get the average

# pop the stack values to restore the registers

ldc1 $fs0, 16($sp)
lw $s2, 12($sp)
lw $s1, 8($sp)
lw $s0, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 24

# return to caller
jr $ra

Note that the code can be speeded up by avoiding the call to intToFP in “calculate the FP
average”. It is faster to do it directly:
mtc1 $s1, $fv0 # move n into a floating point register
cvt.d.w $fv0, $fv0 # convert n into a double-precision FP
This way uses only 2 instructions, instead of 5 (mov, jal, and the 3 in the intToFP routine)

Another way to improve performance is to eliminate the loop counter, by pre-calculating the
final address of the array (Max), and making the loop test compare the pointer to that Max+4 .
The improved loop is now:
Top: lw $a0, 0($s2) # get next integer value from array in memory
jal intToFP # call intToFP to convert it to floating point
add.d $fs0, $fs0, $fv0 # add new FP value into Sum
addi $s2, $s2, 4 # increment pointer to next integer’s address
bne $s2, $s0, Top # until pointer = Max+4, keep iterating the loop

5
This way the loop only contains 5 instructions (but one of them is a call to intToFP). It looks like
1 instruction, but actually 4 are performed, so the total is 8 per loop iteration.

The ultimate speedup would be to eliminate the call to intToFP inside the loop by “in-lining” the
function. In-lining brings the body of the function to the location of the call, eliminating the jal
and the jr instructions (and possibly other instructions also). The resulting loop is like this:
Top: lw $a0, 0($s2) # get next integer value from array in memory
mtc1 $a0, $fv0 # move $a0 into a floating point register
cvt.d.w $fv0, $fv0 # convert n into a double-precision FP
add.d $fs0, $fs0, $fv0 # add new FP value into Sum
addi $s2, $s2, 4 # increment pointer to next integer’s address
bne $s2, $s0, Top # until pointer = Max+4, keep iterating the loop
With this “in-lining”, the number of instructions per loop iteration is now 6. However the
problems specification required the n calls to intToFP, so even though it is faster, this was not
allowed in this question.

Question 3 (Quiz #2 Sec2/3 Spring 2016)

Write a utility function copy in MIPS assembly language that copies an ASCII string from one
memory location into another. It receives the address of the starting location of the string in $a0,
and the address of the location to copy it to in $a1. There is no return value from the copy
function.

copy: lbu $t0, 0($a0) // get byte from string in 1st memory location
sb $t0, 0($a1) // put copy of byte into 2nd memory location
addi $a0, $a0, 1 // move address pointer to next byte in 1st location
addi $a1, $a1, 1 // move address pointer to next byte in 2nd location
bne $t0, $zero, copy // if byte != Null, go get next byte
jr $ra // return to point of call when done

Question 4 (Quiz #2 Sec2/3 Spring 2016)

Write a main program in MIPS assembly language that will copy the ASCII string “Hello Will!”
from the static (a.k.a. global) data segment into the heap part of the dynamic data segment. Your
program should obtain space in heap, call copy to perform the actual string copy, and then end
cleanly by exiting to the operating system. Assume that the label for the “Hello Will!” string’s
location in static (a.k.a. global) memory is Greeting:

main: li $v0, 9 // syscall #9 for sbrk , to get space in heap

li $a0, 12 // 12 bytes needed for the string “Hello Will!” + Null
syscall // the starting address of the heap space will be in $v0

la $a0, Greeting // put address of static memory string into $a0

6
 move $a1, $v0 //put address of dynamic memory string into $a1
jal copy // call copy to do the string copy

li $v0, 10 // syscall #10 for exit

syscall // end of the program—bye bye!

Question 2 (Quiz #1 Sec1 Spring 2016)

For the following MIPS code sequence and given that $a0 = 1 initially, show the contents of the
program counter (PC), register $ra, and the memory stack after the execution of each of the
instructions marked below. Point 1 is given for you. You may use the given labels to indicate the
program execution point.

Question 3 (Quiz #1 Sec3 Spring 2016)

Write a short MIPS assembly language program which implements the C code shown below:

7
 void switchplus5 (int z[ ], int i, int j) {
int temp
plus5 (&z[i]);
temp = z[i];
z[i] = z[j];
z[j] = temp;
}

Your assembly language routine switchplus5 should be a callable function, which has an entry
label “switchplus5:”, and which returns to the place from which it was called at the end of
execution. It is both callee and caller. You may assume that the address of z[0] is passed in $a0,
and the value of i is passed in $a1 and the value of j is passed in $a2. Your code should obey the
software convention for the use of MIPS registers.

[You don't have to write plus5, just assume it exists, and call it. The routine plus5 takes the
address of item z[i], finds the value of that element, and adds 5 to it. It works correctly when
called with the parameter which is the address of z[i]. You can safely assume that plus5 obeys
that software convention also.]

Solution:
switchplus5: addi $sp, $sp, -12 # make room for 3 new items on stack
sw $ra, 0($sp) # push $ra
sw $s0, 4($sp) # push $s0
sw $s1, 8($sp) # push $s1

sll $t0, $a1, 2 # ix4

add $s0, $a0, $t0 # address of z[i] in saved register s0
sll $t0, $s1, 2 # jx4
add $s1, $a0, $t0 # address of z[j] in saved register s1

move $a0, $s0 # set argument for plus5

jal plus5 # invoke the plus5 routine

lw $t0, 0($s0) # load v[i] into temp reg

lw $t1, 0($s1) # load v[j] into temp reg
sw $t1, 0($s0) # store v[j] value into v[i]
sw $t0, 0($s1) # store v[i] value into v[j]

lw $ra, 0($sp) # pop $ra

lw $s0, 4($sp) # pop $s0
lw $s1, 8($sp) # pop $s1
addi $sp, $sp, 12 # restore the $sp to its old value
jr $ra

8
Question 1 (Quiz #1 Sec2 Spring 2016)

Correct the errors in the MIPS code given below. For each error, identify if it is a syntax
error, or a semantic error, or an inefficiency error.

addi $sp, $sp, 4

lw $s0, 0($sp)
addi $t2, 8
divi $t0, $t1, 5
add $t2, $t0, 4($a0)
subi $t2, $t2, 10
move $v0, $t2
sw $s0, 0($sp)
addi $sp, $sp, -4
jr $v0

addi $sp, $sp, 4 addi $sp, $sp, -4 Semantic error

lw $s0, 0($sp) sw $s0, 0($sp) Semantic error
addi $t2, 8 addi $t2, $t2, 8 Syntax error
divi $t0, $t1, 5 div $t0, $t1, 5 Syntax error (could also
be divu)
add $t2, $t0, 4($a0) lw $t2, 4($a0) Syntax error (needs lw,
add $t2, $t0,$t2 then add)
subi $t2, $t2, 10 addi $v0, $t2, -10 Syntax error
move $v0, $t2 See previous instr. Inefficiency error
sw $s0, 0($sp) lw $s0, 0($sp) Semantic error
addi $sp, $sp, -4 addi $sp, $sp, 4 Semantic error
jr $v0 jr $ra Semantic error

Note that push $s0 (addi + sw) and pop $s0 (lw + addi) are not
necessary, since $s0 isn’t used. Thus, the 1st two lines and last 2 lines
before jr $v0 are inefficiency errors as well as semantic.

Question 2 (Quiz #1 Sec2 Spring 2016)

In the code below, identify each pseudo instruction, and change it into one or more actual
MIPS instructions, writing the actual MIPS code to the right of the pseudo instruction.

mul $v0,$t0, $t1

mflo $s0
move $s0, $a0
li $t3, 65538
slti $t2, $t3, -1
sll $t3,$t3, 2

9
 rol $t4, $t4, $t5
bge $a0, $a1, LoopTop

mul $v0,$t0, $t1 [Since the Green Card does not list mul, it is ok to
identify this as a pseudo, but in fact it is part of
the actual MIPS architecture now. It does
mult $t0, $t1 then mflo $v0]
mflo $s0
move $s0, $a0 Pseudo: add $s0, $a0, $zero (or addi $s0, $a0, 0)
li $t3, 65538 Pseudo: lui $at, 1, followed by ori $t3, $at, 2
slti $t2, $t3, -1
sll $t3,$t3, 2
rol $$t4, $t4, $t5 Pseudo: addi $at, $zero, 32, then sub $at, $at, $t5,
then srlv $at, $t4, $at, then sllv $t4, $t4, $t5,
then or $t4, $t4, $at
bge $a0, $a1, LoopTop
Pseudo: slt $at, $a0, $a1, then beq $at, $0, LoopTop

Question 3 (Quiz #1 Sec2 Spring 2016)

Write the shortest possible MIPS assembly language program which implements the C
code shown below:

int calculate (int y, int z)

{
return z*y + y*8;
}

Your code should use the fewest possible number of registers. You should make the
standard assumptions about which registers to use for y and z, and for the return value.
Your code should obey the software convention regarding the use of MIPS registers.

calculate: addi $v0,$a1,8

mul $v0,$v0,$a0
jr $ra

The shortest possible solution calculates y (z + 8) in two steps (add first, then multiply),
then returns to the caller. We use the mul instruction here, which avoids having to write
mult, then mflo $v0.

To minimize the use of registers, use the $v0 register instead of $t or other registers.

10
 Note: the first instruction could have also been addi $a1,$a1,8, since as callee we have
no obligation to save or protect the $a registers. Then the 2nd instruction would be mul
$v0,$a1,$a0.

Question 1 (MT #3 Fall 2015)

Write the utility function Sum_of_averages for finding the total of the average values found in
each 10-element group of a 1-dimensional array of element values. Sum_of_averages should be
a callable function that performs the task and returns to the calling program with the result value.
The address of the first element in the array is given by the caller in $a0. The length of the array
is not known, but it is known that the array’s last element is followed by a terminal value (similar
to the way the NULL character serves as a terminator for ASCII strings). The return value will
be in $v0. Sum_of_averages ignores any leftover elements that are not part of a 10-element
group. For example: if there are 34 values in the array, and the averages of the 1st 10, 2nd 10 and
3rd 10 are 5, -2 and 11 respectively, your Sum_of_averages function should return 14 to the
calling function. But if there are just 8 values in the array, it should return the largest negative
integer (-MAXInt) as the return value. Besides returning the sum-of-averages in a register, it
should also return that same value on the stack, putting it where it will be on the top of stack
after the return, for the caller to find it there.

Your Sum_of_averages routine should call the routine Avg_of_next_10 as many times as it
needs, and use the average values that are returned in its calculation. You can assume that
Avg_of_next_10 is already written, debugged, and available to you as a library function.
Avg_of_next_10 takes as an input argument in $a0 the first address in memory of a group of
consecutive elements. If there are 10 elements which have non-terminal values, then
Avg_of_next_10 returns the average of these 10 element values in $v0. But if there are less than
10 elements left and the terminal value is encountered instead, then the return value in $v0 will
be largest negative integer
(-MAXInt). In summary, Avg_of_next_10 finds and returns in $v0 the average of the next 10
array element values (or -MAXInt if there are not 10 more array elements). [Reminder: you
don’t need to write Avg_of_next_10, it already is available.]

You should write the MIPS assembly language code for Sum_of_averages. You may use real
MIPS instructions and pseudo-instructions, but you may not use psuedo-syntax. You should
explain your code with comments and a header. Code performance is important, but correctness
is more important! IMPORTANT REMINDER: as with any correct MIPS assembly code, both
the calling program and Avg_of_next_10 will obey the MIPS convention for the use of registers.
Therefore your code, Sum_of_averages, must also obey this convention, so that it can work
correctly with these other MIPS codes.

Solution:
########################################################
## Sum_of_averages: calculates and returns the sum of average-of-10 values,
## from an array, taken 10 elements at a time

11
##
## The algorithm does 6 things:
## a. it pushes ra, s0, s1 and s2 values onto stack to protect them
## b it initializes and finds the average value of the 1st 10 elements
## c. looping, it repeatedly calls Avg_of_next_10 to find the average of next 10
## elements, and accumulates it into c
## d. transfer the sum of averages into v0, as the return value
## e. it pops ra, s0, s1, and s2 values from stack and restores them to registers
## f. it returns to the calling program
##
##
## Register Usage
## a0 holds the address of the array, and of each remaining sub-array
## $s0 holds the starting address of the array, and of each remaining sub-array
## $s1 holds the sum of the average-of-10 values
## $s2 holds the –MAXint, the largest possible negative integer: 1000000…….
## $v0 holds the return values (avg of 10, and sum of averages)
## $ra holds the return address
##
#######################################################

Median_avg:
## push onto stack to protect (part a of the algorithm)
addi $sp, $sp, -16 ## make room for 4 new items on top of stack
sw $ra, 12($sp) ## push return address
sw $s0, 8($sp) ## push s0
sw $s1, 4($sp) ## push s1
sw $s2, 0($sp) ## push s2

## find avg value of 1st 10 elements in array (part b of the algorithm)

mov $s0, $a0 ## save the original array starting address in s0
mov $s1, $0 ## initialize the total to 0
li $s2, 0x10000000 ## put –MAXint value into $s2 to use in testing later
jal Avg_of_next_10 ## the average value is returned in $v0
beq $v0, $s2, End ## if –MAXint, go to End (since no more array)

## loop to repeatedly find average of 10, and accumulate it (part c of the algorithm)
addi $s1, $s1, $v0 ## accumulate $v0 into the total
addi $s0, $s0, 40 ## address of rest of array = last address + 40 bytes
mov $a0, $s0 ## put starting address of remaining array into $a0
jal Avg_of_next_10 ## the average value is returned in $v0
bne $v0, $s2, Loop ## if not –MAXint, iterate loop again

## transfers the sum of averages into v0 to return with it (part d)

mov $v0, $s0 ## transfer sum of averages into $v0 for return

12
 ## pop from stack to restore registers (part d of the algorithm)
End: lw $s0, 8($sp) ## pop s0
lw $s1, 4($sp) ## pop s1
lw $s2, 0($sp) ## pop s2
addi $sp, $sp, 12 ## restore stack pointer to original value +4
lw $ra, 0($sp) ## restore the ra register value
sw $v0, 0($sp) ## put the result value onto the top of stack

## return to calling program (part e of the algorithm)

jr $ra ## bye bye go home to point of call

Question #1 (MT #2 Fall 2015)

Write the utility routine Median_avg for finding the average of the median values in 1-dimensional
arrays. Median_avg should be a callable function that performs the task and returns to the calling
program. The address of the first element in the array is given in $a0, and the length of the array is
given in $a1. The return value in $v0 is (Median(lower_halfarray) + Median(upper_halfarray)) / 2.
You may assume that the array contains at least 2 elements. If the number of elements is odd, then it
doesn’t matter which half-array is bigger in size by 1. Besides returning the average of the 2 half-
array’s median values in a register to the calling program, it should also put it in heap. Upon return,
the caller program will have 2 copies of the computed value: in a register, and in a dynamic memory
location (the address of that location should be returned in $v1).

Your Median_avg routine should call the routine find_Median twice, and use the median values that
are returned in its calculation. You can assume that find_Median is already written, debugged, and
available to you as a library function. Like Median_avg, it expects to find the address of the half-
array in $a0, and the length of it in $a1. Using these, it finds and returns the median value in $v0.
[Reminder: you don’t need to write find_Median, it already is available.]

You should write the MIPS assembly language code for Median_average. You may use real MIPS
instructions and pseudo-instructions, but you may not use psuedo-syntax. You should explain your
code with comments and a header. Code performance is important, but correctness is more
important!

########################################################
## Median_avg: calculates and returns the average of 2 median values,
## from 2 half-arrays. Signed 32-bit integer values are assumed.
##
## The algorithm does 8 things:
## a. it pushes ra, s0, s1 and s2 values onto stack to protect them
## b it calculates the starting address of the 2nd half-array (byte address, of
## course) and the lengths of both half-arrays, in items
## c. it calls the find_Median function for the 1st half-array

13
## d. it calls the find_Median function for the 2nd half-array
## e. it calculates the average of the 2 median values found in c and d
## f. it obtains a location in heap and puts the average there, and into v0
## g. it pops ra, s0, s1, and s2 values from stack and restores them to registers
## h. it returns to the calling program
##
## Register Usage
## a0 holds the address of the 1-dimenstional array, of the 1st half-array, and
## of the 2nd half-array
## a1 holds the array length, 1st half-array length, & 2nd half-array length
## $t0 holds the length, in bytes, of the 1st half-array
## $s0 holds the address of the 2nd half-array
## $s1 holds the length of the 2nd half-array
## $s2 holds the 1st median value, and the median average value
## $v0 holds the 1st median value, the 2nd median value, and the Median_avg
## return value
## $v1 holds the address of the value stored in heap, the other return value
## $ra holds the return address
##
#######################################################

Median_avg:
## push onto stack to protect (part a of the algorithm)
addi $sp, $sp, -16 ## make room for 4 new items on top of stack
sw $ra, 12($sp) ## push return address
sw $s0, 8($sp) ## push s0
sw $s1, 4($sp) ## push s1
sw $s2, 0($sp) ## push s2

## calculate values for 1st and 2nd calls to find_Median (part b above)
srl $s1, $a1, 1 ## find half-length of array, in items ( = a1 / 2)
sub $a1, $a1, $s1 ## find other half-length of array, in items
sll $t0, $a1, 2 ## convert length to bytes (i.e multiply by 4)
add $s0, $a0, $t0 ## find starting address of 2nd half-array (byte address)

## 1st call to find median of lower_halfarray (part c of the algorithm)

## $a0 and $a1 already have the correct values
jal find_Median ## the median value is returned in $v0
move $s2, $v0 ## protect it in $s2

## 2nd call to find median of upper_halfarray (part d of the algorithm)

move $a0, $s0 ## transfer pre-computed starting address into $a0
move $a1, $s1 ## transfer pre-computed half-array length into $a1
jal find_Median ## the median value is returned in $v0

14
## calculate the average of the median values (part e of the algorithm)
add $s2, $s2, $v0 ## add the two median values from the 2 half-arrays
sra $s2, $s2, 1 ## sra 1 divides by 2 to get the average value

## put the value into the heap, and into the return register (part f above)
li $a0, 4 ## ask for 4 bytes in heap (to store 1 integer value)
li $v0, 9 ## syscall 9 is sbrk, to allocate space in heap
syscall ## ask OS to do it
move $v1, $v0 ## transfer the address into $v1 for return
sw $s2, 0($v1) ## put the Median_avg value into the heap location
move $v0, $s2 ## transfer Median_avg into $v0 for return

## pop from stack to restore registers (part g of the algorithm)

lw $ra, 12($sp) ## pop return address
lw $s0, 8($sp) ## pop s0
lw $s1, 4($sp) ## pop s1
lw $s2, 0($sp) ## pop s2
addi $sp, $sp, 16 ## restore stack pointer to original value

## return to calling program (part h of the algorithm)

jr $ra ## bye bye go home to point of call

Question 2 (MT #1 Fall 2015)

Write the utility program insert for linked lists. It should be a callable function that performs the
task and returns to the calling routine. You may use real MIPS instructions and pseudo-
instructions. You should explain your code with comments and a header. Code performance is
important, but correctness is more important! The linked list elements have two parts: first a 32-
bit address portion, and after that a 32-bit data portion. These are located in adjacent words of
memory, in heap. You should consider the head element of the list to be the 1st element (N = 1)

The insert function puts a new element into the linked list at postion N+1, inserting it after the
Nth element. To keep things simple, you can assume that the input N is valid, i.e that there are at
least N elements in the list, and that N > 0.. The address of the head of the list is given in $a0, the
address of the element to be added is given in $a1, and N is given in $a2.

Again, you should explain your code with comments and a header.

########################################################
## insert: to insert a new item into the linked list after the Nth element
##
## The algorithm does 3 things:
## a. it finds the location of list element N, moving to the next element repeatedly with a loop
## b it modifies the pointers of element N and the new element, so that it becomes part of

15
## the list at (new) position N+1
## c. it returns to the calling program
##
## In the comments below, notation “N(address) means the address portion of list element N”
##
## Each element’s address part is assumed to point to the next element, to the address part.
## As described in the problem statement, the address part (containing the pointer to the next
## element)comes first, and the data part (containing the value) comes next, i.e. 4 bytes later
## in memory.
## The model of linked list used is shown below:

## Note that if the address part of element N were to point to the data part of element N+1,
## it would not affect the algorithm at all. It would only affect the implementation of the
## loop code in a minor way.
##
## Register Usage
## t0 as loop counter in the loop part, and later as a temp for the pointer changing part
## a0 holds the address of element #N . Initially, the head element’s address is in a0
## a1 holds the address of the new element to be inserted
## a2 holds the number N of the element to be searched for in the loop
## ra holds the return address
##
#######################################################

insert:
## initialization of loop (part a of the algorithm)
li $t0, 1 ## the loop counter is initially 1, since it holds the element number and
## a0 initially contains the address of element 1, the head element.
## Keeping t0 and a0 synchronized avoids “off by 1” errors
j Test ## enter the loop the first time at the test, not at the top

## loop to find element N (part a of the algorithm)

Top: lw $a0, 0($a0) ## get next element’s address part and put it in a0. The offset of “0” is
## due to assumption in the linked list model that the address points to
\ ## the address part of the next element. If instead it points to the data
## part, then “-4” would be the correct amount of offset.
addi $t0, $t0, 1 ## increment the count, which holds the element number
Test: bne $t0, $a2, Top ## continue to iterate in the loop, until a0 contains the address of
## element N. Each time this instruction is executed, t0 = loop count
## = n, and a0 contains the address of element n (using the notation
## stated above: it contains n(address).
16
 ## The final time it is executed, n = N (i.e. t0 = a2), so it ends the loop.

## insert the new list element (part b of the algorithm)

## this section of code uses a temp location (t0) in a kind of triangle
## swap, to change the address parts of the 2 elements:
## temp  N(address)
## N(address)  address of new element
## New(address)  temp

lw $t0, 0($a0) ## make a copy in temp of N(address) the address part of element N
sw $a1, 0($a0) ## store the address of the new element into N(address)
sw $t0, 0($a1) ## store the temp into New(address), which is now N+1(address)

## return (part c of the algorithm)

jr $ra ## return to point of call

Question #1 (Retake Spring 2015) MIPS Assembly Code

a) Write a callable MIPS assembly language routine named word_count which counts the
number of words in a document of ASCII characters, using 2 utility routines: skip_spaces and
sentance_words. Your word_count routine returns the number of words in the document.
word_count is kept simple by repeated calls to the 2 utilities, which are pre-written library
functions. Since they are already written, you just use them in word_count.

skip_spaces receives as input the address of the location in an ASCII string pointing to the first
space character after a non-space character. It moves the pointer, skipping over all spaces (there
can be 1 or more than 1). Its return value is the address of the next non-space character (if there
is one) or 0, if the end-of-string is encountered.

sentance_words receives as input the address of the first character of the first word of the
sentance, searches for the end of the sentance (marked by a period . a question mark ? or an
exclamationpoint !) and returns two output values: a) the address of the first space after the
sentance (or 0, if the end-of-string is encountered) and the number of words in the sentance.
[Assume that there are no partial incomplete sentances in the document.]

Give the MIPS code for word_count. Use only real MIPS instructions.

Counting words in a document will be done by initializing count, then in a loop repeatedly
counting the words in the next sentance, adding that to the total word count, skipping spaces till
the next sentance, etc until the NULL character is encounterd. The total count is the return value
of this procedure. The stack must be used to preserve the value of $ra since word_count is non-
leaf, meaning it calls sub-routines (skip_spaces and sentance_words). And it must preserve the
value of an $s-register, which holds the count value. A $t-register can not be used for count,
since they aren’t preserved across the sub-routine calls.

17
word_count: addi $sp, $sp, -8 // open space for 2 values on the stack
sw $s0, 0($sp) // save old s0 value, in order to use s0 register
sw $ra, 4($sp) // push ra, since it will be changed by jal calls
addi $s0, $0, 0 // initialize count = 0
loop_top jal sentance_words // get number of words in next sentance
add $s0, $s0, $v1 // accumulate the sentance total into count
beq $v0, $0, end // test for end-of-text (if v0=0 NULL was found)
add $a0, $0, $v0 // move address pointer into place for next call
jal skip_spaces // skip over spaces between sentances
beq $v0, $0, end // test for end-of-text (if v0=0 NULL was found)
add $a0, $0, $v0 // move address pointer into place for next call
j loop_top
end: add $v0, $0, $v0 // put total word count into return value register
lw $s0, 0($sp) // restore s0 register’s old value
lw $ra, 4($sp) // restore ra register’s old value
addi $sp, $sp, -8 // return the stack pointer to original value
jr $ra // return to callee

Question #1 (Final Spring 2015)

a) Write a MIPS routine named fact which efficiently and quickly computes and returns the
factorial of a non-negative integer input value. Use only real MIPS instructions. Your code
should seek to minimize the number of multiplications (since 32-bit multiplication is a slow,
multi-cycle, operation) and of course should minimize the total number of instructions executed.

To make assembly code execute fast, a compiler should do the following:

--avoid calls and returns (which means do this task iteratively, NOT
recursively)
--use bottom-tested loops (which eliminate the j Top instruction)
--avoid inequality tests (which take 2 MIPS instructions to do)
instead stick to simple beq and bne tests
--avoid unnecessary register transfers; instead put values where they will need to
be in the end
--avoid stack usage (pushing and popping)
--avoid unnecessary memory usage (loads and stores); instead use values in
register as much as possible
--as much as possible, avoid slow instructions like mul, div, floating
point, etc (which are all multi-cycle)

In light of the above, a fast iterative algorithm for fact(n) is:

fact = 1
if (n == 0)
return (1)

18
 temp = 0
else do {temp++
fact = fact * temp
while (temp != n)
return (fact)

fact: addi $v0, $0, 1 // fact = 1

beq $a0, $0, end // test for n == 0 case
add $t0, $0, $0 // make temp = 0 going into the loop
do: addi $t0, $t0, 1 // temp++
mul $v0, $v0, $t0 // fact = fact * temp
bne $t0, $a0, do // test loop limit: temp != n
end: jr $ra // return (fact)

[Note1: The above solution works correctly for the cases n=0 and n>0, but it can be
made faster by making the n=1 case an initial test, thus avoiding one loop iteration and a
multiply operation.

The pseudocode becomes: if (n == 0 or n==1)

return (1)
temp = 1
. . .

fact: addi $v0, $0, 1 // fact = 1

beq $a0, $0, end // test for n == 0 case
beq $a0, $v0, end // test for n == 1 case
addi $t0, $0, 1 // make temp = 1 going into the loop
do: addi $t0, $t0, 1 // temp++
mul $v0, $v0, $t0 // fact = fact * temp
bne $t0, $a0, do // test loop limit: temp != n
end: jr $ra // return (fact) ]

[Note2: Taking the above improvement a step further, the code could be modified further
to make n=2 as an additional initial case, further reducing loop iterations and number of
multiplications by 1.

b) Analyze your code from part a) to determine the performance of computing fact (n). Fill in
the values in the table below.

For the first code given above, the table values are:
n | # of instr. executed | # of multiplications
0 | 3 | 0
1 | 7 | 1
2 | 10 | 2

19
 x | 3x + 4 | x

[Note1: For the second code given above, the table values are:
n | # of instr. executed | # of multiplications
0 | 3 | 0
1 | 4 | 0
2 | 8 | 1
x | 3x + 2 | x-1
As expected, there is a slight speedup: 2 less instructions, & 1 less multiply ]

[Note2: For the code with if (n == 0 or n==1) return (1)

else if (n==2) return (2)
temp = 2
the table values are:
n | # of instr. executed | # of multiplications
0 | 3 | 0
1 | 4 | 0
2 | 6 | 0
3 | 9 | 1
x | 3x | x-2
As expected, there are again 2 less instructions & 1 less multiply]

[Note3: For the recursive factorial code on page 331, the table values are:
n | # of instr. executed | # of multiplications
0 | 9 | 0
1 | 9 | 0
2 | 22 | 1
x | 13x - 4 | x-1

3x is more than 4 times faster than 13x, so recursive code is slow code!! In addition to
the number of instruction being greatly bloated due to the overhead of calls and returns and
stack operations, each memory access (the stack pushes and pops) is a potential cache miss,
which can create stalls and further slow down the execution. From a performance perspective, it
is hard to find anything good to say about recursive implementations.]

Question 2 (MT #1 Spring 2015)

(a) Write a MIPS code fragment that is equivalent to the code below which writes the maximum
value to the memory location labeled M. For maximum credit, include comments and use
minimal number of instructions. Only real MIPS instructions are allowed, but you may use a
pseudo-syntax with the load and store instructions.

int A[100] = {4, -1, 3, ..., 6, 17};

int max = A[0];
int i;
20
 for (i=1; i<100; i++)
if (max < A[i])
max = A[i];

Answer:
Label Instruction Comment
.data
A: .word 4, -1, 3, ..., 6, 17 # int A[100]={4,-1,3,..., 6,17}
M: .alloc 1 # max value will be stored here
.text
lw $t1, A($0) # initialize max=A[0]
addi $t0, 0, 4 # initialize i = 1
slti $t2, $t0, 400 # check loop exit test
beq $t2, $0, Exit # if i>=100, exit
Loop: lw $t3, A($t0) # read in current element
slt $t2, $t1, $t3 # is max < A[i]?
beq $t2, $0, Skip # if not, skip update
addi $t1, $t3, 0 # else new max = A[i]
Skip: addi $t0, $t0, 4 # update i
slti $t2, $t0, 400 # check loop exit test
bne $t2, $0, Loop # continue looping
Exit: sw $t1, M($0) # store maximum

Question #3 (Retake Spring 2014)

a) A MIPS single-cycle processor runs the following code, but performance is too slow. Instead
of buying an optimizing compiler, the company hires you to “hand tune” the code, in order to
achieve maximum performance and yet still compute the same thing. Be sure to use only real
MIPS instructions, part of the instruction set (not pseudo-instructions). Give the new code, after
“hand tuning”, in the space below.

compute_3a: addi $sp, $sp, -8

sw $s0, 0($sp)
sw $ra, 4($sp)
move $s0, $a0
lui $t0, 0x00FC
ori $t0, $t0, 0xCF00
move $t1, $0
Top: beq $0, $t0, Done
addi $t1, $t1, 1
add $s0, $s0, $t1
addi $t0, $t0, -1
j Top
Done: move $v0, $s0
21
 lw $s0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
jr $ra

Solution: The improved code will have the following changes:

a. the loop will be converted from top-tested to a faster bottom-tested loop
b. the stack pushing and popping will be eliminated, since it is unnecessary
c. instead of using $s0 in the loop, use $a0 or $v0, which eliminates a move
d. move pseudoinstructions will be converted to real MIPS instructions

compute_3a: lui $t0, 0x00FC

ori $t0, $t0, 0xCF00
addi $t1, $0, 0 # converted from move $t1, $0
Top: addi $t1, $t1, 1
add $a0, $a0, $t1
addi $t0, $t0, -1
bne $0, $t0, Top
Done: addi $v0, $a0, 0 # converted from move $v0, $a0
jr $ra

Question #1 (Retake Spring 2014)

Compile the two C routines below into MIPS assembly code. Use no pseudo-instructions; use
only real MIPS instructions, which are part of the instruction set architecture. Your code should
follow the MIPS convention for register usage and function calls.

a) int problem_1a(void) {
int x = 0;
for (j=0; j!=5; j++)
x = x + do_it(j) <<3;
return (x - 13);
}

Answer
problem_1a: addi $Sp, $sp, -16 # make room to push 4 items onto stack
sw $s0, 0($sp) # must preserve s-registers before using
sw $s1, 4($sp) # must use s-registers because t-registers
sw $s2, 8($sp) # would be changed by do_it
sw $ra, 12($sp) # preserve $ra since this routine calls do_it
addi $s0, $0, 0 # x = 0 in $s0
addi $s1, $0, 0 # j = 0 in $s1
addi $s2, $0, 5 # hold 5 in $s2
# loop is bottom-tested, no need for j Test this time

22
 # since 5 != 0
Top: addi $a0, $s1, 0 # put argument in $a0 before the call
jal do_it # call do_it
sll $t0, $v0, 3 # shift return value by 3
add $s0, $s0, $t0 # accumulate into x
addi $s1, $s1, 1 # j++
Test: bne $s1, $s2, Top # test if j != 5
addi $v0, $s0, -13 # return x - 13
lw $s0, 0($sp) # pop stack to undo pushes and restore the
lw $s1, 4($sp) # 4 original values
lw $s2, 8($sp)
lw $ra, 12($sp)
addi $Sp, $sp, 16 # restore stack pointer
jr $ra # return to point of call

b) For this part, PORTD = 0xFFFF0000 and TRISD = 0xFFFF0004. Other conditions are the
same as in part a).

int problem_1b (int a) {

TRISD = 0xFF00;
PORTD = a;
while (PORTD & 0xFF00 == 0) ;
return PORTD;
}

Answer
problem_1b: addi $t0, $0, 0xFF00 # put 0xFF00 into $t0
lui $t1, 0xFFFF # PORTD address = 0xFFFF0000, put into $t1
sw $t0, 4($t1) # TRISD address (=FFFF0004) gets 0xFF00
sw $a0, 0($t1) # PORTD gets $a0, which contains a
spin: lw $t2, 0($t1) # get PORTD value
and $t3, $t2, $t0 # PORTD & 0xFF00
beq $t3, $0, spin # spin while PORTD & 0xFF00 = 0
addi $v0, $t2, 0 # put PORTD value into $v0 for return value
jr $ra # return to point of call

Question #1 (MT #2 Spring 2014)

Translate the C function below into MIPS assembly language. Pay particular attention to
properly saving and restoring registers across function calls, and obeying the MIPS convention
for register usage. Clearly comment your code. Keep local variable a in $s0. You may use
pseudo-instructions if they are well-known (or obvious).

23
int q1(int n, int m) {
int a;

a = m + 2;
if (n == 0) a = 5;
else a = a + (n * n) + q1(n – 1, m + 1);
return a * m;
}

Solution:
#####################################################
## MIPS code for function q1
##
## $a0 contains the first input argument: n
## $a1 contains the 2nd input argument: m
## $s0 contains local variable a
## $t0 is used as a temporary register at 1 place
## $v0 contains the return value from function calls to q1
## $ra contains the return address
##
## q1 is a non-leaf procedure, since it makes a call to invoke a
## routine (in fact, it is recursive, since it calls itself)
##
## q1 has an entry label “q1” , the name of the function in C
## q1 has a single point of return, since the C code has a single return
#####################################################

q1: addi $sp, $sp, -12 # make room to push 3 items

sw $ra, 0($sp) # push $ra, since the jal call will change it
sw $a1, 4($sp) # push $a1, since the original value of m
# is needed, after m+1
sw $s0, 8($sp) # push $s0, since it must be saved
# according to the MIPS convention

addi $s0, $a1, 2 #a=m+2

bne $a0, $zero, Else # if n != 0 branch to Else
addi $s0, $zero, 5 #a=5
j Ret # now go to return part

Else: mul $t0, $a0, $a0 # $t0 = n*n

add $s0, $s0, $t0 # a = a + n*n ; this value will be
# preserved across the call
addi $a0, $a0, -1 # new n = n-1
addi $a1, $a1, 1 # new m = m+1
jal q1 # call q1(n-1, m+1)

24
 # return value will be in $v0

add $s0, $s0, $v0 # a = [a + n*n] + q1(n-1, m+1)

lw $ra, 0($sp) # pop $ra from stack

lw $a1, 4($sp) # pop original m from stack
Ret: mul $v0, $s0, $a1 # return value = a * m
lw $s0, 8($sp) # pop $s0 from stack, to restore original value
addi $sp, $sp, 12 # restore stack pointer to original value
jr $ra # return back to point of q1 call

Question #3 (MT #1 Spring 2014)

Write a MIPS program to find the median value in a list of unsorted integers. Example: in the list
[1 3 6 7 2 8 4] the median value is 4. In the list [1 4 3 2], 2 is the median value, not 3.
Your program main should follow the outline given below, calling GetList and Sort when
necessary to help it do its job. It should output the median value with a short explanatory
message, then end, exiting to the operating system. Your program must obey the MIPS
convention for register usage. Your program should be a short as possible, and use as few
registers as possible. You may use pseudo-instructions if they are well-known (or obvious).

GetList is an existing library I/O utility. When called, it dialogs with the user to determine the
size of the list, and gets the members of the list, making sure that each is an integer value
representable in 32 bits. It acquires memory space from the OS to store the list elements in
sequence as an array. Upon return, the starting address of the array is in $v0 and the number of
elements in the array is in $v1.

Sort is an existing library utility function which takes the starting address of the unsorted list of
integers (in $a0) and the number of integers in the list (in $a1). It sorts the list values into
increasing order, and returns the address (in $v0) of the beginning of the sorted list.

.text
main: jal GetList # get list values from user
move $s0, $v1 # save the number of elements, since $v1 is not preserved
move $a0, $v0
move $a1, $v1

jal Sort # sort list

# calculate address of median value

addi $s0, $s0, -1 # number of elements - 1
srl $s0, $s0, 1 # integer divide by 2 (loses LSB) to get element offset
sll $s0, $s0, 2 # multiply by 4, to get byte offset
add $v0, $v0, $s0 # add base address to offset to get address of median element

25
 lw $s0, 0($v0) # get median value

la $a0, exp_msg # output explanatory message

li $v0, 4
syscall

move $a0, $s0 # output median value

li $v0, 1
syscall

li $v0, 10 # finish and exit

syscall

.data
exp_msg: .asciiz “The median value of the list is “

Question #3 (Retake Fall 2013)

b) Consider the following if statements and their implementation in MIPS. Some of these
implementations can be incorrect. Analyze each of them and state whether the
implementation is correct or incorrect. Assume that $19 is used for i and $20 is used for j.
For incorrect one(s), if any, provide the corrected version(s) without using
pseudoinstructions.

i) if(i > j) go to L1; $19 > $20 ==> $20 < $19
slt $1, $19, $20 ==> slt $1, $20, $19
bne $1, $0, L1
is not correct

ii) if(i >= j) go to L1; $19 >= $20 ==> not ($19 < $ 20)
slt $1, $20, $19 ==> slt $1, $19, $20
beq $1, $0, L1
is not correct

iii) if(i < j) go to L1;

slt $1, $20, $19 ==> slt $1, $19, $20
bne $1, $0, L1
is not correct

26
d) The following program tries to copy bytes from the address in register $t3 to the address in
$t4, one byte at a time, counting the number of bytes copied in register $t2. The program
stops copying when it finds a byte with a value equal to 0 (note that 0 is not copied).

i) Complete the missing parts of the following program. If you need you may introduce
labels (such as L1, L2) to branch to. Provide a comment for each line.
li $t1, 0 # Clear $t1
li $t2, 0 # Initialize the counter
L1: lb $t1, 0($t3) # Get the byte pointed by $t3 to $t1
beq $t1, $zero, L2 # If it is 0 exit loop
sb $t1, 0($t4) # Store byte to location pointed by $t4
addi $t2, $t2, 1 # Increment the counter
addi $t3, $t3, 1 # Increment from pointer
addi $t4, $t4, 1 # Increment to pointer
b L1
L2:
ii) Assume that for the above code segment we have the following data segment
.data # Starts at memory location 1001 000016
from: .word -1, -2, -3, -4, -5, 0
to: .space 30

Assume that, before executing the code segment given in section-i, $t3 and $t4 are
initialized as follows.
la $t3, from
la $t4, to

What will be the contents of the following registers (shown below) after executing the code
segment given above? (Give the values in hexadecimal. To get credit for this section you
have to the give the contents of the registers for the code segment which is completed in the
correct way.)

$t3: 10 01 00 14
$t4: 10 01 00 2C
$t2: 00 00 00 14
$t1: 00 00 00 00

Question #1 (Final Fall 2013)

a) Write a short MIPS subroutine to conditionally exchange 2 integer values in memory, if and
only if the first one is greater than the second one. The address of the first value is passed in $a0,
and the address of the second value is passed in $a1. The return value should indicate if the
exchange was made: 0 = not swapped; 1 = swapped. The entry point of your subroutine is the
label cond_exch: Your code should follow the MIPS convention for register usage. You may use
pseudo-instructions.

27
cond_exch: lw $t0, 0($a0)
lw $t1, 0($a1)
bgt $t0, $t1, Swap
NoSwap: li $v0, 0
j Return
Swap: sw $t0, 0(a1)
sw $t1, 0($a0)
li $v0, 1
Return: jr $ra

Note: cond_exch can be done with 8 lines of MIPS code; the 9-line version here is given for
clarity and understandability

b) Analyze the code below, and determine the values of the given registers just before executing
the instructions at A: B: and C: Assume that Start: is at address 0x0050000. Write your
answers in the box provided.

Start: la $t0, Exit

addi $sp, $sp, -4
sw $ra, 0($sp)
A: sw $t0, 0($sp)
li $t1, 20
li $t2, 2
Top: sll $t2, $t2, 1
B: sub $t3, $t2, $t1
addi $t1, $t1, -3
bgt $t1, $0, Top
sll $zero, $t1, 1
C: add $t1, $t1, $sp
Exit: addi $sp, $sp, 4
jr $ra

i) give the value of $t0 at A: 0x00500038

Note that la and bgt are both pseudoinstructions that take 8 bytes; all other instructions take 4
bytes. The address of Exit: is therefore 56 bytes (38 in hex) after Start:

ii) give the value of $t2

the 4th time at B: 32

$t2 is the initial value multiplied by 24 , or 2 x 16 = 32

28
iii) give the value of $t1 at C: -1

$t1 is the initial value, minus 7 x 3, or 20 – 21 = -1

Question #2 (MT #2 Fall 2013)

a. Consider the following code segment. Note that MIPS code segment begins at memory
location 00 40 00 00 (hex.) and data segment begins at memory location 10 00 00 00 (hex.).
.data
array: .word 0, 1, 3, 5, 10, 20
n: .word 6
a: .word … # its value is specified below in the subsections of the question
.text
.globl main
main: lw $t0, a
la $t1, array
lw $t2, n
li $t4,0
L1: beq $t2, $0, L2
lw $t3, 0($t1)
addi $t1, $t1, 4
addi $t2, $t2, -1
bgt $t3, $t0, L1
add $t4, $t3, $t4
b L1
L2:

i. What will be the contents of the following registers (in hex.) when we reach L2 during
execution time? Assume that the value of a is 0.
$t1 (2 pts.)
10 00 00 18

$t2 (1 pt.)
00 00 00 00

$t3 (1 pt.)
00 00 00 14

$t4 (4 pts.)
00 00 00 00

ii. What will be the contents of the following registers (in hex.) when we reach L2 during
execution time? Assume that the value of a is 10.

29
 $t1 (2 pts.)
10 00 00 18

$t2 (1 pt.)
00 00 00 00

$t3 (1 pt.)
00 00 00 14

$t4 (4 pts.)
00 00 00 13

b. Write the following method in the MIPS assembly language.

int PartB (int x, int y) {

int a;
a = (x * y) % 7; # Note that % represents mod
return (a);
}

The main( ) does the necessary initializations and performs a jump and link instruction to
come to the method. The method PartB returns the result by following the MIPS
programming conventions. In your implementation you are not allowed to use pseudo
instructions like move, etc.

// No need to write anything for the main ( )

PartB: # Write your MIPS assembly language program below

mult $a0,$a1
mflo $t0
li $t1,7
div $t0,$t1
mfhi $v0 # move remainder to $v0
jr $ra

Question #1 (MT #2 Fall 2013)

a. Consider the following code segment.

main: lw $8, 100($7) # at memory location 00 40 00 00 (hex.)

lw $5, main
beq $8, $5, main

ii. What will be the contents of $5 (in hex) after executing the above code segment?

30
 Note that the instruction at memory location "main" is loaded into $5.

8C E8 00 64

c. Assume that $f0 contains FFFFF830. After executing

mfc1 $t0, $f0
li $v0, 1
move $a0, $t0
syscall

What will be the result of the above code segment?

-2000

Summary of syscalls
Service Code in $v0 Arguments
print integer 1 $a0 = integer to print
print float 2 $f12 = float to print
print double 3 $f12 double to print
print string 4 $a0 = address of null-terminated string to print

Question #6 (MT #1 Fall 2013)

a) Trace the execution of the following program, to determine the final values in $t1 and in $v0
at time it return. Assume the initial value in $a0 is 31

.text // a0 is initially 31
Q6_a: la $t3, A // t3 contains the address A
lw $t0, 0($t3) // t0 now contains -4
srl $a0, $a0, 2 // a0 now contains 7 (31 shifted right 2 places)

sub $t1, $a0, $t0 // t1 = 7 – (-4) = 11

slt $t3, $t1, $zero // t3 = 0 since 11 !< 0
bne $t3, $zero, Out2 // branch to Out2 not taken
slt $t3, $zero, $t1 // t3 = 1 since 0 < 11
bne $t3, $zero, Out3 // branch to Out3 is taken

Finish: addi $v0, $zero, 1 // when t1 = 0

jr $ra
Out2: addi $v0, $zero, 0 // when t1 < 0
jr $ra
Out3: addi $v0, $zero, 2 // when t1 > 0
jr $ra
31
 .data
A: .word -4

$t1 = 0x0000000B (or 11 in decimal, since 7 minus -4 = 11) (5 pts)

$v0 = 0x00000002 (or 2 in decimal, since $t1’s final value is positive, (5 pts)

b) Write a short function in MIPS assembly language named get_exp which takes a single-
precision floating point number in $f0 as input, and returns the actual value of the exponent
(without bias) in $v0. The function must be callable, have no unexpected side effects, and obey
the MIPS convention for register usage. Your routine should be a short as possible, and use as
few registers as possible.

One possible answer (the shortest one) is:

get_exp: mfc1 $v0, $f0 # move f0 into v0

sll $v0, $v0, 1 # shift left to eliminate S bit
srl $v0, $v0, 24 # shift right to eliminate F bits
addi $v0, $v0, -127 # remove the bias from E
jr $ra # return, with actual exponent value in v0

Question #1 (Retake Spring 2013)

In this problem, you will write the MIPS assembly code for 2 different subroutines. Your MIPS
routines must follow the MIPS convention for register usage, concerning those which must be
preserved across a call and return. You may use pseudo-instructions. To get full credit, your
code should be fully correct, and it should be efficient.

The subroutine max_diff takes 3 integer values as input, and returns the maximum difference
between any 2 input values. For example, if -8, 5 and 2 are the inputs, the 6 differences are -13, -
10, 13, 3, 10, -3, but the maximum difference is 13. The 3 input arguments are given in $a0, $a1,
and $a2, and the output value is returned in $v0. You must implement max_diff in a way that
makes 3 calls to abs_diff, and compares these differences to find the maximum difference.

a) Write the code for max_diff

Solution:
max_diff: addi $sp, $sp, -20 # make room on the stack to save 5 important regs
sw $ra, 0($sp) # $ra must be saved, since jal calls change it
sw $s0, 4($sp) # $s-registers must be saved, since they are changed
sw $s1, 8($sp) # when written to, at various places in the code
sw $s2, 12($sp)
sw $s3, 16($sp) # $s3 will be used to contain the largest abs_diff

32
 move $s0, $a0 # put the 3 input parameters in a safe place (s-regs)
move $s1, $a1 # since $a-registers AREN’T saved/preserved across
move $s2, $a2 # call & return. They can be changed by the callee

jal abs_diff # 1st call, with $a0 and $a1

move $s3, $v0 #

second_call: move $a0, $s0 # $s0 contains original $a0

move $a1, $s2 # $s2 contains original $a2
jal abs_diff # 2nd call, with original $a0 and $a2
ble $v0, $s3, third_call # if abs_dif is > value in $s3,
move $s3, $v0 # move it in as the new largest abs_diff in $s3

third_call: move $a0, $s1 # $s1 contains original $a1

move $a1, $s2 # $s2 contains original $a2
jal abs_diff # 3rd call, with original $a1 and $a2
bge $v0, $s3, return # if abs_diff in $v0 is >= value in $s3, return with it
move $v0, $s3 # else switch larger value from $s3 into $v0
# so that $v0 has the max diff now
return: lw $ra, 0($sp) # time to pop off from the stack, restoring the values
lw $s0, 4($sp) # of the 5 registers, in preparation for returning
lw $s1, 8($sp)
lw $s2, 12($sp)
lw $s3, 16($sp)
addi $sp, $sp, 20 # restore the $sp to its original value
jr $ra # return to the point of call

The subroutine abs_diff takes two integer values as inputs and returns the absolute value of their
difference. It uses the $a0 and $a1 registers for input arguments, and $v0 to output the value of
the absolute difference. abs_diff does its job without calling any subroutines.

b) Write the code for abs_diff

Solution:
abs_diff: sub $v0, $a0, $a1 # take the difference between the two inputs
abs $v0, $v0 # take the absolute value of the difference
jr $ra # return to the point of call

Question #1 (Final Spring 2013)

Compile this high-level language (HLL) code into MIPS assembly code, by hand. You should
follow the MIPS convention for register usage. Assume that routines func and min exist, and

33
work correctly to do their functions. Make your loop bottom-tested for performance. You may
use pseudo-instructions.

int Q1_code ( ) {
int x, y, z;
x = 0;
for (z = 0, z ≤ 10, z ++)
{ x = func (z, x);
y = func (x, z);
}
return (min (x, y));
}

The MIPS assembly program is started for you on the next page, including the header and the
stack pushing and popping. Following the given header and its use of registers, complete the rest
of the program in the space provided.

Solution: (in italic, the rest was provided at the time of the exam)
## In this program, the following register assignments are made:
##
## S-registers are used to protect values across the call-returns
## $s0 conatains x $s1 contains y $s2 contains z
##
## $a0 and $a1 are used in their normal way, for input parameters
## $v0 is used in its normal way, for output values
## $ra is used for the return address, in the normal way
## $sp is used for stack pointer address, in the normal way
##

Q1_code: addi $sp, $sp, -16 # push ra and s-registers onto stack
sw $ra, 0($sp)
sw $s0, 4($sp)
sw $s1, 8($sp)
sw $s2, 12($sp)

addi $s0, $zero, 0 # initialize x = 0 (mov and add are OK also)

# throughout the code whenever addi is used, move or add could also have been used

addi $s2, $zero, 0 # initialize z = 0

j bottom_test # not actually necessary, since the loop is
# executed at least one time

loop_body: addi $a0, $s2, 0 # move z into $a0

addi $a1, $s0, 0 # move x into $a1

34
 jal func
addi $s0, $v0, 0 # move $v0 result into x

addi $a0, $s0, 0 # move x into $a0

addi $a1, $s2, 0 # move z into $a1
jal func
addi $s1, $v0, 0 # move $v0 result into y

addi $s2, $s2, 1 # z++

bottom_test: ble $s2, 10, loop_body # a pseudoinstruction allowed by MARS

return: addi $a0, $s0, 0 # move x into $a0

addi $a1, $s1, 0 # move y into $a1
jal min # result of min will be in $v0, where it
# needs to be for final return to calling point

lw $ra, 0($sp) # pop ra and s-registers from stack

lw $s0, 4($sp)
lw $s1, 8($sp)
lw $s2, 12($sp)
addi $sp, $sp, 16

jr $ra # return to place of call

Question 2 (Makeup Spring 2013)

void useless(int z[],int length, int choice){

int i,j,k;

j = choice;
k = length - choice;

for(i=0; i <= length; i = i + 2){

if(i + j > k + length){
z[length] = i + length;
while(z[length] < z[j]){
j--;
k++;
}
}
while(j > z[0]){
j--;
for(k=i; i+k > length; k--)
choice = choice + 2;

35
 quicksort(z,i-1,choice-1);
}
z[i] = j + k;
useless(z,j,k);
}
}

The C code for the useless function is given above, where x[] is an array of 32-bit integers to be
used, and where length and choice are integer values. Translate the HLL function into a callable
MIPS assembly language routine by the same name. Put your useless MIPS code below. You do
not need to write code for quicksort, just call it & assume that it performs the sorting. Be sure to:

--use only real MIPS instructions, except for relative comparison branching (blt, etc)--you may
use pseudoinstructions ONLY for these branches
--make all your loops top-tested, not bottom tested
--implement using index addressing, not pointers
--use the given header and code outline to guide you
--create the code as a non-optimizing compiler would, directly from the C code. As directly
as possible, you are to “hand compile” from C into MIPS assembly

Starting with the partially complete header which is given, list all registers used, and what they
contain. Please write your MIPS code legibly, so that it can be read and understood. Note that
plenty of space is given, including the back of the page.

#############################################################
## useless routine: wastes time doing nothing in particular, using an array z of 32-bit integers
##
## $a0: input argument containing base address of array z
## $a1: input argument containing # of integers in array z
## $a2: input argument containing choice, a parameter used for useless purposes
## $s0: contains i
## $s1: contains j
## $s2: contains k
##
## Since useless is non-leaf, calls to itself and to quicksort may change
## the values in a0, a1 and a2. Therefore, these need to be in safe storage
## $s3: contains base address of array z (safe storage for $a0)
## $s4: contains length (safe storage for $a1)
## $s5: contains choice (safe storage for $a2)
##
## $t0, $t1: temporary storage locations for addresses and values in lw and sw operations
##
## The assembly code follows the C code in structure—there are 4 levels:
## -at the outer level: an overall for1 loop, which is implemented with initialization,
## then top-test, then body, then at the bottom incrementaion and goto the top

36
## -at the middle level: an if statement, a while1 loop, an assignment and a call to useless
## -at the almost-inner level: the if contains an assignment of z[] and a while1 loop.
## the while2 loop contains j--, the for2 loop, and a call to q-sort
## -at the very inner level are the statements in the bodies of while1 and for2
## All together, there are 2 while loop, 2 for loops and1 if statement. All of these are
## top-tested in MIPS, which means that the logic of the test (since it branches out and
## doesn’t execute) must be opposite of the test logic in C (which stays in and executes).
##
#############################################################
useless: # entry point for the routine

## do stack pushing, to preserve values of $s-registers (since we use and change them ) ###
## and to preserve $ra (since useless is non-leaf) ###

addi $sp, $sp, -28

sw $s0, 24($sp)
sw $s1, 20($sp)
sw $s2, 16($sp)
sw $s3, 12($sp)
sw $s4, 8($sp)
sw $s5, 4($sp)
sw $ra, 0($sp)

## Values are moved into $s-registers here, to be preserved across the many function calls,
## including recursive ones. Here, we do the initial 2 statements assigning j and k

add $s3, $a0, $0 # move address of x[] into safe storage ($s3)
add $s4, $a1, $0 # move length into safe storage ($s4)
add $s5, $a2, $0 # move choice into safe storage ($s5)

add $s1, $a2, $0 # move j  choice

sub $s2, $a1, $a2 # move k  length – choice

## do the for1 loop, which compares i and length. If the condition is met, the for1 loop will run.
## But if i > length, then the for1 loop isn’t needed, and the useless routine exits via Exit..

add $s0, $0, $0 # initialize i in for1 loop

for1test: bgt $s0, $s4, Exit # if i<=length do the for1 loop; if not,
# then go to Exit, since for1 loop and useless
# are both finished

## do the if test, which compares i+j to k+length. If the condition is met, the if clause

37
## has work to do: the z[length] assignment and the while1 loop. But if i+j<=k+length,
## then the if is skipped, and the for1 loop continues with the while2 loop

if_test: add $t0, $s0, $s1 # get i+j

add $t1, $s2, $s4 # get k+length
ble $t0, $t1, while2test # if i+j > k+length, do the if code; if not,
# then proceed to the while2 loop

assign_zlen: add $t0, $s0, $s4 # get i+length

sll $t1, $s4, 2 # byte offset = length*4
add $t1, $t1, $s3 # address of z[length] = byte offset + base addr
sw $t0, 0($t1) # store i+length into z[length]

## Note that at this point, $t1 contains the address of z[length] , from assign_zlen above ##
lw $t1, 0($t1) # load z[length] value into $t1 (and use it
# repeatedly in the while1 loop
while1test: sll $t0, $s1, 2 # byte offset = j*4
add $t0, $t0, $s3 # address of z[j] = byte offset + base addr
lw $t0, 0($t0) # load z[j] value into $t0
bge $t1, $t0, while2test # if z[length] < z[j] do the while1 loop; if not,
# go to while2loop, since while1, and the if which
# contains it, are both finished
addi $s1, $s1, -1 # j--
addi $s2, $s2, 1 # k++
j while1test # end of while1 loop, goto its re-entry point
# for top-testing

## do the while2 loop, which gets the memory value from z[0] to compare in the test. ##
## Failing the test will cause exit from the loop. The loop body decrements j, does the for2 ##
## loop and calls quicksort.

while2test: lw $t0, 0($s3) # load z[0] value into $t0

ble $s1, $t0, Finish_up # if j > z[0] do the while2 loop; if not,
# then go to Finish_up, since while2 is finished

Decr_j: addi $s1, $s1, -1 # j--

addi $s2, $s0, 0 # initialize k in for2 loop (k  i)

for2test: add $t0, $s0, $s2 # t0 has i+k
ble $t0, $s4, Quicksort # if i+k >length do the for2 loop; if not,
# then go to Quicksort, since for2 is finished
addi $s5, $s5, 2 # choice = choice + 2
addi $s2, $s2, -1 # decrement the loop control variable k
j for2test # this is the bottom of the for2 loop,
# so goto its top for top-testing

38
Quicksort: addi $a0, $s3, 0 # put z[ ] into $a0
addi $a1, $s0, -1 # put i-1into $a1
addi $a2, $s5, -1 # put choice-1 into $a2
jal quicksort # call quicksort

j while2test # end of while2 loop, goto its re-entry point

# for top-testing

## Finish up the rest of the actions in the for1 loop: assign z[i], then call useless, then do ##
## the loop increment, then goto the for1test, the top-of-loop test ##
## ##
## The call to useless is preceded by 3 moves, to get the correct values into the 3 argument ##
## registers. The reason to load all 3 input arguments each time is that a-registers are ##
## NOT protected (i.e “saved”) by the callee, and may be changed by the callee. Since ##
## useless (which calls quicksort) may change a0, a1 and a2, we must not trust that ##
## “they won’t be changed” (i.e “bir sey olmaz” ) ! ##

Finish_up: add $t0, $s1, $s2 # put j+k into t0

sll $t1, $s0, 2 byte offset = i*4
add $t1, $t1, $s3 # address of z[i] = byte offset + base addr
sw $t0, 0($t1) # store j+k into z[i]

addi $a0, $s3, 0 # put x[ ] into $a0

addi $a1, $s1, 0 # put j into $a1
addi $a2, $s2, 0 # put k into $a2
jal useless # call useless (useless is recursive)

addi $s0, $s0, 2 # increment loop control variable i =i + 2

j for1test # this is the bottom of the for1 loop,
# so goto its top for top-testing

## do stack popping, to restore the values of the $s-registers (since we use and change them) ##
## and to restore $ra (since calls to useless and to quicksort have changed it) ##

Exit: lw $s0, 24($sp)

lw $s1, 20($sp)
lw $s2, 16($sp)
lw $s3, 12($sp)
lw $s4, 8($sp)
lw $s5, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 28
jr $ra # return to caller

39
Question 2 (Midterm Spring 2013)

void quicksort(int x[],int first, int last){

int i,j,pivot;

if(first<last){
pivot=first;
i=first;
j=last;

while(i<j){
while(x[i]<=x[pivot] && i<last)
i++;
while(x[j] > x[pivot])
j--;
if(i<j)
swap (x[], i, j) // swaps x[i] and x[j]
}

swap (x[], pivot, j) // swaps x[pivot] and x[j]

quicksort(x,first,j-1);
quicksort(x,j+1,last);

}
}

The C code for quicksort is given above, where x[] is an array of 32-bit integers to be sorted, first
and last are the indexes of the first and last position in the array. Write a callable MIPS assembly
language routine quicksort, which will be called from a main program (or other higher level
routine). Put your quicksort MIPS code below. You do not need to write code for swap, just call
it and assume that it performs the swap indicated.

Be sure to:
--use only real MIPS instructions, no pseudoinstructions
--use the given header and code outline to guide you
--create the code as a non-optimizing compiler would, directly from the C code, Use index
addressing, top-tested loops, etc. As directly as possible, you are to “hand compile” from C into
MIPS assembly

Use the outline of the code given below to guide you as you write your MIPS assembly language
program. In your code, you should use a header and line comments (in English). In the header,
you should state what the routine is doing, and you should list each register used and what it
contains. You should provide comments for your code to make it understandable.

40
#############################################################
## quicksort routine: sorts an array of 32-bit integers, putting them in ascending order
##
## $a0: base address of array x
## $a1: index of first element to be sorted in array (or partitioned sub-array), or
## index of first of 2 elements to be swapped
## $a2: index of last element to be sorted in array (or partitioned sub-array), or
## index of second of 2 elements to be swapped
## $s0: i
## $s1: j
## $s2: pivot
## +
## $s3: base address of array x (safe storage for input parameter in $a0)
## $s4: first (safe storage for input parameter in $a1)
## $s5: last (safe storage for input parameter in $a2)
##
## $t0, $t1: temporary storage locations for addresses and value in lw and sw operations
##
## The assembly code follows the C code in structure—there are 3 levels:
## -at the outer level: an overall if, which skips everything if there are < 2 items to sort
## -at the middle level: initializations, then a while loop, then 3 call statements
## -at the inner level: inner while 1, inner while 2 and inner if
## All together, there are 3 while loops and 2 if statements. All of these are
## top-tested in MIPS, which means that the logic of the test (since it branches out and
## doesn’t execute) must be opposite of the test logic in C (which stays in and executes).
##
#############################################################

quicksort: # entry point for the routine

## do stack pushing, to preserve values of $s-registers (since we use and change them)###
## and to preserve $ra (since quicksort is non-leaf) ###

addi $sp, $sp, -28

sw $s0, 24($sp)
sw $s1, 20($sp)
sw $s2, 16($sp)
sw $s3, 12($sp)
sw $s4, 8($sp)
sw $s5, 4($sp)
sw $ra, 0($sp)

## do the outer if test, which compares i and j. If the condition is met, the quicksort routine
## has work to do. But if i >= j, then the sorting isn’t needed, and the routine exits via Return.
## Values are moved into $s-registers here, to be preserved across the many function calls,

41
## including recursive ones.

If_outer: slt $at, $a1, $a2 # if first<last do the following code; if not,
beq $at, $0, Exit # then go to return, since sorting isn’t needed
# (equivalent to bge $a1, $a2, Exit)
add $s2, $a1, $0 # move pivot <= first
add $s0, $a1, $0 # move i  first
add $s1, $a2, $0 # move j  last
add $s3, $a0, $0 # move address of x into safe storage ($s3)
add $s4, $a1, $0 # move first into safe storage ($s4)
add $s5, $a2, $0 # move last into safe storage ($s5)

While_middle: slt $at, $s0, $s1 # while i<j do the following code
beq $at, $0, Finish_up # (equivalent to bge $s0, $s1, Finish_up)

## do first inner while loop, which gets the memory value from x[pivot] to compare with the ##
## memory value of x[i] in the first test and also compares i and last in the second test. ##
## Failing either test will cause exit from the loop. The loop body just increments i ##
## Note that x[pivot] only needs to be fetched once, and can be used also in While_inner2 ##

While_inner1: sll $t1, $s2, 2 # pivot * 4, the byte offset

add $t1, $t1, $s3 # t1 has the byte address of x[pivot]
lw $t1, 0 ($t1) # t1 has the value from x[pivot]

While_inner1A: sll $t0, $s0, 2 # i * 4, the byte offset

add $t0, $t0, $s3 # t0 has the byte address of x[i]
lw $t0, 0 ($t0) # t0 has the value from x[i]
slt $at, $t1, $t0 # 1st test: x[i] <= x[pivot]
bne $at, $0, While_inner2 # (equivalent to bgt $t0, $t1, While_inner2)
slt $at, $s0, $s5 # 2nd test: i < last
beq $at, $0, While_inner2 # (equivalent to bge $s0, $s5, While_inner2)
addi $s0, $s0, 1 # i++
j While_inner1A # end of While_inner1, goto its re-entry point
# for “top”-testing

## do second inner while loop, which gets the memory value from x[j ] to compare in the test.
## Failing the test will cause exit from the loop. The loop body just decrements j.

While_inner2: sll $t0, $s1, 2 # j * 4, the byte offset

add $t0, $t0, $s3 # t0 has the byte address of x[j]
lw $t0, 0 ($t0) # t0 has the value from x[j]
# t1 still has the value from x[pivot]
slt $at, $t1, $t0 # test: x[j] > x[pivot]
beq $at, $0, If_inner # (equivalent to ble $t0, $t1, If_inner)
addi $s1, $s1, -1 # j--

42
 j While_inner2 # end of While_inner2, goto its top for
# “top”-testing

## do inner if test, which calls swap in is body ##

## The end of this is also the end of the middle-level while, so the jump is back to its top ##

If_inner: slt $at, $s1, $s0 # test: i < j

bne $at, $0, Continue # (equivalent to bgt $s0, $s1, Continue)
add $a0, $s3, $0 # move $a0  x []
add $a1, $s0, $0 # move $a1  i
add $a2, $s1, $0 # move $a2  j
jal swap # call swap

Continue: j While_middle # this is the bottom of the middle-level while,

# so goto its top for top-testing

## Finish up the rest of the actions in the outer-if: swap, then quicksort, the quicksort again ##
## Each call is preceded by 3 moves, to get the correct values into the 3 argument registers ##
## The reason to load all 3 input arguments each time is that a-registers are NOT protected ##
## (“saved”) by the callee, and may be changed by the callee. Since swap (and quicksort ##
## which calls swap) may change a0, a1 and a2, we must not trust that “they won’t be ##
## changed” (i.e “bir sey olmaz” ) ! ##

Finish_up: addi $a0, $s3, 0 # put x[ ] into $a0

addi $a1, $s2, 0 # put pivot into $a1
addi $a2, $s1, 0 # put j into $a2
jal swap

addi $a0, $s3, 0 # put x[ ] into $a0

addi $a1, $s4, 0 # put first into $a1
addi $a2, $s1, -1 # put j-1 into $a2
jal quicksort

addi $a0, $s3, 0 # put x[ ] into $a0

addi $a1, $s1, 1 # put j+1 into $a1
addi $a2, $s5, 0 # put last into $a2
jal quicksort

## do stack popping, to restore the values of the $s-registers (since we use and change them) ##
## and to restore $ra (since calls to swap and to quicksort have changed it) ##

Exit: lw $s0, 24($sp)

lw $s1, 20($sp)
lw $s2, 16($sp)
lw $s3, 12($sp)

43
 lw $s4, 8($sp)
lw $s5, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 28
jr $ra # return to caller

Question 2 (Classwork 6 extra Spring 2013)

Write a callable MIPS routine named find_char which receives the address of the null-terminated
ASCII character string to be searched, and the ASCII code for the character to be searched for,
and returns +1 if that character is found in the string, and -1 otherwise. The routine find_char
should make repeated use of a subroutine named is_match, which takes two character codes as
inputs (in $a0 and $a1) and returns a value in $v0 telling if the two characters were the same
($v0 = 1) or different ($v0 = 0). Give the MIPS code for find_char and for is_match.

find_char: addi $sp, $sp, -12 # make room to push 3 items on stack
sw $ra, 0($sp) # push $ra, since jal changes it
sw $s0, 4($sp) # push $s0, since 1st move changes it
sw $s1, 8($sp) # push $s1, since 2nd move changes it

move $s0, $a0 # protect the pointer in $s0 register

move $s1, $a1 # protect the searched-for character
Top: lbu $t0, 0($s0) # load in the new byte (ASCII char)
beq $t0, $zero, no_match # if NULL: end of string, search fails
move $a0, $t0 # move new character into $a0
move $a1, $s1 # reload $a1 each time, since it isn’t
# protected from change by is_match
jal is_match
addi $s0, $s0, 1 # move the byte pointer to next character
beq $v0, $zero, Top # if is_match says no, go to Top of loop
# else, match is found, continue
ch_found: li $v0, 1
j pop_go

no_match: li $v0, -1 # load in -1

pop_go: lw $ra, 0($sp) # restore $ra

lw $s0, 4($sp) # restore $s0
lw $s1, 8($sp) # restore $s1
addi $sp, $sp, 12 # pop 3 items from stack
jr $ra # return to point of call

is_match: li $v0,1
beq $a0, $a1, End

44
not_match: li $v0, 0
End: jr $ra

Question 1 (Classwork 6 Spring 2013)

A. Practice writing nested loops in MIPS

a) Given the following C code with nested loops, compile it by hand into the equivalent
MIPS assembly code. Make your loops top-tested.

void nestedloops (int X, int Y) {

for (i = 1; i<= X; i++) {
for (j = Y; j>X; j--) {
body_of_inner_loop
}
}
}
Let i be put in $s0, j be put in $s1, X be passed in $a0, Y be passed in $a1

Top Tested
nestedloops: addi $s0, $zero, 1
outertop: bgt $s0, $a0, Done
addi $s1, $zero, $a1
innertop: ble $s1, $a0, End_inner
body_of_inner_loop
addi $s1, $s1, -1
j innertop
End_inner: addi $s0, $s0, 1
j outertop
Done: ...

b) Now, convert the loops from top-tested to bottom-tested loops.

Bottom Tested
nestedloops: addi $s0, $zero, 1
j outertest
outertop: addi $s1, $zero, $a1
j innertest
innertop: body_of_inner_loop
addi $s1, $s1, -1
innertest: bgt $s1, $a0, innertop
addi $s0, $s0. 1
outertest: ble $s0, $a0, outertop
Done: .

45
B. Practice converting array-index-style MIPS assembly code into pointer-style MIPS assembly
code.

Convert the MIPS assembly code given below into a more efficient pointer-style code that
executes faster. As you convert it, try to use the smallest possible number of temporary registers.
How much faster will your new code execute vs. the given code?

addi $t0, $zero, 0 # initialize index i = 0

j Test # jump to bottom-test (for first time entry to loop)
Cont: sll $t1, $t0, 2 # multiply i x 4, since data items are integers
add $t2, $t1, $a0 # add i x 4 to address of x[0] to make
# the address of x[i], in t2
lw $t3, 0 ($t2) # get x[i] into register file
add $t4, $t1, $a1 # add i x 4 to address of y[0] to make
# the address of y[i], in t4
sw $t3, 0 ($t4) # copy x[i] value to new address (i.e. do y[i] = x[i])
addi $t0, $t0, 1 # increment index i++
Test: slt $t5, $t0, $a2 # test if i < Max_Index
bne $t5, $zero, Cont # if so, continue loop with next interation
End: # if not, then leave loop and execute what follows

addi $t0, $zero, $a0 # initialize Xpointer to $a0 value

addi $t1, $zero, $a1 # initialize Ypointer to $a1 value
sll $t2, $a2, 2 # multiply Max_Index x 4, since data items are integers
add $t2, $t2, $t0 #Xmaxaddress = “ “ “ + initial Xpointer
j Test # jump to bottom-test (for first time entry to loop)

Cont: lw $t3, 0 ($t0) # get x[i] into register file

sw $t3, 0 ($t1) # copy x[i] value to new address (i.e. do y[i] = x[i])
addi $t0, $t0, 4 # increment Xpointer by 4 to next address
addi $t1, $t1, 4 # increment Ypointer by 4 to next address
Test: slt $t3, $t0, $t2 # test if Xpointer < Xmaxaddress
bne $t3, $zero, Cont # if so, continue loop with next interation
End: # if not, then leave loop and execute what follows

Only 4 temporary registers are needed:

$t0 is the X pointer
$t1 is the Y pointer
$t2 is the Xmaxaddress
$t3 is the temp for transferring the value from lw to sw, and for transferring the slt result
to beq

46
Since the loop only has 6 statements now instead of 8 (before), the loop will run 8/6 = 1.33 times
faster.

Program 1 (Problem Set 2 Spring 2013)

Write a MIPS program that gets two integer arrays from the user, computes their intersection and
outputs that intersection back for the user to read. You can assume that array sizes are fixed as 5
for first array and 7 for second array. The output should be given, then a message containing
your names and Bilkent ID numbers. Assume for simplicity that the user enters correct input (i.e.
no need for error checking).

The main program will handle the input from the terminal (including prompt messages, reading
the input, forming the values into arrays, etc), and then call the subroutine. Also, the main
program will do the output operations. Note that array sizes are 5 and 7. Integers can be positive
or negative or 0.

A MIPS subroutine handles the actual computation. It receives from the main program the
address of two arrays of integers, computes their intersection and puts these values in an array,
then returns the address of that array to the main program. This subroutine (also called routine,
procedure, method, function) must follow the MIPS convention for register usage (see p. 115 of
the textbook and other possible related sections). In particular, if you use any of the 12 “saved”
registers ($s0-$s7, $fp, $gp, $sp, and $ra), you must ensure that they are returned to the caller
with exactly the same values that were received at the time of call. [Hint: the intersection is
much easier to find if the arrays are sorted.]

47
Example of terminal input and output:
Welcome to our program (AA and ZZ  ).

Please enter your inputs for array 1 (5 integers) followed by the Enter key.

Please enter your inputs for array 2 (7 integers) followed by the Enter key.

10

Here is intersection of the two input arrays: 3 5 7

This program was created by Ali Aydın and Ziya Zafer. We hope you liked it, and
will use it often  . Iyi günler !

Solution:

.data
first: .word 0 : 5
second: .word 0 : 7
result: .word 0 : 5 #max 5 integer can be common

48
fSize: .word 5
sSize: .word 7

start: .asciiz "Welcome to our program (AA and ZZ :) ). \n"

f_pro: .asciiz "Please enter your inputs for array 1 (5 integers) followed by the Enter key.\n"
s_pro: .asciiz "Please enter your inputs for array 2 (7 integers) followed by the Enter key.\n"
p_pro: .asciiz "\nHere is intersection of the two input arrays: "
space: .asciiz " "
end: .asciiz "\This program was created by Ali Aydın and Ziya Zafer. We hope you liked it,
and will use it often :) . Iyi günler !"

.text

main: sub $sp,$sp,24 # save registers on stack

sw $s0,0($sp)
sw $s1,4($sp)
sw $s2,8($sp)
sw $s3,12($sp)
sw $s4,16($sp)
sw $s5,20($sp)

la $a0,start
li $v0,4
syscall

#-------------------------1-------------------------------#

la $a0,f_pro #load the address of "f_pro" string

li $v0,4
syscall

la $t5, fSize
lw $t5, 0($t5) #loading value from the address

la $s0, first

addi $t0, $zero, 0 #reset t0

j TestF
SFir: sll $t1, $t0, 2
add $t2, $s0, $t1

li $v0,5 # syscall 5 reads an integer

49
 syscall
sw $v0, 0($t2)

addi $t0, $t0, 1

TestF: blt $t0, $t5, SFir #to ask only for 5 integers(checks the current index).
# blt checks if value of $t0 is less than the value of $t5.
# If it is, it jumps back to the SFir adress,
# else it keeps going downwards

#-------------------------2-------------------------------#

addi $t0, $zero, 0 #reset t0

la $a0,s_pro
li $v0,4
syscall

la $t5, sSize
lw $t5, 0($t5) #loading value from the address

la $s1, second

j TestS

SSec: sll $t1, $t0, 2

add $t2, $s1, $t1

li $v0,5 # syscall 5 reads an integer

syscall
sw $v0, 0($t2)

addi $t0, $t0, 1

TestS: blt $t0, $t5, SSec #to ask only for 7 integers(checks current index)

#--------------CONTROL--PART-----------------#

addi $t0, $zero, 0

addi $t4, $zero, 0

la $a2, fSize
lw $a2, 0($a2) #loading value from the address

la $a1, sSize
lw $a1, 0($a1) #loading value from the address

50
 la $s2, result

j TestC1
c1: sll $t1, $t0, 2
add $t2, $s0, $t1
lw $t3, 0($t2)

addi $t4, $zero, 0

j TestC2
c2: sll $t5, $t4, 2
add $t6, $s1, $t5
lw $t7, 0($t6)
beq $t3, $t7, found #if a common is integer found, jump to "found" address

addi $t4, $t4, 1

TestC2: blt $t4, $a1, c2 #to pass to next index of second array
addi $t0, $t0, 1
j TestC1
found: sll $s4, $s3, 2
add $s5, $s4, $s2
sw $t7 0($s5)
addi $t0, $t0, 1
addi $s3, $s3, 1
TestC1: blt $t0, $a2, c1 #to pass to next index of first array

#------------------print------------------#

addi $t0, $zero, 0

la $a0,p_pro
li $v0,4
syscall

j TestP
print: sll $t1, $t0, 2
add $t2, $s2, $t1
lw $t3, 0($t2)
la $a0, ($t3)
li $v0,1
syscall
addi $t0, $t0, 1
la $a0,space
li $v0,4
syscall

51
TestP: blt $t0, $s3, print #checks whether there are more integers to print out

la $a0,end
li $v0,4
syscall

lw $s0,0($sp) # restore registers

lw $s1,4($sp)
lw $s2,8($sp)
lw $s3,12($sp)
lw $s4,16($sp)
lw $s5,20($sp)
add $sp,$sp,24

li $v0,10 # return to system at end of main program

syscall # bye bye !

Question 2 (Problem Set 4 Spring 2013)

Write the MIPS code which corresponds to the following C code. Let x be in $f0 & $f1, let y be
in $f30 & $f31.

double x, y;
int i;
for (i=0; i<10; i++)
{
if (x>y)
x=x-y;
else
x=x+y;
}
x=x*y;

Solution:

li $t0, 0 # initialize i to 0 in for loop (assume i uses $t0)

Loop: # body of the for loop starts here
c.gt.d $f0, $f30 # compare the two double precision values
bc1f Else # if x is not greater than y, go to the else part
sub.d $f0, $f0, $f30 # if x > y, then do the double precision FP subtraction
j LoopCheck # then go to the loop increment and loop bottom-test
Else:
add.d $f0, $f0, $f30 # the else-part is the double precision FP addition
LoopCheck: # the loop increment and bottom-test parts begin here

52
 addi $t0, $t0, 1 # increment i, the loop counter
slti $t1, $t0, 10 # this and the next instruction together make the i < 10 test
bne $t1, $zero, Loop # if i<10 we repeat the loop

mul.d $f0, $f0, $f30 # once finished with the loop, we multiply x * y

Question 2 (Problem Set 3 Spring 2013)

Translate the following C routines to MIPS assembly language. Write the MIPS code in the
boxes provided. Use only real MIPS instructions in your code, but put an asterisk * next to lines
where pseudoinstructions would either make the code easier to write, or easier to understand.

int isBigger (int a, int b){

return funcB(a, b)
}

int funcB(int c, int d){

if (c > d)
return c;
else
return -1;
}

#################################################
# isBigger is called with a in $a0 and b in $a1
# its result value is returned in $v0
# $sp contains stack pointer
# $ra contains return address
##################################################
isBigger:
* addi $sp, $sp, -4
* sw $ra, 0($sp) # must push $ra, since this is a non-leaf procedure
jal functB
* lw $ra, 0($sp) # need to pop and restore $ra before return since it was
# changed by jal call
* addi $sp, $sp, 4
jr $ra
[push and pop pseudo-instructions would be helpful ]
#################################################
# functB is called with c in $a0 and d in $a1
# its result value is returned in $v0
# $at contains temporary value used by the assembler
# $ra contains return address
##################################################
53
functB:
* slt $at, $a1, $a0
* bne $at, $zero, put_c # d < c means c > d, so take the branch to put_c
* addi $v0, $zero, -1 # else put -1 and return
jr $ra

put_c:
* add $v0, $zero, $a0 # put c and return
jr $ra
[bgt, li, and move pseudo-instructions would be helpful ]

Question 2 (Problem Set 2 Spring 2013)

Convert the following code segment into MIPS assembly language. Your loop should be
optimized for fast performance (Hint: use bottom-testing and pointer-addressing)

int min = a[0] //beginning address of the array a is given in $a0

for (int i=1; i<size; i++) // size is given in $a1
if(min > a[i])
min = a[i]

Direct Translation (unoptimized):

##############################################################
## ##
## Registers used: ##
## $a0 contains the beginning address of array ##
## $a1 contains the size of array(at the beginning) ##
## then contains size x 4, as part of the calculation ##
## $t0 contains current minimum element ##
## $t1 contains the pointer to the current array location ##
## $t2 contains the current element of the array at location $t1 ##
##############################################################

sll $a1, $a1, 2

add $a1, $a0, $a1

lw $t0, 0($a0)
addi $t1,$zero,1
Top: bge $t1,$a1,Done
sll $t2, $t1, 2
add $t2, $a0, $t2
lw $t2, 0($t2)
ble $t0, $t2, Skip
move $t0, $t2

54
Skip: addi $t1, $t1, 1
j Top
Done: …

Optimized Version:
##############################################################
## ##
## Registers used: ##
## $a0 contains the beginning address of array ##
## $a1 contains the size of array(at the beginning) ##
## then contains size x 4, as part of the calculation ##
## $t0 contains current minimum element ##
## $t1 contains the pointer to the current array location ##
## $t2 contains the current element of the array at location $t1 ##
##############################################################

lw $t0, 0($a0)
sll $a1, $a1, 2
add $a1, $a0, $a1
move $t1, $a0
j Skip
Top: lw $t2, 0($t1)
ble $t0,$t2, Skip
move $t0, $t2 // min <-a[i]
Skip: addi $t1,$t1,4
blt $t1, $a1, Top // i<size

The un-optimized solution has 8 instructions in the loop, but the optimized version has only 5.
The j Top instruction is saved by converting to bottom testing, and 2 instructions are saved by
converting to pointer addressing (since pointer = pointer + 4 does the work of 3 instructions: a
shift to multiply the index by 4, an addition to add base + 4*i to get the address, and i = i + 1 to
increment the index).

Program 1 (Problem Set 1 Spring 2013)

A special sequence of numbers is defined as follows. The first two numbers in the sequence are 0
and 1, and each subsequent number is 4 times the previous number minus the one before that.
In other words, let Ax be the x-th number in sequence. Then,

Ax = (4 × Ax-1) - Ax-2

The sequence is: 0, 1, 4, 15, 56, 209, 780, 2911…

55
Write a program that calculates the x-th number in the sequence. The program asks the user for
the value of x. If the value of x is smaller than 1, the program asks the user to enter a number
greater than 0. After calculating the x-th number in sequence, your program prints the result
along with both your names, surnames and Bilkent IDs. (For example: “the 6 th number in the
sequence is 209 -- Ali Aytek 12345678 and Bora Bilgin 87654321”.) You may assume that user
enters only integers. (This is for simplicity—so there is no need to check for floating point
numbers).

Solution:
.data
aseq:.word 0 : 15 # "array" of words to contain numbers

prompt: .asciiz "Enter x (x <= 15)"

result1: .asciiz "In position "
result2: .asciiz ", the value is "
result3: .asciiz " -- Cagdas Cengiz 20000000"
.text

main: # assume value a is already in $t0, b in $t1

la $a0, prompt # load address of prompt for syscall
li $v0, 4 # specify Print String service
syscall # print the prompt string
li $v0, 5 # specify Read Integer service
syscall # Read the number. After this #instruction, the number
# read is in $v0.
add $s5, $v0, $0 # transfer the number to the desired #register, $s5
add $a0, $s5, $0 # argument to the procedure
ble $s5, $zero, main # check boundary on user input -- if #invalid, restart

la $t0, aseq # load address of array

li $t2, 0 # 0 is the first number in sequence
sw $t2, 0($t0) # A[0] = 0
li $t2, 1 # 1 is the second number in sequence
sw $t2, 4($t0) # A[1] = 1
beq $a0, 1, ret # if x = 1
beq $a0, 2, ret # if x = 2
addi $t1, $a0, -2 # counter for loop, will execute (size-2) times

# Loop to compute each number in sequence using the previous two numbers.

loop: lw $t4, 0($t0) # get value from array A[n-2]

lw $t5, 4($t0) # get value from array A[n-1]
sll $t5, $t5, 2 # A[n-1] = A[n-1] * 4
sub $t2, $t5, $t4 # A[n] = A[n-1] - A[n-2]
sw $t2, 8($t0) # store newly computed A[n] in array

56
 addi $t0, $t0, 4 # increment address to now-known number storage
addi $t1, $t1, -1 # decrement loop counter
bgtz $t1, loop # repeat while not finished

ret: la $t5, aseq

la $a0, result1 # load address of result1 for syscall

li $v0, 4 # specify Print String service
syscall # print the prompt string

add $a0, $0, $s5 # put x in $a0

li $v0, 1 # specify Print Integer service
syscall

la $a0, result2 # load address of result2 for syscall

li $v0, 4 # specify Print String service
syscall # print the prompt string

subi $t6, $s5, 1 # to calculate the offset of the last element of the array
sll $t6, $t6, 2 # multiply by 4
add $t5, $t5, $t6 # add beginning address and the offset
lw $a0, 0($t5) # get the last value from array
beq $s5, 1, one # if x = 1, we should load s0 with zero offset

prnt: li $v0, 1 # specify Print Integer service

syscall

la $a0, result3 # load address of result3 for syscall

li $v0, 4 # specify Print String service
syscall # print the prompt string

end:
li $v0, 10
syscall # bye

one: lw $a0, 0($s0) # special condition for x = 1

b prnt

Program 2 (Problem Set 1 Spring 2013)

Write a program similar to Program 1, including error-checking on the input value. But this time,
take the x value in the main program and then pass x value to a procedure. The called procedure
calculates the first x numbers in the sequence and writes them to an array in memory. After that,
57
the procedure returns the beginning address of the array to the main program. The main program
then accesses the x-th element of the array and prints it out, with both your names, surnames and
Bilkent IDs. (For example: “In position 8, the value is 2911 -- Ali Aytek 12345678 and Bora
Bilgin 87654321”.) You may assume that user enters only integers. (This is for simplicity—so
there is no need to check for floating point numbers). Please follow the MIPS convention for
writing procedures (see p. 115 of the textbook and other related sections). In particular, you
must preserve the value of the $s registers, and the $fp, $gp, $sp, and $ra registers in any called
procedure, so that they are returned to the caller with exactly the same values that were received
at the time of call.

Solution
.data
aseq:.word 0 : 15 # "array" of words to contain numbers

prompt: .asciiz "Enter x (x <= 15)"

result1: .asciiz "In position "
result2: .asciiz ", the value is "
result3: .asciiz " -- Cagdas Cengiz 20000000"
.text

main: # assume value a is already in $t0, b in $t1

la $a0, prompt # load address of prompt for syscall
li $v0, 4 # specify Print String service
syscall # print the prompt string
li $v0, 5 # specify Read Integer service
syscall # Read the number. After this instruction, the number read is in $v0.
add $s5, $v0, $0 # transfer the number to the desired register, $s5
add $a0, $s5, $0 # argument to the procedure
ble $s5, $zero, main # Check boundary on user input -- if invalid, restart
jal proc

add $t5, $v0, $0 # proc returned the beginning address of the array
la $a0, result1 # load address of result1 for syscall
li $v0, 4 # specify Print String service
syscall # print the prompt string

add $a0, $0, $s5 # put x in $a0

li $v0, 1 # specify Print Integer service
syscall

la $a0, result2 # load address of result2 for syscall

li $v0, 4 # specify Print String service
syscall # print the prompt string

58
 subi $t6, $s5, 1 # to calculate the offset of the last element of the array
sll $t6, $t6, 2 # multiply by 4
add $t5, $t5, $t6 # add beginning address and the offset
lw $a0, 0($t5) # Get the last value from array
beq $s5, 1, one # if x = 1, we should load s0 with zero offset

prnt: li $v0, 1 # specify Print Integer service

syscall

la $a0, result3 # load address of result3 for syscall

li $v0, 4 # specify Print String service
syscall # print the prompt string

end:
li $v0, 10
syscall # bye

one: lw $a0, 0($s0) # special condition for x = 1

b prnt

proc:
addi $sp,$sp,-4 # moving stack pointer
sw $t3, 0($sp) # store previous value

# Procedure Body
la $t0, aseq # load address of array
li $t2, 0 # 0 is the first number in sequence
sw $t2, 0($t0) # A[0] = 0
li $t2, 1 # 1 is the second number in sequence
sw $t2, 4($t0) # A[1] = 1
beq $a0, 1, ret # if x = 1
beq $a0, 2, ret # if x = 2
addi $t1, $a0, -2 # counter for loop, will execute (size-2) times

# Loop to compute each number in sequence using the previous two numbers.

loop: lw $t4, 0($t0) # Get value from array A[n-2]

lw $t5, 4($t0) # Get value from array A[n-1]
sll $t5, $t5, 2 # A[n-1] = A[n-1] * 4
sub $t2, $t5, $t4 # A[n] = A[n-1] - A[n-2]
sw $t2, 8($t0) # Store newly computed A[n] in array
addi $t0, $t0, 4 # increment address to now-known number storage
addi $t1, $t1, -1 # decrement loop counter
bgtz $t1, loop # repeat while not finished
la $v0, aseq

59
ret: lw $t3, 0($sp) # load previous value
addi $sp,$sp,4 # moving stack pointer
jr $ra # return (copy $ra to PC)

Question 2c (Problem Set 1 Spring 2013)

c) Write a short MIPS program which computes the following. If A+B is

greater than C, then A is set to C+45. If not, then D takes the value of A+B. Let C and D be
register variables, in $s2 and $s3. Let A and B be memory variables, with their addresses in $s0
and $s1.

Since no restriction was made on the use of pseudoinstructions, we are free to use them. The
most useful one will be ble regX, regY, Target (branch less than or equal). [Without using
pseudoinstructions, this can be implemented with slt $t0, regY, regX followed by beq $t0, $zero,
Target]

Remembering that in HLL“if (A + B> C)” must be implemented in assembly as ble A+B, C,
Else , we write

lw $t0, 0($s0) // get A from memory into register t0

lw $t1, 0($s1) // get B from memory into register t1
add $t1, $t0, $t1 // put A + B into register t1
ble $t1, $s2 , Else // test if A+B is > C
addi $t0, $s2, 45 // if it is, make t0 = C + 45
sw $t0, 0($s0) // put t0 into A, in memory
j Devam // skip over the else clause
Else: move $s3, $t1 // Else: D gets value of A + B (still in t1)
Devam: . . . // code continues from here

60