Understanding MIPS while Loops

Question

Given the traditional while loop in C:

while(save[i] == k)
     i += 1;

The answer in MIPS is such:

The first step is to load save[i] into a temporary register. Before we can load save[i] into a temporary register, we need to have its address. Before we can add i to the base of array save to form the address, we must multiply the index i by 4 due to the byte addressing problem. Fortunately, we can use shift left logical, since shift ing left by 2 bits multiplies by 22 or 4 (see page 88 in the prior section). We need to add the label Loop to it so that we can branch back to that instruction at the end of the loop:

Loop: sll $t1,$s3,2 # Temp reg $t1 = i * 4

To get the address of save[i], we need to add $t1 and the base of save in $s6:

add $t1,$t1,$s6 # $t1 = address of save[i]

Now we can use that address to load save[i] into a temporary register:

lw $t0,0($t1) # Temp reg $t0 = save[i]

The next instruction performs the loop test, exiting if save[i] ≠ k:

bne $t0,$s5, Exit # go to Exit if save[i] ≠ k

Then

addi $s3, $s3, 1 #i = i+1
j Loop # go to Loop
Exit: 

Still with this explanation, I still can't quite get it.

1. I don't understand why we have to shift left by 2 bits. I don't understand the purpose of shift left/right logical, and I can't relate the explanations online to practice problems and examples.

2. Because I don't even get step 1, I don't get step 2, which is adding the result of the shifting ($t1) and the base of save in $s6.

Basically, I need explanation of this problem because even with the answers I can't quite get it. I really need a simple (dumbed down) explanation that would clearly explain every step and why this is done so. PLEASE and thank you!

Answer 1

Imagine you have data starting at an temp address value:

temp address V
             | ValueA | ValueB | ValuesC  |
Byte  offset  0  1 2 3  4 5 6 7  8 9 10 11
Array index   0         1        2

This is assuming that each 'element' is an integer that is 4 bytes in length.

When getting the address of the start of an element, you can see it is multiples of 4

MIPS doesn't care what is at the address (in terms of sizes), so you need to handle that yourself.

So the address of the 1st element is at tempaddress+0, the second element is at tempaddress+(1*4) etc.

Or, when making it more generic, element X is at temp address + (X*4)

X*4 is the same as shifting X left by 2.

I.e.: if X was the value 1 in binary, that is 0000 0001

Shifted left by 2, that is 0000 0100 or in decimal 4.

if X was the value 3 in binary, that is 0000 0011

Shifted left by 2, that is 0000 1100 or in decimal 12.