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:
$s0is 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:
$t2is never modified — all address calculations use$t5and$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 —