Written by JS970
on June 12, 2023

Subprogram Implementation

Subprogram Linkage

서브프로그램 연결

서브프로그램 호출 - call
서브프로그램 복귀 - return

서브프로그램 호출 시 해야 할 작업

data 처리
- 호출하는 서브프로그램의 상태 저장
- 인수 전달 작업
- 복귀할 주소 전달
control
- 호출되는 프로그램으로 분기

서브프로그램 복귀 시 해야 할 작업

data 처리
- 필요에 따라 형식인수 값 복사(outer parameter)
- 함수의 경우, 결과 값 전달
- 호출한 서브프로그램의 상태 복귀
control
- 호출한 서브프로그램으로 분기

Activation Record

서브프로그램을 호출할 때는 아래와 같은 공간이 필요하다.
- 호출자의 상태 정보를 보관할 공간
- 인수를 저장할 공간
- 함수의 반환 값을 저장할 공간
- 복귀할 주소를 저장할 공간
활성 레코드(activation record)란 수행중인 서브프로그램에서 코드를 제외한 부분이 저장되는 형태이다.
활성 레코드 틀 자체는 정적으로 결정 가능하다.
활성 레코드 인스턴스란 활성 레코드가 구체적으로 구축된 것이다.
- 활성 레코드 인스턴스는 실행 시 필요에 따라 생성 및 소멸된다.
- 활성 레코드 인스턴스를 활성 레코드라고 부른다.

활성 레코드 - 정적 할당

아래 그림은 FORTRAN 77의 활성 래코드 구조이다.
호출 여부와 관계없이 미리 서브프로그램을 만들어 static segment로 할당했으므로 재귀 호출을 허용하지 않는다.
활성 레코드를 정적으로 할당 가능하다.

활성 레코드 - 동적 할당

아래 예시 Ada 코드를 바탕으로 활성 레코드 형태에 대해 알아보자.

procedure Main_2 is
	X: Integer;
	procedure Bigsub is
		A, B, C: Integer;
		procedure Sub1 is
			A, D: Integer;
			begin --Sub1
				A:=B+C;
			end;
		procedure Sub2(X: Integer) is
			B, E: Integer;
			procedure Sub3 is
				C, E: Integer;
				begin --Sub3
					Sub1;
					E:=B+A;
				end;
			begin --Sub2
				Sub3;
				A:=D+E;
			end;
		begin --Bigsub
			Sub2 (7);
		end;
	begin --Main_2
		Bigsub;
	end;

아래 그림은 예시 Ada 프로그램의 활성 레코드 구조이다.
재귀 호출이 가능하다.
static scoping rules를 지원한다.
활성 레코드의 형태는 같지만 크기는 각 서브프로그램마다 다르다.
서브프로그램 호출 시 동적으로 활성 레코드가 생성된다.
활성 레코드 필드는 프레임 포인터(FP)와 offset의 조합으로 참조한다.
활성 레코드에는 아래와 같은 내용들이 저장된다.
- Local variables & Parameters
- Dynamic Link : 호출자 활성 레코드의 FP를 가리킨다.
- Return address : 정적 부모(static parent)의 FP를 가리킨다.
- return value(함수의 경우)
점선은 static link를 통해 정적 부모를 가리키는 것을 의미한다.
실선은 dynamic link를 통해 호출자를 카리키는 것을 의미한다.

Terminology

동적 체인 : 활성 레코드 스택 상에서 인접한 동적 링크들을 차례로 연결한 것. 리스트 형태이다.
정적 체인 : 활성 레코드 스택 상에서 정적 링크들로 연결된 체인. 트리 형태이다.
- C언어의 경우 함수 중첩을 허용하지 않으므로 정적 링크가 필요 없다.
local offset : 지역 변위
- 활성 레코드 시작 부분에서 stack dynamic 변수 위치까지의 변위
- 컴파일 시간에 계산 가능하다.

비지역 변수 참조

지역변수는 항상 자신의 활성 레코드 인스턴스에서 찾을 수 있다.
참조되는 비지역 변수는 활성레코드 스택 어딘가에 존재한다.
어떤 영역 규칙이든 활성레코드 스택을 찾아 보면 항상 비지역 변수를 찾을 수 있다.
- parent는 항상 active하기 때문이다.
비지역 변수의 참조를 위해서는 올바른 offeet과 올바른 활성 레코드를 찾는 것이 중요하다.
- FP와 offset을 이용해서 비지역 변수에 접근하기 때문
정적 영역규칙에 따른 비지역 참조 구현의 문제점
- 정적 부모의 활성 레코드가 인접해 있지 않을 수 있다.
- 정적 링크를 반복하여 거슬러 찾아가야 한다.
- 어떤 서브프로그램의 정적 체인은 모든 정적 조상을 포함한다.

정적 체인을 사용하여 비지역 변수를 참조하는 법

정적 깊이(static depth)를 이용한다. 이는 자신을 감싸고 있는 정적 영역의 개수를 의미한다.
비지역 참조의 체인 변위(chain offset)을 활용한다.
- 비지역 변수가 참조되는 지점의 정적 깊이와 해당 비지역 변수가 선언된 지점의 정적 깊이의 차를 의미
- 체인 변위만큼 정적 체인을 거슬러 올라가면 해당 변수의 활성 레코드 인스턴스를 찾을 수 있다.
체인을 거슬러 올라가는 비용은 체인 변위가 클수록 크다.
정적 체인 방법의 장점
- 구현하기 쉽다
- 각 활성 레코드에 하나의 링크만 유지하면 되므로 공간 낭비가 적다.
정적 체인 방법의 단점
- 참조되는 비지역 변수가 선언된 블록의 중첩깊이와 참조 문장을 포함한 중첩깊이의 차이가 크다면 참조 시간 부담이 커진다.
- 비지역 변수의 참조 시간이 변수에 따라 다르기 때문에 응답 시간이 중요한 real-time application에서는 불리하다.

디스플레이 방법

여러 정적 링크들을 별도의 스택에 관리한다.
참조 환경의 모든 변수는 이 스택이 가리키는 활성 레코드 내에 존재한다.
디스플레이는 현재 수행 중인 블록과 이 블록의 정적 조상에 대한 활성 레코드를 가리키는 주소들로 이루어진 스택이다.
디스플레이 변위는 해당 변수가 선언된 서브 프로그램의 정적 깊이와 동일하다. 즉 static depth가 3인 경우 display[3]에 저장된다.
디스플레이에 의한 서브프로그램 호출 및 복귀 과정은 다음과 같다.
1. 호출되는 서브프로그램의 정적 깊이가 k라면 display[k]에 서브프로그램의 활성 레코드 인스턴스 주소를 저장한다.
2. 만약 display[k] 위치에 이미 다른 서브프로그램을 저장 중인 경우 원래 있던 항목을 호출되는 서브프로그램의 활성 레코드 내에 backup한다.
3. 서브프로그램 복귀 시에는 현재 활성레코드 내에 백업되었던 display[k]를 복구한다.
display가 어떻게 변화할 지 알 수 없으므로 모든 경우에 대해 백업을 진행해야 한다.
- 애초에 활성 레코드가 저장되어 있지 않은 상태 재외

정적 체인 방법과 디스플레이 방법의 비교

지역변수 참조는 동일하다.
비지역 변수 참조에 있어 현재 활성 레코드와 한 단계 차이날 경우 두 방법의 비용이 동일하지만 그 이상의 경우 디스플레이 방법이 더 유리하다.
서브프로그램 호출에 있어 디스플레이 방법의 경우 정적 깊이 차가 클수록 정적 체인 방법에 비해 유리하다.
서브프로그램 복귀에 있어 정적 체인 방법과 디스플레이 방법 모두 상수 시간을 보장한다. 하지만 디스플레이 방법의 경우 백업 시간을 추가로 요구하므로 시간이 조금 더 소요된다.
결론적으로 비지역 변수 참조가 빈번하다면 디스플레이 방법이 유리하고, 거의 일어나지 않는다면 정적 체인 방법이 더 유리하다.

동적 영역규칙 - Deep Access

해당 변수를 찾을 때까지 동적 링크를 계속해서 거슬러 올라간다.
거슬러 올라갈 체인 길이가 정해져 있지 않으므로 시간을 보장할 수 없다.
활성 레코드에 변수 이름을 기록해야 한다.

동적 영역규칙 - Shallow Access

참조할 변수를 공용 공간에 저장한다.
Variable Stack, 또는 Central Table방식으로 구현한다.
아래는 Variable Stack방식으로 구현하는 도식이다.
- 디스플레이 방법과 유사한 면이 있다.
- 각 변수 별로 스텍을 가지며, stack.top()을 참조하여 비지역 변수에 접근한다.

Top