Case Study: Implementing Subroutines with Arrays

Introduction

We're going to implement a function that passes an array. This function is called findMin which finds the minimum value in an array.

findMin

Here's a simple C function that finds the minimum value of an array of n values passed in, and returns it.

int findMin( int arr[], int n ) {
  int min = arr[ 0 ] ;
  int i ;
  for ( i = 0 ; i < n ; i++ )
    {
       if ( arr[ i ] < min )
          min = arr[ i ] ;
    }
  return min ;
}

Arrays are really just pointers, and in MIPS, pointers are 32 bits (at least, MIPS R2000/R3000---later MIPS CPUs use 64 bits of addresses). Thus, we can pass the pointers using the argument registers since those registers can store 32 bits.

It's often quite convenient that registers store the same number of bits as addresses.

Implementation

Here's the implementation in MIPS. We assume arr is stored in $a0 and n is stored in $a1. We use $t0 to store min and $t1 to store i. Notice this is a leaf procedure. So, we won't use the stack. Also notice that loading a word at the address stored in $a0 access arr[ 0 ].

findMin:   lw $t0, 0($a0)       # min = arr[0] 
           li $t1, 0            # i = 0 
LOOP:      bge $t1, $a1, END    # branch ! (i < n) 
           add $t2, $t1, $t1    # t2 = 2 * i 
           add $t2, $t2, $t2    # t2 = 4 * i 
           add $t2, $t2, $a0    # t2 = arr + (4 * i) 
           lw  $t3, 0( $t2 )    # t3 = arr[ i ] 
           bge $t3, $t0, INCR   # branch ! (arr[i] < min) 
           move $t0, $t3        # min = arr[i] 
INCR:      addi $t1, $t1, 1     # i++ 
           j LOOP               # back to top of loop 
END:       move $v0, $t0        # retval = min 
           jr $ra               # return

The awkward part is computing the address of the array element. Recall that & arr[ i ] is arr + ( sizeof(int) * i ) where we assume sizeof(int) is 4 bytes. Thus, we must compute 4 * i. There are two ways to do this. Multiply by 4 (which involves some complications of its own) or add the number to itself twice (which seems awkward).

Also notice where the branch statement for the if-statement goes. If the condition is false, it jumps to the increment.

Making the Call

How do we call findMin? If arr is a label which is conveniently declared in the data segment, then all we do is something like:

   la $a0, arr     # set arg 0
   li $a1, 10      # set arg 1
   jal findMin
   move $t0, $v0 # save return value to $t0

findMin, version 2

This is the "same" function as before, at least, in the purpose of the function. It finds the minimum value in an array and returns it.

int findMinTwo( int * arr, int n ) {
  int min = * arr ;
  int i ;
  for ( i = 0 ; i < n ; i++ )
    {
       if ( *arr < min )
          min = * arr ;
       arr++ ;  // POINTER ARITHMETIC: Move arr forward 1 element
    }
  return min ;
}

The difference in this version is that we treat the arr as a pointer variable, and move the pointer forward one element at a time..

In the first version, findMin, we did not alter arr's value. Instead, each iteration, we computed the offset from the start of the array to element i of the array. We summed the offset and arr and storing the sum into a temporary register. Then, we loaded the array element from the address stored in this temporary register.

As you can see, the first version is more complicated to explain and implement in MIPS, even though it's somewhat easier to understand the array version than the pointer version (because most people understand arrays better than pointers, even though, in C, the two are related to one another).

Implementation

Here's the implementation in MIPS. We assume arr is stored in $a0 and n is stored in $a1. We use $t0 to store min. This version is somewhat simpler because we modify arr, which we did not do before, and we do not need to do the more difficult computations of addresses as in the previous version.

findMinTwo: lw $t0, 0($a0)       # min = arr[0] 
            li $t1, 0            # i = 0 
LOOP:       bge $t1, $a1, END    # branch ! (i < n) 
            lw  $t2, 0( $a0 )    # t2 = * arr 
            bge $t2, $t0, INCR   # branch ! (*arr < min) 
            move $t0, $t2        # min = * arr 
INCR:       addi $a0, $a0, 4     # Move arr forward 1 element 
            addi $t1, $t1, 1     # i++ 
            j LOOP               # back to top of loop 
END:        move $v0, $t0        # retval = min 
            jr $ra               # return

This code is shorter and more efficient than the array version. This is one reason why a good knowledge of pointers can help you write more efficient code. However, realize the tradeoffs between efficent code, and code that's easy to follow and maintain.

Summary

Implementing a function with an array is the first time we've actually used an address from memory and used the lw instruction. While compilers allow us to access the ith element of an array conveniently (via pointer arithmetic), we don't get such conveniences in assembly language. We have to compute the offset explicitly as in findMin.

If you don't mind moving the pointer (which you can do, if it's passed as a parameter), then you can avoid computing the offset, as in findMinTwo.

Web Accessibility