8. 하드웨어의 프로시저 지원

Reference :
- 컴퓨터 구조 및 설계 MIPS EDITION [6판] / David A. Patterson / 한빛에듀
- 건국대학교 컴퓨터구조 강의 / 박능수 교수님
- https://developbear.tistory.com/ (김베어의 개발일지)

프로시저 (procedure)

프로시저(procedure)는 제공되는 인수(parameter)에 따라서 특정 작업을 수행하는 서브루틴을 말한다.

 

프로시저는 프로그래밍에서 함수(function)와 같다고 보면 되며,

이들은 프로그램을 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화하는 방법 중 하나이다.

 

인수는 프로시저에 값을 보내고 결과를 받아오는 일을 하므로,

프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할을 한다.

 

따라서 프로시저는 소프트웨어의 추상화를 구현하는 방법이다.

 

 

프로그램이 프로시저를 실행하는 6단계

 

메인 루틴을 Caller(호출 프로그램), 프로시저를 Callee(피호출 프로그램)이라고 하자.

 

1. Caller는 Callee가 접근할 수 있는 곳에 인수를 넣는다.

$a0 ~ $a3 레지스터 - argument 저장

 

2. Caller는 Callee에게 제어를 넘긴다.

 

3. Callee가 필요로 하는 메모리 자원(stack 또는 register)을 요청하여 확보한다.

 

4. Callee가 필요한 작업을 수행한다.

 

5. Caller가 접근할 수 있는 장소에 Callee가 결과 값을 넣는다.

$v0 ~ $v1 레지스터 - return variable 저장

 

6. Callee는 프로그램 내의 여러 곳에서 호출될 수 있으므로, Caller(원래 위치)에게로 제어를 돌려준다.

$ra - return address 저장

 

* 프로시저 호출이 다른 부분에 영향을 미쳐서는 안 되기 때문에

호출 프로그램이 사용하는 모든 레지스터는 복귀하기 전에 프로시저 호출 전의 상태로 되돌려 놓아야 한다.

---

레지스터는 데이터를 저장하는 가장 빠른 장소이기 때문에 가능한 한 많이 사용하는 것이 좋다.

MIPS에서는 다음의 프로시저 호출 관례에 따라 레지스터 32개를 할당한다.

 

• $a0 ~ $a3
  전달할 인수를 가지고 있는 인수 레지스터 4개
  
  
• $v0 ~ $v1
  반환되는 값을 갖게 되는 값 레지스터 2개
  
  
• $ra
  호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터 1개

 

레지스터의 역할

 

 

프로시저를 위한 명령어

 

MIPS 어셈블리 언어는 레지스터를 할당할 뿐만 아니라 프로시저를 위한 명령어도 제공한다.

 

- jal(jump-and-link) 명령어

지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 $ra 레지스터에 저장하는 명령이다.

즉, $ra 레지스터에 PC+4 값을 저장하는 것이다.

jal ProcedureAddress # jump and link

 

jal은 J-format을 따른다.

 

 

 

이름에서 link는 프로시저 종료 후 올바른 주소로 되돌아갈 수 있도록

호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 뜻이다.

 

- jr(jump register) 명령어

31번 레지스터 $ra에 기억되는 링크(link)를 복귀 주소(return address)라고 부른다.

한 프로시저가 여러 곳에서 호출될 수 있기 때문에 복귀 주소는 꼭 필요하다.

 

이것을 지원하기 위해서 MIPS는 jr 명령을 이용한다.

 

이 명령은 레지스터에 저장된 주소로 무조건 점프하라는 뜻이다.

jr $ra # return

즉, 저장된 return address(PC+4)로 복귀하게 되는 것이다.

 

jr 명령어는 R-format을 따른다.

 

---

레지스터 스필링(spilling)

컴파일러가 프로시저를 번역하는 데 레지스터의 개수가 부족한 경우 어떻게 될까?

 

컴퓨터가 갖고 있는 레지스터보다 프로그램에서 사용하는 변수가 더 많은 경우가 있다.

 

이때 컴파일러는 자주 사용되는 변수를 가능한 한 많이 레지스터에 넣고,

나머지 변수는 메모리에 저장했다가 필요할 때 꺼내서 레지스터에 넣는다.

 

자주 사용하지 않는 또는 한참 후에 사용할 변수를 메모리에 넣는 일을 레지스터 스필링(spilling)이라고 한다.

 

레지스터는 메모리보다 접근시간이 짧고 처리량도 많기 때문에

레지스터에 저장된 데이터를 사용하면 시간이 절약되고 사용하기도 편리하며, 에너지도 적게 든다.

 

따라서 좋은 성능과 에너지 절약을 위해서는 컴파일러가 레지스터를 효율적으로 사용해야 한다.

 

레지스터 스필링에 이상적인 자료구조는 스택(stack)이다.

스택은 후입 선출(Last-In-First-Out) 큐로 구성되었다.

 

스택에는 1. 다음 프로시저가 스필 할 레지스터를 저장할 장소나 2. 레지스터의 옛날 값이 저장된 장소를 표시하기 위해

가장 최근에 할당된 주소를 가리키는 포인터가 필요하며, 이 포인트를 스택 포인터(stack pointer)라고 부른다.

 

MIPS 소프트웨어는 스택 포인터를 위해 레지스터 29를 할당해 놓고 있으며, 이름은 $sp이다.

 

 

이 스택 포인터는 레지스터 값 하나가 스택에 저장되거나 스택에서 복구될 때마다 한 워드(word)씩 조정된다.

 

스택은 높은 주소에서 낮은 주소 쪽으로 성장하므로

스택에 푸시(push)할 때 스택 포인터 값은 감소, 스택에서 팝(pop)할 때 스택 포인터 값은 증가시켜야 한다.

* 참고 : 2022.07.08 - [Computer Science/Operating System] - [운영체제] Call Stack Frame & ESP, EBP 레지스터

 

1. 푸시(push) : 스택에 원소 추가

$sp = $sp - 4 # push

 

2. 팝(pop) : 스택에서 원소 제거

$sp = $sp + 4 # pop

 

 

 

스택을 통해서 프로시저들이 서로 같은 레지스터를 사용하지 않도록 해주어 레지스터 변형(register corruption)을 방지하게 된다.

 

즉, 레지스터 overwrite를 방지하기 위해

1. Callee 측에서 자신이 사용할 레지스터들에 저장된 데이터를 스택에 저장한 후 작업(task)을 수행하는 것이고,

2. Callee가 작업을 끝마치면 스택에 저장해놓은 데이터들을 다시 원래의 레지스터에 옮기고 난 다음에

    Caller에게 제어권을 넘기는 것이다.

 

 

다른 프로시저를 호출하지 않는 C 프로시저의 컴파일 (Leaf Procedure Example)

 

아래의 C 프로시저를 예시로 들어보자.

 

int leaf_example (int g, int h, int i, int j) 
{ 
    int f; 
    f = (g + h) - (i + j); 
    return f; 
}

 

다른 프로시저를 호출하지 않는 프로시저를 말단(leaf) 프로시저라고 한다.

 

이를 MIPS 어셈블리 언어로 번역하면 다음과 같다.

leaf_example:

    # adjust stack to make room for 3 items ($t1, $t0, $s0)
    addi $sp, $sp, -12		# 3 words = 12 bytes
    
    # save register for use afterwards
    sw   $t1, 8($sp)		# save $t1 on stack
    sw   $t0, 4($sp)		# save $t0 on stack
    sw   $s0, 0($sp)		# save $s0 on stack
    
    # Procedure body
    add  $t0, $a0, $a1
    add  $t1, $a2, $a3
    sub  $s0, $t0, $t1
    
    add  $v0, $s0, $zero	# Result
    
    # restore register for Caller
    lw   $s0, 0($sp)		# restore $s0
    lw   $t0, 4($sp)		# restore $t0
    lw   $t1, 8($sp)		# restore $t1
    
    # adjust stack to delete 3 items
    addi $sp, $sp, 12
    
    # jump back to calling routine
    jr   $ra			# Return

 

재귀 프로시저의 컴파일 (Non-Leaf Procedure Example)

 

프로시저는 다른 프로시저를 호출할 수 있으며, 자기 자신을 호출하는 재귀(recursive) 프로시저도 있다.

 

아래는 n 계승을 계산하는 재귀 프로시저이다.

 

int fact (int n) {
    if (n < 1) return 1;
    else return n * fact(n - 1);
}

 

이를 MIPS 어셈블리 언어로 번역하면 다음과 같다.

인수 n은 레지스터 $a0에 저장하며, 결과는 레지스터 $v0에 저장한다.

fact:
    addi $sp, $sp, -8 		# adjust stack for 2 items
    
    sw   $ra, 4($sp) 		# save the return address
    sw   $a0, 0($sp) 		# save the argument n
    
    slti $t0, $a0, 1 		# test for n < 1
    beq  $t0, $zero, L1 	# if n >= 1, go to L1
    
    addi $v0, $zero, 1 		# n < 1: result is 1
    addi $sp, $sp, 8 		# pop 2 items from stack
    jr   $ra 			# and return to Caller
    
L1: addi $a0, $a0, -1 		# n >= 1: argument gets (n - 1)
    jal  fact 			# recursive call with (n - 1)
    
    # 돌아갈 준비
    lw   $a0, 0($sp) 		# restore original argument n
    lw   $ra, 4($sp) 		# restore the return address
    addi $sp, $sp, 8 		# adjust stack pointer to pop 2 items
    
    mul  $v0, $a0, $v0 		# return n * fact(n - 1)
    
    jr   $ra 			# return to the Caller

---

프로시저 프레임 (Prodecure Frame)

레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수를 저장하는 데도 스택이 사용되기 때문에 문제가 복잡해진다.

 

프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을

프로시저 프레임(procedure frame) 또는 액티베이션 레코드(activation record)라고 부른다.

 

 

다음은 a. 프로시저 호출 전, b. 프로시저 호출 중, c. 프로시저 호출 후의 스택 할당 상태를 나타낸 그림이다.

 

* 프레임 포인터 $fp : 프로세저의 저장된 레지스터와 지역 변수의 위치를 표시하는 값

 

프레임 포인터($fp)는 프레임의 첫번째 워드를 가리키며, 스택 포인터($sp)는 스택의 맨 위를 가리킨다.

 

프로시저를 호출하면 저장해야 하는 모든 레지스터와 메모리 내의 지역 변수를 넣기 위한 공간을 스택에 만든다.

 

스택 포인터 값은 프로그램이 실행되면서 프로시저 내에서 바뀔 수 있기 때문에 변수 참조는 프레임 포인터를 사용하는 것이 좋다.

프레임 포인터는 변하지 않는 베이스 레지스터 역할을 하여 지역 변수 참조가 간단해진다.

 

프로시저를 호출할 때 $sp의 값으로 $fp를 초기화하고, 나중에 $fp로 $sp를 원상 복구한다.

---

MIPS의 메모리 할당 방식

 

스택에 저장되는 자동 변수 외에도 정적 변수와 동적 자료구조(malloc)를 위한 메모리 공간이 필요하다.

나머지 메모리 구조는 어떻게 사용될까?

 

Reserved

최하위 주소 부분은 사용이 유보되어 있다.

 

Test

MIPS 기계어 코드가 들어가는 부분이다.

전통적으로 텍스트 세그먼트(text segment)라 부른다.

 

Static data

정적 데이터 세그먼트(static data segment) 부분으로,

상수와 기타 정적 변수들이 이곳에 들어간다.

C에서 정적 배열은 그 크기가 고정되어 있어서 정적 데이터 세그먼트에 잘 맞는다.

 

힙(Heap)

malloc으로 할당한 배열이나 linked list처럼 늘어났다 줄어들었다하는 자료구조가 들어가는 부분이다.

힙은 스택과 마찬가지로 동적인 길이를 갖고 있고, 아래에서 위로 자란다.

 

스택(Stack)
자동 변수, 지역 변수가 저장되는 공간이다.

최상위 주소에서부터 시작해서 아래쪽으로 자란다.

 

스택과 힙은 서로 마주보면서 자라도록 할당하기 때문에 메모리를 효율적으로 사용할 수 있다.

---

C에서는 이러한 메모리 할당을 프로그램이 통제하는데, 이 부분이 흔하고도 까다로운 여러 버그의 근원이다.

 

malloc 후 free하는 것을 잊어 메모리 누출(memory leak)이 발생하여

메모리 부족으로 운영체제가 붕괴될 수 있고,

 

반면에 너무 일찍 반납하면

프로그램 의도와 상관없이 엉뚱한 곳을 가리키는 매달린 포인터(dangling pointer)가 발생한다.

 

Java에서는 이러한 버그를 피하기 위해 자동 메모리 할당과 가비지 컬렉션(garbage collection)을 사용한다.