Nested Loop Demonstration in MIPS

Question

I have found a code snippet on this website as an answer to a question. The code uses nested loops in MIPS.

Here is the code :


.data
    prompt: .asciiz "Please enter the edge length of the base of right 
                      triangle: "
    newLine: .asciiz "\n"
    star: .asciiz "*"

.text
    main:
        li $v0, 4       # print the prompt
        la $a0, prompt
        syscall

        li $v0,5            #take user input
            syscall
    
        move $s0, $v0     # move the input to $s0

        li $t0, 0       # load 0 at t0

    outerLoop:
        beq $t0, $s0, end   #(for i=0;i<=baseLength;i++)
                    #if t0=s0 branch to end
        
        addi $t0, $t0, 1    # increment i

        li $t1, 1       #load 1 at t1

        jal changeLine      #jump to changeLine

    innerLoop:
        bgt $t1, $t0, outerLoop  #(for j=0;j<=i;j++)
                     # if t1=t0 branch to outerLoop

        li $v0, 4       # print star
        la $a0, star
        syscall 
    
        addi $t1, $t1, 1    # increment j

        j innerLoop     # jump to innerLoop

    changeLine: 
        li $v0, 4       # new line
        la $a0, newLine
        syscall 

        jr $ra          # jump to after the call instruction

    end:
        li $v0, 10      # end of program
        syscall

The code works perfectly but I could not understand how the outer loop iterates even though there is no an explicit command like j outerLoop.

Any help is appreciated.

asm loops normally shouldn't have a `j` at the bottom, only a conditional branch. [Why are loops always compiled into "do...while" style (tail jump)?](https://stackoverflow.com/q/47783926) — Peter Cordes, Nov 27 '21 at 13:38

score 1 · Accepted Answer · answered Nov 27 '21 at 13:35

The answer is the innerLoop's first statement:

innerLoop:
        bgt $t1, $t0, outerLoop  #(for j=0;j<=i;j++)
                     # if t1=t0 branch to outerLoop

When the total number of iterations for the innerLoop has ended, the code jumps back to the outerLoop label.

Erik Eidt · Answer 2 · 2021-11-27T15:51:45.863

Here's the thing: the outer loop has been "optimized" and no longer directly reflects the for loop stated in comment. The C equivalent looks more like this:

for ( i = 0; i <= baseLength; /* empty increment */ ) {
    i++;
    <loop-body> // includes inner loop
}

Normally a for loop such as this:

for ( i = 0; i < N; i++ ) { <loop-body> }

by definition of the for loop construct, would expand as follows:

i = 0;
while ( i < N ) {
    <loop-body>
    i++;
}

However, as you can see, in the code you're showing, the i++ increment has moved from after the loop-body to before the loop-body.

As a result, there is no increment code for the outer loop to perform after executing the inner loop — and thus, the inner loop's exit location can continue directly with the top of the outer loop.

However, when making these changes, we have to be careful b/c now loop-body executes with a 1 larger value of i than in the C code that this was translated from and now shown in comment. If i is used inside loop-body this is an issue.

And here i is indeed used inside the loop body, as part of the inner loop iteration control. Because i is one larger, this inner loop will iterate one more time than the C code that was written in comment.

If the "optimization" had not been applied, the inner loop would probably exit by jumping forward to an i++ increment that belongs to the outer loop, which would then j outerLoop (jump backwards) as you were expecting, to continue the outer loop.

Beginning assembly programmers are often keen to modify the C or pseudo code they're starting with during translation into assembly, but these changes are often done without the understanding that they are not logically or algorithmically equivalent. For example, changing a while loop into a do-while loop; changing array references into pointer operations — in this case changing the order of operations. Since C can express all of those (do-while, pointers, etc.) I advocate making optimizations in C first, then verify the equivalent behavior, and take that to assembly.

Yes, there are other optimizations that are only sensible in assembly (i.e. not possible or practical in C), though suggest to leave those for when efficiency is the primary topic and until then follow the C starting code rather literally.

Nested Loop Demonstration in MIPS

2 Answers2