주소지정·스택·호출

명령어에 100이라는 수가 적혀 있어도, "100을 더하라"는 뜻일 수도 있고 "주소 100에 든 값을 더하라"는 뜻일 수도 있습니다. 명령어가 피연산자의 값을 어디서 어떻게 찾을지 정한 규칙을 주소 지정 방식(addressing mode)이라고 합니다. 이 글에서는 명령어 집합과 프로그램 실행의 작은 CPU에서 한 가지뿐이던 메모리 접근을 여러 방식으로 넓히고, 배열과 함수 호출에서 주소를 어떻게 계산하는지 다룹니다.

유효 주소를 계산한다

주소 지정 방식에 따라 실제로 접근하게 되는 데이터의 주소를 유효 주소(effective address, EA)라고 합니다. 아래 표에서는 R1 = 100, R2 = 3, M[100] = 40, M[40] = 9, M[104] = 15, M[112] = 8이라고 하겠습니다. 표기는 이 교재에서 정한 것이며, 모든 CPU가 이 방식들을 모두 지원하는 것은 아닙니다.

대괄호를 한 겹 씌울 때마다 그 안의 값을 주소로 보고 메모리를 한 번 더 읽는다고 생각하면 됩니다. 즉시 방식과 레지스터 방식은 메모리를 읽지 않고, 직접과 레지스터 간접은 한 번, 간접은 두 번 읽습니다. 레지스터 간접에서 R1의 100은 데이터가 아니라 데이터가 있는 곳을 가리키는 주소로 쓰였는데, C++ 교재의 포인터 기초에서 다루는 포인터가 바로 이런 값입니다.

memory = {100: 40, 40: 9, 104: 15, 112: 8}
r1, r2 = 100, 3
print(100, memory[100], memory[memory[100]], r1, memory[r1], memory[r1 + 4], memory[r1 + r2 * 4])


class Stack:
    def __init__(self, top=64):
        self.sp, self.memory = top, {}

    def push(self, value):
        self.sp -= 4
        self.memory[self.sp] = value

    def pop(self):
        value = self.memory[self.sp]
        self.sp += 4
        return value


stack = Stack()
stack.push(10)
stack.push(20)
print(stack.sp, stack.memory)
print(stack.pop(), stack.pop(), stack.sp)

for op, pc, target in [("CALL", 10, 30), ("CALL", 32, 50), ("RET", 51, None), ("RET", 33, None)]:
    if op == "CALL":
        stack.push(pc + 1)
        print(f"{pc}: CALL {target} -> 복귀 주소 {pc + 1} 저장, SP={stack.sp}")
    else:
        print(f"{pc}: RET -> 복귀 주소 {stack.pop()}, SP={stack.sp}")

100 40 9 100 40 15 8
56 {60: 10, 56: 20}
20 10 64
10: CALL 30 -> 복귀 주소 11 저장, SP=60
32: CALL 50 -> 복귀 주소 33 저장, SP=56
51: RET -> 복귀 주소 33, SP=60
33: RET -> 복귀 주소 11, SP=64

첫 줄은 표의 일곱 방식을 차례로 계산한 값입니다. memory[memory[100]]이 간접 방식처럼 메모리를 두 번 읽는 모습이고, memory[r1 + r2 * 4]가 인덱스 방식입니다. 나머지 줄은 아래 두 절에서 설명합니다.

PC 상대(PC-relative) 방식은 PC를 기준으로 변위를 더해 주소를 정하며, 주로 분기할 위치를 적을 때 씁니다. 프로그램이 메모리의 어디에 놓이든 명령어 사이의 거리는 같으므로, PC 상대로 적은 분기는 프로그램을 옮겨도 그대로 맞습니다. 다만 기준이 되는 PC가 지금 명령어의 주소인지, 이미 다음 명령어로 넘어간 주소인지는 ISA마다 다릅니다. RISC-V는 분기 명령어 자신의 주소를, x86은 다음 명령어의 주소를 기준으로 하므로, 같은 변위라도 도착하는 곳이 한 명령어만큼 달라질 수 있습니다.

배열과 스택으로 보는 주소 계산

원소 하나가 4바이트인 배열이 주소 100부터 놓여 있으면, 번호가 3인 원소의 주소는 100 + 3 × 4 = 112입니다. 번호 3을 그대로 더해 103으로 계산하면, 원소 하나가 1바이트가 아니므로 원소의 중간을 가리키게 됩니다. 인덱스 방식이 번호에 원소 크기를 곱해 더하는 것도 이 때문이며, 원소 번호와 바이트 주소는 단위가 다르다는 점을 늘 구별해야 합니다.

스택(stack)은 나중에 넣은 것을 먼저 꺼내는 저장 방식(last in, first out, LIFO)입니다. CPU는 스택의 맨 위 주소를 스택 포인터(stack pointer, SP)라는 레지스터에 두고, 함수의 인수, 지역 변수, 잠시 보관할 레지스터 값, 돌아올 주소를 스택에 저장합니다. 이 교재의 모델에서는 빈 스택의 SP가 64이고, 4바이트 값을 넣을(push) 때 SP를 4 줄인 뒤 그 주소에 쓰며, 꺼낼(pop) 때 그 주소에서 읽은 뒤 SP를 4 늘립니다. 스택이 주소가 작아지는 쪽으로 자라는 셈인데, 실제 CPU의 방향, 정렬, 호출 규칙은 ABI(application binary interface)라는 별도의 약속으로 정해집니다.

코드의 둘째 줄은 10과 20을 넣은 뒤의 모습으로, SP가 56이고 주소 60에 10, 주소 56에 20이 있습니다. 셋째 줄에서 두 번 꺼내면 나중에 넣은 20이 먼저 나오고 SP는 64로 돌아옵니다. 꺼낸 자리의 값은 지워지지 않고 남아 있지만, SP가 그 위로 올라갔으므로 더는 스택의 일부가 아닙니다.

함수 호출과 돌아올 주소

함수를 호출하려면 함수의 첫 명령어로 이동하는 것뿐 아니라, 함수가 끝난 뒤 어디로 돌아올지도 저장해야 합니다. 호출 명령어(CALL) 바로 다음 명령어의 주소를 복귀 주소(return address)라 하고, CALL은 이것을 저장한 뒤 함수로 분기하며, 복귀 명령어(RET)는 저장해 둔 주소로 돌아갑니다. 함수 안에서 다시 다른 함수를 부르는 중첩 호출에서는 복귀 주소가 여러 개 필요하고, 가장 나중에 저장한 것을 가장 먼저 써야 하므로 스택이 꼭 맞습니다.

코드의 마지막 네 줄이 중첩 호출입니다. 주소 10의 CALL이 복귀 주소 11을 넣고 30에서 시작하는 함수로 가고, 그 함수가 주소 32에서 다시 CALL로 복귀 주소 33을 넣고 50의 함수로 갑니다. 안쪽 함수의 RET는 나중에 넣은 33을 꺼내 바깥 함수로 돌아가고, 바깥 함수의 RET는 11을 꺼내 처음 호출한 곳으로 돌아갑니다. 복귀 주소를 레지스터 하나에만 저장한다면 안쪽 호출이 바깥 호출의 복귀 주소를 덮어써, 바깥 함수는 돌아갈 곳을 잃게 됩니다.

더 깊이: 복귀 주소를 레지스터에 두는 RISC-V

이 교재 모델의 CALL은 복귀 주소를 스택에 넣지만, RISC-V는 다르게 합니다. RISC-V의 기본 정수 명령어 규격에 따르면 jal은 다음 명령어의 주소인 pc+4를 목적 레지스터에 저장하고 분기하며, 표준 호출 규약은 x1을 복귀 주소 레지스터로 씁니다. 함수에서 돌아갈 때는 그 레지스터가 가리키는 곳으로 건너뛰는 jalr을 씁니다. 그래서 다른 함수를 부르지 않는 함수는 복귀 주소를 메모리에 쓰지 않고 레지스터에서 바로 꺼내 돌아갈 수 있습니다.

대신 앞에서 본 덮어쓰기 문제는 소프트웨어가 막아야 합니다. 다른 함수를 부르는 함수에서는 안쪽의 jal이 x1을 덮어쓰므로, 그 전에 x1을 스택에 저장해 두었다가 돌아가기 직전에 되살려야 합니다. 중첩 호출에 스택이 필요하다는 점은 같고, 그 저장을 하드웨어의 호출 명령이 하느냐 컴파일러가 만든 코드가 하느냐가 다를 뿐입니다.

규격은 고성능 CPU가 복귀 주소를 미리 짐작하는 데 쓰는 복귀 주소 예측 스택(return-address stack)을 위한 약속도 둡니다. 따로 힌트 비트를 두지 않고, 예를 들어 jal의 목적 레지스터가 x1이나 x5일 때만 복귀 주소를 예측 스택에 넣는 식으로 레지스터 번호 자체를 힌트로 씁니다. 명령어 형식의 자리를 아끼려는 선택입니다.

정리

• 주소 지정 방식은 피연산자의 값을 어디서 찾을지 정하며, 실제로 접근하는 데이터의 주소를 유효 주소라고 합니다.
• 즉시와 레지스터 방식은 메모리를 읽지 않고, 직접과 레지스터 간접은 한 번, 간접은 두 번 읽습니다.
• 베이스 + 변위와 인덱스 방식은 레지스터의 값에 변위나 번호 × 원소 크기를 더하며, 배열 원소의 주소를 계산할 때 원소 크기를 곱해야 합니다.
• PC 상대 방식의 기준이 지금 명령어인지 다음 명령어인지는 ISA마다 다릅니다.
• 스택은 SP로 맨 위를 가리키는 LIFO 저장 방식이고, 함수 호출은 복귀 주소를 스택에 넣어 중첩 호출에서도 올바른 곳으로 돌아갑니다.

연습 문제

1. 한 번 읽기와 두 번 읽기

R1 = 24, M[24] = 40, M[40] = 7입니다. R1, [R1], [[R1]]의 값과 각각 데이터 메모리를 몇 번 읽는지 쓰세요. 원소 하나가 2바이트인 배열이 주소 80부터 있을 때, 번호가 5인 원소의 주소도 구하세요.

2. 복귀 주소를 레지스터 하나에 두면

복귀 주소를 스택 대신 레지스터 RA 하나에만 저장하는 CPU에서, 주 프로그램이 함수 f를 부르고 f가 다시 함수 g를 부르면 어떻게 될까요? f와 g가 RA를 따로 보관하지 않는다고 합시다.

3. PC 상대 분기의 기준

주소 200에 있는 4바이트 분기 명령어에 변위 −12가 적혀 있습니다. 기준이 이 명령어의 주소인 CPU와 다음 명령어의 주소인 CPU에서 각각 어디로 분기하나요?

주소를 계산하다 헷갈리면 대괄호를 한 겹씩 벗기며 그때마다 메모리를 읽는지 적어 보세요. 다음 장의 메모리 계층과 주기억장치에서는 같은 주소에 접근하더라도 데이터가 어느 기억장치에 있느냐에 따라 걸리는 시간이 크게 달라지는 이유를 다룹니다.