Another Loop Example in MIPS

Another Loop Example: Reading from and Writing to an Array

        /* Double every value in A */
        int i;
        for ( i = 0; i < numVals; i++ )
        {
            A[i] *= 2;      /* which means A[i] = A[i] * 2 */
        }

/* Double every value in A */

{



    /* A[i] = A[i] * 2 */
    int x = A[i];
    x *= 2;
    A[i] = x;

        # $s6 = A, $s7 = numVals
        # $t0 = i, $t4 = x
        addi $t0, $zero, 0
LOOP:   slt $t1, $t0, $s7
        beq $t1, $zero, ENDLP

        # Calculate address of A[i]
        sll $t1, $t0, 2
        add $t1, $s6, $t1
        # Read value at A[i] into x; etc
        lw  $t4, 0($t1)
        sll $t4, $t4, 1
        sw  $t4, 0($t1)

        addi $t0, $t0, 1
        j LOOP
ENDLP:
        ⋮ 

# $t0 = i = 0
# $t1 = 1 if i < numVals
# Leave loop if i >= numVals


# $t1 = 4 * i (shift left 2)
# t1 = A + 4i, i.e., &A[i]

# Read A[i] into $t4 (x)
# x *= 2 (shift left 1)
# Store $t4 out to A[i]

# Increment i
# Jump to top of loop

More Complex Loop Pattern — Less Intuitive, More Efficient

• How many instructions get executed in the fragment above if numVals = 100?

  1 instruction above the loop, plus 100 * 11 instructions in the loop, plus the two instructions at the top of the loop that get executed when i == numVals, so 1103.

• Could a compiler produce this code differently to make it even more efficient?
  

              addi $t0, $zero, 0     # $t0 = i = 0
              j TEST                 # go to loop test
      LOOP:   sll $t1, $t0, 2        # t1 = i * 4
              add $t1, $s6, $t1      # t1 is address of A[i]
              lw $t4, 0($t1)         # t4 = value at A[i]
              sll $t4, $t4, 1        # t4 = A[i] * 2
              sw $t4, 0($t1)         # A[i] = t4
              addi $t0, $t0, 1       # i += 1 (or i++)
      TEST:   slt $t1, $t0, $s7      # t1 is 1 if i < numVals; 0 if i >= numVals
              bne $t1, $zero, LOOP   # goto LOOP if i < numVals
      END:    ...
  
  

  How many instructions get executed in this fragment if numVals = 100? (Highlight repeated lines)
• Spoiler Alert: we could squeeze a little more efficiency if we use pointers rather than array indices!   (Future topic)

              add $t0, $s6, $zero    # $t0 = ptr = A (i.e., &A[0])
              sll $t1, $s7, 2        # $t1 = 4 * numVals
              add $t9, $t0, $t1      # $t9 = &A[numVals] (too far)
              j TEST                 # go to loop test
      LOOP:   lw $t4, 0($t0)         # t4 = *ptr
              sll $t4, $t4, 1        # t4 = *ptr * 2
              sw $t4, 0($t0)         # *ptr = t4
              addi $t0, $t0, 4       # *ptr++
      TEST:   slt $t1, $t0, $t9      # t1 is 1 if ptr < &A[numVals]
              bne $t1, $zero, LOOP   # goto LOOP if ptr < &A[numVals]
      END:   ...
  

  Now how many instructions get executed in this fragment if numVals = 100?