[컴퓨터 구조] 2-8. 하드웨어의 프로시저 지원

Supproting Procedures in Computer Hardware

---

프로시저(Procedure)나 함수는 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화하는 방법 중의 하나이다. 프로시저는 프로그래머가 한 번에 한 부분씩 집중해서 처리할 수 있게 해 준다. 인수(Parameter)는 프로시저에 값을 보내고 결과를 받아 오는 일을 하므로, 프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할을 한다. 프로시저는 소프트웨어에서 추상화를 구현하는 방법 중의 하나이다.

 

Procedure Calling

프로그램이 프로시저를 실행할 때 다음과 같은 여섯 단계를 거친다.

1. 프로시저가 접근할 수 있는 곳에 인수를 넣는다.
2. 프로시저로 제어를 넘긴다.
3. 프로시저가 필요로 하는 메모리 자원을 획득한다.
4. 필요한 작업을 수행한다.
5. 호출한 프로그램이 접근할 수 있는 장소에 결과값을 넣는다.
6. 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 위치로 제어를 돌려준다.

 

Register Usage

레지스터는 데이터를 저장하는 가장 빠른 장소이므로 가능한 많이 사용하는 것이 바람직하다.

• $a0 ~ $a3: 전달할 인수를 가지고 있는 인수 레지스터 4개
• $v0 ~ $v1: 반환되는 값을 갖게 되는 값 레지스터 2개
• $ra: 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터 1개
• $a0 – $a3: arguments (reg’s 4 – 7)
• $v0, $v1: result values (reg’s 2 and 3)
• $t0 – $t9: temporaries
  Can be overwritten by callee
• $s0 – $s7: saved
  Must be saved/restored by callee
• $gp: global pointer for static data (reg 28)
• $sp: stack pointer (reg 29)
• $fp: frame pointer (reg 30)
• $ra: return address (reg 31)

 

Procedure Call Instructions

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

jal(jump-and-link) 명령어는 지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 $ra 레지스터에 저장한다.

jal		ProcedureAddress

jal에서 link는 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 뜻이다. 레지스터 $ra에 기억되는 이 링크를 복귀 주소(return address)라고 부른다. 한 프로시저가 여러 곳에서 호출될 수 있으므로 복귀 주소는 꼭 필요하다.

 

프로시저에서 복귀할 때 jr(jump register) 명령을 이용한다.

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

jr		$ra

호출 프로그램(caller)은 $a0 ~ $a3에 전달할 인수값을 넣은 후 jal X 명령을 이용해서 프로시저 X(callee)로 점프한다.

callee은 연산을 끝내고 그 결과를 $v0 ~ $v1에 넣은 후 jr $ra 명령을 실행하여 복귀한다.

 

내장 프로그램 개념은 현재 실행 중인 명령어의 주소를 기억하는 레지스터를 필요로 한다.

보통 프로그램 카운터(Program Counter)라고 하며 줄여서 PC라고 많이 부른다.

jal 명령은 프로시저에서 복귀할 때 다음 명령어부터 실행하도록 PC + 4를 레지스터 $ra에 저장한다.

 

Using More Registers

register spilling에 이상적인 자료구조는 스택(stack)이다. 스택에는 다음 프로시저가 spill할 레지스터를 저장할 장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가리키는 포인터가 필요하다.

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

 

스택은 높은 주소에서 낮은 주소 쪽으로 향한다. 그러므로 스택에 push를 할 때는 스택 포인터 값을 감소시켜야 하고, 스택에서 pop할 때는 스택 포인터 값을 증가시켜야 한다.

 

Compiling a C Procedure - Leaf Procedure Example

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

• Argument g, h, i, j는 register $a0, $a1, $a2, $a3에 해당한다.
• f는 $s0에 해당한다.
• 결과값은 $v0 레지스터에 저장된다.

컴파일된 프로그램은 다음과 같은 Procedure label로부터 시작된다.

leaf_example:

다음 단계는 프로시저가 사용할 레지스터 값을 저장하는 것이다.

임시 레지스터를 사용하고 스택에 세 워드를 저장할 자리를 만든 후 값을 저장한다.

addi	$sp, $sp, -12			# adjust stack to make room for 3 items
sw		$t1, 8($sp)				# save register $t1 for use afterwards
sw		$t0, 4($sp)				# save register $t0 for use afterwards
sw		$s0, 0($sp)				# save register $s0 for use afterwards

 

아래 그림은 프로시저 호출 전후와 프로시저 실행 중의 스택의 상태를 보여준다.

The values of the stack pointer and the stack (a) before, (b) during, and (c) after the procedure call. Th e stack pointer always points to the “top” of the stack, or the last word in the stack in this drawing.

다음으로 (g + h) - (i + j)가 연산된다.

add $t0, $a0, $a1			# register $t0 contains g + h
add $t1, $a2, $a3			# register $t1 contains i + j
sub $s0, $t0, $t1			# f = $t0 – $t1, which is (g + h)–(i + j)

 

f를 반환하기 위해 f를 결과값 레지스터에 복사한다.

add $v0, $s0, $zero			# returns f ($v0 = $s0 + 0)

 

호출 프로그램으로 되돌아가기 전에 저장해 두었던 값을 스택에서 pop 하여 레지스터를 복구한다.

lw		$s0, 0($sp)				# restore register $s0 for caller
lw		$t0, 4($sp)				# restore register $t0 for caller
lw		$t1, 8($sp)				# restore register $t1 for caller
addi	$sp, $sp, 12			# adjust stack to delete 3 items

 

프로시저는 점프 명령으로 끝난다.

jr	$ra				# jump back to calling routine

 

 

Nested Procedures (Non-Leaf Procedures)

다른 프로시저를 호출하지 않는 프로시저를 Leaf Procedure라 한다. 프로시저도 프로시저를 호출할 수 있고 자기 자신을 호출하는 recursive 프로시저도 있다. 프로시저에서 레지스터를 사용할 때 조심해야 하는 것처럼 Non-Leaf Procedrue를 호출할 때 더욱 조심해야 한다.

 

A프로시저가 B프로시저를 호출한다고 가정한다면, A가 다 끝나기도 전에 B에서 레지스터 사용에 충돌이 발생할 수 있다. 이러한 문제를 예방하지 않는다면 충돌로 인하여 A 프로시저가 caller프로그램으로 돌아가지 못한다.

 

방법은 값이 보존되어야 할 모든 레지스터를 스택에 넣는 것이다. Stack Pointer $sp는 스택에 저장되는 레지스터 개수에 맞추어 조정된다. 복귀한 후에는 메모리에서 값을 꺼내 레지스터를 복구하고 이에 맞추어 $sp를 다시 조정한다.

 

Compiling a Recursive C Procedure - Non-Leaf Procedures

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

• n은 레지스터 $a0에 해당한다.
• 결과는 $v0에 저장된다.

프로시저 레이블로 시작하며, 복귀 주소와 $a0를 스택에 저장한다.

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

 

fact가 처음 호출되었을 때 sw는 fact를 호출한 프로그램의 주소를 저장한다.

다음으로 n이 1보다 작은지 검사해서 n >= 1 이면 L1으로 가도록 실행한다.

slti	$t0, $a0, 1			# test for n < 1
beq		$t0, $zero, L1		# if n >= 1, go to L1

 

n이 1보다 작으면 $v0에 1을 넣는다. 이때 0에 1을 더해서 $v0에 넣는다. 복귀하기 전에 스택에 저장된 값 2개를 버리고 복귀 주소로 점프한다.

addi	$v0, $zero, 1		# return 1
addi	$sp, $sp, 8			# pop 2 items off stack
jr		$ra					# return to caller

 

n이 1보다 작지 않으면, n을 감소시키고 감소된 n으로 fact를 호출한다.

L1:	addi	$a0, $a0, –1		# n >= 1: argument gets (n – 1)
	jal		fact				# call fact with (n –1)

 

다음은 호출한 프로그램으로 되돌아가는 부분이다. 먼저 Stack Pointer를 사용해서 이전의 복귀 주소와 n을 복구한다.

lw		$a0, 0($sp)			# return from jal: restore argument n
lw		$ra, 4($sp)			# restore the return address
addi	$sp, $sp, 8			# adjust stack pointer to pop 2 items

 

다음으로 인수 $a0와 $v0의 현재 값을 곱해서 $v0에 넣는다.

mul		$v0, $a0, $v0		# return n * fact (n – 1)

 

마지막으로 복귀 주소를 이용해 되돌아간다.

jr		$ra			# return to the caller

What is and what is not preserved across a procedure call

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		# return 1
    addi	$sp, $sp, 8			# pop 2 items off stack
    jr		$ra					# return to caller
L1: addi	$a0, $a0, –1		# n >= 1: argument gets (n – 1)
    jal		fact				# call fact with (n –1)
    lw		$a0, 0($sp)			# return from jal: restore 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

 

Allocating Space for New Data on the Stack

레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수를 저장하는 데도 스택이 사용되기 때문에 문제가 복잡해진다. 프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을 프로시저 프레임(procedure frame)라고 부른다. 

Local Data on the Stack

Illustration of the stack allocation (a) before, (b) during, and (c) after the procedure call.

프레임 포인터($fp)는 프레임의 첫 번째 워드를 가리키며, 스택 포인터($sp)는 스택의 맨 위를 가리킨다. 프로시저를 호출하면 저장된 모든 레지스터와 메모리 상주 지역 변수를 넣기 위한 공간을 스택에 만든다. 스택 포인터는 프로그램이 실행되면서 변할 수 있으므로 변수 참조는 변하지 않는 프레임 포인터를 사용하는 것이 좋다. 스택 포인터를 사용해도 약간의 주소 계산이 추가되면 변수 접근이 가능하다. 스택에 지역 변수를 저장하지 않는 프로시저의 경우 프레임 포인터 값을 바꾸고 나중에 복구하는 일을 생략함으로써 시간을 절약한다. 프레임 포인터를 사용하는 경우는 호출할 때의 $sp 값으로 $fp를 초기화하고 나중에 $fp로 $sp를 복구한다.

 

MIPS 소프트웨어 중에는 프레임 포인터(frame pointer, $fp)가 프로시저 프레임의 첫 번째 워드를 가리킨다. 스택 포인터 값이 프로시저 내에서 바뀔 수도 있으므로 메모리 내 지역 변수에 대한 변위는 변수가 프로시저 어느 부분에서 사용되느냐에 따라 달라질 수 있다. 이런 이유로 프로시저가 더 이해하기 어려워지는데, 프레임 포인터를 사용하면 프레임 포인터가 변하지 않는 베이스 레지스터 역할을 하므로 지역 변수 참조가 간단해진다. 

 

Allocating Space for New Data on the Heap

The MIPS memory allocation for program and data.

스택은 최상위 주소에서부터 시작해서 아래쪽으로 향한다.

최하위 주소 부분은 reserved되어 있다.

기계어 코드, 즉 프로그램 코드는 text segment에 들어간다.

코드 위쪽에는 static data segment가 있는데, 상수, static 변수가 들어간다.

linked list 같이 크기가 변하는 자료구조를 heap에 저장한다.

스택과 힙이 서로 마주 보는 방향으로 할당하기 때문에 메모리를 효율적으로 사용할 수 있다.

 

malloc()은 힙에 공간을 할당한 후 이 공간을 가리키는 포인터를 결과값으로 보내 준다.

free()는 포인터가 가리키는 힙 공간을 반납한다.

• memory leak
  사용이 끝난 공간을 free 해주지 않을 때 발생, 메모리 부족으로 운영체제가 붕괴될 수 있다.
• dangling pointer
  공간을 너무 일찍 반납하면 프로그램 의도와 상관없이 엉뚱한 것을 가리킬 수 있다.