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-14T14:24:25.427

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 '14 at 14:24

answered Sep 14 '14 at 13:31

starrify

14,307
5
33
50

@starrify would this work as well? (edited the question) – Verglas Sep 14 '14 at 14:28
@Verglas Noooooooooot like this plz.. Paste the code to somewhere like gist.github.com or pastebin and send the link > – starrify Sep 14 '14 at 14:31
@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 – starrify Sep 14 '14 at 14:38
@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? – Verglas Sep 14 '14 at 14:53
@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? – starrify Sep 14 '14 at 15:00
@starrify I think I'm confusing myself and you here, sorry. I think I assumed that `j = 1` when it's not. So really `while(w[i] == x) i+=j;` is checking whatever element in the array depending on what i is at the time, is compared to `x`. My question is, How does your final block of code(the one WITH the moved pointer from base address itself by j*4) actually which element to check next? because how I understand the code right now is that it constantly checks the same element in the array? – Verglas Sep 14 '14 at 15:07
@starrify just to check in your final block of code, if we say $11 and $5 are equal so it branches, does the loop start from "lw" or the "start" again? – Verglas Sep 14 '14 at 15:19
@Verglas The loop starts from `Loop:` – starrify Sep 14 '14 at 15:30
if we just say, he first loop checked w[1] then the next one checked w[3], I'm having trouble on how "i" is being updated in w[i]? – Verglas Sep 15 '14 at 05:47

EOF · Answer 2 · 2014-09-14T20:29:07.783

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 '14 at 20:29

answered Sep 14 '14 at 19:33

EOF

6,273
2
26
50

Also related: [Translating C function with args to MIPS: loop over an int array and count negatives](https://stackoverflow.com/a/49518837) for a counted loop, not this weird strided search. (Better canonical duplicate for normal loops over arrays) – Peter Cordes Mar 27 '21 at 13:34
@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? – EOF Mar 27 '21 at 13:51
I was looking for canonical duplicates for [What is the simplest way to iterate through a mips assembly array?](https://stackoverflow.com/q/66831038), 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. – Peter Cordes Mar 27 '21 at 13:54
@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. – EOF Mar 27 '21 at 14:01
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: https://godbolt.org/z/8WdYTWdva. Probably less readable for total beginners who would need an answer to a question like that, though. – Peter Cordes Mar 27 '21 at 14:08

While loop through array, MIPS assembly

2 Answers2

EDITED:

EDITED: