Introduction to Computer Organization (ICO, CCIT 4026) HKU SPACE Community College | AY2526 S2

Q1 [25 marks] — If-Else with Array Access

Python code:

if (k <= 10):
    A[30 + k] = A[30] + k
else:
    k = k + 1

Register mapping: $s0 = base address of array A, $s1 = k

Key Concepts: - Word array → each element is 4 bytes, so A[i] is at address $s0 + i*4 - A[30] → offset = 30 × 4 = 120 bytes - A[30 + k] → address = $s0 + (30+k)*4 = $s0 + 120 + k*4 - k <= 10 is equivalent to k < 11 → use slti to test

MIPS Code:

        # --- Condition: if (k <= 10) ---
        slti $t0, $s1, 11       # $t0 = 1 if k < 11 (i.e., k <= 10)
        beq  $t0, $zero, else   # if $t0 = 0 (k > 10), jump to else

        # --- Then branch: A[30 + k] = A[30] + k ---
        lw   $t1, 120($s0)      # $t1 = A[30]  (offset 30*4 = 120)
        add  $t1, $t1, $s1      # $t1 = A[30] + k
        sll  $t2, $s1, 2        # $t2 = k * 4
        add  $t2, $t2, $s0      # $t2 = base_A + k*4  =  &A[k]
        sw   $t1, 120($t2)      # store to &A[k] + 120 = &A[30+k]
        j    end_if             # skip else branch

else:
        # --- Else branch: k = k + 1 ---
        addi $s1, $s1, 1        # k = k + 1

end_if:

Step-by-step explanation:

Instruction Explanation
slti $t0, $s1, 11 Sets $t0 = 1 if k ≤ 10 (using < 11 is equivalent to ≤ 10)
beq $t0, $zero, else If $t0 = 0 (condition false), jump to else
lw $t1, 120($s0) Load A[30]; 30 × 4 = 120 byte offset from base
add $t1, $t1, $s1 $t1 = A[30] + k
sll $t2, $s1, 2 k × 4 (left-shift by 2 = multiply by 4)
add $t2, $t2, $s0 Compute address of A[k] (base + k × 4)
sw $t1, 120($t2) Write to A[k] + 120 bytes = A[k+30] = A[30+k]
j end_if Jump over else branch
addi $s1, $s1, 1 else: k = k + 1

Note: $s0 is never modified — all address calculations use $t2.

Q2 [25 marks] — While Loop with Array Access

Python code:

b = 0
while (b <= 5):
    A[b - 1] = A[b]*7
    b = b + 1

Register mapping: $t0 = base address of array A, $s0 = b

Key Concepts: - b <= 5 is equivalent to b < 6 → use slti $t1, $s0, 6 - A[b]*7 → multiply using shifts: 7 = 8 - 1, so A[b]*7 = (A[b] << 3) - A[b] - A[b-1] → address = &A[b] - 4, written as sw $t5, -4($t3)

MIPS Code:

        # --- b = 0 ---
        add  $s0, $zero, $zero   # b = 0

while_start:
        # --- Condition: while (b <= 5) ---
        slti $t1, $s0, 6         # $t1 = 1 if b < 6  (i.e., b <= 5)
        beq  $t1, $zero, while_end  # if b > 5, exit loop

        # --- A[b] address and load ---
        sll  $t2, $s0, 2         # $t2 = b * 4
        add  $t3, $t0, $t2       # $t3 = &A[b]
        lw   $t4, 0($t3)         # $t4 = A[b]

        # --- Compute A[b] * 7 using shifts (7 = 8 - 1) ---
        sll  $t5, $t4, 3         # $t5 = A[b] * 8
        sub  $t5, $t5, $t4       # $t5 = A[b]*8 - A[b] = A[b]*7

        # --- Store to A[b-1] ---
        sw   $t5, -4($t3)        # A[b-1] = A[b]*7  (offset -4 from &A[b])

        # --- b = b + 1 ---
        addi $s0, $s0, 1         # b = b + 1
        j    while_start

while_end:

Key trick — Multiply by 7 without pseudo-instruction:

A[b] * 7  =  A[b] * (8 - 1)
           =  A[b] * 8  -  A[b]
           =  (A[b] << 3)  -  A[b]

This uses only sll and sub, which are both real MIPS instructions.

Addressing A[b-1]: Since $t3 = &A[b], the address of A[b-1] is $t3 - 4, expressed as sw $t5, -4($t3).

Q3 [25 marks] — For Loop with Nested If-Else

Python code:

for h in range(3, 10, 1):
    if (h < 5):
        A[h] = A[h//2]
    else:
        A[h] = A[h*2]

Register mapping: $t2 = base address of array A (must NOT be changed), $s3 = h

Key Concepts: - range(3, 10, 1) → h = 3, 4, 5, …, 9; loop condition is h < 10 - h // 2 (floor divide by 2 for positive h) → srl $t5, $s3, 1 (logical right shift by 1) - h * 2 → sll $t5, $s3, 1 - Address of A[i] = $t2 + i*4

MIPS Code:

        # --- h = 3 (loop initialisation) ---
        addi $s3, $zero, 3       # h = 3

for_check:
        # --- h < 10? (loop condition) ---
        slti $t3, $s3, 10        # $t3 = 1 if h < 10
        beq  $t3, $zero, for_end # if h >= 10, exit loop

        # --- if (h < 5) ---
        slti $t4, $s3, 5         # $t4 = 1 if h < 5
        beq  $t4, $zero, else_h  # if h >= 5, go to else

        # --- Then: A[h] = A[h//2] ---
        srl  $t5, $s3, 1         # $t5 = h >> 1  =  h // 2
        sll  $t5, $t5, 2         # $t5 = (h//2) * 4
        add  $t5, $t5, $t2       # $t5 = &A[h//2]
        lw   $t6, 0($t5)         # $t6 = A[h//2]
        sll  $t7, $s3, 2         # $t7 = h * 4
        add  $t7, $t7, $t2       # $t7 = &A[h]
        sw   $t6, 0($t7)         # A[h] = A[h//2]
        j    for_inc

else_h:
        # --- Else: A[h] = A[h*2] ---
        sll  $t5, $s3, 1         # $t5 = h * 2
        sll  $t5, $t5, 2         # $t5 = h*2 * 4  =  h * 8 bytes
        add  $t5, $t5, $t2       # $t5 = &A[h*2]
        lw   $t6, 0($t5)         # $t6 = A[h*2]
        sll  $t7, $s3, 2         # $t7 = h * 4
        add  $t7, $t7, $t2       # $t7 = &A[h]
        sw   $t6, 0($t7)         # A[h] = A[h*2]

for_inc:
        # --- h = h + 1 ---
        addi $s3, $s3, 1         # h++
        j    for_check

for_end:

Verification trace:

h Branch Index computed Operation
3 then (h < 5) h//2 = 1 A[3] = A[1]
4 then (h < 5) h//2 = 2 A[4] = A[2]
5 else (h ≥ 5) h*2 = 10 A[5] = A[10]
6 else (h ≥ 5) h*2 = 12 A[6] = A[12]
9 else (h ≥ 5) h*2 = 18 A[9] = A[18]

Note: $t2 is never modified — all address calculations use $t5 and $t7.

Q4 [25 marks] — Function with Procedure Calling Convention

Python code:

def my_func(x, y):
    a = y // x
    b = 1
    while (a < 5):
        b = x - a
        a = a + 1
    return (b - y)

Allowed registers: $s0, $s1, $v0 (read/write) | $a0, $a1 (read only) | $sp (stack only)

Register Mapping:

Variable Register Reason
x $a0 1st argument (read-only per constraint)
y $a1 2nd argument (read-only per constraint)
a $s0 callee-saved, read/write
b $s1 callee-saved, read/write
return value $v0 standard return-value register
loop condition temp $v0 reused as scratch before final return

Calling Convention Rules Applied: - $s0 and $s1 are callee-saved ($s-registers) → must be pushed to stack on entry and restored before return - $a0, $a1 are never written to (read-only as required) - This is a leaf function (calls no other functions) → $ra is unchanged, no need to save it - div + mflo is used for integer division (no pseudo-instruction div $d, $s, $t)

Stack Frame Layout:

High address  (before addi $sp, $sp, -8)
  ┌──────────────┐
  │   $s0 saved  │  ← $sp + 4
  ├──────────────┤
  │   $s1 saved  │  ← $sp + 0  (current $sp)
  └──────────────┘
Low address

MIPS Code:

my_func:
        # === Prologue: save callee-saved registers ===
        addi $sp, $sp, -8        # allocate 8 bytes on stack
        sw   $s0, 4($sp)         # save $s0
        sw   $s1, 0($sp)         # save $s1

        # === a = y // x ===
        div  $a1, $a0            # signed divide: LO = y / x
        mflo $s0                 # $s0 = a = y // x

        # === b = 1 ===
        addi $s1, $zero, 1       # $s1 = b = 1

while_loop:
        # === while (a < 5) ===
        slti $v0, $s0, 5         # $v0 = 1 if a < 5  (used as scratch)
        beq  $v0, $zero, while_done  # if a >= 5, exit loop

        # === b = x - a ===
        sub  $s1, $a0, $s0       # $s1 = b = x - a

        # === a = a + 1 ===
        addi $s0, $s0, 1         # $s0 = a = a + 1

        j    while_loop

while_done:
        # === return (b - y) ===
        sub  $v0, $s1, $a1       # $v0 = b - y  (final return value)

        # === Epilogue: restore callee-saved registers ===
        lw   $s0, 4($sp)         # restore $s0
        lw   $s1, 0($sp)         # restore $s1
        addi $sp, $sp, 8         # deallocate stack frame

        jr   $ra                 # return to caller

Why $v0 is safe as a scratch register inside the loop: $v0 holds the final return value only when sub $v0, $s1, $a1 executes at the end. During the loop, it is freely overwritten by slti $v0, $s0, 5 each iteration without side effects.

Execution trace example (x = 2, y = 8):

Step a b Condition
Init 8 // 2 = 4 1 —
Iteration 1 4 < 5 ✓ b = 2−4 = −2, a → 5 continue
Check 5 < 5 ✗ — exit loop
Return — b − y = −2 − 8 = −10 $v0 = -10

— END OF ASSIGNMENT 2 ANSWERS —