10장 부프로그램 구현 2017. 5. 31 순천향대학교 컴퓨터공학과 하 상 호

목차 부프로그램의 호출과 복귀의 의미 단순 부프로그램의 구현 스택-동적 지역변수를 갖는 부프로그램의 구현

부프로그램 호출과 복귀 의미 부프로그램 호출과 복귀 연산을 부프로그램 연결(subprogram linkage)라 한다. 부프로그램 연결의 의미에 기반하여 부프로그램 구현 방법 고안

부프로그램 호출과 복귀 의미 부프로그램 호출 연산 의미 매개변수 전달 방법 구현 포함 피호출자의 비정적 지역변수에 대한 기억공간 할당 호출자의 실행 상태를 저장(레지스터 값, CPU 상태, 환경 포인터) 복귀 주소를 피호출자에게 전달 (부프로그램 복귀 마련) 제어를 피호출자에게 전달 중첩 부프로그램 지원시, 피호출자에 가시적인 비지역변수 접근 마련

부프로그램 호출과 복귀 의미 부프로그램 복귀 연산 의미 매개변수가 출력 또는 입출력 모드이고, 복사-전달로 구현되는 경우 형식 매개변수의 값을 대응 실 매개변수로 전달 지역변수에 할당된 기억공간 해제 호출자의 실행 상태를 복원 제어를 호출자에게 반환

단순 부프로그램 구현 ‘단순’ 부프로그램의 특징 호출/복귀시 요구된 기억장소 호출자 또는 피호출자 수행 호출자 수행 부프로그램은 중첩되지 않는다. 모든 지역변수는 정적이다. => Fortran의 초기 버전 호출/복귀시 요구된 기억장소 호출자 상태정보, 매개변수, 복귀주소, 함수 반환 값, 부프로그램에서 사용되는 임시 기억장소 부프로그램 연결의 프롤로그(prologue) 호출(call)의 의미 . 호출자의 실행 상태를 저장 . 매개변수를 평가하고 전달 . 복귀 주소를 피호출자에게 전달 . 제어를 피호출자에게 전달 호출자 또는 피호출자 수행 호출자 수행 단순 부프로그램 구현 부프로그램 연결의 에필로그(epilogue) 복귀(return)의 의미 . 값-결과-전달의 매개변수가 사용되면, 형식 매개변수의 값이 대응 실 매개변수로 이동 . 부프로그램이 함수이면, 함수 값을 호출자에게 전달 . 호출자의 실행 상태를 복원 . 제어를 호출자에게 전달 피호출자 수행 호출자 또는 피호출자 수행

단순 부프로그램 구현 단순 부프로그램의 구성 용어 코드와 지역변수/매개변수/복귀 주소의 두 부분으로 구성 두 부분 모두 고정된 크기를 갖는다. 용어 활성화 레코드(AR: activation record) 실행중인 부프로그램의 비 코드 부분의 형식 (정적) 호출자의 실행 상태는 생략되어 있음 활성화 레코드 사례(ARI: activation record instance) 활성화 레코드의 구체적인 예

단순 부프로그램 구현 예제: 링커/로더가 MAIN이 호출될 때 구성 프로그램은 MAIN, A, B, C로 구성 각 부프로그램의 ARI는 고정된 크기이므로 정적 할당 부프로그램의 ARI는 단지 한 개만 존재 가능(재귀 부프로그램이 허용되지 않기 때문) 링커/로더가 MAIN이 호출될 때 구성 MAIN에서 참조하는 A, B, C, 코드와 그 ARI를 파일로부터 찾아서 메모리에 배치하고, 부프로그램 호출에 대한 목적지 주소를 패치한다.

스택-동적 지역변수를 갖는 부프로그램 구현 스택-동적 지역변수를 갖는 부프로그램 특성 스택-동적 변수 포함 재귀 부프로그램 지원 컴파일러는 지역변수의 묵시적 할당과 해제를 수행하는 코드 생성 부프로그램 연결시 추가 고려사항 재귀 함수의 지원 - 한 부프로그램의 활성화가 동시에 여러 개 존재 가능 - 한 개의 코드와 여러 개의 ARI 지원

스택-동적 지역변수를 갖는 부프로그램 구현 활성화 레코드 형식은 정해져 있으나(정적) 그 크기는 동적 가능 지역 변수가 스택-동적 배열을 포함하는 경우 ARI는 부프로그램이 호출될 때 동적으로 생성 지역변수 매개변수 동적 링크 복귀주소 호출자는 복귀주소, 동적 링크, 매개변수를 ARI에 먼저 배치 다음에 피호출자가 지역변수 배치 복귀주소 값은? 용 어 동적 링크(dynamic link) 호출자의 ARI 기준(첫 주소)에 대한 포인터 피호출자의 ARI를 제거하는데 사용 동적 링크를 제어 링크(control link)라고도 부름

스택-동적 지역변수를 갖는 부프로그램 구현 부프로그램 활성화는 예제 그 부프로그램의 ARI의 동적 생성 요구 마지막에 호출된 부프로그램이 먼저 종료 이러한 스택을 실행-시간 스택이라 불린다 예제 sub의 ARI void sub(float total, int part) { int list[5]; float sum; ... } 용 어 환경 포인터(EP: Environment Pointer) 현재 실행중인 프로그램 단위의 ARI의 기준 주소를 가리킨다 부프로그램 호출시에, 현재의 EP는 새로운 ARI의 동적 링크로서 저장되고, EP는 새로운 ARI의 기준 주소를 가리킨다. EP는 ARI에 포함된 데이터(매개변수, 지역변수) 내용을 접근하는 오프셋 주소의 기준으로 사용

부프로그램 호출/복귀 동작 수정 호출 동작 피호출자의 프롤로그 행동 ARI를 생성하여 스택에 배치 호출 프로그램 단위의 실행 상태 저장 매개변수를 계산하고 전달 복귀 주소를 피호출자에게 전달 제어를 피호출자에게 전달 피호출자의 프롤로그 행동 현재의 EP를 동적 링크로서 스택에 저장하고, EP를 새로운 ARI의 기준 주소로 설정 지역 변수를 할당 피호출자 ARI 지역변수 매개변수 동적 링크 복귀주소 호출자 ARI Top 지역변수 매개변수 동적 링크 복귀주소 EP Top 지역변수 매개변수 동적링크 복귀주소 EP 지역변수 매개변수 동적 링크 복귀주소

부프로그램 호출/복귀 동작 수정 피호출자의 에필로그 행동 Top 지역변수 매개변수 동적링크 복귀주소 피호출자의 에필로그 행동 값-결과-전달 매개변수나 출력-모드 매개변수 사용시, 그러한 매개변수의 값을 대응 실 매개변수로 전달 부프로그램이 함수이면, 함수 값은 호출자에게 접근 가능한 장소로 이동 스택 TOP 포인터를 현재의 EP – 1로 설정하고, EP를 피호출자 ARI의 동적 링크의 주소로 설정 호출자의 실행 상태를 복원 제어를 호출자에게 전달 EP 지역변수 매개변수 동적 링크 복귀주소 Top 지역변수 매개변수 동적 링크 복귀주소 EP

스택-동적 지역변수를 갖는 부프로그램 구현 예제 각 함수의 ARI는? fun1의 ARI fun2의 ARI float p; void fun1(float r) { int s, t; … <---------------- 1 fun2(s); ... } void fun2(int x) { int y; ... <----------------2 fun3(y); void fun3 (int q) { ... <----------------3 void main () { float p; … fun1(p); fun1의 ARI fun2의 ARI fun3의 ARI main -> fun1 호출 fun1 -> fun2 호출 fun2 -> fun3 호출

스택-동적 지역변수를 갖는 부프로그램 구현 예제 지점 1의 스택 내용 float p; void fun1(float r) { int s, t; … <---------------- 1 fun2(s); ... } void fun2(int x) { int y; ... <----------------2 fun3(y); void fun3 (int q) { ... <----------------3 void main () { float p; … fun1(p); main -> fun1 호출 fun1 -> fun2 호출 fun2 -> fun3 호출

스택-동적 지역변수를 갖는 부프로그램 구현 지점 2의 스택 내용 main -> fun1 호출 fun1 -> fun2 호출 fun2 -> fun3 호출 지점 2의 스택 내용 void fun1(float r) { int s, t; … <---------------- 1 fun2(s); ... } void fun2(int x) { int y; ... <----------------2 fun3(y); void fun3 (int q) { ... <----------------3 fun1의 ARI fun2의 ARI

스택-동적 지역변수를 갖는 부프로그램 구현 지점 3의 스택 내용 main -> fun1 호출 fun1 -> fun2 호출 fun2 -> fun3 호출 지점 3의 스택 내용 void fun1(float r) { int s, t; … <---------------- 1 fun2(s); ... } void fun2(int x) { int y; ... <----------------2 fun3(y); void fun3 (int q) { ... <----------------3

스택-동적 지역변수를 갖는 부프로그램 구현 지점 4의 스택 내용 main -> fun1 호출 fun1 -> fun2 호출 fun2 -> fun3 호출 void fun1(float r) { int s, t; … <---------------- 1 fun2(s); ... } void fun2(int x) { int y; ... <----------------2 fun3(y); ... ---------------4 void fun3 (int q) { ... <----------------3 fun1의 ARI fun2의 ARI 4

스택-동적 지역변수를 갖는 부프로그램 구현 지점 5의 스택 내용 main -> fun1 호출 fun1 -> fun2 호출 fun3 -> fun3 호출 지점 5의 스택 내용 fun1의 ARI fun2의 ARI void fun1(float r) { int s, t; … <---------------- 1 fun2(s); ... --------------- 5 } void fun2(int x) { int y; ... <----------------2 fun3(y); ... ---------------4 void fun3 (int q) { ... <----------------3 4

스택-동적 지역변수를 갖는 부프로그램 구현 동적 체인(dynamic chain) 지역 오프셋(local offset) 용 어 동적 체인(dynamic chain) 주어진 시점에서 스택에 포함된 동적 링크들의 집합 실행의 현 시점까지 도달한 동적 history를 반영 호출 체인(call chain)이라고도 함 지역 오프셋(local offset) 활성화 레코드의 시작시점으로부터 지역변수의 오프셋을 말함 지역 변수의 오프셋은 컴파일러가 결정 지역변수의 오프셋은 ARI 시작 지점(EP)으로부터 (매개변수 개수 + 2)의 위치부터 할당

스택-동적 지역변수를 갖는 부프로그램 구현 지역 오프셋 fun1에서 s, t의 지역 오프셋은? void fun1(float r) { int s, t; … fun2(s); ... } void fun2(int x) { int y; fun3(y); void fun3 (int q) {

스택-동적 지역변수를 갖는 부프로그램 구현 지역 오프셋 fun2에서 y의 지역 오프셋은? void fun1(float r) { int s, t; … fun2(s); ... } void fun2(int x) { int y; fun3(y); void fun3 (int q) {

재귀 함수 구현 재귀 예제 프로그램 int factorial(int n) { <----------------- 1 if (n <= 1) return 1; else return (n * factorial(n-1)); <----------------- 2 } void main() { int value; value = factorial(3); <----------------- 3 함수 반환 값이 추가 되었음에 유의 함수 값 매개변수 동적 링크 복귀 주소 factorial의 활성화 레코드 형식

재귀 함수 구현 재귀 예제 프로그램 main에서 factorial 첫번째 호출 고려사항 재귀 예제 프로그램 int factorial(int n) { <----------------- 1 if (n <= 1) return 1; else return (n * factorial(n-1)); <----------------- 2 } void main() { int value; value = factorial(3); <----------------- 3 factorial이 3번 호출 main에서 factorial 첫번째 호출 factorial에서 재귀적으로 factorial 두번째 호출 factorial에서 재귀적으로 factorial 세번째 호출

예제: factorial() 재귀 예제 프로그램 int factorial(int n) { 지점 1에서의 스택 내용? 재귀 예제 프로그램 int factorial(int n) { <----------------- 1 if (n <= 1) return 1; else return (n * factorial(n-1)); <----------------- 2 } void main() { int value; value = factorial(3); <----------------- 3 첫번째 호출 복귀주소가 main에 대한 것임에 유의

예제: factorial() 재귀 예제 프로그램 int factorial(int n) { 지점 1에서의 스택 내용? 재귀 예제 프로그램 int factorial(int n) { <----------------- 1 if (n <= 1) return 1; else return (n * factorial(n-1)); <----------------- 2 } void main() { int value; value = factorial(3); <----------------- 3 두번째 호출 복귀주소가 factorial에 대한 것임에 유의

예제: factorial() 재귀 예제 프로그램 int factorial(int n) { 지점 1에서의 스택 내용? 재귀 예제 프로그램 int factorial(int n) { <----------------- 1 if (n <= 1) return 1; else return (n * factorial(n-1)); <----------------- 2 } void main() { int value; value = factorial(3); <----------------- 3 세번째 호출

예제: factorial() 재귀 예제 프로그램 factorial 세번째 호출 완료 직전 고려사항 int factorial(int n) { <----------------- 1 if (n <= 1) return 1; else return (n * factorial(n-1)); <----------------- 2 } void main() { int value; value = factorial(3); <----------------- 3 factorial의 ARI가 스택에서 제거되기 이전 상태 factorial 세번째 호출 완료 직전 factorial 두번째 호출 완료 직전 factorial 첫번째 호출 완료 직전

예제: factorial() . 재귀 예제 프로그램 int factorial(int n) { <----------------- 1 if (n <= 1) return 1; else return (n * factorial(n-1)); <----------------- 2 } void main() { int value; value = factorial(3); <----------------- 3 지점 2에서의 스택 내용? 세번째 호출 완료 함수 값이 생성되었음에 유의 .

예제: factorial() 재귀 예제 프로그램 int factorial(int n) { <----------------- 1 if (n <= 1) return 1; else return (n * factorial(n-1)); <----------------- 2 } void main() { int value; value = factorial(3); <----------------- 3 지점 2에서의 스택 내용? 두번째 호출 완료 함수 값이 생성되었음에 유의

예제: factorial() 재귀 예제 프로그램 int factorial(int n) { <----------------- 1 if (n <= 1) return 1; else return (n * factorial(n-1)); <----------------- 2 } void main() { int value; value = factorial(3); <----------------- 3 지점 2에서의 스택 내용? 첫번째 호출 완료 함수 최종 값이 생성되었음에 유의

예제: factorial() 재귀 예제 프로그램 int factorial(int n) { <----------------- 1 if (n <= 1) return 1; else return (n * factorial(n-1)); <----------------- 2 } void main() { int value; value = factorial(3); <----------------- 3 지점 3에서의 스택 내용? factorial 종료 value 값이 생성되었음에 유의