Question

Consider the code below, where $a0 is the address of the start of an array of integers and $a1 is the length

of the array. Suppose that it is called with jal label sll . You can assume that sll and mul are executed in
a similar manner to addi and add respectively.
1 l a b e l s l l : s l l $a1 , $a1 , 2
2 l a b e l a d d : add $a1 , $a0 , $a1
3 l a b e l o r i : o r i $v0 , $0 , 1
4 l a b e l b e q 1 : beq $a0 , $a1 , l a b e l j r
5 l a b e l l w : lw $t0 , 0( $a0 )
6 l a b e l m u l : mul $v0 , $v0 , $ t 0
7 l a b e l a d d i : a d d i $a0 , $a0 , 4
8 l a b e l b e q 2 : beq $0 , $0 , l a b e l b e q 1
9 l a b e l j r : j r $ r a

a. In terms of n, how many dynamic instructions will be executed when this procedure is called when
the length of the array is n (i.e. $a1= n)?

Answer 1

The procedure will execute a total of 4 + 5n dynamic instructions, where n is the length of the array.

Step-by-step explanation:

The question requires calculating the number of dynamic instructions executed by a MIPS assembly code procedure when the array length is n (where n is the value of $a1). The code appears to iterate over an array, processing each element. To determine the dynamic instruction count, we must analyze the loop's structure:

The sll $a1, $a1, 2 instruction is executed once to shift the length of the array to calculate the array's byte size.

The code then enters a loop that starts with the beq instruction at label label beq1 and ends with the unconditional branch instruction at label beq2, which jumps back to label beq1.

Within this loop, instructions from label lw through label addi are executed n times, which is the length of the array.

The loop contains 5 instructions that are executed per iteration: lw, mul, addi, beq (at label beq2), and the beq instruction that initially checks the loop condition at label beq1.

Finally, after the loop completes, the jr instruction at label jr is executed once to return from the subroutine.

Overall, the procedure will execute 1 (sll $a1, $a1, 2) + 1 (add) + 1 (ori) + 1 (jr) + 5n (number of instructions in the loop multiplied by the number of iterations, n) for a total of 4 + 5n dynamic instructions.