Level 57: Nested Calls and the Stack

Open level →

Task

Goal: build a chain of nested calls: main calls funcA, funcA calls funcB, funcB calls funcC. The return through ra breaks under nesting — each call overwrites ra. The fix is the stack: a function frame saves ra to memory (prologue addi sp, sp, -4 / sw ra, 0(sp); epilogue lw ra, 0(sp) / addi sp, sp, 4 / ret). sp ≡ x2, starts at 0x1400 — the exclusive boundary above the stack 0x13C0–0x13FC. Cycle counts are NOT predicted here: the level introduces a lot at once — just build the program and match the golden. funcC is a leaf without a frame: 10; funcB adds 20, funcA adds 30; main stores the result into data 0x1000. The guard word 0x13BC is forbidden: reading or writing it is ERR_DATA_ADDRESS_FORBIDDEN with a frozen state.

The CPU schematic does not change: programs still run on the reference single-cycle core (risc-run) in the Assembler tab. What is new — the memory gets a map with a stack, and the program gets nested calls main → funcA → funcB → funcC.

The level memory map: program data — 0x1000–0x13B8; the guard word 0x13BC is forbidden for both reads and writes: any access stops the machine with ERR_DATA_ADDRESS_FORBIDDEN and no side effects; the stack — 0x13C0–0x13FC (16 words, grows down); the initial sp is 0x1400, the exclusive boundary above the stack. The address check order: multiple of 4 first, then the guard word, then the data window.

The canonical program is the "minimum: frames and the result in DMEM". funcC is a leaf without a frame: x10 = 10; funcB adds 20, funcA adds 30; main stores the result into data memory at 0x1000:

        li   sp, 0x1400      # the stack pointer (lui x2, 0x1 + addi x2, x2, 0x400)
        li   x5, 0x1000      # data base
        jal  ra, main        # the call
.end                      # halt at the return point
main:   addi sp, sp, -4      # the main frame
        sw   ra, 0(sp)
        jal  ra, funcA
        lw   ra, 0(sp)
        addi sp, sp, 4
        sw   x10, 0(x5)      # result 60 → 0x1000
        jalr x0, 0(ra)       # ret
funcA:  addi sp, sp, -4      # the funcA frame
        sw   ra, 0(sp)
        jal  ra, funcB
        lw   ra, 0(sp)
        addi sp, sp, 4
        addi x10, x10, 30
        jalr x0, 0(ra)
funcB:  addi sp, sp, -4      # the funcB frame
        sw   ra, 0(sp)
        jal  ra, funcC
        lw   ra, 0(sp)
        addi sp, sp, 4
        addi x10, x10, 20
        jalr x0, 0(ra)
funcC:  addi x10, x0, 10     # leaf: no frame
        jalr x0, 0(ra)

Level tasks:

  1. Write the header and the function bodies to match the canon bitwise: 28 cycles, x10 = 60 in memory at 0x1000, return to .end (PC = 20), ra = 20, sp = 0x1400.
  2. Watch the stack window in the Execution block: three saved ra values land in 0x13FC–0x13F4, the sp marker descends and climbs back.
  3. Negative: replace one store with sw x1, 0(x2) at x2 = 0x13BC — the machine must freeze with ERR_DATA_ADDRESS_FORBIDDEN, having changed neither memory nor registers.
  4. No cycle prediction on this level: it introduces a lot at once, so Check compares the run against the golden directly.

Try it (unchecked): rewrite funcA to call itself — a recursive fib no deeper than 5 frames. The 16-word stack will take it, and the trace will show frames growing and collapsing.

Solution for self-checking

Write the frames yourself first. The solution below is a checklist.

What you should get: the nested calls match the golden: 28 cycles, x10 = 60 and the word 0x1000 = 60, ra = 20, sp = 0x1400; the negative — sw into the guard word 0x13BC gives ERR_DATA_ADDRESS_FORBIDDEN with no memory or register changes.

Step 1 — prologue and epilogue. Prologue: addi sp, sp, -4, then sw ra, 0(sp). Epilogue: lw ra, 0(sp), then addi sp, sp, 4 and ret (that is jalr x0, 0(ra)). The order matters: read ra first, release the frame afterwards. A leaf (funcC) calls nobody — it needs no frame.

Step 2 — cycles. Header: lui + addi + li (2 words) + jal = 5; main — 7 instructions; funcA — 7; funcB — 7; funcC — 2. Total 5 + 7 + 7 + 7 + 2 = 28; the .end halt adds no cycle, the PC freezes at 20.

Step 3 — checking the state. Final: x10 = 60 (10 + 20 + 30), the word at 0x1000 = 60, x1 = 20 (the return address into main), x2 = 0x1400 (the stack is balanced). The stack words 0x13FC/0x13F8/0x13F4 stay "dirty" — a frame is released by the pointer, not by clearing; the comparison mask only looks at the data region 0x1000–0x13B8.

Step 4 — the "ra restore removed" mutant. Remove lw ra from funcA: by the time B returns, ra still points to the return from B into A. The A epilogue runs again — and jumps through the same ra again. The PC spins in a circle, and the program never reaches the halt (the core hits the cycle limit). This is not a catalog error: jalr trusts the register, not the stack.

Step 5 — the guard word. li x2, 0x13BC and sw x1, 0(x2): the multiple of 4 is fine, but the address is in the forbidden zone — a freeze with ERR_DATA_ADDRESS_FORBIDDEN, memory and registers unchanged. The check order matters: 0x13BE first trips the alignment check (ERR_DATA_ADDRESS_MISALIGNED), and only an aligned access reaches the guard-zone check.

Check yourself

Why does ra without saving break at the very first nesting?

Every jal overwrites ra: by the time funcA returns, ra holds the return address from funcB, and the A epilogue spins in a loop until the cycle limit. The frame saves ra to memory and restores it before ret — jalr trusts the register, not the stack.