C 프로그램이 어떻게 실행되고 있는지 살펴보고, procedure call의 과정에 대해 살펴보자.
Program Execution
프로그램을 실행한다는걸 각각의 레벨에서 다르게 설명할 수 있다.
1) HHL perspective
- Object level
: (function보다 high level) Object 레벨의 프로그래밍에서 object들끼리 서로 메세지를 주고 받는식으로 프로그램이 실행된다.
근데 이게 실행차원으로 내려오면 전부 function call, return으로 표현이 된다.
그래서 우리는 function call, return을 중점적으로 배울거임.
- Procedure level
: (Statement level보다 조금 높은 레벨에서 보면) 프로그램이 실행되는 것은 function call & return이 반복되는 것
- Statement level
: 프로그램이 실행되는 것은 statement가 하나씩 실행된다는 것
2) ISA perspective
- Machine instruction level(HW-SW interface)
: 머신 instruction이 하나씩 실행되는 것
- Procedure internal level(fetch, decode, execute)
: (interface level 말고 internal level에서 보면) fetch-decode-execute가 반복되는 것
- Procedure call
→ 함수를 call하는 것은 프로그램을 실행하는데 있어서 굉장히 기본적인 activity
→ 함수를 call 하는 것은 굉장히 heavy한 operation
많은 일을 요구한다. 따라서 머신은 procedure call return을 효율적으로 지원해야한다.
→ procedure level에서 프로그램이 실행된다는 것은 이런 모습
Leaf Procedure Example
- 대부분의 function은 부름을 당하기도 하고, 안에서 다른 function을 부르기도 해서
caller와 callee의 역할을 둘 다 한다.
- 하지만 leaf procedure는 callee의 역할만 한다. (위의 그림에서 D와 같은 함수)
leaf procedure가 되는 이유: function 안에서 다른 function을 call 하지 않기 때문
→ 이 함수는 내부에서 다른 function을 call 하지 않음
→ 즉 leaf procedure
Supporting Leaf Procedures
- 생각해야하는 이슈들
1) 파라미터를 어디에 놓고 return value를 어떻게 돌려받을 것인가?
2) return address를 어디에 명시할 것인지?
3) register usage에 대한 caller와 callee의 coordination
<leaf procedure이 컴파일 되는 과정>
- Caller에서
1) parameter를 적절한 위치에 놔둬야한다
(4개 넘으면 어쩔수없이 메모리 allocate 받아서 거기에 저장해야한다)
2) return address를 적절한 위치에 저장하고 Callee로 jump
jump and link instruction을 사용해서 (jal, jalr) 한 instruction으로 처리 할 수 있다.
return address는 ra(r31)에 저장된다.
- Callee에서(leaf example에서)
1) 필요한 레지스터를 스택에 백업한다.
→ instruction들을 실행시키기 위해선 reigster를 써야하는데 거기에 caller가 의미있는 값을 넣어놨을수도 있음.
→ 그래서 레지스터 안에 있는 값을 바꿀려면 기존의 값을 백업 해놓아야한다.
2) 원하는 task를 수행하고
4) return value를 적절한 위치에 놔두고
return address를 넘기는데 사용되는데 사용되는 전용 레지스터가 2개 할당되어 있음
→ return value는 하나인데 왜 전용 레지스터가 2개?
C 프로그래밍을 하다보면 double이라는 데이터 타입이 나오는데 double은 64비트 공간을 필요로 해서 register 1개에 저장 못함
→ 여러개의 item을 return 하고 싶을 땐 어떻게 하나?
structure로 마늗ㄹ어서 포인터를 return 하거나, external variable을 이요해서 return
4) 원래 레지스터값을 restore
5) caller로 돌아간다. (return address register에 있는 값으로 jump. jr $ra)
MIPS Register Conventions
→ $s, $t, $gp, $sp, $fp 이런 레지스터의 어셈블리 네임은 procedure의 call, return 관점에서 지어진거
→ procedure call, return이 얼마나 fundamental 한 개념인지 알 수 있다.
Leaf Procedure Example(1)
→ 실제로 t1. t0, s0에 caller가 의미있는 값을 담아놨는지는 모르지만 일단 확실해야하니까 스택에 저장해놓는거
→ 뒤에서 배우지만 실제로 이렇게 instruction을 많이 쓰진 않음.
Coordinating Register Usage
앞에서 봤을 때 function 안에서 register를 쓰기 위해 백업 & restore 하는 과정에 굉장히 복잡했음
이 부분을 어떻게 효율적으로 처리할 수 있는지 알아볼거다.
Coordinate Register Usage
- Caller와 Callee 사이의 레지스터 사용을 잘 조절해야한다. Caller와 Callee 는 같은 32개의 레지스터를 쓰기 때문에
잘 조절하지 않으면 서로의 데이터를 파괴할 수 있음
- Caller와 Callee 사이에 레지스터 사용을 조절하는 방식은 크게 2가지로 나눌 수 있음
1) Callee saving
→ 모든 register save 의 책임을 callee가 지는 것
→ Callee는 자기가 쓸 레지스터는 쓰기 전에 스택에 save 해야한다. (앞에서 본 예시와 동일)
→ 실제 Callee가 쓰는 레지스터 안에 Caller가 의미있는 데이터를 넣어놨는지는 컴파일러도 모르기 때문에 최악의 경우를 대비해 다 저장해놓음
(pessimistic: optimal하지 않고 최악의 경우를 대비해서 정확하게 동작)
2) Caller saving
→ 모든 register save 의 책임을 callee 가 지는 것
→ Callee는 레지스터를 자유롭게 쓰면 된다.
→ 실제 Caller가 의미있는 값을 넣어놓은 레지스터를 Callee가 쓸지는 레지스터도 모르기 때문에 최악의 경우를 대비해 다 저장해놓음
(얘도 pessimistic 하게 동작)
3) MIPS는 둘을 변형한 register coordination policy를 사용한다.
- MIPS policy
MIPS에서는 계산에 사용되는 register를 두 그룹으로 나눈다. 그리고 각각의 그룹에 다른 policy를 적용한다.
- Saved registers ($s): callee saving
Caller 입장에서 원래 값이 보존된다는 의미로 Saved Register 라는 이름이 붙음
모든 function은 s 레지스터를 쓰기 전에 stack에 save를 해놓아야한다. 하지만 main은 그냥 써도 된다. 자신을 call한 caller가 없으므로
- Temporary registers($t): caller saving
Caller 입장에서 원래 값이 보존되지 않는다는 의미로 Temporary Register 라는 이름이 붙음.
만약 내가 함수를 call하고 나서도 쓸 값이 t 레지스터에 들어있다면 이건 caller로서 내가 stack에 백업해놓아야한다.
- Saved registers ($s): callee saving
- Compiler 입장에서 function을 컴파일할 때 일단 함수 내에서 또 다른 함수를 call 하지 않는 이상 신경안써도 되는 t 레지스터를 우선적으로 쓴다.
- 그러다가 t 레지스터를 다 쓰면 s 레지스터를 백업을 한 다음 쓰도록 한다.
- s 레지스터까지 다 썼는데도 공간이 모자라면 느리지만 어쩔 수 없이 메모리를 써야한다.
- function 안에서 또 다른 function을 call 한 뒤에도 쓸 값들은 s 레지스터에 저장하기
Leaf Procedure Example(2)
→ 아까는 연산 중에 t0, t1, s0 쓰니까 전부 백업했었는데
→ t 레지스터는 백업 없이 자유롭게 써도 되므로 이제 s0에 대해서만 backup & restore를 진행하면 된다.
→ 그런데 생각해보면 s0 레지스터에 저장했다가 v0에 옮길 필요도 없음. 이렇게 되면 backup & restore 과정이 아예 필요없어진다.
→ 이렇게 leaf procedure는 간단하게 컴파일되어 돌아간다.
→ non-leaf procedure은 이것보다 조금 더 복잡함.
Uploaded by N2T