Implementing Loops

Introduction

Unlike conditional statements, which have assembly instructions that support them more-or-less directly (i.e., beq), loops do not have similar support.

To translate loops, it's easier to convert the loops to if-statements with goto statements, prior to tranlation. Doing so also gives you insight into how a loop really behaves.

We'll translate a while-loop, then a for-loop. You can do the do-while loop as an exercise (and you should!).

Here's a generic while-loop:

while ( <cond> )
  {
    <while-body>   
  }

This is how it's translated to an if-statement with goto's.

L1: if ( <cond> )
      {
         <while-body>   
         goto L1 ;
      }

C really does support goto-statements, with labels, so you can do this translation on a C compiler, if you want.

Here's an example with real code.

while ( i < j )
  {
    k++ ;
    i = i * 2 ;
  }

Then translate it to if-statements with goto's.

L1: if ( i < j )
      {
        k++ ;
        i = i * 2 ; 
        goto L1 ;
      }

This should be easy to convert to MIPS. Assume $r1 stores i, $r2 stores j, and $r3 stores k.

L1:   bge  $r1, $r2, EXIT   # branch if ! ( i < k )
      addi $r3, $r3, 1      # k++
      add  $r1, $r1, $r1    # i = i * 2 
      j    L1               # jump back to top of loop 
EXIT:

We used the pseudo-instruction bge for convenience. Also, rather than use the multiply instruction (which requires using two new registers, HI and LO), we multiplied by 2 by adding the value to itself.

Translating for-loops

To translate a for-loop, we'll only go part way, and translate it to if-statements and goto's. You can do the rest on your own. Here's a generic for-loop:

for ( <init> ; <cond> ; <update> )
  {
     <for-body> 
  }

This is how it's translated to an if-statement with goto's.

<init>
L1: if ( <cond> )
      {
         <for-body> 
UPDATE:  <update> 
         goto L1 ;
      }
EXIT:

There's only one special case. Suppose the <for-body> has a continue statement. Then, you need to jump to the <update> code, which is at the UPDATE label.

break should still work fine, becuase you can jump to the EXIT label.

Translating do-while loops

You should do this on your own.

Translating nested loops

You just need to follow the rules for translating for-loops, and realize that the <for-body> may itself contain a for-loop.

Summary

Translating loops is fairly easy, because you can just translate them to if-statements with goto's. You've reduced the problem of translating loops to translating if-statements.

Web Accessibility