How to convert a high level language statement involving arrays into MIPS 32 bit?

Question

Here's the high-level function: J[6] = K[d-e]

d = $t0, e = $t1, J = $s1, K = $s2, final result goes in $s4

So far I have:

lw $t2, 24($s1) #Load J[6] into $t2
sub $t3, $t0, $t1 #Subtract e from d to $t3

What I know I can't do is lw $t4, $t3($s2) but I'm not sure how to translate K[$t0 - $t1].

Answer 1

To start: to translate this statement into assembly,

J[6] = K[d-e];

first, let's look at it in Three Address Code, which requires us to tease out the direction and order of the smaller operations:

x1 = d-e             # store subt
x2 = x1 * 4          # scaling by element size
x3 = K + x2          # byte address pointer arithmetic
x4 = *x3             # dereference to fetch K[d-e]
x5 = J + 24          # compute byte address of J[6]
*x5 = x4             # store into J[6] the value of K[d-e]

(Note that three address code never reuses temporary variables, though in the MIPS equivalent, that would be common to reuse/repurpose registers for temporary results (when the old temp value is no longer needed)).

Also MIPS can do the J[6]= without separately computing J+24, so x5 does not have to be computed.

The * operation, the C operator known as dereference, when it occurs on the right hand side of = assignment, it is done as a load instruction to fetch data from memory.  When it appears on the left hand side of an = assignment, that is done as a store instruction to store data into memory.

---

Next, let's look at the address computations and what MIPS can and cannot do.

You have the right idea with $t3($s2), but MIPS cannot do that.  It can only do constant indexing.

So, what does $t3($s2) represent?  It is the combination of a dynamic index with a base address, that results in an elemental address.

In this (not supported form) $t3($s2), how would these two values, $t3 and $t2, be combined?  By addition: we can add an index to a pointer and get a new pointer.

However, because MIPS is a byte addressable machine, addresses & pointers in MIPS refer to individual bytes.  A byte is an 8-bit datum.  So, when we use pointers and address on such a machine, these the type of such addresses and pointers is byte addresses.

When we use 32-bit words, these occupy multiple bytes, 4 x 8-bit bytes in fact for a 32-bit word.  When a 32-bit is the element of an array that word occupies 4 bytes, each of which has its own byte address, so it occupies 4 byte addresses as well.

Similar to how the whole array is sometimes referred to by the address of where it starts (its index 0), a whole element (4 bytes) is referred to by the address of its lowest byte.  To move from one element to the next, means moving by 4 byte addresses.

So, given an index, we have convert that index into a byte offset, which in this context, is called scaling.  The scale factor is the same as the size of the elements in the array, here an integer array, so 4 bytes per element.  The scale factor is thus 4.

So, what we want is more like $t3*4($s2), but of course MIPS cannot do this either.  But using separate instructions, MIPS can multiply by 4, and MIPS can also add dynamic values together.  Once these are done, we can use the constant coefficient dereference form that MIPS does provide — with the additive identity, since we have already computed the complete address.

---

There are two ways to do: K[i+1]:

1. Add i and 1, then multiply that result by 4, then add K and use zero for the offset in a load or store instruction.

2. Multiply i by 4, then add K and use 4 for the offset in the store instruction.

Form 2 uses a non-zero offset value of 4, which is the +1 scaled by *4.  This happens to be 1 instruction shorter than solution 1.

---

How to multiply by a small constant like 4, let's say the number to multiply is in $t0, and the result is desired to be in $t1:

1. Add number to itself 4 times, using the target to accumulate the result:

    add $t1, $t0, $t0     # t1 = t0 + t0 = t0 * 2
    add $t1, $t1, $t0     # t1 = t1 + t0 = t0 * 3
    add $t1, $t1, $t0     # t1 = t1 + t0 = t0 * 4

2. Add number to itself once, then add that number to itself once

    add $t1, $t0, $t0     # t1 = t0 + t0 = t0 * 2
    add $t1, $t1, $t1     # t1 = t1 + t1 = t0 * 2 + t0 * 2 = t0 * 4

3. Shift the number left by 2 (binary) places

    sll $t1, $t0, 2       # t1 = t0 << 2 = t0 * 4

Answer 2

This is just me working out my own homework problem with the help of advice from commenters. Earlier revisions of this answer included a wrong version that loaded from J[6] instead of storing and overuse of temps.

This is the pseudo-code:

x1 = d-e             # store subtraction
x2 = x1 * 4          # scaling by element size
x3 = K + x2          # byte address pointer arithmetic

x4 = *x3             # dereference to fetch K[d-e]
x5 = J + 24          # compute byte address of J[6]
*x5 = x4             # store into J[6] the value of K[d-e]

This is the attempted implementation, the only issue is the last two steps, in the question it specifies $s4 to hold the final answer, but J[6] still needs to be overwritten because that's the assignment statement:

sub $t3, $t0, $t1  #Subtract d-e to $t3, next step is multiply by 4 to scale
add $t5, $t3, $t3  # t5 = t3 + t3 = t3 * 2
add $t5, $t5, $t5  # t5 = t5 + t5 = t3 * 4  = (d-e)*4 as a byte offset
add $t3, $s2, $t5  #Add d-e index plus K's 0th index to get final index into $t3 temp

lw $t3, 0($t3)     #Load K's pointer based on index into the value of K
sw $s1, 0($t3)     #Store the value of K into J[6]
sw $s4, 24($s1)    #Store J[6] into $s4, it's 24 because index 6 x 4-byte array element size

Another possibility for the last two is this, I'm not entirely sure:

lw $s1, 24($s1)    # compute byte address of J[6], its old value doesn't matter
sw $s1, 0($t3)     #Store the value of K into J[6]
sw $s4, 24($s1)    #Store J[6] into $s4, it's 24 because index 6 x 4-byte array element size