While loop through array, MIPS assembly

Question

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!

starrify · Accepted Answer · 2014-09-14 14:24:25Z

1

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.

edited Sep 14, 2014 at 14:24

answered Sep 14, 2014 at 13:31

starrify

15k6 gold badges40 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Verglas Over a year ago

@starrify would this work as well? (edited the question)

starrify Over a year ago

@Verglas Noooooooooot like this plz.. Paste the code to somewhere like gist.github.com or pastebin and send the link > <

starrify Over a year ago

@Verglas No and I cannot even point out a single problem. i's not changed, the array member loaded was w[j] not w[i], and j was changed. If while (w[i] == x) i += j; is what you want to convert then the assembly does completely another thing. If it's not, show others your original problem

Verglas Over a year ago

@starrify If $11 and $5 are equal, so it branches, where does the loop start? from the "lw" line or the first ever line of the code? Also, if it starts from the "lw" line how is each element of the array checked?

starrify Over a year ago

@Verglas 1. There are several code blocks, you have to tell me which one you're talking about. 2. You said you are converting while (w[i] == x) i += j;, and it is not the case that "each element of the array" is checked unless j=1. So what exactly is your goal?

|

score 1 · Accepted Answer · 2014-09-14 20:29:07Z

1

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

edited Sep 14, 2014 at 20:29

answered Sep 14, 2014 at 19:33

user3185968

5 Comments

Peter Cordes Over a year ago

Also related: Translating C function with args to MIPS: loop over an int array and count negatives for a counted loop, not this weird strided search. (Better canonical duplicate for normal loops over arrays)

user3185968 Over a year ago

@PeterCordes This is a pretty old answer, and one I'm not particularly proud of. In my defense, it was written before I knew godbolt.org, so maybe I can be forgiven. Not sure why this question and answer would be relevant now?

Peter Cordes Over a year ago

I was looking for canonical duplicates for What is the simplest way to iterate through a mips assembly array?, and this one of the first I found that didn't waste instructions on either a separate counter (instead of pointer increment), or on a stupid j instruction at the bottom with an if() break at the top. I only later realized exactly what the loop was doing, which ruled it out as a good duplicate for "normal" loop-over-array questions. This Q&A does come up in google for MIPS loop over array.

user3185968 Over a year ago

@PeterCordes Ah, Ok. For such trivial questions I could only recommend godbolt.org with some decent optimization settings (and a MIPS target without load delay slots). I'm pretty sure it'll always generate at least as good code as a human, so assembly-writing questions about it are useless anyway.

Peter Cordes Over a year ago

An answer explaining the code in human terms (pointer increment) is not useless, and it's a common enough question that having a good canonical answer is a good way to teach people some standard idioms. But yes, GCC does do a good job with the right C source: godbolt.org/z/8WdYTWdva. Probably less readable for total beginners who would need an answer to a question like that, though.

Collectives™ on Stack Overflow

While loop through array, MIPS assembly

2 Answers 2

EDITED:

EDITED:

9 Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

EDITED:

EDITED:

9 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related