Full beginner lecture
RISC-V ABI and Stack
Intuition
ABI는 함수들이 서로 깨뜨리지 않고 협력하기 위한 약속입니다. caller는 argument를 a0-a7에 놓고 jal로 callee를 부릅니다. callee는 결과를 a0에 놓고 ret으로 돌아갑니다. 문제는 register가 모두 공유 자원이라는 점입니다. 그래서 누가 어떤 register를 저장하고 복구할지 정한 규칙이 필요합니다.
Rule
a0-a7과 t0-t6는 caller-saved입니다. call 이후에도 값이 필요하면 caller가 저장합니다. s0-s11은 callee-saved입니다. callee가 사용하면 원래 값으로 복구해야 합니다. ra는 jal이 쓰는 return address register입니다. 함수 안에서 다시 jal을 실행하는 non-leaf function은 자기 caller로 돌아갈 ra를 stack에 저장해야 합니다.
Stack은 보통 낮은 address 방향으로 자랍니다. frame을 만들 때 addi sp, sp, -N, 없앨 때 addi sp, sp, N을 씁니다. return 직전 sp는 entry 때의 값과 같아야 합니다.
Visual Block
higher address
old sp -> caller frame
12(sp): saved ra
8(sp): saved s0
4(sp): local or spill
new sp -> 0(sp): local or spill
lower address
caller flow
put args in a0-a7
save needed caller-saved values
jal callee
callee flow
make stack frame
save used s-registers and needed ra
compute result in a0
restore saved values
restore sp
ret
Worked Example 1
Problem. Function foo uses s0 and calls bar. What must it save.
s0 is callee-saved, so foo must save and restore it.foo calls another function, so jal bar will overwrite ra.foo still needs its original ra to return to its caller.- A clean 16-byte frame is:
foo:
addi sp, sp, -16
sw ra, 12(sp)
sw s0, 8(sp)
...
jal bar
...
lw s0, 8(sp)
lw ra, 12(sp)
addi sp, sp, 16
ret
Worked Example 2
Problem. main has an important value in t0 and calls calc. It needs t0 after the call.
t0 is caller-saved.calc may freely use t0.- Therefore
main, not calc, must save t0 before jal calc. - Example:
addi sp, sp, -16
sw t0, 12(sp)
jal calc
lw t0, 12(sp)
addi sp, sp, 16
C-String: Nullterminator와 byte trace
입문 설명
C의 String은 별도의 length field가 붙은 object가 아니라, 연속된 char byte 뒤에 값 0x00을 놓아 끝을 표시하는 경우가 기본입니다. 이 마지막 byte가 Nullterminator입니다.
".string \"RO\"" at base 0x2000
address byte meaning
0x2000 0x52 'R'
0x2001 0x4F 'O'
0x2002 0x00 Nullterminator
String length는 실제 문자 수이므로 terminator를 세지 않습니다. char는 1 byte이기 때문에 str+i의 address는 base+i입니다. RISC-V에서는 문자 하나를 읽을 때 lbu, 쓸 때 sb를 사용합니다. lw로 4 byte씩 읽는 최적화는 이 입문 trace의 범위가 아닙니다.
Übung 3의 str_length 핵심은 다음과 같습니다.
str_length:
addi t0, zero, 0 # len = 0
loop:
add t1, a0, t0 # &str[len]
lbu t1, 0(t1) # current byte
beq t1, zero, done # 0x00이면 끝
addi t0, t0, 1
j loop
done:
addi a0, t0, 0 # return len
jr ra
Worked Trace: "RO\0"의 길이
초기 상태는 a0=0x2000, t0=0이고 위 memory byte를 사용합니다.
| iteration | t0 | 계산한 address | lbu 값 | branch | 다음 상태 |
|---|
| 1 | 0 | 0x2000 | 0x52 | not taken | t0=1 |
| 2 | 1 | 0x2001 | 0x4F | not taken | t0=2 |
| 3 | 2 | 0x2002 | 0x00 | taken to done | a0=2 |
정답·검산 확인
return length는 2, 첫 terminator 주소는 **0x2002**입니다. 검산은 nonzero byte가 정확히 두 개이고 0x00은 세지 않았는지 확인하는 것입니다.
변형 문제
0x3000부터 byte가 0x41, 0x00, 0x42, 0x00 순서라면 같은 str_length(0x3000)의 반환값과 종료 주소는 무엇인가요?
정답·검산 확인
첫 byte 0x41='A'만 센 뒤 0x3001의 0x00에서 멈추므로 반환값은 1, 종료 주소는 **0x3001**입니다. 뒤의 0x42는 memory에 존재하지만 이 C-String의 일부가 아닙니다.
Active Recall
Q1. "Hi"를 .string으로 저장하면 최소 몇 byte가 필요한가요?
정답 확인
H, i, 0x00의 3 byte입니다.
Q2. 왜 str_length가 terminator를 length에 더하지 않나요?
정답 확인
terminator는 실제 문자 데이터가 아니라 끝을 표시하는 marker이기 때문입니다.
Q3. char *p에서 p+3은 base에서 몇 byte 떨어진 주소인가요?
정답 확인
char 하나가 1 byte이므로 base+3 byte입니다.
Q4. lbu 뒤 현재 byte가 zero일 때 counter를 먼저 증가시키면 어떤 오류가 나나요?
정답 확인
Nullterminator까지 문자로 세어 length가 1 크게 나옵니다.
근거: current:Vorlesung\Rechnerorganisation - Teil 1.pdf, pages 67-69; current:Uebung\Übung 3 Musterlösung.pdf, pages 4-7.
Rekursion: call마다 독립적인 Stack Frame
입문 설명
재귀 함수는 “자기 자신 한 개가 여러 번 움직이는 것”이 아니라, 아직 끝나지 않은 호출들이 각각 자기 argument와 return address를 가진 채 겹쳐 있는 상태입니다. 같은 a0와 ra register를 다음 recursive call도 다시 쓰므로, 현재 호출이 나중에 필요로 하는 값은 자기 Stack Frame에 저장해야 합니다.
Vorlesung의 factorial 예는 호출마다 8 byte를 사용합니다.
0(sp): saved ra
4(sp): saved n (old a0)
non-base call은 n-1로 jal factorial을 실행합니다. child가 a0=factorial(n-1)을 반환하면 parent는 자기 frame의 saved n을 불러 n * a0를 계산하고, saved ra와 sp를 복구합니다.
Worked Trace: factorial(3), initial sp=0x1000
정확한 machine-code address 대신 return address를 의미가 분명한 기호로 둡니다: Rcaller는 factorial을 부른 상위 함수로 돌아갈 주소, R3와 R2는 각각 factorial(3)과 factorial(2)의 recursive jal 다음 주소입니다.
내려갈 때
| active call | allocation 뒤 sp | 0(sp) saved ra | 4(sp) saved n |
|---|
factorial(3) | 0x0FF8 | Rcaller | 3 |
factorial(2) | 0x0FF0 | R3 | 2 |
factorial(1) | 0x0FE8 | R2 | 1 |
factorial(1)은 base case라 a0=1로 만들고 자기 8-byte frame을 해제하여 sp=0x0FF0으로 돌아갑니다. 이 호출은 내부 jal을 하지 않았으므로 현재 ra=R2로 parent에게 돌아갈 수 있습니다.
올라올 때
factorial(2)는 4(sp)에서 old n=2를 읽고 child result a0=1과 곱해 a0=2를 만듭니다.0(sp)의 R3를 ra에 복구하고 frame을 해제하여 sp=0x0FF8로 돌아갑니다.factorial(3)는 자기 4(sp)에서 old n=3을 읽고 child result a0=2와 곱해 a0=6을 만듭니다.Rcaller를 복구하고 frame을 해제하여 최종 sp=0x1000으로 돌아갑니다.
정답·검산 확인
최대 동시 frame은 3개, 가장 깊은 sp는 **0x0FE8, 최종 결과는 a0=6, 최종 stack pointer는 초기값과 같은 0x1000**입니다.
검산 invariant:
호출 깊이 d에서 sp = SP0 - 8*d
return할 때마다 sp += 8
각 parent는 자기 frame의 n과 ra만 복구
최종 sp = SP0
변형 문제
같은 구현으로 factorial(2)를 sp=0x8000에서 시작합니다. 최대 동시 frame 수, 가장 깊은 sp, 최종 a0와 sp를 구하세요.
정답·검산 확인
active call은 factorial(2)와 base case factorial(1)의 2개입니다. 두 번 8 byte를 할당하므로 가장 깊은 sp=0x7FF0입니다. unwind 뒤 a0=2*1=2, sp=0x8000입니다.
Active Recall
Q1. recursive call 전에 현재 n을 stack에 저장해야 하는 이유는 무엇인가요?
정답 확인
child 호출이 argument/return value용 a0를 덮지만 parent가 child 반환 뒤 old n을 곱셈에 다시 써야 하기 때문입니다.
Q2. 왜 모든 active call이 서로 다른 saved ra를 가져야 하나요?
정답 확인
각 call은 서로 다른 jal 다음 위치로 돌아가야 하며, 다음 recursive jal이 현재 ra를 덮기 때문입니다.
Q3. base case도 frame을 만들었다면 return 전에 무엇을 반드시 해야 하나요?
정답 확인
자신이 할당한 크기만큼 sp를 복구해야 합니다. 내부 call이 없었다면 저장한 ra를 다시 load하는 것은 불필요할 수 있어도 stack 해제는 필요합니다.
Q4. recursion trace에서 최종 결과만 맞고 sp가 SP0-8이면 올바른가요?
정답 확인
아닙니다. ABI invariant를 깨서 caller의 stack 상태를 손상하므로 sp는 반드시 진입 값으로 돌아와야 합니다.
근거: current:Vorlesung\Rechnerorganisation - Teil 1.pdf, pages 85-87; current:Uebung\Übung 3.pdf, page 4와 current:Uebung\Übung 3 Musterlösung.pdf, pages 7-9.
Common Mistakes
- Believing the callee restores every register. It only must preserve callee-saved registers it uses.
- Forgetting to save
ra in a non-leaf function. - Restoring
sp before loading saved values from the current frame. - Overwriting
a0 return value during epilogue. - String의
0x00을 length에 포함하거나, 그 뒤 byte까지 계속 읽습니다. 첫 Nullterminator에서 즉시 멈춥니다. - 모든 recursive call이 같은 stack slot을 쓴다고 그립니다. 각 call은 먼저
sp를 내리므로 address가 다른 자기 frame을 가집니다.
Active Recall
- Which registers carry the first arguments and return value.
- Who saves
s0 if a function uses it. - Who saves
t0 if caller needs it after a call. - Why does recursion need a stack frame per call.
Source Grounding
current:Vorlesung\Rechnerorganisation - Teil 1.pdf, pages 67-69: ASCII, char-array/String, 0x00 Endemarker, lbu와 sb.current:Vorlesung\Rechnerorganisation - Teil 1.pdf, pages 73-87: Unterprogrammaufruf, register preservation, stack growth와 recursive factorial frame trace.current:Uebung\Übung 3.pdf, pages 1-4와 current:Uebung\Übung 3 Musterlösung.pdf, pages 1-9: ABI, stack frames, str_length, str_reverse, Fibonacci recursion.current:Uebung\RISC-V Reference.pdf, pages 1-2: ABI register table and saver responsibilities.