CODEWITHSUNDEEP
cassemblymips
Verglas
Verglas

Reputation: 79

While loop through array, MIPS assembly

I want to convert while (w[i] == x) i += j; into MIPS assembly code. Assuming INTEGERS i,j, and x are in $3,$4 and $5. Also assume i=0 initially before the while loop. w => array of integers and its base address is stored in $6. So far I have this.

Loop:
    sll $10, $3, 2    # $10 = i* 4
    add $10, $6, $10  # $10 has address of w[i]
    lw  $11, 0($10)   # $11 = w[i]
    bne $11, $5, Exit # exit from loop if w[i]!= x
    add $3,  $3, $4   # i= i+ j
    j Loop
Exit:

Is it possible to optimize this code by moving the base address itself by j*4 and also get rid of the multiple branch instructions? Cause I have no clue on how to do that.

Thanks in advance!

Upvotes: 0

Views: 5997

Answers (2)

user3185968
user3185968

Reputation:

To make the comparison easier, I've written a small dummy function:

#include <stdint.h>
#include <stdlib.h>

uint32_t fun1(uint32_t const *in, uint32_t cmp, size_t j)
{
  size_t i = 0;
  while (in[i] == cmp)
    {
      i += j;
    }
  return in[i];
}

this can be compiled, and the output can be compared to an equivalent function:

uint32_t fun2(uint32_t const *in, uint32_t cmp, size_t j)
{
  while (*in == cmp)
    {
      in += j;
    }
  return *in;
}

For both functions, gcc (4.8 on x86-64) generates a loop with only 4 instructions. For the second function it essentially goes:

temp1 = (in)
compare temp1, cmp
if not equal, return temp1
temp2 = j*sizeof(uint32_t)

loop:
in += temp2            #\
temp1 = (in)           # \
compare temp1, cmp     #  - 4 instructions loop
if equal, goto loop    # /

return temp1

This pseudo-assembly can probably be implemented for MIPS like so:

lw   $v0, 0($a0)
beq  $a1, $v0, end
sll  $t1, $a2, 2

loop:
add  $a0, $a0, $t1      #\
lw   $v0, 0($a0)        # - only 3 instructions in loop, due to test-and-branch
bne  $a1, $v0, loop     #/

end:
jr $ra

Upvotes: 1

starrify
starrify

Reputation: 14781

To get rid of the multiple branch instructions, this trick can be used:
WARNING: NOT exactly equivalent to your code

Loop:
    sll $10, $3, 2    # $10 = i* 4
    add $10, $6, $10  # $10 has address of w[i]
    lw  $11, 0($10)   # $11 = w[i]
    add $3,  $3, $4   # i = i + j
    beq $11, $5, Loop # keep looping if w[i] == x
Exit:
    sub $3,  $3, $4   # i = i - j

The trick is to perform i += j before testing for keep looping or not.
This do introduce a problem sometimes: it may trigger an additional integer overflow when your code doesn't.

EDITED:

It's something like rewriting this:

while (some_condition())
    do_something();

into this:

do
    do_something();
while (some_condition());
undo_something();

EDITED:

Well, let me try to "move the pointer from the base address itself by j*4" this time :)

Start:
    sll $11, $3, 2    # $11 = i * 4
    add $10, $11, $6  # Let $10 be a "cursor" pointing to w[i]        
Loop:
    lw  $11, 0($10)   # $11 = w[i]
    sll $12, $4, 2    # $12 = j * 4
    add $10, $10, $12 # update $10 by 4 * j
    add $3,  $3, $4   # update i by j
    beq $11, $5, Loop # keep looping if w[i] == x
Exit:
    sub $3,  $3, $4   # i = i - j

However it's not more optimized than the version I gave above: both of them uses 5 instructions inside the loop body.

Upvotes: 1

Related Questions