Loop Example 2 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 */
}
C MIPS Equivalent
/* 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? Previous Slide Next Slide Alyce Brady, Kalamazoo College
