3-3 `bubbleSort` Prolog · RO Probeklausur

왜 이 소문제를 따로 배우는가

함수 call 경계는 register 값의 생존 규칙이 바뀌는 지점입니다. loop state를 caller-saved a/t register에 그대로 두면 `swap` 호출 뒤 사라질 수 있고, s-register를 쓰면서 원래 값을 저장하지 않으면 caller의 상태를 깨뜨립니다.

이 페이지는 Aufgabe 3의 공통 템플릿이 아니라 3-3 `bubbleSort` Prolog에 필요한 내용만 담습니다. 챕터 전체 배경이 필요하면 Aufgabe 3 개념 수업을 먼저 읽으세요.

이 소문제에서 실제로 쓰는 용어

정의뿐 아니라 이 문제의 어느 판단에 쓰이는지까지 연결합니다.

Prolog: 함수 시작에서 stack frame을 만들고 보존할 register를 저장하는 instruction 묶음입니다.이 소문제에서: `addi sp,sp,-32` 뒤 ra와 s0–s3를 저장합니다.
callee-saved register: 함수가 사용하면 반환 전에 원래 값을 복원해야 하는 s-register입니다.이 소문제에서: arr, n, i, j를 swap 호출 뒤에도 유지하려고 s0–s3에 두고 기존 값을 stack에 보존합니다.
ra: jal이 `PC+4`를 기록하는 return address register x1입니다.이 소문제에서: bubbleSort가 swap을 호출하면 자신의 caller로 돌아갈 ra가 덮이므로 stack에 저장합니다.
stack alignment: ABI call boundary에서 sp가 요구된 배수, 여기서는 16 Byte에 맞는 조건입니다.이 소문제에서: 실사용 20 Byte를 그대로 -20 하지 않고 32-Byte frame을 선택합니다.

이 소문제 전용 규칙과 종이 작업

call 뒤 생존성 규칙

호출 뒤에도 필요한 값은 caller-saved a/t register에만 의존하지 말고 s-register 또는 stack에 보존합니다.

종이에: 각 variable 옆에 `swap 뒤 필요?`를 표시하고 필요하면 s0–s3에 배정합니다.

callee-saved 대칭 규칙

bubbleSort가 s0–s3를 자신의 값에 사용하려면 incoming 원래 s0–s3를 Prolog에서 저장하고 Epilog에서 복원해야 합니다.

종이에: 저장 목록과 복원 목록을 같은 순서의 표로 만듭니다.

frame round-up 규칙

저장 data가 20 Byte여도 sp alignment를 유지하도록 frame 크기를 다음 16의 배수인 32 Byte로 올립니다.

종이에: `5 regs×4=20 → round up 32` 계산을 남깁니다.

Aufgabe 전체 흐름은 챕터 흐름도에서 확인할 수 있습니다. 여기서는 현재 판단에 직접 필요한 규칙만 적용합니다.

이 소문제 전용 작은 예제

함수 f가 다른 함수를 호출하며 ra, s0, s1을 사용한다. RV32에서 16-Byte alignment를 지키는 최소 Prolog를 작성하세요.

주어진 것

register 하나는 4 Byte입니다.
기존 ra, s0, s1을 보존해야 합니다.

필요 저장 공간을 계산하고 frame을 round up합니다.
3×4=12 Byte지만 sp는 16의 배수만큼 이동해야 합니다.

종이 산출물: `12 Byte → frame 16 Byte`
sp를 먼저 감소시킵니다.
새 frame 안의 유효한 주소를 만든 뒤 store해야 합니다.

종이 산출물: `addi sp,sp,-16`
서로 겹치지 않는 offset에 세 register를 저장합니다.
각 원본을 Epilog에서 독립적으로 복원할 수 있어야 합니다.

종이 산출물: `sw ra,0(sp); sw s0,4(sp); sw s1,8(sp)`

예제 답과 독립 검산 보기

`addi sp,sp,-16; sw ra,0(sp); sw s0,4(sp); sw s1,8(sp)`입니다.

독립 검산: 사용 offset 0,4,8이 frame `0…15` 안에 있고 새 sp도 16-Byte aligned인지 확인합니다.

이제 실제 시험 문제를 micro-work로 풀기

공식 시험이 요구하는 것

swap을 부르기 전에 무엇을 stack에 저장해야 하나요?

공식 답을 보기 전, 내 답 먼저 남기기

완성 문장이 아니어도 좋습니다. 중간값·register·cycle·cache state처럼 채점 가능한 흔적을 먼저 적으세요.

내 풀이 또는 예상 답

각 작업의 중간 산출물을 직접 적고 완료 조건을 만족한 뒤 체크하세요. 단계별 이유·산출물·오류가 현재 소문제에 맞게 따로 작성되어 있습니다.

Micro-work 3-3.1 · 완료 표시

ra와 s0–s3 저장에 필요한 공간을 계산하고 32-Byte frame을 선택합니다.

왜 하는가: 5개 register는 20 Byte지만 call boundary의 16-Byte sp alignment를 유지해야 합니다.
종이 산출물: `5×4=20; align16 → frame=32; addi sp,sp,-32`
완료 조건: frame 크기 32와 선택 근거가 모두 적혀 있습니다.

내 중간 산출물

막혔을 때 단계 힌트·대표 오류

힌트: 20 이상인 가장 작은 16의 배수를 찾으세요.

이 단계의 대표 오류: `addi sp,sp,-20`으로 필요한 Byte만 정확히 빼 alignment를 깨는 것입니다.

Micro-work 3-3.2 · 완료 표시

ra와 기존 s0–s3를 새 stack frame에 저장합니다.

왜 하는가: swap 호출은 ra를 덮고 bubbleSort가 사용하는 s-register는 caller에게 원래 값으로 돌려줘야 합니다.
종이 산출물: `sw ra,0(sp); sw s0,4(sp); sw s1,8(sp); sw s2,12(sp); sw s3,16(sp)`
완료 조건: 다섯 register가 겹치지 않는 4-Byte offset에 한 번씩 저장되어 있습니다.

내 중간 산출물

막혔을 때 단계 힌트·대표 오류

힌트: sp를 감소시킨 뒤의 새 sp를 기준으로 offset을 쓰세요.

이 단계의 대표 오류: 새 s0 값을 먼저 쓴 뒤 원래 s0를 저장해 caller 값이 사라지는 것입니다.

Micro-work 3-3.3 · 완료 표시

입력 arr와 n을 a0/a1에서 s0/s1으로 옮깁니다.

왜 하는가: swap 호출 뒤에도 전체 sorting 동안 필요한 값은 caller-saved argument register에만 둘 수 없습니다.
종이 산출물: `mv s0,a0 # arr; mv s1,a1 # n`
완료 조건: variable map에 s0=arr, s1=n이 표시되어 있습니다.

내 중간 산출물

막혔을 때 단계 힌트·대표 오류

힌트: a0–a2는 swap argument를 놓을 때 덮일 예정입니다.

이 단계의 대표 오류: arr와 n을 계속 a0/a1에서 읽어 swap 호출 후에도 유지된다고 가정하는 것입니다.

Micro-work 3-3.4 · 완료 표시

바깥 loop index i를 s2=0으로 초기화합니다.

왜 하는가: i는 여러 swap 호출과 inner loop를 거쳐 살아야 하므로 callee-saved register에 둡니다.
종이 산출물: `li s2,0 # i=0`
완료 조건: s2의 의미와 초기값 0이 register map에 있습니다.

내 중간 산출물

막혔을 때 단계 힌트·대표 오류

힌트: 공식 register 배정에서 s3는 inner index j에 사용됩니다.

이 단계의 대표 오류: i를 t-register에 두고 swap이 보존해 줄 것이라 믿는 것입니다.

공식 답을 열기 전 마지막 회상

왜 swap을 호출하지 않는 leaf function은 ra를 저장하지 않아도 될 수 있나요?

내 설명

내 풀이 후 공식 결론·이유·대표 함정 확인

공식 결론

공식안: `addi sp,sp,-32`, `sw ra,0(sp)`, `sw s0,4(sp)` … `sw s3,16(sp)`, 그 뒤 s0=arr, s1=n, s2=0.

왜 이 답이 되는가

`jal`은 ra를 덮고 caller-saved t/a register는 보존되지 않습니다. bubbleSort의 arr,n,i,j는 swap 뒤에도 필요하므로 s0–s3에 두고, callee인 bubbleSort가 원래 s-register 값을 저장합니다.

대표 함정

저장할 값은 20 Byte지만 frame을 -20으로 만들면 16-byte alignment가 깨집니다.

명령어와 식을 줄 단위로 읽기

본문 속 code를 한 줄씩 분리했습니다. 각 줄에서 source, operation, destination을 표시하세요.

jal
addi sp,sp,-32
sw ra,0(sp)
sw s0,4(sp)
sw s3,16(sp)

새 문제로 전이하기

세 문항은 앞 문장의 반복이 아닙니다. 직접 답을 입력하면 rubric의 필수 기준을 하나씩 검사하고, 첫 누락 기준을 알려 줍니다.

1. 개념 재구성

non-leaf 함수가 ra를 저장해야 하는 이유와 s-register의 저장/복원 책임을 caller-saved a/t와 비교해 설명하세요.

내 답

제출 후 모델 답 보기

non-leaf 함수가 jal로 다른 함수를 호출하면 ra가 새 `PC+4`로 덮이므로 자신의 caller에게 돌아갈 ra를 저장해야 합니다. s-register는 callee-saved라 사용한 함수가 원래 값을 저장/복원합니다. a/t는 caller-saved라 호출 뒤 필요한 값은 caller가 미리 s-register나 stack으로 옮겨야 합니다.

2. 변형 문제

함수 g가 다른 함수를 호출하고 ra, s0, s1, s2를 보존해야 한다. RV32, 16-Byte alignment에서 최소 frame 크기와 Prolog store를 작성하세요.

내 답

제출 후 모델 답 보기

4개 register는 16 Byte이므로 frame은 16 Byte입니다. Prolog는 `addi sp,sp,-16; sw ra,0(sp); sw s0,4(sp); sw s1,8(sp); sw s2,12(sp)`입니다.

3. 오류 진단

학생 Prolog는 `addi sp,sp,-20` 뒤 ra와 s0–s3를 저장합니다. 모든 store가 frame 안인데도 ABI 관점에서 첫 오류가 무엇인지, 올바른 frame은 얼마인지 쓰세요.

내 답

제출 후 모델 답 보기

첫 오류는 frame이 충분한지만 보고 16-Byte stack alignment를 무시한 것입니다. -20은 새 sp를 16의 배수 경계에서 벗어나게 하므로 20 Byte를 다음 배수로 round up한 32-Byte frame, 즉 `addi sp,sp,-32`를 사용해야 합니다.

이 소문제를 끝냈다고 말할 수 있는 기준

call 뒤에도 살아야 하는 각 variable을 caller/callee-saved 규칙에 따라 배치할 수 있다. 저장 register 수로 필요한 Byte를 계산하고 16-Byte aligned frame으로 올릴 수 있다.

이 소문제의 정확한 공식 페이지와 대조하기

왼쪽은 문제를 읽을 때, 오른쪽은 자신의 풀이를 끝낸 뒤에 확인하세요. 해설 이미지를 먼저 보면 중간 과정을 스스로 만드는 연습이 사라집니다.

3-3 관련 공식 시험 또는 해설 페이지 — exam-p07.png · 클릭해 원본 크기로 확인

Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p7–8 · 공식 해설 p8–11 · SoSe26 Probeklausur 시험 p7 Aufgabe 3 `bubbleSort` Prolog 요구와 공식 해설 p9의 32-Byte frame·ra/s0–s3 저장·초기 register 배정 범위.