컴퓨터시스템 05: 기계 수준 프로그래밍 3: 프로시저

글에 들어가기 앞서…

이 포스팅은 서울시립대학교 인공지능학과 백형부 교수님의 ‘컴퓨터시스템’ 강좌의 중간고사 이전 범위 수업 내용에 대한 정리를 담고 있습니다.

수업 자료 출처: Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, 3rd Edition

기계 수준 프로그래밍 III: 프로시저

프로그래밍에서 함수와 프로시저는 겉보기에 상당히 유사해 보이며, 실제로 많은 경우 그 구분이 크게 중요하지 않을 수 있습니다. 함수는 결과값을 반환하는 특징을 가지고 있으며, 프로시저는 반환값이 없이 일련의 작업을 수행하는데 그 목적이 있습니다. 이런 차이에도 불구하고, 두 개념은 종종 서로 교환 가능하게 사용될 수 있으며, 프로그램의 구현에 있어 큰 차이를 만들어내지 않는 경우가 많습니다.

하지만, 이런 미묘한 차이를 명확히 이해하는 것은 여전히 중요합니다. 이유는, 프로그래밍 언어의 구문과 의미론을 정확하게 파악하고, 더 정교하고 효율적인 코드를 작성하는 데 있어 필수적인 기반이 되기 때문입니다. 함수와 프로시저의 구분은 특히, 다양한 프로그래밍 패러다임과 언어에서 각기 다른 방식으로 구현되고 활용되기 때문에, 이를 정확히 아는 것이 프로그래머로서의 유연성과 깊이 있는 이해를 높이는 데 도움이 될 수 있습니다.

프로시저가 프로그램 내에서 실행될 때, 고려해야 할 여러 요소들이 있습니다. 첫째로, 프로그램의 제어 흐름을 관리해야 합니다. 이는 프로그램 카운터인 %rip(Instruction Pointer)가 다음에 실행할 명령어를 가리키도록 변경되어야 함을 의미합니다. 프로시저가 시작될 때는 %rip가 프로시저의 첫 번째 명령어를 가리키도록 설정되고, 프로시저가 종료되면 다시 메인 함수 또는 호출한 함수의 다음 명령어로 %rip가 올바르게 설정되어야 합니다.

데이터 전달도 중요한 과정입니다. 프로시저가 실행될 때 필요한 데이터는 레지스터를 통해 전달될 수 있으며, 프로시저의 결과 역시 레지스터를 통해 반환됩니다. 이 과정에서 호출하는 측과 호출되는 측 사이의 데이터 전달 방식을 명확히 정의해야 합니다.

메모리 관리도 중요한 요소입니다. 프로시저 내부에서 지역 변수가 선언되면, 이 변수들을 저장하기 위한 메모리 공간이 필요합니다. 이러한 지역 변수들은 주로 스택에 저장되며, 프로시저가 종료되면 이 사용된 메모리는 반환되어야 합니다. 이 과정은 메모리의 효율적 사용과 프로그램의 안정성을 보장하는 데 있어 중요합니다.

마지막으로, 프로시저 호출 시 발생할 수 있는 부수적인 상황들, 예를 들어 레지스터의 값이 변경되는 것을 방지하기 위한 레지스터의 저장 및 복원 같은 작업도 고려해야 합니다. 이는 프로시저가 실행되는 동안 원래의 프로그램 상태를 보존하고, 프로시저 종료 후 원활한 프로그램 실행을 위해 필요합니다.

이 모든 요소들이 구체적으로 어떻게 이루어지는지 자세하게 살펴보도록 하겠습니다.

스택 구조

위 설명은 컴퓨터 메모리의 주요 구성 요소 중 하나인 스택 구조에 관한 것입니다. 스택은 특이하게도 바닥 부분이 가장 큰 주소 값을 가지며, 꼭대기 부분이 가장 작은 주소 값을 가집니다. %rsp는 현재 스택의 꼭대기를 가리키는 레지스터로, 스택에 데이터가 추가되거나 제거될 때마다 %rsp의 값이 갱신됩니다.

데이터가 스택에 푸시(push)될 때는 %rsp가 감소하고(주소 값이 작아짐), 팝(pop)될 때는 %rsp가 증가합니다(주소 값이 커짐). 이러한 방식으로 %rsp는 스택의 현재 상태를 정확히 반영하며, 스택 기반의 데이터 관리와 프로시저 호출에서 중요한 역할을 수행합니다.

Calling Conventions

제어 흐름 변경

메인 프로세스에서 함수(프로시저)를 호출할 때, 현재 실행 중인 프로그램이 다음에 실행해야 할 명령어의 주소를 스택에 저장합니다. 이후, 프로시저의 시작 주소를 프로그램 카운터인 %rip 레지스터에 저장함으로써 프로시저의 명령어를 실행하게 됩니다. 프로시저의 실행이 완료되고 반환될 때는, 스택에서 이전에 저장해 두었던 주소를 팝하여 rip에 다시 할당함으로써 메인 프로세스의 실행을 중단했던 지점부터 명령어를 계속해서 읽어나가게 됩니다.

데이터 전달

위 어셈블리 코드는 메인 함수와 프로시저 간에 레지스터를 통한 데이터 전달 방식을 보여주는 예시입니다. 각 레지스터 별로 정해진 규약에 따라 데이터가 전달되는 것을 확인할 수 있습니다.

지역 데이터 관리

코드가 재진입 가능(Reentrant)하다는 것은, 함수가 전달 인자와 지역 변수를 사용하더라도, 함수를 호출할 때마다 그 상태가 독립적이라는 의미입니다. 즉, 동일한 함수가 동시에 여러 위치에서 호출되어도 각 호출이 서로의 실행에 영향을 주지 않습니다. 이러한 독립성은 함수 호출 시 사용하는 스택의 별도 영역, 즉 프레임(Frame)을 통해 관리됩니다.

위 예시에는 yoo(), who(), amI()라는 세 개의 프로시저가 있고, 그중 amI()는 재귀적인 프로시저입니다. amI() 프로시저가 재귀적으로 호출될 때 스택 공간이 어떻게 관리되는지를 도식화한 것을 더 자세히 설명하겠습니다.

1. call 명령어: 프로시저가 호출될 때, call 명령어가 실행됩니다. 이 명령어는 현재 실행 중인 프로시저의 다음 명령어 주소(즉, 반환 주소)를 스택에 푸시하고, 호출된 프로시저(amI())의 시작 주소로 프로그램 카운터를 이동시킵니다. 이 과정에서 새로운 스택 프레임이 생성되어, 호출된 프로시저의 매개변수, 지역 변수, 반환 주소 등의 정보가 스택에 저장됩니다.
2. 재귀 호출: amI() 프로시저가 자기 자신을 재귀적으로 호출할 때마다, call 명령어가 다시 실행되어, 새로운 스택 프레임이 스택에 추가됩니다. 이렇게 각 재귀 호출마다 스택에는 새로운 프레임이 계속 쌓이게 되며, 각 프레임은 그 호출에 해당하는 정보를 담고 있습니다.
3. ret 명령어: 프로시저의 실행이 종료되고, 반환될 때 ret 명령어가 실행됩니다. 이 명령어는 스택의 최상위에 있는 반환 주소를 팝하여, 프로그램 카운터에 그 주소를 로드합니다. 이 과정을 통해 프로시저의 실행이 완료된 후에 원래의 프로시저로 돌아갈 수 있습니다. 또한, 해당 프로시저의 스택 프레임도 스택에서 제거되어, 사용했던 메모리 공간이 반환됩니다.

프레임의 범위는 rsp(스택 포인터)와 rbp(베이스 포인터) 레지스터를 통해 정의됩니다. 여기서 rsp는 항상 필요하며, 스택의 현재 위치를 나타냅니다. 반면, rbp의 사용은 필수적이지 않으나, 함수 호출 시 스택 프레임의 기준점으로 활용되어 프로그램의 가독성과 디버깅을 용이하게 합니다.

위 예시는 C 언어로 작성된 함수입니다. incr 함수는 포인터 p로 전달된 변수의 값을 val만큼 증가시키고, 증가되기 전의 원래 값을 반환합니다. 이 함수가 다른 함수에 의해 호출되는 구조를 가정하겠습니다. 그리고, 구체적으로 이 과정이 어셈블리 언어 수준에서 어떻게 동작하는지 분석해보겠습니다.

call_incr 함수는 incr 함수를 호출하는데요, 어셈블리 코드를 통해 함수가 어떻게 실행되는지 자세히 살펴보겠습니다.

C

• v1 변수를 15213으로 초기화하고, incr 함수를 호출하여 v1을 3000만큼 증가시킵니다.

• incr 함수는 증가하기 전의 원래 v1 값을 v2에 저장하고, v1은 새로운 값(18213)으로 업데이트됩니다.

• 함수는 수정된 v1 값과 원래 v1 값을 더한 값을 반환합니다.

Assembly

• subq $8, %rsp: 스택 포인터를 조정하여 로컬 변수에 대한 공간을 확보합니다.

• movq $15213, (%rsp): 15213을 스택에 할당된 공간(%rsp가 가리키는 곳)에 저장하여 v1 변수를 초기화합니다.

• movl $3000, %esi: incr 함수에 전달할 두 번째 인수(3000)를 %esi 레지스터에 로드합니다.

• leaq (%rsp), %rdi: v1의 주소(스택 포인터 %rsp의 현재 값)를 첫 번째 인수로 사용하기 위해 %rdi 레지스터에 로드합니다.

• call incr: incr 함수를 호출합니다. 이 과정에서 v1의 값은 3000만큼 증가하고, 함수의 반환 값은 %rax 레지스터에 저장됩니다(증가 전의 v1 값).

• addq (%rsp), %rax: 스택에서 v1의 새로운 값(증가 후)을 불러와 %rax에 저장된 원래 값(증가 전)과 더합니다.

• addq $8, %rsp: 스택 포인터를 원래 위치로 복원합니다.

• ret: 함수에서 반환하며, 이때 %rax에 저장된 합계 값이 반환 값이 됩니다.

이러한 과정을 통해, call_incr 함수는 수정된 v1 값과 원래 v1 값을 더한 결과를 제대로 반환하게 됩니다.

레지스터 저장 규약(register saving conventions)

레지스터 저장 규약(register saving convention)은 함수 호출 시 사용되는 레지스터의 값이 보존되어야 하는지 여부를 결정하는 규칙입니다. 이 규약은 함수 호출에 따른 레지스터 사용의 예측 가능성을 높이고, 함수 간의 데이터 전달과 반환 값을 관리하는 데 도움을 줍니다.

Caller saved register

“Caller saved” 레지스터는 함수를 호출하는 측(caller)이 호출된 함수(callee)에 의해 변경될 수 있는 레지스터입니다. 함수 호출 전에 이 레지스터들의 값이 필요한 경우, caller는 이 값을 백업하고 함수 호출이 끝난 후에 복원해야 합니다. 이 규약에 속하는 주요 레지스터는 다음과 같습니다:

• rdi: 첫 번째 인수
• rsi: 두 번째 인수
• rdx: 세 번째 인수
• rcx: 네 번째 인수
• r8: 다섯 번째 인수
• r9: 여섯 번째 인수
• r10, r11: 임시 사용
• rax: 함수 반환 값

즉, 함수에 들어가는 모든 인수들, 그리고 함수 반환 용도로 사용되는 rax는 호출한 함수가 저장하고 있어야 합니다.

Callee saved register

반면에 “callee saved” 레지스터는 함수를 호출되는 측(callee)이 변경하기 전에 원래 값들을 보존해야 하는 레지스터입니다. 이는 callee 함수가 이 레지스터를 사용할 때, 원래 값을 변경하기 전에 백업하고 함수가 끝나기 전에 복원해야 함을 의미합니다. 이 규약에 속하는 주요 레지스터는 다음과 같습니다:

• r12, r13, r14: 일반 목적
• rbx: 일반 목적
• rsp: 스택 포인터
• rbp: 베이스 포인터

이 예시는 이전 예시와 다르게 %rbx 레지스터의 사용이 포함된 경우입니다. 기존의 %rbx 레지스터가 caller에서 중요한 정보를 담고 있을 가능성이 있기 때문에, 이 정보를 안전하게 보관하는 것이 필수적입니다. 그리고 이러한 정보 보관의 책임은 callee에게 있습니다. 따라서 call_incr2 함수의 어셈블리 코드에서 %rbx의 값을 스택에 저장하는 부분을 볼 수 있습니다.

Illustration of Recursion

그럼, 함수가 다른 함수를 호출하는 것이 아니라 스스로를 재귀적으로 호출하는 경우 어떻게 작동하는지, 어셈블리 코드를 통해 구체적으로 살펴보겠습니다.

이 어셈블리 코드는 재귀적으로 작동하는 pcount_r라는 함수를 나타냅니다. 이 함수의 목적은 주어진 정수(64비트)의 이진 표현에서 1의 개수를 세는 것입니다. 코드를 단계별로 분석해 보겠습니다.

1. movl $0, %eax: %eax 레지스터를 0으로 초기화합니다. 이 레지스터는 함수의 반환 값(1의 개수)을 저장하는 데 사용됩니다.

2. testq %rdi, %rdi: 인자로 받은 정수 %rdi를 자기 자신과 AND 연산합니다. 이 연산의 목적은 %rdi가 0인지 확인하기 위함입니다. 만약 %rdi가 0이라면, 즉 이진 표현에 1이 더 이상 없다면, 제어는 .L6으로 점프합니다.

3. je .L6: testq 명령어의 결과가 0이라면 (더 이상 세야 할 1이 없다면), .L6 레이블로 점프하여 함수를 종료합니다.

4. pushq %rbx: 현재 %rbx의 값을 스택에 백업합니다. %rbx는 재귀 호출 동안 사용되는 임시 값 저장소로 사용됩니다.

5. movq %rdi, %rbx: 인자로 받은 정수 %rdi를 %rbx로 복사합니다.

6. andl $1, %ebx: %ebx의 이진 표현에서 가장 낮은 비트(최하위 비트)만을 남기고 나머지를 0으로 설정합니다. 이는 현재 검사하는 비트가 1인지 아닌지를 확인하는 데 사용됩니다.

7. shrq %rdi: %rdi의 값을 오른쪽으로 1비트 쉬프트합니다. 이는 다음 재귀 호출에서 다음 비트를 검사하기 위함입니다.

8. call pcount_r: 변경된 %rdi 값으로 pcount_r 함수를 재귀적으로 호출합니다.

9. addq %rbx, %rax: 재귀 호출로부터 반환된 값(1의 개수)에 현재 검사한 비트의 값(0 또는 1)을 더합니다.

10. popq %rbx: 스택에서 %rbx의 이전 값을 복원합니다.

11. .L6: ret: 함수를 종료하고 호출한 곳으로 제어를 반환합니다.

요약하자면, pcount_r 함수는 주어진 정수의 이진 표현에서 1의 개수를 재귀적으로 계산하여 반환합니다. 이 과정에서 최하위 비트부터 시작하여 각 비트를 순차적으로 검사하고, 1의 개수를 누적하여 최종 결과를 반환합니다.