ICO AY2526S2 — Lab 05 Answers & Solutions

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

Problem Overview

Given two vectors C and D:

C = { c0  c1 }
D = { d0  d1 }

Calculate M defined as:

M = Σᵢ₌₀¹ [ dᵢ + int( (cᵢ + dᵢ)² / (dᵢ + 1) ) ]
  = d0 + int((c0+d0)² / (d0+1))
  + d1 + int((c1+d1)² / (d1+1))

Using the example SID 12345678 → C = {5, 6}, D = {7, 8}:

M = 7 + int((5+7)² / (7+1))  +  8 + int((6+8)² / (8+1))
  = 7 + int(144 / 8)          +  8 + int(196 / 9)
  = 7 + 18                    +  8 + 21
  = 54

Program Architecture

The program is made up of three parts:

┌─────────────────────────────────────────────────┐
│  main                                           │
│    Load C, D → $a0-$a3                         │
│    jal comp_sum ──────────────────────────┐    │
│    Print $v0 (= M)                        │    │
└───────────────────────────────────────────│────┘
                                            ▼
┌─────────────────────────────────────────────────┐
│  comp_sum($a0=c0, $a1=c1, $a2=d0, $a3=d1)     │
│    sum1 = c0 + d0                               │
│    jal square_div(sum1, d0) ──────────────┐    │
│    partial1 = d0 + result                 │    │
│    sum2 = c1 + d1                         │    │
│    jal square_div(sum2, d1) ──────────────│──┐ │
│    return partial1 + result2 + d1         │  │ │
└───────────────────────────────────────────│──│─┘
                                            ▼  ▼
┌─────────────────────────────────────────────────┐
│  square_div($a0=sum, $a1=d)                     │
│    return int(sum² / (d+1))                     │
└─────────────────────────────────────────────────┘

Register Constraints

Function	Register	Permission
`comp_sum`	`$a0`–`$a3`	Read AND Write
`comp_sum`	`$v0`–`$v1`	Read AND Write
`comp_sum`	`$sp`, `$ra`	Stack operation ONLY
`square_div`	`$a0`–`$a1`	Read ONLY
`square_div`	`$s0`–`$s1`	Read AND Write
`square_div`	`$v0`–`$v1`	Read AND Write
`square_div`	`$sp`, `$ra`	Stack operation ONLY

Calling Convention Rules

Register Class	Who Saves?	Registers
Callee-saved	Called function saves/restores	`$s0`–`$s7`, `$ra` (if non-leaf)
Caller-saved	Calling function saves/restores	`$v0`–`$v1`, `$a0`–`$a3`, `$t0`–`$t9`

comp_sum is a non-leaf function (it calls square_div) → must save $ra in prologue.
square_div is a leaf function (calls nothing) → does NOT need to save $ra. It must save $s0 and $s1 since they are callee-saved.
Parameters cannot be passed via the stack — arguments must go in $a0–$a3.

Stack Frame Diagrams

`comp_sum` stack usage

On entry:
  ┌───────────┐ ← $sp (after prologue, -4)
  │   $ra     │
  └───────────┘

Before 1st call to square_div (additional -12):
  ┌───────────┐ ← $sp
  │   d1=$a3  │ $sp+0
  ├───────────┤
  │   d0=$a2  │ $sp+4
  ├───────────┤
  │   c1=$a1  │ $sp+8
  ├───────────┤
  │   $ra     │ $sp+12
  └───────────┘

After 1st call restore → back to just [$ra] on stack.

Before 2nd call to square_div (additional -8):
  ┌───────────┐ ← $sp
  │ partial1  │ $sp+0
  ├───────────┤
  │   d1=$a3  │ $sp+4
  ├───────────┤
  │   $ra     │ $sp+8
  └───────────┘

After 2nd call restore → back to just [$ra] on stack.
On return: pop $ra → stack fully restored.

`square_div` stack usage

On entry:
  ┌───────────┐ ← $sp (after prologue, -8)
  │   $s1     │ $sp+0
  ├───────────┤
  │   $s0     │ $sp+4
  └───────────┘
On return: both restored.

Complete MIPS Assembly Solution

# ============================================================
# ICO Lab 05 — Procedure Call with MIPS
# Calculates M = Σᵢ₌₀¹ [ dᵢ + int((cᵢ+dᵢ)² / (dᵢ+1)) ]
# Using example SID 12345678: C={5,6}, D={7,8}, M=54
# ============================================================

.data
    stack:     .space 256          # 256 bytes reserved for stack (64 words)
    stack_top:                     # label at high end of stack (TOS)
    C:         .word 5, 6          # c0=5, c1=6  (derived from SID)
    D:         .word 7, 8          # d0=7, d1=8  (derived from SID)
    msg:       .asciiz "M = "     # output prefix string

.text
.globl main

# ============================================================
# Function: square_div
#   Computes int( sum² / (d+1) )
#   Input:  $a0 = sum  (READ ONLY)
#           $a1 = d    (READ ONLY)
#   Output: $v0 = int(sum² / (d+1))
#   Uses:   $s0 (square), $s1 (divisor)  [callee-saved]
# ============================================================
square_div:
    # Step 1.1 — Save callee-saving registers ($s0, $s1)
    addi $sp, $sp, -8
    sw   $s0, 4($sp)              # save $s0
    sw   $s1, 0($sp)              # save $s1

    # Step 1.2 — Find the square of the first parameter: square = sum * sum
    mult $a0, $a0                 # HI:LO = sum * sum  ($a0 is read-only)
    mflo $s0                      # $s0 = sum²  (lower 32 bits)

    # Step 1.3 — Increment second parameter by 1: divisor = d + 1
    addi $s1, $a1, 1              # $s1 = d + 1  ($a1 is read-only)

    # Step 1.4 — Divide squared result by incremented result
    div  $s0, $s1                 # LO = int($s0 / $s1) = int(sum² / (d+1))

    # Step 1.5 — Copy division result to return register
    mflo $v0                      # $v0 = int(sum² / (d+1))

    # Step 1.6 — Restore callee-saving registers
    lw   $s0, 4($sp)              # restore $s0
    lw   $s1, 0($sp)              # restore $s1
    addi $sp, $sp, 8

    # Step 1.7 — Return to caller
    jr   $ra


# ============================================================
# Function: comp_sum
#   Computes M = d0+int((c0+d0)²/(d0+1)) + d1+int((c1+d1)²/(d1+1))
#   Input:  $a0 = c0,  $a1 = c1,  $a2 = d0,  $a3 = d1
#   Output: $v0 = M
#   Uses:   $a0-$a3, $v0-$v1  (all allowed read/write)
#           $ra saved on stack (non-leaf function)
# ============================================================
comp_sum:
    # Step 1.1 — Save callee-saving registers
    #            comp_sum calls square_div via jal, so $ra will be overwritten.
    #            Save $ra as callee-saving register for a non-leaf function.
    addi $sp, $sp, -4
    sw   $ra, 0($sp)              # save return address

    # Step 1.2 — Find sum of first components: sum1 = c0 + d0
    add  $v0, $a0, $a2            # $v0 = sum1 = c0 + d0

    # Step 1.3 — Prepare: sum1 → $a0, d0 → $a1  (done below after saving)

    # Step 1.4 — Save caller-saving registers before first call to square_div
    #            Need to preserve: c1($a1), d0($a2), d1($a3) across the call
    addi $sp, $sp, -12
    sw   $a1, 8($sp)              # save c1
    sw   $a2, 4($sp)              # save d0
    sw   $a3, 0($sp)              # save d1
    add  $a0, $v0, $zero          # $a0 = sum1  (arg1 for square_div)
    add  $a1, $a2, $zero          # $a1 = d0    (arg2 for square_div)

    # Step 1.5 — Call square_div(sum1, d0)
    jal  square_div               # $v0 = int(sum1² / (d0+1))

    # Step 1.6 — Restore caller-saving registers after first call
    lw   $a1, 8($sp)              # restore c1
    lw   $a2, 4($sp)              # restore d0
    lw   $a3, 0($sp)              # restore d1
    addi $sp, $sp, 12

    # Step 1.7 — Sum first D component with return value: partial1 = d0 + result1
    add  $v1, $a2, $v0            # $v1 = partial1 = d0 + int(sum1²/(d0+1))

    # Step 1.8 — Find sum of second components: sum2 = c1 + d1
    add  $v0, $a1, $a3            # $v0 = sum2 = c1 + d1

    # Step 1.9 — Prepare: sum2 → $a0, d1 → $a1  (done below after saving)

    # Step 1.10 — Save caller-saving registers before second call to square_div
    #             Need to preserve: d1($a3), partial1($v1)
    addi $sp, $sp, -8
    sw   $a3, 4($sp)              # save d1
    sw   $v1, 0($sp)              # save partial1
    add  $a0, $v0, $zero          # $a0 = sum2  (arg1 for square_div)
    add  $a1, $a3, $zero          # $a1 = d1    (arg2 for square_div)

    # Step 1.11 — Call square_div(sum2, d1)
    jal  square_div               # $v0 = int(sum2² / (d1+1))

    # Step 1.12 — Restore caller-saving registers after second call
    lw   $a3, 4($sp)              # restore d1
    lw   $v1, 0($sp)              # restore partial1
    addi $sp, $sp, 8

    # Step 1.13 — Add the two square_div return values together
    add  $v0, $v0, $v1            # $v0 = partial1 + int(sum2²/(d1+1))

    # Step 1.14 — Add second D component to return register
    add  $v0, $v0, $a3            # $v0 = M  (= partial1 + result2 + d1)

    # Step 1.15 — Restore callee-saving registers
    lw   $ra, 0($sp)              # restore return address
    addi $sp, $sp, 4

    # Step 1.16 — Return to caller
    jr   $ra


# ============================================================
# Main Program
# ============================================================
__start:
main:
    # Step 1.1 — Set up stack pointer to Top of Stack (TOS)
    la   $sp, stack_top           # $sp = high end of stack region

    # Step 1.2 — Load all four vector components into argument registers
    la   $t0, C
    lw   $a0, 0($t0)              # $a0 = c0 = C[0]
    lw   $a1, 4($t0)              # $a1 = c1 = C[1]
    la   $t0, D
    lw   $a2, 0($t0)              # $a2 = d0 = D[0]
    lw   $a3, 4($t0)              # $a3 = d1 = D[1]

    # Step 1.3 — No caller-saving registers need to be preserved in main
    #            (main does not use any values after the call to comp_sum)

    # Step 1.4 — Call comp_sum(c0, c1, d0, d1)
    jal  comp_sum                 # $v0 = M

    # Step 1.5 — No registers to restore in main

    # Step 1.6 — Print result prompt and value
    add  $t0, $v0, $zero          # temporarily save M (syscall will overwrite $v0)
    la   $a0, msg                 # load address of "M = "
    li   $v0, 4                   # syscall 4: print string
    syscall
    add  $a0, $t0, $zero          # $a0 = M (the computed value)
    li   $v0, 1                   # syscall 1: print integer
    syscall

    # Step 1.7 — Exit program
    li   $v0, 10                  # syscall 10: exit
    syscall

Step-by-Step Execution Trace

Using C = {5, 6}, D = {7, 8}:

In `main`

Step	Action	Register State
Init	Load C, D	`$a0=5, $a1=6, $a2=7, $a3=8`
1.4	`jal comp_sum`	enters comp_sum

In `comp_sum` (first entry)

Step	Instruction	Value
1.1	Save `$ra` on stack	stack = [`$ra`]
1.2	`sum1 = c0 + d0`	`$v0 = 5+7 = 12`
1.4	Save `$a1=6, $a2=7, $a3=8`; set `$a0=12, $a1=7`	stack = [`$ra`, 6, 7, 8]
1.5	`jal square_div(12, 7)`	enters square_div

In `square_div` (1st call, sum=12, d=7)

Step	Instruction	Value
1.1	Save `$s0, $s1` on stack	stack grows by 2
1.2	`square = 12 × 12 = 144`	`$s0 = 144`
1.3	`divisor = 7 + 1 = 8`	`$s1 = 8`
1.4	`div 144 / 8 = 18`	`LO = 18`
1.5	`$v0 = 18`	return value set
1.6	Restore `$s0, $s1`	stack restored
1.7	`jr $ra`	returns to comp_sum

Back in `comp_sum`

Step	Instruction	Value
1.6	Restore `$a1=6, $a2=7, $a3=8`	stack = [`$ra`]
1.7	`partial1 = d0 + result1 = 7 + 18`	`$v1 = 25`
1.8	`sum2 = c1 + d1 = 6 + 8`	`$v0 = 14`
1.10	Save `$a3=8, $v1=25`; set `$a0=14, $a1=8`	stack = [`$ra`, 8, 25]
1.11	`jal square_div(14, 8)`	enters square_div

In `square_div` (2nd call, sum=14, d=8)

Step	Instruction	Value
1.1	Save `$s0, $s1` on stack	stack grows by 2
1.2	`square = 14 × 14 = 196`	`$s0 = 196`
1.3	`divisor = 8 + 1 = 9`	`$s1 = 9`
1.4	`div 196 / 9 = 21` remainder 7	`LO = 21`
1.5	`$v0 = 21`	return value set
1.6	Restore `$s0, $s1`	stack restored
1.7	`jr $ra`	returns to comp_sum

Back in `comp_sum`

Step	Instruction	Value
1.12	Restore `$a3=8, $v1=25`	stack = [`$ra`]
1.13	`$v0 = partial1 + result2 = 25 + 21`	`$v0 = 46`
1.14	`$v0 = $v0 + d1 = 46 + 8`	`$v0 = 54`
1.15	Restore `$ra`	stack fully restored
1.16	`jr $ra`	returns to main

Back in `main`

Print "M = " → Print 54
Output: M = 54 ✓

Key Design Decisions Explained

1. Why save `$ra` in `comp_sum` but not in `square_div`?

comp_sum calls square_div using jal, which overwrites $ra with the return address back to comp_sum. If comp_sum doesn't save its own $ra (pointing back to main) before the jal, that address would be lost and the program could never return to main.

square_div is a leaf function — it makes no jal calls, so $ra is never overwritten while inside it. It safely uses jr $ra at the end without needing to save/restore it.

2. Why save `$a0`–`$a3` before calling `square_div`?

$a0–$a3 are caller-saved registers. By convention, the called function (square_div) is free to modify them. After square_div returns, comp_sum still needs c1, d0, and d1 to compute partial1 and sum2. Since we cannot guarantee those registers survived the call, comp_sum must save them on the stack beforehand and restore them afterwards.

3. Why save `$s0` and `$s1` in `square_div`?

$s0–$s7 are callee-saved registers. The calling function (comp_sum) trusts these registers to be unchanged after any function call. Since square_div uses $s0 and $s1 for its computation (it's not allowed to use $t registers per the constraints), it must save their original values on entry and restore them before returning.

4. How is `A[b]*7` computed without `mul`?

Not applicable here, but in square_div, the multiplication sum × sum uses the MIPS mult instruction (real instruction), not a pseudo-instruction. The result is read from the LO register via mflo.

5. Why use `$v1` for `partial1` in `comp_sum`?

The available registers in comp_sum are only $a0–$a3 and $v0–$v1. After the first call to square_div: - $v0 holds result1 (return value) - $a0–$a3 are restored to c0, c1, d0, d1

We compute partial1 = d0 + result1 and need to keep it alive across the second call to square_div. Storing it in $v1 (and saving $v1 to the stack before the second call) is the most natural choice given the register constraints.

6. Why is `parameters cannot be passed through stack` important?

MIPS convention allows up to 4 arguments in $a0–$a3. This lab enforces that rule strictly — both comp_sum and square_div receive all their inputs via argument registers, not via memory locations or the stack. This keeps the interface clean and hardware-efficient.

Expected Output

M = 54

— END OF LAB 05 ANSWERS —

ICO AY2526S2 — Lab 05 Answers & Solutions

Problem Overview

Program Architecture

Register Constraints

Calling Convention Rules

Stack Frame Diagrams

`comp_sum` stack usage

`square_div` stack usage

Complete MIPS Assembly Solution

Step-by-Step Execution Trace

In `main`

In `comp_sum` (first entry)

In `square_div` (1st call, sum=12, d=7)

Back in `comp_sum`

In `square_div` (2nd call, sum=14, d=8)

Back in `comp_sum`

Back in `main`

Key Design Decisions Explained

1. Why save `$ra` in `comp_sum` but not in `square_div`?

2. Why save `$a0`–`$a3` before calling `square_div`?

3. Why save `$s0` and `$s1` in `square_div`?

4. How is `A[b]*7` computed without `mul`?

5. Why use `$v1` for `partial1` in `comp_sum`?

6. Why is `parameters cannot be passed through stack` important?

Expected Output

Articoli correlati

Mobile Application Development CCIT4059

Mobile Application Development CCIT4059

COMSM1302 電腦架構概論四份模擬試卷完整詳解

COMSM1302 電腦架構概論卡諾圖化簡 15 題精練

COMSM1302 電腦架構概論 Sheet 1 完整詳解

COMSM1302 電腦架構概論第一週完整教材：數位邏輯基礎

Problem Overview

Program Architecture

Register Constraints

Calling Convention Rules

Stack Frame Diagrams

comp_sum stack usage

square_div stack usage

Complete MIPS Assembly Solution

Step-by-Step Execution Trace

In main

In comp_sum (first entry)

In square_div (1st call, sum=12, d=7)

Back in comp_sum

In square_div (2nd call, sum=14, d=8)

Back in comp_sum

Back in main

Key Design Decisions Explained

1. Why save $ra in comp_sum but not in square_div?

2. Why save $a0–$a3 before calling square_div?

3. Why save $s0 and $s1 in square_div?

4. How is A[b]*7 computed without mul?

5. Why use $v1 for partial1 in comp_sum?

6. Why is parameters cannot be passed through stack important?

Expected Output

Articoli correlati

Mobile Application Development CCIT4059

Mobile Application Development CCIT4059

COMSM1302 電腦架構概論四份模擬試卷完整詳解

COMSM1302 電腦架構概論卡諾圖化簡 15 題精練

COMSM1302 電腦架構概論 Sheet 1 完整詳解

COMSM1302 電腦架構概論第一週完整教材：數位邏輯基礎

`comp_sum` stack usage

`square_div` stack usage

In `main`

In `comp_sum` (first entry)

In `square_div` (1st call, sum=12, d=7)

Back in `comp_sum`

In `square_div` (2nd call, sum=14, d=8)

Back in `comp_sum`

Back in `main`

1. Why save `$ra` in `comp_sum` but not in `square_div`?

2. Why save `$a0`–`$a3` before calling `square_div`?

3. Why save `$s0` and `$s1` in `square_div`?

4. How is `A[b]*7` computed without `mul`?

5. Why use `$v1` for `partial1` in `comp_sum`?

6. Why is `parameters cannot be passed through stack` important?