yeolyi.com성열의 컴퓨터공학

메모리에 빵 부스러기 남기기

스택 포인터

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

같은 명령어 묶음을 프로그램 여러 곳에서 써야 할 때, 쓰는 곳마다 그대로 복사해 넣을 수도 있습니다. 이를 펼쳐 넣기(inline)라 합니다. 쉽지만 쓰는 곳이 늘수록 프로그램이 그만큼 길어집니다.

호출과 복귀에서 본 CALL과 RET를 쓰면, 묶음은 한 번만 적어 두고 쓸 때마다 다녀오면 됩니다. CALL은 돌아올 주소를 R3에 적고 묶음으로 점프하고, RET는 R3에 적힌 주소로 돌아옵니다. 이렇게 불러 쓰는 명령어 묶음을 함수(function)라 합니다. 그런데 함수 안에서 또 CALL하면 어떻게 될까요?

0LDI R0, 1
1CALL 3
2HALT
3CALL 5
4RET
5ADDI R0, 1
6RET
R00
R30

주소 0부터 실행합니다.

3번의 CALL이 R3에 적힌 돌아올 주소 2를 4로 덮어써, 4번의 RET가 제자리로만 돌아갑니다.

스택

돌아올 주소를 덮어쓰지 말고 하나씩 쌓아 두었다가, 돌아갈 때는 가장 나중에 쌓은 것부터 꺼내면 됩니다. 이렇게 넣은 순서의 반대로 꺼내는 구조를 스택(stack)이라 합니다. 메모리 맨 끝인 255번 주소부터 쌓고, 지금 맨 위 칸의 주소는 새 레지스터 SP에 적어 둡시다. 이를 스택 포인터(stack pointer)라 합니다. 포인터처럼 주소를 담아서 붙은 이름입니다.

메모리 끝 칸
255
254
253
252
251
250
SP0
꺼낸 값

SP = 0, 스택이 비어 있습니다.

  1. PUSH를 세 번 누른 뒤 POP을 눌러 봅시다. 마지막에 넣은 3이 먼저 나옵니다.
  2. 넣을 때마다 SP가 하나씩 줄어, 255번부터 주소가 작아지는 쪽으로 쌓입니다.
  3. 꺼낸 칸의 값은 지워지지 않고 흐리게 남습니다. POP은 SP만 하나 늘리고 값은 그대로 두니, 그 칸은 다음 PUSH 때 덮어써집니다.

프로그램과 변수는 0번 주소부터 차지하니, 반대편 끝에서 쌓으면 서로 멀리 떨어집니다. 메모리는 주소가 큰 칸을 위에 그리는 일이 많아, 이렇게 주소가 작아지는 쪽으로 쌓는 것을 흔히 스택이 아래로 자란다고 합니다.

PUSH와 POP

데모에서 한 일을 명령어 둘로 기계에 더합시다. 레지스터의 값을 넣고 꺼내며, 아래 R0 자리에는 어느 레지스터든 쓸 수 있습니다.

SP가 0이면 스택이 비어 있다는 뜻입니다. 0에서 하나 줄이면 255가 되니 첫 PUSH는 255번 주소에 들어갑니다.

스택을 쓰는 CALL과 RET

이제 CALL과 RET가 돌아올 주소를 R3 대신 스택에 두도록 바꿉시다.

함수 안에서 또 CALL하면 돌아올 주소가 그 위에 쌓이고, 안쪽의 RET가 맨 위의 주소를 먼저 꺼내 갑니다. 바깥 함수의 돌아올 주소는 그 아래에 그대로 남아 있다가 바깥의 RET가 꺼내 씁니다. R3에는 더는 돌아올 주소를 적지 않으니, 다른 레지스터처럼 값을 담는 데 씁니다.

어셈블리어
0–1LDI R0, 1
2–3CALL f
4–5HALT
6–7f: CALL g
8–9RET
10–11g: ADDI R0, 1
12–13RET
R0 0R1 0R2 0R3 0SP 0Z 0
스택
비어 있음

앞의 프로그램을 바뀐 CALL과 RET로 돌려 봅시다. 돌아올 주소 4와 8이 스택에 쌓였다가 차례로 빠지고, 이번에는 HALT에 닿습니다.

도전 문제

SP가 0일 때 아래 프로그램을 0번 주소부터 실행합니다. 실행하는 동안 SP가 가장 작을 때는 얼마일까요? 숫자로 답하세요.

   CALL f
   HALT
f: PUSH R0
   PUSH R1
   POP R1
   POP R0
   RET