C-Code to MIPS Assembly

Question

I was trying to convert C code to MIPS assembly. There are these two following C code snippets. The problem is that my solution differs from the standard solution. Also, I don't understand the standard solution. I hoped, someone could explain me the two following mips assembly code snippets.

First of all some additional information for the task. Only the following MIPS instructions are allowed: lw, add, beq, bne and j.
The register:
$s3 contains i
$s4 contains j
$s5 contains k
A is an array of 32-Bit-Integer and the initial address of A is in $s6
$t0 and $t1 can be used for storing temporary variables

The first one is a simple do-while loop:

do {
    i = i + j;
} while(A[i] == k);

MIPS Assembly

loop: add $s3, $s3, $s4   // this is i = i+j
      add $t1, $s3, $s3  // from now on
      add $t1, $t1, $t1  // I cant follow anymore
      add $t1, $t1, $s6  // What happens in these three lines?
      lw  $t0, 0($t1)    // 0($t1) is new for me. What does this zero do?
      beq $t0, $s5, loop

Now the second C code:

if ( i == j )
    i = i + A[k];
else if( i == k )
    i = i + A[j];
else
   i = i + k;

Here is the MIPS assembly code:

       bne $s3, $s4, Else1  // this line is if(i==j)
       add $t1, $s5, $s5   // from here on
       add $t1, $t1, $t1   // till
       add $t1, $t1, $s6  // 
       lw  $t0, 0($t1)    //
       add $s3, $s3, $t0  // here I don't understand
       j done
ELSE1: bne $s3, $s5, Else2  // this line is if(i==k)
       add $t1, $s4, $s4   // The same game as above
       add $t1, $t1, $t1
       add $t1, $t1, $s6
       lw  $t0, 0($t1)
       add $s3, $s3, $t0  // till here
       j done
ELSE2: add $s3, $s4, $s5

Could anyone explain me what really goes on? That would be very helpful

Answer 1

O.k. the most interesting and not-understandable piece of code is the following:add $t1,

add $t1, $s5, $s5
add $t1, $t1, $t1
add $t1, $t1, $s6

this code multiplies $s5 by four, and stores it in $t1, then adds to $t1 $s6. That is equivalent to:

$t1 = A[k]

after you understand this, the code looks much clearer.

about the lw $t0, 0($t1):

you can use an offset point in the address. Here the offset is 0.

Answer 2

lw is load. The mode here is indirect addressing, the most common is:

lw $t2, ($t0)

But you can also include a byte offset,

lw $t2, 4($t0)   # load word at RAM address ($t0 + 4) into register $t2

The compiler is just putting the 0 placeholder in the non-offset version.

So, to load A[i] you need to do two things. Take the base address of A[] and then add i times the sizeof(A[0]). I am guessing that the values in A are 32 bit.

add $t1, $s3, $s3

$t1 = j + j or 2 * j

add $t1, $t1, $t1

$t1 = $t1 + $t1 or j +j +j +j or 4 * j

So why did it do it this way? Well, doing a straight multiply is slow in terms of clock cycles. The next choice would be a shift operation, but in this case, the compiler designers decided that two adds beat a shift.

add $t1, $t1, $s6

I would guess that $s6 is the base address of A[]. So ultimately '$t1 = A[] + 4 * j`