MIPS: what am I doing wrong in traversing array backwards

Question

I cant find a flaw in my instructions. In instruction 2, I am putting A[19] + 4 into register $t1.

Something is wrong

Answer 1

This assignment is pretty tricky. I think the only way to use that loop structure with that number of instructions is to load from -4($t1), if you want to access every element once.

That means exiting when ptr == &A[0] is correct (beq $t1, $s0, EXIT), since you already accessed it as ptr[-1] last iteration.

That also avoids the problem of loading from A[n], one-past-the-end, a bug in your current code.

But I wouldn't describe t1 as "the current address"; it's the address + 4 of the element you're going to access this iteration. But this loop structure with a conditional branch at the top is inefficient anyway, not a pattern you'd want to memorize.

Normally you want to arrange things so there's a conditional branch at the bottom, going back to the top of the loop or falling through. You don't want a j LOOP with an if () break inside the body if you can avoid it by rotating the loop to put the condition at the bottom, even if that means peeling a couple instructions at the start or end.

For example:

• Translating C function with args to MIPS: loop over an int array and count negatives the last few versions in Craig's answer show good loop structure with a bne reg,reg, loop.
• Why are loops always compiled into "do...while" style (tail jump)?
• What is the simplest way to iterate through a mips assembly array? a simple memset / fill loop.

In this case, the normal way to write this efficiently would be
endp = arr+n; ; for(p = arr ; p != endp ; p++) ...

   or     $s1, $zero, $zero  # sum=0:  move $s1, $zero
## for variable n, check that it's non-zero like beqz $n, skip_loop
   or     $t1, $s0, $zero    # p = A;  move $t1, $t0
   addiu  $t2, $s0, 80       # endp = A + n
LOOP:                        # do{
    lw     $t0, 0($t1)
    addiu  $t1, $t1, 4
    add    $s1, $s1, $t0        # sum += *p++  with trapping on signed overflow 
    bne    $t1, $t2, LOOP    # }while(p != endp)

One more instruction outside the loop, and one more register needed. Unless you don't need the base address of A after the loop, then you can just increment $s1 instead of copying it first.

But this is fewer instructions in the loop, so fewer instructions executed for n>=1, and same static code size. (Or smaller if we can destroy the pointer).

MIPS has lots of registers, so using one extra is usually not a problem. And unless your loop runs only a couple, spending an extra instruction inside the loop to use fewer registers is a false economy. Loops with the conditional branch not at the bottom are dumb, especially when it's easy to be sure they run at least 1 iteration, and when the condition is simple so it's easy to write it the more efficient way.

Also, I scheduled my instructions to not use the load result right after the load! No sense stalling an in-order pipeline unnecessarily. MIPS II and later made it safe to do that for correctness, but would still stall. A pointer increment is the perfect thing to do right after a load. (On a real MIPS with a branch delay slot, you'd reorder the add $s1, $s1, $t0 into the branch delay slot, so it's load / p++ / bne / sum+=.)