MIPS Control Instruction: Summing the first ten integers
Lets understand mips control instruction by examples. Followings are the MIPS control instructions. There are two types of MIPS control instructions.
- Branch instruction: These are conditional mips control instructions. These instructions includes branch if equal to, branch if greater than, branch if less than instruction. I will explain them through examples in later part of this article.
- Jump instructions : These are unconditional mips control instructions.
In this example, I will be using both branch and jump instructions. The following code sums the first ten positive integers (10+9+8+7+…), Figure out the missing parts in the code, fill them up and run the program. Use only the registers mentioned in this program, i.e., $s0, $t0, $zero.
Exercise 1
Code:
.text .globl main main: addi $s0, $zero, 10 # counter initialized to 10 addi $t0, $zero, 0 # sum/accumulator initialized to 0 loop1: # fill missing values add $t0, $t0, $s0 # Performing accumulation in $t0 addi $s0, $s0, -1 # counter−− bne $s0, $zero, loop1 # Exit the loop after 10th iteration nop # Few no operations to indicate end of interest nop
What is the value of $t0? Hex: 0x00000037, Decimal: 55 when we reach the end of the program (first nop).
Exercise 2
Modify the program in Exercise 1 to calculate (1+2+4+8+16+32+….), for the first 20 numbers. Write your code below; store the value of the sum in $t0. Use the registers mentioned before in Exercise-1, i.e., $s0, $t0, $zero. In addition to these registers, you can only use $t1. Store the final (and intermediate) sum in $t0. Multiple implementations are possible. Write only one.
There can be two implementations. Both are given below.
Implementation 1:
.text .globl main main: addi $s0, $zero, 20 # counter initialized to 20 addi $t0, $zero, 0 # sum/accumulator initialized to 0 addi $t1, $zero, 1 # $t1 initialized with “1” loop1: add $t0, $t0, $t1 # Performing accumulation is $t0 add $t1, $t1, $t1 # Calculating new number to be added addi $s0, $s0, -1 # counter−− bne $s0, $zero, loop1 # Exit the loop after 20th iteration nop nop
The program above calculated the sum of 20 numbers. What is the value of the final sum Hex: 0x000fffff; Decimal: 1048575
Implementation 2:
.text .globl main main: addi $s0, $zero, 20 # counter initialized to 20 addi $t0, $zero, 0 # sum/accumulator initialized to 0 addi $t1, $zero, 1 # $t1 initialized with “1” loop1: add $t0, $t0, $t1 # Performing accumulation is $t0 sll $t1, $t1, 1 # Calculating new number to be added addi $s0, $s0, -1 # counter−− bne $s0, $zero, loop1 # Exit the loop after 20th iteration nop nop
The program above calculated the sum of 20 numbers. What is the value of the final sum Hex: 0x000fffff; Decimal: 1048575
Modify the above programs and do as directed (Explanation for both implementations given separately)
Solution for Implementation 1:
Modify the program to calculate the sum of more numbers (say 50 numbers). What is the value of the intermediate sum contained in $t0 when an overflow occurs in any of the registers involved:Hex: 0x7fffffff, How do you know it has overflown? At this point we get an exception caused due to an arithmetic overflow. However, the overflow was not caused by the intermediate sum but by the new number obtained by the instruction (add $t1, $t1, $t1), note that this command is doing a signed addition. When $t1 has 0x40000000 (at which point sum is 0x7fffffff), the instruction just mentioned would try to put 0x80000000 into $t1, however this would mean that the signed bit (MSB) would be set to 1 which is not possible when two positive numbers are added. Hence the program will suffer an exception caused by an arithmetic overflow into the signed bit and would jump to the kernel part of the code.
Repeat the above program (of the same 50 numbers) but this time use the addu instruction while calculating the sum instead of the add instruction. Now what is the first value of the intermediate sum for which overflow occurs in any of the registers involved:Hex: 0xffffffff (which in this case is a positive number due to unsigned addition), the overflow is caused by the new number obtained by the instruction (addu $t1, $t1, $t1) because it’s value becomes 0x100000000 which cannot be accommodated in the 32 bit space. At this point the value in $t1 becomes zero and the register $t0 contains 0xffffffff for the rest of the program. Does the overflow occur at the same point? If it does not, then why not? No it does not occur at the same point. In the signed addition case an arithmetic overflow into the signed bit of register $t1 caused an exception whereas in the unsigned addition case an exception was not caused but overflow did occur in $t1 because it ran out of space. However, this occurred at a comparatively different point as compared to the signed case.
Solution for Implementation 2:
Modify the program to calculate the sum of more numbers (say 50 numbers). What is the value of the intermediate sum contained in $t0 when an overflow occurs in any of the registers involved:Hex: 0xffffffff, How do you know it has overflown? The instruction add $t0, $t0, $t1 performs the signed accumulation while the instruction (sll $t1, $t1, 1) creates the new number to be added on each iteration. A point comes when register $t1 contains 0x40000000 (at which point $t0 contains 0x7fffffff). At this point the shift left logical instruction performs a left shift and the number 0x80000000 is placed in $t1. Although the signed bit is set to 1 in this case but this is perfectly legal since the shift operation is a logical operation (not an arithmetic operation) and it treats the signed bit as any other bit. However, the instruction (add $t0, $t0, $t1) now treats 0x80000000 as a negative number (−214748364810) since it performs signed addition and adds this number to 0x7fffffff (214748364710) which results in 0xffffffff (-110).
On the next left shift the number 0x80000000 becomes 0x100000000 which cannot be accommodated in a 32 bit space and hence we see 0x00000000 in $t1. This can be classified as a logical overflow beyond the available 32 bit space. The contents of $t0 at this point are 0xffffffff. The same value remains in $t0 till the end of the program. Thus, it must be seen that no exception occurred although the final addition before logical overflow was in contrast to the theme of the program. The programmer needs to be careful while doing assembly language programming and he/she must keep the characteristics and limitations of the underlying architecture in mind.Repeat the above program (of the same 50 numbers) but this time use the addu instruction while calculating the sum instead of the add instruction. Now what is the first value of the intermediate sum for which overflow occurs in any of the registers involved:
Hex: 0xffffffff, The instruction (addu $t0, $t0, $t1) performs the unsigned accumulation while the instruction (sll $t1, $t1, 1) creates the new number to be added on each iteration. A point comes when register $t1 contains 0x40000000 (at which point $t0 contains 0x7fffffff). At this point the shift left logical instruction performs a left shift and the number 0x80000000 is placed in $t1. Although the signed bit is set to 1 in this case but this is perfectly legal since the shift operation is a logical operation (not an arithmetic operation) and it treats the signed bit as any other bit. The instruction (addu $t0, $t0, $t1) now treats 0x80000000 as a positive number (214748364810) since it performs unsigned addition and adds this number to 0x7fffffff (214748364710) which results in 0xffffffff (429496729510) which in this case is a positive number due to unsigned addition. On the next left shift the number 0x80000000 becomes 0x100000000 which cannot be accommodated in a 32 bit space and hence we see 0x00000000 in $t1. This can be classified as a logical overflow beyond the available 32 bit space. The contents of $t0 at this point are 0xffffffff. The same value remains in $t0 till the end of the program. Does the overflow occur at the same point? If it does not, then why not? Yes it occurs at the same point as before (in both cases: logical overflow beyond the register capacity occurred at the same point). Show the programs to the TA
Exercise 3
Without using branches, write a program that sums the integers in an array of 5 elements and then saves the result in “sum”. The starting code is given below:
Code:
.data # This is how data is initialized in PCSpim myData: .word 2, 12, -5, 7, 4 # array initialization sum: .word 0 # this will contain the sum .text .globl main main: la $s0, myData #load address of myData into $s0 li $t2, 0 #initialize $t2 to save the sum lw $t0, 0($s0) add $t2, $t2, $t0 lw $t0, 4($s0) add $t2, $t2, $t0 lw $t0, 8($s0) add $t2, $t2, $t0 lw $t0, 12($s0) add $t2, $t2, $t0 lw $t0, 16($s0) add $t2, $t2, $t0 la $s0, sum #Load the address of “sum” into $s0 sw $t2, 0($s0) #Store the value of final sum in $t2 to the #memory location at “sum”
After completing Exercise 3 fill the following blanks:
- What is the value of sum (in $t2 and stored in memory at location “sum”) after running this program Hex: 0x00000014; Decimal: 20
- Observe the data segment and write the address of myData (hex): 0x10010000
- What is the address of the first element of the array in the data segment: 0x10010000
- What is the address of the third element of the array in the data segment: 0x10010008
- The value stored at the above address (Hex) 0xfffffffb (Decimal): −5
- Observe how INT variables are stored in data area, what format are they stored in: word
- Check that after you run the first instruction of the program, $s0 is indeed loaded with the correct address of the array myData using the special assembler generated instruction. We may not discuss la (load address instruction) any further.
- What address is loaded for sum in $s0 at the end of the program 0x10010014
- Fill up the missing values in the following table:
| Address (Hex) | Value (Hex) | Value (Decimal) |
| 0x10010000 | 0x00000002 | 2 |
| 0x10010004 | 0x0000000c | 12 |
| 0x10010008 | 0xfffffffb | -5 |
| 0x1001000c | 0x00000007 | 7 |
| 0x10010010 | 0x00000004 | 4 |
Exercise 4
Repeat Exercise 3 above but this time use branch instruction(s) and the following 15 element array.
Code:
.data myData: .word 200, -1299, -5000, 7123, 4, -2, 3, -7, 89, 4, -1000, 11, 0, 14, -1 sum: .word 0 # this location will contain the sum .text .globl main main: la $s0, myData # load address of myData into $s0 li $t1, 15 # initialize the index add $t2, $zero, $zero # initialize to save the sum in $t2 loop: addi $t1, $t1, -1 sll $t3, $t1, 2 add $t3, $s0, $t3 lw $t0, 0($t3) add $t2, $t2, $t0 bne $t1, $zero, loop exit: la $s0, sum #Load the address of “sum” into $s0 sw $t2, 0($s0) #Store the value of the final sum to memory
What is the value of sum Hex: 0x0000008b; Decimal: 139
What branch instruction is produced by the assembler? bne $9, $0, −20