명령어 (16) - 프로시져 / 함수 (2)

1. Non Leaf Procedure

• Non Leaf Procedure는 스택프레임에 반드시 ra (반환 주소)를 저장해야한다. (덮어씌이기 때문에)
• 필요에 따라서 파라미터들도 덮어 쓰여질 수 있으니, 스택에 저장해야 하는 경우도 있다.
• 리턴될 때는, 메모리에서 ra를 로드한 뒤에, 다시 스택포인터를 올려주고 ra로 jump해야한다.
• recursion이 아닌 코드는 Non Leaf Procedure는 이전 글의 코드를 보면 확인할 수 있다.

 

2. Non Leaf Procedure Example

.data
n_msg : .asciiz "n : "
result_msg : .asciiz "result : "
line_msg : .asciiz "\n"

.text
.globl main

# int factorial(int n){
#	
#	printf("n : %d\n", n);
#
#	if(n != 1)
#		return n * factorial(n-1);	
#	else
#		return 1;
# }
# 
# int main(){
#	factorial(5);
#	return 0;
# }


main:
	li $a0 5		# factorial(5)
	li $v0 1	
	jal factorial
	
	move $a0 $v0		# a = result;
	la $a1 result_msg	# printf("%d", a);
	jal print
	
	li $v0 10		# exit
	syscall 
	
factorial:
	addi $sp $sp -4		# make stack frame
	sw $ra 0($sp)		# save ra

	la $a1 n_msg		# printf("n : %d\n", a0);
	jal print
	
	bne $a0 1 reccurssion	# if (n != 1) recurssion
	lw $ra 0($sp)		# load return address
	addi $sp $sp 4		# delete stack frame
	jr $ra	

reccurssion:
	mul $v0 $v0 $a0		#else n * factorial(n - 1)
	addi $a0 $a0 -1	
	jal factorial
	
	lw $ra 0($sp)		# load return address
	addi $sp $sp 4		# delete stack frame
	jr $ra			# jump to r	

print:
	addi $sp $sp -8
	sw $a0 4($sp)
	sw $v0 0($sp)
	
	li $v0 4		# print string
	move $a0 $a1		# printf(a1);
	syscall
	
	li $v0 1		# print integer
	lw $a0 4($sp)		# printf("%d", n);
	syscall
	
	li $v0 4		# print string
	la $a0 line_msg		# printf("\n);
	syscall
	
	lw $a0 4($sp)
	lw $v0 0($sp)
	addi $sp $sp 8
	jr $ra

• 직접 작성한 팩토리얼 함수의 코드이다 재귀함수의 경우 return address 관리를 확실히 해줘야하는데,
• 가장 처음에 n = 5일때부터 1이 되기 전까진, bne조건에 걸려서 recurssion: 태그로 이동하게 된다.
• recurssion 태그로 이동하면, 현재 n을 곱하고 n을 n-1로 만들고 다시 recurssion으로 jump and link한다.
• 이 때 jal하면서, 같은 태그 내의 다음 주소인 lw ra 0(sp)를 ra 레지스터에 담으면서 jal한다. (핵심)
• 때문에 스택포인터는 계속 4칸씩 내려가면서 recurssion 태그 내의 lw부분을 저장시킨다.

 

• n = 1이 되면 ra를 불러오고 스택포인터를 4칸 올리는데, 거기엔 lw부분의 코드 주소가 저장되어있다.
• 따라서 계속 다시 4칸씩 올라가면서 계속 같은부분 (recurssion 태그의 lw부분)을 반복하고, 최종적으로
• 가장 처음에 저장한 main함수로 빠져나가는 ra주소를 만나면 메인함수로 빠져나가게 된다.

 

3. Register Usage

• a0 ~ a3 : 파라미터 전달용으로 사용
• v0, v1 : 리턴값 전달용으로 사용
• t0 ~ t9 : Callee에 의해 변경될 수 있는 레지스터
• s0 ~ s7 : Callee에 의해 저장/로드 될 수 있는 레지스터 (지역변수용으로 사용)
• gp : 글로벌 포인터 (Data 영역에 엑세스하기 위해 사용되는 포인터)
• sp : 스택 포인터 (스택이 계속 아래로 내려감에 따라 현재 위치를 기록)
• fp : 프레임 포인터 (스택프레임의 최 상단을 기록하는 포인터)
• ra : 리턴 주소 (jal시 해당하는 명령어의 바래 아래 명령어 주소를 기록)
• pc : 프로그램 카운터 (다음에 실행할/실행 중인 명령어의 주소가 담겨있음)

 

4. Activation Record (Stack Frame)

[그림] Activation Record

• 우리가 함수를 만들 땐, 아래와 같이 공간을 만들어야하는데 (고급언어는 자동으로 만들어짐)
• 함수마다 return address와 argument, variable등이 저장되는 공간을 통틀어서 activation record 혹은
• stack frame이라고 부른다. (우리가 고급언어에서 알고 있었던 그 스택프레임이 맞다)
• sp는 stack pointer의 줄임말로 스택 프레임의 가장 아랫부분을 가리키는 포인터로 사용되며,
• fp는 frame pointer의 줄임말로 스택 프레임의 구장 윗부분을 가리키는 포인터로 사용된다.

 

5. Memory Layout

[그림] 메모리 레이아웃

• 메모리에 프로그램이 올라갈 때에는 Text영역에 소스코드, Data영역에 데이터, BSS영역에는 전역변수,
• 그리고 그 위에는 동적할당을 위한 Heap과 지역변수 및 스택프레임을 위한 Stack이 존재한다.
• 자세한 설명은 여기를 참고하면 된다. (이전에 작성한 Memory Layout 관련 게시글)

 

6. Reference

컴퓨터구조