Delayed Branching in MIPS

Question

I have the following MIPS code and I am looking to rewrite/reorder the code so that I can reduce the number of nop instructions needed for proper pipelined execution while preserving correctness. It is assumed that the datapath neither stalls nor forwards. The problem gives two hints: it reminds us that branches and jumps are delayed and need their delay slots filled in and it hints at chaging the offset value in memory accesss instructions (lw,sw) when necessary.

LOOP:  lw           $1, 100 ($2)
       addi         $1, $1, 1
       sw           $1, 500 ($2)
       addiu        $2, $2, 4
       bne          $2, $10, LOOP

It's quite obvious to me that this code increments the contents of one array and stores it in another array. So I'm not exactly seeing how I could possibly rearrange this code since the indices need to be calculated prior to completing the loop.

My guess would be to move the lw instruction after the branch instruction since (as far as I understand) the instruction in the delay slot is always executed. Then again, I don't quite understand this subject and I would appreciate an explination. I understand pipelining in general, but not so much delayed branching. Thanks

Answer 1

One way of filling the branch delay slot would be:

addiu  $2, $2, 4  # We'll now iterate over [$2+4, $10] instead of [$2, $10[
LOOP:  lw           $1, 96 ($2)
       addi         $1, $1, 1
       sw           $1, 496 ($2)
       bne          $2, $10, LOOP
       addiu        $2, $2, 4  # Use the delay slot to increase $2

Answer 2

In terms of the second hint:

Make the 4th instruction the 2nd. It can be pipelined in (after ID of the 1st instruction, if you use P/H terminology) while the first still executes. Then make the offset in the (old) 3rd instruction 496 instead of 500. I assume you see now why?

As to the first hint, I'm not too familiar with how exactly delayed branches execute (not implemented on SPIM so I didn't care). The old last instruction can probably be made second-to-last as the name "delayed" indicates, but I couldn't tell you how and why.