0

I'm trying to optimize MIPS code by reducing instructions. Right now, I have a while loop as such:

funct: add  $v0, $zero, 0
       add  $t0, $zero, 0
Loop:  slt  $t1, $t0, $a0
       beq  $t1, $zero, Exit
       add  $v0, $v0, $t0
       addi $t0, $t0, 1
       j    Loop
Exit:  jr   $ra

I know this equivalently translates to a simple while loop. However, I am confused how to convert this to a do-while loop to reduce the executions of the program.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
zzzOp
  • 105
  • 1
  • 1
  • 9

2 Answers2

2

This looks like a homework problem, so I'm going to try to point you in the right direction without spoon-feeding you the answer.

Instead of making your conditional jump ask "are we done", consider what you could do if the conditional were reversed to "should we keep going".

0

If a loop might need to run 0 times, put a conditional branch outside the loop to check for that case.

You can also put some instructions to set up for (or actually do some of) the first iteration outside the loop. Another trick is to jump into the middle of the loop instead of falling into the first instruction. I'm not sure if there's a name for this technique. (Wikipedia defines software pipelining as something more complex that increases code size, instead of just rotating the sequence of instructions inside the loop while adjusting the code outside to match.)

Then restructuring to put the loop condition at the bottom is straightforward: invert the check so fall-through out of the loop happens when appropriate, instead of taking the branch to exit.

If you really want to reduce the number of instructions executed, you can just do some math and eliminate the loop. $t0 = 0 .. $a-1, and you add that to $v0 every iteration. So the loop is just a sum(0..$a-1). There's a closed-form formula for sum(0..n): n * (n+1) / 2.

Note that you can skip the $t0 = 0 iteration when transforming your loop (if you decide to keep it), since 0 is the additive identity.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
  • My answer on [Why are loops always compiled into "do...while" style (tail jump)?](https://stackoverflow.com/q/47783926) goes into more detail on the same concept. Also try asking a compiler. (On a real MIPS with branch-delay slots, you'll need to fill the delay slots. Can be hard when the loop is truly tiny, but OTOH there aren't many different possibilities to consider... Until you start considering peeling some of the first and/or last iteration so you can "rotate" the loop to have the branch condition at the bottom even when that's not the most natural form for the loop logic.) – Peter Cordes Jan 04 '21 at 10:03